clang 19.0.0git
SemaTemplateDeduction.cpp
Go to the documentation of this file.
1//===- SemaTemplateDeduction.cpp - Template Argument Deduction ------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements C++ template argument deduction.
10//
11//===----------------------------------------------------------------------===//
12
13#include "TreeTransform.h"
14#include "TypeLocBuilder.h"
16#include "clang/AST/ASTLambda.h"
17#include "clang/AST/Decl.h"
19#include "clang/AST/DeclBase.h"
20#include "clang/AST/DeclCXX.h"
23#include "clang/AST/Expr.h"
24#include "clang/AST/ExprCXX.h"
29#include "clang/AST/Type.h"
30#include "clang/AST/TypeLoc.h"
34#include "clang/Basic/LLVM.h"
41#include "clang/Sema/Sema.h"
42#include "clang/Sema/Template.h"
44#include "llvm/ADT/APInt.h"
45#include "llvm/ADT/APSInt.h"
46#include "llvm/ADT/ArrayRef.h"
47#include "llvm/ADT/DenseMap.h"
48#include "llvm/ADT/FoldingSet.h"
49#include "llvm/ADT/SmallBitVector.h"
50#include "llvm/ADT/SmallPtrSet.h"
51#include "llvm/ADT/SmallVector.h"
52#include "llvm/Support/Casting.h"
53#include "llvm/Support/Compiler.h"
54#include "llvm/Support/ErrorHandling.h"
55#include <algorithm>
56#include <cassert>
57#include <optional>
58#include <tuple>
59#include <type_traits>
60#include <utility>
61
62namespace clang {
63
64 /// Various flags that control template argument deduction.
65 ///
66 /// These flags can be bitwise-OR'd together.
68 /// No template argument deduction flags, which indicates the
69 /// strictest results for template argument deduction (as used for, e.g.,
70 /// matching class template partial specializations).
72
73 /// Within template argument deduction from a function call, we are
74 /// matching with a parameter type for which the original parameter was
75 /// a reference.
77
78 /// Within template argument deduction from a function call, we
79 /// are matching in a case where we ignore cv-qualifiers.
81
82 /// Within template argument deduction from a function call,
83 /// we are matching in a case where we can perform template argument
84 /// deduction from a template-id of a derived class of the argument type.
86
87 /// Allow non-dependent types to differ, e.g., when performing
88 /// template argument deduction from a function call where conversions
89 /// may apply.
91
92 /// Whether we are performing template argument deduction for
93 /// parameters and arguments in a top-level template argument
95
96 /// Within template argument deduction from overload resolution per
97 /// C++ [over.over] allow matching function types that are compatible in
98 /// terms of noreturn and default calling convention adjustments, or
99 /// similarly matching a declared template specialization against a
100 /// possible template, per C++ [temp.deduct.decl]. In either case, permit
101 /// deduction where the parameter is a function type that can be converted
102 /// to the argument type.
104
105 /// Within template argument deduction for a conversion function, we are
106 /// matching with an argument type for which the original argument was
107 /// a reference.
109 };
110}
111
112using namespace clang;
113using namespace sema;
114
115/// Compare two APSInts, extending and switching the sign as
116/// necessary to compare their values regardless of underlying type.
117static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) {
118 if (Y.getBitWidth() > X.getBitWidth())
119 X = X.extend(Y.getBitWidth());
120 else if (Y.getBitWidth() < X.getBitWidth())
121 Y = Y.extend(X.getBitWidth());
122
123 // If there is a signedness mismatch, correct it.
124 if (X.isSigned() != Y.isSigned()) {
125 // If the signed value is negative, then the values cannot be the same.
126 if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative()))
127 return false;
128
129 Y.setIsSigned(true);
130 X.setIsSigned(true);
131 }
132
133 return X == Y;
134}
135
137 Sema &S, TemplateParameterList *TemplateParams, QualType Param,
139 SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF,
140 bool PartialOrdering = false, bool DeducedFromArrayBound = false);
141
148 bool NumberOfArgumentsMustMatch);
149
152 bool OnlyDeduced, unsigned Depth,
153 llvm::SmallBitVector &Used);
154
156 bool OnlyDeduced, unsigned Level,
157 llvm::SmallBitVector &Deduced);
158
159/// If the given expression is of a form that permits the deduction
160/// of a non-type template parameter, return the declaration of that
161/// non-type template parameter.
162static const NonTypeTemplateParmDecl *
163getDeducedParameterFromExpr(const Expr *E, unsigned Depth) {
164 // If we are within an alias template, the expression may have undergone
165 // any number of parameter substitutions already.
166 while (true) {
167 if (const auto *IC = dyn_cast<ImplicitCastExpr>(E))
168 E = IC->getSubExpr();
169 else if (const auto *CE = dyn_cast<ConstantExpr>(E))
170 E = CE->getSubExpr();
171 else if (const auto *Subst = dyn_cast<SubstNonTypeTemplateParmExpr>(E))
172 E = Subst->getReplacement();
173 else if (const auto *CCE = dyn_cast<CXXConstructExpr>(E)) {
174 // Look through implicit copy construction from an lvalue of the same type.
175 if (CCE->getParenOrBraceRange().isValid())
176 break;
177 // Note, there could be default arguments.
178 assert(CCE->getNumArgs() >= 1 && "implicit construct expr should have 1 arg");
179 E = CCE->getArg(0);
180 } else
181 break;
182 }
183
184 if (const auto *DRE = dyn_cast<DeclRefExpr>(E))
185 if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()))
186 if (NTTP->getDepth() == Depth)
187 return NTTP;
188
189 return nullptr;
190}
191
192static const NonTypeTemplateParmDecl *
195}
196
197/// Determine whether two declaration pointers refer to the same
198/// declaration.
199static bool isSameDeclaration(Decl *X, Decl *Y) {
200 if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
201 X = NX->getUnderlyingDecl();
202 if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
203 Y = NY->getUnderlyingDecl();
204
205 return X->getCanonicalDecl() == Y->getCanonicalDecl();
206}
207
208/// Verify that the given, deduced template arguments are compatible.
209///
210/// \returns The deduced template argument, or a NULL template argument if
211/// the deduced template arguments were incompatible.
216 bool AggregateCandidateDeduction = false) {
217 // We have no deduction for one or both of the arguments; they're compatible.
218 if (X.isNull())
219 return Y;
220 if (Y.isNull())
221 return X;
222
223 // If we have two non-type template argument values deduced for the same
224 // parameter, they must both match the type of the parameter, and thus must
225 // match each other's type. As we're only keeping one of them, we must check
226 // for that now. The exception is that if either was deduced from an array
227 // bound, the type is permitted to differ.
228 if (!X.wasDeducedFromArrayBound() && !Y.wasDeducedFromArrayBound()) {
229 QualType XType = X.getNonTypeTemplateArgumentType();
230 if (!XType.isNull()) {
232 if (YType.isNull() || !Context.hasSameType(XType, YType))
234 }
235 }
236
237 switch (X.getKind()) {
239 llvm_unreachable("Non-deduced template arguments handled above");
240
242 // If two template type arguments have the same type, they're compatible.
243 QualType TX = X.getAsType(), TY = Y.getAsType();
244 if (Y.getKind() == TemplateArgument::Type && Context.hasSameType(TX, TY))
245 return DeducedTemplateArgument(Context.getCommonSugaredType(TX, TY),
246 X.wasDeducedFromArrayBound() ||
248
249 // If one of the two arguments was deduced from an array bound, the other
250 // supersedes it.
251 if (X.wasDeducedFromArrayBound() != Y.wasDeducedFromArrayBound())
252 return X.wasDeducedFromArrayBound() ? Y : X;
253
254 // The arguments are not compatible.
256 }
257
259 // If we deduced a constant in one case and either a dependent expression or
260 // declaration in another case, keep the integral constant.
261 // If both are integral constants with the same value, keep that value.
265 hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral())))
266 return X.wasDeducedFromArrayBound() ? Y : X;
267
268 // All other combinations are incompatible.
270
272 // If we deduced a value and a dependent expression, keep the value.
275 X.structurallyEquals(Y)))
276 return X;
277
278 // All other combinations are incompatible.
280
283 Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
284 return X;
285
286 // All other combinations are incompatible.
288
291 Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
293 return X;
294
295 // All other combinations are incompatible.
297
300 return checkDeducedTemplateArguments(Context, Y, X);
301
302 // Compare the expressions for equality
303 llvm::FoldingSetNodeID ID1, ID2;
304 X.getAsExpr()->Profile(ID1, Context, true);
305 Y.getAsExpr()->Profile(ID2, Context, true);
306 if (ID1 == ID2)
307 return X.wasDeducedFromArrayBound() ? Y : X;
308
309 // Differing dependent expressions are incompatible.
311 }
312
314 assert(!X.wasDeducedFromArrayBound());
315
316 // If we deduced a declaration and a dependent expression, keep the
317 // declaration.
319 return X;
320
321 // If we deduced a declaration and an integral constant, keep the
322 // integral constant and whichever type did not come from an array
323 // bound.
326 return TemplateArgument(Context, Y.getAsIntegral(),
327 X.getParamTypeForDecl());
328 return Y;
329 }
330
331 // If we deduced two declarations, make sure that they refer to the
332 // same declaration.
334 isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))
335 return X;
336
337 // All other combinations are incompatible.
339
341 // If we deduced a null pointer and a dependent expression, keep the
342 // null pointer.
345 X.getNullPtrType(), Y.getAsExpr()->getType()),
346 true);
347
348 // If we deduced a null pointer and an integral constant, keep the
349 // integral constant.
351 return Y;
352
353 // If we deduced two null pointers, they are the same.
355 return TemplateArgument(
356 Context.getCommonSugaredType(X.getNullPtrType(), Y.getNullPtrType()),
357 true);
358
359 // All other combinations are incompatible.
361
363 if (Y.getKind() != TemplateArgument::Pack ||
364 (!AggregateCandidateDeduction && X.pack_size() != Y.pack_size()))
366
369 XA = X.pack_begin(),
370 XAEnd = X.pack_end(), YA = Y.pack_begin(), YAEnd = Y.pack_end();
371 XA != XAEnd; ++XA, ++YA) {
372 if (YA != YAEnd) {
374 Context, DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
376 if (Merged.isNull() && !(XA->isNull() && YA->isNull()))
378 NewPack.push_back(Merged);
379 } else {
380 NewPack.push_back(*XA);
381 }
382 }
383
385 TemplateArgument::CreatePackCopy(Context, NewPack),
386 X.wasDeducedFromArrayBound() && Y.wasDeducedFromArrayBound());
387 }
388 }
389
390 llvm_unreachable("Invalid TemplateArgument Kind!");
391}
392
393/// Deduce the value of the given non-type template parameter
394/// as the given deduced template argument. All non-type template parameter
395/// deduction is funneled through here.
397 Sema &S, TemplateParameterList *TemplateParams,
398 const NonTypeTemplateParmDecl *NTTP,
399 const DeducedTemplateArgument &NewDeduced, QualType ValueType,
402 assert(NTTP->getDepth() == Info.getDeducedDepth() &&
403 "deducing non-type template argument with wrong depth");
404
406 S.Context, Deduced[NTTP->getIndex()], NewDeduced);
407 if (Result.isNull()) {
408 Info.Param = const_cast<NonTypeTemplateParmDecl*>(NTTP);
409 Info.FirstArg = Deduced[NTTP->getIndex()];
410 Info.SecondArg = NewDeduced;
411 return TemplateDeductionResult::Inconsistent;
412 }
413
414 Deduced[NTTP->getIndex()] = Result;
415 if (!S.getLangOpts().CPlusPlus17)
416 return TemplateDeductionResult::Success;
417
418 if (NTTP->isExpandedParameterPack())
419 // FIXME: We may still need to deduce parts of the type here! But we
420 // don't have any way to find which slice of the type to use, and the
421 // type stored on the NTTP itself is nonsense. Perhaps the type of an
422 // expanded NTTP should be a pack expansion type?
423 return TemplateDeductionResult::Success;
424
425 // Get the type of the parameter for deduction. If it's a (dependent) array
426 // or function type, we will not have decayed it yet, so do that now.
427 QualType ParamType = S.Context.getAdjustedParameterType(NTTP->getType());
428 if (auto *Expansion = dyn_cast<PackExpansionType>(ParamType))
429 ParamType = Expansion->getPattern();
430
431 // FIXME: It's not clear how deduction of a parameter of reference
432 // type from an argument (of non-reference type) should be performed.
433 // For now, we just remove reference types from both sides and let
434 // the final check for matching types sort out the mess.
435 ValueType = ValueType.getNonReferenceType();
436 if (ParamType->isReferenceType())
437 ParamType = ParamType.getNonReferenceType();
438 else
439 // Top-level cv-qualifiers are irrelevant for a non-reference type.
440 ValueType = ValueType.getUnqualifiedType();
441
443 S, TemplateParams, ParamType, ValueType, Info, Deduced,
444 TDF_SkipNonDependent, /*PartialOrdering=*/false,
445 /*ArrayBound=*/NewDeduced.wasDeducedFromArrayBound());
446}
447
448/// Deduce the value of the given non-type template parameter
449/// from the given integral constant.
451 Sema &S, TemplateParameterList *TemplateParams,
452 const NonTypeTemplateParmDecl *NTTP, const llvm::APSInt &Value,
453 QualType ValueType, bool DeducedFromArrayBound, TemplateDeductionInfo &Info,
456 S, TemplateParams, NTTP,
458 DeducedFromArrayBound),
459 ValueType, Info, Deduced);
460}
461
462/// Deduce the value of the given non-type template parameter
463/// from the given null pointer template argument type.
465 Sema &S, TemplateParameterList *TemplateParams,
466 const NonTypeTemplateParmDecl *NTTP, QualType NullPtrType,
471 NTTP->getLocation()),
472 NullPtrType,
473 NullPtrType->isMemberPointerType() ? CK_NullToMemberPointer
474 : CK_NullToPointer)
475 .get();
476 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
478 Value->getType(), Info, Deduced);
479}
480
481/// Deduce the value of the given non-type template parameter
482/// from the given type- or value-dependent expression.
483///
484/// \returns true if deduction succeeded, false otherwise.
486 Sema &S, TemplateParameterList *TemplateParams,
487 const NonTypeTemplateParmDecl *NTTP, Expr *Value,
490 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
492 Value->getType(), Info, Deduced);
493}
494
495/// Deduce the value of the given non-type template parameter
496/// from the given declaration.
497///
498/// \returns true if deduction succeeded, false otherwise.
500 Sema &S, TemplateParameterList *TemplateParams,
504 D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : nullptr;
505 TemplateArgument New(D, T);
507 S, TemplateParams, NTTP, DeducedTemplateArgument(New), T, Info, Deduced);
508}
509
512 TemplateName Param, TemplateName Arg,
515 TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
516 if (!ParamDecl) {
517 // The parameter type is dependent and is not a template template parameter,
518 // so there is nothing that we can deduce.
519 return TemplateDeductionResult::Success;
520 }
521
522 if (TemplateTemplateParmDecl *TempParam
523 = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
524 // If we're not deducing at this depth, there's nothing to deduce.
525 if (TempParam->getDepth() != Info.getDeducedDepth())
526 return TemplateDeductionResult::Success;
527
530 Deduced[TempParam->getIndex()],
531 NewDeduced);
532 if (Result.isNull()) {
533 Info.Param = TempParam;
534 Info.FirstArg = Deduced[TempParam->getIndex()];
535 Info.SecondArg = NewDeduced;
536 return TemplateDeductionResult::Inconsistent;
537 }
538
539 Deduced[TempParam->getIndex()] = Result;
540 return TemplateDeductionResult::Success;
541 }
542
543 // Verify that the two template names are equivalent.
544 if (S.Context.hasSameTemplateName(Param, Arg))
545 return TemplateDeductionResult::Success;
546
547 // Mismatch of non-dependent template parameter to argument.
548 Info.FirstArg = TemplateArgument(Param);
549 Info.SecondArg = TemplateArgument(Arg);
550 return TemplateDeductionResult::NonDeducedMismatch;
551}
552
553/// Deduce the template arguments by comparing the template parameter
554/// type (which is a template-id) with the template argument type.
555///
556/// \param S the Sema
557///
558/// \param TemplateParams the template parameters that we are deducing
559///
560/// \param P the parameter type
561///
562/// \param A the argument type
563///
564/// \param Info information about the template argument deduction itself
565///
566/// \param Deduced the deduced template arguments
567///
568/// \returns the result of template argument deduction so far. Note that a
569/// "success" result means that template argument deduction has not yet failed,
570/// but it may still fail, later, for other reasons.
573 const QualType P, QualType A,
576 QualType UP = P;
577 if (const auto *IP = P->getAs<InjectedClassNameType>())
578 UP = IP->getInjectedSpecializationType();
579 // FIXME: Try to preserve type sugar here, which is hard
580 // because of the unresolved template arguments.
581 const auto *TP = UP.getCanonicalType()->castAs<TemplateSpecializationType>();
582 TemplateName TNP = TP->getTemplateName();
583
584 // If the parameter is an alias template, there is nothing to deduce.
585 if (const auto *TD = TNP.getAsTemplateDecl(); TD && TD->isTypeAlias())
586 return TemplateDeductionResult::Success;
587
588 ArrayRef<TemplateArgument> PResolved = TP->template_arguments();
589
590 QualType UA = A;
591 // Treat an injected-class-name as its underlying template-id.
592 if (const auto *Injected = A->getAs<InjectedClassNameType>())
593 UA = Injected->getInjectedSpecializationType();
594
595 // Check whether the template argument is a dependent template-id.
596 // FIXME: Should not lose sugar here.
597 if (const auto *SA =
598 dyn_cast<TemplateSpecializationType>(UA.getCanonicalType())) {
599 TemplateName TNA = SA->getTemplateName();
600
601 // If the argument is an alias template, there is nothing to deduce.
602 if (const auto *TD = TNA.getAsTemplateDecl(); TD && TD->isTypeAlias())
603 return TemplateDeductionResult::Success;
604
605 // Perform template argument deduction for the template name.
606 if (auto Result =
607 DeduceTemplateArguments(S, TemplateParams, TNP, TNA, Info, Deduced);
608 Result != TemplateDeductionResult::Success)
609 return Result;
610 // Perform template argument deduction on each template
611 // argument. Ignore any missing/extra arguments, since they could be
612 // filled in by default arguments.
613 return DeduceTemplateArguments(S, TemplateParams, PResolved,
614 SA->template_arguments(), Info, Deduced,
615 /*NumberOfArgumentsMustMatch=*/false);
616 }
617
618 // If the argument type is a class template specialization, we
619 // perform template argument deduction using its template
620 // arguments.
621 const auto *RA = UA->getAs<RecordType>();
622 const auto *SA =
623 RA ? dyn_cast<ClassTemplateSpecializationDecl>(RA->getDecl()) : nullptr;
624 if (!SA) {
626 Info.SecondArg = TemplateArgument(A);
627 return TemplateDeductionResult::NonDeducedMismatch;
628 }
629
630 // Perform template argument deduction for the template name.
631 if (auto Result = DeduceTemplateArguments(
632 S, TemplateParams, TP->getTemplateName(),
633 TemplateName(SA->getSpecializedTemplate()), Info, Deduced);
634 Result != TemplateDeductionResult::Success)
635 return Result;
636
637 // Perform template argument deduction for the template arguments.
638 return DeduceTemplateArguments(S, TemplateParams, PResolved,
639 SA->getTemplateArgs().asArray(), Info, Deduced,
640 /*NumberOfArgumentsMustMatch=*/true);
641}
642
644 assert(T->isCanonicalUnqualified());
645
646 switch (T->getTypeClass()) {
647 case Type::TypeOfExpr:
648 case Type::TypeOf:
649 case Type::DependentName:
650 case Type::Decltype:
651 case Type::PackIndexing:
652 case Type::UnresolvedUsing:
653 case Type::TemplateTypeParm:
654 case Type::Auto:
655 return true;
656
657 case Type::ConstantArray:
658 case Type::IncompleteArray:
659 case Type::VariableArray:
660 case Type::DependentSizedArray:
662 cast<ArrayType>(T)->getElementType().getTypePtr());
663
664 default:
665 return false;
666 }
667}
668
669/// Determines whether the given type is an opaque type that
670/// might be more qualified when instantiated.
674}
675
676/// Helper function to build a TemplateParameter when we don't
677/// know its type statically.
679 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
680 return TemplateParameter(TTP);
681 if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
682 return TemplateParameter(NTTP);
683
684 return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
685}
686
687/// A pack that we're currently deducing.
689 // The index of the pack.
690 unsigned Index;
691
692 // The old value of the pack before we started deducing it.
694
695 // A deferred value of this pack from an inner deduction, that couldn't be
696 // deduced because this deduction hadn't happened yet.
698
699 // The new value of the pack.
701
702 // The outer deduction for this pack, if any.
703 DeducedPack *Outer = nullptr;
704
705 DeducedPack(unsigned Index) : Index(Index) {}
706};
707
708namespace {
709
710/// A scope in which we're performing pack deduction.
711class PackDeductionScope {
712public:
713 /// Prepare to deduce the packs named within Pattern.
714 PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
717 bool DeducePackIfNotAlreadyDeduced = false)
718 : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info),
719 DeducePackIfNotAlreadyDeduced(DeducePackIfNotAlreadyDeduced){
720 unsigned NumNamedPacks = addPacks(Pattern);
721 finishConstruction(NumNamedPacks);
722 }
723
724 /// Prepare to directly deduce arguments of the parameter with index \p Index.
725 PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
727 TemplateDeductionInfo &Info, unsigned Index)
728 : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
729 addPack(Index);
730 finishConstruction(1);
731 }
732
733private:
734 void addPack(unsigned Index) {
735 // Save the deduced template argument for the parameter pack expanded
736 // by this pack expansion, then clear out the deduction.
737 DeducedFromEarlierParameter = !Deduced[Index].isNull();
738 DeducedPack Pack(Index);
739 Pack.Saved = Deduced[Index];
740 Deduced[Index] = TemplateArgument();
741
742 // FIXME: What if we encounter multiple packs with different numbers of
743 // pre-expanded expansions? (This should already have been diagnosed
744 // during substitution.)
745 if (std::optional<unsigned> ExpandedPackExpansions =
746 getExpandedPackSize(TemplateParams->getParam(Index)))
747 FixedNumExpansions = ExpandedPackExpansions;
748
749 Packs.push_back(Pack);
750 }
751
752 unsigned addPacks(TemplateArgument Pattern) {
753 // Compute the set of template parameter indices that correspond to
754 // parameter packs expanded by the pack expansion.
755 llvm::SmallBitVector SawIndices(TemplateParams->size());
757
758 auto AddPack = [&](unsigned Index) {
759 if (SawIndices[Index])
760 return;
761 SawIndices[Index] = true;
762 addPack(Index);
763
764 // Deducing a parameter pack that is a pack expansion also constrains the
765 // packs appearing in that parameter to have the same deduced arity. Also,
766 // in C++17 onwards, deducing a non-type template parameter deduces its
767 // type, so we need to collect the pending deduced values for those packs.
768 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(
769 TemplateParams->getParam(Index))) {
770 if (!NTTP->isExpandedParameterPack())
771 if (auto *Expansion = dyn_cast<PackExpansionType>(NTTP->getType()))
772 ExtraDeductions.push_back(Expansion->getPattern());
773 }
774 // FIXME: Also collect the unexpanded packs in any type and template
775 // parameter packs that are pack expansions.
776 };
777
778 auto Collect = [&](TemplateArgument Pattern) {
780 S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
781 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
782 unsigned Depth, Index;
783 std::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
784 if (Depth == Info.getDeducedDepth())
785 AddPack(Index);
786 }
787 };
788
789 // Look for unexpanded packs in the pattern.
790 Collect(Pattern);
791 assert(!Packs.empty() && "Pack expansion without unexpanded packs?");
792
793 unsigned NumNamedPacks = Packs.size();
794
795 // Also look for unexpanded packs that are indirectly deduced by deducing
796 // the sizes of the packs in this pattern.
797 while (!ExtraDeductions.empty())
798 Collect(ExtraDeductions.pop_back_val());
799
800 return NumNamedPacks;
801 }
802
803 void finishConstruction(unsigned NumNamedPacks) {
804 // Dig out the partially-substituted pack, if there is one.
805 const TemplateArgument *PartialPackArgs = nullptr;
806 unsigned NumPartialPackArgs = 0;
807 std::pair<unsigned, unsigned> PartialPackDepthIndex(-1u, -1u);
808 if (auto *Scope = S.CurrentInstantiationScope)
809 if (auto *Partial = Scope->getPartiallySubstitutedPack(
810 &PartialPackArgs, &NumPartialPackArgs))
811 PartialPackDepthIndex = getDepthAndIndex(Partial);
812
813 // This pack expansion will have been partially or fully expanded if
814 // it only names explicitly-specified parameter packs (including the
815 // partially-substituted one, if any).
816 bool IsExpanded = true;
817 for (unsigned I = 0; I != NumNamedPacks; ++I) {
818 if (Packs[I].Index >= Info.getNumExplicitArgs()) {
819 IsExpanded = false;
820 IsPartiallyExpanded = false;
821 break;
822 }
823 if (PartialPackDepthIndex ==
824 std::make_pair(Info.getDeducedDepth(), Packs[I].Index)) {
825 IsPartiallyExpanded = true;
826 }
827 }
828
829 // Skip over the pack elements that were expanded into separate arguments.
830 // If we partially expanded, this is the number of partial arguments.
831 if (IsPartiallyExpanded)
832 PackElements += NumPartialPackArgs;
833 else if (IsExpanded)
834 PackElements += *FixedNumExpansions;
835
836 for (auto &Pack : Packs) {
837 if (Info.PendingDeducedPacks.size() > Pack.Index)
838 Pack.Outer = Info.PendingDeducedPacks[Pack.Index];
839 else
840 Info.PendingDeducedPacks.resize(Pack.Index + 1);
841 Info.PendingDeducedPacks[Pack.Index] = &Pack;
842
843 if (PartialPackDepthIndex ==
844 std::make_pair(Info.getDeducedDepth(), Pack.Index)) {
845 Pack.New.append(PartialPackArgs, PartialPackArgs + NumPartialPackArgs);
846 // We pre-populate the deduced value of the partially-substituted
847 // pack with the specified value. This is not entirely correct: the
848 // value is supposed to have been substituted, not deduced, but the
849 // cases where this is observable require an exact type match anyway.
850 //
851 // FIXME: If we could represent a "depth i, index j, pack elem k"
852 // parameter, we could substitute the partially-substituted pack
853 // everywhere and avoid this.
854 if (!IsPartiallyExpanded)
855 Deduced[Pack.Index] = Pack.New[PackElements];
856 }
857 }
858 }
859
860public:
861 ~PackDeductionScope() {
862 for (auto &Pack : Packs)
863 Info.PendingDeducedPacks[Pack.Index] = Pack.Outer;
864 }
865
866 // Return the size of the saved packs if all of them has the same size.
867 std::optional<unsigned> getSavedPackSizeIfAllEqual() const {
868 unsigned PackSize = Packs[0].Saved.pack_size();
869
870 if (std::all_of(Packs.begin() + 1, Packs.end(), [&PackSize](const auto &P) {
871 return P.Saved.pack_size() == PackSize;
872 }))
873 return PackSize;
874 return {};
875 }
876
877 /// Determine whether this pack has already been deduced from a previous
878 /// argument.
879 bool isDeducedFromEarlierParameter() const {
880 return DeducedFromEarlierParameter;
881 }
882
883 /// Determine whether this pack has already been partially expanded into a
884 /// sequence of (prior) function parameters / template arguments.
885 bool isPartiallyExpanded() { return IsPartiallyExpanded; }
886
887 /// Determine whether this pack expansion scope has a known, fixed arity.
888 /// This happens if it involves a pack from an outer template that has
889 /// (notionally) already been expanded.
890 bool hasFixedArity() { return FixedNumExpansions.has_value(); }
891
892 /// Determine whether the next element of the argument is still part of this
893 /// pack. This is the case unless the pack is already expanded to a fixed
894 /// length.
895 bool hasNextElement() {
896 return !FixedNumExpansions || *FixedNumExpansions > PackElements;
897 }
898
899 /// Move to deducing the next element in each pack that is being deduced.
900 void nextPackElement() {
901 // Capture the deduced template arguments for each parameter pack expanded
902 // by this pack expansion, add them to the list of arguments we've deduced
903 // for that pack, then clear out the deduced argument.
904 for (auto &Pack : Packs) {
905 DeducedTemplateArgument &DeducedArg = Deduced[Pack.Index];
906 if (!Pack.New.empty() || !DeducedArg.isNull()) {
907 while (Pack.New.size() < PackElements)
908 Pack.New.push_back(DeducedTemplateArgument());
909 if (Pack.New.size() == PackElements)
910 Pack.New.push_back(DeducedArg);
911 else
912 Pack.New[PackElements] = DeducedArg;
913 DeducedArg = Pack.New.size() > PackElements + 1
914 ? Pack.New[PackElements + 1]
916 }
917 }
918 ++PackElements;
919 }
920
921 /// Finish template argument deduction for a set of argument packs,
922 /// producing the argument packs and checking for consistency with prior
923 /// deductions.
924 TemplateDeductionResult finish() {
925 // Build argument packs for each of the parameter packs expanded by this
926 // pack expansion.
927 for (auto &Pack : Packs) {
928 // Put back the old value for this pack.
929 Deduced[Pack.Index] = Pack.Saved;
930
931 // Always make sure the size of this pack is correct, even if we didn't
932 // deduce any values for it.
933 //
934 // FIXME: This isn't required by the normative wording, but substitution
935 // and post-substitution checking will always fail if the arity of any
936 // pack is not equal to the number of elements we processed. (Either that
937 // or something else has gone *very* wrong.) We're permitted to skip any
938 // hard errors from those follow-on steps by the intent (but not the
939 // wording) of C++ [temp.inst]p8:
940 //
941 // If the function selected by overload resolution can be determined
942 // without instantiating a class template definition, it is unspecified
943 // whether that instantiation actually takes place
944 Pack.New.resize(PackElements);
945
946 // Build or find a new value for this pack.
948 if (Pack.New.empty()) {
949 // If we deduced an empty argument pack, create it now.
951 } else {
952 TemplateArgument *ArgumentPack =
953 new (S.Context) TemplateArgument[Pack.New.size()];
954 std::copy(Pack.New.begin(), Pack.New.end(), ArgumentPack);
955 NewPack = DeducedTemplateArgument(
956 TemplateArgument(llvm::ArrayRef(ArgumentPack, Pack.New.size())),
957 // FIXME: This is wrong, it's possible that some pack elements are
958 // deduced from an array bound and others are not:
959 // template<typename ...T, T ...V> void g(const T (&...p)[V]);
960 // g({1, 2, 3}, {{}, {}});
961 // ... should deduce T = {int, size_t (from array bound)}.
962 Pack.New[0].wasDeducedFromArrayBound());
963 }
964
965 // Pick where we're going to put the merged pack.
967 if (Pack.Outer) {
968 if (Pack.Outer->DeferredDeduction.isNull()) {
969 // Defer checking this pack until we have a complete pack to compare
970 // it against.
971 Pack.Outer->DeferredDeduction = NewPack;
972 continue;
973 }
974 Loc = &Pack.Outer->DeferredDeduction;
975 } else {
976 Loc = &Deduced[Pack.Index];
977 }
978
979 // Check the new pack matches any previous value.
980 DeducedTemplateArgument OldPack = *Loc;
982 S.Context, OldPack, NewPack, DeducePackIfNotAlreadyDeduced);
983
984 Info.AggregateDeductionCandidateHasMismatchedArity =
985 OldPack.getKind() == TemplateArgument::Pack &&
986 NewPack.getKind() == TemplateArgument::Pack &&
987 OldPack.pack_size() != NewPack.pack_size() && !Result.isNull();
988
989 // If we deferred a deduction of this pack, check that one now too.
990 if (!Result.isNull() && !Pack.DeferredDeduction.isNull()) {
991 OldPack = Result;
992 NewPack = Pack.DeferredDeduction;
993 Result = checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
994 }
995
996 NamedDecl *Param = TemplateParams->getParam(Pack.Index);
997 if (Result.isNull()) {
998 Info.Param = makeTemplateParameter(Param);
999 Info.FirstArg = OldPack;
1000 Info.SecondArg = NewPack;
1001 return TemplateDeductionResult::Inconsistent;
1002 }
1003
1004 // If we have a pre-expanded pack and we didn't deduce enough elements
1005 // for it, fail deduction.
1006 if (std::optional<unsigned> Expansions = getExpandedPackSize(Param)) {
1007 if (*Expansions != PackElements) {
1008 Info.Param = makeTemplateParameter(Param);
1009 Info.FirstArg = Result;
1010 return TemplateDeductionResult::IncompletePack;
1011 }
1012 }
1013
1014 *Loc = Result;
1015 }
1016
1017 return TemplateDeductionResult::Success;
1018 }
1019
1020private:
1021 Sema &S;
1022 TemplateParameterList *TemplateParams;
1025 unsigned PackElements = 0;
1026 bool IsPartiallyExpanded = false;
1027 bool DeducePackIfNotAlreadyDeduced = false;
1028 bool DeducedFromEarlierParameter = false;
1029 /// The number of expansions, if we have a fully-expanded pack in this scope.
1030 std::optional<unsigned> FixedNumExpansions;
1031
1033};
1034
1035} // namespace
1036
1037/// Deduce the template arguments by comparing the list of parameter
1038/// types to the list of argument types, as in the parameter-type-lists of
1039/// function types (C++ [temp.deduct.type]p10).
1040///
1041/// \param S The semantic analysis object within which we are deducing
1042///
1043/// \param TemplateParams The template parameters that we are deducing
1044///
1045/// \param Params The list of parameter types
1046///
1047/// \param NumParams The number of types in \c Params
1048///
1049/// \param Args The list of argument types
1050///
1051/// \param NumArgs The number of types in \c Args
1052///
1053/// \param Info information about the template argument deduction itself
1054///
1055/// \param Deduced the deduced template arguments
1056///
1057/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
1058/// how template argument deduction is performed.
1059///
1060/// \param PartialOrdering If true, we are performing template argument
1061/// deduction for during partial ordering for a call
1062/// (C++0x [temp.deduct.partial]).
1063///
1064/// \returns the result of template argument deduction so far. Note that a
1065/// "success" result means that template argument deduction has not yet failed,
1066/// but it may still fail, later, for other reasons.
1069 const QualType *Params, unsigned NumParams,
1070 const QualType *Args, unsigned NumArgs,
1073 unsigned TDF, bool PartialOrdering = false) {
1074 // C++0x [temp.deduct.type]p10:
1075 // Similarly, if P has a form that contains (T), then each parameter type
1076 // Pi of the respective parameter-type- list of P is compared with the
1077 // corresponding parameter type Ai of the corresponding parameter-type-list
1078 // of A. [...]
1079 unsigned ArgIdx = 0, ParamIdx = 0;
1080 for (; ParamIdx != NumParams; ++ParamIdx) {
1081 // Check argument types.
1082 const PackExpansionType *Expansion
1083 = dyn_cast<PackExpansionType>(Params[ParamIdx]);
1084 if (!Expansion) {
1085 // Simple case: compare the parameter and argument types at this point.
1086
1087 // Make sure we have an argument.
1088 if (ArgIdx >= NumArgs)
1089 return TemplateDeductionResult::MiscellaneousDeductionFailure;
1090
1091 if (isa<PackExpansionType>(Args[ArgIdx])) {
1092 // C++0x [temp.deduct.type]p22:
1093 // If the original function parameter associated with A is a function
1094 // parameter pack and the function parameter associated with P is not
1095 // a function parameter pack, then template argument deduction fails.
1096 return TemplateDeductionResult::MiscellaneousDeductionFailure;
1097 }
1098
1100 S, TemplateParams, Params[ParamIdx].getUnqualifiedType(),
1101 Args[ArgIdx].getUnqualifiedType(), Info, Deduced, TDF,
1103 /*DeducedFromArrayBound=*/false);
1104 Result != TemplateDeductionResult::Success)
1105 return Result;
1106
1107 ++ArgIdx;
1108 continue;
1109 }
1110
1111 // C++0x [temp.deduct.type]p10:
1112 // If the parameter-declaration corresponding to Pi is a function
1113 // parameter pack, then the type of its declarator- id is compared with
1114 // each remaining parameter type in the parameter-type-list of A. Each
1115 // comparison deduces template arguments for subsequent positions in the
1116 // template parameter packs expanded by the function parameter pack.
1117
1118 QualType Pattern = Expansion->getPattern();
1119 PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
1120
1121 // A pack scope with fixed arity is not really a pack any more, so is not
1122 // a non-deduced context.
1123 if (ParamIdx + 1 == NumParams || PackScope.hasFixedArity()) {
1124 for (; ArgIdx < NumArgs && PackScope.hasNextElement(); ++ArgIdx) {
1125 // Deduce template arguments from the pattern.
1127 S, TemplateParams, Pattern.getUnqualifiedType(),
1128 Args[ArgIdx].getUnqualifiedType(), Info, Deduced, TDF,
1129 PartialOrdering, /*DeducedFromArrayBound=*/false);
1130 Result != TemplateDeductionResult::Success)
1131 return Result;
1132
1133 PackScope.nextPackElement();
1134 }
1135 } else {
1136 // C++0x [temp.deduct.type]p5:
1137 // The non-deduced contexts are:
1138 // - A function parameter pack that does not occur at the end of the
1139 // parameter-declaration-clause.
1140 //
1141 // FIXME: There is no wording to say what we should do in this case. We
1142 // choose to resolve this by applying the same rule that is applied for a
1143 // function call: that is, deduce all contained packs to their
1144 // explicitly-specified values (or to <> if there is no such value).
1145 //
1146 // This is seemingly-arbitrarily different from the case of a template-id
1147 // with a non-trailing pack-expansion in its arguments, which renders the
1148 // entire template-argument-list a non-deduced context.
1149
1150 // If the parameter type contains an explicitly-specified pack that we
1151 // could not expand, skip the number of parameters notionally created
1152 // by the expansion.
1153 std::optional<unsigned> NumExpansions = Expansion->getNumExpansions();
1154 if (NumExpansions && !PackScope.isPartiallyExpanded()) {
1155 for (unsigned I = 0; I != *NumExpansions && ArgIdx < NumArgs;
1156 ++I, ++ArgIdx)
1157 PackScope.nextPackElement();
1158 }
1159 }
1160
1161 // Build argument packs for each of the parameter packs expanded by this
1162 // pack expansion.
1163 if (auto Result = PackScope.finish();
1164 Result != TemplateDeductionResult::Success)
1165 return Result;
1166 }
1167
1168 // DR692, DR1395
1169 // C++0x [temp.deduct.type]p10:
1170 // If the parameter-declaration corresponding to P_i ...
1171 // During partial ordering, if Ai was originally a function parameter pack:
1172 // - if P does not contain a function parameter type corresponding to Ai then
1173 // Ai is ignored;
1174 if (PartialOrdering && ArgIdx + 1 == NumArgs &&
1175 isa<PackExpansionType>(Args[ArgIdx]))
1176 return TemplateDeductionResult::Success;
1177
1178 // Make sure we don't have any extra arguments.
1179 if (ArgIdx < NumArgs)
1180 return TemplateDeductionResult::MiscellaneousDeductionFailure;
1181
1182 return TemplateDeductionResult::Success;
1183}
1184
1185/// Determine whether the parameter has qualifiers that the argument
1186/// lacks. Put another way, determine whether there is no way to add
1187/// a deduced set of qualifiers to the ParamType that would result in
1188/// its qualifiers matching those of the ArgType.
1190 QualType ArgType) {
1191 Qualifiers ParamQs = ParamType.getQualifiers();
1192 Qualifiers ArgQs = ArgType.getQualifiers();
1193
1194 if (ParamQs == ArgQs)
1195 return false;
1196
1197 // Mismatched (but not missing) Objective-C GC attributes.
1198 if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() &&
1199 ParamQs.hasObjCGCAttr())
1200 return true;
1201
1202 // Mismatched (but not missing) address spaces.
1203 if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() &&
1204 ParamQs.hasAddressSpace())
1205 return true;
1206
1207 // Mismatched (but not missing) Objective-C lifetime qualifiers.
1208 if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() &&
1209 ParamQs.hasObjCLifetime())
1210 return true;
1211
1212 // CVR qualifiers inconsistent or a superset.
1213 return (ParamQs.getCVRQualifiers() & ~ArgQs.getCVRQualifiers()) != 0;
1214}
1215
1216/// Compare types for equality with respect to possibly compatible
1217/// function types (noreturn adjustment, implicit calling conventions). If any
1218/// of parameter and argument is not a function, just perform type comparison.
1219///
1220/// \param P the template parameter type.
1221///
1222/// \param A the argument type.
1224 const FunctionType *PF = P->getAs<FunctionType>(),
1225 *AF = A->getAs<FunctionType>();
1226
1227 // Just compare if not functions.
1228 if (!PF || !AF)
1229 return Context.hasSameType(P, A);
1230
1231 // Noreturn and noexcept adjustment.
1232 QualType AdjustedParam;
1233 if (IsFunctionConversion(P, A, AdjustedParam))
1234 return Context.hasSameType(AdjustedParam, A);
1235
1236 // FIXME: Compatible calling conventions.
1237
1238 return Context.hasSameType(P, A);
1239}
1240
1241/// Get the index of the first template parameter that was originally from the
1242/// innermost template-parameter-list. This is 0 except when we concatenate
1243/// the template parameter lists of a class template and a constructor template
1244/// when forming an implicit deduction guide.
1246 auto *Guide = dyn_cast<CXXDeductionGuideDecl>(FTD->getTemplatedDecl());
1247 if (!Guide || !Guide->isImplicit())
1248 return 0;
1249 return Guide->getDeducedTemplate()->getTemplateParameters()->size();
1250}
1251
1252/// Determine whether a type denotes a forwarding reference.
1253static bool isForwardingReference(QualType Param, unsigned FirstInnerIndex) {
1254 // C++1z [temp.deduct.call]p3:
1255 // A forwarding reference is an rvalue reference to a cv-unqualified
1256 // template parameter that does not represent a template parameter of a
1257 // class template.
1258 if (auto *ParamRef = Param->getAs<RValueReferenceType>()) {
1259 if (ParamRef->getPointeeType().getQualifiers())
1260 return false;
1261 auto *TypeParm = ParamRef->getPointeeType()->getAs<TemplateTypeParmType>();
1262 return TypeParm && TypeParm->getIndex() >= FirstInnerIndex;
1263 }
1264 return false;
1265}
1266
1268 return cast<CXXRecordDecl>(
1270}
1271
1272/// Attempt to deduce the template arguments by checking the base types
1273/// according to (C++20 [temp.deduct.call] p4b3.
1274///
1275/// \param S the semantic analysis object within which we are deducing.
1276///
1277/// \param RD the top level record object we are deducing against.
1278///
1279/// \param TemplateParams the template parameters that we are deducing.
1280///
1281/// \param P the template specialization parameter type.
1282///
1283/// \param Info information about the template argument deduction itself.
1284///
1285/// \param Deduced the deduced template arguments.
1286///
1287/// \returns the result of template argument deduction with the bases. "invalid"
1288/// means no matches, "success" found a single item, and the
1289/// "MiscellaneousDeductionFailure" result happens when the match is ambiguous.
1292 TemplateParameterList *TemplateParams, QualType P,
1295 // C++14 [temp.deduct.call] p4b3:
1296 // If P is a class and P has the form simple-template-id, then the
1297 // transformed A can be a derived class of the deduced A. Likewise if
1298 // P is a pointer to a class of the form simple-template-id, the
1299 // transformed A can be a pointer to a derived class pointed to by the
1300 // deduced A. However, if there is a class C that is a (direct or
1301 // indirect) base class of D and derived (directly or indirectly) from a
1302 // class B and that would be a valid deduced A, the deduced A cannot be
1303 // B or pointer to B, respectively.
1304 //
1305 // These alternatives are considered only if type deduction would
1306 // otherwise fail. If they yield more than one possible deduced A, the
1307 // type deduction fails.
1308
1309 // Use a breadth-first search through the bases to collect the set of
1310 // successful matches. Visited contains the set of nodes we have already
1311 // visited, while ToVisit is our stack of records that we still need to
1312 // visit. Matches contains a list of matches that have yet to be
1313 // disqualified.
1316 // We iterate over this later, so we have to use MapVector to ensure
1317 // determinism.
1318 llvm::MapVector<const CXXRecordDecl *,
1320 Matches;
1321
1322 auto AddBases = [&Visited, &ToVisit](const CXXRecordDecl *RD) {
1323 for (const auto &Base : RD->bases()) {
1324 QualType T = Base.getType();
1325 assert(T->isRecordType() && "Base class that isn't a record?");
1326 if (Visited.insert(::getCanonicalRD(T)).second)
1327 ToVisit.push_back(T);
1328 }
1329 };
1330
1331 // Set up the loop by adding all the bases.
1332 AddBases(RD);
1333
1334 // Search each path of bases until we either run into a successful match
1335 // (where all bases of it are invalid), or we run out of bases.
1336 while (!ToVisit.empty()) {
1337 QualType NextT = ToVisit.pop_back_val();
1338
1339 SmallVector<DeducedTemplateArgument, 8> DeducedCopy(Deduced.begin(),
1340 Deduced.end());
1343 S, TemplateParams, P, NextT, BaseInfo, DeducedCopy);
1344
1345 // If this was a successful deduction, add it to the list of matches,
1346 // otherwise we need to continue searching its bases.
1347 const CXXRecordDecl *RD = ::getCanonicalRD(NextT);
1349 Matches.insert({RD, DeducedCopy});
1350 else
1351 AddBases(RD);
1352 }
1353
1354 // At this point, 'Matches' contains a list of seemingly valid bases, however
1355 // in the event that we have more than 1 match, it is possible that the base
1356 // of one of the matches might be disqualified for being a base of another
1357 // valid match. We can count on cyclical instantiations being invalid to
1358 // simplify the disqualifications. That is, if A & B are both matches, and B
1359 // inherits from A (disqualifying A), we know that A cannot inherit from B.
1360 if (Matches.size() > 1) {
1361 Visited.clear();
1362 for (const auto &Match : Matches)
1363 AddBases(Match.first);
1364
1365 // We can give up once we have a single item (or have run out of things to
1366 // search) since cyclical inheritance isn't valid.
1367 while (Matches.size() > 1 && !ToVisit.empty()) {
1368 const CXXRecordDecl *RD = ::getCanonicalRD(ToVisit.pop_back_val());
1369 Matches.erase(RD);
1370
1371 // Always add all bases, since the inheritance tree can contain
1372 // disqualifications for multiple matches.
1373 AddBases(RD);
1374 }
1375 }
1376
1377 if (Matches.empty())
1379 if (Matches.size() > 1)
1381
1382 std::swap(Matches.front().second, Deduced);
1384}
1385
1386/// Deduce the template arguments by comparing the parameter type and
1387/// the argument type (C++ [temp.deduct.type]).
1388///
1389/// \param S the semantic analysis object within which we are deducing
1390///
1391/// \param TemplateParams the template parameters that we are deducing
1392///
1393/// \param P the parameter type
1394///
1395/// \param A the argument type
1396///
1397/// \param Info information about the template argument deduction itself
1398///
1399/// \param Deduced the deduced template arguments
1400///
1401/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
1402/// how template argument deduction is performed.
1403///
1404/// \param PartialOrdering Whether we're performing template argument deduction
1405/// in the context of partial ordering (C++0x [temp.deduct.partial]).
1406///
1407/// \returns the result of template argument deduction so far. Note that a
1408/// "success" result means that template argument deduction has not yet failed,
1409/// but it may still fail, later, for other reasons.
1411 Sema &S, TemplateParameterList *TemplateParams, QualType P, QualType A,
1413 SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF,
1414 bool PartialOrdering, bool DeducedFromArrayBound) {
1415
1416 // If the argument type is a pack expansion, look at its pattern.
1417 // This isn't explicitly called out
1418 if (const auto *AExp = dyn_cast<PackExpansionType>(A))
1419 A = AExp->getPattern();
1420 assert(!isa<PackExpansionType>(A.getCanonicalType()));
1421
1422 if (PartialOrdering) {
1423 // C++11 [temp.deduct.partial]p5:
1424 // Before the partial ordering is done, certain transformations are
1425 // performed on the types used for partial ordering:
1426 // - If P is a reference type, P is replaced by the type referred to.
1427 const ReferenceType *PRef = P->getAs<ReferenceType>();
1428 if (PRef)
1429 P = PRef->getPointeeType();
1430
1431 // - If A is a reference type, A is replaced by the type referred to.
1432 const ReferenceType *ARef = A->getAs<ReferenceType>();
1433 if (ARef)
1434 A = A->getPointeeType();
1435
1436 if (PRef && ARef && S.Context.hasSameUnqualifiedType(P, A)) {
1437 // C++11 [temp.deduct.partial]p9:
1438 // If, for a given type, deduction succeeds in both directions (i.e.,
1439 // the types are identical after the transformations above) and both
1440 // P and A were reference types [...]:
1441 // - if [one type] was an lvalue reference and [the other type] was
1442 // not, [the other type] is not considered to be at least as
1443 // specialized as [the first type]
1444 // - if [one type] is more cv-qualified than [the other type],
1445 // [the other type] is not considered to be at least as specialized
1446 // as [the first type]
1447 // Objective-C ARC adds:
1448 // - [one type] has non-trivial lifetime, [the other type] has
1449 // __unsafe_unretained lifetime, and the types are otherwise
1450 // identical
1451 //
1452 // A is "considered to be at least as specialized" as P iff deduction
1453 // succeeds, so we model this as a deduction failure. Note that
1454 // [the first type] is P and [the other type] is A here; the standard
1455 // gets this backwards.
1456 Qualifiers PQuals = P.getQualifiers(), AQuals = A.getQualifiers();
1457 if ((PRef->isLValueReferenceType() && !ARef->isLValueReferenceType()) ||
1458 PQuals.isStrictSupersetOf(AQuals) ||
1459 (PQuals.hasNonTrivialObjCLifetime() &&
1460 AQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone &&
1461 PQuals.withoutObjCLifetime() == AQuals.withoutObjCLifetime())) {
1462 Info.FirstArg = TemplateArgument(P);
1463 Info.SecondArg = TemplateArgument(A);
1465 }
1466 }
1467 Qualifiers DiscardedQuals;
1468 // C++11 [temp.deduct.partial]p7:
1469 // Remove any top-level cv-qualifiers:
1470 // - If P is a cv-qualified type, P is replaced by the cv-unqualified
1471 // version of P.
1472 P = S.Context.getUnqualifiedArrayType(P, DiscardedQuals);
1473 // - If A is a cv-qualified type, A is replaced by the cv-unqualified
1474 // version of A.
1475 A = S.Context.getUnqualifiedArrayType(A, DiscardedQuals);
1476 } else {
1477 // C++0x [temp.deduct.call]p4 bullet 1:
1478 // - If the original P is a reference type, the deduced A (i.e., the type
1479 // referred to by the reference) can be more cv-qualified than the
1480 // transformed A.
1481 if (TDF & TDF_ParamWithReferenceType) {
1482 Qualifiers Quals;
1483 QualType UnqualP = S.Context.getUnqualifiedArrayType(P, Quals);
1485 P = S.Context.getQualifiedType(UnqualP, Quals);
1486 }
1487
1488 if ((TDF & TDF_TopLevelParameterTypeList) && !P->isFunctionType()) {
1489 // C++0x [temp.deduct.type]p10:
1490 // If P and A are function types that originated from deduction when
1491 // taking the address of a function template (14.8.2.2) or when deducing
1492 // template arguments from a function declaration (14.8.2.6) and Pi and
1493 // Ai are parameters of the top-level parameter-type-list of P and A,
1494 // respectively, Pi is adjusted if it is a forwarding reference and Ai
1495 // is an lvalue reference, in
1496 // which case the type of Pi is changed to be the template parameter
1497 // type (i.e., T&& is changed to simply T). [ Note: As a result, when
1498 // Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
1499 // deduced as X&. - end note ]
1500 TDF &= ~TDF_TopLevelParameterTypeList;
1501 if (isForwardingReference(P, /*FirstInnerIndex=*/0) &&
1503 P = P->getPointeeType();
1504 }
1505 }
1506
1507 // C++ [temp.deduct.type]p9:
1508 // A template type argument T, a template template argument TT or a
1509 // template non-type argument i can be deduced if P and A have one of
1510 // the following forms:
1511 //
1512 // T
1513 // cv-list T
1514 if (const auto *TTP = P->getAs<TemplateTypeParmType>()) {
1515 // Just skip any attempts to deduce from a placeholder type or a parameter
1516 // at a different depth.
1517 if (A->isPlaceholderType() || Info.getDeducedDepth() != TTP->getDepth())
1519
1520 unsigned Index = TTP->getIndex();
1521
1522 // If the argument type is an array type, move the qualifiers up to the
1523 // top level, so they can be matched with the qualifiers on the parameter.
1524 if (A->isArrayType()) {
1525 Qualifiers Quals;
1526 A = S.Context.getUnqualifiedArrayType(A, Quals);
1527 if (Quals)
1528 A = S.Context.getQualifiedType(A, Quals);
1529 }
1530
1531 // The argument type can not be less qualified than the parameter
1532 // type.
1533 if (!(TDF & TDF_IgnoreQualifiers) &&
1535 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1536 Info.FirstArg = TemplateArgument(P);
1537 Info.SecondArg = TemplateArgument(A);
1539 }
1540
1541 // Do not match a function type with a cv-qualified type.
1542 // http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1584
1543 if (A->isFunctionType() && P.hasQualifiers())
1545
1546 assert(TTP->getDepth() == Info.getDeducedDepth() &&
1547 "saw template type parameter with wrong depth");
1548 assert(A->getCanonicalTypeInternal() != S.Context.OverloadTy &&
1549 "Unresolved overloaded function");
1551
1552 // Remove any qualifiers on the parameter from the deduced type.
1553 // We checked the qualifiers for consistency above.
1554 Qualifiers DeducedQs = DeducedType.getQualifiers();
1555 Qualifiers ParamQs = P.getQualifiers();
1556 DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers());
1557 if (ParamQs.hasObjCGCAttr())
1558 DeducedQs.removeObjCGCAttr();
1559 if (ParamQs.hasAddressSpace())
1560 DeducedQs.removeAddressSpace();
1561 if (ParamQs.hasObjCLifetime())
1562 DeducedQs.removeObjCLifetime();
1563
1564 // Objective-C ARC:
1565 // If template deduction would produce a lifetime qualifier on a type
1566 // that is not a lifetime type, template argument deduction fails.
1567 if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() &&
1569 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1570 Info.FirstArg = TemplateArgument(P);
1571 Info.SecondArg = TemplateArgument(A);
1573 }
1574
1575 // Objective-C ARC:
1576 // If template deduction would produce an argument type with lifetime type
1577 // but no lifetime qualifier, the __strong lifetime qualifier is inferred.
1578 if (S.getLangOpts().ObjCAutoRefCount && DeducedType->isObjCLifetimeType() &&
1579 !DeducedQs.hasObjCLifetime())
1581
1582 DeducedType =
1583 S.Context.getQualifiedType(DeducedType.getUnqualifiedType(), DeducedQs);
1584
1585 DeducedTemplateArgument NewDeduced(DeducedType, DeducedFromArrayBound);
1587 checkDeducedTemplateArguments(S.Context, Deduced[Index], NewDeduced);
1588 if (Result.isNull()) {
1589 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1590 Info.FirstArg = Deduced[Index];
1591 Info.SecondArg = NewDeduced;
1593 }
1594
1595 Deduced[Index] = Result;
1597 }
1598
1599 // Set up the template argument deduction information for a failure.
1600 Info.FirstArg = TemplateArgument(P);
1601 Info.SecondArg = TemplateArgument(A);
1602
1603 // If the parameter is an already-substituted template parameter
1604 // pack, do nothing: we don't know which of its arguments to look
1605 // at, so we have to wait until all of the parameter packs in this
1606 // expansion have arguments.
1607 if (P->getAs<SubstTemplateTypeParmPackType>())
1609
1610 // Check the cv-qualifiers on the parameter and argument types.
1611 if (!(TDF & TDF_IgnoreQualifiers)) {
1612 if (TDF & TDF_ParamWithReferenceType) {
1615 } else if (TDF & TDF_ArgWithReferenceType) {
1616 // C++ [temp.deduct.conv]p4:
1617 // If the original A is a reference type, A can be more cv-qualified
1618 // than the deduced A
1619 if (!A.getQualifiers().compatiblyIncludes(P.getQualifiers()))
1621
1622 // Strip out all extra qualifiers from the argument to figure out the
1623 // type we're converting to, prior to the qualification conversion.
1624 Qualifiers Quals;
1625 A = S.Context.getUnqualifiedArrayType(A, Quals);
1626 A = S.Context.getQualifiedType(A, P.getQualifiers());
1627 } else if (!IsPossiblyOpaquelyQualifiedType(P)) {
1628 if (P.getCVRQualifiers() != A.getCVRQualifiers())
1630 }
1631 }
1632
1633 // If the parameter type is not dependent, there is nothing to deduce.
1634 if (!P->isDependentType()) {
1635 if (TDF & TDF_SkipNonDependent)
1638 : S.Context.hasSameType(P, A))
1643 if (!(TDF & TDF_IgnoreQualifiers))
1645 // Otherwise, when ignoring qualifiers, the types not having the same
1646 // unqualified type does not mean they do not match, so in this case we
1647 // must keep going and analyze with a non-dependent parameter type.
1648 }
1649
1650 switch (P.getCanonicalType()->getTypeClass()) {
1651 // Non-canonical types cannot appear here.
1652#define NON_CANONICAL_TYPE(Class, Base) \
1653 case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class);
1654#define TYPE(Class, Base)
1655#include "clang/AST/TypeNodes.inc"
1656
1657 case Type::TemplateTypeParm:
1658 case Type::SubstTemplateTypeParmPack:
1659 llvm_unreachable("Type nodes handled above");
1660
1661 case Type::Auto:
1662 // C++23 [temp.deduct.funcaddr]/3:
1663 // A placeholder type in the return type of a function template is a
1664 // non-deduced context.
1665 // There's no corresponding wording for [temp.deduct.decl], but we treat
1666 // it the same to match other compilers.
1667 if (P->isDependentType())
1669 [[fallthrough]];
1670 case Type::Builtin:
1671 case Type::VariableArray:
1672 case Type::Vector:
1673 case Type::FunctionNoProto:
1674 case Type::Record:
1675 case Type::Enum:
1676 case Type::ObjCObject:
1677 case Type::ObjCInterface:
1678 case Type::ObjCObjectPointer:
1679 case Type::BitInt:
1680 return (TDF & TDF_SkipNonDependent) ||
1681 ((TDF & TDF_IgnoreQualifiers)
1683 : S.Context.hasSameType(P, A))
1686
1687 // _Complex T [placeholder extension]
1688 case Type::Complex: {
1689 const auto *CP = P->castAs<ComplexType>(), *CA = A->getAs<ComplexType>();
1690 if (!CA)
1693 S, TemplateParams, CP->getElementType(), CA->getElementType(), Info,
1694 Deduced, TDF);
1695 }
1696
1697 // _Atomic T [extension]
1698 case Type::Atomic: {
1699 const auto *PA = P->castAs<AtomicType>(), *AA = A->getAs<AtomicType>();
1700 if (!AA)
1703 S, TemplateParams, PA->getValueType(), AA->getValueType(), Info,
1704 Deduced, TDF);
1705 }
1706
1707 // T *
1708 case Type::Pointer: {
1709 QualType PointeeType;
1710 if (const auto *PA = A->getAs<PointerType>()) {
1711 PointeeType = PA->getPointeeType();
1712 } else if (const auto *PA = A->getAs<ObjCObjectPointerType>()) {
1713 PointeeType = PA->getPointeeType();
1714 } else {
1716 }
1718 S, TemplateParams, P->castAs<PointerType>()->getPointeeType(),
1719 PointeeType, Info, Deduced,
1721 }
1722
1723 // T &
1724 case Type::LValueReference: {
1725 const auto *RP = P->castAs<LValueReferenceType>(),
1726 *RA = A->getAs<LValueReferenceType>();
1727 if (!RA)
1729
1731 S, TemplateParams, RP->getPointeeType(), RA->getPointeeType(), Info,
1732 Deduced, 0);
1733 }
1734
1735 // T && [C++0x]
1736 case Type::RValueReference: {
1737 const auto *RP = P->castAs<RValueReferenceType>(),
1738 *RA = A->getAs<RValueReferenceType>();
1739 if (!RA)
1741
1743 S, TemplateParams, RP->getPointeeType(), RA->getPointeeType(), Info,
1744 Deduced, 0);
1745 }
1746
1747 // T [] (implied, but not stated explicitly)
1748 case Type::IncompleteArray: {
1749 const auto *IAA = S.Context.getAsIncompleteArrayType(A);
1750 if (!IAA)
1752
1753 const auto *IAP = S.Context.getAsIncompleteArrayType(P);
1754 assert(IAP && "Template parameter not of incomplete array type");
1755
1757 S, TemplateParams, IAP->getElementType(), IAA->getElementType(), Info,
1758 Deduced, TDF & TDF_IgnoreQualifiers);
1759 }
1760
1761 // T [integer-constant]
1762 case Type::ConstantArray: {
1763 const auto *CAA = S.Context.getAsConstantArrayType(A),
1765 assert(CAP);
1766 if (!CAA || CAA->getSize() != CAP->getSize())
1768
1770 S, TemplateParams, CAP->getElementType(), CAA->getElementType(), Info,
1771 Deduced, TDF & TDF_IgnoreQualifiers);
1772 }
1773
1774 // type [i]
1775 case Type::DependentSizedArray: {
1776 const auto *AA = S.Context.getAsArrayType(A);
1777 if (!AA)
1779
1780 // Check the element type of the arrays
1781 const auto *DAP = S.Context.getAsDependentSizedArrayType(P);
1782 assert(DAP);
1784 S, TemplateParams, DAP->getElementType(), AA->getElementType(),
1785 Info, Deduced, TDF & TDF_IgnoreQualifiers);
1787 return Result;
1788
1789 // Determine the array bound is something we can deduce.
1790 const NonTypeTemplateParmDecl *NTTP =
1791 getDeducedParameterFromExpr(Info, DAP->getSizeExpr());
1792 if (!NTTP)
1794
1795 // We can perform template argument deduction for the given non-type
1796 // template parameter.
1797 assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1798 "saw non-type template parameter with wrong depth");
1799 if (const auto *CAA = dyn_cast<ConstantArrayType>(AA)) {
1800 llvm::APSInt Size(CAA->getSize());
1802 S, TemplateParams, NTTP, Size, S.Context.getSizeType(),
1803 /*ArrayBound=*/true, Info, Deduced);
1804 }
1805 if (const auto *DAA = dyn_cast<DependentSizedArrayType>(AA))
1806 if (DAA->getSizeExpr())
1808 S, TemplateParams, NTTP, DAA->getSizeExpr(), Info, Deduced);
1809
1810 // Incomplete type does not match a dependently-sized array type
1812 }
1813
1814 // type(*)(T)
1815 // T(*)()
1816 // T(*)(T)
1817 case Type::FunctionProto: {
1818 const auto *FPP = P->castAs<FunctionProtoType>(),
1819 *FPA = A->getAs<FunctionProtoType>();
1820 if (!FPA)
1822
1823 if (FPP->getMethodQuals() != FPA->getMethodQuals() ||
1824 FPP->getRefQualifier() != FPA->getRefQualifier() ||
1825 FPP->isVariadic() != FPA->isVariadic())
1827
1828 // Check return types.
1830 S, TemplateParams, FPP->getReturnType(), FPA->getReturnType(),
1831 Info, Deduced, 0,
1832 /*PartialOrdering=*/false,
1833 /*DeducedFromArrayBound=*/false);
1835 return Result;
1836
1837 // Check parameter types.
1839 S, TemplateParams, FPP->param_type_begin(), FPP->getNumParams(),
1840 FPA->param_type_begin(), FPA->getNumParams(), Info, Deduced,
1843 return Result;
1844
1847
1848 // FIXME: Per core-2016/10/1019 (no corresponding core issue yet), permit
1849 // deducing through the noexcept-specifier if it's part of the canonical
1850 // type. libstdc++ relies on this.
1851 Expr *NoexceptExpr = FPP->getNoexceptExpr();
1852 if (const NonTypeTemplateParmDecl *NTTP =
1853 NoexceptExpr ? getDeducedParameterFromExpr(Info, NoexceptExpr)
1854 : nullptr) {
1855 assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1856 "saw non-type template parameter with wrong depth");
1857
1858 llvm::APSInt Noexcept(1);
1859 switch (FPA->canThrow()) {
1860 case CT_Cannot:
1861 Noexcept = 1;
1862 [[fallthrough]];
1863
1864 case CT_Can:
1865 // We give E in noexcept(E) the "deduced from array bound" treatment.
1866 // FIXME: Should we?
1868 S, TemplateParams, NTTP, Noexcept, S.Context.BoolTy,
1869 /*DeducedFromArrayBound=*/true, Info, Deduced);
1870
1871 case CT_Dependent:
1872 if (Expr *ArgNoexceptExpr = FPA->getNoexceptExpr())
1874 S, TemplateParams, NTTP, ArgNoexceptExpr, Info, Deduced);
1875 // Can't deduce anything from throw(T...).
1876 break;
1877 }
1878 }
1879 // FIXME: Detect non-deduced exception specification mismatches?
1880 //
1881 // Careful about [temp.deduct.call] and [temp.deduct.conv], which allow
1882 // top-level differences in noexcept-specifications.
1883
1885 }
1886
1887 case Type::InjectedClassName:
1888 // Treat a template's injected-class-name as if the template
1889 // specialization type had been used.
1890
1891 // template-name<T> (where template-name refers to a class template)
1892 // template-name<i>
1893 // TT<T>
1894 // TT<i>
1895 // TT<>
1896 case Type::TemplateSpecialization: {
1897 // When Arg cannot be a derived class, we can just try to deduce template
1898 // arguments from the template-id.
1899 if (!(TDF & TDF_DerivedClass) || !A->isRecordType())
1900 return DeduceTemplateSpecArguments(S, TemplateParams, P, A, Info,
1901 Deduced);
1902
1903 SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(),
1904 Deduced.end());
1905
1906 auto Result =
1907 DeduceTemplateSpecArguments(S, TemplateParams, P, A, Info, Deduced);
1909 return Result;
1910
1911 // We cannot inspect base classes as part of deduction when the type
1912 // is incomplete, so either instantiate any templates necessary to
1913 // complete the type, or skip over it if it cannot be completed.
1914 if (!S.isCompleteType(Info.getLocation(), A))
1915 return Result;
1916
1917 // Reset the incorrectly deduced argument from above.
1918 Deduced = DeducedOrig;
1919
1920 // Check bases according to C++14 [temp.deduct.call] p4b3:
1922 TemplateParams, P, Info, Deduced);
1924 : Result;
1925 }
1926
1927 // T type::*
1928 // T T::*
1929 // T (type::*)()
1930 // type (T::*)()
1931 // type (type::*)(T)
1932 // type (T::*)(T)
1933 // T (type::*)(T)
1934 // T (T::*)()
1935 // T (T::*)(T)
1936 case Type::MemberPointer: {
1937 const auto *MPP = P->castAs<MemberPointerType>(),
1938 *MPA = A->getAs<MemberPointerType>();
1939 if (!MPA)
1941
1942 QualType PPT = MPP->getPointeeType();
1943 if (PPT->isFunctionType())
1944 S.adjustMemberFunctionCC(PPT, /*HasThisPointer=*/false,
1945 /*IsCtorOrDtor=*/false, Info.getLocation());
1946 QualType APT = MPA->getPointeeType();
1947 if (APT->isFunctionType())
1948 S.adjustMemberFunctionCC(APT, /*HasThisPointer=*/false,
1949 /*IsCtorOrDtor=*/false, Info.getLocation());
1950
1951 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1953 S, TemplateParams, PPT, APT, Info, Deduced, SubTDF);
1955 return Result;
1957 S, TemplateParams, QualType(MPP->getClass(), 0),
1958 QualType(MPA->getClass(), 0), Info, Deduced, SubTDF);
1959 }
1960
1961 // (clang extension)
1962 //
1963 // type(^)(T)
1964 // T(^)()
1965 // T(^)(T)
1966 case Type::BlockPointer: {
1967 const auto *BPP = P->castAs<BlockPointerType>(),
1968 *BPA = A->getAs<BlockPointerType>();
1969 if (!BPA)
1972 S, TemplateParams, BPP->getPointeeType(), BPA->getPointeeType(), Info,
1973 Deduced, 0);
1974 }
1975
1976 // (clang extension)
1977 //
1978 // T __attribute__(((ext_vector_type(<integral constant>))))
1979 case Type::ExtVector: {
1980 const auto *VP = P->castAs<ExtVectorType>();
1981 QualType ElementType;
1982 if (const auto *VA = A->getAs<ExtVectorType>()) {
1983 // Make sure that the vectors have the same number of elements.
1984 if (VP->getNumElements() != VA->getNumElements())
1986 ElementType = VA->getElementType();
1987 } else if (const auto *VA = A->getAs<DependentSizedExtVectorType>()) {
1988 // We can't check the number of elements, since the argument has a
1989 // dependent number of elements. This can only occur during partial
1990 // ordering.
1991 ElementType = VA->getElementType();
1992 } else {
1994 }
1995 // Perform deduction on the element types.
1997 S, TemplateParams, VP->getElementType(), ElementType, Info, Deduced,
1998 TDF);
1999 }
2000
2001 case Type::DependentVector: {
2002 const auto *VP = P->castAs<DependentVectorType>();
2003
2004 if (const auto *VA = A->getAs<VectorType>()) {
2005 // Perform deduction on the element types.
2007 S, TemplateParams, VP->getElementType(), VA->getElementType(),
2008 Info, Deduced, TDF);
2010 return Result;
2011
2012 // Perform deduction on the vector size, if we can.
2013 const NonTypeTemplateParmDecl *NTTP =
2014 getDeducedParameterFromExpr(Info, VP->getSizeExpr());
2015 if (!NTTP)
2017
2018 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
2019 ArgSize = VA->getNumElements();
2020 // Note that we use the "array bound" rules here; just like in that
2021 // case, we don't have any particular type for the vector size, but
2022 // we can provide one if necessary.
2023 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
2024 S.Context.UnsignedIntTy, true,
2025 Info, Deduced);
2026 }
2027
2028 if (const auto *VA = A->getAs<DependentVectorType>()) {
2029 // Perform deduction on the element types.
2031 S, TemplateParams, VP->getElementType(), VA->getElementType(),
2032 Info, Deduced, TDF);
2034 return Result;
2035
2036 // Perform deduction on the vector size, if we can.
2037 const NonTypeTemplateParmDecl *NTTP =
2038 getDeducedParameterFromExpr(Info, VP->getSizeExpr());
2039 if (!NTTP)
2041
2042 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2043 VA->getSizeExpr(), Info, Deduced);
2044 }
2045
2047 }
2048
2049 // (clang extension)
2050 //
2051 // T __attribute__(((ext_vector_type(N))))
2052 case Type::DependentSizedExtVector: {
2053 const auto *VP = P->castAs<DependentSizedExtVectorType>();
2054
2055 if (const auto *VA = A->getAs<ExtVectorType>()) {
2056 // Perform deduction on the element types.
2058 S, TemplateParams, VP->getElementType(), VA->getElementType(),
2059 Info, Deduced, TDF);
2061 return Result;
2062
2063 // Perform deduction on the vector size, if we can.
2064 const NonTypeTemplateParmDecl *NTTP =
2065 getDeducedParameterFromExpr(Info, VP->getSizeExpr());
2066 if (!NTTP)
2068
2069 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
2070 ArgSize = VA->getNumElements();
2071 // Note that we use the "array bound" rules here; just like in that
2072 // case, we don't have any particular type for the vector size, but
2073 // we can provide one if necessary.
2074 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
2075 S.Context.IntTy, true, Info,
2076 Deduced);
2077 }
2078
2079 if (const auto *VA = A->getAs<DependentSizedExtVectorType>()) {
2080 // Perform deduction on the element types.
2082 S, TemplateParams, VP->getElementType(), VA->getElementType(),
2083 Info, Deduced, TDF);
2085 return Result;
2086
2087 // Perform deduction on the vector size, if we can.
2088 const NonTypeTemplateParmDecl *NTTP =
2089 getDeducedParameterFromExpr(Info, VP->getSizeExpr());
2090 if (!NTTP)
2092
2093 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2094 VA->getSizeExpr(), Info, Deduced);
2095 }
2096
2098 }
2099
2100 // (clang extension)
2101 //
2102 // T __attribute__((matrix_type(<integral constant>,
2103 // <integral constant>)))
2104 case Type::ConstantMatrix: {
2105 const auto *MP = P->castAs<ConstantMatrixType>(),
2106 *MA = A->getAs<ConstantMatrixType>();
2107 if (!MA)
2109
2110 // Check that the dimensions are the same
2111 if (MP->getNumRows() != MA->getNumRows() ||
2112 MP->getNumColumns() != MA->getNumColumns()) {
2114 }
2115 // Perform deduction on element types.
2117 S, TemplateParams, MP->getElementType(), MA->getElementType(), Info,
2118 Deduced, TDF);
2119 }
2120
2121 case Type::DependentSizedMatrix: {
2122 const auto *MP = P->castAs<DependentSizedMatrixType>();
2123 const auto *MA = A->getAs<MatrixType>();
2124 if (!MA)
2126
2127 // Check the element type of the matrixes.
2129 S, TemplateParams, MP->getElementType(), MA->getElementType(),
2130 Info, Deduced, TDF);
2132 return Result;
2133
2134 // Try to deduce a matrix dimension.
2135 auto DeduceMatrixArg =
2136 [&S, &Info, &Deduced, &TemplateParams](
2137 Expr *ParamExpr, const MatrixType *A,
2138 unsigned (ConstantMatrixType::*GetArgDimension)() const,
2139 Expr *(DependentSizedMatrixType::*GetArgDimensionExpr)() const) {
2140 const auto *ACM = dyn_cast<ConstantMatrixType>(A);
2141 const auto *ADM = dyn_cast<DependentSizedMatrixType>(A);
2142 if (!ParamExpr->isValueDependent()) {
2143 std::optional<llvm::APSInt> ParamConst =
2144 ParamExpr->getIntegerConstantExpr(S.Context);
2145 if (!ParamConst)
2147
2148 if (ACM) {
2149 if ((ACM->*GetArgDimension)() == *ParamConst)
2152 }
2153
2154 Expr *ArgExpr = (ADM->*GetArgDimensionExpr)();
2155 if (std::optional<llvm::APSInt> ArgConst =
2156 ArgExpr->getIntegerConstantExpr(S.Context))
2157 if (*ArgConst == *ParamConst)
2160 }
2161
2162 const NonTypeTemplateParmDecl *NTTP =
2163 getDeducedParameterFromExpr(Info, ParamExpr);
2164 if (!NTTP)
2166
2167 if (ACM) {
2168 llvm::APSInt ArgConst(
2170 ArgConst = (ACM->*GetArgDimension)();
2172 S, TemplateParams, NTTP, ArgConst, S.Context.getSizeType(),
2173 /*ArrayBound=*/true, Info, Deduced);
2174 }
2175
2176 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2177 (ADM->*GetArgDimensionExpr)(),
2178 Info, Deduced);
2179 };
2180
2181 if (auto Result = DeduceMatrixArg(MP->getRowExpr(), MA,
2185 return Result;
2186
2187 return DeduceMatrixArg(MP->getColumnExpr(), MA,
2190 }
2191
2192 // (clang extension)
2193 //
2194 // T __attribute__(((address_space(N))))
2195 case Type::DependentAddressSpace: {
2196 const auto *ASP = P->castAs<DependentAddressSpaceType>();
2197
2198 if (const auto *ASA = A->getAs<DependentAddressSpaceType>()) {
2199 // Perform deduction on the pointer type.
2201 S, TemplateParams, ASP->getPointeeType(), ASA->getPointeeType(),
2202 Info, Deduced, TDF);
2204 return Result;
2205
2206 // Perform deduction on the address space, if we can.
2207 const NonTypeTemplateParmDecl *NTTP =
2208 getDeducedParameterFromExpr(Info, ASP->getAddrSpaceExpr());
2209 if (!NTTP)
2211
2213 S, TemplateParams, NTTP, ASA->getAddrSpaceExpr(), Info, Deduced);
2214 }
2215
2217 llvm::APSInt ArgAddressSpace(S.Context.getTypeSize(S.Context.IntTy),
2218 false);
2219 ArgAddressSpace = toTargetAddressSpace(A.getAddressSpace());
2220
2221 // Perform deduction on the pointer types.
2223 S, TemplateParams, ASP->getPointeeType(),
2224 S.Context.removeAddrSpaceQualType(A), Info, Deduced, TDF);
2226 return Result;
2227
2228 // Perform deduction on the address space, if we can.
2229 const NonTypeTemplateParmDecl *NTTP =
2230 getDeducedParameterFromExpr(Info, ASP->getAddrSpaceExpr());
2231 if (!NTTP)
2233
2234 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2235 ArgAddressSpace, S.Context.IntTy,
2236 true, Info, Deduced);
2237 }
2238
2240 }
2241 case Type::DependentBitInt: {
2242 const auto *IP = P->castAs<DependentBitIntType>();
2243
2244 if (const auto *IA = A->getAs<BitIntType>()) {
2245 if (IP->isUnsigned() != IA->isUnsigned())
2247
2248 const NonTypeTemplateParmDecl *NTTP =
2249 getDeducedParameterFromExpr(Info, IP->getNumBitsExpr());
2250 if (!NTTP)
2252
2253 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
2254 ArgSize = IA->getNumBits();
2255
2256 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
2257 S.Context.IntTy, true, Info,
2258 Deduced);
2259 }
2260
2261 if (const auto *IA = A->getAs<DependentBitIntType>()) {
2262 if (IP->isUnsigned() != IA->isUnsigned())
2265 }
2266
2268 }
2269
2270 case Type::TypeOfExpr:
2271 case Type::TypeOf:
2272 case Type::DependentName:
2273 case Type::UnresolvedUsing:
2274 case Type::Decltype:
2275 case Type::UnaryTransform:
2276 case Type::DeducedTemplateSpecialization:
2277 case Type::DependentTemplateSpecialization:
2278 case Type::PackExpansion:
2279 case Type::Pipe:
2280 case Type::ArrayParameter:
2281 // No template argument deduction for these types
2283
2284 case Type::PackIndexing: {
2285 const PackIndexingType *PIT = P->getAs<PackIndexingType>();
2286 if (PIT->hasSelectedType()) {
2288 S, TemplateParams, PIT->getSelectedType(), A, Info, Deduced, TDF);
2289 }
2291 }
2292 }
2293
2294 llvm_unreachable("Invalid Type Class!");
2295}
2296
2302 // If the template argument is a pack expansion, perform template argument
2303 // deduction against the pattern of that expansion. This only occurs during
2304 // partial ordering.
2305 if (A.isPackExpansion())
2307
2308 switch (P.getKind()) {
2310 llvm_unreachable("Null template argument in parameter list");
2311
2315 S, TemplateParams, P.getAsType(), A.getAsType(), Info, Deduced, 0);
2316 Info.FirstArg = P;
2317 Info.SecondArg = A;
2319
2322 return DeduceTemplateArguments(S, TemplateParams, P.getAsTemplate(),
2323 A.getAsTemplate(), Info, Deduced);
2324 Info.FirstArg = P;
2325 Info.SecondArg = A;
2327
2329 llvm_unreachable("caller should handle pack expansions");
2330
2333 isSameDeclaration(P.getAsDecl(), A.getAsDecl()))
2335
2336 Info.FirstArg = P;
2337 Info.SecondArg = A;
2339
2342 S.Context.hasSameType(P.getNullPtrType(), A.getNullPtrType()))
2344
2345 Info.FirstArg = P;
2346 Info.SecondArg = A;
2348
2351 if (hasSameExtendedValue(P.getAsIntegral(), A.getAsIntegral()))
2353 }
2354 Info.FirstArg = P;
2355 Info.SecondArg = A;
2357
2362
2363 Info.FirstArg = P;
2364 Info.SecondArg = A;
2366
2368 if (const NonTypeTemplateParmDecl *NTTP =
2369 getDeducedParameterFromExpr(Info, P.getAsExpr())) {
2370 switch (A.getKind()) {
2375 S, TemplateParams, NTTP, DeducedTemplateArgument(A),
2376 A.getNonTypeTemplateArgumentType(), Info, Deduced);
2377
2379 return DeduceNullPtrTemplateArgument(S, TemplateParams, NTTP,
2380 A.getNullPtrType(), Info, Deduced);
2381
2384 S, TemplateParams, NTTP, A.getAsDecl(), A.getParamTypeForDecl(),
2385 Info, Deduced);
2386
2392 Info.FirstArg = P;
2393 Info.SecondArg = A;
2395 }
2396 llvm_unreachable("Unknown template argument kind");
2397 }
2398
2399 // Can't deduce anything, but that's okay.
2402 llvm_unreachable("Argument packs should be expanded by the caller!");
2403 }
2404
2405 llvm_unreachable("Invalid TemplateArgument Kind!");
2406}
2407
2408/// Determine whether there is a template argument to be used for
2409/// deduction.
2410///
2411/// This routine "expands" argument packs in-place, overriding its input
2412/// parameters so that \c Args[ArgIdx] will be the available template argument.
2413///
2414/// \returns true if there is another template argument (which will be at
2415/// \c Args[ArgIdx]), false otherwise.
2417 unsigned &ArgIdx) {
2418 if (ArgIdx == Args.size())
2419 return false;
2420
2421 const TemplateArgument &Arg = Args[ArgIdx];
2422 if (Arg.getKind() != TemplateArgument::Pack)
2423 return true;
2424
2425 assert(ArgIdx == Args.size() - 1 && "Pack not at the end of argument list?");
2426 Args = Arg.pack_elements();
2427 ArgIdx = 0;
2428 return ArgIdx < Args.size();
2429}
2430
2431/// Determine whether the given set of template arguments has a pack
2432/// expansion that is not the last template argument.
2434 bool FoundPackExpansion = false;
2435 for (const auto &A : Args) {
2436 if (FoundPackExpansion)
2437 return true;
2438
2439 if (A.getKind() == TemplateArgument::Pack)
2440 return hasPackExpansionBeforeEnd(A.pack_elements());
2441
2442 // FIXME: If this is a fixed-arity pack expansion from an outer level of
2443 // templates, it should not be treated as a pack expansion.
2444 if (A.isPackExpansion())
2445 FoundPackExpansion = true;
2446 }
2447
2448 return false;
2449}
2450
2457 bool NumberOfArgumentsMustMatch) {
2458 // C++0x [temp.deduct.type]p9:
2459 // If the template argument list of P contains a pack expansion that is not
2460 // the last template argument, the entire template argument list is a
2461 // non-deduced context.
2464
2465 // C++0x [temp.deduct.type]p9:
2466 // If P has a form that contains <T> or <i>, then each argument Pi of the
2467 // respective template argument list P is compared with the corresponding
2468 // argument Ai of the corresponding template argument list of A.
2469 unsigned ArgIdx = 0, ParamIdx = 0;
2471 const TemplateArgument &P = Ps[ParamIdx];
2472 if (!P.isPackExpansion()) {
2473 // The simple case: deduce template arguments by matching Pi and Ai.
2474
2475 // Check whether we have enough arguments.
2476 if (!hasTemplateArgumentForDeduction(As, ArgIdx))
2477 return NumberOfArgumentsMustMatch
2480
2481 // C++1z [temp.deduct.type]p9:
2482 // During partial ordering, if Ai was originally a pack expansion [and]
2483 // Pi is not a pack expansion, template argument deduction fails.
2484 if (As[ArgIdx].isPackExpansion())
2486
2487 // Perform deduction for this Pi/Ai pair.
2488 if (auto Result = DeduceTemplateArguments(S, TemplateParams, P,
2489 As[ArgIdx], Info, Deduced);
2491 return Result;
2492
2493 // Move to the next argument.
2494 ++ArgIdx;
2495 continue;
2496 }
2497
2498 // The parameter is a pack expansion.
2499
2500 // C++0x [temp.deduct.type]p9:
2501 // If Pi is a pack expansion, then the pattern of Pi is compared with
2502 // each remaining argument in the template argument list of A. Each
2503 // comparison deduces template arguments for subsequent positions in the
2504 // template parameter packs expanded by Pi.
2505 TemplateArgument Pattern = P.getPackExpansionPattern();
2506
2507 // Prepare to deduce the packs within the pattern.
2508 PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
2509
2510 // Keep track of the deduced template arguments for each parameter pack
2511 // expanded by this pack expansion (the outer index) and for each
2512 // template argument (the inner SmallVectors).
2513 for (; hasTemplateArgumentForDeduction(As, ArgIdx) &&
2514 PackScope.hasNextElement();
2515 ++ArgIdx) {
2516 // Deduce template arguments from the pattern.
2517 if (auto Result = DeduceTemplateArguments(S, TemplateParams, Pattern,
2518 As[ArgIdx], Info, Deduced);
2520 return Result;
2521
2522 PackScope.nextPackElement();
2523 }
2524
2525 // Build argument packs for each of the parameter packs expanded by this
2526 // pack expansion.
2527 if (auto Result = PackScope.finish();
2529 return Result;
2530 }
2531
2533}
2534
2539 bool NumberOfArgumentsMustMatch) {
2540 return ::DeduceTemplateArguments(*this, TemplateParams, Ps, As, Info, Deduced,
2541 NumberOfArgumentsMustMatch);
2542}
2543
2544/// Determine whether two template arguments are the same.
2545static bool isSameTemplateArg(ASTContext &Context,
2547 const TemplateArgument &Y,
2548 bool PartialOrdering,
2549 bool PackExpansionMatchesPack = false) {
2550 // If we're checking deduced arguments (X) against original arguments (Y),
2551 // we will have flattened packs to non-expansions in X.
2552 if (PackExpansionMatchesPack && X.isPackExpansion() && !Y.isPackExpansion())
2553 X = X.getPackExpansionPattern();
2554
2555 if (X.getKind() != Y.getKind())
2556 return false;
2557
2558 switch (X.getKind()) {
2560 llvm_unreachable("Comparing NULL template argument");
2561
2563 return Context.getCanonicalType(X.getAsType()) ==
2564 Context.getCanonicalType(Y.getAsType());
2565
2567 return isSameDeclaration(X.getAsDecl(), Y.getAsDecl());
2568
2570 return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
2571
2574 return Context.getCanonicalTemplateName(
2575 X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
2578
2580 return hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral());
2581
2583 return X.structurallyEquals(Y);
2584
2586 llvm::FoldingSetNodeID XID, YID;
2587 X.getAsExpr()->Profile(XID, Context, true);
2588 Y.getAsExpr()->Profile(YID, Context, true);
2589 return XID == YID;
2590 }
2591
2593 unsigned PackIterationSize = X.pack_size();
2594 if (X.pack_size() != Y.pack_size()) {
2595 if (!PartialOrdering)
2596 return false;
2597
2598 // C++0x [temp.deduct.type]p9:
2599 // During partial ordering, if Ai was originally a pack expansion:
2600 // - if P does not contain a template argument corresponding to Ai
2601 // then Ai is ignored;
2602 bool XHasMoreArg = X.pack_size() > Y.pack_size();
2603 if (!(XHasMoreArg && X.pack_elements().back().isPackExpansion()) &&
2604 !(!XHasMoreArg && Y.pack_elements().back().isPackExpansion()))
2605 return false;
2606
2607 if (XHasMoreArg)
2608 PackIterationSize = Y.pack_size();
2609 }
2610
2611 ArrayRef<TemplateArgument> XP = X.pack_elements();
2613 for (unsigned i = 0; i < PackIterationSize; ++i)
2614 if (!isSameTemplateArg(Context, XP[i], YP[i], PartialOrdering,
2615 PackExpansionMatchesPack))
2616 return false;
2617 return true;
2618 }
2619 }
2620
2621 llvm_unreachable("Invalid TemplateArgument Kind!");
2622}
2623
2624/// Allocate a TemplateArgumentLoc where all locations have
2625/// been initialized to the given location.
2626///
2627/// \param Arg The template argument we are producing template argument
2628/// location information for.
2629///
2630/// \param NTTPType For a declaration template argument, the type of
2631/// the non-type template parameter that corresponds to this template
2632/// argument. Can be null if no type sugar is available to add to the
2633/// type from the template argument.
2634///
2635/// \param Loc The source location to use for the resulting template
2636/// argument.
2639 QualType NTTPType, SourceLocation Loc) {
2640 switch (Arg.getKind()) {
2642 llvm_unreachable("Can't get a NULL template argument here");
2643
2645 return TemplateArgumentLoc(
2646 Arg, Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
2647
2649 if (NTTPType.isNull())
2650 NTTPType = Arg.getParamTypeForDecl();
2651 Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2652 .getAs<Expr>();
2654 }
2655
2657 if (NTTPType.isNull())
2658 NTTPType = Arg.getNullPtrType();
2659 Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2660 .getAs<Expr>();
2661 return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true),
2662 E);
2663 }
2664
2669 }
2670
2676 Builder.MakeTrivial(Context, DTN->getQualifier(), Loc);
2677 else if (QualifiedTemplateName *QTN =
2678 Template.getAsQualifiedTemplateName())
2679 Builder.MakeTrivial(Context, QTN->getQualifier(), Loc);
2680
2682 return TemplateArgumentLoc(Context, Arg,
2683 Builder.getWithLocInContext(Context), Loc);
2684
2685 return TemplateArgumentLoc(
2686 Context, Arg, Builder.getWithLocInContext(Context), Loc, Loc);
2687 }
2688
2690 return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2691
2694 }
2695
2696 llvm_unreachable("Invalid TemplateArgument Kind!");
2697}
2698
2701 SourceLocation Location) {
2703 Context.getInjectedTemplateArg(TemplateParm), QualType(), Location);
2704}
2705
2706/// Convert the given deduced template argument and add it to the set of
2707/// fully-converted template arguments.
2709 Sema &S, NamedDecl *Param, DeducedTemplateArgument Arg, NamedDecl *Template,
2710 TemplateDeductionInfo &Info, bool IsDeduced,
2711 SmallVectorImpl<TemplateArgument> &SugaredOutput,
2712 SmallVectorImpl<TemplateArgument> &CanonicalOutput) {
2713 auto ConvertArg = [&](DeducedTemplateArgument Arg,
2714 unsigned ArgumentPackIndex) {
2715 // Convert the deduced template argument into a template
2716 // argument that we can check, almost as if the user had written
2717 // the template argument explicitly.
2718 TemplateArgumentLoc ArgLoc =
2720
2721 // Check the template argument, converting it as necessary.
2722 return S.CheckTemplateArgument(
2723 Param, ArgLoc, Template, Template->getLocation(),
2724 Template->getSourceRange().getEnd(), ArgumentPackIndex, SugaredOutput,
2725 CanonicalOutput,
2726 IsDeduced
2730 };
2731
2732 if (Arg.getKind() == TemplateArgument::Pack) {
2733 // This is a template argument pack, so check each of its arguments against
2734 // the template parameter.
2735 SmallVector<TemplateArgument, 2> SugaredPackedArgsBuilder,
2736 CanonicalPackedArgsBuilder;
2737 for (const auto &P : Arg.pack_elements()) {
2738 // When converting the deduced template argument, append it to the
2739 // general output list. We need to do this so that the template argument
2740 // checking logic has all of the prior template arguments available.
2741 DeducedTemplateArgument InnerArg(P);
2743 assert(InnerArg.getKind() != TemplateArgument::Pack &&
2744 "deduced nested pack");
2745 if (P.isNull()) {
2746 // We deduced arguments for some elements of this pack, but not for
2747 // all of them. This happens if we get a conditionally-non-deduced
2748 // context in a pack expansion (such as an overload set in one of the
2749 // arguments).
2750 S.Diag(Param->getLocation(),
2751 diag::err_template_arg_deduced_incomplete_pack)
2752 << Arg << Param;
2753 return true;
2754 }
2755 if (ConvertArg(InnerArg, SugaredPackedArgsBuilder.size()))
2756 return true;
2757
2758 // Move the converted template argument into our argument pack.
2759 SugaredPackedArgsBuilder.push_back(SugaredOutput.pop_back_val());
2760 CanonicalPackedArgsBuilder.push_back(CanonicalOutput.pop_back_val());
2761 }
2762
2763 // If the pack is empty, we still need to substitute into the parameter
2764 // itself, in case that substitution fails.
2765 if (SugaredPackedArgsBuilder.empty()) {
2767 MultiLevelTemplateArgumentList Args(Template, SugaredOutput,
2768 /*Final=*/true);
2769
2770 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2771 Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2772 NTTP, SugaredOutput,
2773 Template->getSourceRange());
2774 if (Inst.isInvalid() ||
2775 S.SubstType(NTTP->getType(), Args, NTTP->getLocation(),
2776 NTTP->getDeclName()).isNull())
2777 return true;
2778 } else if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(Param)) {
2779 Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2780 TTP, SugaredOutput,
2781 Template->getSourceRange());
2782 if (Inst.isInvalid() || !S.SubstDecl(TTP, S.CurContext, Args))
2783 return true;
2784 }
2785 // For type parameters, no substitution is ever required.
2786 }
2787
2788 // Create the resulting argument pack.
2789 SugaredOutput.push_back(
2790 TemplateArgument::CreatePackCopy(S.Context, SugaredPackedArgsBuilder));
2791 CanonicalOutput.push_back(TemplateArgument::CreatePackCopy(
2792 S.Context, CanonicalPackedArgsBuilder));
2793 return false;
2794 }
2795
2796 return ConvertArg(Arg, 0);
2797}
2798
2799// FIXME: This should not be a template, but
2800// ClassTemplatePartialSpecializationDecl sadly does not derive from
2801// TemplateDecl.
2802template <typename TemplateDeclT>
2804 Sema &S, TemplateDeclT *Template, bool IsDeduced,
2807 SmallVectorImpl<TemplateArgument> &SugaredBuilder,
2808 SmallVectorImpl<TemplateArgument> &CanonicalBuilder,
2809 LocalInstantiationScope *CurrentInstantiationScope = nullptr,
2810 unsigned NumAlreadyConverted = 0, bool PartialOverloading = false) {
2811 TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2812
2813 for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2814 NamedDecl *Param = TemplateParams->getParam(I);
2815
2816 // C++0x [temp.arg.explicit]p3:
2817 // A trailing template parameter pack (14.5.3) not otherwise deduced will
2818 // be deduced to an empty sequence of template arguments.
2819 // FIXME: Where did the word "trailing" come from?
2820 if (Deduced[I].isNull() && Param->isTemplateParameterPack()) {
2821 if (auto Result =
2822 PackDeductionScope(S, TemplateParams, Deduced, Info, I).finish();
2824 return Result;
2825 }
2826
2827 if (!Deduced[I].isNull()) {
2828 if (I < NumAlreadyConverted) {
2829 // We may have had explicitly-specified template arguments for a
2830 // template parameter pack (that may or may not have been extended
2831 // via additional deduced arguments).
2832 if (Param->isParameterPack() && CurrentInstantiationScope &&
2833 CurrentInstantiationScope->getPartiallySubstitutedPack() == Param) {
2834 // Forget the partially-substituted pack; its substitution is now
2835 // complete.
2836 CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2837 // We still need to check the argument in case it was extended by
2838 // deduction.
2839 } else {
2840 // We have already fully type-checked and converted this
2841 // argument, because it was explicitly-specified. Just record the
2842 // presence of this argument.
2843 SugaredBuilder.push_back(Deduced[I]);
2844 CanonicalBuilder.push_back(
2846 continue;
2847 }
2848 }
2849
2850 // We may have deduced this argument, so it still needs to be
2851 // checked and converted.
2852 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info,
2853 IsDeduced, SugaredBuilder,
2854 CanonicalBuilder)) {
2855 Info.Param = makeTemplateParameter(Param);
2856 // FIXME: These template arguments are temporary. Free them!
2857 Info.reset(
2858 TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder),
2859 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder));
2861 }
2862
2863 continue;
2864 }
2865
2866 // Substitute into the default template argument, if available.
2867 bool HasDefaultArg = false;
2868 TemplateDecl *TD = dyn_cast<TemplateDecl>(Template);
2869 if (!TD) {
2870 assert(isa<ClassTemplatePartialSpecializationDecl>(Template) ||
2871 isa<VarTemplatePartialSpecializationDecl>(Template));
2873 }
2874
2875 TemplateArgumentLoc DefArg;
2876 {
2877 Qualifiers ThisTypeQuals;
2878 CXXRecordDecl *ThisContext = nullptr;
2879 if (auto *Rec = dyn_cast<CXXRecordDecl>(TD->getDeclContext()))
2880 if (Rec->isLambda())
2881 if (auto *Method = dyn_cast<CXXMethodDecl>(Rec->getDeclContext())) {
2882 ThisContext = Method->getParent();
2883 ThisTypeQuals = Method->getMethodQualifiers();
2884 }
2885
2886 Sema::CXXThisScopeRAII ThisScope(S, ThisContext, ThisTypeQuals,
2887 S.getLangOpts().CPlusPlus17);
2888
2890 TD, TD->getLocation(), TD->getSourceRange().getEnd(), Param,
2891 SugaredBuilder, CanonicalBuilder, HasDefaultArg);
2892 }
2893
2894 // If there was no default argument, deduction is incomplete.
2895 if (DefArg.getArgument().isNull()) {
2897 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2898 Info.reset(TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder),
2899 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder));
2900 if (PartialOverloading) break;
2901
2904 }
2905
2906 // Check whether we can actually use the default argument.
2908 Param, DefArg, TD, TD->getLocation(), TD->getSourceRange().getEnd(),
2909 0, SugaredBuilder, CanonicalBuilder, Sema::CTAK_Specified)) {
2911 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2912 // FIXME: These template arguments are temporary. Free them!
2913 Info.reset(TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder),
2914 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder));
2916 }
2917
2918 // If we get here, we successfully used the default template argument.
2919 }
2920
2922}
2923
2925 if (auto *DC = dyn_cast<DeclContext>(D))
2926 return DC;
2927 return D->getDeclContext();
2928}
2929
2930template<typename T> struct IsPartialSpecialization {
2931 static constexpr bool value = false;
2932};
2933template<>
2935 static constexpr bool value = true;
2936};
2937template<>
2939 static constexpr bool value = true;
2940};
2941template <typename TemplateDeclT>
2942static bool DeducedArgsNeedReplacement(TemplateDeclT *Template) {
2943 return false;
2944}
2945template <>
2948 return !Spec->isClassScopeExplicitSpecialization();
2949}
2950template <>
2953 return !Spec->isClassScopeExplicitSpecialization();
2954}
2955
2956template <typename TemplateDeclT>
2958CheckDeducedArgumentConstraints(Sema &S, TemplateDeclT *Template,
2959 ArrayRef<TemplateArgument> SugaredDeducedArgs,
2960 ArrayRef<TemplateArgument> CanonicalDeducedArgs,
2961 TemplateDeductionInfo &Info) {
2962 llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
2963 Template->getAssociatedConstraints(AssociatedConstraints);
2964
2965 std::optional<ArrayRef<TemplateArgument>> Innermost;
2966 // If we don't need to replace the deduced template arguments,
2967 // we can add them immediately as the inner-most argument list.
2968 if (!DeducedArgsNeedReplacement(Template))
2969 Innermost = CanonicalDeducedArgs;
2970
2972 Template, Template->getDeclContext(), /*Final=*/false, Innermost,
2973 /*RelativeToPrimary=*/true, /*Pattern=*/
2974 nullptr, /*ForConstraintInstantiation=*/true);
2975
2976 // getTemplateInstantiationArgs picks up the non-deduced version of the
2977 // template args when this is a variable template partial specialization and
2978 // not class-scope explicit specialization, so replace with Deduced Args
2979 // instead of adding to inner-most.
2980 if (!Innermost)
2981 MLTAL.replaceInnermostTemplateArguments(Template, CanonicalDeducedArgs);
2982
2983 if (S.CheckConstraintSatisfaction(Template, AssociatedConstraints, MLTAL,
2984 Info.getLocation(),
2987 Info.reset(
2988 TemplateArgumentList::CreateCopy(S.Context, SugaredDeducedArgs),
2989 TemplateArgumentList::CreateCopy(S.Context, CanonicalDeducedArgs));
2991 }
2993}
2994
2995/// Complete template argument deduction for a partial specialization.
2996template <typename T>
2997static std::enable_if_t<IsPartialSpecialization<T>::value,
3000 Sema &S, T *Partial, bool IsPartialOrdering,
3001 ArrayRef<TemplateArgument> TemplateArgs,
3003 TemplateDeductionInfo &Info) {
3004 // Unevaluated SFINAE context.
3007 Sema::SFINAETrap Trap(S);
3008
3009 Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Partial));
3010
3011 // C++ [temp.deduct.type]p2:
3012 // [...] or if any template argument remains neither deduced nor
3013 // explicitly specified, template argument deduction fails.
3014 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
3016 S, Partial, IsPartialOrdering, Deduced, Info, SugaredBuilder,
3017 CanonicalBuilder);
3019 return Result;
3020
3021 // Form the template argument list from the deduced template arguments.
3022 TemplateArgumentList *SugaredDeducedArgumentList =
3023 TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder);
3024 TemplateArgumentList *CanonicalDeducedArgumentList =
3025 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder);
3026
3027 Info.reset(SugaredDeducedArgumentList, CanonicalDeducedArgumentList);
3028
3029 // Substitute the deduced template arguments into the template
3030 // arguments of the class template partial specialization, and
3031 // verify that the instantiated template arguments are both valid
3032 // and are equivalent to the template arguments originally provided
3033 // to the class template.
3034 LocalInstantiationScope InstScope(S);
3035 auto *Template = Partial->getSpecializedTemplate();
3036 const ASTTemplateArgumentListInfo *PartialTemplArgInfo =
3037 Partial->getTemplateArgsAsWritten();
3038
3039 TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
3040 PartialTemplArgInfo->RAngleLoc);
3041
3042 if (S.SubstTemplateArguments(PartialTemplArgInfo->arguments(),
3044 SugaredBuilder,
3045 /*Final=*/true),
3046 InstArgs)) {
3047 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
3048 if (ParamIdx >= Partial->getTemplateParameters()->size())
3049 ParamIdx = Partial->getTemplateParameters()->size() - 1;
3050
3051 Decl *Param = const_cast<NamedDecl *>(
3052 Partial->getTemplateParameters()->getParam(ParamIdx));
3053 Info.Param = makeTemplateParameter(Param);
3054 Info.FirstArg = (*PartialTemplArgInfo)[ArgIdx].getArgument();
3056 }
3057
3059 SmallVector<TemplateArgument, 4> SugaredConvertedInstArgs,
3060 CanonicalConvertedInstArgs;
3062 Template, Partial->getLocation(), InstArgs, false,
3063 SugaredConvertedInstArgs, CanonicalConvertedInstArgs,
3064 /*UpdateArgsWithConversions=*/true, &ConstraintsNotSatisfied))
3068
3069 TemplateParameterList *TemplateParams = Template->getTemplateParameters();
3070 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
3071 TemplateArgument InstArg = SugaredConvertedInstArgs.data()[I];
3072 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg,
3073 IsPartialOrdering)) {
3074 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
3075 Info.FirstArg = TemplateArgs[I];
3076 Info.SecondArg = InstArg;
3078 }
3079 }
3080
3081 if (Trap.hasErrorOccurred())
3083
3084 if (auto Result = CheckDeducedArgumentConstraints(S, Partial, SugaredBuilder,
3085 CanonicalBuilder, Info);
3087 return Result;
3088
3090}
3091
3092/// Complete template argument deduction for a class or variable template,
3093/// when partial ordering against a partial specialization.
3094// FIXME: Factor out duplication with partial specialization version above.
3096 Sema &S, TemplateDecl *Template, bool PartialOrdering,
3097 ArrayRef<TemplateArgument> TemplateArgs,
3099 TemplateDeductionInfo &Info) {
3100 // Unevaluated SFINAE context.
3103 Sema::SFINAETrap Trap(S);
3104
3105 Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Template));
3106
3107 // C++ [temp.deduct.type]p2:
3108 // [...] or if any template argument remains neither deduced nor
3109 // explicitly specified, template argument deduction fails.
3110 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
3112 S, Template, /*IsDeduced*/ PartialOrdering, Deduced, Info,
3113 SugaredBuilder, CanonicalBuilder,
3114 /*CurrentInstantiationScope=*/nullptr,
3115 /*NumAlreadyConverted=*/0U, /*PartialOverloading=*/false);
3117 return Result;
3118
3119 // Check that we produced the correct argument list.
3120 TemplateParameterList *TemplateParams = Template->getTemplateParameters();
3121 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
3122 TemplateArgument InstArg = CanonicalBuilder[I];
3123 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg, PartialOrdering,
3124 /*PackExpansionMatchesPack=*/true)) {
3125 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
3126 Info.FirstArg = TemplateArgs[I];
3127 Info.SecondArg = InstArg;
3129 }
3130 }
3131
3132 if (Trap.hasErrorOccurred())
3134
3135 if (auto Result = CheckDeducedArgumentConstraints(S, Template, SugaredBuilder,
3136 CanonicalBuilder, Info);
3138 return Result;
3139
3141}
3142
3143/// Perform template argument deduction to determine whether the given template
3144/// arguments match the given class or variable template partial specialization
3145/// per C++ [temp.class.spec.match].
3146template <typename T>
3147static std::enable_if_t<IsPartialSpecialization<T>::value,
3150 ArrayRef<TemplateArgument> TemplateArgs,
3151 TemplateDeductionInfo &Info) {
3152 if (Partial->isInvalidDecl())
3154
3155 // C++ [temp.class.spec.match]p2:
3156 // A partial specialization matches a given actual template
3157 // argument list if the template arguments of the partial
3158 // specialization can be deduced from the actual template argument
3159 // list (14.8.2).
3160
3161 // Unevaluated SFINAE context.
3164 Sema::SFINAETrap Trap(S);
3165
3166 // This deduction has no relation to any outer instantiation we might be
3167 // performing.
3168 LocalInstantiationScope InstantiationScope(S);
3169
3171 Deduced.resize(Partial->getTemplateParameters()->size());
3173 S, Partial->getTemplateParameters(),
3174 Partial->getTemplateArgs().asArray(), TemplateArgs, Info, Deduced,
3175 /*NumberOfArgumentsMustMatch=*/false);
3177 return Result;
3178
3179 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3180 Sema::InstantiatingTemplate Inst(S, Info.getLocation(), Partial, DeducedArgs,
3181 Info);
3182 if (Inst.isInvalid())
3184
3185 if (Trap.hasErrorOccurred())
3187
3190 Result = ::FinishTemplateArgumentDeduction(S, Partial,
3191 /*IsPartialOrdering=*/false,
3192 TemplateArgs, Deduced, Info);
3193 });
3194 return Result;
3195}
3196
3199 ArrayRef<TemplateArgument> TemplateArgs,
3200 TemplateDeductionInfo &Info) {
3201 return ::DeduceTemplateArguments(*this, Partial, TemplateArgs, Info);
3202}
3205 ArrayRef<TemplateArgument> TemplateArgs,
3206 TemplateDeductionInfo &Info) {
3207 return ::DeduceTemplateArguments(*this, Partial, TemplateArgs, Info);
3208}
3209
3210/// Determine whether the given type T is a simple-template-id type.
3212 if (const TemplateSpecializationType *Spec
3214 return Spec->getTemplateName().getAsTemplateDecl() != nullptr;
3215
3216 // C++17 [temp.local]p2:
3217 // the injected-class-name [...] is equivalent to the template-name followed
3218 // by the template-arguments of the class template specialization or partial
3219 // specialization enclosed in <>
3220 // ... which means it's equivalent to a simple-template-id.
3221 //
3222 // This only arises during class template argument deduction for a copy
3223 // deduction candidate, where it permits slicing.
3225 return true;
3226
3227 return false;
3228}
3229
3230/// Substitute the explicitly-provided template arguments into the
3231/// given function template according to C++ [temp.arg.explicit].
3232///
3233/// \param FunctionTemplate the function template into which the explicit
3234/// template arguments will be substituted.
3235///
3236/// \param ExplicitTemplateArgs the explicitly-specified template
3237/// arguments.
3238///
3239/// \param Deduced the deduced template arguments, which will be populated
3240/// with the converted and checked explicit template arguments.
3241///
3242/// \param ParamTypes will be populated with the instantiated function
3243/// parameters.
3244///
3245/// \param FunctionType if non-NULL, the result type of the function template
3246/// will also be instantiated and the pointed-to value will be updated with
3247/// the instantiated function type.
3248///
3249/// \param Info if substitution fails for any reason, this object will be
3250/// populated with more information about the failure.
3251///
3252/// \returns TemplateDeductionResult::Success if substitution was successful, or
3253/// some failure condition.
3255 FunctionTemplateDecl *FunctionTemplate,
3256 TemplateArgumentListInfo &ExplicitTemplateArgs,
3259 TemplateDeductionInfo &Info) {
3260 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3261 TemplateParameterList *TemplateParams
3262 = FunctionTemplate->getTemplateParameters();
3263
3264 if (ExplicitTemplateArgs.size() == 0) {
3265 // No arguments to substitute; just copy over the parameter types and
3266 // fill in the function type.
3267 for (auto *P : Function->parameters())
3268 ParamTypes.push_back(P->getType());
3269
3270 if (FunctionType)
3271 *FunctionType = Function->getType();
3273 }
3274
3275 // Unevaluated SFINAE context.
3278 SFINAETrap Trap(*this);
3279
3280 // C++ [temp.arg.explicit]p3:
3281 // Template arguments that are present shall be specified in the
3282 // declaration order of their corresponding template-parameters. The
3283 // template argument list shall not specify more template-arguments than
3284 // there are corresponding template-parameters.
3285 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
3286
3287 // Enter a new template instantiation context where we check the
3288 // explicitly-specified template arguments against this function template,
3289 // and then substitute them into the function parameter types.
3292 *this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3294 if (Inst.isInvalid())
3296
3298 ExplicitTemplateArgs, true, SugaredBuilder,
3299 CanonicalBuilder,
3300 /*UpdateArgsWithConversions=*/false) ||
3301 Trap.hasErrorOccurred()) {
3302 unsigned Index = SugaredBuilder.size();
3303 if (Index >= TemplateParams->size())
3305 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
3307 }
3308
3309 // Form the template argument list from the explicitly-specified
3310 // template arguments.
3311 TemplateArgumentList *SugaredExplicitArgumentList =
3313 TemplateArgumentList *CanonicalExplicitArgumentList =
3314 TemplateArgumentList::CreateCopy(Context, CanonicalBuilder);
3315 Info.setExplicitArgs(SugaredExplicitArgumentList,
3316 CanonicalExplicitArgumentList);
3317
3318 // Template argument deduction and the final substitution should be
3319 // done in the context of the templated declaration. Explicit
3320 // argument substitution, on the other hand, needs to happen in the
3321 // calling context.
3322 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3323
3324 // If we deduced template arguments for a template parameter pack,
3325 // note that the template argument pack is partially substituted and record
3326 // the explicit template arguments. They'll be used as part of deduction
3327 // for this template parameter pack.
3328 unsigned PartiallySubstitutedPackIndex = -1u;
3329 if (!CanonicalBuilder.empty()) {
3330 const TemplateArgument &Arg = CanonicalBuilder.back();
3331 if (Arg.getKind() == TemplateArgument::Pack) {
3332 auto *Param = TemplateParams->getParam(CanonicalBuilder.size() - 1);
3333 // If this is a fully-saturated fixed-size pack, it should be
3334 // fully-substituted, not partially-substituted.
3335 std::optional<unsigned> Expansions = getExpandedPackSize(Param);
3336 if (!Expansions || Arg.pack_size() < *Expansions) {
3337 PartiallySubstitutedPackIndex = CanonicalBuilder.size() - 1;
3339 Param, Arg.pack_begin(), Arg.pack_size());
3340 }
3341 }
3342 }
3343
3344 const FunctionProtoType *Proto
3345 = Function->getType()->getAs<FunctionProtoType>();
3346 assert(Proto && "Function template does not have a prototype?");
3347
3348 // Isolate our substituted parameters from our caller.
3349 LocalInstantiationScope InstScope(*this, /*MergeWithOuterScope*/true);
3350
3351 ExtParameterInfoBuilder ExtParamInfos;
3352
3354 SugaredExplicitArgumentList->asArray(),
3355 /*Final=*/true);
3356
3357 // Instantiate the types of each of the function parameters given the
3358 // explicitly-specified template arguments. If the function has a trailing
3359 // return type, substitute it after the arguments to ensure we substitute
3360 // in lexical order.
3361 if (Proto->hasTrailingReturn()) {
3362 if (SubstParmTypes(Function->getLocation(), Function->parameters(),
3363 Proto->getExtParameterInfosOrNull(), MLTAL, ParamTypes,
3364 /*params=*/nullptr, ExtParamInfos))
3366 }
3367
3368 // Instantiate the return type.
3369 QualType ResultType;
3370 {
3371 // C++11 [expr.prim.general]p3:
3372 // If a declaration declares a member function or member function
3373 // template of a class X, the expression this is a prvalue of type
3374 // "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
3375 // and the end of the function-definition, member-declarator, or
3376 // declarator.
3377 Qualifiers ThisTypeQuals;
3378 CXXRecordDecl *ThisContext = nullptr;
3379 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
3380 ThisContext = Method->getParent();
3381 ThisTypeQuals = Method->getMethodQualifiers();
3382 }
3383
3384 CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
3386
3387 ResultType =
3388 SubstType(Proto->getReturnType(), MLTAL,
3389 Function->getTypeSpecStartLoc(), Function->getDeclName());
3390 if (ResultType.isNull() || Trap.hasErrorOccurred())
3392 // CUDA: Kernel function must have 'void' return type.
3393 if (getLangOpts().CUDA)
3394 if (Function->hasAttr<CUDAGlobalAttr>() && !ResultType->isVoidType()) {
3395 Diag(Function->getLocation(), diag::err_kern_type_not_void_return)
3396 << Function->getType() << Function->getSourceRange();
3398 }
3399 }
3400
3401 // Instantiate the types of each of the function parameters given the
3402 // explicitly-specified template arguments if we didn't do so earlier.
3403 if (!Proto->hasTrailingReturn() &&
3404 SubstParmTypes(Function->getLocation(), Function->parameters(),
3405 Proto->getExtParameterInfosOrNull(), MLTAL, ParamTypes,
3406 /*params*/ nullptr, ExtParamInfos))
3408
3409 if (FunctionType) {
3410 auto EPI = Proto->getExtProtoInfo();
3411 EPI.ExtParameterInfos = ExtParamInfos.getPointerOrNull(ParamTypes.size());
3412
3413 // In C++1z onwards, exception specifications are part of the function type,
3414 // so substitution into the type must also substitute into the exception
3415 // specification.
3416 SmallVector<QualType, 4> ExceptionStorage;
3417 if (getLangOpts().CPlusPlus17 &&
3419 Function->getLocation(), EPI.ExceptionSpec, ExceptionStorage,
3421 FunctionTemplate, nullptr, /*Final=*/true,
3422 /*Innermost=*/SugaredExplicitArgumentList->asArray(),
3423 /*RelativeToPrimary=*/false,
3424 /*Pattern=*/nullptr,
3425 /*ForConstraintInstantiation=*/false,
3426 /*SkipForSpecialization=*/true)))
3428
3429 *FunctionType = BuildFunctionType(ResultType, ParamTypes,
3430 Function->getLocation(),
3431 Function->getDeclName(),
3432 EPI);
3433 if (FunctionType->isNull() || Trap.hasErrorOccurred())
3435 }
3436
3437 // C++ [temp.arg.explicit]p2:
3438 // Trailing template arguments that can be deduced (14.8.2) may be
3439 // omitted from the list of explicit template-arguments. If all of the
3440 // template arguments can be deduced, they may all be omitted; in this
3441 // case, the empty template argument list <> itself may also be omitted.
3442 //
3443 // Take all of the explicitly-specified arguments and put them into
3444 // the set of deduced template arguments. The partially-substituted
3445 // parameter pack, however, will be set to NULL since the deduction
3446 // mechanism handles the partially-substituted argument pack directly.
3447 Deduced.reserve(TemplateParams->size());
3448 for (unsigned I = 0, N = SugaredExplicitArgumentList->size(); I != N; ++I) {
3449 const TemplateArgument &Arg = SugaredExplicitArgumentList->get(I);
3450 if (I == PartiallySubstitutedPackIndex)
3451 Deduced.push_back(DeducedTemplateArgument());
3452 else
3453 Deduced.push_back(Arg);
3454 }
3455
3457}
3458
3459/// Check whether the deduced argument type for a call to a function
3460/// template matches the actual argument type per C++ [temp.deduct.call]p4.
3463 Sema::OriginalCallArg OriginalArg,
3464 QualType DeducedA) {
3465 ASTContext &Context = S.Context;
3466
3467 auto Failed = [&]() -> TemplateDeductionResult {
3468 Info.FirstArg = TemplateArgument(DeducedA);
3469 Info.SecondArg = TemplateArgument(OriginalArg.OriginalArgType);
3470 Info.CallArgIndex = OriginalArg.ArgIdx;
3471 return OriginalArg.DecomposedParam
3474 };
3475
3476 QualType A = OriginalArg.OriginalArgType;
3477 QualType OriginalParamType = OriginalArg.OriginalParamType;
3478
3479 // Check for type equality (top-level cv-qualifiers are ignored).
3480 if (Context.hasSameUnqualifiedType(A, DeducedA))
3482
3483 // Strip off references on the argument types; they aren't needed for
3484 // the following checks.
3485 if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
3486 DeducedA = DeducedARef->getPointeeType();
3487 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3488 A = ARef->getPointeeType();
3489
3490 // C++ [temp.deduct.call]p4:
3491 // [...] However, there are three cases that allow a difference:
3492 // - If the original P is a reference type, the deduced A (i.e., the
3493 // type referred to by the reference) can be more cv-qualified than
3494 // the transformed A.
3495 if (const ReferenceType *OriginalParamRef
3496 = OriginalParamType->getAs<ReferenceType>()) {
3497 // We don't want to keep the reference around any more.
3498 OriginalParamType = OriginalParamRef->getPointeeType();
3499
3500 // FIXME: Resolve core issue (no number yet): if the original P is a
3501 // reference type and the transformed A is function type "noexcept F",
3502 // the deduced A can be F.
3503 QualType Tmp;
3504 if (A->isFunctionType() && S.IsFunctionConversion(A, DeducedA, Tmp))
3506
3507 Qualifiers AQuals = A.getQualifiers();
3508 Qualifiers DeducedAQuals = DeducedA.getQualifiers();
3509
3510 // Under Objective-C++ ARC, the deduced type may have implicitly
3511 // been given strong or (when dealing with a const reference)
3512 // unsafe_unretained lifetime. If so, update the original
3513 // qualifiers to include this lifetime.
3514 if (S.getLangOpts().ObjCAutoRefCount &&
3515 ((DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong &&
3517 (DeducedAQuals.hasConst() &&
3518 DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone))) {
3519 AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime());
3520 }
3521
3522 if (AQuals == DeducedAQuals) {
3523 // Qualifiers match; there's nothing to do.
3524 } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) {
3525 return Failed();
3526 } else {
3527 // Qualifiers are compatible, so have the argument type adopt the
3528 // deduced argument type's qualifiers as if we had performed the
3529 // qualification conversion.
3530 A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
3531 }
3532 }
3533
3534 // - The transformed A can be another pointer or pointer to member
3535 // type that can be converted to the deduced A via a function pointer
3536 // conversion and/or a qualification conversion.
3537 //
3538 // Also allow conversions which merely strip __attribute__((noreturn)) from
3539 // function types (recursively).
3540 bool ObjCLifetimeConversion = false;
3541 QualType ResultTy;
3542 if ((A->isAnyPointerType() || A->isMemberPointerType()) &&
3543 (S.IsQualificationConversion(A, DeducedA, false,
3544 ObjCLifetimeConversion) ||
3545 S.IsFunctionConversion(A, DeducedA, ResultTy)))
3547
3548 // - If P is a class and P has the form simple-template-id, then the
3549 // transformed A can be a derived class of the deduced A. [...]
3550 // [...] Likewise, if P is a pointer to a class of the form
3551 // simple-template-id, the transformed A can be a pointer to a
3552 // derived class pointed to by the deduced A.
3553 if (const PointerType *OriginalParamPtr
3554 = OriginalParamType->getAs<PointerType>()) {
3555 if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
3556 if (const PointerType *APtr = A->getAs<PointerType>()) {
3557 if (A->getPointeeType()->isRecordType()) {
3558 OriginalParamType = OriginalParamPtr->getPointeeType();
3559 DeducedA = DeducedAPtr->getPointeeType();
3560 A = APtr->getPointeeType();
3561 }
3562 }
3563 }
3564 }
3565
3566 if (Context.hasSameUnqualifiedType(A, DeducedA))
3568
3569 if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) &&
3570 S.IsDerivedFrom(Info.getLocation(), A, DeducedA))
3572
3573 return Failed();
3574}
3575
3576/// Find the pack index for a particular parameter index in an instantiation of
3577/// a function template with specific arguments.
3578///
3579/// \return The pack index for whichever pack produced this parameter, or -1
3580/// if this was not produced by a parameter. Intended to be used as the
3581/// ArgumentPackSubstitutionIndex for further substitutions.
3582// FIXME: We should track this in OriginalCallArgs so we don't need to
3583// reconstruct it here.
3584static unsigned getPackIndexForParam(Sema &S,
3585 FunctionTemplateDecl *FunctionTemplate,
3587 unsigned ParamIdx) {
3588 unsigned Idx = 0;
3589 for (auto *PD : FunctionTemplate->getTemplatedDecl()->parameters()) {
3590 if (PD->isParameterPack()) {
3591 unsigned NumExpansions =
3592 S.getNumArgumentsInExpansion(PD->getType(), Args).value_or(1);
3593 if (Idx + NumExpansions > ParamIdx)
3594 return ParamIdx - Idx;
3595 Idx += NumExpansions;
3596 } else {
3597 if (Idx == ParamIdx)
3598 return -1; // Not a pack expansion
3599 ++Idx;
3600 }
3601 }
3602
3603 llvm_unreachable("parameter index would not be produced from template");
3604}
3605
3606// if `Specialization` is a `CXXConstructorDecl` or `CXXConversionDecl`,
3607// we'll try to instantiate and update its explicit specifier after constraint
3608// checking.
3611 const MultiLevelTemplateArgumentList &SubstArgs,
3612 TemplateDeductionInfo &Info, FunctionTemplateDecl *FunctionTemplate,
3613 ArrayRef<TemplateArgument> DeducedArgs) {
3614 auto GetExplicitSpecifier = [](FunctionDecl *D) {
3615 return isa<CXXConstructorDecl>(D)
3616 ? cast<CXXConstructorDecl>(D)->getExplicitSpecifier()
3617 : cast<CXXConversionDecl>(D)->getExplicitSpecifier();
3618 };
3619 auto SetExplicitSpecifier = [](FunctionDecl *D, ExplicitSpecifier ES) {
3620 isa<CXXConstructorDecl>(D)
3621 ? cast<CXXConstructorDecl>(D)->setExplicitSpecifier(ES)
3622 : cast<CXXConversionDecl>(D)->setExplicitSpecifier(ES);
3623 };
3624
3625 ExplicitSpecifier ES = GetExplicitSpecifier(Specialization);
3626 Expr *ExplicitExpr = ES.getExpr();
3627 if (!ExplicitExpr)
3629 if (!ExplicitExpr->isValueDependent())
3631
3633 S, Info.getLocation(), FunctionTemplate, DeducedArgs,
3635 if (Inst.isInvalid())
3637 Sema::SFINAETrap Trap(S);
3638 const ExplicitSpecifier InstantiatedES =
3639 S.instantiateExplicitSpecifier(SubstArgs, ES);
3640 if (InstantiatedES.isInvalid() || Trap.hasErrorOccurred()) {
3641 Specialization->setInvalidDecl(true);
3643 }
3644 SetExplicitSpecifier(Specialization, InstantiatedES);
3646}
3647
3648/// Finish template argument deduction for a function template,
3649/// checking the deduced template arguments for completeness and forming
3650/// the function template specialization.
3651///
3652/// \param OriginalCallArgs If non-NULL, the original call arguments against
3653/// which the deduced argument types should be compared.
3655 FunctionTemplateDecl *FunctionTemplate,
3657 unsigned NumExplicitlySpecified, FunctionDecl *&Specialization,
3659 SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs,
3660 bool PartialOverloading, llvm::function_ref<bool()> CheckNonDependent) {
3661 // Unevaluated SFINAE context.
3664 SFINAETrap Trap(*this);
3665
3666 // Enter a new template instantiation context while we instantiate the
3667 // actual function declaration.
3668 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3670 *this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3672 if (Inst.isInvalid())
3674
3675 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3676
3677 // C++ [temp.deduct.type]p2:
3678 // [...] or if any template argument remains neither deduced nor
3679 // explicitly specified, template argument deduction fails.
3680 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
3682 *this, FunctionTemplate, /*IsDeduced*/ true, Deduced, Info,
3683 SugaredBuilder, CanonicalBuilder, CurrentInstantiationScope,
3684 NumExplicitlySpecified, PartialOverloading);
3686 return Result;
3687
3688 // C++ [temp.deduct.call]p10: [DR1391]
3689 // If deduction succeeds for all parameters that contain
3690 // template-parameters that participate in template argument deduction,
3691 // and all template arguments are explicitly specified, deduced, or
3692 // obtained from default template arguments, remaining parameters are then
3693 // compared with the corresponding arguments. For each remaining parameter
3694 // P with a type that was non-dependent before substitution of any
3695 // explicitly-specified template arguments, if the corresponding argument
3696 // A cannot be implicitly converted to P, deduction fails.
3697 if (CheckNonDependent())
3699
3700 // Form the template argument list from the deduced template arguments.
3701 TemplateArgumentList *SugaredDeducedArgumentList =
3703 TemplateArgumentList *CanonicalDeducedArgumentList =
3704 TemplateArgumentList::CreateCopy(Context, CanonicalBuilder);
3705 Info.reset(SugaredDeducedArgumentList, CanonicalDeducedArgumentList);
3706
3707 // Substitute the deduced template arguments into the function template
3708 // declaration to produce the function template specialization.
3709 DeclContext *Owner = FunctionTemplate->getDeclContext();
3710 if (FunctionTemplate->getFriendObjectKind())
3711 Owner = FunctionTemplate->getLexicalDeclContext();
3712 FunctionDecl *FD = FunctionTemplate->getTemplatedDecl();
3713 // additional check for inline friend,
3714 // ```
3715 // template <class F1> int foo(F1 X);
3716 // template <int A1> struct A {
3717 // template <class F1> friend int foo(F1 X) { return A1; }
3718 // };
3719 // template struct A<1>;
3720 // int a = foo(1.0);
3721 // ```
3722 const FunctionDecl *FDFriend;
3724 FD->isDefined(FDFriend, /*CheckForPendingFriendDefinition*/ true) &&
3726 FD = const_cast<FunctionDecl *>(FDFriend);
3727 Owner = FD->getLexicalDeclContext();
3728 }
3730 FunctionTemplate, CanonicalDeducedArgumentList->asArray(),
3731 /*Final=*/false);
3732 Specialization = cast_or_null<FunctionDecl>(
3733 SubstDecl(FD, Owner, SubstArgs));
3734 if (!Specialization || Specialization->isInvalidDecl())
3736
3737 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
3738 FunctionTemplate->getCanonicalDecl());
3739
3740 // If the template argument list is owned by the function template
3741 // specialization, release it.
3742 if (Specialization->getTemplateSpecializationArgs() ==
3743 CanonicalDeducedArgumentList &&
3744 !Trap.hasErrorOccurred())
3745 Info.takeCanonical();
3746
3747 // There may have been an error that did not prevent us from constructing a
3748 // declaration. Mark the declaration invalid and return with a substitution
3749 // failure.
3750 if (Trap.hasErrorOccurred()) {
3751 Specialization->setInvalidDecl(true);
3753 }
3754
3755 // C++2a [temp.deduct]p5
3756 // [...] When all template arguments have been deduced [...] all uses of
3757 // template parameters [...] are replaced with the corresponding deduced
3758 // or default argument values.
3759 // [...] If the function template has associated constraints
3760 // ([temp.constr.decl]), those constraints are checked for satisfaction
3761 // ([temp.constr.constr]). If the constraints are not satisfied, type
3762 // deduction fails.
3763 if (!PartialOverloading ||
3764 (CanonicalBuilder.size() ==
3765 FunctionTemplate->getTemplateParameters()->size())) {
3767 Info.getLocation(), Specialization, CanonicalBuilder,
3770
3772 Info.reset(Info.takeSugared(),
3773 TemplateArgumentList::CreateCopy(Context, CanonicalBuilder));
3775 }
3776 }
3777
3778 // We skipped the instantiation of the explicit-specifier during the
3779 // substitution of `FD` before. So, we try to instantiate it back if
3780 // `Specialization` is either a constructor or a conversion function.
3781 if (isa<CXXConstructorDecl, CXXConversionDecl>(Specialization)) {
3784 Info, FunctionTemplate,
3785 DeducedArgs)) {
3787 }
3788 }
3789
3790 if (OriginalCallArgs) {
3791 // C++ [temp.deduct.call]p4:
3792 // In general, the deduction process attempts to find template argument
3793 // values that will make the deduced A identical to A (after the type A
3794 // is transformed as described above). [...]
3795 llvm::SmallDenseMap<std::pair<unsigned, QualType>, QualType> DeducedATypes;
3796 for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
3797 OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
3798
3799 auto ParamIdx = OriginalArg.ArgIdx;
3800 unsigned ExplicitOffset =
3801 Specialization->hasCXXExplicitFunctionObjectParameter() ? 1 : 0;
3802 if (ParamIdx >= Specialization->getNumParams() - ExplicitOffset)
3803 // FIXME: This presumably means a pack ended up smaller than we
3804 // expected while deducing. Should this not result in deduction
3805 // failure? Can it even happen?
3806 continue;
3807
3808 QualType DeducedA;
3809 if (!OriginalArg.DecomposedParam) {
3810 // P is one of the function parameters, just look up its substituted
3811 // type.
3812 DeducedA =
3813 Specialization->getParamDecl(ParamIdx + ExplicitOffset)->getType();
3814 } else {
3815 // P is a decomposed element of a parameter corresponding to a
3816 // braced-init-list argument. Substitute back into P to find the
3817 // deduced A.
3818 QualType &CacheEntry =
3819 DeducedATypes[{ParamIdx, OriginalArg.OriginalParamType}];
3820 if (CacheEntry.isNull()) {
3822 *this, getPackIndexForParam(*this, FunctionTemplate, SubstArgs,
3823 ParamIdx));
3824 CacheEntry =
3825 SubstType(OriginalArg.OriginalParamType, SubstArgs,
3826 Specialization->getTypeSpecStartLoc(),
3827 Specialization->getDeclName());
3828 }
3829 DeducedA = CacheEntry;
3830 }
3831
3832 if (auto TDK =
3833 CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA);
3835 return TDK;
3836 }
3837 }
3838
3839 // If we suppressed any diagnostics while performing template argument
3840 // deduction, and if we haven't already instantiated this declaration,
3841 // keep track of these diagnostics. They'll be emitted if this specialization
3842 // is actually used.
3843 if (Info.diag_begin() != Info.diag_end()) {
3844 SuppressedDiagnosticsMap::iterator
3845 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
3846 if (Pos == SuppressedDiagnostics.end())
3847 SuppressedDiagnostics[Specialization->getCanonicalDecl()]
3848 .append(Info.diag_begin(), Info.diag_end());
3849 }
3850
3852}
3853
3854/// Gets the type of a function for template-argument-deducton
3855/// purposes when it's considered as part of an overload set.
3857 FunctionDecl *Fn) {
3858 // We may need to deduce the return type of the function now.
3859 if (S.getLangOpts().CPlusPlus14 && Fn->getReturnType()->isUndeducedType() &&
3860 S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/ false))
3861 return {};
3862
3863 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
3864 if (Method->isImplicitObjectMemberFunction()) {
3865 // An instance method that's referenced in a form that doesn't
3866 // look like a member pointer is just invalid.
3868 return {};
3869
3870 return S.Context.getMemberPointerType(Fn->getType(),
3871 S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
3872 }
3873
3874 if (!R.IsAddressOfOperand) return Fn->getType();
3875 return S.Context.getPointerType(Fn->getType());
3876}
3877
3878/// Apply the deduction rules for overload sets.
3879///
3880/// \return the null type if this argument should be treated as an
3881/// undeduced context
3882static QualType
3884 Expr *Arg, QualType ParamType,
3885 bool ParamWasReference,
3886 TemplateSpecCandidateSet *FailedTSC = nullptr) {
3887
3889
3890 OverloadExpr *Ovl = R.Expression;
3891
3892 // C++0x [temp.deduct.call]p4
3893 unsigned TDF = 0;
3894 if (ParamWasReference)
3896 if (R.IsAddressOfOperand)
3897 TDF |= TDF_IgnoreQualifiers;
3898
3899 // C++0x [temp.deduct.call]p6:
3900 // When P is a function type, pointer to function type, or pointer
3901 // to member function type:
3902
3903 if (!ParamType->isFunctionType() &&
3904 !ParamType->isFunctionPointerType() &&
3905 !ParamType->isMemberFunctionPointerType()) {
3906 if (Ovl->hasExplicitTemplateArgs()) {
3907 // But we can still look for an explicit specialization.
3908 if (FunctionDecl *ExplicitSpec =
3910 Ovl, /*Complain=*/false,
3911 /*FoundDeclAccessPair=*/nullptr, FailedTSC))
3912 return GetTypeOfFunction(S, R, ExplicitSpec);
3913 }
3914
3915 DeclAccessPair DAP;
3916 if (FunctionDecl *Viable =
3918 return GetTypeOfFunction(S, R, Viable);
3919
3920 return {};
3921 }
3922
3923 // Gather the explicit template arguments, if any.
3924 TemplateArgumentListInfo ExplicitTemplateArgs;
3925 if (Ovl->hasExplicitTemplateArgs())
3926 Ovl->copyTemplateArgumentsInto(ExplicitTemplateArgs);
3927 QualType Match;
3928 for (UnresolvedSetIterator I = Ovl->decls_begin(),
3929 E = Ovl->decls_end(); I != E; ++I) {
3930 NamedDecl *D = (*I)->getUnderlyingDecl();
3931
3932 if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
3933 // - If the argument is an overload set containing one or more
3934 // function templates, the parameter is treated as a
3935 // non-deduced context.
3936 if (!Ovl->hasExplicitTemplateArgs())
3937 return {};
3938
3939 // Otherwise, see if we can resolve a function type
3940 FunctionDecl *Specialization = nullptr;
3941 TemplateDeductionInfo Info(Ovl->getNameLoc());
3942 if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
3945 continue;
3946
3947 D = Specialization;
3948 }
3949
3950 FunctionDecl *Fn = cast<FunctionDecl>(D);
3951 QualType ArgType = GetTypeOfFunction(S, R, Fn);
3952 if (ArgType.isNull()) continue;
3953
3954 // Function-to-pointer conversion.
3955 if (!ParamWasReference && ParamType->isPointerType() &&
3956 ArgType->isFunctionType())
3957 ArgType = S.Context.getPointerType(ArgType);
3958
3959 // - If the argument is an overload set (not containing function
3960 // templates), trial argument deduction is attempted using each
3961 // of the members of the set. If deduction succeeds for only one
3962 // of the overload set members, that member is used as the
3963 // argument value for the deduction. If deduction succeeds for
3964 // more than one member of the overload set the parameter is
3965 // treated as a non-deduced context.
3966
3967 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
3968 // Type deduction is done independently for each P/A pair, and
3969 // the deduced template argument values are then combined.
3970 // So we do not reject deductions which were made elsewhere.
3972 Deduced(TemplateParams->size());
3973 TemplateDeductionInfo Info(Ovl->getNameLoc());
3975 S, TemplateParams, ParamType, ArgType, Info, Deduced, TDF);
3977 continue;
3978 if (!Match.isNull())
3979 return {};
3980 Match = ArgType;
3981 }
3982
3983 return Match;
3984}
3985
3986/// Perform the adjustments to the parameter and argument types
3987/// described in C++ [temp.deduct.call].
3988///
3989/// \returns true if the caller should not attempt to perform any template
3990/// argument deduction based on this P/A pair because the argument is an
3991/// overloaded function set that could not be resolved.
3993 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3994 QualType &ParamType, QualType &ArgType,
3995 Expr::Classification ArgClassification, Expr *Arg, unsigned &TDF,
3996 TemplateSpecCandidateSet *FailedTSC = nullptr) {
3997 // C++0x [temp.deduct.call]p3:
3998 // If P is a cv-qualified type, the top level cv-qualifiers of P's type
3999 // are ignored for type deduction.
4000 if (ParamType.hasQualifiers())
4001 ParamType = ParamType.getUnqualifiedType();
4002
4003 // [...] If P is a reference type, the type referred to by P is
4004 // used for type deduction.
4005 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
4006 if (ParamRefType)
4007 ParamType = ParamRefType->getPointeeType();
4008
4009 // Overload sets usually make this parameter an undeduced context,
4010 // but there are sometimes special circumstances. Typically
4011 // involving a template-id-expr.
4012 if (ArgType == S.Context.OverloadTy) {
4013 assert(Arg && "expected a non-null arg expression");
4014 ArgType = ResolveOverloadForDeduction(S, TemplateParams, Arg, ParamType,
4015 ParamRefType != nullptr, FailedTSC);
4016 if (ArgType.isNull())
4017 return true;
4018 }
4019
4020 if (ParamRefType) {
4021 // If the argument has incomplete array type, try to complete its type.
4022 if (ArgType->isIncompleteArrayType()) {
4023 assert(Arg && "expected a non-null arg expression");
4024 ArgType = S.getCompletedType(Arg);
4025 }
4026
4027 // C++1z [temp.deduct.call]p3:
4028 // If P is a forwarding reference and the argument is an lvalue, the type
4029 // "lvalue reference to A" is used in place of A for type deduction.
4030 if (isForwardingReference(QualType(ParamRefType, 0), FirstInnerIndex) &&
4031 ArgClassification.isLValue()) {
4032 if (S.getLangOpts().OpenCL && !ArgType.hasAddressSpace())
4033 ArgType = S.Context.getAddrSpaceQualType(
4035 ArgType = S.Context.getLValueReferenceType(ArgType);
4036 }
4037 } else {
4038 // C++ [temp.deduct.call]p2:
4039 // If P is not a reference type:
4040 // - If A is an array type, the pointer type produced by the
4041 // array-to-pointer standard conversion (4.2) is used in place of
4042 // A for type deduction; otherwise,
4043 // - If A is a function type, the pointer type produced by the
4044 // function-to-pointer standard conversion (4.3) is used in place
4045 // of A for type deduction; otherwise,
4046 if (ArgType->canDecayToPointerType())
4047 ArgType = S.Context.getDecayedType(ArgType);
4048 else {
4049 // - If A is a cv-qualified type, the top level cv-qualifiers of A's
4050 // type are ignored for type deduction.
4051 ArgType = ArgType.getUnqualifiedType();
4052 }
4053 }
4054
4055 // C++0x [temp.deduct.call]p4:
4056 // In general, the deduction process attempts to find template argument
4057 // values that will make the deduced A identical to A (after the type A
4058 // is transformed as described above). [...]
4060
4061 // - If the original P is a reference type, the deduced A (i.e., the
4062 // type referred to by the reference) can be more cv-qualified than
4063 // the transformed A.
4064 if (ParamRefType)
4066 // - The transformed A can be another pointer or pointer to member
4067 // type that can be converted to the deduced A via a qualification
4068 // conversion (4.4).
4069 if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
4070 ArgType->isObjCObjectPointerType())
4071 TDF |= TDF_IgnoreQualifiers;
4072 // - If P is a class and P has the form simple-template-id, then the
4073 // transformed A can be a derived class of the deduced A. Likewise,
4074 // if P is a pointer to a class of the form simple-template-id, the
4075 // transformed A can be a pointer to a derived class pointed to by
4076 // the deduced A.
4077 if (isSimpleTemplateIdType(ParamType) ||
4078 (isa<PointerType>(ParamType) &&
4080 ParamType->castAs<PointerType>()->getPointeeType())))
4081 TDF |= TDF_DerivedClass;
4082
4083 return false;
4084}
4085
4086static bool
4088 QualType T);
4089
4091 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
4092 QualType ParamType, QualType ArgType,
4093 Expr::Classification ArgClassification, Expr *Arg,
4097 bool DecomposedParam, unsigned ArgIdx, unsigned TDF,
4098 TemplateSpecCandidateSet *FailedTSC = nullptr);
4099
4100/// Attempt template argument deduction from an initializer list
4101/// deemed to be an argument in a function call.
4103 Sema &S, TemplateParameterList *TemplateParams, QualType AdjustedParamType,
4106 SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs, unsigned ArgIdx,
4107 unsigned TDF) {
4108 // C++ [temp.deduct.call]p1: (CWG 1591)
4109 // If removing references and cv-qualifiers from P gives
4110 // std::initializer_list<P0> or P0[N] for some P0 and N and the argument is
4111 // a non-empty initializer list, then deduction is performed instead for
4112 // each element of the initializer list, taking P0 as a function template
4113 // parameter type and the initializer element as its argument
4114 //
4115 // We've already removed references and cv-qualifiers here.
4116 if (!ILE->getNumInits())
4118
4119 QualType ElTy;
4120 auto *ArrTy = S.Context.getAsArrayType(AdjustedParamType);
4121 if (ArrTy)
4122 ElTy = ArrTy->getElementType();
4123 else if (!S.isStdInitializerList(AdjustedParamType, &ElTy)) {
4124 // Otherwise, an initializer list argument causes the parameter to be
4125 // considered a non-deduced context
4127 }
4128
4129 // Resolving a core issue: a braced-init-list containing any designators is
4130 // a non-deduced context.
4131 for (Expr *E : ILE->inits())
4132 if (isa<DesignatedInitExpr>(E))
4134
4135 // Deduction only needs to be done for dependent types.
4136 if (ElTy->isDependentType()) {
4137 for (Expr *E : ILE->inits()) {
4139 S, TemplateParams, 0, ElTy, E->getType(),
4140 E->Classify(S.getASTContext()), E, Info, Deduced,
4141 OriginalCallArgs, true, ArgIdx, TDF);
4143 return Result;
4144 }
4145 }
4146
4147 // in the P0[N] case, if N is a non-type template parameter, N is deduced
4148 // from the length of the initializer list.
4149 if (auto *DependentArrTy = dyn_cast_or_null<DependentSizedArrayType>(ArrTy)) {
4150 // Determine the array bound is something we can deduce.
4151 if (const NonTypeTemplateParmDecl *NTTP =
4152 getDeducedParameterFromExpr(Info, DependentArrTy->getSizeExpr())) {
4153 // We can perform template argument deduction for the given non-type
4154 // template parameter.
4155 // C++ [temp.deduct.type]p13:
4156 // The type of N in the type T[N] is std::size_t.
4158 llvm::APInt Size(S.Context.getIntWidth(T), ILE->getNumInits());
4160 S, TemplateParams, NTTP, llvm::APSInt(Size), T,
4161 /*ArrayBound=*/true, Info, Deduced);
4163 return Result;
4164 }
4165 }
4166
4168}
4169
4170/// Perform template argument deduction per [temp.deduct.call] for a
4171/// single parameter / argument pair.
4173 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
4174 QualType ParamType, QualType ArgType,
4175 Expr::Classification ArgClassification, Expr *Arg,
4179 bool DecomposedParam, unsigned ArgIdx, unsigned TDF,
4180 TemplateSpecCandidateSet *FailedTSC) {
4181
4182 QualType OrigParamType = ParamType;
4183
4184 // If P is a reference type [...]
4185 // If P is a cv-qualified type [...]
4187 S, TemplateParams, FirstInnerIndex, ParamType, ArgType,
4188 ArgClassification, Arg, TDF, FailedTSC))
4190
4191 // If [...] the argument is a non-empty initializer list [...]
4192 if (InitListExpr *ILE = dyn_cast_if_present<InitListExpr>(Arg))
4193 return DeduceFromInitializerList(S, TemplateParams, ParamType, ILE, Info,
4194 Deduced, OriginalCallArgs, ArgIdx, TDF);
4195
4196 // [...] the deduction process attempts to find template argument values
4197 // that will make the deduced A identical to A
4198 //
4199 // Keep track of the argument type and corresponding parameter index,
4200 // so we can check for compatibility between the deduced A and A.
4201 if (Arg)
4202 OriginalCallArgs.push_back(
4203 Sema::OriginalCallArg(OrigParamType, DecomposedParam, ArgIdx, ArgType));
4204 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
4205 ArgType, Info, Deduced, TDF);
4206}
4207
4208/// Perform template argument deduction from a function call
4209/// (C++ [temp.deduct.call]).
4210///
4211/// \param FunctionTemplate the function template for which we are performing
4212/// template argument deduction.
4213///
4214/// \param ExplicitTemplateArgs the explicit template arguments provided
4215/// for this call.
4216///
4217/// \param Args the function call arguments
4218///
4219/// \param Specialization if template argument deduction was successful,
4220/// this will be set to the function template specialization produced by
4221/// template argument deduction.
4222///
4223/// \param Info the argument will be updated to provide additional information
4224/// about template argument deduction.
4225///
4226/// \param CheckNonDependent A callback to invoke to check conversions for
4227/// non-dependent parameters, between deduction and substitution, per DR1391.
4228/// If this returns true, substitution will be skipped and we return
4229/// TemplateDeductionResult::NonDependentConversionFailure. The callback is
4230/// passed the parameter types (after substituting explicit template arguments).
4231///
4232/// \returns the result of template argument deduction.
4234 FunctionTemplateDecl *FunctionTemplate,
4235 TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args,
4237 bool PartialOverloading, bool AggregateDeductionCandidate,
4238 QualType ObjectType, Expr::Classification ObjectClassification,
4239 llvm::function_ref<bool(ArrayRef<QualType>)> CheckNonDependent) {
4240 if (FunctionTemplate->isInvalidDecl())
4242
4243 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4244 unsigned NumParams = Function->getNumParams();
4245 bool HasExplicitObject = false;
4246 int ExplicitObjectOffset = 0;
4247 if (Function->hasCXXExplicitFunctionObjectParameter()) {
4248 HasExplicitObject = true;
4249 ExplicitObjectOffset = 1;
4250 }
4251
4252 unsigned FirstInnerIndex = getFirstInnerIndex(FunctionTemplate);
4253
4254 // C++ [temp.deduct.call]p1:
4255 // Template argument deduction is done by comparing each function template
4256 // parameter type (call it P) with the type of the corresponding argument
4257 // of the call (call it A) as described below.
4258 if (Args.size() < Function->getMinRequiredExplicitArguments() &&
4259 !PartialOverloading)
4261 else if (TooManyArguments(NumParams, Args.size() + ExplicitObjectOffset,
4262 PartialOverloading)) {
4263 const auto *Proto = Function->getType()->castAs<FunctionProtoType>();
4264 if (Proto->isTemplateVariadic())
4265 /* Do nothing */;
4266 else if (!Proto->isVariadic())
4268 }
4269
4270 // The types of the parameters from which we will perform template argument
4271 // deduction.
4272 LocalInstantiationScope InstScope(*this);
4273 TemplateParameterList *TemplateParams
4274 = FunctionTemplate->getTemplateParameters();
4276 SmallVector<QualType, 8> ParamTypes;
4277 unsigned NumExplicitlySpecified = 0;
4278 if (ExplicitTemplateArgs) {
4281 Result = SubstituteExplicitTemplateArguments(
4282 FunctionTemplate, *ExplicitTemplateArgs, Deduced, ParamTypes, nullptr,
4283 Info);
4284 });
4286 return Result;
4287
4288 NumExplicitlySpecified = Deduced.size();
4289 } else {
4290 // Just fill in the parameter types from the function declaration.
4291 for (unsigned I = 0; I != NumParams; ++I)
4292 ParamTypes.push_back(Function->getParamDecl(I)->getType());
4293 }
4294
4295 SmallVector<OriginalCallArg, 8> OriginalCallArgs;
4296
4297 // Deduce an argument of type ParamType from an expression with index ArgIdx.
4298 auto DeduceCallArgument = [&](QualType ParamType, unsigned ArgIdx,
4299 bool ExplicitObjetArgument) {
4300 // C++ [demp.deduct.call]p1: (DR1391)
4301 // Template argument deduction is done by comparing each function template
4302 // parameter that contains template-parameters that participate in
4303 // template argument deduction ...
4304 if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
4306
4307 if (ExplicitObjetArgument) {
4308 // ... with the type of the corresponding argument
4310 *this, TemplateParams, FirstInnerIndex, ParamType, ObjectType,
4311 ObjectClassification,
4312 /*Arg=*/nullptr, Info, Deduced, OriginalCallArgs,
4313 /*Decomposed*/ false, ArgIdx, /*TDF*/ 0);
4314 }
4315
4316 // ... with the type of the corresponding argument
4318 *this, TemplateParams, FirstInnerIndex, ParamType,
4319 Args[ArgIdx]->getType(), Args[ArgIdx]->Classify(getASTContext()),
4320 Args[ArgIdx], Info, Deduced, OriginalCallArgs, /*Decomposed*/ false,
4321 ArgIdx, /*TDF*/ 0);
4322 };
4323
4324 // Deduce template arguments from the function parameters.
4325 Deduced.resize(TemplateParams->size());
4326 SmallVector<QualType, 8> ParamTypesForArgChecking;
4327 for (unsigned ParamIdx = 0, NumParamTypes = ParamTypes.size(), ArgIdx = 0;
4328 ParamIdx != NumParamTypes; ++ParamIdx) {
4329 QualType ParamType = ParamTypes[ParamIdx];
4330
4331 const PackExpansionType *ParamExpansion =
4332 dyn_cast<PackExpansionType>(ParamType);
4333 if (!ParamExpansion) {
4334 // Simple case: matching a function parameter to a function argument.
4335 if (ArgIdx >= Args.size() && !(HasExplicitObject && ParamIdx == 0))
4336 break;
4337
4338 ParamTypesForArgChecking.push_back(ParamType);
4339
4340 if (ParamIdx == 0 && HasExplicitObject) {
4341 if (auto Result = DeduceCallArgument(ParamType, 0,
4342 /*ExplicitObjetArgument=*/true);
4344 return Result;
4345 continue;
4346 }
4347
4348 if (auto Result = DeduceCallArgument(ParamType, ArgIdx++,
4349 /*ExplicitObjetArgument=*/false);
4351 return Result;
4352
4353 continue;
4354 }
4355
4356 bool IsTrailingPack = ParamIdx + 1 == NumParamTypes;
4357
4358 QualType ParamPattern = ParamExpansion->getPattern();
4359 PackDeductionScope PackScope(*this, TemplateParams, Deduced, Info,
4360 ParamPattern,
4361 AggregateDeductionCandidate && IsTrailingPack);
4362
4363 // C++0x [temp.deduct.call]p1:
4364 // For a function parameter pack that occurs at the end of the
4365 // parameter-declaration-list, the type A of each remaining argument of
4366 // the call is compared with the type P of the declarator-id of the
4367 // function parameter pack. Each comparison deduces template arguments
4368 // for subsequent positions in the template parameter packs expanded by
4369 // the function parameter pack. When a function parameter pack appears
4370 // in a non-deduced context [not at the end of the list], the type of
4371 // that parameter pack is never deduced.
4372 //
4373 // FIXME: The above rule allows the size of the parameter pack to change
4374 // after we skip it (in the non-deduced case). That makes no sense, so
4375 // we instead notionally deduce the pack against N arguments, where N is
4376 // the length of the explicitly-specified pack if it's expanded by the
4377 // parameter pack and 0 otherwise, and we treat each deduction as a
4378 // non-deduced context.
4379 if (IsTrailingPack || PackScope.hasFixedArity()) {
4380 for (; ArgIdx < Args.size() && PackScope.hasNextElement();
4381 PackScope.nextPackElement(), ++ArgIdx) {
4382 ParamTypesForArgChecking.push_back(ParamPattern);
4383 if (auto Result = DeduceCallArgument(ParamPattern, ArgIdx,
4384 /*ExplicitObjetArgument=*/false);
4386 return Result;
4387 }
4388 } else {
4389 // If the parameter type contains an explicitly-specified pack that we
4390 // could not expand, skip the number of parameters notionally created
4391 // by the expansion.
4392 std::optional<unsigned> NumExpansions =
4393 ParamExpansion->getNumExpansions();
4394 if (NumExpansions && !PackScope.isPartiallyExpanded()) {
4395 for (unsigned I = 0; I != *NumExpansions && ArgIdx < Args.size();
4396 ++I, ++ArgIdx) {
4397 ParamTypesForArgChecking.push_back(ParamPattern);
4398 // FIXME: Should we add OriginalCallArgs for these? What if the
4399 // corresponding argument is a list?
4400 PackScope.nextPackElement();
4401 }
4402 } else if (!IsTrailingPack && !PackScope.isPartiallyExpanded() &&
4403 PackScope.isDeducedFromEarlierParameter()) {
4404 // [temp.deduct.general#3]
4405 // When all template arguments have been deduced
4406 // or obtained from default template arguments, all uses of template
4407 // parameters in the template parameter list of the template are
4408 // replaced with the corresponding deduced or default argument values
4409 //
4410 // If we have a trailing parameter pack, that has been deduced
4411 // previously we substitute the pack here in a similar fashion as
4412 // above with the trailing parameter packs. The main difference here is
4413 // that, in this case we are not processing all of the remaining
4414 // arguments. We are only process as many arguments as we have in
4415 // the already deduced parameter.
4416 std::optional<unsigned> ArgPosAfterSubstitution =
4417 PackScope.getSavedPackSizeIfAllEqual();
4418 if (!ArgPosAfterSubstitution)
4419 continue;
4420
4421 unsigned PackArgEnd = ArgIdx + *ArgPosAfterSubstitution;
4422 for (; ArgIdx < PackArgEnd && ArgIdx < Args.size(); ArgIdx++) {
4423 ParamTypesForArgChecking.push_back(ParamPattern);
4424 if (auto Result = DeduceCallArgument(ParamPattern, ArgIdx,
4425 /*ExplicitObjetArgument=*/false);
4427 return Result;
4428
4429 PackScope.nextPackElement();
4430 }
4431 }
4432 }
4433
4434 // Build argument packs for each of the parameter packs expanded by this
4435 // pack expansion.
4436 if (auto Result = PackScope.finish();
4438 return Result;
4439 }
4440
4441 // Capture the context in which the function call is made. This is the context
4442 // that is needed when the accessibility of template arguments is checked.
4443 DeclContext *CallingCtx = CurContext;
4444
4447 Result = FinishTemplateArgumentDeduction(
4448 FunctionTemplate, Deduced, NumExplicitlySpecified, Specialization, Info,
4449 &OriginalCallArgs, PartialOverloading, [&, CallingCtx]() {
4450 ContextRAII SavedContext(*this, CallingCtx);
4451 return CheckNonDependent(ParamTypesForArgChecking);
4452 });
4453 });
4454 return Result;
4455}
4456
4459 bool AdjustExceptionSpec) {
4460 if (ArgFunctionType.isNull())
4461 return ArgFunctionType;
4462
4463 const auto *FunctionTypeP = FunctionType->castAs<FunctionProtoType>();
4464 const auto *ArgFunctionTypeP = ArgFunctionType->castAs<FunctionProtoType>();
4465 FunctionProtoType::ExtProtoInfo EPI = ArgFunctionTypeP->getExtProtoInfo();
4466 bool Rebuild = false;
4467
4468 CallingConv CC = FunctionTypeP->getCallConv();
4469 if (EPI.ExtInfo.getCC() != CC) {
4470 EPI.ExtInfo = EPI.ExtInfo.withCallingConv(CC);
4471 Rebuild = true;
4472 }
4473
4474 bool NoReturn = FunctionTypeP->getNoReturnAttr();
4475 if (EPI.ExtInfo.getNoReturn() != NoReturn) {
4476 EPI.ExtInfo = EPI.ExtInfo.withNoReturn(NoReturn);
4477 Rebuild = true;
4478 }
4479
4480 if (AdjustExceptionSpec && (FunctionTypeP->hasExceptionSpec() ||
4481 ArgFunctionTypeP->hasExceptionSpec())) {
4482 EPI.ExceptionSpec = FunctionTypeP->getExtProtoInfo().ExceptionSpec;
4483 Rebuild = true;
4484 }
4485
4486 if (!Rebuild)
4487 return ArgFunctionType;
4488
4489 return Context.getFunctionType(ArgFunctionTypeP->getReturnType(),
4490 ArgFunctionTypeP->getParamTypes(), EPI);
4491}
4492
4493/// Deduce template arguments when taking the address of a function
4494/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
4495/// a template.
4496///
4497/// \param FunctionTemplate the function template for which we are performing
4498/// template argument deduction.
4499///
4500/// \param ExplicitTemplateArgs the explicitly-specified template
4501/// arguments.
4502///
4503/// \param ArgFunctionType the function type that will be used as the
4504/// "argument" type (A) when performing template argument deduction from the
4505/// function template's function type. This type may be NULL, if there is no
4506/// argument type to compare against, in C++0x [temp.arg.explicit]p3.
4507///
4508/// \param Specialization if template argument deduction was successful,
4509/// this will be set to the function template specialization produced by
4510/// template argument deduction.
4511///
4512/// \param Info the argument will be updated to provide additional information
4513/// about template argument deduction.
4514///
4515/// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4516/// the address of a function template per [temp.deduct.funcaddr] and
4517/// [over.over]. If \c false, we are looking up a function template
4518/// specialization based on its signature, per [temp.deduct.decl].
4519///
4520/// \returns the result of template argument deduction.
4522 FunctionTemplateDecl *FunctionTemplate,
4523 TemplateArgumentListInfo *ExplicitTemplateArgs, QualType ArgFunctionType,
4525 bool IsAddressOfFunction) {
4526 if (FunctionTemplate->isInvalidDecl())
4528
4529 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4530 TemplateParameterList *TemplateParams
4531 = FunctionTemplate->getTemplateParameters();
4532 QualType FunctionType = Function->getType();
4533
4534 // Substitute any explicit template arguments.
4535 LocalInstantiationScope InstScope(*this);
4537 unsigned NumExplicitlySpecified = 0;
4538 SmallVector<QualType, 4> ParamTypes;
4539 if (ExplicitTemplateArgs) {
4542 Result = SubstituteExplicitTemplateArguments(
4543 FunctionTemplate, *ExplicitTemplateArgs, Deduced, ParamTypes,
4544 &FunctionType, Info);
4545 });
4547 return Result;
4548
4549 NumExplicitlySpecified = Deduced.size();
4550 }
4551
4552 // When taking the address of a function, we require convertibility of
4553 // the resulting function type. Otherwise, we allow arbitrary mismatches
4554 // of calling convention and noreturn.
4555 if (!IsAddressOfFunction)
4556 ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, FunctionType,
4557 /*AdjustExceptionSpec*/false);
4558
4559 // Unevaluated SFINAE context.
4562 SFINAETrap Trap(*this);
4563
4564 Deduced.resize(TemplateParams->size());
4565
4566 // If the function has a deduced return type, substitute it for a dependent
4567 // type so that we treat it as a non-deduced context in what follows.
4568 bool HasDeducedReturnType = false;
4569 if (getLangOpts().CPlusPlus14 &&
4570 Function->getReturnType()->getContainedAutoType()) {
4572 HasDeducedReturnType = true;
4573 }
4574
4575 if (!ArgFunctionType.isNull() && !FunctionType.isNull()) {
4576 unsigned TDF =
4578 // Deduce template arguments from the function type.
4580 *this, TemplateParams, FunctionType, ArgFunctionType, Info, Deduced,
4581 TDF);
4583 return Result;
4584 }
4585
4588 Result = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
4589 NumExplicitlySpecified,
4590 Specialization, Info);
4591 });
4593 return Result;
4594
4595 // If the function has a deduced return type, deduce it now, so we can check
4596 // that the deduced function type matches the requested type.
4597 if (HasDeducedReturnType && IsAddressOfFunction &&
4598 Specialization->getReturnType()->isUndeducedType() &&
4601
4602 if (IsAddressOfFunction && getLangOpts().CPlusPlus20 &&
4603 Specialization->isImmediateEscalating() &&
4605 Info.getLocation()))
4607
4608 auto *SpecializationFPT =
4609 Specialization->getType()->castAs<FunctionProtoType>();
4610 if (IsAddressOfFunction && getLangOpts().CPlusPlus17 &&
4611 isUnresolvedExceptionSpec(SpecializationFPT->getExceptionSpecType()) &&
4612 !ResolveExceptionSpec(Info.getLocation(), SpecializationFPT))
4614
4615 // Adjust the exception specification of the argument to match the
4616 // substituted and resolved type we just formed. (Calling convention and
4617 // noreturn can't be dependent, so we don't actually need this for them
4618 // right now.)
4619 QualType SpecializationType = Specialization->getType();
4620 if (!IsAddressOfFunction) {
4621 ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, SpecializationType,
4622 /*AdjustExceptionSpec*/true);
4623
4624 // Revert placeholder types in the return type back to undeduced types so
4625 // that the comparison below compares the declared return types.
4626 if (HasDeducedReturnType) {
4627 SpecializationType = SubstAutoType(SpecializationType, QualType());
4628 ArgFunctionType = SubstAutoType(ArgFunctionType, QualType());
4629 }
4630 }
4631
4632 // If the requested function type does not match the actual type of the
4633 // specialization with respect to arguments of compatible pointer to function
4634 // types, template argument deduction fails.
4635 if (!ArgFunctionType.isNull()) {
4636 if (IsAddressOfFunction ? !isSameOrCompatibleFunctionType(
4637 Context.getCanonicalType(SpecializationType),
4638 Context.getCanonicalType(ArgFunctionType))
4640 SpecializationType, ArgFunctionType)) {
4641 Info.FirstArg = TemplateArgument(SpecializationType);
4642 Info.SecondArg = TemplateArgument(ArgFunctionType);
4644 }
4645 }
4646
4648}
4649
4650/// Deduce template arguments for a templated conversion
4651/// function (C++ [temp.deduct.conv]) and, if successful, produce a
4652/// conversion function template specialization.
4654 FunctionTemplateDecl *ConversionTemplate, QualType ObjectType,
4655 Expr::Classification ObjectClassification, QualType ToType,
4657 if (ConversionTemplate->isInvalidDecl())
4659
4660 CXXConversionDecl *ConversionGeneric
4661 = cast<CXXConversionDecl>(ConversionTemplate->getTemplatedDecl());
4662
4663 QualType FromType = ConversionGeneric->getConversionType();
4664
4665 // Canonicalize the types for deduction.
4666 QualType P = Context.getCanonicalType(FromType);
4667 QualType A = Context.getCanonicalType(ToType);
4668
4669 // C++0x [temp.deduct.conv]p2:
4670 // If P is a reference type, the type referred to by P is used for
4671 // type deduction.
4672 if (const ReferenceType *PRef = P->getAs<ReferenceType>())
4673 P = PRef->getPointeeType();
4674
4675 // C++0x [temp.deduct.conv]p4:
4676 // [...] If A is a reference type, the type referred to by A is used
4677 // for type deduction.
4678 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) {
4679 A = ARef->getPointeeType();
4680 // We work around a defect in the standard here: cv-qualifiers are also
4681 // removed from P and A in this case, unless P was a reference type. This
4682 // seems to mostly match what other compilers are doing.
4683 if (!FromType->getAs<ReferenceType>()) {
4684 A = A.getUnqualifiedType();
4685 P = P.getUnqualifiedType();
4686 }
4687
4688 // C++ [temp.deduct.conv]p3:
4689 //
4690 // If A is not a reference type:
4691 } else {
4692 assert(!A->isReferenceType() && "Reference types were handled above");
4693
4694 // - If P is an array type, the pointer type produced by the
4695 // array-to-pointer standard conversion (4.2) is used in place
4696 // of P for type deduction; otherwise,
4697 if (P->isArrayType())
4699 // - If P is a function type, the pointer type produced by the
4700 // function-to-pointer standard conversion (4.3) is used in
4701 // place of P for type deduction; otherwise,
4702 else if (P->isFunctionType())
4704 // - If P is a cv-qualified type, the top level cv-qualifiers of
4705 // P's type are ignored for type deduction.
4706 else
4707 P = P.getUnqualifiedType();
4708
4709 // C++0x [temp.deduct.conv]p4:
4710 // If A is a cv-qualified type, the top level cv-qualifiers of A's
4711 // type are ignored for type deduction. If A is a reference type, the type
4712 // referred to by A is used for type deduction.
4713 A = A.getUnqualifiedType();
4714 }
4715
4716 // Unevaluated SFINAE context.
4719 SFINAETrap Trap(*this);
4720
4721 // C++ [temp.deduct.conv]p1:
4722 // Template argument deduction is done by comparing the return
4723 // type of the template conversion function (call it P) with the
4724 // type that is required as the result of the conversion (call it
4725 // A) as described in 14.8.2.4.
4726 TemplateParameterList *TemplateParams
4727 = ConversionTemplate->getTemplateParameters();
4729 Deduced.resize(TemplateParams->size());
4730
4731 // C++0x [temp.deduct.conv]p4:
4732 // In general, the deduction process attempts to find template
4733 // argument values that will make the deduced A identical to
4734 // A. However, there are two cases that allow a difference:
4735 unsigned TDF = 0;
4736 // - If the original A is a reference type, A can be more
4737 // cv-qualified than the deduced A (i.e., the type referred to
4738 // by the reference)
4739 if (ToType->isReferenceType())
4741 // - The deduced A can be another pointer or pointer to member
4742 // type that can be converted to A via a qualification
4743 // conversion.
4744 //
4745 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
4746 // both P and A are pointers or member pointers. In this case, we
4747 // just ignore cv-qualifiers completely).
4748 if ((P->isPointerType() && A->isPointerType()) ||
4749 (P->isMemberPointerType() && A->isMemberPointerType()))
4750 TDF |= TDF_IgnoreQualifiers;
4751
4753 if (ConversionGeneric->isExplicitObjectMemberFunction()) {
4754 QualType ParamType = ConversionGeneric->getParamDecl(0)->getType();
4757 *this, TemplateParams, getFirstInnerIndex(ConversionTemplate),
4758 ParamType, ObjectType, ObjectClassification,
4759 /*Arg=*/nullptr, Info, Deduced, OriginalCallArgs,
4760 /*Decomposed*/ false, 0, /*TDF*/ 0);
4762 return Result;
4763 }
4764
4766 *this, TemplateParams, P, A, Info, Deduced, TDF);
4768 return Result;
4769
4770 // Create an Instantiation Scope for finalizing the operator.
4771 LocalInstantiationScope InstScope(*this);
4772 // Finish template argument deduction.
4773 FunctionDecl *ConversionSpecialized = nullptr;
4776 Result = FinishTemplateArgumentDeduction(ConversionTemplate, Deduced, 0,
4777 ConversionSpecialized, Info,
4778 &OriginalCallArgs);
4779 });
4780 Specialization = cast_or_null<CXXConversionDecl>(ConversionSpecialized);
4781 return Result;
4782}
4783
4784/// Deduce template arguments for a function template when there is
4785/// nothing to deduce against (C++0x [temp.arg.explicit]p3).
4786///
4787/// \param FunctionTemplate the function template for which we are performing
4788/// template argument deduction.
4789///
4790/// \param ExplicitTemplateArgs the explicitly-specified template
4791/// arguments.
4792///
4793/// \param Specialization if template argument deduction was successful,
4794/// this will be set to the function template specialization produced by
4795/// template argument deduction.
4796///
4797/// \param Info the argument will be updated to provide additional information
4798/// about template argument deduction.
4799///
4800/// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4801/// the address of a function template in a context where we do not have a
4802/// target type, per [over.over]. If \c false, we are looking up a function
4803/// template specialization based on its signature, which only happens when
4804/// deducing a function parameter type from an argument that is a template-id
4805/// naming a function template specialization.
4806///
4807/// \returns the result of template argument deduction.
4810 TemplateArgumentListInfo *ExplicitTemplateArgs,
4813 bool IsAddressOfFunction) {
4814 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
4815 QualType(), Specialization, Info,
4816 IsAddressOfFunction);
4817}
4818
4819namespace {
4820 struct DependentAuto { bool IsPack; };
4821
4822 /// Substitute the 'auto' specifier or deduced template specialization type
4823 /// specifier within a type for a given replacement type.
4824 class SubstituteDeducedTypeTransform :
4825 public TreeTransform<SubstituteDeducedTypeTransform> {
4826 QualType Replacement;
4827 bool ReplacementIsPack;
4828 bool UseTypeSugar;
4830
4831 public:
4832 SubstituteDeducedTypeTransform(Sema &SemaRef, DependentAuto DA)
4833 : TreeTransform<SubstituteDeducedTypeTransform>(SemaRef),
4834 ReplacementIsPack(DA.IsPack), UseTypeSugar(true) {}
4835
4836 SubstituteDeducedTypeTransform(Sema &SemaRef, QualType Replacement,
4837 bool UseTypeSugar = true)
4838 : TreeTransform<SubstituteDeducedTypeTransform>(SemaRef),
4839 Replacement(Replacement), ReplacementIsPack(false),
4840 UseTypeSugar(UseTypeSugar) {}
4841
4842 QualType TransformDesugared(TypeLocBuilder &TLB, DeducedTypeLoc TL) {
4843 assert(isa<TemplateTypeParmType>(Replacement) &&
4844 "unexpected unsugared replacement kind");
4845 QualType Result = Replacement;
4847 NewTL.setNameLoc(TL.getNameLoc());
4848 return Result;
4849 }
4850
4851 QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
4852 // If we're building the type pattern to deduce against, don't wrap the
4853 // substituted type in an AutoType. Certain template deduction rules
4854 // apply only when a template type parameter appears directly (and not if
4855 // the parameter is found through desugaring). For instance:
4856 // auto &&lref = lvalue;
4857 // must transform into "rvalue reference to T" not "rvalue reference to
4858 // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
4859 //
4860 // FIXME: Is this still necessary?
4861 if (!UseTypeSugar)
4862 return TransformDesugared(TLB, TL);
4863
4864 QualType Result = SemaRef.Context.getAutoType(
4865 Replacement, TL.getTypePtr()->getKeyword(), Replacement.isNull(),
4866 ReplacementIsPack, TL.getTypePtr()->getTypeConstraintConcept(),
4868 auto NewTL = TLB.push<AutoTypeLoc>(Result);
4869 NewTL.copy(TL);
4870 return Result;
4871 }
4872
4873 QualType TransformDeducedTemplateSpecializationType(
4875 if (!UseTypeSugar)
4876 return TransformDesugared(TLB, TL);
4877
4878 QualType Result = SemaRef.Context.getDeducedTemplateSpecializationType(
4880 Replacement, Replacement.isNull());
4881 auto NewTL = TLB.push<DeducedTemplateSpecializationTypeLoc>(Result);
4882 NewTL.setNameLoc(TL.getNameLoc());
4883 return Result;
4884 }
4885
4886 ExprResult TransformLambdaExpr(LambdaExpr *E) {
4887 // Lambdas never need to be transformed.
4888 return E;
4889 }
4890 bool TransformExceptionSpec(SourceLocation Loc,
4892 SmallVectorImpl<QualType> &Exceptions,
4893 bool &Changed) {
4894 if (ESI.Type == EST_Uninstantiated) {
4895 ESI.instantiate();
4896 Changed = true;
4897 }
4898 return inherited::TransformExceptionSpec(Loc, ESI, Exceptions, Changed);
4899 }
4900
4901 QualType Apply(TypeLoc TL) {
4902 // Create some scratch storage for the transformed type locations.
4903 // FIXME: We're just going to throw this information away. Don't build it.
4904 TypeLocBuilder TLB;
4905 TLB.reserve(TL.getFullDataSize());
4906 return TransformType(TLB, TL);
4907 }
4908 };
4909
4910} // namespace
4911
4914 QualType Deduced) {
4915 ConstraintSatisfaction Satisfaction;
4916 ConceptDecl *Concept = Type.getTypeConstraintConcept();
4917 TemplateArgumentListInfo TemplateArgs(TypeLoc.getLAngleLoc(),
4918 TypeLoc.getRAngleLoc());
4919 TemplateArgs.addArgument(
4922 Deduced, TypeLoc.getNameLoc())));
4923 for (unsigned I = 0, C = TypeLoc.getNumArgs(); I != C; ++I)
4924 TemplateArgs.addArgument(TypeLoc.getArgLoc(I));
4925
4926 llvm::SmallVector<TemplateArgument, 4> SugaredConverted, CanonicalConverted;
4927 if (S.CheckTemplateArgumentList(Concept, SourceLocation(), TemplateArgs,
4928 /*PartialTemplateArgs=*/false,
4929 SugaredConverted, CanonicalConverted))
4930 return true;
4931 MultiLevelTemplateArgumentList MLTAL(Concept, CanonicalConverted,
4932 /*Final=*/false);
4933 if (S.CheckConstraintSatisfaction(Concept, {Concept->getConstraintExpr()},
4935 Satisfaction))
4936 return true;
4937 if (!Satisfaction.IsSatisfied) {
4938</