1 //===------- SemaTemplateDeduction.cpp - Template Argument Deduction ------===/
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //===----------------------------------------------------------------------===/
9 // This file implements C++ template argument deduction.
11 //===----------------------------------------------------------------------===/
13 #include "clang/Sema/TemplateDeduction.h"
14 #include "TreeTransform.h"
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/DeclObjC.h"
17 #include "clang/AST/DeclTemplate.h"
18 #include "clang/AST/Expr.h"
19 #include "clang/AST/ExprCXX.h"
20 #include "clang/AST/StmtVisitor.h"
21 #include "clang/Sema/DeclSpec.h"
22 #include "clang/Sema/Sema.h"
23 #include "clang/Sema/Template.h"
24 #include "llvm/ADT/SmallBitVector.h"
30 /// \brief Various flags that control template argument deduction.
32 /// These flags can be bitwise-OR'd together.
33 enum TemplateDeductionFlags {
34 /// \brief No template argument deduction flags, which indicates the
35 /// strictest results for template argument deduction (as used for, e.g.,
36 /// matching class template partial specializations).
38 /// \brief Within template argument deduction from a function call, we are
39 /// matching with a parameter type for which the original parameter was
41 TDF_ParamWithReferenceType = 0x1,
42 /// \brief Within template argument deduction from a function call, we
43 /// are matching in a case where we ignore cv-qualifiers.
44 TDF_IgnoreQualifiers = 0x02,
45 /// \brief Within template argument deduction from a function call,
46 /// we are matching in a case where we can perform template argument
47 /// deduction from a template-id of a derived class of the argument type.
48 TDF_DerivedClass = 0x04,
49 /// \brief Allow non-dependent types to differ, e.g., when performing
50 /// template argument deduction from a function call where conversions
52 TDF_SkipNonDependent = 0x08,
53 /// \brief Whether we are performing template argument deduction for
54 /// parameters and arguments in a top-level template argument
55 TDF_TopLevelParameterTypeList = 0x10,
56 /// \brief Within template argument deduction from overload resolution per
57 /// C++ [over.over] allow matching function types that are compatible in
58 /// terms of noreturn and default calling convention adjustments.
59 TDF_InOverloadResolution = 0x20
63 using namespace clang;
65 /// \brief Compare two APSInts, extending and switching the sign as
66 /// necessary to compare their values regardless of underlying type.
67 static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) {
68 if (Y.getBitWidth() > X.getBitWidth())
69 X = X.extend(Y.getBitWidth());
70 else if (Y.getBitWidth() < X.getBitWidth())
71 Y = Y.extend(X.getBitWidth());
73 // If there is a signedness mismatch, correct it.
74 if (X.isSigned() != Y.isSigned()) {
75 // If the signed value is negative, then the values cannot be the same.
76 if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative()))
86 static Sema::TemplateDeductionResult
87 DeduceTemplateArguments(Sema &S,
88 TemplateParameterList *TemplateParams,
89 const TemplateArgument &Param,
91 TemplateDeductionInfo &Info,
92 SmallVectorImpl<DeducedTemplateArgument> &Deduced);
94 /// \brief Whether template argument deduction for two reference parameters
95 /// resulted in the argument type, parameter type, or neither type being more
96 /// qualified than the other.
97 enum DeductionQualifierComparison {
98 NeitherMoreQualified = 0,
103 /// \brief Stores the result of comparing two reference parameters while
104 /// performing template argument deduction for partial ordering of function
106 struct RefParamPartialOrderingComparison {
107 /// \brief Whether the parameter type is an rvalue reference type.
108 bool ParamIsRvalueRef;
109 /// \brief Whether the argument type is an rvalue reference type.
112 /// \brief Whether the parameter or argument (or neither) is more qualified.
113 DeductionQualifierComparison Qualifiers;
118 static Sema::TemplateDeductionResult
119 DeduceTemplateArgumentsByTypeMatch(Sema &S,
120 TemplateParameterList *TemplateParams,
123 TemplateDeductionInfo &Info,
124 SmallVectorImpl<DeducedTemplateArgument> &
127 bool PartialOrdering = false,
128 SmallVectorImpl<RefParamPartialOrderingComparison> *
129 RefParamComparisons = 0);
131 static Sema::TemplateDeductionResult
132 DeduceTemplateArguments(Sema &S,
133 TemplateParameterList *TemplateParams,
134 const TemplateArgument *Params, unsigned NumParams,
135 const TemplateArgument *Args, unsigned NumArgs,
136 TemplateDeductionInfo &Info,
137 SmallVectorImpl<DeducedTemplateArgument> &Deduced);
139 /// \brief If the given expression is of a form that permits the deduction
140 /// of a non-type template parameter, return the declaration of that
141 /// non-type template parameter.
142 static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
143 // If we are within an alias template, the expression may have undergone
144 // any number of parameter substitutions already.
146 if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
147 E = IC->getSubExpr();
148 else if (SubstNonTypeTemplateParmExpr *Subst =
149 dyn_cast<SubstNonTypeTemplateParmExpr>(E))
150 E = Subst->getReplacement();
155 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
156 return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
161 /// \brief Determine whether two declaration pointers refer to the same
163 static bool isSameDeclaration(Decl *X, Decl *Y) {
164 if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
165 X = NX->getUnderlyingDecl();
166 if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
167 Y = NY->getUnderlyingDecl();
169 return X->getCanonicalDecl() == Y->getCanonicalDecl();
172 /// \brief Verify that the given, deduced template arguments are compatible.
174 /// \returns The deduced template argument, or a NULL template argument if
175 /// the deduced template arguments were incompatible.
176 static DeducedTemplateArgument
177 checkDeducedTemplateArguments(ASTContext &Context,
178 const DeducedTemplateArgument &X,
179 const DeducedTemplateArgument &Y) {
180 // We have no deduction for one or both of the arguments; they're compatible.
186 switch (X.getKind()) {
187 case TemplateArgument::Null:
188 llvm_unreachable("Non-deduced template arguments handled above");
190 case TemplateArgument::Type:
191 // If two template type arguments have the same type, they're compatible.
192 if (Y.getKind() == TemplateArgument::Type &&
193 Context.hasSameType(X.getAsType(), Y.getAsType()))
196 return DeducedTemplateArgument();
198 case TemplateArgument::Integral:
199 // If we deduced a constant in one case and either a dependent expression or
200 // declaration in another case, keep the integral constant.
201 // If both are integral constants with the same value, keep that value.
202 if (Y.getKind() == TemplateArgument::Expression ||
203 Y.getKind() == TemplateArgument::Declaration ||
204 (Y.getKind() == TemplateArgument::Integral &&
205 hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral())))
206 return DeducedTemplateArgument(X,
207 X.wasDeducedFromArrayBound() &&
208 Y.wasDeducedFromArrayBound());
210 // All other combinations are incompatible.
211 return DeducedTemplateArgument();
213 case TemplateArgument::Template:
214 if (Y.getKind() == TemplateArgument::Template &&
215 Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
218 // All other combinations are incompatible.
219 return DeducedTemplateArgument();
221 case TemplateArgument::TemplateExpansion:
222 if (Y.getKind() == TemplateArgument::TemplateExpansion &&
223 Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
224 Y.getAsTemplateOrTemplatePattern()))
227 // All other combinations are incompatible.
228 return DeducedTemplateArgument();
230 case TemplateArgument::Expression:
231 // If we deduced a dependent expression in one case and either an integral
232 // constant or a declaration in another case, keep the integral constant
234 if (Y.getKind() == TemplateArgument::Integral ||
235 Y.getKind() == TemplateArgument::Declaration)
236 return DeducedTemplateArgument(Y, X.wasDeducedFromArrayBound() &&
237 Y.wasDeducedFromArrayBound());
239 if (Y.getKind() == TemplateArgument::Expression) {
240 // Compare the expressions for equality
241 llvm::FoldingSetNodeID ID1, ID2;
242 X.getAsExpr()->Profile(ID1, Context, true);
243 Y.getAsExpr()->Profile(ID2, Context, true);
248 // All other combinations are incompatible.
249 return DeducedTemplateArgument();
251 case TemplateArgument::Declaration:
252 // If we deduced a declaration and a dependent expression, keep the
254 if (Y.getKind() == TemplateArgument::Expression)
257 // If we deduced a declaration and an integral constant, keep the
258 // integral constant.
259 if (Y.getKind() == TemplateArgument::Integral)
262 // If we deduced two declarations, make sure they they refer to the
264 if (Y.getKind() == TemplateArgument::Declaration &&
265 isSameDeclaration(X.getAsDecl(), Y.getAsDecl()) &&
266 X.isDeclForReferenceParam() == Y.isDeclForReferenceParam())
269 // All other combinations are incompatible.
270 return DeducedTemplateArgument();
272 case TemplateArgument::NullPtr:
273 // If we deduced a null pointer and a dependent expression, keep the
275 if (Y.getKind() == TemplateArgument::Expression)
278 // If we deduced a null pointer and an integral constant, keep the
279 // integral constant.
280 if (Y.getKind() == TemplateArgument::Integral)
283 // If we deduced two null pointers, make sure they have the same type.
284 if (Y.getKind() == TemplateArgument::NullPtr &&
285 Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType()))
288 // All other combinations are incompatible.
289 return DeducedTemplateArgument();
291 case TemplateArgument::Pack:
292 if (Y.getKind() != TemplateArgument::Pack ||
293 X.pack_size() != Y.pack_size())
294 return DeducedTemplateArgument();
296 for (TemplateArgument::pack_iterator XA = X.pack_begin(),
297 XAEnd = X.pack_end(),
299 XA != XAEnd; ++XA, ++YA) {
300 if (checkDeducedTemplateArguments(Context,
301 DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
302 DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound()))
304 return DeducedTemplateArgument();
310 llvm_unreachable("Invalid TemplateArgument Kind!");
313 /// \brief Deduce the value of the given non-type template parameter
314 /// from the given constant.
315 static Sema::TemplateDeductionResult
316 DeduceNonTypeTemplateArgument(Sema &S,
317 NonTypeTemplateParmDecl *NTTP,
318 llvm::APSInt Value, QualType ValueType,
319 bool DeducedFromArrayBound,
320 TemplateDeductionInfo &Info,
321 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
322 assert(NTTP->getDepth() == 0 &&
323 "Cannot deduce non-type template argument with depth > 0");
325 DeducedTemplateArgument NewDeduced(S.Context, Value, ValueType,
326 DeducedFromArrayBound);
327 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
328 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 type- or value-dependent expression.
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");
353 assert((Value->isTypeDependent() || Value->isValueDependent()) &&
354 "Expression template argument must be type- or value-dependent.");
356 DeducedTemplateArgument NewDeduced(Value);
357 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
358 Deduced[NTTP->getIndex()],
361 if (Result.isNull()) {
363 Info.FirstArg = Deduced[NTTP->getIndex()];
364 Info.SecondArg = NewDeduced;
365 return Sema::TDK_Inconsistent;
368 Deduced[NTTP->getIndex()] = Result;
369 return Sema::TDK_Success;
372 /// \brief Deduce the value of the given non-type template parameter
373 /// from the given declaration.
375 /// \returns true if deduction succeeded, false otherwise.
376 static Sema::TemplateDeductionResult
377 DeduceNonTypeTemplateArgument(Sema &S,
378 NonTypeTemplateParmDecl *NTTP,
380 TemplateDeductionInfo &Info,
381 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
382 assert(NTTP->getDepth() == 0 &&
383 "Cannot deduce non-type template argument with depth > 0");
385 D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : 0;
386 TemplateArgument New(D, NTTP->getType()->isReferenceType());
387 DeducedTemplateArgument NewDeduced(New);
388 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
389 Deduced[NTTP->getIndex()],
391 if (Result.isNull()) {
393 Info.FirstArg = Deduced[NTTP->getIndex()];
394 Info.SecondArg = NewDeduced;
395 return Sema::TDK_Inconsistent;
398 Deduced[NTTP->getIndex()] = Result;
399 return Sema::TDK_Success;
402 static Sema::TemplateDeductionResult
403 DeduceTemplateArguments(Sema &S,
404 TemplateParameterList *TemplateParams,
407 TemplateDeductionInfo &Info,
408 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
409 TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
411 // The parameter type is dependent and is not a template template parameter,
412 // so there is nothing that we can deduce.
413 return Sema::TDK_Success;
416 if (TemplateTemplateParmDecl *TempParam
417 = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
418 DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg));
419 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
420 Deduced[TempParam->getIndex()],
422 if (Result.isNull()) {
423 Info.Param = TempParam;
424 Info.FirstArg = Deduced[TempParam->getIndex()];
425 Info.SecondArg = NewDeduced;
426 return Sema::TDK_Inconsistent;
429 Deduced[TempParam->getIndex()] = Result;
430 return Sema::TDK_Success;
433 // Verify that the two template names are equivalent.
434 if (S.Context.hasSameTemplateName(Param, Arg))
435 return Sema::TDK_Success;
437 // Mismatch of non-dependent template parameter to argument.
438 Info.FirstArg = TemplateArgument(Param);
439 Info.SecondArg = TemplateArgument(Arg);
440 return Sema::TDK_NonDeducedMismatch;
443 /// \brief Deduce the template arguments by comparing the template parameter
444 /// type (which is a template-id) with the template argument type.
446 /// \param S the Sema
448 /// \param TemplateParams the template parameters that we are deducing
450 /// \param Param the parameter type
452 /// \param Arg the argument type
454 /// \param Info information about the template argument deduction itself
456 /// \param Deduced the deduced template arguments
458 /// \returns the result of template argument deduction so far. Note that a
459 /// "success" result means that template argument deduction has not yet failed,
460 /// but it may still fail, later, for other reasons.
461 static Sema::TemplateDeductionResult
462 DeduceTemplateArguments(Sema &S,
463 TemplateParameterList *TemplateParams,
464 const TemplateSpecializationType *Param,
466 TemplateDeductionInfo &Info,
467 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
468 assert(Arg.isCanonical() && "Argument type must be canonical");
470 // Check whether the template argument is a dependent template-id.
471 if (const TemplateSpecializationType *SpecArg
472 = dyn_cast<TemplateSpecializationType>(Arg)) {
473 // Perform template argument deduction for the template name.
474 if (Sema::TemplateDeductionResult Result
475 = DeduceTemplateArguments(S, TemplateParams,
476 Param->getTemplateName(),
477 SpecArg->getTemplateName(),
482 // Perform template argument deduction on each template
483 // argument. Ignore any missing/extra arguments, since they could be
484 // filled in by default arguments.
485 return DeduceTemplateArguments(S, TemplateParams,
486 Param->getArgs(), Param->getNumArgs(),
487 SpecArg->getArgs(), SpecArg->getNumArgs(),
491 // If the argument type is a class template specialization, we
492 // perform template argument deduction using its template
494 const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
496 Info.FirstArg = TemplateArgument(QualType(Param, 0));
497 Info.SecondArg = TemplateArgument(Arg);
498 return Sema::TDK_NonDeducedMismatch;
501 ClassTemplateSpecializationDecl *SpecArg
502 = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
504 Info.FirstArg = TemplateArgument(QualType(Param, 0));
505 Info.SecondArg = TemplateArgument(Arg);
506 return Sema::TDK_NonDeducedMismatch;
509 // Perform template argument deduction for the template name.
510 if (Sema::TemplateDeductionResult Result
511 = DeduceTemplateArguments(S,
513 Param->getTemplateName(),
514 TemplateName(SpecArg->getSpecializedTemplate()),
518 // Perform template argument deduction for the template arguments.
519 return DeduceTemplateArguments(S, TemplateParams,
520 Param->getArgs(), Param->getNumArgs(),
521 SpecArg->getTemplateArgs().data(),
522 SpecArg->getTemplateArgs().size(),
526 /// \brief Determines whether the given type is an opaque type that
527 /// might be more qualified when instantiated.
528 static bool IsPossiblyOpaquelyQualifiedType(QualType T) {
529 switch (T->getTypeClass()) {
530 case Type::TypeOfExpr:
532 case Type::DependentName:
534 case Type::UnresolvedUsing:
535 case Type::TemplateTypeParm:
538 case Type::ConstantArray:
539 case Type::IncompleteArray:
540 case Type::VariableArray:
541 case Type::DependentSizedArray:
542 return IsPossiblyOpaquelyQualifiedType(
543 cast<ArrayType>(T)->getElementType());
550 /// \brief Retrieve the depth and index of a template parameter.
551 static std::pair<unsigned, unsigned>
552 getDepthAndIndex(NamedDecl *ND) {
553 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
554 return std::make_pair(TTP->getDepth(), TTP->getIndex());
556 if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
557 return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
559 TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
560 return std::make_pair(TTP->getDepth(), TTP->getIndex());
563 /// \brief Retrieve the depth and index of an unexpanded parameter pack.
564 static std::pair<unsigned, unsigned>
565 getDepthAndIndex(UnexpandedParameterPack UPP) {
566 if (const TemplateTypeParmType *TTP
567 = UPP.first.dyn_cast<const TemplateTypeParmType *>())
568 return std::make_pair(TTP->getDepth(), TTP->getIndex());
570 return getDepthAndIndex(UPP.first.get<NamedDecl *>());
573 /// \brief Helper function to build a TemplateParameter when we don't
574 /// know its type statically.
575 static TemplateParameter makeTemplateParameter(Decl *D) {
576 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
577 return TemplateParameter(TTP);
578 else if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
579 return TemplateParameter(NTTP);
581 return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
584 /// \brief Prepare to perform template argument deduction for all of the
585 /// arguments in a set of argument packs.
586 static void PrepareArgumentPackDeduction(Sema &S,
587 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
588 ArrayRef<unsigned> PackIndices,
589 SmallVectorImpl<DeducedTemplateArgument> &SavedPacks,
591 SmallVector<DeducedTemplateArgument, 4> > &NewlyDeducedPacks) {
592 // Save the deduced template arguments for each parameter pack expanded
593 // by this pack expansion, then clear out the deduction.
594 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
595 // Save the previously-deduced argument pack, then clear it out so that we
596 // can deduce a new argument pack.
597 SavedPacks[I] = Deduced[PackIndices[I]];
598 Deduced[PackIndices[I]] = TemplateArgument();
600 if (!S.CurrentInstantiationScope)
603 // If the template argument pack was explicitly specified, add that to
604 // the set of deduced arguments.
605 const TemplateArgument *ExplicitArgs;
606 unsigned NumExplicitArgs;
607 if (NamedDecl *PartiallySubstitutedPack
608 = S.CurrentInstantiationScope->getPartiallySubstitutedPack(
611 if (getDepthAndIndex(PartiallySubstitutedPack).second == PackIndices[I])
612 NewlyDeducedPacks[I].append(ExplicitArgs,
613 ExplicitArgs + NumExplicitArgs);
618 /// \brief Finish template argument deduction for a set of argument packs,
619 /// producing the argument packs and checking for consistency with prior
621 static Sema::TemplateDeductionResult
622 FinishArgumentPackDeduction(Sema &S,
623 TemplateParameterList *TemplateParams,
624 bool HasAnyArguments,
625 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
626 ArrayRef<unsigned> PackIndices,
627 SmallVectorImpl<DeducedTemplateArgument> &SavedPacks,
629 SmallVector<DeducedTemplateArgument, 4> > &NewlyDeducedPacks,
630 TemplateDeductionInfo &Info) {
631 // Build argument packs for each of the parameter packs expanded by this
633 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
634 if (HasAnyArguments && NewlyDeducedPacks[I].empty()) {
635 // We were not able to deduce anything for this parameter pack,
636 // so just restore the saved argument pack.
637 Deduced[PackIndices[I]] = SavedPacks[I];
641 DeducedTemplateArgument NewPack;
643 if (NewlyDeducedPacks[I].empty()) {
644 // If we deduced an empty argument pack, create it now.
645 NewPack = DeducedTemplateArgument(TemplateArgument::getEmptyPack());
647 TemplateArgument *ArgumentPack
648 = new (S.Context) TemplateArgument [NewlyDeducedPacks[I].size()];
649 std::copy(NewlyDeducedPacks[I].begin(), NewlyDeducedPacks[I].end(),
652 = DeducedTemplateArgument(TemplateArgument(ArgumentPack,
653 NewlyDeducedPacks[I].size()),
654 NewlyDeducedPacks[I][0].wasDeducedFromArrayBound());
657 DeducedTemplateArgument Result
658 = checkDeducedTemplateArguments(S.Context, SavedPacks[I], NewPack);
659 if (Result.isNull()) {
661 = makeTemplateParameter(TemplateParams->getParam(PackIndices[I]));
662 Info.FirstArg = SavedPacks[I];
663 Info.SecondArg = NewPack;
664 return Sema::TDK_Inconsistent;
667 Deduced[PackIndices[I]] = Result;
670 return Sema::TDK_Success;
673 /// \brief Deduce the template arguments by comparing the list of parameter
674 /// types to the list of argument types, as in the parameter-type-lists of
675 /// function types (C++ [temp.deduct.type]p10).
677 /// \param S The semantic analysis object within which we are deducing
679 /// \param TemplateParams The template parameters that we are deducing
681 /// \param Params The list of parameter types
683 /// \param NumParams The number of types in \c Params
685 /// \param Args The list of argument types
687 /// \param NumArgs The number of types in \c Args
689 /// \param Info information about the template argument deduction itself
691 /// \param Deduced the deduced template arguments
693 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
694 /// how template argument deduction is performed.
696 /// \param PartialOrdering If true, we are performing template argument
697 /// deduction for during partial ordering for a call
698 /// (C++0x [temp.deduct.partial]).
700 /// \param RefParamComparisons If we're performing template argument deduction
701 /// in the context of partial ordering, the set of qualifier comparisons.
703 /// \returns the result of template argument deduction so far. Note that a
704 /// "success" result means that template argument deduction has not yet failed,
705 /// but it may still fail, later, for other reasons.
706 static Sema::TemplateDeductionResult
707 DeduceTemplateArguments(Sema &S,
708 TemplateParameterList *TemplateParams,
709 const QualType *Params, unsigned NumParams,
710 const QualType *Args, unsigned NumArgs,
711 TemplateDeductionInfo &Info,
712 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
714 bool PartialOrdering = false,
715 SmallVectorImpl<RefParamPartialOrderingComparison> *
716 RefParamComparisons = 0) {
717 // Fast-path check to see if we have too many/too few arguments.
718 if (NumParams != NumArgs &&
719 !(NumParams && isa<PackExpansionType>(Params[NumParams - 1])) &&
720 !(NumArgs && isa<PackExpansionType>(Args[NumArgs - 1])))
721 return Sema::TDK_MiscellaneousDeductionFailure;
723 // C++0x [temp.deduct.type]p10:
724 // Similarly, if P has a form that contains (T), then each parameter type
725 // Pi of the respective parameter-type- list of P is compared with the
726 // corresponding parameter type Ai of the corresponding parameter-type-list
728 unsigned ArgIdx = 0, ParamIdx = 0;
729 for (; ParamIdx != NumParams; ++ParamIdx) {
730 // Check argument types.
731 const PackExpansionType *Expansion
732 = dyn_cast<PackExpansionType>(Params[ParamIdx]);
734 // Simple case: compare the parameter and argument types at this point.
736 // Make sure we have an argument.
737 if (ArgIdx >= NumArgs)
738 return Sema::TDK_MiscellaneousDeductionFailure;
740 if (isa<PackExpansionType>(Args[ArgIdx])) {
741 // C++0x [temp.deduct.type]p22:
742 // If the original function parameter associated with A is a function
743 // parameter pack and the function parameter associated with P is not
744 // a function parameter pack, then template argument deduction fails.
745 return Sema::TDK_MiscellaneousDeductionFailure;
748 if (Sema::TemplateDeductionResult Result
749 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
750 Params[ParamIdx], Args[ArgIdx],
753 RefParamComparisons))
760 // C++0x [temp.deduct.type]p5:
761 // The non-deduced contexts are:
762 // - A function parameter pack that does not occur at the end of the
763 // parameter-declaration-clause.
764 if (ParamIdx + 1 < NumParams)
765 return Sema::TDK_Success;
767 // C++0x [temp.deduct.type]p10:
768 // If the parameter-declaration corresponding to Pi is a function
769 // parameter pack, then the type of its declarator- id is compared with
770 // each remaining parameter type in the parameter-type-list of A. Each
771 // comparison deduces template arguments for subsequent positions in the
772 // template parameter packs expanded by the function parameter pack.
774 // Compute the set of template parameter indices that correspond to
775 // parameter packs expanded by the pack expansion.
776 SmallVector<unsigned, 2> PackIndices;
777 QualType Pattern = Expansion->getPattern();
779 llvm::SmallBitVector SawIndices(TemplateParams->size());
780 SmallVector<UnexpandedParameterPack, 2> Unexpanded;
781 S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
782 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
783 unsigned Depth, Index;
784 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
785 if (Depth == 0 && !SawIndices[Index]) {
786 SawIndices[Index] = true;
787 PackIndices.push_back(Index);
791 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
793 // Keep track of the deduced template arguments for each parameter pack
794 // expanded by this pack expansion (the outer index) and for each
795 // template argument (the inner SmallVectors).
796 SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2>
797 NewlyDeducedPacks(PackIndices.size());
798 SmallVector<DeducedTemplateArgument, 2>
799 SavedPacks(PackIndices.size());
800 PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks,
803 bool HasAnyArguments = false;
804 for (; ArgIdx < NumArgs; ++ArgIdx) {
805 HasAnyArguments = true;
807 // Deduce template arguments from the pattern.
808 if (Sema::TemplateDeductionResult Result
809 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, Pattern,
810 Args[ArgIdx], Info, Deduced,
811 TDF, PartialOrdering,
812 RefParamComparisons))
815 // Capture the deduced template arguments for each parameter pack expanded
816 // by this pack expansion, add them to the list of arguments we've deduced
817 // for that pack, then clear out the deduced argument.
818 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
819 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
820 if (!DeducedArg.isNull()) {
821 NewlyDeducedPacks[I].push_back(DeducedArg);
822 DeducedArg = DeducedTemplateArgument();
827 // Build argument packs for each of the parameter packs expanded by this
829 if (Sema::TemplateDeductionResult Result
830 = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments,
831 Deduced, PackIndices, SavedPacks,
832 NewlyDeducedPacks, Info))
836 // Make sure we don't have any extra arguments.
837 if (ArgIdx < NumArgs)
838 return Sema::TDK_MiscellaneousDeductionFailure;
840 return Sema::TDK_Success;
843 /// \brief Determine whether the parameter has qualifiers that are either
844 /// inconsistent with or a superset of the argument's qualifiers.
845 static bool hasInconsistentOrSupersetQualifiersOf(QualType ParamType,
847 Qualifiers ParamQs = ParamType.getQualifiers();
848 Qualifiers ArgQs = ArgType.getQualifiers();
850 if (ParamQs == ArgQs)
853 // Mismatched (but not missing) Objective-C GC attributes.
854 if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() &&
855 ParamQs.hasObjCGCAttr())
858 // Mismatched (but not missing) address spaces.
859 if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() &&
860 ParamQs.hasAddressSpace())
863 // Mismatched (but not missing) Objective-C lifetime qualifiers.
864 if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() &&
865 ParamQs.hasObjCLifetime())
868 // CVR qualifier superset.
869 return (ParamQs.getCVRQualifiers() != ArgQs.getCVRQualifiers()) &&
870 ((ParamQs.getCVRQualifiers() | ArgQs.getCVRQualifiers())
871 == ParamQs.getCVRQualifiers());
874 /// \brief Compare types for equality with respect to possibly compatible
875 /// function types (noreturn adjustment, implicit calling conventions). If any
876 /// of parameter and argument is not a function, just perform type comparison.
878 /// \param Param the template parameter type.
880 /// \param Arg the argument type.
881 bool Sema::isSameOrCompatibleFunctionType(CanQualType Param,
883 const FunctionType *ParamFunction = Param->getAs<FunctionType>(),
884 *ArgFunction = Arg->getAs<FunctionType>();
886 // Just compare if not functions.
887 if (!ParamFunction || !ArgFunction)
890 // Noreturn adjustment.
891 QualType AdjustedParam;
892 if (IsNoReturnConversion(Param, Arg, AdjustedParam))
893 return Arg == Context.getCanonicalType(AdjustedParam);
895 // FIXME: Compatible calling conventions.
900 /// \brief Deduce the template arguments by comparing the parameter type and
901 /// the argument type (C++ [temp.deduct.type]).
903 /// \param S the semantic analysis object within which we are deducing
905 /// \param TemplateParams the template parameters that we are deducing
907 /// \param ParamIn the parameter type
909 /// \param ArgIn the argument type
911 /// \param Info information about the template argument deduction itself
913 /// \param Deduced the deduced template arguments
915 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
916 /// how template argument deduction is performed.
918 /// \param PartialOrdering Whether we're performing template argument deduction
919 /// in the context of partial ordering (C++0x [temp.deduct.partial]).
921 /// \param RefParamComparisons If we're performing template argument deduction
922 /// in the context of partial ordering, the set of qualifier comparisons.
924 /// \returns the result of template argument deduction so far. Note that a
925 /// "success" result means that template argument deduction has not yet failed,
926 /// but it may still fail, later, for other reasons.
927 static Sema::TemplateDeductionResult
928 DeduceTemplateArgumentsByTypeMatch(Sema &S,
929 TemplateParameterList *TemplateParams,
930 QualType ParamIn, QualType ArgIn,
931 TemplateDeductionInfo &Info,
932 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
934 bool PartialOrdering,
935 SmallVectorImpl<RefParamPartialOrderingComparison> *
936 RefParamComparisons) {
937 // We only want to look at the canonical types, since typedefs and
938 // sugar are not part of template argument deduction.
939 QualType Param = S.Context.getCanonicalType(ParamIn);
940 QualType Arg = S.Context.getCanonicalType(ArgIn);
942 // If the argument type is a pack expansion, look at its pattern.
943 // This isn't explicitly called out
944 if (const PackExpansionType *ArgExpansion
945 = dyn_cast<PackExpansionType>(Arg))
946 Arg = ArgExpansion->getPattern();
948 if (PartialOrdering) {
949 // C++0x [temp.deduct.partial]p5:
950 // Before the partial ordering is done, certain transformations are
951 // performed on the types used for partial ordering:
952 // - If P is a reference type, P is replaced by the type referred to.
953 const ReferenceType *ParamRef = Param->getAs<ReferenceType>();
955 Param = ParamRef->getPointeeType();
957 // - If A is a reference type, A is replaced by the type referred to.
958 const ReferenceType *ArgRef = Arg->getAs<ReferenceType>();
960 Arg = ArgRef->getPointeeType();
962 if (RefParamComparisons && ParamRef && ArgRef) {
963 // C++0x [temp.deduct.partial]p6:
964 // If both P and A were reference types (before being replaced with the
965 // type referred to above), determine which of the two types (if any) is
966 // more cv-qualified than the other; otherwise the types are considered
967 // to be equally cv-qualified for partial ordering purposes. The result
968 // of this determination will be used below.
970 // We save this information for later, using it only when deduction
971 // succeeds in both directions.
972 RefParamPartialOrderingComparison Comparison;
973 Comparison.ParamIsRvalueRef = ParamRef->getAs<RValueReferenceType>();
974 Comparison.ArgIsRvalueRef = ArgRef->getAs<RValueReferenceType>();
975 Comparison.Qualifiers = NeitherMoreQualified;
977 Qualifiers ParamQuals = Param.getQualifiers();
978 Qualifiers ArgQuals = Arg.getQualifiers();
979 if (ParamQuals.isStrictSupersetOf(ArgQuals))
980 Comparison.Qualifiers = ParamMoreQualified;
981 else if (ArgQuals.isStrictSupersetOf(ParamQuals))
982 Comparison.Qualifiers = ArgMoreQualified;
983 RefParamComparisons->push_back(Comparison);
986 // C++0x [temp.deduct.partial]p7:
987 // Remove any top-level cv-qualifiers:
988 // - If P is a cv-qualified type, P is replaced by the cv-unqualified
990 Param = Param.getUnqualifiedType();
991 // - If A is a cv-qualified type, A is replaced by the cv-unqualified
993 Arg = Arg.getUnqualifiedType();
995 // C++0x [temp.deduct.call]p4 bullet 1:
996 // - If the original P is a reference type, the deduced A (i.e., the type
997 // referred to by the reference) can be more cv-qualified than the
999 if (TDF & TDF_ParamWithReferenceType) {
1001 QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals);
1002 Quals.setCVRQualifiers(Quals.getCVRQualifiers() &
1003 Arg.getCVRQualifiers());
1004 Param = S.Context.getQualifiedType(UnqualParam, Quals);
1007 if ((TDF & TDF_TopLevelParameterTypeList) && !Param->isFunctionType()) {
1008 // C++0x [temp.deduct.type]p10:
1009 // If P and A are function types that originated from deduction when
1010 // taking the address of a function template (14.8.2.2) or when deducing
1011 // template arguments from a function declaration (14.8.2.6) and Pi and
1012 // Ai are parameters of the top-level parameter-type-list of P and A,
1013 // respectively, Pi is adjusted if it is an rvalue reference to a
1014 // cv-unqualified template parameter and Ai is an lvalue reference, in
1015 // which case the type of Pi is changed to be the template parameter
1016 // type (i.e., T&& is changed to simply T). [ Note: As a result, when
1017 // Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
1018 // deduced as X&. - end note ]
1019 TDF &= ~TDF_TopLevelParameterTypeList;
1021 if (const RValueReferenceType *ParamRef
1022 = Param->getAs<RValueReferenceType>()) {
1023 if (isa<TemplateTypeParmType>(ParamRef->getPointeeType()) &&
1024 !ParamRef->getPointeeType().getQualifiers())
1025 if (Arg->isLValueReferenceType())
1026 Param = ParamRef->getPointeeType();
1031 // C++ [temp.deduct.type]p9:
1032 // A template type argument T, a template template argument TT or a
1033 // template non-type argument i can be deduced if P and A have one of
1034 // the following forms:
1038 if (const TemplateTypeParmType *TemplateTypeParm
1039 = Param->getAs<TemplateTypeParmType>()) {
1040 // Just skip any attempts to deduce from a placeholder type.
1041 if (Arg->isPlaceholderType())
1042 return Sema::TDK_Success;
1044 unsigned Index = TemplateTypeParm->getIndex();
1045 bool RecanonicalizeArg = false;
1047 // If the argument type is an array type, move the qualifiers up to the
1048 // top level, so they can be matched with the qualifiers on the parameter.
1049 if (isa<ArrayType>(Arg)) {
1051 Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
1053 Arg = S.Context.getQualifiedType(Arg, Quals);
1054 RecanonicalizeArg = true;
1058 // The argument type can not be less qualified than the parameter
1060 if (!(TDF & TDF_IgnoreQualifiers) &&
1061 hasInconsistentOrSupersetQualifiersOf(Param, Arg)) {
1062 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1063 Info.FirstArg = TemplateArgument(Param);
1064 Info.SecondArg = TemplateArgument(Arg);
1065 return Sema::TDK_Underqualified;
1068 assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
1069 assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function");
1070 QualType DeducedType = Arg;
1072 // Remove any qualifiers on the parameter from the deduced type.
1073 // We checked the qualifiers for consistency above.
1074 Qualifiers DeducedQs = DeducedType.getQualifiers();
1075 Qualifiers ParamQs = Param.getQualifiers();
1076 DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers());
1077 if (ParamQs.hasObjCGCAttr())
1078 DeducedQs.removeObjCGCAttr();
1079 if (ParamQs.hasAddressSpace())
1080 DeducedQs.removeAddressSpace();
1081 if (ParamQs.hasObjCLifetime())
1082 DeducedQs.removeObjCLifetime();
1085 // If template deduction would produce a lifetime qualifier on a type
1086 // that is not a lifetime type, template argument deduction fails.
1087 if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() &&
1088 !DeducedType->isDependentType()) {
1089 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1090 Info.FirstArg = TemplateArgument(Param);
1091 Info.SecondArg = TemplateArgument(Arg);
1092 return Sema::TDK_Underqualified;
1096 // If template deduction would produce an argument type with lifetime type
1097 // but no lifetime qualifier, the __strong lifetime qualifier is inferred.
1098 if (S.getLangOpts().ObjCAutoRefCount &&
1099 DeducedType->isObjCLifetimeType() &&
1100 !DeducedQs.hasObjCLifetime())
1101 DeducedQs.setObjCLifetime(Qualifiers::OCL_Strong);
1103 DeducedType = S.Context.getQualifiedType(DeducedType.getUnqualifiedType(),
1106 if (RecanonicalizeArg)
1107 DeducedType = S.Context.getCanonicalType(DeducedType);
1109 DeducedTemplateArgument NewDeduced(DeducedType);
1110 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
1113 if (Result.isNull()) {
1114 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1115 Info.FirstArg = Deduced[Index];
1116 Info.SecondArg = NewDeduced;
1117 return Sema::TDK_Inconsistent;
1120 Deduced[Index] = Result;
1121 return Sema::TDK_Success;
1124 // Set up the template argument deduction information for a failure.
1125 Info.FirstArg = TemplateArgument(ParamIn);
1126 Info.SecondArg = TemplateArgument(ArgIn);
1128 // If the parameter is an already-substituted template parameter
1129 // pack, do nothing: we don't know which of its arguments to look
1130 // at, so we have to wait until all of the parameter packs in this
1131 // expansion have arguments.
1132 if (isa<SubstTemplateTypeParmPackType>(Param))
1133 return Sema::TDK_Success;
1135 // Check the cv-qualifiers on the parameter and argument types.
1136 CanQualType CanParam = S.Context.getCanonicalType(Param);
1137 CanQualType CanArg = S.Context.getCanonicalType(Arg);
1138 if (!(TDF & TDF_IgnoreQualifiers)) {
1139 if (TDF & TDF_ParamWithReferenceType) {
1140 if (hasInconsistentOrSupersetQualifiersOf(Param, Arg))
1141 return Sema::TDK_NonDeducedMismatch;
1142 } else if (!IsPossiblyOpaquelyQualifiedType(Param)) {
1143 if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
1144 return Sema::TDK_NonDeducedMismatch;
1147 // If the parameter type is not dependent, there is nothing to deduce.
1148 if (!Param->isDependentType()) {
1149 if (!(TDF & TDF_SkipNonDependent)) {
1150 bool NonDeduced = (TDF & TDF_InOverloadResolution)?
1151 !S.isSameOrCompatibleFunctionType(CanParam, CanArg) :
1154 return Sema::TDK_NonDeducedMismatch;
1157 return Sema::TDK_Success;
1159 } else if (!Param->isDependentType()) {
1160 CanQualType ParamUnqualType = CanParam.getUnqualifiedType(),
1161 ArgUnqualType = CanArg.getUnqualifiedType();
1162 bool Success = (TDF & TDF_InOverloadResolution)?
1163 S.isSameOrCompatibleFunctionType(ParamUnqualType,
1165 ParamUnqualType == ArgUnqualType;
1167 return Sema::TDK_Success;
1170 switch (Param->getTypeClass()) {
1171 // Non-canonical types cannot appear here.
1172 #define NON_CANONICAL_TYPE(Class, Base) \
1173 case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class);
1174 #define TYPE(Class, Base)
1175 #include "clang/AST/TypeNodes.def"
1177 case Type::TemplateTypeParm:
1178 case Type::SubstTemplateTypeParmPack:
1179 llvm_unreachable("Type nodes handled above");
1181 // These types cannot be dependent, so simply check whether the types are
1184 case Type::VariableArray:
1186 case Type::FunctionNoProto:
1189 case Type::ObjCObject:
1190 case Type::ObjCInterface:
1191 case Type::ObjCObjectPointer: {
1192 if (TDF & TDF_SkipNonDependent)
1193 return Sema::TDK_Success;
1195 if (TDF & TDF_IgnoreQualifiers) {
1196 Param = Param.getUnqualifiedType();
1197 Arg = Arg.getUnqualifiedType();
1200 return Param == Arg? Sema::TDK_Success : Sema::TDK_NonDeducedMismatch;
1203 // _Complex T [placeholder extension]
1205 if (const ComplexType *ComplexArg = Arg->getAs<ComplexType>())
1206 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1207 cast<ComplexType>(Param)->getElementType(),
1208 ComplexArg->getElementType(),
1209 Info, Deduced, TDF);
1211 return Sema::TDK_NonDeducedMismatch;
1213 // _Atomic T [extension]
1215 if (const AtomicType *AtomicArg = Arg->getAs<AtomicType>())
1216 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1217 cast<AtomicType>(Param)->getValueType(),
1218 AtomicArg->getValueType(),
1219 Info, Deduced, TDF);
1221 return Sema::TDK_NonDeducedMismatch;
1224 case Type::Pointer: {
1225 QualType PointeeType;
1226 if (const PointerType *PointerArg = Arg->getAs<PointerType>()) {
1227 PointeeType = PointerArg->getPointeeType();
1228 } else if (const ObjCObjectPointerType *PointerArg
1229 = Arg->getAs<ObjCObjectPointerType>()) {
1230 PointeeType = PointerArg->getPointeeType();
1232 return Sema::TDK_NonDeducedMismatch;
1235 unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass);
1236 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1237 cast<PointerType>(Param)->getPointeeType(),
1239 Info, Deduced, SubTDF);
1243 case Type::LValueReference: {
1244 const LValueReferenceType *ReferenceArg = Arg->getAs<LValueReferenceType>();
1246 return Sema::TDK_NonDeducedMismatch;
1248 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1249 cast<LValueReferenceType>(Param)->getPointeeType(),
1250 ReferenceArg->getPointeeType(), Info, Deduced, 0);
1254 case Type::RValueReference: {
1255 const RValueReferenceType *ReferenceArg = Arg->getAs<RValueReferenceType>();
1257 return Sema::TDK_NonDeducedMismatch;
1259 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1260 cast<RValueReferenceType>(Param)->getPointeeType(),
1261 ReferenceArg->getPointeeType(),
1265 // T [] (implied, but not stated explicitly)
1266 case Type::IncompleteArray: {
1267 const IncompleteArrayType *IncompleteArrayArg =
1268 S.Context.getAsIncompleteArrayType(Arg);
1269 if (!IncompleteArrayArg)
1270 return Sema::TDK_NonDeducedMismatch;
1272 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1273 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1274 S.Context.getAsIncompleteArrayType(Param)->getElementType(),
1275 IncompleteArrayArg->getElementType(),
1276 Info, Deduced, SubTDF);
1279 // T [integer-constant]
1280 case Type::ConstantArray: {
1281 const ConstantArrayType *ConstantArrayArg =
1282 S.Context.getAsConstantArrayType(Arg);
1283 if (!ConstantArrayArg)
1284 return Sema::TDK_NonDeducedMismatch;
1286 const ConstantArrayType *ConstantArrayParm =
1287 S.Context.getAsConstantArrayType(Param);
1288 if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
1289 return Sema::TDK_NonDeducedMismatch;
1291 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1292 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1293 ConstantArrayParm->getElementType(),
1294 ConstantArrayArg->getElementType(),
1295 Info, Deduced, SubTDF);
1299 case Type::DependentSizedArray: {
1300 const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg);
1302 return Sema::TDK_NonDeducedMismatch;
1304 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1306 // Check the element type of the arrays
1307 const DependentSizedArrayType *DependentArrayParm
1308 = S.Context.getAsDependentSizedArrayType(Param);
1309 if (Sema::TemplateDeductionResult Result
1310 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1311 DependentArrayParm->getElementType(),
1312 ArrayArg->getElementType(),
1313 Info, Deduced, SubTDF))
1316 // Determine the array bound is something we can deduce.
1317 NonTypeTemplateParmDecl *NTTP
1318 = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
1320 return Sema::TDK_Success;
1322 // We can perform template argument deduction for the given non-type
1323 // template parameter.
1324 assert(NTTP->getDepth() == 0 &&
1325 "Cannot deduce non-type template argument at depth > 0");
1326 if (const ConstantArrayType *ConstantArrayArg
1327 = dyn_cast<ConstantArrayType>(ArrayArg)) {
1328 llvm::APSInt Size(ConstantArrayArg->getSize());
1329 return DeduceNonTypeTemplateArgument(S, NTTP, Size,
1330 S.Context.getSizeType(),
1331 /*ArrayBound=*/true,
1334 if (const DependentSizedArrayType *DependentArrayArg
1335 = dyn_cast<DependentSizedArrayType>(ArrayArg))
1336 if (DependentArrayArg->getSizeExpr())
1337 return DeduceNonTypeTemplateArgument(S, NTTP,
1338 DependentArrayArg->getSizeExpr(),
1341 // Incomplete type does not match a dependently-sized array type
1342 return Sema::TDK_NonDeducedMismatch;
1348 case Type::FunctionProto: {
1349 unsigned SubTDF = TDF & TDF_TopLevelParameterTypeList;
1350 const FunctionProtoType *FunctionProtoArg =
1351 dyn_cast<FunctionProtoType>(Arg);
1352 if (!FunctionProtoArg)
1353 return Sema::TDK_NonDeducedMismatch;
1355 const FunctionProtoType *FunctionProtoParam =
1356 cast<FunctionProtoType>(Param);
1358 if (FunctionProtoParam->getTypeQuals()
1359 != FunctionProtoArg->getTypeQuals() ||
1360 FunctionProtoParam->getRefQualifier()
1361 != FunctionProtoArg->getRefQualifier() ||
1362 FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
1363 return Sema::TDK_NonDeducedMismatch;
1365 // Check return types.
1366 if (Sema::TemplateDeductionResult Result
1367 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1368 FunctionProtoParam->getResultType(),
1369 FunctionProtoArg->getResultType(),
1373 return DeduceTemplateArguments(S, TemplateParams,
1374 FunctionProtoParam->arg_type_begin(),
1375 FunctionProtoParam->getNumArgs(),
1376 FunctionProtoArg->arg_type_begin(),
1377 FunctionProtoArg->getNumArgs(),
1378 Info, Deduced, SubTDF);
1381 case Type::InjectedClassName: {
1382 // Treat a template's injected-class-name as if the template
1383 // specialization type had been used.
1384 Param = cast<InjectedClassNameType>(Param)
1385 ->getInjectedSpecializationType();
1386 assert(isa<TemplateSpecializationType>(Param) &&
1387 "injected class name is not a template specialization type");
1391 // template-name<T> (where template-name refers to a class template)
1396 case Type::TemplateSpecialization: {
1397 const TemplateSpecializationType *SpecParam
1398 = cast<TemplateSpecializationType>(Param);
1400 // Try to deduce template arguments from the template-id.
1401 Sema::TemplateDeductionResult Result
1402 = DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg,
1405 if (Result && (TDF & TDF_DerivedClass)) {
1406 // C++ [temp.deduct.call]p3b3:
1407 // If P is a class, and P has the form template-id, then A can be a
1408 // derived class of the deduced A. Likewise, if P is a pointer to a
1409 // class of the form template-id, A can be a pointer to a derived
1410 // class pointed to by the deduced A.
1412 // More importantly:
1413 // These alternatives are considered only if type deduction would
1415 if (const RecordType *RecordT = Arg->getAs<RecordType>()) {
1416 // We cannot inspect base classes as part of deduction when the type
1417 // is incomplete, so either instantiate any templates necessary to
1418 // complete the type, or skip over it if it cannot be completed.
1419 if (S.RequireCompleteType(Info.getLocation(), Arg, 0))
1422 // Use data recursion to crawl through the list of base classes.
1423 // Visited contains the set of nodes we have already visited, while
1424 // ToVisit is our stack of records that we still need to visit.
1425 llvm::SmallPtrSet<const RecordType *, 8> Visited;
1426 SmallVector<const RecordType *, 8> ToVisit;
1427 ToVisit.push_back(RecordT);
1428 bool Successful = false;
1429 SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(),
1431 while (!ToVisit.empty()) {
1432 // Retrieve the next class in the inheritance hierarchy.
1433 const RecordType *NextT = ToVisit.back();
1436 // If we have already seen this type, skip it.
1437 if (!Visited.insert(NextT))
1440 // If this is a base class, try to perform template argument
1441 // deduction from it.
1442 if (NextT != RecordT) {
1443 TemplateDeductionInfo BaseInfo(Info.getLocation());
1444 Sema::TemplateDeductionResult BaseResult
1445 = DeduceTemplateArguments(S, TemplateParams, SpecParam,
1446 QualType(NextT, 0), BaseInfo,
1449 // If template argument deduction for this base was successful,
1450 // note that we had some success. Otherwise, ignore any deductions
1451 // from this base class.
1452 if (BaseResult == Sema::TDK_Success) {
1454 DeducedOrig.clear();
1455 DeducedOrig.append(Deduced.begin(), Deduced.end());
1456 Info.Param = BaseInfo.Param;
1457 Info.FirstArg = BaseInfo.FirstArg;
1458 Info.SecondArg = BaseInfo.SecondArg;
1461 Deduced = DeducedOrig;
1464 // Visit base classes
1465 CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
1466 for (CXXRecordDecl::base_class_iterator Base = Next->bases_begin(),
1467 BaseEnd = Next->bases_end();
1468 Base != BaseEnd; ++Base) {
1469 assert(Base->getType()->isRecordType() &&
1470 "Base class that isn't a record?");
1471 ToVisit.push_back(Base->getType()->getAs<RecordType>());
1476 return Sema::TDK_Success;
1488 // type (type::*)(T)
1493 case Type::MemberPointer: {
1494 const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
1495 const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
1497 return Sema::TDK_NonDeducedMismatch;
1499 if (Sema::TemplateDeductionResult Result
1500 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1501 MemPtrParam->getPointeeType(),
1502 MemPtrArg->getPointeeType(),
1504 TDF & TDF_IgnoreQualifiers))
1507 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1508 QualType(MemPtrParam->getClass(), 0),
1509 QualType(MemPtrArg->getClass(), 0),
1511 TDF & TDF_IgnoreQualifiers);
1514 // (clang extension)
1519 case Type::BlockPointer: {
1520 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
1521 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
1524 return Sema::TDK_NonDeducedMismatch;
1526 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1527 BlockPtrParam->getPointeeType(),
1528 BlockPtrArg->getPointeeType(),
1532 // (clang extension)
1534 // T __attribute__(((ext_vector_type(<integral constant>))))
1535 case Type::ExtVector: {
1536 const ExtVectorType *VectorParam = cast<ExtVectorType>(Param);
1537 if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1538 // Make sure that the vectors have the same number of elements.
1539 if (VectorParam->getNumElements() != VectorArg->getNumElements())
1540 return Sema::TDK_NonDeducedMismatch;
1542 // Perform deduction on the element types.
1543 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1544 VectorParam->getElementType(),
1545 VectorArg->getElementType(),
1546 Info, Deduced, TDF);
1549 if (const DependentSizedExtVectorType *VectorArg
1550 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1551 // We can't check the number of elements, since the argument has a
1552 // dependent number of elements. This can only occur during partial
1555 // Perform deduction on the element types.
1556 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1557 VectorParam->getElementType(),
1558 VectorArg->getElementType(),
1559 Info, Deduced, TDF);
1562 return Sema::TDK_NonDeducedMismatch;
1565 // (clang extension)
1567 // T __attribute__(((ext_vector_type(N))))
1568 case Type::DependentSizedExtVector: {
1569 const DependentSizedExtVectorType *VectorParam
1570 = cast<DependentSizedExtVectorType>(Param);
1572 if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1573 // Perform deduction on the element types.
1574 if (Sema::TemplateDeductionResult Result
1575 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1576 VectorParam->getElementType(),
1577 VectorArg->getElementType(),
1578 Info, Deduced, TDF))
1581 // Perform deduction on the vector size, if we can.
1582 NonTypeTemplateParmDecl *NTTP
1583 = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1585 return Sema::TDK_Success;
1587 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1588 ArgSize = VectorArg->getNumElements();
1589 return DeduceNonTypeTemplateArgument(S, NTTP, ArgSize, S.Context.IntTy,
1590 false, Info, Deduced);
1593 if (const DependentSizedExtVectorType *VectorArg
1594 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1595 // Perform deduction on the element types.
1596 if (Sema::TemplateDeductionResult Result
1597 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1598 VectorParam->getElementType(),
1599 VectorArg->getElementType(),
1600 Info, Deduced, TDF))
1603 // Perform deduction on the vector size, if we can.
1604 NonTypeTemplateParmDecl *NTTP
1605 = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1607 return Sema::TDK_Success;
1609 return DeduceNonTypeTemplateArgument(S, NTTP, VectorArg->getSizeExpr(),
1613 return Sema::TDK_NonDeducedMismatch;
1616 case Type::TypeOfExpr:
1618 case Type::DependentName:
1619 case Type::UnresolvedUsing:
1620 case Type::Decltype:
1621 case Type::UnaryTransform:
1623 case Type::DependentTemplateSpecialization:
1624 case Type::PackExpansion:
1625 // No template argument deduction for these types
1626 return Sema::TDK_Success;
1629 llvm_unreachable("Invalid Type Class!");
1632 static Sema::TemplateDeductionResult
1633 DeduceTemplateArguments(Sema &S,
1634 TemplateParameterList *TemplateParams,
1635 const TemplateArgument &Param,
1636 TemplateArgument Arg,
1637 TemplateDeductionInfo &Info,
1638 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1639 // If the template argument is a pack expansion, perform template argument
1640 // deduction against the pattern of that expansion. This only occurs during
1641 // partial ordering.
1642 if (Arg.isPackExpansion())
1643 Arg = Arg.getPackExpansionPattern();
1645 switch (Param.getKind()) {
1646 case TemplateArgument::Null:
1647 llvm_unreachable("Null template argument in parameter list");
1649 case TemplateArgument::Type:
1650 if (Arg.getKind() == TemplateArgument::Type)
1651 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1655 Info.FirstArg = Param;
1656 Info.SecondArg = Arg;
1657 return Sema::TDK_NonDeducedMismatch;
1659 case TemplateArgument::Template:
1660 if (Arg.getKind() == TemplateArgument::Template)
1661 return DeduceTemplateArguments(S, TemplateParams,
1662 Param.getAsTemplate(),
1663 Arg.getAsTemplate(), Info, Deduced);
1664 Info.FirstArg = Param;
1665 Info.SecondArg = Arg;
1666 return Sema::TDK_NonDeducedMismatch;
1668 case TemplateArgument::TemplateExpansion:
1669 llvm_unreachable("caller should handle pack expansions");
1671 case TemplateArgument::Declaration:
1672 if (Arg.getKind() == TemplateArgument::Declaration &&
1673 isSameDeclaration(Param.getAsDecl(), Arg.getAsDecl()) &&
1674 Param.isDeclForReferenceParam() == Arg.isDeclForReferenceParam())
1675 return Sema::TDK_Success;
1677 Info.FirstArg = Param;
1678 Info.SecondArg = Arg;
1679 return Sema::TDK_NonDeducedMismatch;
1681 case TemplateArgument::NullPtr:
1682 if (Arg.getKind() == TemplateArgument::NullPtr &&
1683 S.Context.hasSameType(Param.getNullPtrType(), Arg.getNullPtrType()))
1684 return Sema::TDK_Success;
1686 Info.FirstArg = Param;
1687 Info.SecondArg = Arg;
1688 return Sema::TDK_NonDeducedMismatch;
1690 case TemplateArgument::Integral:
1691 if (Arg.getKind() == TemplateArgument::Integral) {
1692 if (hasSameExtendedValue(Param.getAsIntegral(), Arg.getAsIntegral()))
1693 return Sema::TDK_Success;
1695 Info.FirstArg = Param;
1696 Info.SecondArg = Arg;
1697 return Sema::TDK_NonDeducedMismatch;
1700 if (Arg.getKind() == TemplateArgument::Expression) {
1701 Info.FirstArg = Param;
1702 Info.SecondArg = Arg;
1703 return Sema::TDK_NonDeducedMismatch;
1706 Info.FirstArg = Param;
1707 Info.SecondArg = Arg;
1708 return Sema::TDK_NonDeducedMismatch;
1710 case TemplateArgument::Expression: {
1711 if (NonTypeTemplateParmDecl *NTTP
1712 = getDeducedParameterFromExpr(Param.getAsExpr())) {
1713 if (Arg.getKind() == TemplateArgument::Integral)
1714 return DeduceNonTypeTemplateArgument(S, NTTP,
1715 Arg.getAsIntegral(),
1716 Arg.getIntegralType(),
1717 /*ArrayBound=*/false,
1719 if (Arg.getKind() == TemplateArgument::Expression)
1720 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(),
1722 if (Arg.getKind() == TemplateArgument::Declaration)
1723 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(),
1726 Info.FirstArg = Param;
1727 Info.SecondArg = Arg;
1728 return Sema::TDK_NonDeducedMismatch;
1731 // Can't deduce anything, but that's okay.
1732 return Sema::TDK_Success;
1734 case TemplateArgument::Pack:
1735 llvm_unreachable("Argument packs should be expanded by the caller!");
1738 llvm_unreachable("Invalid TemplateArgument Kind!");
1741 /// \brief Determine whether there is a template argument to be used for
1744 /// This routine "expands" argument packs in-place, overriding its input
1745 /// parameters so that \c Args[ArgIdx] will be the available template argument.
1747 /// \returns true if there is another template argument (which will be at
1748 /// \c Args[ArgIdx]), false otherwise.
1749 static bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args,
1751 unsigned &NumArgs) {
1752 if (ArgIdx == NumArgs)
1755 const TemplateArgument &Arg = Args[ArgIdx];
1756 if (Arg.getKind() != TemplateArgument::Pack)
1759 assert(ArgIdx == NumArgs - 1 && "Pack not at the end of argument list?");
1760 Args = Arg.pack_begin();
1761 NumArgs = Arg.pack_size();
1763 return ArgIdx < NumArgs;
1766 /// \brief Determine whether the given set of template arguments has a pack
1767 /// expansion that is not the last template argument.
1768 static bool hasPackExpansionBeforeEnd(const TemplateArgument *Args,
1770 unsigned ArgIdx = 0;
1771 while (ArgIdx < NumArgs) {
1772 const TemplateArgument &Arg = Args[ArgIdx];
1774 // Unwrap argument packs.
1775 if (Args[ArgIdx].getKind() == TemplateArgument::Pack) {
1776 Args = Arg.pack_begin();
1777 NumArgs = Arg.pack_size();
1783 if (ArgIdx == NumArgs)
1786 if (Arg.isPackExpansion())
1793 static Sema::TemplateDeductionResult
1794 DeduceTemplateArguments(Sema &S,
1795 TemplateParameterList *TemplateParams,
1796 const TemplateArgument *Params, unsigned NumParams,
1797 const TemplateArgument *Args, unsigned NumArgs,
1798 TemplateDeductionInfo &Info,
1799 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1800 // C++0x [temp.deduct.type]p9:
1801 // If the template argument list of P contains a pack expansion that is not
1802 // the last template argument, the entire template argument list is a
1803 // non-deduced context.
1804 if (hasPackExpansionBeforeEnd(Params, NumParams))
1805 return Sema::TDK_Success;
1807 // C++0x [temp.deduct.type]p9:
1808 // If P has a form that contains <T> or <i>, then each argument Pi of the
1809 // respective template argument list P is compared with the corresponding
1810 // argument Ai of the corresponding template argument list of A.
1811 unsigned ArgIdx = 0, ParamIdx = 0;
1812 for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams);
1814 if (!Params[ParamIdx].isPackExpansion()) {
1815 // The simple case: deduce template arguments by matching Pi and Ai.
1817 // Check whether we have enough arguments.
1818 if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
1819 return Sema::TDK_Success;
1821 if (Args[ArgIdx].isPackExpansion()) {
1822 // FIXME: We follow the logic of C++0x [temp.deduct.type]p22 here,
1823 // but applied to pack expansions that are template arguments.
1824 return Sema::TDK_MiscellaneousDeductionFailure;
1827 // Perform deduction for this Pi/Ai pair.
1828 if (Sema::TemplateDeductionResult Result
1829 = DeduceTemplateArguments(S, TemplateParams,
1830 Params[ParamIdx], Args[ArgIdx],
1834 // Move to the next argument.
1839 // The parameter is a pack expansion.
1841 // C++0x [temp.deduct.type]p9:
1842 // If Pi is a pack expansion, then the pattern of Pi is compared with
1843 // each remaining argument in the template argument list of A. Each
1844 // comparison deduces template arguments for subsequent positions in the
1845 // template parameter packs expanded by Pi.
1846 TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
1848 // Compute the set of template parameter indices that correspond to
1849 // parameter packs expanded by the pack expansion.
1850 SmallVector<unsigned, 2> PackIndices;
1852 llvm::SmallBitVector SawIndices(TemplateParams->size());
1853 SmallVector<UnexpandedParameterPack, 2> Unexpanded;
1854 S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
1855 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
1856 unsigned Depth, Index;
1857 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
1858 if (Depth == 0 && !SawIndices[Index]) {
1859 SawIndices[Index] = true;
1860 PackIndices.push_back(Index);
1864 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
1866 // FIXME: If there are no remaining arguments, we can bail out early
1867 // and set any deduced parameter packs to an empty argument pack.
1868 // The latter part of this is a (minor) correctness issue.
1870 // Save the deduced template arguments for each parameter pack expanded
1871 // by this pack expansion, then clear out the deduction.
1872 SmallVector<DeducedTemplateArgument, 2>
1873 SavedPacks(PackIndices.size());
1874 SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2>
1875 NewlyDeducedPacks(PackIndices.size());
1876 PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks,
1879 // Keep track of the deduced template arguments for each parameter pack
1880 // expanded by this pack expansion (the outer index) and for each
1881 // template argument (the inner SmallVectors).
1882 bool HasAnyArguments = false;
1883 while (hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) {
1884 HasAnyArguments = true;
1886 // Deduce template arguments from the pattern.
1887 if (Sema::TemplateDeductionResult Result
1888 = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
1892 // Capture the deduced template arguments for each parameter pack expanded
1893 // by this pack expansion, add them to the list of arguments we've deduced
1894 // for that pack, then clear out the deduced argument.
1895 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
1896 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
1897 if (!DeducedArg.isNull()) {
1898 NewlyDeducedPacks[I].push_back(DeducedArg);
1899 DeducedArg = DeducedTemplateArgument();
1906 // Build argument packs for each of the parameter packs expanded by this
1908 if (Sema::TemplateDeductionResult Result
1909 = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments,
1910 Deduced, PackIndices, SavedPacks,
1911 NewlyDeducedPacks, Info))
1915 return Sema::TDK_Success;
1918 static Sema::TemplateDeductionResult
1919 DeduceTemplateArguments(Sema &S,
1920 TemplateParameterList *TemplateParams,
1921 const TemplateArgumentList &ParamList,
1922 const TemplateArgumentList &ArgList,
1923 TemplateDeductionInfo &Info,
1924 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1925 return DeduceTemplateArguments(S, TemplateParams,
1926 ParamList.data(), ParamList.size(),
1927 ArgList.data(), ArgList.size(),
1931 /// \brief Determine whether two template arguments are the same.
1932 static bool isSameTemplateArg(ASTContext &Context,
1933 const TemplateArgument &X,
1934 const TemplateArgument &Y) {
1935 if (X.getKind() != Y.getKind())
1938 switch (X.getKind()) {
1939 case TemplateArgument::Null:
1940 llvm_unreachable("Comparing NULL template argument");
1942 case TemplateArgument::Type:
1943 return Context.getCanonicalType(X.getAsType()) ==
1944 Context.getCanonicalType(Y.getAsType());
1946 case TemplateArgument::Declaration:
1947 return isSameDeclaration(X.getAsDecl(), Y.getAsDecl()) &&
1948 X.isDeclForReferenceParam() == Y.isDeclForReferenceParam();
1950 case TemplateArgument::NullPtr:
1951 return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
1953 case TemplateArgument::Template:
1954 case TemplateArgument::TemplateExpansion:
1955 return Context.getCanonicalTemplateName(
1956 X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
1957 Context.getCanonicalTemplateName(
1958 Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
1960 case TemplateArgument::Integral:
1961 return X.getAsIntegral() == Y.getAsIntegral();
1963 case TemplateArgument::Expression: {
1964 llvm::FoldingSetNodeID XID, YID;
1965 X.getAsExpr()->Profile(XID, Context, true);
1966 Y.getAsExpr()->Profile(YID, Context, true);
1970 case TemplateArgument::Pack:
1971 if (X.pack_size() != Y.pack_size())
1974 for (TemplateArgument::pack_iterator XP = X.pack_begin(),
1975 XPEnd = X.pack_end(),
1976 YP = Y.pack_begin();
1977 XP != XPEnd; ++XP, ++YP)
1978 if (!isSameTemplateArg(Context, *XP, *YP))
1984 llvm_unreachable("Invalid TemplateArgument Kind!");
1987 /// \brief Allocate a TemplateArgumentLoc where all locations have
1988 /// been initialized to the given location.
1990 /// \param S The semantic analysis object.
1992 /// \param Arg The template argument we are producing template argument
1993 /// location information for.
1995 /// \param NTTPType For a declaration template argument, the type of
1996 /// the non-type template parameter that corresponds to this template
1999 /// \param Loc The source location to use for the resulting template
2001 static TemplateArgumentLoc
2002 getTrivialTemplateArgumentLoc(Sema &S,
2003 const TemplateArgument &Arg,
2005 SourceLocation Loc) {
2006 switch (Arg.getKind()) {
2007 case TemplateArgument::Null:
2008 llvm_unreachable("Can't get a NULL template argument here");
2010 case TemplateArgument::Type:
2011 return TemplateArgumentLoc(Arg,
2012 S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
2014 case TemplateArgument::Declaration: {
2016 = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2018 return TemplateArgumentLoc(TemplateArgument(E), E);
2021 case TemplateArgument::NullPtr: {
2023 = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2025 return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true),
2029 case TemplateArgument::Integral: {
2031 = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).takeAs<Expr>();
2032 return TemplateArgumentLoc(TemplateArgument(E), E);
2035 case TemplateArgument::Template:
2036 case TemplateArgument::TemplateExpansion: {
2037 NestedNameSpecifierLocBuilder Builder;
2038 TemplateName Template = Arg.getAsTemplate();
2039 if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
2040 Builder.MakeTrivial(S.Context, DTN->getQualifier(), Loc);
2041 else if (QualifiedTemplateName *QTN = Template.getAsQualifiedTemplateName())
2042 Builder.MakeTrivial(S.Context, QTN->getQualifier(), Loc);
2044 if (Arg.getKind() == TemplateArgument::Template)
2045 return TemplateArgumentLoc(Arg,
2046 Builder.getWithLocInContext(S.Context),
2050 return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(S.Context),
2054 case TemplateArgument::Expression:
2055 return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2057 case TemplateArgument::Pack:
2058 return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
2061 llvm_unreachable("Invalid TemplateArgument Kind!");
2065 /// \brief Convert the given deduced template argument and add it to the set of
2066 /// fully-converted template arguments.
2067 static bool ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
2068 DeducedTemplateArgument Arg,
2069 NamedDecl *Template,
2071 unsigned ArgumentPackIndex,
2072 TemplateDeductionInfo &Info,
2073 bool InFunctionTemplate,
2074 SmallVectorImpl<TemplateArgument> &Output) {
2075 if (Arg.getKind() == TemplateArgument::Pack) {
2076 // This is a template argument pack, so check each of its arguments against
2077 // the template parameter.
2078 SmallVector<TemplateArgument, 2> PackedArgsBuilder;
2079 for (TemplateArgument::pack_iterator PA = Arg.pack_begin(),
2080 PAEnd = Arg.pack_end();
2081 PA != PAEnd; ++PA) {
2082 // When converting the deduced template argument, append it to the
2083 // general output list. We need to do this so that the template argument
2084 // checking logic has all of the prior template arguments available.
2085 DeducedTemplateArgument InnerArg(*PA);
2086 InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
2087 if (ConvertDeducedTemplateArgument(S, Param, InnerArg, Template,
2088 NTTPType, PackedArgsBuilder.size(),
2089 Info, InFunctionTemplate, Output))
2092 // Move the converted template argument into our argument pack.
2093 PackedArgsBuilder.push_back(Output.back());
2097 // Create the resulting argument pack.
2098 Output.push_back(TemplateArgument::CreatePackCopy(S.Context,
2099 PackedArgsBuilder.data(),
2100 PackedArgsBuilder.size()));
2104 // Convert the deduced template argument into a template
2105 // argument that we can check, almost as if the user had written
2106 // the template argument explicitly.
2107 TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType,
2108 Info.getLocation());
2110 // Check the template argument, converting it as necessary.
2111 return S.CheckTemplateArgument(Param, ArgLoc,
2113 Template->getLocation(),
2114 Template->getSourceRange().getEnd(),
2118 ? (Arg.wasDeducedFromArrayBound()
2119 ? Sema::CTAK_DeducedFromArrayBound
2120 : Sema::CTAK_Deduced)
2121 : Sema::CTAK_Specified);
2124 /// Complete template argument deduction for a class template partial
2126 static Sema::TemplateDeductionResult
2127 FinishTemplateArgumentDeduction(Sema &S,
2128 ClassTemplatePartialSpecializationDecl *Partial,
2129 const TemplateArgumentList &TemplateArgs,
2130 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2131 TemplateDeductionInfo &Info) {
2132 // Unevaluated SFINAE context.
2133 EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated);
2134 Sema::SFINAETrap Trap(S);
2136 Sema::ContextRAII SavedContext(S, Partial);
2138 // C++ [temp.deduct.type]p2:
2139 // [...] or if any template argument remains neither deduced nor
2140 // explicitly specified, template argument deduction fails.
2141 SmallVector<TemplateArgument, 4> Builder;
2142 TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2143 for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2144 NamedDecl *Param = PartialParams->getParam(I);
2145 if (Deduced[I].isNull()) {
2146 Info.Param = makeTemplateParameter(Param);
2147 return Sema::TDK_Incomplete;
2150 // We have deduced this argument, so it still needs to be
2151 // checked and converted.
2153 // First, for a non-type template parameter type that is
2154 // initialized by a declaration, we need the type of the
2155 // corresponding non-type template parameter.
2157 if (NonTypeTemplateParmDecl *NTTP
2158 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2159 NTTPType = NTTP->getType();
2160 if (NTTPType->isDependentType()) {
2161 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2162 Builder.data(), Builder.size());
2163 NTTPType = S.SubstType(NTTPType,
2164 MultiLevelTemplateArgumentList(TemplateArgs),
2165 NTTP->getLocation(),
2166 NTTP->getDeclName());
2167 if (NTTPType.isNull()) {
2168 Info.Param = makeTemplateParameter(Param);
2169 // FIXME: These template arguments are temporary. Free them!
2170 Info.reset(TemplateArgumentList::CreateCopy(S.Context,
2173 return Sema::TDK_SubstitutionFailure;
2178 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I],
2179 Partial, NTTPType, 0, Info, false,
2181 Info.Param = makeTemplateParameter(Param);
2182 // FIXME: These template arguments are temporary. Free them!
2183 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2185 return Sema::TDK_SubstitutionFailure;
2189 // Form the template argument list from the deduced template arguments.
2190 TemplateArgumentList *DeducedArgumentList
2191 = TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2194 Info.reset(DeducedArgumentList);
2196 // Substitute the deduced template arguments into the template
2197 // arguments of the class template partial specialization, and
2198 // verify that the instantiated template arguments are both valid
2199 // and are equivalent to the template arguments originally provided
2200 // to the class template.
2201 LocalInstantiationScope InstScope(S);
2202 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
2203 const TemplateArgumentLoc *PartialTemplateArgs
2204 = Partial->getTemplateArgsAsWritten();
2206 // Note that we don't provide the langle and rangle locations.
2207 TemplateArgumentListInfo InstArgs;
2209 if (S.Subst(PartialTemplateArgs,
2210 Partial->getNumTemplateArgsAsWritten(),
2211 InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2212 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2213 if (ParamIdx >= Partial->getTemplateParameters()->size())
2214 ParamIdx = Partial->getTemplateParameters()->size() - 1;
2217 = const_cast<NamedDecl *>(
2218 Partial->getTemplateParameters()->getParam(ParamIdx));
2219 Info.Param = makeTemplateParameter(Param);
2220 Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2221 return Sema::TDK_SubstitutionFailure;
2224 SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2225 if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(),
2226 InstArgs, false, ConvertedInstArgs))
2227 return Sema::TDK_SubstitutionFailure;
2229 TemplateParameterList *TemplateParams
2230 = ClassTemplate->getTemplateParameters();
2231 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2232 TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2233 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2234 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2235 Info.FirstArg = TemplateArgs[I];
2236 Info.SecondArg = InstArg;
2237 return Sema::TDK_NonDeducedMismatch;
2241 if (Trap.hasErrorOccurred())
2242 return Sema::TDK_SubstitutionFailure;
2244 return Sema::TDK_Success;
2247 /// \brief Perform template argument deduction to determine whether
2248 /// the given template arguments match the given class template
2249 /// partial specialization per C++ [temp.class.spec.match].
2250 Sema::TemplateDeductionResult
2251 Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
2252 const TemplateArgumentList &TemplateArgs,
2253 TemplateDeductionInfo &Info) {
2254 if (Partial->isInvalidDecl())
2257 // C++ [temp.class.spec.match]p2:
2258 // A partial specialization matches a given actual template
2259 // argument list if the template arguments of the partial
2260 // specialization can be deduced from the actual template argument
2263 // Unevaluated SFINAE context.
2264 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2265 SFINAETrap Trap(*this);
2267 SmallVector<DeducedTemplateArgument, 4> Deduced;
2268 Deduced.resize(Partial->getTemplateParameters()->size());
2269 if (TemplateDeductionResult Result
2270 = ::DeduceTemplateArguments(*this,
2271 Partial->getTemplateParameters(),
2272 Partial->getTemplateArgs(),
2273 TemplateArgs, Info, Deduced))
2276 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2277 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial,
2280 return TDK_InstantiationDepth;
2282 if (Trap.hasErrorOccurred())
2283 return Sema::TDK_SubstitutionFailure;
2285 return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2289 /// \brief Determine whether the given type T is a simple-template-id type.
2290 static bool isSimpleTemplateIdType(QualType T) {
2291 if (const TemplateSpecializationType *Spec
2292 = T->getAs<TemplateSpecializationType>())
2293 return Spec->getTemplateName().getAsTemplateDecl() != 0;
2298 /// \brief Substitute the explicitly-provided template arguments into the
2299 /// given function template according to C++ [temp.arg.explicit].
2301 /// \param FunctionTemplate the function template into which the explicit
2302 /// template arguments will be substituted.
2304 /// \param ExplicitTemplateArgs the explicitly-specified template
2307 /// \param Deduced the deduced template arguments, which will be populated
2308 /// with the converted and checked explicit template arguments.
2310 /// \param ParamTypes will be populated with the instantiated function
2313 /// \param FunctionType if non-NULL, the result type of the function template
2314 /// will also be instantiated and the pointed-to value will be updated with
2315 /// the instantiated function type.
2317 /// \param Info if substitution fails for any reason, this object will be
2318 /// populated with more information about the failure.
2320 /// \returns TDK_Success if substitution was successful, or some failure
2322 Sema::TemplateDeductionResult
2323 Sema::SubstituteExplicitTemplateArguments(
2324 FunctionTemplateDecl *FunctionTemplate,
2325 TemplateArgumentListInfo &ExplicitTemplateArgs,
2326 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2327 SmallVectorImpl<QualType> &ParamTypes,
2328 QualType *FunctionType,
2329 TemplateDeductionInfo &Info) {
2330 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2331 TemplateParameterList *TemplateParams
2332 = FunctionTemplate->getTemplateParameters();
2334 if (ExplicitTemplateArgs.size() == 0) {
2335 // No arguments to substitute; just copy over the parameter types and
2336 // fill in the function type.
2337 for (FunctionDecl::param_iterator P = Function->param_begin(),
2338 PEnd = Function->param_end();
2341 ParamTypes.push_back((*P)->getType());
2344 *FunctionType = Function->getType();
2348 // Unevaluated SFINAE context.
2349 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2350 SFINAETrap Trap(*this);
2352 // C++ [temp.arg.explicit]p3:
2353 // Template arguments that are present shall be specified in the
2354 // declaration order of their corresponding template-parameters. The
2355 // template argument list shall not specify more template-arguments than
2356 // there are corresponding template-parameters.
2357 SmallVector<TemplateArgument, 4> Builder;
2359 // Enter a new template instantiation context where we check the
2360 // explicitly-specified template arguments against this function template,
2361 // and then substitute them into the function parameter types.
2362 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2363 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
2364 FunctionTemplate, DeducedArgs,
2365 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution,
2368 return TDK_InstantiationDepth;
2370 if (CheckTemplateArgumentList(FunctionTemplate,
2372 ExplicitTemplateArgs,
2374 Builder) || Trap.hasErrorOccurred()) {
2375 unsigned Index = Builder.size();
2376 if (Index >= TemplateParams->size())
2377 Index = TemplateParams->size() - 1;
2378 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
2379 return TDK_InvalidExplicitArguments;
2382 // Form the template argument list from the explicitly-specified
2383 // template arguments.
2384 TemplateArgumentList *ExplicitArgumentList
2385 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2386 Info.reset(ExplicitArgumentList);
2388 // Template argument deduction and the final substitution should be
2389 // done in the context of the templated declaration. Explicit
2390 // argument substitution, on the other hand, needs to happen in the
2392 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2394 // If we deduced template arguments for a template parameter pack,
2395 // note that the template argument pack is partially substituted and record
2396 // the explicit template arguments. They'll be used as part of deduction
2397 // for this template parameter pack.
2398 for (unsigned I = 0, N = Builder.size(); I != N; ++I) {
2399 const TemplateArgument &Arg = Builder[I];
2400 if (Arg.getKind() == TemplateArgument::Pack) {
2401 CurrentInstantiationScope->SetPartiallySubstitutedPack(
2402 TemplateParams->getParam(I),
2409 const FunctionProtoType *Proto
2410 = Function->getType()->getAs<FunctionProtoType>();
2411 assert(Proto && "Function template does not have a prototype?");
2413 // Instantiate the types of each of the function parameters given the
2414 // explicitly-specified template arguments. If the function has a trailing
2415 // return type, substitute it after the arguments to ensure we substitute
2416 // in lexical order.
2417 if (Proto->hasTrailingReturn()) {
2418 if (SubstParmTypes(Function->getLocation(),
2419 Function->param_begin(), Function->getNumParams(),
2420 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2422 return TDK_SubstitutionFailure;
2425 // Instantiate the return type.
2426 // FIXME: exception-specifications?
2427 QualType ResultType;
2429 // C++11 [expr.prim.general]p3:
2430 // If a declaration declares a member function or member function
2431 // template of a class X, the expression this is a prvalue of type
2432 // "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
2433 // and the end of the function-definition, member-declarator, or
2435 unsigned ThisTypeQuals = 0;
2436 CXXRecordDecl *ThisContext = 0;
2437 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
2438 ThisContext = Method->getParent();
2439 ThisTypeQuals = Method->getTypeQualifiers();
2442 CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
2443 getLangOpts().CPlusPlus11);
2445 ResultType = SubstType(Proto->getResultType(),
2446 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2447 Function->getTypeSpecStartLoc(),
2448 Function->getDeclName());
2449 if (ResultType.isNull() || Trap.hasErrorOccurred())
2450 return TDK_SubstitutionFailure;
2453 // Instantiate the types of each of the function parameters given the
2454 // explicitly-specified template arguments if we didn't do so earlier.
2455 if (!Proto->hasTrailingReturn() &&
2456 SubstParmTypes(Function->getLocation(),
2457 Function->param_begin(), Function->getNumParams(),
2458 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2460 return TDK_SubstitutionFailure;
2463 *FunctionType = BuildFunctionType(ResultType, ParamTypes,
2464 Function->getLocation(),
2465 Function->getDeclName(),
2466 Proto->getExtProtoInfo());
2467 if (FunctionType->isNull() || Trap.hasErrorOccurred())
2468 return TDK_SubstitutionFailure;
2471 // C++ [temp.arg.explicit]p2:
2472 // Trailing template arguments that can be deduced (14.8.2) may be
2473 // omitted from the list of explicit template-arguments. If all of the
2474 // template arguments can be deduced, they may all be omitted; in this
2475 // case, the empty template argument list <> itself may also be omitted.
2477 // Take all of the explicitly-specified arguments and put them into
2478 // the set of deduced template arguments. Explicitly-specified
2479 // parameter packs, however, will be set to NULL since the deduction
2480 // mechanisms handle explicitly-specified argument packs directly.
2481 Deduced.reserve(TemplateParams->size());
2482 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) {
2483 const TemplateArgument &Arg = ExplicitArgumentList->get(I);
2484 if (Arg.getKind() == TemplateArgument::Pack)
2485 Deduced.push_back(DeducedTemplateArgument());
2487 Deduced.push_back(Arg);
2493 /// \brief Check whether the deduced argument type for a call to a function
2494 /// template matches the actual argument type per C++ [temp.deduct.call]p4.
2496 CheckOriginalCallArgDeduction(Sema &S, Sema::OriginalCallArg OriginalArg,
2497 QualType DeducedA) {
2498 ASTContext &Context = S.Context;
2500 QualType A = OriginalArg.OriginalArgType;
2501 QualType OriginalParamType = OriginalArg.OriginalParamType;
2503 // Check for type equality (top-level cv-qualifiers are ignored).
2504 if (Context.hasSameUnqualifiedType(A, DeducedA))
2507 // Strip off references on the argument types; they aren't needed for
2508 // the following checks.
2509 if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
2510 DeducedA = DeducedARef->getPointeeType();
2511 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
2512 A = ARef->getPointeeType();
2514 // C++ [temp.deduct.call]p4:
2515 // [...] However, there are three cases that allow a difference:
2516 // - If the original P is a reference type, the deduced A (i.e., the
2517 // type referred to by the reference) can be more cv-qualified than
2518 // the transformed A.
2519 if (const ReferenceType *OriginalParamRef
2520 = OriginalParamType->getAs<ReferenceType>()) {
2521 // We don't want to keep the reference around any more.
2522 OriginalParamType = OriginalParamRef->getPointeeType();
2524 Qualifiers AQuals = A.getQualifiers();
2525 Qualifiers DeducedAQuals = DeducedA.getQualifiers();
2527 // Under Objective-C++ ARC, the deduced type may have implicitly been
2528 // given strong lifetime. If so, update the original qualifiers to
2529 // include this strong lifetime.
2530 if (S.getLangOpts().ObjCAutoRefCount &&
2531 DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong &&
2532 AQuals.getObjCLifetime() == Qualifiers::OCL_None) {
2533 AQuals.setObjCLifetime(Qualifiers::OCL_Strong);
2536 if (AQuals == DeducedAQuals) {
2537 // Qualifiers match; there's nothing to do.
2538 } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) {
2541 // Qualifiers are compatible, so have the argument type adopt the
2542 // deduced argument type's qualifiers as if we had performed the
2543 // qualification conversion.
2544 A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
2548 // - The transformed A can be another pointer or pointer to member
2549 // type that can be converted to the deduced A via a qualification
2552 // Also allow conversions which merely strip [[noreturn]] from function types
2553 // (recursively) as an extension.
2554 // FIXME: Currently, this doesn't place nicely with qualfication conversions.
2555 bool ObjCLifetimeConversion = false;
2557 if ((A->isAnyPointerType() || A->isMemberPointerType()) &&
2558 (S.IsQualificationConversion(A, DeducedA, false,
2559 ObjCLifetimeConversion) ||
2560 S.IsNoReturnConversion(A, DeducedA, ResultTy)))
2564 // - If P is a class and P has the form simple-template-id, then the
2565 // transformed A can be a derived class of the deduced A. [...]
2566 // [...] Likewise, if P is a pointer to a class of the form
2567 // simple-template-id, the transformed A can be a pointer to a
2568 // derived class pointed to by the deduced A.
2569 if (const PointerType *OriginalParamPtr
2570 = OriginalParamType->getAs<PointerType>()) {
2571 if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
2572 if (const PointerType *APtr = A->getAs<PointerType>()) {
2573 if (A->getPointeeType()->isRecordType()) {
2574 OriginalParamType = OriginalParamPtr->getPointeeType();
2575 DeducedA = DeducedAPtr->getPointeeType();
2576 A = APtr->getPointeeType();
2582 if (Context.hasSameUnqualifiedType(A, DeducedA))
2585 if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) &&
2586 S.IsDerivedFrom(A, DeducedA))
2592 /// \brief Finish template argument deduction for a function template,
2593 /// checking the deduced template arguments for completeness and forming
2594 /// the function template specialization.
2596 /// \param OriginalCallArgs If non-NULL, the original call arguments against
2597 /// which the deduced argument types should be compared.
2598 Sema::TemplateDeductionResult
2599 Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate,
2600 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2601 unsigned NumExplicitlySpecified,
2602 FunctionDecl *&Specialization,
2603 TemplateDeductionInfo &Info,
2604 SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs) {
2605 TemplateParameterList *TemplateParams
2606 = FunctionTemplate->getTemplateParameters();
2608 // Unevaluated SFINAE context.
2609 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2610 SFINAETrap Trap(*this);
2612 // Enter a new template instantiation context while we instantiate the
2613 // actual function declaration.
2614 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2615 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
2616 FunctionTemplate, DeducedArgs,
2617 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution,
2620 return TDK_InstantiationDepth;
2622 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2624 // C++ [temp.deduct.type]p2:
2625 // [...] or if any template argument remains neither deduced nor
2626 // explicitly specified, template argument deduction fails.
2627 SmallVector<TemplateArgument, 4> Builder;
2628 for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2629 NamedDecl *Param = TemplateParams->getParam(I);
2631 if (!Deduced[I].isNull()) {
2632 if (I < NumExplicitlySpecified) {
2633 // We have already fully type-checked and converted this
2634 // argument, because it was explicitly-specified. Just record the
2635 // presence of this argument.
2636 Builder.push_back(Deduced[I]);
2640 // We have deduced this argument, so it still needs to be
2641 // checked and converted.
2643 // First, for a non-type template parameter type that is
2644 // initialized by a declaration, we need the type of the
2645 // corresponding non-type template parameter.
2647 if (NonTypeTemplateParmDecl *NTTP
2648 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2649 NTTPType = NTTP->getType();
2650 if (NTTPType->isDependentType()) {
2651 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2652 Builder.data(), Builder.size());
2653 NTTPType = SubstType(NTTPType,
2654 MultiLevelTemplateArgumentList(TemplateArgs),
2655 NTTP->getLocation(),
2656 NTTP->getDeclName());
2657 if (NTTPType.isNull()) {
2658 Info.Param = makeTemplateParameter(Param);
2659 // FIXME: These template arguments are temporary. Free them!
2660 Info.reset(TemplateArgumentList::CreateCopy(Context,
2663 return TDK_SubstitutionFailure;
2668 if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I],
2669 FunctionTemplate, NTTPType, 0, Info,
2671 Info.Param = makeTemplateParameter(Param);
2672 // FIXME: These template arguments are temporary. Free them!
2673 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2675 return TDK_SubstitutionFailure;
2681 // C++0x [temp.arg.explicit]p3:
2682 // A trailing template parameter pack (14.5.3) not otherwise deduced will
2683 // be deduced to an empty sequence of template arguments.
2684 // FIXME: Where did the word "trailing" come from?
2685 if (Param->isTemplateParameterPack()) {
2686 // We may have had explicitly-specified template arguments for this
2687 // template parameter pack. If so, our empty deduction extends the
2688 // explicitly-specified set (C++0x [temp.arg.explicit]p9).
2689 const TemplateArgument *ExplicitArgs;
2690 unsigned NumExplicitArgs;
2691 if (CurrentInstantiationScope &&
2692 CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs,
2695 Builder.push_back(TemplateArgument(ExplicitArgs, NumExplicitArgs));
2697 // Forget the partially-substituted pack; it's substitution is now
2699 CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2701 Builder.push_back(TemplateArgument::getEmptyPack());
2706 // Substitute into the default template argument, if available.
2707 TemplateArgumentLoc DefArg
2708 = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate,
2709 FunctionTemplate->getLocation(),
2710 FunctionTemplate->getSourceRange().getEnd(),
2714 // If there was no default argument, deduction is incomplete.
2715 if (DefArg.getArgument().isNull()) {
2716 Info.Param = makeTemplateParameter(
2717 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2718 return TDK_Incomplete;
2721 // Check whether we can actually use the default argument.
2722 if (CheckTemplateArgument(Param, DefArg,
2724 FunctionTemplate->getLocation(),
2725 FunctionTemplate->getSourceRange().getEnd(),
2728 Info.Param = makeTemplateParameter(
2729 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2730 // FIXME: These template arguments are temporary. Free them!
2731 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2733 return TDK_SubstitutionFailure;
2736 // If we get here, we successfully used the default template argument.
2739 // Form the template argument list from the deduced template arguments.
2740 TemplateArgumentList *DeducedArgumentList
2741 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2742 Info.reset(DeducedArgumentList);
2744 // Substitute the deduced template arguments into the function template
2745 // declaration to produce the function template specialization.
2746 DeclContext *Owner = FunctionTemplate->getDeclContext();
2747 if (FunctionTemplate->getFriendObjectKind())
2748 Owner = FunctionTemplate->getLexicalDeclContext();
2749 Specialization = cast_or_null<FunctionDecl>(
2750 SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner,
2751 MultiLevelTemplateArgumentList(*DeducedArgumentList)));
2752 if (!Specialization || Specialization->isInvalidDecl())
2753 return TDK_SubstitutionFailure;
2755 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
2756 FunctionTemplate->getCanonicalDecl());
2758 // If the template argument list is owned by the function template
2759 // specialization, release it.
2760 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
2761 !Trap.hasErrorOccurred())
2764 // There may have been an error that did not prevent us from constructing a
2765 // declaration. Mark the declaration invalid and return with a substitution
2767 if (Trap.hasErrorOccurred()) {
2768 Specialization->setInvalidDecl(true);
2769 return TDK_SubstitutionFailure;
2772 if (OriginalCallArgs) {
2773 // C++ [temp.deduct.call]p4:
2774 // In general, the deduction process attempts to find template argument
2775 // values that will make the deduced A identical to A (after the type A
2776 // is transformed as described above). [...]
2777 for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
2778 OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
2779 unsigned ParamIdx = OriginalArg.ArgIdx;
2781 if (ParamIdx >= Specialization->getNumParams())
2784 QualType DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
2785 if (CheckOriginalCallArgDeduction(*this, OriginalArg, DeducedA))
2786 return Sema::TDK_SubstitutionFailure;
2790 // If we suppressed any diagnostics while performing template argument
2791 // deduction, and if we haven't already instantiated this declaration,
2792 // keep track of these diagnostics. They'll be emitted if this specialization
2793 // is actually used.
2794 if (Info.diag_begin() != Info.diag_end()) {
2795 llvm::DenseMap<Decl *, SmallVector<PartialDiagnosticAt, 1> >::iterator
2796 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
2797 if (Pos == SuppressedDiagnostics.end())
2798 SuppressedDiagnostics[Specialization->getCanonicalDecl()]
2799 .append(Info.diag_begin(), Info.diag_end());
2805 /// Gets the type of a function for template-argument-deducton
2806 /// purposes when it's considered as part of an overload set.
2807 static QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R,
2809 // We may need to deduce the return type of the function now.
2810 if (S.getLangOpts().CPlusPlus1y && Fn->getResultType()->isUndeducedType() &&
2811 S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/false))
2814 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
2815 if (Method->isInstance()) {
2816 // An instance method that's referenced in a form that doesn't
2817 // look like a member pointer is just invalid.
2818 if (!R.HasFormOfMemberPointer) return QualType();
2820 return S.Context.getMemberPointerType(Fn->getType(),
2821 S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
2824 if (!R.IsAddressOfOperand) return Fn->getType();
2825 return S.Context.getPointerType(Fn->getType());
2828 /// Apply the deduction rules for overload sets.
2830 /// \return the null type if this argument should be treated as an
2831 /// undeduced context
2833 ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
2834 Expr *Arg, QualType ParamType,
2835 bool ParamWasReference) {
2837 OverloadExpr::FindResult R = OverloadExpr::find(Arg);
2839 OverloadExpr *Ovl = R.Expression;
2841 // C++0x [temp.deduct.call]p4
2843 if (ParamWasReference)
2844 TDF |= TDF_ParamWithReferenceType;
2845 if (R.IsAddressOfOperand)
2846 TDF |= TDF_IgnoreQualifiers;
2848 // C++0x [temp.deduct.call]p6:
2849 // When P is a function type, pointer to function type, or pointer
2850 // to member function type:
2852 if (!ParamType->isFunctionType() &&
2853 !ParamType->isFunctionPointerType() &&
2854 !ParamType->isMemberFunctionPointerType()) {
2855 if (Ovl->hasExplicitTemplateArgs()) {
2856 // But we can still look for an explicit specialization.
2857 if (FunctionDecl *ExplicitSpec
2858 = S.ResolveSingleFunctionTemplateSpecialization(Ovl))
2859 return GetTypeOfFunction(S, R, ExplicitSpec);
2865 // Gather the explicit template arguments, if any.
2866 TemplateArgumentListInfo ExplicitTemplateArgs;
2867 if (Ovl->hasExplicitTemplateArgs())
2868 Ovl->getExplicitTemplateArgs().copyInto(ExplicitTemplateArgs);
2870 for (UnresolvedSetIterator I = Ovl->decls_begin(),
2871 E = Ovl->decls_end(); I != E; ++I) {
2872 NamedDecl *D = (*I)->getUnderlyingDecl();
2874 if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
2875 // - If the argument is an overload set containing one or more
2876 // function templates, the parameter is treated as a
2877 // non-deduced context.
2878 if (!Ovl->hasExplicitTemplateArgs())
2881 // Otherwise, see if we can resolve a function type
2882 FunctionDecl *Specialization = 0;
2883 TemplateDeductionInfo Info(Ovl->getNameLoc());
2884 if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
2885 Specialization, Info))
2891 FunctionDecl *Fn = cast<FunctionDecl>(D);
2892 QualType ArgType = GetTypeOfFunction(S, R, Fn);
2893 if (ArgType.isNull()) continue;
2895 // Function-to-pointer conversion.
2896 if (!ParamWasReference && ParamType->isPointerType() &&
2897 ArgType->isFunctionType())
2898 ArgType = S.Context.getPointerType(ArgType);
2900 // - If the argument is an overload set (not containing function
2901 // templates), trial argument deduction is attempted using each
2902 // of the members of the set. If deduction succeeds for only one
2903 // of the overload set members, that member is used as the
2904 // argument value for the deduction. If deduction succeeds for
2905 // more than one member of the overload set the parameter is
2906 // treated as a non-deduced context.
2908 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
2909 // Type deduction is done independently for each P/A pair, and
2910 // the deduced template argument values are then combined.
2911 // So we do not reject deductions which were made elsewhere.
2912 SmallVector<DeducedTemplateArgument, 8>
2913 Deduced(TemplateParams->size());
2914 TemplateDeductionInfo Info(Ovl->getNameLoc());
2915 Sema::TemplateDeductionResult Result
2916 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
2917 ArgType, Info, Deduced, TDF);
2918 if (Result) continue;
2919 if (!Match.isNull()) return QualType();
2926 /// \brief Perform the adjustments to the parameter and argument types
2927 /// described in C++ [temp.deduct.call].
2929 /// \returns true if the caller should not attempt to perform any template
2930 /// argument deduction based on this P/A pair because the argument is an
2931 /// overloaded function set that could not be resolved.
2932 static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
2933 TemplateParameterList *TemplateParams,
2934 QualType &ParamType,
2938 // C++0x [temp.deduct.call]p3:
2939 // If P is a cv-qualified type, the top level cv-qualifiers of P's type
2940 // are ignored for type deduction.
2941 if (ParamType.hasQualifiers())
2942 ParamType = ParamType.getUnqualifiedType();
2943 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
2945 QualType PointeeType = ParamRefType->getPointeeType();
2947 // If the argument has incomplete array type, try to complete its type.
2948 if (ArgType->isIncompleteArrayType() && !S.RequireCompleteExprType(Arg, 0))
2949 ArgType = Arg->getType();
2951 // [C++0x] If P is an rvalue reference to a cv-unqualified
2952 // template parameter and the argument is an lvalue, the type
2953 // "lvalue reference to A" is used in place of A for type
2955 if (isa<RValueReferenceType>(ParamType)) {
2956 if (!PointeeType.getQualifiers() &&
2957 isa<TemplateTypeParmType>(PointeeType) &&
2958 Arg->Classify(S.Context).isLValue() &&
2959 Arg->getType() != S.Context.OverloadTy &&
2960 Arg->getType() != S.Context.BoundMemberTy)
2961 ArgType = S.Context.getLValueReferenceType(ArgType);
2964 // [...] If P is a reference type, the type referred to by P is used
2965 // for type deduction.
2966 ParamType = PointeeType;
2969 // Overload sets usually make this parameter an undeduced
2970 // context, but there are sometimes special circumstances.
2971 if (ArgType == S.Context.OverloadTy) {
2972 ArgType = ResolveOverloadForDeduction(S, TemplateParams,
2975 if (ArgType.isNull())
2980 // C++0x [temp.deduct.call]p3:
2981 // [...] If P is of the form T&&, where T is a template parameter, and
2982 // the argument is an lvalue, the type A& is used in place of A for
2984 if (ParamRefType->isRValueReferenceType() &&
2985 ParamRefType->getAs<TemplateTypeParmType>() &&
2987 ArgType = S.Context.getLValueReferenceType(ArgType);
2989 // C++ [temp.deduct.call]p2:
2990 // If P is not a reference type:
2991 // - If A is an array type, the pointer type produced by the
2992 // array-to-pointer standard conversion (4.2) is used in place of
2993 // A for type deduction; otherwise,
2994 if (ArgType->isArrayType())
2995 ArgType = S.Context.getArrayDecayedType(ArgType);
2996 // - If A is a function type, the pointer type produced by the
2997 // function-to-pointer standard conversion (4.3) is used in place
2998 // of A for type deduction; otherwise,
2999 else if (ArgType->isFunctionType())
3000 ArgType = S.Context.getPointerType(ArgType);
3002 // - If A is a cv-qualified type, the top level cv-qualifiers of A's
3003 // type are ignored for type deduction.
3004 ArgType = ArgType.getUnqualifiedType();
3008 // C++0x [temp.deduct.call]p4:
3009 // In general, the deduction process attempts to find template argument
3010 // values that will make the deduced A identical to A (after the type A
3011 // is transformed as described above). [...]
3012 TDF = TDF_SkipNonDependent;
3014 // - If the original P is a reference type, the deduced A (i.e., the
3015 // type referred to by the reference) can be more cv-qualified than
3016 // the transformed A.
3018 TDF |= TDF_ParamWithReferenceType;
3019 // - The transformed A can be another pointer or pointer to member
3020 // type that can be converted to the deduced A via a qualification
3021 // conversion (4.4).
3022 if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
3023 ArgType->isObjCObjectPointerType())
3024 TDF |= TDF_IgnoreQualifiers;
3025 // - If P is a class and P has the form simple-template-id, then the
3026 // transformed A can be a derived class of the deduced A. Likewise,
3027 // if P is a pointer to a class of the form simple-template-id, the
3028 // transformed A can be a pointer to a derived class pointed to by
3030 if (isSimpleTemplateIdType(ParamType) ||
3031 (isa<PointerType>(ParamType) &&
3032 isSimpleTemplateIdType(
3033 ParamType->getAs<PointerType>()->getPointeeType())))
3034 TDF |= TDF_DerivedClass;
3039 static bool hasDeducibleTemplateParameters(Sema &S,
3040 FunctionTemplateDecl *FunctionTemplate,
3043 /// \brief Perform template argument deduction by matching a parameter type
3044 /// against a single expression, where the expression is an element of
3045 /// an initializer list that was originally matched against a parameter
3046 /// of type \c initializer_list\<ParamType\>.
3047 static Sema::TemplateDeductionResult
3048 DeduceTemplateArgumentByListElement(Sema &S,
3049 TemplateParameterList *TemplateParams,
3050 QualType ParamType, Expr *Arg,
3051 TemplateDeductionInfo &Info,
3052 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3054 // Handle the case where an init list contains another init list as the
3056 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3058 if (!S.isStdInitializerList(ParamType.getNonReferenceType(), &X))
3059 return Sema::TDK_Success; // Just ignore this expression.
3061 // Recurse down into the init list.
3062 for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) {
3063 if (Sema::TemplateDeductionResult Result =
3064 DeduceTemplateArgumentByListElement(S, TemplateParams, X,
3066 Info, Deduced, TDF))
3069 return Sema::TDK_Success;
3072 // For all other cases, just match by type.
3073 QualType ArgType = Arg->getType();
3074 if (AdjustFunctionParmAndArgTypesForDeduction(S, TemplateParams, ParamType,
3075 ArgType, Arg, TDF)) {
3076 Info.Expression = Arg;
3077 return Sema::TDK_FailedOverloadResolution;
3079 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3080 ArgType, Info, Deduced, TDF);
3083 /// \brief Perform template argument deduction from a function call
3084 /// (C++ [temp.deduct.call]).
3086 /// \param FunctionTemplate the function template for which we are performing
3087 /// template argument deduction.
3089 /// \param ExplicitTemplateArgs the explicit template arguments provided
3092 /// \param Args the function call arguments
3094 /// \param Specialization if template argument deduction was successful,
3095 /// this will be set to the function template specialization produced by
3096 /// template argument deduction.
3098 /// \param Info the argument will be updated to provide additional information
3099 /// about template argument deduction.
3101 /// \returns the result of template argument deduction.
3102 Sema::TemplateDeductionResult
3103 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3104 TemplateArgumentListInfo *ExplicitTemplateArgs,
3105 llvm::ArrayRef<Expr *> Args,
3106 FunctionDecl *&Specialization,
3107 TemplateDeductionInfo &Info) {
3108 if (FunctionTemplate->isInvalidDecl())
3111 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3113 // C++ [temp.deduct.call]p1:
3114 // Template argument deduction is done by comparing each function template
3115 // parameter type (call it P) with the type of the corresponding argument
3116 // of the call (call it A) as described below.
3117 unsigned CheckArgs = Args.size();
3118 if (Args.size() < Function->getMinRequiredArguments())
3119 return TDK_TooFewArguments;
3120 else if (Args.size() > Function->getNumParams()) {
3121 const FunctionProtoType *Proto
3122 = Function->getType()->getAs<FunctionProtoType>();
3123 if (Proto->isTemplateVariadic())
3125 else if (Proto->isVariadic())
3126 CheckArgs = Function->getNumParams();
3128 return TDK_TooManyArguments;
3131 // The types of the parameters from which we will perform template argument
3133 LocalInstantiationScope InstScope(*this);
3134 TemplateParameterList *TemplateParams
3135 = FunctionTemplate->getTemplateParameters();
3136 SmallVector<DeducedTemplateArgument, 4> Deduced;
3137 SmallVector<QualType, 4> ParamTypes;
3138 unsigned NumExplicitlySpecified = 0;
3139 if (ExplicitTemplateArgs) {
3140 TemplateDeductionResult Result =
3141 SubstituteExplicitTemplateArguments(FunctionTemplate,
3142 *ExplicitTemplateArgs,
3150 NumExplicitlySpecified = Deduced.size();
3152 // Just fill in the parameter types from the function declaration.
3153 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
3154 ParamTypes.push_back(Function->getParamDecl(I)->getType());
3157 // Deduce template arguments from the function parameters.
3158 Deduced.resize(TemplateParams->size());
3159 unsigned ArgIdx = 0;
3160 SmallVector<OriginalCallArg, 4> OriginalCallArgs;
3161 for (unsigned ParamIdx = 0, NumParams = ParamTypes.size();
3162 ParamIdx != NumParams; ++ParamIdx) {
3163 QualType OrigParamType = ParamTypes[ParamIdx];
3164 QualType ParamType = OrigParamType;
3166 const PackExpansionType *ParamExpansion
3167 = dyn_cast<PackExpansionType>(ParamType);
3168 if (!ParamExpansion) {
3169 // Simple case: matching a function parameter to a function argument.
3170 if (ArgIdx >= CheckArgs)
3173 Expr *Arg = Args[ArgIdx++];
3174 QualType ArgType = Arg->getType();
3177 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
3178 ParamType, ArgType, Arg,
3182 // If we have nothing to deduce, we're done.
3183 if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3186 // If the argument is an initializer list ...
3187 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3188 // ... then the parameter is an undeduced context, unless the parameter
3189 // type is (reference to cv) std::initializer_list<P'>, in which case
3190 // deduction is done for each element of the initializer list, and the
3191 // result is the deduced type if it's the same for all elements.
3193 // Removing references was already done.
3194 if (!isStdInitializerList(ParamType, &X))
3197 for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) {
3198 if (TemplateDeductionResult Result =
3199 DeduceTemplateArgumentByListElement(*this, TemplateParams, X,
3201 Info, Deduced, TDF))
3204 // Don't track the argument type, since an initializer list has none.
3208 // Keep track of the argument type and corresponding parameter index,
3209 // so we can check for compatibility between the deduced A and A.
3210 OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx-1,
3213 if (TemplateDeductionResult Result
3214 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3216 Info, Deduced, TDF))
3222 // C++0x [temp.deduct.call]p1:
3223 // For a function parameter pack that occurs at the end of the
3224 // parameter-declaration-list, the type A of each remaining argument of
3225 // the call is compared with the type P of the declarator-id of the
3226 // function parameter pack. Each comparison deduces template arguments
3227 // for subsequent positions in the template parameter packs expanded by
3228 // the function parameter pack. For a function parameter pack that does
3229 // not occur at the end of the parameter-declaration-list, the type of
3230 // the parameter pack is a non-deduced context.
3231 if (ParamIdx + 1 < NumParams)
3234 QualType ParamPattern = ParamExpansion->getPattern();
3235 SmallVector<unsigned, 2> PackIndices;
3237 llvm::SmallBitVector SawIndices(TemplateParams->size());
3238 SmallVector<UnexpandedParameterPack, 2> Unexpanded;
3239 collectUnexpandedParameterPacks(ParamPattern, Unexpanded);
3240 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
3241 unsigned Depth, Index;
3242 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
3243 if (Depth == 0 && !SawIndices[Index]) {
3244 SawIndices[Index] = true;
3245 PackIndices.push_back(Index);
3249 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
3251 // Keep track of the deduced template arguments for each parameter pack
3252 // expanded by this pack expansion (the outer index) and for each
3253 // template argument (the inner SmallVectors).
3254 SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2>
3255 NewlyDeducedPacks(PackIndices.size());
3256 SmallVector<DeducedTemplateArgument, 2>
3257 SavedPacks(PackIndices.size());
3258 PrepareArgumentPackDeduction(*this, Deduced, PackIndices, SavedPacks,
3260 bool HasAnyArguments = false;
3261 for (; ArgIdx < Args.size(); ++ArgIdx) {
3262 HasAnyArguments = true;
3264 QualType OrigParamType = ParamPattern;
3265 ParamType = OrigParamType;
3266 Expr *Arg = Args[ArgIdx];
3267 QualType ArgType = Arg->getType();
3270 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
3271 ParamType, ArgType, Arg,
3273 // We can't actually perform any deduction for this argument, so stop
3274 // deduction at this point.
3279 // As above, initializer lists need special handling.
3280 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3282 if (!isStdInitializerList(ParamType, &X)) {
3287 for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) {
3288 if (TemplateDeductionResult Result =
3289 DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, X,
3290 ILE->getInit(i)->getType(),
3291 Info, Deduced, TDF))
3296 // Keep track of the argument type and corresponding argument index,
3297 // so we can check for compatibility between the deduced A and A.
3298 if (hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3299 OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx,
3302 if (TemplateDeductionResult Result
3303 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3304 ParamType, ArgType, Info,
3309 // Capture the deduced template arguments for each parameter pack expanded
3310 // by this pack expansion, add them to the list of arguments we've deduced
3311 // for that pack, then clear out the deduced argument.
3312 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
3313 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
3314 if (!DeducedArg.isNull()) {
3315 NewlyDeducedPacks[I].push_back(DeducedArg);
3316 DeducedArg = DeducedTemplateArgument();
3321 // Build argument packs for each of the parameter packs expanded by this
3323 if (Sema::TemplateDeductionResult Result
3324 = FinishArgumentPackDeduction(*this, TemplateParams, HasAnyArguments,
3325 Deduced, PackIndices, SavedPacks,
3326 NewlyDeducedPacks, Info))
3329 // After we've matching against a parameter pack, we're done.
3333 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3334 NumExplicitlySpecified,
3335 Specialization, Info, &OriginalCallArgs);
3338 /// \brief Deduce template arguments when taking the address of a function
3339 /// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
3342 /// \param FunctionTemplate the function template for which we are performing
3343 /// template argument deduction.
3345 /// \param ExplicitTemplateArgs the explicitly-specified template
3348 /// \param ArgFunctionType the function type that will be used as the
3349 /// "argument" type (A) when performing template argument deduction from the
3350 /// function template's function type. This type may be NULL, if there is no
3351 /// argument type to compare against, in C++0x [temp.arg.explicit]p3.
3353 /// \param Specialization if template argument deduction was successful,
3354 /// this will be set to the function template specialization produced by
3355 /// template argument deduction.
3357 /// \param Info the argument will be updated to provide additional information
3358 /// about template argument deduction.
3360 /// \returns the result of template argument deduction.
3361 Sema::TemplateDeductionResult
3362 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3363 TemplateArgumentListInfo *ExplicitTemplateArgs,
3364 QualType ArgFunctionType,
3365 FunctionDecl *&Specialization,
3366 TemplateDeductionInfo &Info,
3367 bool InOverloadResolution) {
3368 if (FunctionTemplate->isInvalidDecl())
3371 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3372 TemplateParameterList *TemplateParams
3373 = FunctionTemplate->getTemplateParameters();
3374 QualType FunctionType = Function->getType();
3376 // Substitute any explicit template arguments.
3377 LocalInstantiationScope InstScope(*this);
3378 SmallVector<DeducedTemplateArgument, 4> Deduced;
3379 unsigned NumExplicitlySpecified = 0;
3380 SmallVector<QualType, 4> ParamTypes;
3381 if (ExplicitTemplateArgs) {
3382 if (TemplateDeductionResult Result
3383 = SubstituteExplicitTemplateArguments(FunctionTemplate,
3384 *ExplicitTemplateArgs,
3385 Deduced, ParamTypes,
3386 &FunctionType, Info))
3389 NumExplicitlySpecified = Deduced.size();
3392 // Unevaluated SFINAE context.
3393 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
3394 SFINAETrap Trap(*this);
3396 Deduced.resize(TemplateParams->size());
3398 // If the function has a deduced return type, substitute it for a dependent
3399 // type so that we treat it as a non-deduced context in what follows.
3400 bool HasUndeducedReturnType = false;
3401 if (getLangOpts().CPlusPlus1y && InOverloadResolution &&
3402 Function->getResultType()->isUndeducedType()) {
3403 FunctionType = SubstAutoType(FunctionType, Context.DependentTy);
3404 HasUndeducedReturnType = true;
3407 if (!ArgFunctionType.isNull()) {
3408 unsigned TDF = TDF_TopLevelParameterTypeList;
3409 if (InOverloadResolution) TDF |= TDF_InOverloadResolution;
3410 // Deduce template arguments from the function type.
3411 if (TemplateDeductionResult Result
3412 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3413 FunctionType, ArgFunctionType,
3414 Info, Deduced, TDF))
3418 if (TemplateDeductionResult Result
3419 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3420 NumExplicitlySpecified,
3421 Specialization, Info))
3424 // If the function has a deduced return type, deduce it now, so we can check
3425 // that the deduced function type matches the requested type.
3426 if (HasUndeducedReturnType &&
3427 Specialization->getResultType()->isUndeducedType() &&
3428 DeduceReturnType(Specialization, Info.getLocation(), false))
3429 return TDK_MiscellaneousDeductionFailure;
3431 // If the requested function type does not match the actual type of the
3432 // specialization with respect to arguments of compatible pointer to function
3433 // types, template argument deduction fails.
3434 if (!ArgFunctionType.isNull()) {
3435 if (InOverloadResolution && !isSameOrCompatibleFunctionType(
3436 Context.getCanonicalType(Specialization->getType()),
3437 Context.getCanonicalType(ArgFunctionType)))
3438 return TDK_MiscellaneousDeductionFailure;
3439 else if(!InOverloadResolution &&
3440 !Context.hasSameType(Specialization->getType(), ArgFunctionType))
3441 return TDK_MiscellaneousDeductionFailure;
3447 /// \brief Deduce template arguments for a templated conversion
3448 /// function (C++ [temp.deduct.conv]) and, if successful, produce a
3449 /// conversion function template specialization.
3450 Sema::TemplateDeductionResult
3451 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3453 CXXConversionDecl *&Specialization,
3454 TemplateDeductionInfo &Info) {
3455 if (FunctionTemplate->isInvalidDecl())
3458 CXXConversionDecl *Conv
3459 = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl());
3460 QualType FromType = Conv->getConversionType();
3462 // Canonicalize the types for deduction.
3463 QualType P = Context.getCanonicalType(FromType);
3464 QualType A = Context.getCanonicalType(ToType);
3466 // C++0x [temp.deduct.conv]p2:
3467 // If P is a reference type, the type referred to by P is used for
3469 if (const ReferenceType *PRef = P->getAs<ReferenceType>())
3470 P = PRef->getPointeeType();
3472 // C++0x [temp.deduct.conv]p4:
3473 // [...] If A is a reference type, the type referred to by A is used
3474 // for type deduction.
3475 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3476 A = ARef->getPointeeType().getUnqualifiedType();
3477 // C++ [temp.deduct.conv]p3:
3479 // If A is not a reference type:
3481 assert(!A->isReferenceType() && "Reference types were handled above");
3483 // - If P is an array type, the pointer type produced by the
3484 // array-to-pointer standard conversion (4.2) is used in place
3485 // of P for type deduction; otherwise,
3486 if (P->isArrayType())
3487 P = Context.getArrayDecayedType(P);
3488 // - If P is a function type, the pointer type produced by the
3489 // function-to-pointer standard conversion (4.3) is used in
3490 // place of P for type deduction; otherwise,
3491 else if (P->isFunctionType())
3492 P = Context.getPointerType(P);
3493 // - If P is a cv-qualified type, the top level cv-qualifiers of
3494 // P's type are ignored for type deduction.
3496 P = P.getUnqualifiedType();
3498 // C++0x [temp.deduct.conv]p4:
3499 // If A is a cv-qualified type, the top level cv-qualifiers of A's
3500 // type are ignored for type deduction. If A is a reference type, the type
3501 // referred to by A is used for type deduction.
3502 A = A.getUnqualifiedType();
3505 // Unevaluated SFINAE context.
3506 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
3507 SFINAETrap Trap(*this);
3509 // C++ [temp.deduct.conv]p1:
3510 // Template argument deduction is done by comparing the return
3511 // type of the template conversion function (call it P) with the
3512 // type that is required as the result of the conversion (call it
3513 // A) as described in 14.8.2.4.
3514 TemplateParameterList *TemplateParams
3515 = FunctionTemplate->getTemplateParameters();
3516 SmallVector<DeducedTemplateArgument, 4> Deduced;
3517 Deduced.resize(TemplateParams->size());
3519 // C++0x [temp.deduct.conv]p4:
3520 // In general, the deduction process attempts to find template
3521 // argument values that will make the deduced A identical to
3522 // A. However, there are two cases that allow a difference:
3524 // - If the original A is a reference type, A can be more
3525 // cv-qualified than the deduced A (i.e., the type referred to
3526 // by the reference)
3527 if (ToType->isReferenceType())
3528 TDF |= TDF_ParamWithReferenceType;
3529 // - The deduced A can be another pointer or pointer to member
3530 // type that can be converted to A via a qualification
3533 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
3534 // both P and A are pointers or member pointers. In this case, we
3535 // just ignore cv-qualifiers completely).
3536 if ((P->isPointerType() && A->isPointerType()) ||
3537 (P->isMemberPointerType() && A->isMemberPointerType()))
3538 TDF |= TDF_IgnoreQualifiers;
3539 if (TemplateDeductionResult Result
3540 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3541 P, A, Info, Deduced, TDF))
3544 // Finish template argument deduction.
3545 LocalInstantiationScope InstScope(*this);
3546 FunctionDecl *Spec = 0;
3547 TemplateDeductionResult Result
3548 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec,
3550 Specialization = cast_or_null<CXXConversionDecl>(Spec);
3554 /// \brief Deduce template arguments for a function template when there is
3555 /// nothing to deduce against (C++0x [temp.arg.explicit]p3).
3557 /// \param FunctionTemplate the function template for which we are performing
3558 /// template argument deduction.
3560 /// \param ExplicitTemplateArgs the explicitly-specified template
3563 /// \param Specialization if template argument deduction was successful,
3564 /// this will be set to the function template specialization produced by
3565 /// template argument deduction.
3567 /// \param Info the argument will be updated to provide additional information
3568 /// about template argument deduction.
3570 /// \returns the result of template argument deduction.
3571 Sema::TemplateDeductionResult
3572 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3573 TemplateArgumentListInfo *ExplicitTemplateArgs,
3574 FunctionDecl *&Specialization,
3575 TemplateDeductionInfo &Info,
3576 bool InOverloadResolution) {
3577 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
3578 QualType(), Specialization, Info,
3579 InOverloadResolution);
3583 /// Substitute the 'auto' type specifier within a type for a given replacement
3585 class SubstituteAutoTransform :
3586 public TreeTransform<SubstituteAutoTransform> {
3587 QualType Replacement;
3589 SubstituteAutoTransform(Sema &SemaRef, QualType Replacement) :
3590 TreeTransform<SubstituteAutoTransform>(SemaRef), Replacement(Replacement) {
3592 QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
3593 // If we're building the type pattern to deduce against, don't wrap the
3594 // substituted type in an AutoType. Certain template deduction rules
3595 // apply only when a template type parameter appears directly (and not if
3596 // the parameter is found through desugaring). For instance:
3597 // auto &&lref = lvalue;
3598 // must transform into "rvalue reference to T" not "rvalue reference to
3599 // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
3600 if (!Replacement.isNull() && isa<TemplateTypeParmType>(Replacement)) {
3601 QualType Result = Replacement;
3602 TemplateTypeParmTypeLoc NewTL =
3603 TLB.push<TemplateTypeParmTypeLoc>(Result);
3604 NewTL.setNameLoc(TL.getNameLoc());
3608 !Replacement.isNull() && Replacement->isDependentType();
3610 SemaRef.Context.getAutoType(Dependent ? QualType() : Replacement,
3611 TL.getTypePtr()->isDecltypeAuto(),
3613 AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result);
3614 NewTL.setNameLoc(TL.getNameLoc());
3619 ExprResult TransformLambdaExpr(LambdaExpr *E) {
3620 // Lambdas never need to be transformed.
3624 QualType Apply(TypeLoc TL) {
3625 // Create some scratch storage for the transformed type locations.
3626 // FIXME: We're just going to throw this information away. Don't build it.
3628 TLB.reserve(TL.getFullDataSize());
3629 return TransformType(TLB, TL);
3634 Sema::DeduceAutoResult
3635 Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result) {
3636 return DeduceAutoType(Type->getTypeLoc(), Init, Result);
3639 /// \brief Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6)
3641 /// \param Type the type pattern using the auto type-specifier.
3642 /// \param Init the initializer for the variable whose type is to be deduced.
3643 /// \param Result if type deduction was successful, this will be set to the
3645 Sema::DeduceAutoResult
3646 Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
3647 if (Init->getType()->isNonOverloadPlaceholderType()) {
3648 ExprResult NonPlaceholder = CheckPlaceholderExpr(Init);
3649 if (NonPlaceholder.isInvalid())
3650 return DAR_FailedAlreadyDiagnosed;
3651 Init = NonPlaceholder.take();
3654 if (Init->isTypeDependent() || Type.getType()->isDependentType()) {
3655 Result = SubstituteAutoTransform(*this, Context.DependentTy).Apply(Type);
3656 assert(!Result.isNull() && "substituting DependentTy can't fail");
3657 return DAR_Succeeded;
3660 // If this is a 'decltype(auto)' specifier, do the decltype dance.
3661 // Since 'decltype(auto)' can only occur at the top of the type, we
3662 // don't need to go digging for it.
3663 if (const AutoType *AT = Type.getType()->getAs<AutoType>()) {
3664 if (AT->isDecltypeAuto()) {
3665 if (isa<InitListExpr>(Init)) {
3666 Diag(Init->getLocStart(), diag::err_decltype_auto_initializer_list);
3667 return DAR_FailedAlreadyDiagnosed;
3670 QualType Deduced = BuildDecltypeType(Init, Init->getLocStart());
3671 // FIXME: Support a non-canonical deduced type for 'auto'.
3672 Deduced = Context.getCanonicalType(Deduced);
3673 Result = SubstituteAutoTransform(*this, Deduced).Apply(Type);
3674 if (Result.isNull())
3675 return DAR_FailedAlreadyDiagnosed;
3676 return DAR_Succeeded;
3680 SourceLocation Loc = Init->getExprLoc();
3682 LocalInstantiationScope InstScope(*this);
3684 // Build template<class TemplParam> void Func(FuncParam);
3685 TemplateTypeParmDecl *TemplParam =
3686 TemplateTypeParmDecl::Create(Context, 0, SourceLocation(), Loc, 0, 0, 0,
3688 QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
3689 NamedDecl *TemplParamPtr = TemplParam;
3690 FixedSizeTemplateParameterList<1> TemplateParams(Loc, Loc, &TemplParamPtr,
3693 QualType FuncParam = SubstituteAutoTransform(*this, TemplArg).Apply(Type);
3694 assert(!FuncParam.isNull() &&
3695 "substituting template parameter for 'auto' failed");
3697 // Deduce type of TemplParam in Func(Init)
3698 SmallVector<DeducedTemplateArgument, 1> Deduced;
3700 QualType InitType = Init->getType();
3703 TemplateDeductionInfo Info(Loc);
3705 InitListExpr *InitList = dyn_cast<InitListExpr>(Init);
3707 for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) {
3708 if (DeduceTemplateArgumentByListElement(*this, &TemplateParams,
3710 InitList->getInit(i),
3711 Info, Deduced, TDF))
3715 if (AdjustFunctionParmAndArgTypesForDeduction(*this, &TemplateParams,
3716 FuncParam, InitType, Init,
3720 if (DeduceTemplateArgumentsByTypeMatch(*this, &TemplateParams, FuncParam,
3721 InitType, Info, Deduced, TDF))
3725 if (Deduced[0].getKind() != TemplateArgument::Type)
3728 QualType DeducedType = Deduced[0].getAsType();
3731 DeducedType = BuildStdInitializerList(DeducedType, Loc);
3732 if (DeducedType.isNull())
3733 return DAR_FailedAlreadyDiagnosed;
3736 Result = SubstituteAutoTransform(*this, DeducedType).Apply(Type);
3737 if (Result.isNull())
3738 return DAR_FailedAlreadyDiagnosed;
3740 // Check that the deduced argument type is compatible with the original
3741 // argument type per C++ [temp.deduct.call]p4.
3742 if (!InitList && !Result.isNull() &&
3743 CheckOriginalCallArgDeduction(*this,
3744 Sema::OriginalCallArg(FuncParam,0,InitType),
3746 Result = QualType();
3750 return DAR_Succeeded;
3753 QualType Sema::SubstAutoType(QualType Type, QualType Deduced) {
3754 return SubstituteAutoTransform(*this, Deduced).TransformType(Type);
3757 void Sema::DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init) {
3758 if (isa<InitListExpr>(Init))
3759 Diag(VDecl->getLocation(),
3760 diag::err_auto_var_deduction_failure_from_init_list)
3761 << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange();
3763 Diag(VDecl->getLocation(), diag::err_auto_var_deduction_failure)
3764 << VDecl->getDeclName() << VDecl->getType() << Init->getType()
3765 << Init->getSourceRange();
3768 bool Sema::DeduceReturnType(FunctionDecl *FD, SourceLocation Loc,
3770 assert(FD->getResultType()->isUndeducedType());
3772 if (FD->getTemplateInstantiationPattern())
3773 InstantiateFunctionDefinition(Loc, FD);
3775 bool StillUndeduced = FD->getResultType()->isUndeducedType();
3776 if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) {
3777 Diag(Loc, diag::err_auto_fn_used_before_defined) << FD;
3778 Diag(FD->getLocation(), diag::note_callee_decl) << FD;
3781 return StillUndeduced;
3785 MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
3788 llvm::SmallBitVector &Deduced);
3790 /// \brief If this is a non-static member function,
3791 static void AddImplicitObjectParameterType(ASTContext &Context,
3792 CXXMethodDecl *Method,
3793 SmallVectorImpl<QualType> &ArgTypes) {
3794 // C++11 [temp.func.order]p3:
3795 // [...] The new parameter is of type "reference to cv A," where cv are
3796 // the cv-qualifiers of the function template (if any) and A is
3797 // the class of which the function template is a member.
3799 // The standard doesn't say explicitly, but we pick the appropriate kind of
3800 // reference type based on [over.match.funcs]p4.
3801 QualType ArgTy = Context.getTypeDeclType(Method->getParent());
3802 ArgTy = Context.getQualifiedType(ArgTy,
3803 Qualifiers::fromCVRMask(Method->getTypeQualifiers()));
3804 if (Method->getRefQualifier() == RQ_RValue)
3805 ArgTy = Context.getRValueReferenceType(ArgTy);
3807 ArgTy = Context.getLValueReferenceType(ArgTy);
3808 ArgTypes.push_back(ArgTy);
3811 /// \brief Determine whether the function template \p FT1 is at least as
3812 /// specialized as \p FT2.
3813 static bool isAtLeastAsSpecializedAs(Sema &S,
3815 FunctionTemplateDecl *FT1,
3816 FunctionTemplateDecl *FT2,
3817 TemplatePartialOrderingContext TPOC,
3818 unsigned NumCallArguments,
3819 SmallVectorImpl<RefParamPartialOrderingComparison> *RefParamComparisons) {
3820 FunctionDecl *FD1 = FT1->getTemplatedDecl();
3821 FunctionDecl *FD2 = FT2->getTemplatedDecl();
3822 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>();
3823 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>();
3825 assert(Proto1 && Proto2 && "Function templates must have prototypes");
3826 TemplateParameterList *TemplateParams = FT2->getTemplateParameters();
3827 SmallVector<DeducedTemplateArgument, 4> Deduced;
3828 Deduced.resize(TemplateParams->size());
3830 // C++0x [temp.deduct.partial]p3:
3831 // The types used to determine the ordering depend on the context in which
3832 // the partial ordering is done:
3833 TemplateDeductionInfo Info(Loc);
3834 CXXMethodDecl *Method1 = 0;
3835 CXXMethodDecl *Method2 = 0;
3836 bool IsNonStatic2 = false;
3837 bool IsNonStatic1 = false;
3841 // - In the context of a function call, the function parameter types are
3843 Method1 = dyn_cast<CXXMethodDecl>(FD1);
3844 Method2 = dyn_cast<CXXMethodDecl>(FD2);
3845 IsNonStatic1 = Method1 && !Method1->isStatic();
3846 IsNonStatic2 = Method2 && !Method2->isStatic();
3848 // C++11 [temp.func.order]p3:
3849 // [...] If only one of the function templates is a non-static
3850 // member, that function template is considered to have a new
3851 // first parameter inserted in its function parameter list. The
3852 // new parameter is of type "reference to cv A," where cv are
3853 // the cv-qualifiers of the function template (if any) and A is
3854 // the class of which the function template is a member.
3856 // Note that we interpret this to mean "if one of the function
3857 // templates is a non-static member and the other is a non-member";
3858 // otherwise, the ordering rules for static functions against non-static
3859 // functions don't make any sense.
3861 // C++98/03 doesn't have this provision, so instead we drop the
3862 // first argument of the free function, which seems to match
3863 // existing practice.
3864 SmallVector<QualType, 4> Args1;
3865 unsigned Skip1 = !S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !Method1;
3866 if (S.getLangOpts().CPlusPlus11 && IsNonStatic1 && !Method2)
3867 AddImplicitObjectParameterType(S.Context, Method1, Args1);
3868 Args1.insert(Args1.end(),
3869 Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end());
3871 SmallVector<QualType, 4> Args2;
3872 Skip2 = !S.getLangOpts().CPlusPlus11 && IsNonStatic1 && !Method2;
3873 if (S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !Method1)
3874 AddImplicitObjectParameterType(S.Context, Method2, Args2);
3875 Args2.insert(Args2.end(),
3876 Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end());
3878 // C++ [temp.func.order]p5:
3879 // The presence of unused ellipsis and default arguments has no effect on
3880 // the partial ordering of function templates.
3881 if (Args1.size() > NumCallArguments)
3882 Args1.resize(NumCallArguments);
3883 if (Args2.size() > NumCallArguments)
3884 Args2.resize(NumCallArguments);
3885 if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(),
3886 Args1.data(), Args1.size(), Info, Deduced,
3887 TDF_None, /*PartialOrdering=*/true,
3888 RefParamComparisons))
3894 case TPOC_Conversion:
3895 // - In the context of a call to a conversion operator, the return types
3896 // of the conversion function templates are used.
3897 if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
3898 Proto2->getResultType(),
3899 Proto1->getResultType(),
3900 Info, Deduced, TDF_None,
3901 /*PartialOrdering=*/true,
3902 RefParamComparisons))
3907 // - In other contexts (14.6.6.2) the function template's function type
3909 if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
3910 FD2->getType(), FD1->getType(),
3911 Info, Deduced, TDF_None,
3912 /*PartialOrdering=*/true,
3913 RefParamComparisons))
3918 // C++0x [temp.deduct.partial]p11:
3919 // In most cases, all template parameters must have values in order for
3920 // deduction to succeed, but for partial ordering purposes a template
3921 // parameter may remain without a value provided it is not used in the
3922 // types being used for partial ordering. [ Note: a template parameter used
3923 // in a non-deduced context is considered used. -end note]
3924 unsigned ArgIdx = 0, NumArgs = Deduced.size();
3925 for (; ArgIdx != NumArgs; ++ArgIdx)
3926 if (Deduced[ArgIdx].isNull())
3929 if (ArgIdx == NumArgs) {
3930 // All template arguments were deduced. FT1 is at least as specialized
3935 // Figure out which template parameters were used.
3936 llvm::SmallBitVector UsedParameters(TemplateParams->size());
3939 unsigned NumParams = std::min(NumCallArguments,
3940 std::min(Proto1->getNumArgs(),
3941 Proto2->getNumArgs()));
3942 if (S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !IsNonStatic1)
3943 ::MarkUsedTemplateParameters(S.Context, Method2->getThisType(S.Context),
3945 TemplateParams->getDepth(), UsedParameters);
3946 for (unsigned I = Skip2; I < NumParams; ++I)
3947 ::MarkUsedTemplateParameters(S.Context, Proto2->getArgType(I), false,
3948 TemplateParams->getDepth(),
3953 case TPOC_Conversion:
3954 ::MarkUsedTemplateParameters(S.Context, Proto2->getResultType(), false,
3955 TemplateParams->getDepth(),
3960 ::MarkUsedTemplateParameters(S.Context, FD2->getType(), false,
3961 TemplateParams->getDepth(),
3966 for (; ArgIdx != NumArgs; ++ArgIdx)
3967 // If this argument had no value deduced but was used in one of the types
3968 // used for partial ordering, then deduction fails.
3969 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
3975 /// \brief Determine whether this a function template whose parameter-type-list
3976 /// ends with a function parameter pack.
3977 static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) {
3978 FunctionDecl *Function = FunTmpl->getTemplatedDecl();
3979 unsigned NumParams = Function->getNumParams();
3983 ParmVarDecl *Last = Function->getParamDecl(NumParams - 1);
3984 if (!Last->isParameterPack())
3987 // Make sure that no previous parameter is a parameter pack.
3988 while (--NumParams > 0) {
3989 if (Function->getParamDecl(NumParams - 1)->isParameterPack())
3996 /// \brief Returns the more specialized function template according
3997 /// to the rules of function template partial ordering (C++ [temp.func.order]).
3999 /// \param FT1 the first function template
4001 /// \param FT2 the second function template
4003 /// \param TPOC the context in which we are performing partial ordering of
4004 /// function templates.
4006 /// \param NumCallArguments The number of arguments in a call, used only
4007 /// when \c TPOC is \c TPOC_Call.
4009 /// \returns the more specialized function template. If neither
4010 /// template is more specialized, returns NULL.
4011 FunctionTemplateDecl *
4012 Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1,
4013 FunctionTemplateDecl *FT2,
4015 TemplatePartialOrderingContext TPOC,
4016 unsigned NumCallArguments) {
4017 SmallVector<RefParamPartialOrderingComparison, 4> RefParamComparisons;
4018 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
4019 NumCallArguments, 0);
4020 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
4022 &RefParamComparisons);
4024 if (Better1 != Better2) // We have a clear winner
4025 return Better1? FT1 : FT2;
4027 if (!Better1 && !Better2) // Neither is better than the other
4030 // C++0x [temp.deduct.partial]p10:
4031 // If for each type being considered a given template is at least as
4032 // specialized for all types and more specialized for some set of types and
4033 // the other template is not more specialized for any types or is not at
4034 // least as specialized for any types, then the given template is more
4035 // specialized than the other template. Otherwise, neither template is more
4036 // specialized than the other.
4039 for (unsigned I = 0, N = RefParamComparisons.size(); I != N; ++I) {
4040 // C++0x [temp.deduct.partial]p9:
4041 // If, for a given type, deduction succeeds in both directions (i.e., the
4042 // types are identical after the transformations above) and both P and A
4043 // were reference types (before being replaced with the type referred to
4046 // -- if the type from the argument template was an lvalue reference
4047 // and the type from the parameter template was not, the argument
4048 // type is considered to be more specialized than the other;
4050 if (!RefParamComparisons[I].ArgIsRvalueRef &&
4051 RefParamComparisons[I].ParamIsRvalueRef) {
4056 } else if (!RefParamComparisons[I].ParamIsRvalueRef &&
4057 RefParamComparisons[I].ArgIsRvalueRef) {
4064 // -- if the type from the argument template is more cv-qualified than
4065 // the type from the parameter template (as described above), the
4066 // argument type is considered to be more specialized than the
4067 // other; otherwise,
4068 switch (RefParamComparisons[I].Qualifiers) {
4069 case NeitherMoreQualified:
4072 case ParamMoreQualified:
4078 case ArgMoreQualified:
4085 // -- neither type is more specialized than the other.
4088 assert(!(Better1 && Better2) && "Should have broken out in the loop above");
4094 // FIXME: This mimics what GCC implements, but doesn't match up with the
4095 // proposed resolution for core issue 692. This area needs to be sorted out,
4096 // but for now we attempt to maintain compatibility.
4097 bool Variadic1 = isVariadicFunctionTemplate(FT1);
4098 bool Variadic2 = isVariadicFunctionTemplate(FT2);
4099 if (Variadic1 != Variadic2)
4100 return Variadic1? FT2 : FT1;
4105 /// \brief Determine if the two templates are equivalent.
4106 static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) {
4113 return T1->getCanonicalDecl() == T2->getCanonicalDecl();
4116 /// \brief Retrieve the most specialized of the given function template
4117 /// specializations.
4119 /// \param SpecBegin the start iterator of the function template
4120 /// specializations that we will be comparing.
4122 /// \param SpecEnd the end iterator of the function template
4123 /// specializations, paired with \p SpecBegin.
4125 /// \param TPOC the partial ordering context to use to compare the function
4126 /// template specializations.
4128 /// \param NumCallArguments The number of arguments in a call, used only
4129 /// when \c TPOC is \c TPOC_Call.
4131 /// \param Loc the location where the ambiguity or no-specializations
4132 /// diagnostic should occur.
4134 /// \param NoneDiag partial diagnostic used to diagnose cases where there are
4135 /// no matching candidates.
4137 /// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one
4140 /// \param CandidateDiag partial diagnostic used for each function template
4141 /// specialization that is a candidate in the ambiguous ordering. One parameter
4142 /// in this diagnostic should be unbound, which will correspond to the string
4143 /// describing the template arguments for the function template specialization.
4145 /// \returns the most specialized function template specialization, if
4146 /// found. Otherwise, returns SpecEnd.
4148 /// \todo FIXME: Consider passing in the "also-ran" candidates that failed
4149 /// template argument deduction.
4150 UnresolvedSetIterator
4151 Sema::getMostSpecialized(UnresolvedSetIterator SpecBegin,
4152 UnresolvedSetIterator SpecEnd,
4153 TemplatePartialOrderingContext TPOC,
4154 unsigned NumCallArguments,
4156 const PartialDiagnostic &NoneDiag,
4157 const PartialDiagnostic &AmbigDiag,
4158 const PartialDiagnostic &CandidateDiag,
4160 QualType TargetType) {
4161 if (SpecBegin == SpecEnd) {
4163 Diag(Loc, NoneDiag);
4167 if (SpecBegin + 1 == SpecEnd)
4170 // Find the function template that is better than all of the templates it
4171 // has been compared to.
4172 UnresolvedSetIterator Best = SpecBegin;
4173 FunctionTemplateDecl *BestTemplate
4174 = cast<FunctionDecl>(*Best)->getPrimaryTemplate();
4175 assert(BestTemplate && "Not a function template specialization?");
4176 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) {
4177 FunctionTemplateDecl *Challenger
4178 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4179 assert(Challenger && "Not a function template specialization?");
4180 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4181 Loc, TPOC, NumCallArguments),
4184 BestTemplate = Challenger;
4188 // Make sure that the "best" function template is more specialized than all
4190 bool Ambiguous = false;
4191 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4192 FunctionTemplateDecl *Challenger
4193 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4195 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4196 Loc, TPOC, NumCallArguments),
4204 // We found an answer. Return it.
4208 // Diagnose the ambiguity.
4210 Diag(Loc, AmbigDiag);
4212 // FIXME: Can we order the candidates in some sane way?
4213 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4214 PartialDiagnostic PD = CandidateDiag;
4215 PD << getTemplateArgumentBindingsText(
4216 cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(),
4217 *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs());
4218 if (!TargetType.isNull())
4219 HandleFunctionTypeMismatch(PD, cast<FunctionDecl>(*I)->getType(),
4221 Diag((*I)->getLocation(), PD);
4228 /// \brief Returns the more specialized class template partial specialization
4229 /// according to the rules of partial ordering of class template partial
4230 /// specializations (C++ [temp.class.order]).
4232 /// \param PS1 the first class template partial specialization
4234 /// \param PS2 the second class template partial specialization
4236 /// \returns the more specialized class template partial specialization. If
4237 /// neither partial specialization is more specialized, returns NULL.
4238 ClassTemplatePartialSpecializationDecl *
4239 Sema::getMoreSpecializedPartialSpecialization(
4240 ClassTemplatePartialSpecializationDecl *PS1,
4241 ClassTemplatePartialSpecializationDecl *PS2,
4242 SourceLocation Loc) {
4243 // C++ [temp.class.order]p1:
4244 // For two class template partial specializations, the first is at least as
4245 // specialized as the second if, given the following rewrite to two
4246 // function templates, the first function template is at least as
4247 // specialized as the second according to the ordering rules for function
4248 // templates (14.6.6.2):
4249 // - the first function template has the same template parameters as the
4250 // first partial specialization and has a single function parameter
4251 // whose type is a class template specialization with the template
4252 // arguments of the first partial specialization, and
4253 // - the second function template has the same template parameters as the
4254 // second partial specialization and has a single function parameter
4255 // whose type is a class template specialization with the template
4256 // arguments of the second partial specialization.
4258 // Rather than synthesize function templates, we merely perform the
4259 // equivalent partial ordering by performing deduction directly on
4260 // the template arguments of the class template partial
4261 // specializations. This computation is slightly simpler than the
4262 // general problem of function template partial ordering, because
4263 // class template partial specializations are more constrained. We
4264 // know that every template parameter is deducible from the class
4265 // template partial specialization's template arguments, for
4267 SmallVector<DeducedTemplateArgument, 4> Deduced;
4268 TemplateDeductionInfo Info(Loc);
4270 QualType PT1 = PS1->getInjectedSpecializationType();
4271 QualType PT2 = PS2->getInjectedSpecializationType();
4273 // Determine whether PS1 is at least as specialized as PS2
4274 Deduced.resize(PS2->getTemplateParameters()->size());
4275 bool Better1 = !DeduceTemplateArgumentsByTypeMatch(*this,
4276 PS2->getTemplateParameters(),
4277 PT2, PT1, Info, Deduced, TDF_None,
4278 /*PartialOrdering=*/true,
4279 /*RefParamComparisons=*/0);
4281 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end());
4282 InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2,
4284 Better1 = !::FinishTemplateArgumentDeduction(*this, PS2,
4285 PS1->getTemplateArgs(),
4289 // Determine whether PS2 is at least as specialized as PS1
4291 Deduced.resize(PS1->getTemplateParameters()->size());
4292 bool Better2 = !DeduceTemplateArgumentsByTypeMatch(*this,
4293 PS1->getTemplateParameters(),
4294 PT1, PT2, Info, Deduced, TDF_None,
4295 /*PartialOrdering=*/true,
4296 /*RefParamComparisons=*/0);
4298 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end());
4299 InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1,
4301 Better2 = !::FinishTemplateArgumentDeduction(*this, PS1,
4302 PS2->getTemplateArgs(),
4306 if (Better1 == Better2)
4309 return Better1? PS1 : PS2;
4313 MarkUsedTemplateParameters(ASTContext &Ctx,
4314 const TemplateArgument &TemplateArg,
4317 llvm::SmallBitVector &Used);
4319 /// \brief Mark the template parameters that are used by the given
4322 MarkUsedTemplateParameters(ASTContext &Ctx,
4326 llvm::SmallBitVector &Used) {
4327 // We can deduce from a pack expansion.
4328 if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E))
4329 E = Expansion->getPattern();
4331 // Skip through any implicit casts we added while type-checking, and any
4332 // substitutions performed by template alias expansion.
4334 if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
4335 E = ICE->getSubExpr();
4336 else if (const SubstNonTypeTemplateParmExpr *Subst =
4337 dyn_cast<SubstNonTypeTemplateParmExpr>(E))
4338 E = Subst->getReplacement();
4343 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to
4344 // find other occurrences of template parameters.
4345 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
4349 const NonTypeTemplateParmDecl *NTTP
4350 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
4354 if (NTTP->getDepth() == Depth)
4355 Used[NTTP->getIndex()] = true;
4358 /// \brief Mark the template parameters that are used by the given
4359 /// nested name specifier.
4361 MarkUsedTemplateParameters(ASTContext &Ctx,
4362 NestedNameSpecifier *NNS,
4365 llvm::SmallBitVector &Used) {
4369 MarkUsedTemplateParameters(Ctx, NNS->getPrefix(), OnlyDeduced, Depth,
4371 MarkUsedTemplateParameters(Ctx, QualType(NNS->getAsType(), 0),
4372 OnlyDeduced, Depth, Used);
4375 /// \brief Mark the template parameters that are used by the given
4378 MarkUsedTemplateParameters(ASTContext &Ctx,
4382 llvm::SmallBitVector &Used) {
4383 if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
4384 if (TemplateTemplateParmDecl *TTP
4385 = dyn_cast<TemplateTemplateParmDecl>(Template)) {
4386 if (TTP->getDepth() == Depth)
4387 Used[TTP->getIndex()] = true;
4392 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName())
4393 MarkUsedTemplateParameters(Ctx, QTN->getQualifier(), OnlyDeduced,
4395 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName())
4396 MarkUsedTemplateParameters(Ctx, DTN->getQualifier(), OnlyDeduced,
4400 /// \brief Mark the template parameters that are used by the given
4403 MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
4406 llvm::SmallBitVector &Used) {
4410 // Non-dependent types have nothing deducible
4411 if (!T->isDependentType())
4414 T = Ctx.getCanonicalType(T);
4415 switch (T->getTypeClass()) {
4417 MarkUsedTemplateParameters(Ctx,
4418 cast<PointerType>(T)->getPointeeType(),
4424 case Type::BlockPointer:
4425 MarkUsedTemplateParameters(Ctx,
4426 cast<BlockPointerType>(T)->getPointeeType(),
4432 case Type::LValueReference:
4433 case Type::RValueReference:
4434 MarkUsedTemplateParameters(Ctx,
4435 cast<ReferenceType>(T)->getPointeeType(),
4441 case Type::MemberPointer: {
4442 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
4443 MarkUsedTemplateParameters(Ctx, MemPtr->getPointeeType(), OnlyDeduced,
4445 MarkUsedTemplateParameters(Ctx, QualType(MemPtr->getClass(), 0),
4446 OnlyDeduced, Depth, Used);
4450 case Type::DependentSizedArray:
4451 MarkUsedTemplateParameters(Ctx,
4452 cast<DependentSizedArrayType>(T)->getSizeExpr(),
4453 OnlyDeduced, Depth, Used);
4454 // Fall through to check the element type
4456 case Type::ConstantArray:
4457 case Type::IncompleteArray:
4458 MarkUsedTemplateParameters(Ctx,
4459 cast<ArrayType>(T)->getElementType(),
4460 OnlyDeduced, Depth, Used);
4464 case Type::ExtVector:
4465 MarkUsedTemplateParameters(Ctx,
4466 cast<VectorType>(T)->getElementType(),
4467 OnlyDeduced, Depth, Used);
4470 case Type::DependentSizedExtVector: {
4471 const DependentSizedExtVectorType *VecType
4472 = cast<DependentSizedExtVectorType>(T);
4473 MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced,
4475 MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced,
4480 case Type::FunctionProto: {
4481 const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
4482 MarkUsedTemplateParameters(Ctx, Proto->getResultType(), OnlyDeduced,
4484 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I)
4485 MarkUsedTemplateParameters(Ctx, Proto->getArgType(I), OnlyDeduced,
4490 case Type::TemplateTypeParm: {
4491 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T);
4492 if (TTP->getDepth() == Depth)
4493 Used[TTP->getIndex()] = true;
4497 case Type::SubstTemplateTypeParmPack: {
4498 const SubstTemplateTypeParmPackType *Subst
4499 = cast<SubstTemplateTypeParmPackType>(T);
4500 MarkUsedTemplateParameters(Ctx,
4501 QualType(Subst->getReplacedParameter(), 0),
4502 OnlyDeduced, Depth, Used);
4503 MarkUsedTemplateParameters(Ctx, Subst->getArgumentPack(),
4504 OnlyDeduced, Depth, Used);
4508 case Type::InjectedClassName:
4509 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType();
4512 case Type::TemplateSpecialization: {
4513 const TemplateSpecializationType *Spec
4514 = cast<TemplateSpecializationType>(T);
4515 MarkUsedTemplateParameters(Ctx, Spec->getTemplateName(), OnlyDeduced,
4518 // C++0x [temp.deduct.type]p9:
4519 // If the template argument list of P contains a pack expansion that is not
4520 // the last template argument, the entire template argument list is a
4521 // non-deduced context.
4523 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
4526 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4527 MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
4534 MarkUsedTemplateParameters(Ctx,
4535 cast<ComplexType>(T)->getElementType(),
4536 OnlyDeduced, Depth, Used);
4541 MarkUsedTemplateParameters(Ctx,
4542 cast<AtomicType>(T)->getValueType(),
4543 OnlyDeduced, Depth, Used);
4546 case Type::DependentName:
4548 MarkUsedTemplateParameters(Ctx,
4549 cast<DependentNameType>(T)->getQualifier(),
4550 OnlyDeduced, Depth, Used);
4553 case Type::DependentTemplateSpecialization: {
4554 const DependentTemplateSpecializationType *Spec
4555 = cast<DependentTemplateSpecializationType>(T);
4557 MarkUsedTemplateParameters(Ctx, Spec->getQualifier(),
4558 OnlyDeduced, Depth, Used);
4560 // C++0x [temp.deduct.type]p9:
4561 // If the template argument list of P contains a pack expansion that is not
4562 // the last template argument, the entire template argument list is a
4563 // non-deduced context.
4565 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
4568 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4569 MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
4576 MarkUsedTemplateParameters(Ctx,
4577 cast<TypeOfType>(T)->getUnderlyingType(),
4578 OnlyDeduced, Depth, Used);
4581 case Type::TypeOfExpr:
4583 MarkUsedTemplateParameters(Ctx,
4584 cast<TypeOfExprType>(T)->getUnderlyingExpr(),
4585 OnlyDeduced, Depth, Used);
4588 case Type::Decltype:
4590 MarkUsedTemplateParameters(Ctx,
4591 cast<DecltypeType>(T)->getUnderlyingExpr(),
4592 OnlyDeduced, Depth, Used);
4595 case Type::UnaryTransform:
4597 MarkUsedTemplateParameters(Ctx,
4598 cast<UnaryTransformType>(T)->getUnderlyingType(),
4599 OnlyDeduced, Depth, Used);
4602 case Type::PackExpansion:
4603 MarkUsedTemplateParameters(Ctx,
4604 cast<PackExpansionType>(T)->getPattern(),
4605 OnlyDeduced, Depth, Used);
4609 MarkUsedTemplateParameters(Ctx,
4610 cast<AutoType>(T)->getDeducedType(),
4611 OnlyDeduced, Depth, Used);
4613 // None of these types have any template parameters in them.
4615 case Type::VariableArray:
4616 case Type::FunctionNoProto:
4619 case Type::ObjCInterface:
4620 case Type::ObjCObject:
4621 case Type::ObjCObjectPointer:
4622 case Type::UnresolvedUsing:
4623 #define TYPE(Class, Base)
4624 #define ABSTRACT_TYPE(Class, Base)
4625 #define DEPENDENT_TYPE(Class, Base)
4626 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
4627 #include "clang/AST/TypeNodes.def"
4632 /// \brief Mark the template parameters that are used by this
4633 /// template argument.
4635 MarkUsedTemplateParameters(ASTContext &Ctx,
4636 const TemplateArgument &TemplateArg,
4639 llvm::SmallBitVector &Used) {
4640 switch (TemplateArg.getKind()) {
4641 case TemplateArgument::Null:
4642 case TemplateArgument::Integral:
4643 case TemplateArgument::Declaration:
4646 case TemplateArgument::NullPtr:
4647 MarkUsedTemplateParameters(Ctx, TemplateArg.getNullPtrType(), OnlyDeduced,
4651 case TemplateArgument::Type:
4652 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsType(), OnlyDeduced,
4656 case TemplateArgument::Template:
4657 case TemplateArgument::TemplateExpansion:
4658 MarkUsedTemplateParameters(Ctx,
4659 TemplateArg.getAsTemplateOrTemplatePattern(),
4660 OnlyDeduced, Depth, Used);
4663 case TemplateArgument::Expression:
4664 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsExpr(), OnlyDeduced,
4668 case TemplateArgument::Pack:
4669 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(),
4670 PEnd = TemplateArg.pack_end();
4672 MarkUsedTemplateParameters(Ctx, *P, OnlyDeduced, Depth, Used);
4677 /// \brief Mark which template parameters can be deduced from a given
4678 /// template argument list.
4680 /// \param TemplateArgs the template argument list from which template
4681 /// parameters will be deduced.
4683 /// \param Used a bit vector whose elements will be set to \c true
4684 /// to indicate when the corresponding template parameter will be
4687 Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs,
4688 bool OnlyDeduced, unsigned Depth,
4689 llvm::SmallBitVector &Used) {
4690 // C++0x [temp.deduct.type]p9:
4691 // If the template argument list of P contains a pack expansion that is not
4692 // the last template argument, the entire template argument list is a
4693 // non-deduced context.
4695 hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size()))
4698 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
4699 ::MarkUsedTemplateParameters(Context, TemplateArgs[I], OnlyDeduced,
4703 /// \brief Marks all of the template parameters that will be deduced by a
4704 /// call to the given function template.
4706 Sema::MarkDeducedTemplateParameters(ASTContext &Ctx,
4707 const FunctionTemplateDecl *FunctionTemplate,
4708 llvm::SmallBitVector &Deduced) {
4709 TemplateParameterList *TemplateParams
4710 = FunctionTemplate->getTemplateParameters();
4712 Deduced.resize(TemplateParams->size());
4714 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4715 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
4716 ::MarkUsedTemplateParameters(Ctx, Function->getParamDecl(I)->getType(),
4717 true, TemplateParams->getDepth(), Deduced);
4720 bool hasDeducibleTemplateParameters(Sema &S,
4721 FunctionTemplateDecl *FunctionTemplate,
4723 if (!T->isDependentType())
4726 TemplateParameterList *TemplateParams
4727 = FunctionTemplate->getTemplateParameters();
4728 llvm::SmallBitVector Deduced(TemplateParams->size());
4729 ::MarkUsedTemplateParameters(S.Context, T, true, TemplateParams->getDepth(),
4732 return Deduced.any();