clang 18.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
273 Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
274 return X;
275
276 // All other combinations are incompatible.
278
281 Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
283 return X;
284
285 // All other combinations are incompatible.
287
290 return checkDeducedTemplateArguments(Context, Y, X);
291
292 // Compare the expressions for equality
293 llvm::FoldingSetNodeID ID1, ID2;
294 X.getAsExpr()->Profile(ID1, Context, true);
295 Y.getAsExpr()->Profile(ID2, Context, true);
296 if (ID1 == ID2)
297 return X.wasDeducedFromArrayBound() ? Y : X;
298
299 // Differing dependent expressions are incompatible.
301 }
302
304 assert(!X.wasDeducedFromArrayBound());
305
306 // If we deduced a declaration and a dependent expression, keep the
307 // declaration.
309 return X;
310
311 // If we deduced a declaration and an integral constant, keep the
312 // integral constant and whichever type did not come from an array
313 // bound.
316 return TemplateArgument(Context, Y.getAsIntegral(),
317 X.getParamTypeForDecl());
318 return Y;
319 }
320
321 // If we deduced two declarations, make sure that they refer to the
322 // same declaration.
324 isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))
325 return X;
326
327 // All other combinations are incompatible.
329
331 // If we deduced a null pointer and a dependent expression, keep the
332 // null pointer.
335 X.getNullPtrType(), Y.getAsExpr()->getType()),
336 true);
337
338 // If we deduced a null pointer and an integral constant, keep the
339 // integral constant.
341 return Y;
342
343 // If we deduced two null pointers, they are the same.
345 return TemplateArgument(
346 Context.getCommonSugaredType(X.getNullPtrType(), Y.getNullPtrType()),
347 true);
348
349 // All other combinations are incompatible.
351
353 if (Y.getKind() != TemplateArgument::Pack ||
354 (!AggregateCandidateDeduction && X.pack_size() != Y.pack_size()))
356
359 XA = X.pack_begin(),
360 XAEnd = X.pack_end(), YA = Y.pack_begin(), YAEnd = Y.pack_end();
361 XA != XAEnd; ++XA, ++YA) {
362 if (YA != YAEnd) {
364 Context, DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
366 if (Merged.isNull() && !(XA->isNull() && YA->isNull()))
368 NewPack.push_back(Merged);
369 } else {
370 NewPack.push_back(*XA);
371 }
372 }
373
375 TemplateArgument::CreatePackCopy(Context, NewPack),
376 X.wasDeducedFromArrayBound() && Y.wasDeducedFromArrayBound());
377 }
378 }
379
380 llvm_unreachable("Invalid TemplateArgument Kind!");
381}
382
383/// Deduce the value of the given non-type template parameter
384/// as the given deduced template argument. All non-type template parameter
385/// deduction is funneled through here.
387 Sema &S, TemplateParameterList *TemplateParams,
388 const NonTypeTemplateParmDecl *NTTP, const DeducedTemplateArgument &NewDeduced,
389 QualType ValueType, TemplateDeductionInfo &Info,
391 assert(NTTP->getDepth() == Info.getDeducedDepth() &&
392 "deducing non-type template argument with wrong depth");
393
395 S.Context, Deduced[NTTP->getIndex()], NewDeduced);
396 if (Result.isNull()) {
397 Info.Param = const_cast<NonTypeTemplateParmDecl*>(NTTP);
398 Info.FirstArg = Deduced[NTTP->getIndex()];
399 Info.SecondArg = NewDeduced;
401 }
402
403 Deduced[NTTP->getIndex()] = Result;
404 if (!S.getLangOpts().CPlusPlus17)
405 return Sema::TDK_Success;
406
407 if (NTTP->isExpandedParameterPack())
408 // FIXME: We may still need to deduce parts of the type here! But we
409 // don't have any way to find which slice of the type to use, and the
410 // type stored on the NTTP itself is nonsense. Perhaps the type of an
411 // expanded NTTP should be a pack expansion type?
412 return Sema::TDK_Success;
413
414 // Get the type of the parameter for deduction. If it's a (dependent) array
415 // or function type, we will not have decayed it yet, so do that now.
416 QualType ParamType = S.Context.getAdjustedParameterType(NTTP->getType());
417 if (auto *Expansion = dyn_cast<PackExpansionType>(ParamType))
418 ParamType = Expansion->getPattern();
419
420 // FIXME: It's not clear how deduction of a parameter of reference
421 // type from an argument (of non-reference type) should be performed.
422 // For now, we just remove reference types from both sides and let
423 // the final check for matching types sort out the mess.
424 ValueType = ValueType.getNonReferenceType();
425 if (ParamType->isReferenceType())
426 ParamType = ParamType.getNonReferenceType();
427 else
428 // Top-level cv-qualifiers are irrelevant for a non-reference type.
429 ValueType = ValueType.getUnqualifiedType();
430
432 S, TemplateParams, ParamType, ValueType, Info, Deduced,
433 TDF_SkipNonDependent, /*PartialOrdering=*/false,
434 /*ArrayBound=*/NewDeduced.wasDeducedFromArrayBound());
435}
436
437/// Deduce the value of the given non-type template parameter
438/// from the given integral constant.
440 Sema &S, TemplateParameterList *TemplateParams,
441 const NonTypeTemplateParmDecl *NTTP, const llvm::APSInt &Value,
442 QualType ValueType, bool DeducedFromArrayBound, TemplateDeductionInfo &Info,
445 S, TemplateParams, NTTP,
447 DeducedFromArrayBound),
448 ValueType, Info, Deduced);
449}
450
451/// Deduce the value of the given non-type template parameter
452/// from the given null pointer template argument type.
454 Sema &S, TemplateParameterList *TemplateParams,
455 const NonTypeTemplateParmDecl *NTTP, QualType NullPtrType,
460 NTTP->getLocation()),
461 NullPtrType,
462 NullPtrType->isMemberPointerType() ? CK_NullToMemberPointer
463 : CK_NullToPointer)
464 .get();
465 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
467 Value->getType(), Info, Deduced);
468}
469
470/// Deduce the value of the given non-type template parameter
471/// from the given type- or value-dependent expression.
472///
473/// \returns true if deduction succeeded, false otherwise.
475 Sema &S, TemplateParameterList *TemplateParams,
478 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
480 Value->getType(), Info, Deduced);
481}
482
483/// Deduce the value of the given non-type template parameter
484/// from the given declaration.
485///
486/// \returns true if deduction succeeded, false otherwise.
488 Sema &S, TemplateParameterList *TemplateParams,
489 const NonTypeTemplateParmDecl *NTTP, ValueDecl *D, QualType T,
492 D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : nullptr;
493 TemplateArgument New(D, T);
495 S, TemplateParams, NTTP, DeducedTemplateArgument(New), T, Info, Deduced);
496}
497
500 TemplateParameterList *TemplateParams,
501 TemplateName Param,
502 TemplateName Arg,
505 TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
506 if (!ParamDecl) {
507 // The parameter type is dependent and is not a template template parameter,
508 // so there is nothing that we can deduce.
509 return Sema::TDK_Success;
510 }
511
512 if (TemplateTemplateParmDecl *TempParam
513 = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
514 // If we're not deducing at this depth, there's nothing to deduce.
515 if (TempParam->getDepth() != Info.getDeducedDepth())
516 return Sema::TDK_Success;
517
520 Deduced[TempParam->getIndex()],
521 NewDeduced);
522 if (Result.isNull()) {
523 Info.Param = TempParam;
524 Info.FirstArg = Deduced[TempParam->getIndex()];
525 Info.SecondArg = NewDeduced;
527 }
528
529 Deduced[TempParam->getIndex()] = Result;
530 return Sema::TDK_Success;
531 }
532
533 // Verify that the two template names are equivalent.
534 if (S.Context.hasSameTemplateName(Param, Arg))
535 return Sema::TDK_Success;
536
537 // Mismatch of non-dependent template parameter to argument.
538 Info.FirstArg = TemplateArgument(Param);
539 Info.SecondArg = TemplateArgument(Arg);
541}
542
543/// Deduce the template arguments by comparing the template parameter
544/// type (which is a template-id) with the template argument type.
545///
546/// \param S the Sema
547///
548/// \param TemplateParams the template parameters that we are deducing
549///
550/// \param P the parameter type
551///
552/// \param A the argument type
553///
554/// \param Info information about the template argument deduction itself
555///
556/// \param Deduced the deduced template arguments
557///
558/// \returns the result of template argument deduction so far. Note that a
559/// "success" result means that template argument deduction has not yet failed,
560/// but it may still fail, later, for other reasons.
563 const QualType P, QualType A,
566 QualType UP = P;
567 if (const auto *IP = P->getAs<InjectedClassNameType>())
568 UP = IP->getInjectedSpecializationType();
569 // FIXME: Try to preserve type sugar here, which is hard
570 // because of the unresolved template arguments.
571 const auto *TP = UP.getCanonicalType()->castAs<TemplateSpecializationType>();
572 TemplateName TNP = TP->getTemplateName();
573
574 // If the parameter is an alias template, there is nothing to deduce.
575 if (const auto *TD = TNP.getAsTemplateDecl(); TD && TD->isTypeAlias())
576 return Sema::TDK_Success;
577
578 ArrayRef<TemplateArgument> PResolved = TP->template_arguments();
579
580 QualType UA = A;
581 // Treat an injected-class-name as its underlying template-id.
582 if (const auto *Injected = A->getAs<InjectedClassNameType>())
583 UA = Injected->getInjectedSpecializationType();
584
585 // Check whether the template argument is a dependent template-id.
586 // FIXME: Should not lose sugar here.
587 if (const auto *SA =
588 dyn_cast<TemplateSpecializationType>(UA.getCanonicalType())) {
589 TemplateName TNA = SA->getTemplateName();
590
591 // If the argument is an alias template, there is nothing to deduce.
592 if (const auto *TD = TNA.getAsTemplateDecl(); TD && TD->isTypeAlias())
593 return Sema::TDK_Success;
594
595 // Perform template argument deduction for the template name.
596 if (auto Result =
597 DeduceTemplateArguments(S, TemplateParams, TNP, TNA, Info, Deduced))
598 return Result;
599 // Perform template argument deduction on each template
600 // argument. Ignore any missing/extra arguments, since they could be
601 // filled in by default arguments.
602 return DeduceTemplateArguments(S, TemplateParams, PResolved,
603 SA->template_arguments(), Info, Deduced,
604 /*NumberOfArgumentsMustMatch=*/false);
605 }
606
607 // If the argument type is a class template specialization, we
608 // perform template argument deduction using its template
609 // arguments.
610 const auto *RA = UA->getAs<RecordType>();
611 const auto *SA =
612 RA ? dyn_cast<ClassTemplateSpecializationDecl>(RA->getDecl()) : nullptr;
613 if (!SA) {
615 Info.SecondArg = TemplateArgument(A);
617 }
618
619 // Perform template argument deduction for the template name.
620 if (auto Result = DeduceTemplateArguments(
621 S, TemplateParams, TP->getTemplateName(),
622 TemplateName(SA->getSpecializedTemplate()), Info, Deduced))
623 return Result;
624
625 // Perform template argument deduction for the template arguments.
626 return DeduceTemplateArguments(S, TemplateParams, PResolved,
627 SA->getTemplateArgs().asArray(), Info, Deduced,
628 /*NumberOfArgumentsMustMatch=*/true);
629}
630
632 assert(T->isCanonicalUnqualified());
633
634 switch (T->getTypeClass()) {
635 case Type::TypeOfExpr:
636 case Type::TypeOf:
637 case Type::DependentName:
638 case Type::Decltype:
639 case Type::UnresolvedUsing:
640 case Type::TemplateTypeParm:
641 return true;
642
643 case Type::ConstantArray:
644 case Type::IncompleteArray:
645 case Type::VariableArray:
646 case Type::DependentSizedArray:
648 cast<ArrayType>(T)->getElementType().getTypePtr());
649
650 default:
651 return false;
652 }
653}
654
655/// Determines whether the given type is an opaque type that
656/// might be more qualified when instantiated.
660}
661
662/// Helper function to build a TemplateParameter when we don't
663/// know its type statically.
665 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
666 return TemplateParameter(TTP);
667 if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
668 return TemplateParameter(NTTP);
669
670 return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
671}
672
673/// A pack that we're currently deducing.
675 // The index of the pack.
676 unsigned Index;
677
678 // The old value of the pack before we started deducing it.
680
681 // A deferred value of this pack from an inner deduction, that couldn't be
682 // deduced because this deduction hadn't happened yet.
684
685 // The new value of the pack.
687
688 // The outer deduction for this pack, if any.
689 DeducedPack *Outer = nullptr;
690
691 DeducedPack(unsigned Index) : Index(Index) {}
692};
693
694namespace {
695
696/// A scope in which we're performing pack deduction.
697class PackDeductionScope {
698public:
699 /// Prepare to deduce the packs named within Pattern.
700 PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
703 bool DeducePackIfNotAlreadyDeduced = false)
704 : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info),
705 DeducePackIfNotAlreadyDeduced(DeducePackIfNotAlreadyDeduced){
706 unsigned NumNamedPacks = addPacks(Pattern);
707 finishConstruction(NumNamedPacks);
708 }
709
710 /// Prepare to directly deduce arguments of the parameter with index \p Index.
711 PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
713 TemplateDeductionInfo &Info, unsigned Index)
714 : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
715 addPack(Index);
716 finishConstruction(1);
717 }
718
719private:
720 void addPack(unsigned Index) {
721 // Save the deduced template argument for the parameter pack expanded
722 // by this pack expansion, then clear out the deduction.
723 DeducedPack Pack(Index);
724 Pack.Saved = Deduced[Index];
725 Deduced[Index] = TemplateArgument();
726
727 // FIXME: What if we encounter multiple packs with different numbers of
728 // pre-expanded expansions? (This should already have been diagnosed
729 // during substitution.)
730 if (std::optional<unsigned> ExpandedPackExpansions =
731 getExpandedPackSize(TemplateParams->getParam(Index)))
732 FixedNumExpansions = ExpandedPackExpansions;
733
734 Packs.push_back(Pack);
735 }
736
737 unsigned addPacks(TemplateArgument Pattern) {
738 // Compute the set of template parameter indices that correspond to
739 // parameter packs expanded by the pack expansion.
740 llvm::SmallBitVector SawIndices(TemplateParams->size());
742
743 auto AddPack = [&](unsigned Index) {
744 if (SawIndices[Index])
745 return;
746 SawIndices[Index] = true;
747 addPack(Index);
748
749 // Deducing a parameter pack that is a pack expansion also constrains the
750 // packs appearing in that parameter to have the same deduced arity. Also,
751 // in C++17 onwards, deducing a non-type template parameter deduces its
752 // type, so we need to collect the pending deduced values for those packs.
753 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(
754 TemplateParams->getParam(Index))) {
755 if (!NTTP->isExpandedParameterPack())
756 if (auto *Expansion = dyn_cast<PackExpansionType>(NTTP->getType()))
757 ExtraDeductions.push_back(Expansion->getPattern());
758 }
759 // FIXME: Also collect the unexpanded packs in any type and template
760 // parameter packs that are pack expansions.
761 };
762
763 auto Collect = [&](TemplateArgument Pattern) {
765 S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
766 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
767 unsigned Depth, Index;
768 std::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
769 if (Depth == Info.getDeducedDepth())
770 AddPack(Index);
771 }
772 };
773
774 // Look for unexpanded packs in the pattern.
775 Collect(Pattern);
776 assert(!Packs.empty() && "Pack expansion without unexpanded packs?");
777
778 unsigned NumNamedPacks = Packs.size();
779
780 // Also look for unexpanded packs that are indirectly deduced by deducing
781 // the sizes of the packs in this pattern.
782 while (!ExtraDeductions.empty())
783 Collect(ExtraDeductions.pop_back_val());
784
785 return NumNamedPacks;
786 }
787
788 void finishConstruction(unsigned NumNamedPacks) {
789 // Dig out the partially-substituted pack, if there is one.
790 const TemplateArgument *PartialPackArgs = nullptr;
791 unsigned NumPartialPackArgs = 0;
792 std::pair<unsigned, unsigned> PartialPackDepthIndex(-1u, -1u);
793 if (auto *Scope = S.CurrentInstantiationScope)
794 if (auto *Partial = Scope->getPartiallySubstitutedPack(
795 &PartialPackArgs, &NumPartialPackArgs))
796 PartialPackDepthIndex = getDepthAndIndex(Partial);
797
798 // This pack expansion will have been partially or fully expanded if
799 // it only names explicitly-specified parameter packs (including the
800 // partially-substituted one, if any).
801 bool IsExpanded = true;
802 for (unsigned I = 0; I != NumNamedPacks; ++I) {
803 if (Packs[I].Index >= Info.getNumExplicitArgs()) {
804 IsExpanded = false;
805 IsPartiallyExpanded = false;
806 break;
807 }
808 if (PartialPackDepthIndex ==
809 std::make_pair(Info.getDeducedDepth(), Packs[I].Index)) {
810 IsPartiallyExpanded = true;
811 }
812 }
813
814 // Skip over the pack elements that were expanded into separate arguments.
815 // If we partially expanded, this is the number of partial arguments.
816 if (IsPartiallyExpanded)
817 PackElements += NumPartialPackArgs;
818 else if (IsExpanded)
819 PackElements += *FixedNumExpansions;
820
821 for (auto &Pack : Packs) {
822 if (Info.PendingDeducedPacks.size() > Pack.Index)
823 Pack.Outer = Info.PendingDeducedPacks[Pack.Index];
824 else
825 Info.PendingDeducedPacks.resize(Pack.Index + 1);
826 Info.PendingDeducedPacks[Pack.Index] = &Pack;
827
828 if (PartialPackDepthIndex ==
829 std::make_pair(Info.getDeducedDepth(), Pack.Index)) {
830 Pack.New.append(PartialPackArgs, PartialPackArgs + NumPartialPackArgs);
831 // We pre-populate the deduced value of the partially-substituted
832 // pack with the specified value. This is not entirely correct: the
833 // value is supposed to have been substituted, not deduced, but the
834 // cases where this is observable require an exact type match anyway.
835 //
836 // FIXME: If we could represent a "depth i, index j, pack elem k"
837 // parameter, we could substitute the partially-substituted pack
838 // everywhere and avoid this.
839 if (!IsPartiallyExpanded)
840 Deduced[Pack.Index] = Pack.New[PackElements];
841 }
842 }
843 }
844
845public:
846 ~PackDeductionScope() {
847 for (auto &Pack : Packs)
848 Info.PendingDeducedPacks[Pack.Index] = Pack.Outer;
849 }
850
851 /// Determine whether this pack has already been partially expanded into a
852 /// sequence of (prior) function parameters / template arguments.
853 bool isPartiallyExpanded() { return IsPartiallyExpanded; }
854
855 /// Determine whether this pack expansion scope has a known, fixed arity.
856 /// This happens if it involves a pack from an outer template that has
857 /// (notionally) already been expanded.
858 bool hasFixedArity() { return FixedNumExpansions.has_value(); }
859
860 /// Determine whether the next element of the argument is still part of this
861 /// pack. This is the case unless the pack is already expanded to a fixed
862 /// length.
863 bool hasNextElement() {
864 return !FixedNumExpansions || *FixedNumExpansions > PackElements;
865 }
866
867 /// Move to deducing the next element in each pack that is being deduced.
868 void nextPackElement() {
869 // Capture the deduced template arguments for each parameter pack expanded
870 // by this pack expansion, add them to the list of arguments we've deduced
871 // for that pack, then clear out the deduced argument.
872 for (auto &Pack : Packs) {
873 DeducedTemplateArgument &DeducedArg = Deduced[Pack.Index];
874 if (!Pack.New.empty() || !DeducedArg.isNull()) {
875 while (Pack.New.size() < PackElements)
876 Pack.New.push_back(DeducedTemplateArgument());
877 if (Pack.New.size() == PackElements)
878 Pack.New.push_back(DeducedArg);
879 else
880 Pack.New[PackElements] = DeducedArg;
881 DeducedArg = Pack.New.size() > PackElements + 1
882 ? Pack.New[PackElements + 1]
884 }
885 }
886 ++PackElements;
887 }
888
889 /// Finish template argument deduction for a set of argument packs,
890 /// producing the argument packs and checking for consistency with prior
891 /// deductions.
893 // Build argument packs for each of the parameter packs expanded by this
894 // pack expansion.
895 for (auto &Pack : Packs) {
896 // Put back the old value for this pack.
897 Deduced[Pack.Index] = Pack.Saved;
898
899 // Always make sure the size of this pack is correct, even if we didn't
900 // deduce any values for it.
901 //
902 // FIXME: This isn't required by the normative wording, but substitution
903 // and post-substitution checking will always fail if the arity of any
904 // pack is not equal to the number of elements we processed. (Either that
905 // or something else has gone *very* wrong.) We're permitted to skip any
906 // hard errors from those follow-on steps by the intent (but not the
907 // wording) of C++ [temp.inst]p8:
908 //
909 // If the function selected by overload resolution can be determined
910 // without instantiating a class template definition, it is unspecified
911 // whether that instantiation actually takes place
912 Pack.New.resize(PackElements);
913
914 // Build or find a new value for this pack.
916 if (Pack.New.empty()) {
917 // If we deduced an empty argument pack, create it now.
919 } else {
920 TemplateArgument *ArgumentPack =
921 new (S.Context) TemplateArgument[Pack.New.size()];
922 std::copy(Pack.New.begin(), Pack.New.end(), ArgumentPack);
923 NewPack = DeducedTemplateArgument(
924 TemplateArgument(llvm::ArrayRef(ArgumentPack, Pack.New.size())),
925 // FIXME: This is wrong, it's possible that some pack elements are
926 // deduced from an array bound and others are not:
927 // template<typename ...T, T ...V> void g(const T (&...p)[V]);
928 // g({1, 2, 3}, {{}, {}});
929 // ... should deduce T = {int, size_t (from array bound)}.
930 Pack.New[0].wasDeducedFromArrayBound());
931 }
932
933 // Pick where we're going to put the merged pack.
935 if (Pack.Outer) {
936 if (Pack.Outer->DeferredDeduction.isNull()) {
937 // Defer checking this pack until we have a complete pack to compare
938 // it against.
939 Pack.Outer->DeferredDeduction = NewPack;
940 continue;
941 }
942 Loc = &Pack.Outer->DeferredDeduction;
943 } else {
944 Loc = &Deduced[Pack.Index];
945 }
946
947 // Check the new pack matches any previous value.
948 DeducedTemplateArgument OldPack = *Loc;
950 S.Context, OldPack, NewPack, DeducePackIfNotAlreadyDeduced);
951
952 Info.AggregateDeductionCandidateHasMismatchedArity =
953 OldPack.getKind() == TemplateArgument::Pack &&
954 NewPack.getKind() == TemplateArgument::Pack &&
955 OldPack.pack_size() != NewPack.pack_size() && !Result.isNull();
956
957 // If we deferred a deduction of this pack, check that one now too.
958 if (!Result.isNull() && !Pack.DeferredDeduction.isNull()) {
959 OldPack = Result;
960 NewPack = Pack.DeferredDeduction;
961 Result = checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
962 }
963
964 NamedDecl *Param = TemplateParams->getParam(Pack.Index);
965 if (Result.isNull()) {
966 Info.Param = makeTemplateParameter(Param);
967 Info.FirstArg = OldPack;
968 Info.SecondArg = NewPack;
970 }
971
972 // If we have a pre-expanded pack and we didn't deduce enough elements
973 // for it, fail deduction.
974 if (std::optional<unsigned> Expansions = getExpandedPackSize(Param)) {
975 if (*Expansions != PackElements) {
976 Info.Param = makeTemplateParameter(Param);
977 Info.FirstArg = Result;
979 }
980 }
981
982 *Loc = Result;
983 }
984
985 return Sema::TDK_Success;
986 }
987
988private:
989 Sema &S;
990 TemplateParameterList *TemplateParams;
993 unsigned PackElements = 0;
994 bool IsPartiallyExpanded = false;
995 bool DeducePackIfNotAlreadyDeduced = false;
996 /// The number of expansions, if we have a fully-expanded pack in this scope.
997 std::optional<unsigned> FixedNumExpansions;
998
1000};
1001
1002} // namespace
1003
1004/// Deduce the template arguments by comparing the list of parameter
1005/// types to the list of argument types, as in the parameter-type-lists of
1006/// function types (C++ [temp.deduct.type]p10).
1007///
1008/// \param S The semantic analysis object within which we are deducing
1009///
1010/// \param TemplateParams The template parameters that we are deducing
1011///
1012/// \param Params The list of parameter types
1013///
1014/// \param NumParams The number of types in \c Params
1015///
1016/// \param Args The list of argument types
1017///
1018/// \param NumArgs The number of types in \c Args
1019///
1020/// \param Info information about the template argument deduction itself
1021///
1022/// \param Deduced the deduced template arguments
1023///
1024/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
1025/// how template argument deduction is performed.
1026///
1027/// \param PartialOrdering If true, we are performing template argument
1028/// deduction for during partial ordering for a call
1029/// (C++0x [temp.deduct.partial]).
1030///
1031/// \returns the result of template argument deduction so far. Note that a
1032/// "success" result means that template argument deduction has not yet failed,
1033/// but it may still fail, later, for other reasons.
1036 TemplateParameterList *TemplateParams,
1037 const QualType *Params, unsigned NumParams,
1038 const QualType *Args, unsigned NumArgs,
1041 unsigned TDF,
1042 bool PartialOrdering = false) {
1043 // C++0x [temp.deduct.type]p10:
1044 // Similarly, if P has a form that contains (T), then each parameter type
1045 // Pi of the respective parameter-type- list of P is compared with the
1046 // corresponding parameter type Ai of the corresponding parameter-type-list
1047 // of A. [...]
1048 unsigned ArgIdx = 0, ParamIdx = 0;
1049 for (; ParamIdx != NumParams; ++ParamIdx) {
1050 // Check argument types.
1051 const PackExpansionType *Expansion
1052 = dyn_cast<PackExpansionType>(Params[ParamIdx]);
1053 if (!Expansion) {
1054 // Simple case: compare the parameter and argument types at this point.
1055
1056 // Make sure we have an argument.
1057 if (ArgIdx >= NumArgs)
1059
1060 if (isa<PackExpansionType>(Args[ArgIdx])) {
1061 // C++0x [temp.deduct.type]p22:
1062 // If the original function parameter associated with A is a function
1063 // parameter pack and the function parameter associated with P is not
1064 // a function parameter pack, then template argument deduction fails.
1066 }
1067
1070 S, TemplateParams, Params[ParamIdx].getUnqualifiedType(),
1071 Args[ArgIdx].getUnqualifiedType(), Info, Deduced, TDF,
1073 /*DeducedFromArrayBound=*/false))
1074 return Result;
1075
1076 ++ArgIdx;
1077 continue;
1078 }
1079
1080 // C++0x [temp.deduct.type]p10:
1081 // If the parameter-declaration corresponding to Pi is a function
1082 // parameter pack, then the type of its declarator- id is compared with
1083 // each remaining parameter type in the parameter-type-list of A. Each
1084 // comparison deduces template arguments for subsequent positions in the
1085 // template parameter packs expanded by the function parameter pack.
1086
1087 QualType Pattern = Expansion->getPattern();
1088 PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
1089
1090 // A pack scope with fixed arity is not really a pack any more, so is not
1091 // a non-deduced context.
1092 if (ParamIdx + 1 == NumParams || PackScope.hasFixedArity()) {
1093 for (; ArgIdx < NumArgs && PackScope.hasNextElement(); ++ArgIdx) {
1094 // Deduce template arguments from the pattern.
1097 S, TemplateParams, Pattern.getUnqualifiedType(),
1098 Args[ArgIdx].getUnqualifiedType(), Info, Deduced, TDF,
1099 PartialOrdering, /*DeducedFromArrayBound=*/false))
1100 return Result;
1101
1102 PackScope.nextPackElement();
1103 }
1104 } else {
1105 // C++0x [temp.deduct.type]p5:
1106 // The non-deduced contexts are:
1107 // - A function parameter pack that does not occur at the end of the
1108 // parameter-declaration-clause.
1109 //
1110 // FIXME: There is no wording to say what we should do in this case. We
1111 // choose to resolve this by applying the same rule that is applied for a
1112 // function call: that is, deduce all contained packs to their
1113 // explicitly-specified values (or to <> if there is no such value).
1114 //
1115 // This is seemingly-arbitrarily different from the case of a template-id
1116 // with a non-trailing pack-expansion in its arguments, which renders the
1117 // entire template-argument-list a non-deduced context.
1118
1119 // If the parameter type contains an explicitly-specified pack that we
1120 // could not expand, skip the number of parameters notionally created
1121 // by the expansion.
1122 std::optional<unsigned> NumExpansions = Expansion->getNumExpansions();
1123 if (NumExpansions && !PackScope.isPartiallyExpanded()) {
1124 for (unsigned I = 0; I != *NumExpansions && ArgIdx < NumArgs;
1125 ++I, ++ArgIdx)
1126 PackScope.nextPackElement();
1127 }
1128 }
1129
1130 // Build argument packs for each of the parameter packs expanded by this
1131 // pack expansion.
1132 if (auto Result = PackScope.finish())
1133 return Result;
1134 }
1135
1136 // DR692, DR1395
1137 // C++0x [temp.deduct.type]p10:
1138 // If the parameter-declaration corresponding to P_i ...
1139 // During partial ordering, if Ai was originally a function parameter pack:
1140 // - if P does not contain a function parameter type corresponding to Ai then
1141 // Ai is ignored;
1142 if (PartialOrdering && ArgIdx + 1 == NumArgs &&
1143 isa<PackExpansionType>(Args[ArgIdx]))
1144 return Sema::TDK_Success;
1145
1146 // Make sure we don't have any extra arguments.
1147 if (ArgIdx < NumArgs)
1149
1150 return Sema::TDK_Success;
1151}
1152
1153/// Determine whether the parameter has qualifiers that the argument
1154/// lacks. Put another way, determine whether there is no way to add
1155/// a deduced set of qualifiers to the ParamType that would result in
1156/// its qualifiers matching those of the ArgType.
1158 QualType ArgType) {
1159 Qualifiers ParamQs = ParamType.getQualifiers();
1160 Qualifiers ArgQs = ArgType.getQualifiers();
1161
1162 if (ParamQs == ArgQs)
1163 return false;
1164
1165 // Mismatched (but not missing) Objective-C GC attributes.
1166 if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() &&
1167 ParamQs.hasObjCGCAttr())
1168 return true;
1169
1170 // Mismatched (but not missing) address spaces.
1171 if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() &&
1172 ParamQs.hasAddressSpace())
1173 return true;
1174
1175 // Mismatched (but not missing) Objective-C lifetime qualifiers.
1176 if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() &&
1177 ParamQs.hasObjCLifetime())
1178 return true;
1179
1180 // CVR qualifiers inconsistent or a superset.
1181 return (ParamQs.getCVRQualifiers() & ~ArgQs.getCVRQualifiers()) != 0;
1182}
1183
1184/// Compare types for equality with respect to possibly compatible
1185/// function types (noreturn adjustment, implicit calling conventions). If any
1186/// of parameter and argument is not a function, just perform type comparison.
1187///
1188/// \param P the template parameter type.
1189///
1190/// \param A the argument type.
1192 const FunctionType *PF = P->getAs<FunctionType>(),
1193 *AF = A->getAs<FunctionType>();
1194
1195 // Just compare if not functions.
1196 if (!PF || !AF)
1197 return Context.hasSameType(P, A);
1198
1199 // Noreturn and noexcept adjustment.
1200 QualType AdjustedParam;
1201 if (IsFunctionConversion(P, A, AdjustedParam))
1202 return Context.hasSameType(AdjustedParam, A);
1203
1204 // FIXME: Compatible calling conventions.
1205
1206 return Context.hasSameType(P, A);
1207}
1208
1209/// Get the index of the first template parameter that was originally from the
1210/// innermost template-parameter-list. This is 0 except when we concatenate
1211/// the template parameter lists of a class template and a constructor template
1212/// when forming an implicit deduction guide.
1214 auto *Guide = dyn_cast<CXXDeductionGuideDecl>(FTD->getTemplatedDecl());
1215 if (!Guide || !Guide->isImplicit())
1216 return 0;
1217 return Guide->getDeducedTemplate()->getTemplateParameters()->size();
1218}
1219
1220/// Determine whether a type denotes a forwarding reference.
1221static bool isForwardingReference(QualType Param, unsigned FirstInnerIndex) {
1222 // C++1z [temp.deduct.call]p3:
1223 // A forwarding reference is an rvalue reference to a cv-unqualified
1224 // template parameter that does not represent a template parameter of a
1225 // class template.
1226 if (auto *ParamRef = Param->getAs<RValueReferenceType>()) {
1227 if (ParamRef->getPointeeType().getQualifiers())
1228 return false;
1229 auto *TypeParm = ParamRef->getPointeeType()->getAs<TemplateTypeParmType>();
1230 return TypeParm && TypeParm->getIndex() >= FirstInnerIndex;
1231 }
1232 return false;
1233}
1234
1236 return cast<CXXRecordDecl>(
1238}
1239
1240/// Attempt to deduce the template arguments by checking the base types
1241/// according to (C++20 [temp.deduct.call] p4b3.
1242///
1243/// \param S the semantic analysis object within which we are deducing.
1244///
1245/// \param RD the top level record object we are deducing against.
1246///
1247/// \param TemplateParams the template parameters that we are deducing.
1248///
1249/// \param P the template specialization parameter type.
1250///
1251/// \param Info information about the template argument deduction itself.
1252///
1253/// \param Deduced the deduced template arguments.
1254///
1255/// \returns the result of template argument deduction with the bases. "invalid"
1256/// means no matches, "success" found a single item, and the
1257/// "MiscellaneousDeductionFailure" result happens when the match is ambiguous.
1260 TemplateParameterList *TemplateParams, QualType P,
1263 // C++14 [temp.deduct.call] p4b3:
1264 // If P is a class and P has the form simple-template-id, then the
1265 // transformed A can be a derived class of the deduced A. Likewise if
1266 // P is a pointer to a class of the form simple-template-id, the
1267 // transformed A can be a pointer to a derived class pointed to by the
1268 // deduced A. However, if there is a class C that is a (direct or
1269 // indirect) base class of D and derived (directly or indirectly) from a
1270 // class B and that would be a valid deduced A, the deduced A cannot be
1271 // B or pointer to B, respectively.
1272 //
1273 // These alternatives are considered only if type deduction would
1274 // otherwise fail. If they yield more than one possible deduced A, the
1275 // type deduction fails.
1276
1277 // Use a breadth-first search through the bases to collect the set of
1278 // successful matches. Visited contains the set of nodes we have already
1279 // visited, while ToVisit is our stack of records that we still need to
1280 // visit. Matches contains a list of matches that have yet to be
1281 // disqualified.
1284 // We iterate over this later, so we have to use MapVector to ensure
1285 // determinism.
1286 llvm::MapVector<const CXXRecordDecl *,
1288 Matches;
1289
1290 auto AddBases = [&Visited, &ToVisit](const CXXRecordDecl *RD) {
1291 for (const auto &Base : RD->bases()) {
1292 QualType T = Base.getType();
1293 assert(T->isRecordType() && "Base class that isn't a record?");
1294 if (Visited.insert(::getCanonicalRD(T)).second)
1295 ToVisit.push_back(T);
1296 }
1297 };
1298
1299 // Set up the loop by adding all the bases.
1300 AddBases(RD);
1301
1302 // Search each path of bases until we either run into a successful match
1303 // (where all bases of it are invalid), or we run out of bases.
1304 while (!ToVisit.empty()) {
1305 QualType NextT = ToVisit.pop_back_val();
1306
1307 SmallVector<DeducedTemplateArgument, 8> DeducedCopy(Deduced.begin(),
1308 Deduced.end());
1311 S, TemplateParams, P, NextT, BaseInfo, DeducedCopy);
1312
1313 // If this was a successful deduction, add it to the list of matches,
1314 // otherwise we need to continue searching its bases.
1315 const CXXRecordDecl *RD = ::getCanonicalRD(NextT);
1317 Matches.insert({RD, DeducedCopy});
1318 else
1319 AddBases(RD);
1320 }
1321
1322 // At this point, 'Matches' contains a list of seemingly valid bases, however
1323 // in the event that we have more than 1 match, it is possible that the base
1324 // of one of the matches might be disqualified for being a base of another
1325 // valid match. We can count on cyclical instantiations being invalid to
1326 // simplify the disqualifications. That is, if A & B are both matches, and B
1327 // inherits from A (disqualifying A), we know that A cannot inherit from B.
1328 if (Matches.size() > 1) {
1329 Visited.clear();
1330 for (const auto &Match : Matches)
1331 AddBases(Match.first);
1332
1333 // We can give up once we have a single item (or have run out of things to
1334 // search) since cyclical inheritance isn't valid.
1335 while (Matches.size() > 1 && !ToVisit.empty()) {
1336 const CXXRecordDecl *RD = ::getCanonicalRD(ToVisit.pop_back_val());
1337 Matches.erase(RD);
1338
1339 // Always add all bases, since the inheritance tree can contain
1340 // disqualifications for multiple matches.
1341 AddBases(RD);
1342 }
1343 }
1344
1345 if (Matches.empty())
1346 return Sema::TDK_Invalid;
1347 if (Matches.size() > 1)
1349
1350 std::swap(Matches.front().second, Deduced);
1351 return Sema::TDK_Success;
1352}
1353
1354/// Deduce the template arguments by comparing the parameter type and
1355/// the argument type (C++ [temp.deduct.type]).
1356///
1357/// \param S the semantic analysis object within which we are deducing
1358///
1359/// \param TemplateParams the template parameters that we are deducing
1360///
1361/// \param P the parameter type
1362///
1363/// \param A the argument type
1364///
1365/// \param Info information about the template argument deduction itself
1366///
1367/// \param Deduced the deduced template arguments
1368///
1369/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
1370/// how template argument deduction is performed.
1371///
1372/// \param PartialOrdering Whether we're performing template argument deduction
1373/// in the context of partial ordering (C++0x [temp.deduct.partial]).
1374///
1375/// \returns the result of template argument deduction so far. Note that a
1376/// "success" result means that template argument deduction has not yet failed,
1377/// but it may still fail, later, for other reasons.
1379 Sema &S, TemplateParameterList *TemplateParams, QualType P, QualType A,
1381 SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF,
1382 bool PartialOrdering, bool DeducedFromArrayBound) {
1383
1384 // If the argument type is a pack expansion, look at its pattern.
1385 // This isn't explicitly called out
1386 if (const auto *AExp = dyn_cast<PackExpansionType>(A))
1387 A = AExp->getPattern();
1388 assert(!isa<PackExpansionType>(A.getCanonicalType()));
1389
1390 if (PartialOrdering) {
1391 // C++11 [temp.deduct.partial]p5:
1392 // Before the partial ordering is done, certain transformations are
1393 // performed on the types used for partial ordering:
1394 // - If P is a reference type, P is replaced by the type referred to.
1395 const ReferenceType *PRef = P->getAs<ReferenceType>();
1396 if (PRef)
1397 P = PRef->getPointeeType();
1398
1399 // - If A is a reference type, A is replaced by the type referred to.
1400 const ReferenceType *ARef = A->getAs<ReferenceType>();
1401 if (ARef)
1402 A = A->getPointeeType();
1403
1404 if (PRef && ARef && S.Context.hasSameUnqualifiedType(P, A)) {
1405 // C++11 [temp.deduct.partial]p9:
1406 // If, for a given type, deduction succeeds in both directions (i.e.,
1407 // the types are identical after the transformations above) and both
1408 // P and A were reference types [...]:
1409 // - if [one type] was an lvalue reference and [the other type] was
1410 // not, [the other type] is not considered to be at least as
1411 // specialized as [the first type]
1412 // - if [one type] is more cv-qualified than [the other type],
1413 // [the other type] is not considered to be at least as specialized
1414 // as [the first type]
1415 // Objective-C ARC adds:
1416 // - [one type] has non-trivial lifetime, [the other type] has
1417 // __unsafe_unretained lifetime, and the types are otherwise
1418 // identical
1419 //
1420 // A is "considered to be at least as specialized" as P iff deduction
1421 // succeeds, so we model this as a deduction failure. Note that
1422 // [the first type] is P and [the other type] is A here; the standard
1423 // gets this backwards.
1424 Qualifiers PQuals = P.getQualifiers(), AQuals = A.getQualifiers();
1425 if ((PRef->isLValueReferenceType() && !ARef->isLValueReferenceType()) ||
1426 PQuals.isStrictSupersetOf(AQuals) ||
1427 (PQuals.hasNonTrivialObjCLifetime() &&
1428 AQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone &&
1429 PQuals.withoutObjCLifetime() == AQuals.withoutObjCLifetime())) {
1430 Info.FirstArg = TemplateArgument(P);
1431 Info.SecondArg = TemplateArgument(A);
1433 }
1434 }
1435 Qualifiers DiscardedQuals;
1436 // C++11 [temp.deduct.partial]p7:
1437 // Remove any top-level cv-qualifiers:
1438 // - If P is a cv-qualified type, P is replaced by the cv-unqualified
1439 // version of P.
1440 P = S.Context.getUnqualifiedArrayType(P, DiscardedQuals);
1441 // - If A is a cv-qualified type, A is replaced by the cv-unqualified
1442 // version of A.
1443 A = S.Context.getUnqualifiedArrayType(A, DiscardedQuals);
1444 } else {
1445 // C++0x [temp.deduct.call]p4 bullet 1:
1446 // - If the original P is a reference type, the deduced A (i.e., the type
1447 // referred to by the reference) can be more cv-qualified than the
1448 // transformed A.
1449 if (TDF & TDF_ParamWithReferenceType) {
1450 Qualifiers Quals;
1451 QualType UnqualP = S.Context.getUnqualifiedArrayType(P, Quals);
1453 P = S.Context.getQualifiedType(UnqualP, Quals);
1454 }
1455
1456 if ((TDF & TDF_TopLevelParameterTypeList) && !P->isFunctionType()) {
1457 // C++0x [temp.deduct.type]p10:
1458 // If P and A are function types that originated from deduction when
1459 // taking the address of a function template (14.8.2.2) or when deducing
1460 // template arguments from a function declaration (14.8.2.6) and Pi and
1461 // Ai are parameters of the top-level parameter-type-list of P and A,
1462 // respectively, Pi is adjusted if it is a forwarding reference and Ai
1463 // is an lvalue reference, in
1464 // which case the type of Pi is changed to be the template parameter
1465 // type (i.e., T&& is changed to simply T). [ Note: As a result, when
1466 // Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
1467 // deduced as X&. - end note ]
1468 TDF &= ~TDF_TopLevelParameterTypeList;
1469 if (isForwardingReference(P, /*FirstInnerIndex=*/0) &&
1471 P = P->getPointeeType();
1472 }
1473 }
1474
1475 // C++ [temp.deduct.type]p9:
1476 // A template type argument T, a template template argument TT or a
1477 // template non-type argument i can be deduced if P and A have one of
1478 // the following forms:
1479 //
1480 // T
1481 // cv-list T
1482 if (const auto *TTP = P->getAs<TemplateTypeParmType>()) {
1483 // Just skip any attempts to deduce from a placeholder type or a parameter
1484 // at a different depth.
1485 if (A->isPlaceholderType() || Info.getDeducedDepth() != TTP->getDepth())
1486 return Sema::TDK_Success;
1487
1488 unsigned Index = TTP->getIndex();
1489
1490 // If the argument type is an array type, move the qualifiers up to the
1491 // top level, so they can be matched with the qualifiers on the parameter.
1492 if (A->isArrayType()) {
1493 Qualifiers Quals;
1494 A = S.Context.getUnqualifiedArrayType(A, Quals);
1495 if (Quals)
1496 A = S.Context.getQualifiedType(A, Quals);
1497 }
1498
1499 // The argument type can not be less qualified than the parameter
1500 // type.
1501 if (!(TDF & TDF_IgnoreQualifiers) &&
1503 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1504 Info.FirstArg = TemplateArgument(P);
1505 Info.SecondArg = TemplateArgument(A);
1507 }
1508
1509 // Do not match a function type with a cv-qualified type.
1510 // http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1584
1511 if (A->isFunctionType() && P.hasQualifiers())
1513
1514 assert(TTP->getDepth() == Info.getDeducedDepth() &&
1515 "saw template type parameter with wrong depth");
1516 assert(A->getCanonicalTypeInternal() != S.Context.OverloadTy &&
1517 "Unresolved overloaded function");
1519
1520 // Remove any qualifiers on the parameter from the deduced type.
1521 // We checked the qualifiers for consistency above.
1522 Qualifiers DeducedQs = DeducedType.getQualifiers();
1523 Qualifiers ParamQs = P.getQualifiers();
1524 DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers());
1525 if (ParamQs.hasObjCGCAttr())
1526 DeducedQs.removeObjCGCAttr();
1527 if (ParamQs.hasAddressSpace())
1528 DeducedQs.removeAddressSpace();
1529 if (ParamQs.hasObjCLifetime())
1530 DeducedQs.removeObjCLifetime();
1531
1532 // Objective-C ARC:
1533 // If template deduction would produce a lifetime qualifier on a type
1534 // that is not a lifetime type, template argument deduction fails.
1535 if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() &&
1537 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1538 Info.FirstArg = TemplateArgument(P);
1539 Info.SecondArg = TemplateArgument(A);
1541 }
1542
1543 // Objective-C ARC:
1544 // If template deduction would produce an argument type with lifetime type
1545 // but no lifetime qualifier, the __strong lifetime qualifier is inferred.
1546 if (S.getLangOpts().ObjCAutoRefCount && DeducedType->isObjCLifetimeType() &&
1547 !DeducedQs.hasObjCLifetime())
1549
1550 DeducedType =
1551 S.Context.getQualifiedType(DeducedType.getUnqualifiedType(), DeducedQs);
1552
1553 DeducedTemplateArgument NewDeduced(DeducedType, DeducedFromArrayBound);
1555 checkDeducedTemplateArguments(S.Context, Deduced[Index], NewDeduced);
1556 if (Result.isNull()) {
1557 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1558 Info.FirstArg = Deduced[Index];
1559 Info.SecondArg = NewDeduced;
1561 }
1562
1563 Deduced[Index] = Result;
1564 return Sema::TDK_Success;
1565 }
1566
1567 // Set up the template argument deduction information for a failure.
1568 Info.FirstArg = TemplateArgument(P);
1569 Info.SecondArg = TemplateArgument(A);
1570
1571 // If the parameter is an already-substituted template parameter
1572 // pack, do nothing: we don't know which of its arguments to look
1573 // at, so we have to wait until all of the parameter packs in this
1574 // expansion have arguments.
1575 if (P->getAs<SubstTemplateTypeParmPackType>())
1576 return Sema::TDK_Success;
1577
1578 // Check the cv-qualifiers on the parameter and argument types.
1579 if (!(TDF & TDF_IgnoreQualifiers)) {
1580 if (TDF & TDF_ParamWithReferenceType) {
1583 } else if (TDF & TDF_ArgWithReferenceType) {
1584 // C++ [temp.deduct.conv]p4:
1585 // If the original A is a reference type, A can be more cv-qualified
1586 // than the deduced A
1587 if (!A.getQualifiers().compatiblyIncludes(P.getQualifiers()))
1589
1590 // Strip out all extra qualifiers from the argument to figure out the
1591 // type we're converting to, prior to the qualification conversion.
1592 Qualifiers Quals;
1593 A = S.Context.getUnqualifiedArrayType(A, Quals);
1594 A = S.Context.getQualifiedType(A, P.getQualifiers());
1595 } else if (!IsPossiblyOpaquelyQualifiedType(P)) {
1596 if (P.getCVRQualifiers() != A.getCVRQualifiers())
1598 }
1599 }
1600
1601 // If the parameter type is not dependent, there is nothing to deduce.
1602 if (!P->isDependentType()) {
1603 if (TDF & TDF_SkipNonDependent)
1604 return Sema::TDK_Success;
1606 : S.Context.hasSameType(P, A))
1607 return Sema::TDK_Success;
1610 return Sema::TDK_Success;
1611 if (!(TDF & TDF_IgnoreQualifiers))
1613 // Otherwise, when ignoring qualifiers, the types not having the same
1614 // unqualified type does not mean they do not match, so in this case we
1615 // must keep going and analyze with a non-dependent parameter type.
1616 }
1617
1618 switch (P.getCanonicalType()->getTypeClass()) {
1619 // Non-canonical types cannot appear here.
1620#define NON_CANONICAL_TYPE(Class, Base) \
1621 case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class);
1622#define TYPE(Class, Base)
1623#include "clang/AST/TypeNodes.inc"
1624
1625 case Type::TemplateTypeParm:
1626 case Type::SubstTemplateTypeParmPack:
1627 llvm_unreachable("Type nodes handled above");
1628
1629 case Type::Auto:
1630 // C++23 [temp.deduct.funcaddr]/3:
1631 // A placeholder type in the return type of a function template is a
1632 // non-deduced context.
1633 // There's no corresponding wording for [temp.deduct.decl], but we treat
1634 // it the same to match other compilers.
1635 if (P->isDependentType())
1636 return Sema::TDK_Success;
1637 [[fallthrough]];
1638 case Type::Builtin:
1639 case Type::VariableArray:
1640 case Type::Vector:
1641 case Type::FunctionNoProto:
1642 case Type::Record:
1643 case Type::Enum:
1644 case Type::ObjCObject:
1645 case Type::ObjCInterface:
1646 case Type::ObjCObjectPointer:
1647 case Type::BitInt:
1648 return (TDF & TDF_SkipNonDependent) ||
1649 ((TDF & TDF_IgnoreQualifiers)
1651 : S.Context.hasSameType(P, A))
1654
1655 // _Complex T [placeholder extension]
1656 case Type::Complex: {
1657 const auto *CP = P->castAs<ComplexType>(), *CA = A->getAs<ComplexType>();
1658 if (!CA)
1661 S, TemplateParams, CP->getElementType(), CA->getElementType(), Info,
1662 Deduced, TDF);
1663 }
1664
1665 // _Atomic T [extension]
1666 case Type::Atomic: {
1667 const auto *PA = P->castAs<AtomicType>(), *AA = A->getAs<AtomicType>();
1668 if (!AA)
1671 S, TemplateParams, PA->getValueType(), AA->getValueType(), Info,
1672 Deduced, TDF);
1673 }
1674
1675 // T *
1676 case Type::Pointer: {
1677 QualType PointeeType;
1678 if (const auto *PA = A->getAs<PointerType>()) {
1679 PointeeType = PA->getPointeeType();
1680 } else if (const auto *PA = A->getAs<ObjCObjectPointerType>()) {
1681 PointeeType = PA->getPointeeType();
1682 } else {
1684 }
1686 S, TemplateParams, P->castAs<PointerType>()->getPointeeType(),
1687 PointeeType, Info, Deduced,
1689 }
1690
1691 // T &
1692 case Type::LValueReference: {
1693 const auto *RP = P->castAs<LValueReferenceType>(),
1694 *RA = A->getAs<LValueReferenceType>();
1695 if (!RA)
1697
1699 S, TemplateParams, RP->getPointeeType(), RA->getPointeeType(), Info,
1700 Deduced, 0);
1701 }
1702
1703 // T && [C++0x]
1704 case Type::RValueReference: {
1705 const auto *RP = P->castAs<RValueReferenceType>(),
1706 *RA = A->getAs<RValueReferenceType>();
1707 if (!RA)
1709
1711 S, TemplateParams, RP->getPointeeType(), RA->getPointeeType(), Info,
1712 Deduced, 0);
1713 }
1714
1715 // T [] (implied, but not stated explicitly)
1716 case Type::IncompleteArray: {
1717 const auto *IAA = S.Context.getAsIncompleteArrayType(A);
1718 if (!IAA)
1720
1721 const auto *IAP = S.Context.getAsIncompleteArrayType(P);
1722 assert(IAP && "Template parameter not of incomplete array type");
1723
1725 S, TemplateParams, IAP->getElementType(), IAA->getElementType(), Info,
1726 Deduced, TDF & TDF_IgnoreQualifiers);
1727 }
1728
1729 // T [integer-constant]
1730 case Type::ConstantArray: {
1731 const auto *CAA = S.Context.getAsConstantArrayType(A),
1733 assert(CAP);
1734 if (!CAA || CAA->getSize() != CAP->getSize())
1736
1738 S, TemplateParams, CAP->getElementType(), CAA->getElementType(), Info,
1739 Deduced, TDF & TDF_IgnoreQualifiers);
1740 }
1741
1742 // type [i]
1743 case Type::DependentSizedArray: {
1744 const auto *AA = S.Context.getAsArrayType(A);
1745 if (!AA)
1747
1748 // Check the element type of the arrays
1749 const auto *DAP = S.Context.getAsDependentSizedArrayType(P);
1750 assert(DAP);
1752 S, TemplateParams, DAP->getElementType(), AA->getElementType(),
1753 Info, Deduced, TDF & TDF_IgnoreQualifiers))
1754 return Result;
1755
1756 // Determine the array bound is something we can deduce.
1757 const NonTypeTemplateParmDecl *NTTP =
1758 getDeducedParameterFromExpr(Info, DAP->getSizeExpr());
1759 if (!NTTP)
1760 return Sema::TDK_Success;
1761
1762 // We can perform template argument deduction for the given non-type
1763 // template parameter.
1764 assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1765 "saw non-type template parameter with wrong depth");
1766 if (const auto *CAA = dyn_cast<ConstantArrayType>(AA)) {
1767 llvm::APSInt Size(CAA->getSize());
1769 S, TemplateParams, NTTP, Size, S.Context.getSizeType(),
1770 /*ArrayBound=*/true, Info, Deduced);
1771 }
1772 if (const auto *DAA = dyn_cast<DependentSizedArrayType>(AA))
1773 if (DAA->getSizeExpr())
1775 S, TemplateParams, NTTP, DAA->getSizeExpr(), Info, Deduced);
1776
1777 // Incomplete type does not match a dependently-sized array type
1779 }
1780
1781 // type(*)(T)
1782 // T(*)()
1783 // T(*)(T)
1784 case Type::FunctionProto: {
1785 const auto *FPP = P->castAs<FunctionProtoType>(),
1786 *FPA = A->getAs<FunctionProtoType>();
1787 if (!FPA)
1789
1790 if (FPP->getMethodQuals() != FPA->getMethodQuals() ||
1791 FPP->getRefQualifier() != FPA->getRefQualifier() ||
1792 FPP->isVariadic() != FPA->isVariadic())
1794
1795 // Check return types.
1797 S, TemplateParams, FPP->getReturnType(), FPA->getReturnType(),
1798 Info, Deduced, 0,
1799 /*PartialOrdering=*/false,
1800 /*DeducedFromArrayBound=*/false))
1801 return Result;
1802
1803 // Check parameter types.
1805 S, TemplateParams, FPP->param_type_begin(), FPP->getNumParams(),
1806 FPA->param_type_begin(), FPA->getNumParams(), Info, Deduced,
1808 return Result;
1809
1811 return Sema::TDK_Success;
1812
1813 // FIXME: Per core-2016/10/1019 (no corresponding core issue yet), permit
1814 // deducing through the noexcept-specifier if it's part of the canonical
1815 // type. libstdc++ relies on this.
1816 Expr *NoexceptExpr = FPP->getNoexceptExpr();
1817 if (const NonTypeTemplateParmDecl *NTTP =
1818 NoexceptExpr ? getDeducedParameterFromExpr(Info, NoexceptExpr)
1819 : nullptr) {
1820 assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1821 "saw non-type template parameter with wrong depth");
1822
1823 llvm::APSInt Noexcept(1);
1824 switch (FPA->canThrow()) {
1825 case CT_Cannot:
1826 Noexcept = 1;
1827 [[fallthrough]];
1828
1829 case CT_Can:
1830 // We give E in noexcept(E) the "deduced from array bound" treatment.
1831 // FIXME: Should we?
1833 S, TemplateParams, NTTP, Noexcept, S.Context.BoolTy,
1834 /*DeducedFromArrayBound=*/true, Info, Deduced);
1835
1836 case CT_Dependent:
1837 if (Expr *ArgNoexceptExpr = FPA->getNoexceptExpr())
1839 S, TemplateParams, NTTP, ArgNoexceptExpr, Info, Deduced);
1840 // Can't deduce anything from throw(T...).
1841 break;
1842 }
1843 }
1844 // FIXME: Detect non-deduced exception specification mismatches?
1845 //
1846 // Careful about [temp.deduct.call] and [temp.deduct.conv], which allow
1847 // top-level differences in noexcept-specifications.
1848
1849 return Sema::TDK_Success;
1850 }
1851
1852 case Type::InjectedClassName:
1853 // Treat a template's injected-class-name as if the template
1854 // specialization type had been used.
1855
1856 // template-name<T> (where template-name refers to a class template)
1857 // template-name<i>
1858 // TT<T>
1859 // TT<i>
1860 // TT<>
1861 case Type::TemplateSpecialization: {
1862 // When Arg cannot be a derived class, we can just try to deduce template
1863 // arguments from the template-id.
1864 if (!(TDF & TDF_DerivedClass) || !A->isRecordType())
1865 return DeduceTemplateSpecArguments(S, TemplateParams, P, A, Info,
1866 Deduced);
1867
1868 SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(),
1869 Deduced.end());
1870
1871 auto Result =
1872 DeduceTemplateSpecArguments(S, TemplateParams, P, A, Info, Deduced);
1874 return Result;
1875
1876 // We cannot inspect base classes as part of deduction when the type
1877 // is incomplete, so either instantiate any templates necessary to
1878 // complete the type, or skip over it if it cannot be completed.
1879 if (!S.isCompleteType(Info.getLocation(), A))
1880 return Result;
1881
1882 // Reset the incorrectly deduced argument from above.
1883 Deduced = DeducedOrig;
1884
1885 // Check bases according to C++14 [temp.deduct.call] p4b3:
1887 TemplateParams, P, Info, Deduced);
1889 }
1890
1891 // T type::*
1892 // T T::*
1893 // T (type::*)()
1894 // type (T::*)()
1895 // type (type::*)(T)
1896 // type (T::*)(T)
1897 // T (type::*)(T)
1898 // T (T::*)()
1899 // T (T::*)(T)
1900 case Type::MemberPointer: {
1901 const auto *MPP = P->castAs<MemberPointerType>(),
1902 *MPA = A->getAs<MemberPointerType>();
1903 if (!MPA)
1905
1906 QualType PPT = MPP->getPointeeType();
1907 if (PPT->isFunctionType())
1908 S.adjustMemberFunctionCC(PPT, /*IsStatic=*/true,
1909 /*IsCtorOrDtor=*/false, Info.getLocation());
1910 QualType APT = MPA->getPointeeType();
1911 if (APT->isFunctionType())
1912 S.adjustMemberFunctionCC(APT, /*IsStatic=*/true,
1913 /*IsCtorOrDtor=*/false, Info.getLocation());
1914
1915 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1917 S, TemplateParams, PPT, APT, Info, Deduced, SubTDF))
1918 return Result;
1920 S, TemplateParams, QualType(MPP->getClass(), 0),
1921 QualType(MPA->getClass(), 0), Info, Deduced, SubTDF);
1922 }
1923
1924 // (clang extension)
1925 //
1926 // type(^)(T)
1927 // T(^)()
1928 // T(^)(T)
1929 case Type::BlockPointer: {
1930 const auto *BPP = P->castAs<BlockPointerType>(),
1931 *BPA = A->getAs<BlockPointerType>();
1932 if (!BPA)
1935 S, TemplateParams, BPP->getPointeeType(), BPA->getPointeeType(), Info,
1936 Deduced, 0);
1937 }
1938
1939 // (clang extension)
1940 //
1941 // T __attribute__(((ext_vector_type(<integral constant>))))
1942 case Type::ExtVector: {
1943 const auto *VP = P->castAs<ExtVectorType>();
1944 QualType ElementType;
1945 if (const auto *VA = A->getAs<ExtVectorType>()) {
1946 // Make sure that the vectors have the same number of elements.
1947 if (VP->getNumElements() != VA->getNumElements())
1949 ElementType = VA->getElementType();
1950 } else if (const auto *VA = A->getAs<DependentSizedExtVectorType>()) {
1951 // We can't check the number of elements, since the argument has a
1952 // dependent number of elements. This can only occur during partial
1953 // ordering.
1954 ElementType = VA->getElementType();
1955 } else {
1957 }
1958 // Perform deduction on the element types.
1960 S, TemplateParams, VP->getElementType(), ElementType, Info, Deduced,
1961 TDF);
1962 }
1963
1964 case Type::DependentVector: {
1965 const auto *VP = P->castAs<DependentVectorType>();
1966
1967 if (const auto *VA = A->getAs<VectorType>()) {
1968 // Perform deduction on the element types.
1970 S, TemplateParams, VP->getElementType(), VA->getElementType(),
1971 Info, Deduced, TDF))
1972 return Result;
1973
1974 // Perform deduction on the vector size, if we can.
1975 const NonTypeTemplateParmDecl *NTTP =
1976 getDeducedParameterFromExpr(Info, VP->getSizeExpr());
1977 if (!NTTP)
1978 return Sema::TDK_Success;
1979
1980 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1981 ArgSize = VA->getNumElements();
1982 // Note that we use the "array bound" rules here; just like in that
1983 // case, we don't have any particular type for the vector size, but
1984 // we can provide one if necessary.
1985 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
1986 S.Context.UnsignedIntTy, true,
1987 Info, Deduced);
1988 }
1989
1990 if (const auto *VA = A->getAs<DependentVectorType>()) {
1991 // Perform deduction on the element types.
1993 S, TemplateParams, VP->getElementType(), VA->getElementType(),
1994 Info, Deduced, TDF))
1995 return Result;
1996
1997 // Perform deduction on the vector size, if we can.
1998 const NonTypeTemplateParmDecl *NTTP =
1999 getDeducedParameterFromExpr(Info, VP->getSizeExpr());
2000 if (!NTTP)
2001 return Sema::TDK_Success;
2002
2003 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2004 VA->getSizeExpr(), Info, Deduced);
2005 }
2006
2008 }
2009
2010 // (clang extension)
2011 //
2012 // T __attribute__(((ext_vector_type(N))))
2013 case Type::DependentSizedExtVector: {
2014 const auto *VP = P->castAs<DependentSizedExtVectorType>();
2015
2016 if (const auto *VA = A->getAs<ExtVectorType>()) {
2017 // Perform deduction on the element types.
2019 S, TemplateParams, VP->getElementType(), VA->getElementType(),
2020 Info, Deduced, TDF))
2021 return Result;
2022
2023 // Perform deduction on the vector size, if we can.
2024 const NonTypeTemplateParmDecl *NTTP =
2025 getDeducedParameterFromExpr(Info, VP->getSizeExpr());
2026 if (!NTTP)
2027 return Sema::TDK_Success;
2028
2029 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
2030 ArgSize = VA->getNumElements();
2031 // Note that we use the "array bound" rules here; just like in that
2032 // case, we don't have any particular type for the vector size, but
2033 // we can provide one if necessary.
2034 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
2035 S.Context.IntTy, true, Info,
2036 Deduced);
2037 }
2038
2039 if (const auto *VA = A->getAs<DependentSizedExtVectorType>()) {
2040 // Perform deduction on the element types.
2042 S, TemplateParams, VP->getElementType(), VA->getElementType(),
2043 Info, Deduced, TDF))
2044 return Result;
2045
2046 // Perform deduction on the vector size, if we can.
2047 const NonTypeTemplateParmDecl *NTTP =
2048 getDeducedParameterFromExpr(Info, VP->getSizeExpr());
2049 if (!NTTP)
2050 return Sema::TDK_Success;
2051
2052 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2053 VA->getSizeExpr(), Info, Deduced);
2054 }
2055
2057 }
2058
2059 // (clang extension)
2060 //
2061 // T __attribute__((matrix_type(<integral constant>,
2062 // <integral constant>)))
2063 case Type::ConstantMatrix: {
2064 const auto *MP = P->castAs<ConstantMatrixType>(),
2065 *MA = A->getAs<ConstantMatrixType>();
2066 if (!MA)
2068
2069 // Check that the dimensions are the same
2070 if (MP->getNumRows() != MA->getNumRows() ||
2071 MP->getNumColumns() != MA->getNumColumns()) {
2073 }
2074 // Perform deduction on element types.
2076 S, TemplateParams, MP->getElementType(), MA->getElementType(), Info,
2077 Deduced, TDF);
2078 }
2079
2080 case Type::DependentSizedMatrix: {
2081 const auto *MP = P->castAs<DependentSizedMatrixType>();
2082 const auto *MA = A->getAs<MatrixType>();
2083 if (!MA)
2085
2086 // Check the element type of the matrixes.
2088 S, TemplateParams, MP->getElementType(), MA->getElementType(),
2089 Info, Deduced, TDF))
2090 return Result;
2091
2092 // Try to deduce a matrix dimension.
2093 auto DeduceMatrixArg =
2094 [&S, &Info, &Deduced, &TemplateParams](
2095 Expr *ParamExpr, const MatrixType *A,
2096 unsigned (ConstantMatrixType::*GetArgDimension)() const,
2097 Expr *(DependentSizedMatrixType::*GetArgDimensionExpr)() const) {
2098 const auto *ACM = dyn_cast<ConstantMatrixType>(A);
2099 const auto *ADM = dyn_cast<DependentSizedMatrixType>(A);
2100 if (!ParamExpr->isValueDependent()) {
2101 std::optional<llvm::APSInt> ParamConst =
2102 ParamExpr->getIntegerConstantExpr(S.Context);
2103 if (!ParamConst)
2105
2106 if (ACM) {
2107 if ((ACM->*GetArgDimension)() == *ParamConst)
2108 return Sema::TDK_Success;
2110 }
2111
2112 Expr *ArgExpr = (ADM->*GetArgDimensionExpr)();
2113 if (std::optional<llvm::APSInt> ArgConst =
2114 ArgExpr->getIntegerConstantExpr(S.Context))
2115 if (*ArgConst == *ParamConst)
2116 return Sema::TDK_Success;
2118 }
2119
2120 const NonTypeTemplateParmDecl *NTTP =
2121 getDeducedParameterFromExpr(Info, ParamExpr);
2122 if (!NTTP)
2123 return Sema::TDK_Success;
2124
2125 if (ACM) {
2126 llvm::APSInt ArgConst(
2128 ArgConst = (ACM->*GetArgDimension)();
2130 S, TemplateParams, NTTP, ArgConst, S.Context.getSizeType(),
2131 /*ArrayBound=*/true, Info, Deduced);
2132 }
2133
2134 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2135 (ADM->*GetArgDimensionExpr)(),
2136 Info, Deduced);
2137 };
2138
2139 if (auto Result = DeduceMatrixArg(MP->getRowExpr(), MA,
2142 return Result;
2143
2144 return DeduceMatrixArg(MP->getColumnExpr(), MA,
2147 }
2148
2149 // (clang extension)
2150 //
2151 // T __attribute__(((address_space(N))))
2152 case Type::DependentAddressSpace: {
2153 const auto *ASP = P->castAs<DependentAddressSpaceType>();
2154
2155 if (const auto *ASA = A->getAs<DependentAddressSpaceType>()) {
2156 // Perform deduction on the pointer type.
2158 S, TemplateParams, ASP->getPointeeType(), ASA->getPointeeType(),
2159 Info, Deduced, TDF))
2160 return Result;
2161
2162 // Perform deduction on the address space, if we can.
2163 const NonTypeTemplateParmDecl *NTTP =
2164 getDeducedParameterFromExpr(Info, ASP->getAddrSpaceExpr());
2165 if (!NTTP)
2166 return Sema::TDK_Success;
2167
2169 S, TemplateParams, NTTP, ASA->getAddrSpaceExpr(), Info, Deduced);
2170 }
2171
2173 llvm::APSInt ArgAddressSpace(S.Context.getTypeSize(S.Context.IntTy),
2174 false);
2175 ArgAddressSpace = toTargetAddressSpace(A.getAddressSpace());
2176
2177 // Perform deduction on the pointer types.
2179 S, TemplateParams, ASP->getPointeeType(),
2180 S.Context.removeAddrSpaceQualType(A), Info, Deduced, TDF))
2181 return Result;
2182
2183 // Perform deduction on the address space, if we can.
2184 const NonTypeTemplateParmDecl *NTTP =
2185 getDeducedParameterFromExpr(Info, ASP->getAddrSpaceExpr());
2186 if (!NTTP)
2187 return Sema::TDK_Success;
2188
2189 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2190 ArgAddressSpace, S.Context.IntTy,
2191 true, Info, Deduced);
2192 }
2193
2195 }
2196 case Type::DependentBitInt: {
2197 const auto *IP = P->castAs<DependentBitIntType>();
2198
2199 if (const auto *IA = A->getAs<BitIntType>()) {
2200 if (IP->isUnsigned() != IA->isUnsigned())
2202
2203 const NonTypeTemplateParmDecl *NTTP =
2204 getDeducedParameterFromExpr(Info, IP->getNumBitsExpr());
2205 if (!NTTP)
2206 return Sema::TDK_Success;
2207
2208 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
2209 ArgSize = IA->getNumBits();
2210
2211 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
2212 S.Context.IntTy, true, Info,
2213 Deduced);
2214 }
2215
2216 if (const auto *IA = A->getAs<DependentBitIntType>()) {
2217 if (IP->isUnsigned() != IA->isUnsigned())
2219 return Sema::TDK_Success;
2220 }
2221
2223 }
2224
2225 case Type::TypeOfExpr:
2226 case Type::TypeOf:
2227 case Type::DependentName:
2228 case Type::UnresolvedUsing:
2229 case Type::Decltype:
2230 case Type::UnaryTransform:
2231 case Type::DeducedTemplateSpecialization:
2232 case Type::DependentTemplateSpecialization:
2233 case Type::PackExpansion:
2234 case Type::Pipe:
2235 // No template argument deduction for these types
2236 return Sema::TDK_Success;
2237 }
2238
2239 llvm_unreachable("Invalid Type Class!");
2240}
2241
2247 // If the template argument is a pack expansion, perform template argument
2248 // deduction against the pattern of that expansion. This only occurs during
2249 // partial ordering.
2250 if (A.isPackExpansion())
2252
2253 switch (P.getKind()) {
2255 llvm_unreachable("Null template argument in parameter list");
2256
2260 S, TemplateParams, P.getAsType(), A.getAsType(), Info, Deduced, 0);
2261 Info.FirstArg = P;
2262 Info.SecondArg = A;
2264
2267 return DeduceTemplateArguments(S, TemplateParams, P.getAsTemplate(),
2268 A.getAsTemplate(), Info, Deduced);
2269 Info.FirstArg = P;
2270 Info.SecondArg = A;
2272
2274 llvm_unreachable("caller should handle pack expansions");
2275
2278 isSameDeclaration(P.getAsDecl(), A.getAsDecl()))
2279 return Sema::TDK_Success;
2280
2281 Info.FirstArg = P;
2282 Info.SecondArg = A;
2284
2287 S.Context.hasSameType(P.getNullPtrType(), A.getNullPtrType()))
2288 return Sema::TDK_Success;
2289
2290 Info.FirstArg = P;
2291 Info.SecondArg = A;
2293
2296 if (hasSameExtendedValue(P.getAsIntegral(), A.getAsIntegral()))
2297 return Sema::TDK_Success;
2298 }
2299 Info.FirstArg = P;
2300 Info.SecondArg = A;
2302
2304 if (const NonTypeTemplateParmDecl *NTTP =
2305 getDeducedParameterFromExpr(Info, P.getAsExpr())) {
2308 S, TemplateParams, NTTP, A.getAsIntegral(), A.getIntegralType(),
2309 /*ArrayBound=*/false, Info, Deduced);
2311 return DeduceNullPtrTemplateArgument(S, TemplateParams, NTTP,
2312 A.getNullPtrType(), Info, Deduced);
2314 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2315 A.getAsExpr(), Info, Deduced);
2318 S, TemplateParams, NTTP, A.getAsDecl(), A.getParamTypeForDecl(),
2319 Info, Deduced);
2320
2321 Info.FirstArg = P;
2322 Info.SecondArg = A;
2324 }
2325
2326 // Can't deduce anything, but that's okay.
2327 return Sema::TDK_Success;
2329 llvm_unreachable("Argument packs should be expanded by the caller!");
2330 }
2331
2332 llvm_unreachable("Invalid TemplateArgument Kind!");
2333}
2334
2335/// Determine whether there is a template argument to be used for
2336/// deduction.
2337///
2338/// This routine "expands" argument packs in-place, overriding its input
2339/// parameters so that \c Args[ArgIdx] will be the available template argument.
2340///
2341/// \returns true if there is another template argument (which will be at
2342/// \c Args[ArgIdx]), false otherwise.
2344 unsigned &ArgIdx) {
2345 if (ArgIdx == Args.size())
2346 return false;
2347
2348 const TemplateArgument &Arg = Args[ArgIdx];
2349 if (Arg.getKind() != TemplateArgument::Pack)
2350 return true;
2351
2352 assert(ArgIdx == Args.size() - 1 && "Pack not at the end of argument list?");
2353 Args = Arg.pack_elements();
2354 ArgIdx = 0;
2355 return ArgIdx < Args.size();
2356}
2357
2358/// Determine whether the given set of template arguments has a pack
2359/// expansion that is not the last template argument.
2361 bool FoundPackExpansion = false;
2362 for (const auto &A : Args) {
2363 if (FoundPackExpansion)
2364 return true;
2365
2366 if (A.getKind() == TemplateArgument::Pack)
2367 return hasPackExpansionBeforeEnd(A.pack_elements());
2368
2369 // FIXME: If this is a fixed-arity pack expansion from an outer level of
2370 // templates, it should not be treated as a pack expansion.
2371 if (A.isPackExpansion())
2372 FoundPackExpansion = true;
2373 }
2374
2375 return false;
2376}
2377
2384 bool NumberOfArgumentsMustMatch) {
2385 // C++0x [temp.deduct.type]p9:
2386 // If the template argument list of P contains a pack expansion that is not
2387 // the last template argument, the entire template argument list is a
2388 // non-deduced context.
2390 return Sema::TDK_Success;
2391
2392 // C++0x [temp.deduct.type]p9:
2393 // If P has a form that contains <T> or <i>, then each argument Pi of the
2394 // respective template argument list P is compared with the corresponding
2395 // argument Ai of the corresponding template argument list of A.
2396 unsigned ArgIdx = 0, ParamIdx = 0;
2398 const TemplateArgument &P = Ps[ParamIdx];
2399 if (!P.isPackExpansion()) {
2400 // The simple case: deduce template arguments by matching Pi and Ai.
2401
2402 // Check whether we have enough arguments.
2403 if (!hasTemplateArgumentForDeduction(As, ArgIdx))
2404 return NumberOfArgumentsMustMatch
2407
2408 // C++1z [temp.deduct.type]p9:
2409 // During partial ordering, if Ai was originally a pack expansion [and]
2410 // Pi is not a pack expansion, template argument deduction fails.
2411 if (As[ArgIdx].isPackExpansion())
2413
2414 // Perform deduction for this Pi/Ai pair.
2415 if (auto Result = DeduceTemplateArguments(S, TemplateParams, P,
2416 As[ArgIdx], Info, Deduced))
2417 return Result;
2418
2419 // Move to the next argument.
2420 ++ArgIdx;
2421 continue;
2422 }
2423
2424 // The parameter is a pack expansion.
2425
2426 // C++0x [temp.deduct.type]p9:
2427 // If Pi is a pack expansion, then the pattern of Pi is compared with
2428 // each remaining argument in the template argument list of A. Each
2429 // comparison deduces template arguments for subsequent positions in the
2430 // template parameter packs expanded by Pi.
2431 TemplateArgument Pattern = P.getPackExpansionPattern();
2432
2433 // Prepare to deduce the packs within the pattern.
2434 PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
2435
2436 // Keep track of the deduced template arguments for each parameter pack
2437 // expanded by this pack expansion (the outer index) and for each
2438 // template argument (the inner SmallVectors).
2439 for (; hasTemplateArgumentForDeduction(As, ArgIdx) &&
2440 PackScope.hasNextElement();
2441 ++ArgIdx) {
2442 // Deduce template arguments from the pattern.
2443 if (auto Result = DeduceTemplateArguments(S, TemplateParams, Pattern,
2444 As[ArgIdx], Info, Deduced))
2445 return Result;
2446
2447 PackScope.nextPackElement();
2448 }
2449
2450 // Build argument packs for each of the parameter packs expanded by this
2451 // pack expansion.
2452 if (auto Result = PackScope.finish())
2453 return Result;
2454 }
2455
2456 return Sema::TDK_Success;
2457}
2458
2461 const TemplateArgumentList &ParamList,
2462 const TemplateArgumentList &ArgList,
2465 return DeduceTemplateArguments(S, TemplateParams, ParamList.asArray(),
2466 ArgList.asArray(), Info, Deduced,
2467 /*NumberOfArgumentsMustMatch=*/false);
2468}
2469
2470/// Determine whether two template arguments are the same.
2471static bool isSameTemplateArg(ASTContext &Context,
2473 const TemplateArgument &Y,
2474 bool PartialOrdering,
2475 bool PackExpansionMatchesPack = false) {
2476 // If we're checking deduced arguments (X) against original arguments (Y),
2477 // we will have flattened packs to non-expansions in X.
2478 if (PackExpansionMatchesPack && X.isPackExpansion() && !Y.isPackExpansion())
2479 X = X.getPackExpansionPattern();
2480
2481 if (X.getKind() != Y.getKind())
2482 return false;
2483
2484 switch (X.getKind()) {
2486 llvm_unreachable("Comparing NULL template argument");
2487
2489 return Context.getCanonicalType(X.getAsType()) ==
2490 Context.getCanonicalType(Y.getAsType());
2491
2493 return isSameDeclaration(X.getAsDecl(), Y.getAsDecl());
2494
2496 return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
2497
2500 return Context.getCanonicalTemplateName(
2501 X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
2504
2506 return hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral());
2507
2509 llvm::FoldingSetNodeID XID, YID;
2510 X.getAsExpr()->Profile(XID, Context, true);
2511 Y.getAsExpr()->Profile(YID, Context, true);
2512 return XID == YID;
2513 }
2514
2516 unsigned PackIterationSize = X.pack_size();
2517 if (X.pack_size() != Y.pack_size()) {
2518 if (!PartialOrdering)
2519 return false;
2520
2521 // C++0x [temp.deduct.type]p9:
2522 // During partial ordering, if Ai was originally a pack expansion:
2523 // - if P does not contain a template argument corresponding to Ai
2524 // then Ai is ignored;
2525 bool XHasMoreArg = X.pack_size() > Y.pack_size();
2526 if (!(XHasMoreArg && X.pack_elements().back().isPackExpansion()) &&
2527 !(!XHasMoreArg && Y.pack_elements().back().isPackExpansion()))
2528 return false;
2529
2530 if (XHasMoreArg)
2531 PackIterationSize = Y.pack_size();
2532 }
2533
2534 ArrayRef<TemplateArgument> XP = X.pack_elements();
2536 for (unsigned i = 0; i < PackIterationSize; ++i)
2537 if (!isSameTemplateArg(Context, XP[i], YP[i], PartialOrdering,
2538 PackExpansionMatchesPack))
2539 return false;
2540 return true;
2541 }
2542 }
2543
2544 llvm_unreachable("Invalid TemplateArgument Kind!");
2545}
2546
2547/// Allocate a TemplateArgumentLoc where all locations have
2548/// been initialized to the given location.
2549///
2550/// \param Arg The template argument we are producing template argument
2551/// location information for.
2552///
2553/// \param NTTPType For a declaration template argument, the type of
2554/// the non-type template parameter that corresponds to this template
2555/// argument. Can be null if no type sugar is available to add to the
2556/// type from the template argument.
2557///
2558/// \param Loc The source location to use for the resulting template
2559/// argument.
2562 QualType NTTPType, SourceLocation Loc) {
2563 switch (Arg.getKind()) {
2565 llvm_unreachable("Can't get a NULL template argument here");
2566
2568 return TemplateArgumentLoc(
2569 Arg, Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
2570
2572 if (NTTPType.isNull())
2573 NTTPType = Arg.getParamTypeForDecl();
2574 Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2575 .getAs<Expr>();
2577 }
2578
2580 if (NTTPType.isNull())
2581 NTTPType = Arg.getNullPtrType();
2582 Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2583 .getAs<Expr>();
2584 return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true),
2585 E);
2586 }
2587
2589 Expr *E =
2592 }
2593
2599 Builder.MakeTrivial(Context, DTN->getQualifier(), Loc);
2600 else if (QualifiedTemplateName *QTN =
2601 Template.getAsQualifiedTemplateName())
2602 Builder.MakeTrivial(Context, QTN->getQualifier(), Loc);
2603
2605 return TemplateArgumentLoc(Context, Arg,
2606 Builder.getWithLocInContext(Context), Loc);
2607
2608 return TemplateArgumentLoc(
2609 Context, Arg, Builder.getWithLocInContext(Context), Loc, Loc);
2610 }
2611
2613 return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2614
2617 }
2618
2619 llvm_unreachable("Invalid TemplateArgument Kind!");
2620}
2621
2624 SourceLocation Location) {
2626 Context.getInjectedTemplateArg(TemplateParm), QualType(), Location);
2627}
2628
2629/// Convert the given deduced template argument and add it to the set of
2630/// fully-converted template arguments.
2632 Sema &S, NamedDecl *Param, DeducedTemplateArgument Arg, NamedDecl *Template,
2633 TemplateDeductionInfo &Info, bool IsDeduced,
2634 SmallVectorImpl<TemplateArgument> &SugaredOutput,
2635 SmallVectorImpl<TemplateArgument> &CanonicalOutput) {
2636 auto ConvertArg = [&](DeducedTemplateArgument Arg,
2637 unsigned ArgumentPackIndex) {
2638 // Convert the deduced template argument into a template
2639 // argument that we can check, almost as if the user had written
2640 // the template argument explicitly.
2641 TemplateArgumentLoc ArgLoc =
2643
2644 // Check the template argument, converting it as necessary.
2645 return S.CheckTemplateArgument(
2646 Param, ArgLoc, Template, Template->getLocation(),
2647 Template->getSourceRange().getEnd(), ArgumentPackIndex, SugaredOutput,
2648 CanonicalOutput,
2649 IsDeduced
2653 };
2654
2655 if (Arg.getKind() == TemplateArgument::Pack) {
2656 // This is a template argument pack, so check each of its arguments against
2657 // the template parameter.
2658 SmallVector<TemplateArgument, 2> SugaredPackedArgsBuilder,
2659 CanonicalPackedArgsBuilder;
2660 for (const auto &P : Arg.pack_elements()) {
2661 // When converting the deduced template argument, append it to the
2662 // general output list. We need to do this so that the template argument
2663 // checking logic has all of the prior template arguments available.
2664 DeducedTemplateArgument InnerArg(P);
2666 assert(InnerArg.getKind() != TemplateArgument::Pack &&
2667 "deduced nested pack");
2668 if (P.isNull()) {
2669 // We deduced arguments for some elements of this pack, but not for
2670 // all of them. This happens if we get a conditionally-non-deduced
2671 // context in a pack expansion (such as an overload set in one of the
2672 // arguments).
2673 S.Diag(Param->getLocation(),
2674 diag::err_template_arg_deduced_incomplete_pack)
2675 << Arg << Param;
2676 return true;
2677 }
2678 if (ConvertArg(InnerArg, SugaredPackedArgsBuilder.size()))
2679 return true;
2680
2681 // Move the converted template argument into our argument pack.
2682 SugaredPackedArgsBuilder.push_back(SugaredOutput.pop_back_val());
2683 CanonicalPackedArgsBuilder.push_back(CanonicalOutput.pop_back_val());
2684 }
2685
2686 // If the pack is empty, we still need to substitute into the parameter
2687 // itself, in case that substitution fails.
2688 if (SugaredPackedArgsBuilder.empty()) {
2690 MultiLevelTemplateArgumentList Args(Template, SugaredOutput,
2691 /*Final=*/true);
2692
2693 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2694 Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2695 NTTP, SugaredOutput,
2696 Template->getSourceRange());
2697 if (Inst.isInvalid() ||
2698 S.SubstType(NTTP->getType(), Args, NTTP->getLocation(),
2699 NTTP->getDeclName()).isNull())
2700 return true;
2701 } else if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(Param)) {
2702 Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2703 TTP, SugaredOutput,
2704 Template->getSourceRange());
2705 if (Inst.isInvalid() || !S.SubstDecl(TTP, S.CurContext, Args))
2706 return true;
2707 }
2708 // For type parameters, no substitution is ever required.
2709 }
2710
2711 // Create the resulting argument pack.
2712 SugaredOutput.push_back(
2713 TemplateArgument::CreatePackCopy(S.Context, SugaredPackedArgsBuilder));
2714 CanonicalOutput.push_back(TemplateArgument::CreatePackCopy(
2715 S.Context, CanonicalPackedArgsBuilder));
2716 return false;
2717 }
2718
2719 return ConvertArg(Arg, 0);
2720}
2721
2722// FIXME: This should not be a template, but
2723// ClassTemplatePartialSpecializationDecl sadly does not derive from
2724// TemplateDecl.
2725template <typename TemplateDeclT>
2727 Sema &S, TemplateDeclT *Template, bool IsDeduced,
2730 SmallVectorImpl<TemplateArgument> &SugaredBuilder,
2731 SmallVectorImpl<TemplateArgument> &CanonicalBuilder,
2732 LocalInstantiationScope *CurrentInstantiationScope = nullptr,
2733 unsigned NumAlreadyConverted = 0, bool PartialOverloading = false) {
2734 TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2735
2736 for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2737 NamedDecl *Param = TemplateParams->getParam(I);
2738
2739 // C++0x [temp.arg.explicit]p3:
2740 // A trailing template parameter pack (14.5.3) not otherwise deduced will
2741 // be deduced to an empty sequence of template arguments.
2742 // FIXME: Where did the word "trailing" come from?
2743 if (Deduced[I].isNull() && Param->isTemplateParameterPack()) {
2744 if (auto Result =
2745 PackDeductionScope(S, TemplateParams, Deduced, Info, I).finish())
2746 return Result;
2747 }
2748
2749 if (!Deduced[I].isNull()) {
2750 if (I < NumAlreadyConverted) {
2751 // We may have had explicitly-specified template arguments for a
2752 // template parameter pack (that may or may not have been extended
2753 // via additional deduced arguments).
2754 if (Param->isParameterPack() && CurrentInstantiationScope &&
2755 CurrentInstantiationScope->getPartiallySubstitutedPack() == Param) {
2756 // Forget the partially-substituted pack; its substitution is now
2757 // complete.
2758 CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2759 // We still need to check the argument in case it was extended by
2760 // deduction.
2761 } else {
2762 // We have already fully type-checked and converted this
2763 // argument, because it was explicitly-specified. Just record the
2764 // presence of this argument.
2765 SugaredBuilder.push_back(Deduced[I]);
2766 CanonicalBuilder.push_back(
2768 continue;
2769 }
2770 }
2771
2772 // We may have deduced this argument, so it still needs to be
2773 // checked and converted.
2774 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info,
2775 IsDeduced, SugaredBuilder,
2776 CanonicalBuilder)) {
2777 Info.Param = makeTemplateParameter(Param);
2778 // FIXME: These template arguments are temporary. Free them!
2779 Info.reset(
2780 TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder),
2781 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder));
2783 }
2784
2785 continue;
2786 }
2787
2788 // Substitute into the default template argument, if available.
2789 bool HasDefaultArg = false;
2790 TemplateDecl *TD = dyn_cast<TemplateDecl>(Template);
2791 if (!TD) {
2792 assert(isa<ClassTemplatePartialSpecializationDecl>(Template) ||
2793 isa<VarTemplatePartialSpecializationDecl>(Template));
2794 return Sema::TDK_Incomplete;
2795 }
2796
2797 TemplateArgumentLoc DefArg;
2798 {
2799 Qualifiers ThisTypeQuals;
2800 CXXRecordDecl *ThisContext = nullptr;
2801 if (auto *Rec = dyn_cast<CXXRecordDecl>(TD->getDeclContext()))
2802 if (Rec->isLambda())
2803 if (auto *Method = dyn_cast<CXXMethodDecl>(Rec->getDeclContext())) {
2804 ThisContext = Method->getParent();
2805 ThisTypeQuals = Method->getMethodQualifiers();
2806 }
2807
2808 Sema::CXXThisScopeRAII ThisScope(S, ThisContext, ThisTypeQuals,
2809 S.getLangOpts().CPlusPlus17);
2810
2812 TD, TD->getLocation(), TD->getSourceRange().getEnd(), Param,
2813 SugaredBuilder, CanonicalBuilder, HasDefaultArg);
2814 }
2815
2816 // If there was no default argument, deduction is incomplete.
2817 if (DefArg.getArgument().isNull()) {
2819 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2820 Info.reset(TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder),
2821 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder));
2822 if (PartialOverloading) break;
2823
2824 return HasDefaultArg ? Sema::TDK_SubstitutionFailure
2826 }
2827
2828 // Check whether we can actually use the default argument.
2830 Param, DefArg, TD, TD->getLocation(), TD->getSourceRange().getEnd(),
2831 0, SugaredBuilder, CanonicalBuilder, Sema::CTAK_Specified)) {
2833 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2834 // FIXME: These template arguments are temporary. Free them!
2835 Info.reset(TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder),
2836 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder));
2838 }
2839
2840 // If we get here, we successfully used the default template argument.
2841 }
2842
2843 return Sema::TDK_Success;
2844}
2845
2847 if (auto *DC = dyn_cast<DeclContext>(D))
2848 return DC;
2849 return D->getDeclContext();
2850}
2851
2852template<typename T> struct IsPartialSpecialization {
2853 static constexpr bool value = false;
2854};
2855template<>
2857 static constexpr bool value = true;
2858};
2859template<>
2861 static constexpr bool value = true;
2862};
2863template <typename TemplateDeclT>
2864static bool DeducedArgsNeedReplacement(TemplateDeclT *Template) {
2865 return false;
2866}
2867template <>
2870 return !Spec->isClassScopeExplicitSpecialization();
2871}
2872template <>
2875 return !Spec->isClassScopeExplicitSpecialization();
2876}
2877
2878template <typename TemplateDeclT>
2880CheckDeducedArgumentConstraints(Sema &S, TemplateDeclT *Template,
2881 ArrayRef<TemplateArgument> SugaredDeducedArgs,
2882 ArrayRef<TemplateArgument> CanonicalDeducedArgs,
2883 TemplateDeductionInfo &Info) {
2884 llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
2885 Template->getAssociatedConstraints(AssociatedConstraints);
2886
2887 bool NeedsReplacement = DeducedArgsNeedReplacement(Template);
2889 CanonicalDeducedArgs};
2890
2892 Template, /*Final=*/false,
2893 /*InnerMost=*/NeedsReplacement ? nullptr : &DeducedTAL,
2894 /*RelativeToPrimary=*/true, /*Pattern=*/
2895 nullptr, /*ForConstraintInstantiation=*/true);
2896
2897 // getTemplateInstantiationArgs picks up the non-deduced version of the
2898 // template args when this is a variable template partial specialization and
2899 // not class-scope explicit specialization, so replace with Deduced Args
2900 // instead of adding to inner-most.
2901 if (NeedsReplacement)
2902 MLTAL.replaceInnermostTemplateArguments(Template, CanonicalDeducedArgs);
2903
2904 if (S.CheckConstraintSatisfaction(Template, AssociatedConstraints, MLTAL,
2905 Info.getLocation(),
2908 Info.reset(
2909 TemplateArgumentList::CreateCopy(S.Context, SugaredDeducedArgs),
2910 TemplateArgumentList::CreateCopy(S.Context, CanonicalDeducedArgs));
2912 }
2913 return Sema::TDK_Success;
2914}
2915
2916/// Complete template argument deduction for a partial specialization.
2917template <typename T>
2918static std::enable_if_t<IsPartialSpecialization<T>::value,
2921 Sema &S, T *Partial, bool IsPartialOrdering,
2922 const TemplateArgumentList &TemplateArgs,
2924 TemplateDeductionInfo &Info) {
2925 // Unevaluated SFINAE context.
2928 Sema::SFINAETrap Trap(S);
2929
2930 Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Partial));
2931
2932 // C++ [temp.deduct.type]p2:
2933 // [...] or if any template argument remains neither deduced nor
2934 // explicitly specified, template argument deduction fails.
2935 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
2937 S, Partial, IsPartialOrdering, Deduced, Info, SugaredBuilder,
2938 CanonicalBuilder))
2939 return Result;
2940
2941 // Form the template argument list from the deduced template arguments.
2942 TemplateArgumentList *SugaredDeducedArgumentList =
2943 TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder);
2944 TemplateArgumentList *CanonicalDeducedArgumentList =
2945 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder);
2946
2947 Info.reset(SugaredDeducedArgumentList, CanonicalDeducedArgumentList);
2948
2949 // Substitute the deduced template arguments into the template
2950 // arguments of the class template partial specialization, and
2951 // verify that the instantiated template arguments are both valid
2952 // and are equivalent to the template arguments originally provided
2953 // to the class template.
2954 LocalInstantiationScope InstScope(S);
2955 auto *Template = Partial->getSpecializedTemplate();
2956 const ASTTemplateArgumentListInfo *PartialTemplArgInfo =
2957 Partial->getTemplateArgsAsWritten();
2958
2959 TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2960 PartialTemplArgInfo->RAngleLoc);
2961
2962 if (S.SubstTemplateArguments(PartialTemplArgInfo->arguments(),
2964 SugaredBuilder,
2965 /*Final=*/true),
2966 InstArgs)) {
2967 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2968 if (ParamIdx >= Partial->getTemplateParameters()->size())
2969 ParamIdx = Partial->getTemplateParameters()->size() - 1;
2970
2971 Decl *Param = const_cast<NamedDecl *>(
2972 Partial->getTemplateParameters()->getParam(ParamIdx));
2973 Info.Param = makeTemplateParameter(Param);
2974 Info.FirstArg = (*PartialTemplArgInfo)[ArgIdx].getArgument();
2976 }
2977
2978 bool ConstraintsNotSatisfied;
2979 SmallVector<TemplateArgument, 4> SugaredConvertedInstArgs,
2980 CanonicalConvertedInstArgs;
2982 Template, Partial->getLocation(), InstArgs, false,
2983 SugaredConvertedInstArgs, CanonicalConvertedInstArgs,
2984 /*UpdateArgsWithConversions=*/true, &ConstraintsNotSatisfied))
2985 return ConstraintsNotSatisfied ? Sema::TDK_ConstraintsNotSatisfied
2987
2988 TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2989 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2990 TemplateArgument InstArg = SugaredConvertedInstArgs.data()[I];
2991 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg,
2992 IsPartialOrdering)) {
2993 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2994 Info.FirstArg = TemplateArgs[I];
2995 Info.SecondArg = InstArg;
2997 }
2998 }
2999
3000 if (Trap.hasErrorOccurred())
3002
3003 if (auto Result = CheckDeducedArgumentConstraints(S, Partial, SugaredBuilder,
3004 CanonicalBuilder, Info))
3005 return Result;
3006
3007 return Sema::TDK_Success;
3008}
3009
3010/// Complete template argument deduction for a class or variable template,
3011/// when partial ordering against a partial specialization.
3012// FIXME: Factor out duplication with partial specialization version above.
3014 Sema &S, TemplateDecl *Template, bool PartialOrdering,
3015 const TemplateArgumentList &TemplateArgs,
3017 TemplateDeductionInfo &Info) {
3018 // Unevaluated SFINAE context.
3021 Sema::SFINAETrap Trap(S);
3022
3023 Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Template));
3024
3025 // C++ [temp.deduct.type]p2:
3026 // [...] or if any template argument remains neither deduced nor
3027 // explicitly specified, template argument deduction fails.
3028 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
3030 S, Template, /*IsDeduced*/ PartialOrdering, Deduced, Info,
3031 SugaredBuilder, CanonicalBuilder,
3032 /*CurrentInstantiationScope=*/nullptr,
3033 /*NumAlreadyConverted=*/0U, /*PartialOverloading=*/false))
3034 return Result;
3035
3036 // Check that we produced the correct argument list.
3037 TemplateParameterList *TemplateParams = Template->getTemplateParameters();
3038 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
3039 TemplateArgument InstArg = CanonicalBuilder[I];
3040 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg, PartialOrdering,
3041 /*PackExpansionMatchesPack=*/true)) {
3042 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
3043 Info.FirstArg = TemplateArgs[I];
3044 Info.SecondArg = InstArg;
3046 }
3047 }
3048
3049 if (Trap.hasErrorOccurred())
3051
3052 if (auto Result = CheckDeducedArgumentConstraints(S, Template, SugaredBuilder,
3053 CanonicalBuilder, Info))
3054 return Result;
3055
3056 return Sema::TDK_Success;
3057}
3058
3059/// Perform template argument deduction to determine whether
3060/// the given template arguments match the given class template
3061/// partial specialization per C++ [temp.class.spec.match].
3064 const TemplateArgumentList &TemplateArgs,
3065 TemplateDeductionInfo &Info) {
3066 if (Partial->isInvalidDecl())
3067 return TDK_Invalid;
3068
3069 // C++ [temp.class.spec.match]p2:
3070 // A partial specialization matches a given actual template
3071 // argument list if the template arguments of the partial
3072 // specialization can be deduced from the actual template argument
3073 // list (14.8.2).
3074
3075 // Unevaluated SFINAE context.
3078 SFINAETrap Trap(*this);
3079
3080 // This deduction has no relation to any outer instantiation we might be
3081 // performing.
3082 LocalInstantiationScope InstantiationScope(*this);
3083
3085 Deduced.resize(Partial->getTemplateParameters()->size());
3088 Partial->getTemplateParameters(),
3089 Partial->getTemplateArgs(),
3090 TemplateArgs, Info, Deduced))
3091 return Result;
3092
3093 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3094 InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
3095 Info);
3096 if (Inst.isInvalid())
3098
3099 if (Trap.hasErrorOccurred())
3101
3104 Result = ::FinishTemplateArgumentDeduction(*this, Partial,
3105 /*IsPartialOrdering=*/false,
3106 TemplateArgs, Deduced, Info);
3107 });
3108 return Result;
3109}
3110
3111/// Perform template argument deduction to determine whether
3112/// the given template arguments match the given variable template
3113/// partial specialization per C++ [temp.class.spec.match].
3116 const TemplateArgumentList &TemplateArgs,
3117 TemplateDeductionInfo &Info) {
3118 if (Partial->isInvalidDecl())
3119 return TDK_Invalid;
3120
3121 // C++ [temp.class.spec.match]p2:
3122 // A partial specialization matches a given actual template
3123 // argument list if the template arguments of the partial
3124 // specialization can be deduced from the actual template argument
3125 // list (14.8.2).
3126
3127 // Unevaluated SFINAE context.
3130 SFINAETrap Trap(*this);
3131
3132 // This deduction has no relation to any outer instantiation we might be
3133 // performing.
3134 LocalInstantiationScope InstantiationScope(*this);
3135
3137 Deduced.resize(Partial->getTemplateParameters()->size());
3139 *this, Partial->getTemplateParameters(), Partial->getTemplateArgs(),
3140 TemplateArgs, Info, Deduced))
3141 return Result;
3142
3143 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3144 InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
3145 Info);
3146 if (Inst.isInvalid())
3148
3149 if (Trap.hasErrorOccurred())
3151
3154 Result = ::FinishTemplateArgumentDeduction(*this, Partial,
3155 /*IsPartialOrdering=*/false,
3156 TemplateArgs, Deduced, Info);
3157 });
3158 return Result;
3159}
3160
3161/// Determine whether the given type T is a simple-template-id type.
3163 if (const TemplateSpecializationType *Spec
3165 return Spec->getTemplateName().getAsTemplateDecl() != nullptr;
3166
3167 // C++17 [temp.local]p2:
3168 // the injected-class-name [...] is equivalent to the template-name followed
3169 // by the template-arguments of the class template specialization or partial
3170 // specialization enclosed in <>
3171 // ... which means it's equivalent to a simple-template-id.
3172 //
3173 // This only arises during class template argument deduction for a copy
3174 // deduction candidate, where it permits slicing.
3175 if (T->getAs<InjectedClassNameType>())
3176 return true;
3177
3178 return false;
3179}
3180
3181/// Substitute the explicitly-provided template arguments into the
3182/// given function template according to C++ [temp.arg.explicit].
3183///
3184/// \param FunctionTemplate the function template into which the explicit
3185/// template arguments will be substituted.
3186///
3187/// \param ExplicitTemplateArgs the explicitly-specified template
3188/// arguments.
3189///
3190/// \param Deduced the deduced template arguments, which will be populated
3191/// with the converted and checked explicit template arguments.
3192///
3193/// \param ParamTypes will be populated with the instantiated function
3194/// parameters.
3195///
3196/// \param FunctionType if non-NULL, the result type of the function template
3197/// will also be instantiated and the pointed-to value will be updated with
3198/// the instantiated function type.
3199///
3200/// \param Info if substitution fails for any reason, this object will be
3201/// populated with more information about the failure.
3202///
3203/// \returns TDK_Success if substitution was successful, or some failure
3204/// condition.
3206 FunctionTemplateDecl *FunctionTemplate,
3207 TemplateArgumentListInfo &ExplicitTemplateArgs,
3210 TemplateDeductionInfo &Info) {
3211 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3212 TemplateParameterList *TemplateParams
3213 = FunctionTemplate->getTemplateParameters();
3214
3215 if (ExplicitTemplateArgs.size() == 0) {
3216 // No arguments to substitute; just copy over the parameter types and
3217 // fill in the function type.
3218 for (auto *P : Function->parameters())
3219 ParamTypes.push_back(P->getType());
3220
3221 if (FunctionType)
3222 *FunctionType = Function->getType();
3223 return TDK_Success;
3224 }
3225
3226 // Unevaluated SFINAE context.
3229 SFINAETrap Trap(*this);
3230
3231 // C++ [temp.arg.explicit]p3:
3232 // Template arguments that are present shall be specified in the
3233 // declaration order of their corresponding template-parameters. The
3234 // template argument list shall not specify more template-arguments than
3235 // there are corresponding template-parameters.
3236 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
3237
3238 // Enter a new template instantiation context where we check the
3239 // explicitly-specified template arguments against this function template,
3240 // and then substitute them into the function parameter types.
3243 *this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3245 if (Inst.isInvalid())
3247
3249 ExplicitTemplateArgs, true, SugaredBuilder,
3250 CanonicalBuilder,
3251 /*UpdateArgsWithConversions=*/false) ||
3252 Trap.hasErrorOccurred()) {
3253 unsigned Index = SugaredBuilder.size();
3254 if (Index >= TemplateParams->size())
3256 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
3258 }
3259
3260 // Form the template argument list from the explicitly-specified
3261 // template arguments.
3262 TemplateArgumentList *SugaredExplicitArgumentList =
3264 TemplateArgumentList *CanonicalExplicitArgumentList =
3265 TemplateArgumentList::CreateCopy(Context, CanonicalBuilder);
3266 Info.setExplicitArgs(SugaredExplicitArgumentList,
3267 CanonicalExplicitArgumentList);
3268
3269 // Template argument deduction and the final substitution should be
3270 // done in the context of the templated declaration. Explicit
3271 // argument substitution, on the other hand, needs to happen in the
3272 // calling context.
3273 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3274
3275 // If we deduced template arguments for a template parameter pack,
3276 // note that the template argument pack is partially substituted and record
3277 // the explicit template arguments. They'll be used as part of deduction
3278 // for this template parameter pack.
3279 unsigned PartiallySubstitutedPackIndex = -1u;
3280 if (!CanonicalBuilder.empty()) {
3281 const TemplateArgument &Arg = CanonicalBuilder.back();
3282 if (Arg.getKind() == TemplateArgument::Pack) {
3283 auto *Param = TemplateParams->getParam(CanonicalBuilder.size() - 1);
3284 // If this is a fully-saturated fixed-size pack, it should be
3285 // fully-substituted, not partially-substituted.
3286 std::optional<unsigned> Expansions = getExpandedPackSize(Param);
3287 if (!Expansions || Arg.pack_size() < *Expansions) {
3288 PartiallySubstitutedPackIndex = CanonicalBuilder.size() - 1;
3290 Param, Arg.pack_begin(), Arg.pack_size());
3291 }
3292 }
3293 }
3294
3295 const FunctionProtoType *Proto
3296 = Function->getType()->getAs<FunctionProtoType>();
3297 assert(Proto && "Function template does not have a prototype?");
3298
3299 // Isolate our substituted parameters from our caller.
3300 LocalInstantiationScope InstScope(*this, /*MergeWithOuterScope*/true);
3301
3302 ExtParameterInfoBuilder ExtParamInfos;
3303
3305 SugaredExplicitArgumentList->asArray(),
3306 /*Final=*/true);
3307
3308 // Instantiate the types of each of the function parameters given the
3309 // explicitly-specified template arguments. If the function has a trailing
3310 // return type, substitute it after the arguments to ensure we substitute
3311 // in lexical order.
3312 if (Proto->hasTrailingReturn()) {
3313 if (SubstParmTypes(Function->getLocation(), Function->parameters(),
3314 Proto->getExtParameterInfosOrNull(), MLTAL, ParamTypes,
3315 /*params=*/nullptr, ExtParamInfos))
3317 }
3318
3319 // Instantiate the return type.
3320 QualType ResultType;
3321 {
3322 // C++11 [expr.prim.general]p3:
3323 // If a declaration declares a member function or member function
3324 // template of a class X, the expression this is a prvalue of type
3325 // "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
3326 // and the end of the function-definition, member-declarator, or
3327 // declarator.
3328 Qualifiers ThisTypeQuals;
3329 CXXRecordDecl *ThisContext = nullptr;
3330 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
3331 ThisContext = Method->getParent();
3332 ThisTypeQuals = Method->getMethodQualifiers();
3333 }
3334
3335 CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
3337
3338 ResultType =
3339 SubstType(Proto->getReturnType(), MLTAL,
3340 Function->getTypeSpecStartLoc(), Function->getDeclName());
3341 if (ResultType.isNull() || Trap.hasErrorOccurred())
3343 // CUDA: Kernel function must have 'void' return type.
3344 if (getLangOpts().CUDA)
3345 if (Function->hasAttr<CUDAGlobalAttr>() && !ResultType->isVoidType()) {
3346 Diag(Function->getLocation(), diag::err_kern_type_not_void_return)
3347 << Function->getType() << Function->getSourceRange();
3349 }
3350 }
3351
3352 // Instantiate the types of each of the function parameters given the
3353 // explicitly-specified template arguments if we didn't do so earlier.
3354 if (!Proto->hasTrailingReturn() &&
3355 SubstParmTypes(Function->getLocation(), Function->parameters(),
3356 Proto->getExtParameterInfosOrNull(), MLTAL, ParamTypes,
3357 /*params*/ nullptr, ExtParamInfos))
3359
3360 if (FunctionType) {
3361 auto EPI = Proto->getExtProtoInfo();
3362 EPI.ExtParameterInfos = ExtParamInfos.getPointerOrNull(ParamTypes.size());
3363
3364 // In C++1z onwards, exception specifications are part of the function type,
3365 // so substitution into the type must also substitute into the exception
3366 // specification.
3367 SmallVector<QualType, 4> ExceptionStorage;
3368 if (getLangOpts().CPlusPlus17 &&
3369 SubstExceptionSpec(Function->getLocation(), EPI.ExceptionSpec,
3370 ExceptionStorage, MLTAL))
3372
3373 *FunctionType = BuildFunctionType(ResultType, ParamTypes,
3374 Function->getLocation(),
3375 Function->getDeclName(),
3376 EPI);
3377 if (FunctionType->isNull() || Trap.hasErrorOccurred())
3379 }
3380
3381 // C++ [temp.arg.explicit]p2:
3382 // Trailing template arguments that can be deduced (14.8.2) may be
3383 // omitted from the list of explicit template-arguments. If all of the
3384 // template arguments can be deduced, they may all be omitted; in this
3385 // case, the empty template argument list <> itself may also be omitted.
3386 //
3387 // Take all of the explicitly-specified arguments and put them into
3388 // the set of deduced template arguments. The partially-substituted
3389 // parameter pack, however, will be set to NULL since the deduction
3390 // mechanism handles the partially-substituted argument pack directly.
3391 Deduced.reserve(TemplateParams->size());
3392 for (unsigned I = 0, N = SugaredExplicitArgumentList->size(); I != N; ++I) {
3393 const TemplateArgument &Arg = SugaredExplicitArgumentList->get(I);
3394 if (I == PartiallySubstitutedPackIndex)
3395 Deduced.push_back(DeducedTemplateArgument());
3396 else
3397 Deduced.push_back(Arg);
3398 }
3399
3400 return TDK_Success;
3401}
3402
3403/// Check whether the deduced argument type for a call to a function
3404/// template matches the actual argument type per C++ [temp.deduct.call]p4.
3407 Sema::OriginalCallArg OriginalArg,
3408 QualType DeducedA) {
3409 ASTContext &Context = S.Context;
3410
3411 auto Failed = [&]() -> Sema::TemplateDeductionResult {
3412 Info.FirstArg = TemplateArgument(DeducedA);
3413 Info.SecondArg = TemplateArgument(OriginalArg.OriginalArgType);
3414 Info.CallArgIndex = OriginalArg.ArgIdx;
3417 };
3418
3419 QualType A = OriginalArg.OriginalArgType;
3420 QualType OriginalParamType = OriginalArg.OriginalParamType;
3421
3422 // Check for type equality (top-level cv-qualifiers are ignored).
3423 if (Context.hasSameUnqualifiedType(A, DeducedA))
3424 return Sema::TDK_Success;
3425
3426 // Strip off references on the argument types; they aren't needed for
3427 // the following checks.
3428 if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
3429 DeducedA = DeducedARef->getPointeeType();
3430 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3431 A = ARef->getPointeeType();
3432
3433 // C++ [temp.deduct.call]p4:
3434 // [...] However, there are three cases that allow a difference:
3435 // - If the original P is a reference type, the deduced A (i.e., the
3436 // type referred to by the reference) can be more cv-qualified than
3437 // the transformed A.
3438 if (const ReferenceType *OriginalParamRef
3439 = OriginalParamType->getAs<ReferenceType>()) {
3440 // We don't want to keep the reference around any more.
3441 OriginalParamType = OriginalParamRef->getPointeeType();
3442
3443 // FIXME: Resolve core issue (no number yet): if the original P is a
3444 // reference type and the transformed A is function type "noexcept F",
3445 // the deduced A can be F.
3446 QualType Tmp;
3447 if (A->isFunctionType() && S.IsFunctionConversion(A, DeducedA, Tmp))
3448 return Sema::TDK_Success;
3449
3450 Qualifiers AQuals = A.getQualifiers();
3451 Qualifiers DeducedAQuals = DeducedA.getQualifiers();
3452
3453 // Under Objective-C++ ARC, the deduced type may have implicitly
3454 // been given strong or (when dealing with a const reference)
3455 // unsafe_unretained lifetime. If so, update the original
3456 // qualifiers to include this lifetime.
3457 if (S.getLangOpts().ObjCAutoRefCount &&
3458 ((DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong &&
3460 (DeducedAQuals.hasConst() &&
3461 DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone))) {
3462 AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime());
3463 }
3464
3465 if (AQuals == DeducedAQuals) {
3466 // Qualifiers match; there's nothing to do.
3467 } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) {
3468 return Failed();
3469 } else {
3470 // Qualifiers are compatible, so have the argument type adopt the
3471 // deduced argument type's qualifiers as if we had performed the
3472 // qualification conversion.
3473 A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
3474 }
3475 }
3476
3477 // - The transformed A can be another pointer or pointer to member
3478 // type that can be converted to the deduced A via a function pointer
3479 // conversion and/or a qualification conversion.
3480 //
3481 // Also allow conversions which merely strip __attribute__((noreturn)) from
3482 // function types (recursively).
3483 bool ObjCLifetimeConversion = false;
3484 QualType ResultTy;
3485 if ((A->isAnyPointerType() || A->isMemberPointerType()) &&
3486 (S.IsQualificationConversion(A, DeducedA, false,
3487 ObjCLifetimeConversion) ||
3488 S.IsFunctionConversion(A, DeducedA, ResultTy)))
3489 return Sema::TDK_Success;
3490
3491 // - If P is a class and P has the form simple-template-id, then the
3492 // transformed A can be a derived class of the deduced A. [...]
3493 // [...] Likewise, if P is a pointer to a class of the form
3494 // simple-template-id, the transformed A can be a pointer to a
3495 // derived class pointed to by the deduced A.
3496 if (const PointerType *OriginalParamPtr
3497 = OriginalParamType->getAs<PointerType>()) {
3498 if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
3499 if (const PointerType *APtr = A->getAs<PointerType>()) {
3500 if (A->getPointeeType()->isRecordType()) {
3501 OriginalParamType = OriginalParamPtr->getPointeeType();
3502 DeducedA = DeducedAPtr->getPointeeType();
3503 A = APtr->getPointeeType();
3504 }
3505 }
3506 }
3507 }
3508
3509 if (Context.hasSameUnqualifiedType(A, DeducedA))
3510 return Sema::TDK_Success;
3511
3512 if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) &&
3513 S.IsDerivedFrom(Info.getLocation(), A, DeducedA))
3514 return Sema::TDK_Success;
3515
3516 return Failed();
3517}
3518
3519/// Find the pack index for a particular parameter index in an instantiation of
3520/// a function template with specific arguments.
3521///
3522/// \return The pack index for whichever pack produced this parameter, or -1
3523/// if this was not produced by a parameter. Intended to be used as the
3524/// ArgumentPackSubstitutionIndex for further substitutions.
3525// FIXME: We should track this in OriginalCallArgs so we don't need to
3526// reconstruct it here.
3527static unsigned getPackIndexForParam(Sema &S,
3528 FunctionTemplateDecl *FunctionTemplate,
3530 unsigned ParamIdx) {
3531 unsigned Idx = 0;
3532 for (auto *PD : FunctionTemplate->getTemplatedDecl()->parameters()) {
3533 if (PD->isParameterPack()) {
3534 unsigned NumExpansions =
3535 S.getNumArgumentsInExpansion(PD->getType(), Args).value_or(1);
3536 if (Idx + NumExpansions > ParamIdx)
3537 return ParamIdx - Idx;
3538 Idx += NumExpansions;
3539 } else {
3540 if (Idx == ParamIdx)
3541 return -1; // Not a pack expansion
3542 ++Idx;
3543 }
3544 }
3545
3546 llvm_unreachable("parameter index would not be produced from template");
3547}
3548
3549/// Finish template argument deduction for a function template,
3550/// checking the deduced template arguments for completeness and forming
3551/// the function template specialization.
3552///
3553/// \param OriginalCallArgs If non-NULL, the original call arguments against
3554/// which the deduced argument types should be compared.
3556 FunctionTemplateDecl *FunctionTemplate,
3558 unsigned NumExplicitlySpecified, FunctionDecl *&Specialization,
3560 SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs,
3561 bool PartialOverloading, llvm::function_ref<bool()> CheckNonDependent) {
3562 // Unevaluated SFINAE context.
3565 SFINAETrap Trap(*this);
3566
3567 // Enter a new template instantiation context while we instantiate the
3568 // actual function declaration.
3569 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3571 *this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3573 if (Inst.isInvalid())
3575
3576 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3577
3578 // C++ [temp.deduct.type]p2:
3579 // [...] or if any template argument remains neither deduced nor
3580 // explicitly specified, template argument deduction fails.
3581 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
3583 *this, FunctionTemplate, /*IsDeduced*/ true, Deduced, Info,
3584 SugaredBuilder, CanonicalBuilder, CurrentInstantiationScope,
3585 NumExplicitlySpecified, PartialOverloading))
3586 return Result;
3587
3588 // C++ [temp.deduct.call]p10: [DR1391]
3589 // If deduction succeeds for all parameters that contain
3590 // template-parameters that participate in template argument deduction,
3591 // and all template arguments are explicitly specified, deduced, or
3592 // obtained from default template arguments, remaining parameters are then
3593 // compared with the corresponding arguments. For each remaining parameter
3594 // P with a type that was non-dependent before substitution of any
3595 // explicitly-specified template arguments, if the corresponding argument
3596 // A cannot be implicitly converted to P, deduction fails.
3597 if (CheckNonDependent())
3599
3600 // Form the template argument list from the deduced template arguments.
3601 TemplateArgumentList *SugaredDeducedArgumentList =
3603 TemplateArgumentList *CanonicalDeducedArgumentList =
3604 TemplateArgumentList::CreateCopy(Context, CanonicalBuilder);
3605 Info.reset(SugaredDeducedArgumentList, CanonicalDeducedArgumentList);
3606
3607 // Substitute the deduced template arguments into the function template
3608 // declaration to produce the function template specialization.
3609 DeclContext *Owner = FunctionTemplate->getDeclContext();
3610 if (FunctionTemplate->getFriendObjectKind())
3611 Owner = FunctionTemplate->getLexicalDeclContext();
3612 FunctionDecl *FD = FunctionTemplate->getTemplatedDecl();
3613 // additional check for inline friend,
3614 // ```
3615 // template <class F1> int foo(F1 X);
3616 // template <int A1> struct A {
3617 // template <class F1> friend int foo(F1 X) { return A1; }
3618 // };
3619 // template struct A<1>;
3620 // int a = foo(1.0);
3621 // ```
3622 const FunctionDecl *FDFriend;
3624 FD->isDefined(FDFriend, /*CheckForPendingFriendDefinition*/ true) &&
3626 FD = const_cast<FunctionDecl *>(FDFriend);
3627 Owner = FD->getLexicalDeclContext();
3628 }
3630 FunctionTemplate, CanonicalDeducedArgumentList->asArray(),
3631 /*Final=*/false);
3632 Specialization = cast_or_null<FunctionDecl>(
3633 SubstDecl(FD, Owner, SubstArgs));
3634 if (!Specialization || Specialization->isInvalidDecl())
3636
3637 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
3638 FunctionTemplate->getCanonicalDecl());
3639
3640 // If the template argument list is owned by the function template
3641 // specialization, release it.
3642 if (Specialization->getTemplateSpecializationArgs() ==
3643 CanonicalDeducedArgumentList &&
3644 !Trap.hasErrorOccurred())
3645 Info.takeCanonical();
3646
3647 // There may have been an error that did not prevent us from constructing a
3648 // declaration. Mark the declaration invalid and return with a substitution
3649 // failure.
3650 if (Trap.hasErrorOccurred()) {
3651 Specialization->setInvalidDecl(true);
3653 }
3654
3655 // C++2a [temp.deduct]p5
3656 // [...] When all template arguments have been deduced [...] all uses of
3657 // template parameters [...] are replaced with the corresponding deduced
3658 // or default argument values.
3659 // [...] If the function template has associated constraints
3660 // ([temp.constr.decl]), those constraints are checked for satisfaction
3661 // ([temp.constr.constr]). If the constraints are not satisfied, type
3662 // deduction fails.
3663 if (!PartialOverloading ||
3664 (CanonicalBuilder.size() ==
3665 FunctionTemplate->getTemplateParameters()->size())) {
3667 Info.getLocation(), Specialization, CanonicalBuilder,
3670
3672 Info.reset(Info.takeSugared(),
3673 TemplateArgumentList::CreateCopy(Context, CanonicalBuilder));
3675 }
3676 }
3677
3678 if (OriginalCallArgs) {
3679 // C++ [temp.deduct.call]p4:
3680 // In general, the deduction process attempts to find template argument
3681 // values that will make the deduced A identical to A (after the type A
3682 // is transformed as described above). [...]
3683 llvm::SmallDenseMap<std::pair<unsigned, QualType>, QualType> DeducedATypes;
3684 for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
3685 OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
3686
3687 auto ParamIdx = OriginalArg.ArgIdx;
3688 if (ParamIdx >= Specialization->getNumParams())
3689 // FIXME: This presumably means a pack ended up smaller than we
3690 // expected while deducing. Should this not result in deduction
3691 // failure? Can it even happen?
3692 continue;
3693
3694 QualType DeducedA;
3695 if (!OriginalArg.DecomposedParam) {
3696 // P is one of the function parameters, just look up its substituted
3697 // type.
3698 DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
3699 } else {
3700 // P is a decomposed element of a parameter corresponding to a
3701 // braced-init-list argument. Substitute back into P to find the
3702 // deduced A.
3703 QualType &CacheEntry =
3704 DeducedATypes[{ParamIdx, OriginalArg.OriginalParamType}];
3705 if (CacheEntry.isNull()) {
3707 *this, getPackIndexForParam(*this, FunctionTemplate, SubstArgs,
3708 ParamIdx));
3709 CacheEntry =
3710 SubstType(OriginalArg.OriginalParamType, SubstArgs,
3711 Specialization->getTypeSpecStartLoc(),
3712 Specialization->getDeclName());
3713 }
3714 DeducedA = CacheEntry;
3715 }
3716
3717 if (auto TDK =
3718 CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA))
3719 return TDK;
3720 }
3721 }
3722
3723 // If we suppressed any diagnostics while performing template argument
3724 // deduction, and if we haven't already instantiated this declaration,
3725 // keep track of these diagnostics. They'll be emitted if this specialization
3726 // is actually used.
3727 if (Info.diag_begin() != Info.diag_end()) {
3728 SuppressedDiagnosticsMap::iterator
3729 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
3730 if (Pos == SuppressedDiagnostics.end())
3731 SuppressedDiagnostics[Specialization->getCanonicalDecl()]
3732 .append(Info.diag_begin(), Info.diag_end());
3733 }
3734
3735 return TDK_Success;
3736}
3737
3738/// Gets the type of a function for template-argument-deducton
3739/// purposes when it's considered as part of an overload set.
3741 FunctionDecl *Fn) {
3742 // We may need to deduce the return type of the function now.
3743 if (S.getLangOpts().CPlusPlus14 && Fn->getReturnType()->isUndeducedType() &&
3744 S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/ false))
3745 return {};
3746
3747 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
3748 if (Method->isInstance()) {
3749 // An instance method that's referenced in a form that doesn't
3750 // look like a member pointer is just invalid.
3752 return {};
3753
3754 return S.Context.getMemberPointerType(Fn->getType(),
3755 S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
3756 }
3757
3758 if (!R.IsAddressOfOperand) return Fn->getType();
3759 return S.Context.getPointerType(Fn->getType());
3760}
3761
3762/// Apply the deduction rules for overload sets.
3763///
3764/// \return the null type if this argument should be treated as an
3765/// undeduced context
3766static QualType
3768 Expr *Arg, QualType ParamType,
3769 bool ParamWasReference,
3770 TemplateSpecCandidateSet *FailedTSC = nullptr) {
3771
3773
3774 OverloadExpr *Ovl = R.Expression;
3775
3776 // C++0x [temp.deduct.call]p4
3777 unsigned TDF = 0;
3778 if (ParamWasReference)
3780 if (R.IsAddressOfOperand)
3781 TDF |= TDF_IgnoreQualifiers;
3782
3783 // C++0x [temp.deduct.call]p6:
3784 // When P is a function type, pointer to function type, or pointer
3785 // to member function type:
3786
3787 if (!ParamType->isFunctionType() &&
3788 !ParamType->isFunctionPointerType() &&
3789 !ParamType->isMemberFunctionPointerType()) {
3790 if (Ovl->hasExplicitTemplateArgs()) {
3791 // But we can still look for an explicit specialization.
3792 if (FunctionDecl *ExplicitSpec =
3794 Ovl, /*Complain=*/false,
3795 /*FoundDeclAccessPair=*/nullptr, FailedTSC))
3796 return GetTypeOfFunction(S, R, ExplicitSpec);
3797 }
3798
3799 DeclAccessPair DAP;
3800 if (FunctionDecl *Viable =
3802 return GetTypeOfFunction(S, R, Viable);
3803
3804 return {};
3805 }
3806
3807 // Gather the explicit template arguments, if any.
3808 TemplateArgumentListInfo ExplicitTemplateArgs;
3809 if (Ovl->hasExplicitTemplateArgs())
3810 Ovl->copyTemplateArgumentsInto(ExplicitTemplateArgs);
3811 QualType Match;
3812 for (UnresolvedSetIterator I = Ovl->decls_begin(),
3813 E = Ovl->decls_end(); I != E; ++I) {
3814 NamedDecl *D = (*I)->getUnderlyingDecl();
3815
3816 if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
3817 // - If the argument is an overload set containing one or more
3818 // function templates, the parameter is treated as a
3819 // non-deduced context.
3820 if (!Ovl->hasExplicitTemplateArgs())
3821 return {};
3822
3823 // Otherwise, see if we can resolve a function type
3824 FunctionDecl *Specialization = nullptr;
3825 TemplateDeductionInfo Info(Ovl->getNameLoc());
3826 if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
3827 Specialization, Info))
3828 continue;
3829
3830 D = Specialization;
3831 }
3832
3833 FunctionDecl *Fn = cast<FunctionDecl>(D);
3834 QualType ArgType = GetTypeOfFunction(S, R, Fn);
3835 if (ArgType.isNull()) continue;
3836
3837 // Function-to-pointer conversion.
3838 if (!ParamWasReference && ParamType->isPointerType() &&
3839 ArgType->isFunctionType())
3840 ArgType = S.Context.getPointerType(ArgType);
3841
3842 // - If the argument is an overload set (not containing function
3843 // templates), trial argument deduction is attempted using each
3844 // of the members of the set. If deduction succeeds for only one
3845 // of the overload set members, that member is used as the
3846 // argument value for the deduction. If deduction succeeds for
3847 // more than one member of the overload set the parameter is
3848 // treated as a non-deduced context.
3849
3850 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
3851 // Type deduction is done independently for each P/A pair, and
3852 // the deduced template argument values are then combined.
3853 // So we do not reject deductions which were made elsewhere.
3855 Deduced(TemplateParams->size());
3856 TemplateDeductionInfo Info(Ovl->getNameLoc());
3858 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3859 ArgType, Info, Deduced, TDF);
3860 if (Result) continue;
3861 if (!Match.isNull())
3862 return {};
3863 Match = ArgType;
3864 }
3865
3866 return Match;
3867}
3868
3869/// Perform the adjustments to the parameter and argument types
3870/// described in C++ [temp.deduct.call].
3871///
3872/// \returns true if the caller should not attempt to perform any template
3873/// argument deduction based on this P/A pair because the argument is an
3874/// overloaded function set that could not be resolved.
3876 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3877 QualType &ParamType, QualType &ArgType, Expr *Arg, unsigned &TDF,
3878 TemplateSpecCandidateSet *FailedTSC = nullptr) {
3879 // C++0x [temp.deduct.call]p3:
3880 // If P is a cv-qualified type, the top level cv-qualifiers of P's type
3881 // are ignored for type deduction.
3882 if (ParamType.hasQualifiers())
3883 ParamType = ParamType.getUnqualifiedType();
3884
3885 // [...] If P is a reference type, the type referred to by P is
3886 // used for type deduction.
3887 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
3888 if (ParamRefType)
3889 ParamType = ParamRefType->getPointeeType();
3890
3891 // Overload sets usually make this parameter an undeduced context,
3892 // but there are sometimes special circumstances. Typically
3893 // involving a template-id-expr.
3894 if (ArgType == S.Context.OverloadTy) {
3895 ArgType = ResolveOverloadForDeduction(S, TemplateParams, Arg, ParamType,
3896 ParamRefType != nullptr, FailedTSC);
3897 if (ArgType.isNull())
3898 return true;
3899 }
3900
3901 if (ParamRefType) {
3902 // If the argument has incomplete array type, try to complete its type.
3903 if (ArgType->isIncompleteArrayType())
3904 ArgType = S.getCompletedType(Arg);
3905
3906 // C++1z [temp.deduct.call]p3:
3907 // If P is a forwarding reference and the argument is an lvalue, the type
3908 // "lvalue reference to A" is used in place of A for type deduction.
3909 if (isForwardingReference(QualType(ParamRefType, 0), FirstInnerIndex) &&
3910 Arg->isLValue()) {
3911 if (S.getLangOpts().OpenCL && !ArgType.hasAddressSpace())
3912 ArgType = S.Context.getAddrSpaceQualType(
3914 ArgType = S.Context.getLValueReferenceType(ArgType);
3915 }
3916 } else {
3917 // C++ [temp.deduct.call]p2:
3918 // If P is not a reference type:
3919 // - If A is an array type, the pointer type produced by the
3920 // array-to-pointer standard conversion (4.2) is used in place of
3921 // A for type deduction; otherwise,
3922 // - If A is a function type, the pointer type produced by the
3923 // function-to-pointer standard conversion (4.3) is used in place
3924 // of A for type deduction; otherwise,
3925 if (ArgType->canDecayToPointerType())
3926 ArgType = S.Context.getDecayedType(ArgType);
3927 else {
3928 // - If A is a cv-qualified type, the top level cv-qualifiers of A's
3929 // type are ignored for type deduction.
3930 ArgType = ArgType.getUnqualifiedType();
3931 }
3932 }
3933
3934 // C++0x [temp.deduct.call]p4:
3935 // In general, the deduction process attempts to find template argument
3936 // values that will make the deduced A identical to A (after the type A
3937 // is transformed as described above). [...]
3939
3940 // - If the original P is a reference type, the deduced A (i.e., the
3941 // type referred to by the reference) can be more cv-qualified than
3942 // the transformed A.
3943 if (ParamRefType)
3945 // - The transformed A can be another pointer or pointer to member
3946 // type that can be converted to the deduced A via a qualification
3947 // conversion (4.4).
3948 if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
3949 ArgType->isObjCObjectPointerType())
3950 TDF |= TDF_IgnoreQualifiers;
3951 // - If P is a class and P has the form simple-template-id, then the
3952 // transformed A can be a derived class of the deduced A. Likewise,
3953 // if P is a pointer to a class of the form simple-template-id, the
3954 // transformed A can be a pointer to a derived class pointed to by
3955 // the deduced A.
3956 if (isSimpleTemplateIdType(ParamType) ||
3957 (isa<PointerType>(ParamType) &&
3959 ParamType->castAs<PointerType>()->getPointeeType())))
3960 TDF |= TDF_DerivedClass;
3961
3962 return false;
3963}
3964
3965static bool
3967 QualType T);
3968
3970 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3971 QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
3974 bool DecomposedParam, unsigned ArgIdx, unsigned TDF,
3975 TemplateSpecCandidateSet *FailedTSC = nullptr);
3976
3977/// Attempt template argument deduction from an initializer list
3978/// deemed to be an argument in a function call.
3980 Sema &S, TemplateParameterList *TemplateParams, QualType AdjustedParamType,
3983 SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs, unsigned ArgIdx,
3984 unsigned TDF) {
3985 // C++ [temp.deduct.call]p1: (CWG 1591)
3986 // If removing references and cv-qualifiers from P gives
3987 // std::initializer_list<P0> or P0[N] for some P0 and N and the argument is
3988 // a non-empty initializer list, then deduction is performed instead for
3989 // each element of the initializer list, taking P0 as a function template
3990 // parameter type and the initializer element as its argument
3991 //
3992 // We've already removed references and cv-qualifiers here.
3993 if (!ILE->getNumInits())
3994 return Sema::TDK_Success;
3995
3996 QualType ElTy;
3997 auto *ArrTy = S.Context.getAsArrayType(AdjustedParamType);
3998 if (ArrTy)
3999 ElTy = ArrTy->getElementType();
4000 else if (!S.isStdInitializerList(AdjustedParamType, &ElTy)) {
4001 // Otherwise, an initializer list argument causes the parameter to be
4002 // considered a non-deduced context
4003 return Sema::TDK_Success;
4004 }
4005
4006 // Resolving a core issue: a braced-init-list containing any designators is
4007 // a non-deduced context.
4008 for (Expr *E : ILE->inits())
4009 if (isa<DesignatedInitExpr>(E))
4010 return Sema::TDK_Success;
4011
4012 // Deduction only needs to be done for dependent types.
4013 if (ElTy->isDependentType()) {
4014 for (Expr *E : ILE->inits()) {
4016 S, TemplateParams, 0, ElTy, E, Info, Deduced, OriginalCallArgs, true,
4017 ArgIdx, TDF))
4018 return Result;
4019 }
4020 }
4021
4022 // in the P0[N] case, if N is a non-type template parameter, N is deduced
4023 // from the length of the initializer list.
4024 if (auto *DependentArrTy = dyn_cast_or_null<DependentSizedArrayType>(ArrTy)) {
4025 // Determine the array bound is something we can deduce.
4026 if (const NonTypeTemplateParmDecl *NTTP =
4027 getDeducedParameterFromExpr(Info, DependentArrTy->getSizeExpr())) {
4028 // We can perform template argument deduction for the given non-type
4029 // template parameter.
4030 // C++ [temp.deduct.type]p13:
4031 // The type of N in the type T[N] is std::size_t.
4033 llvm::APInt Size(S.Context.getIntWidth(T), ILE->getNumInits());
4035 S, TemplateParams, NTTP, llvm::APSInt(Size), T,
4036 /*ArrayBound=*/true, Info, Deduced))
4037 return Result;
4038 }
4039 }
4040
4041 return Sema::TDK_Success;
4042}
4043
4044/// Perform template argument deduction per [temp.deduct.call] for a
4045/// single parameter / argument pair.
4047 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
4048 QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
4051 bool DecomposedParam, unsigned ArgIdx, unsigned TDF,
4052 TemplateSpecCandidateSet *FailedTSC) {
4053 QualType ArgType = Arg->getType();
4054 QualType OrigParamType = ParamType;
4055
4056 // If P is a reference type [...]
4057 // If P is a cv-qualified type [...]
4058 if (AdjustFunctionParmAndArgTypesForDeduction(S, TemplateParams,
4059 FirstInnerIndex, ParamType,
4060 ArgType, Arg, TDF, FailedTSC))
4061 return Sema::TDK_Success;
4062
4063 // If [...] the argument is a non-empty initializer list [...]
4064 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg))
4065 return DeduceFromInitializerList(S, TemplateParams, ParamType, ILE, Info,
4066 Deduced, OriginalCallArgs, ArgIdx, TDF);
4067
4068 // [...] the deduction process attempts to find template argument values
4069 // that will make the deduced A identical to A
4070 //
4071 // Keep track of the argument type and corresponding parameter index,
4072 // so we can check for compatibility between the deduced A and A.
4073 OriginalCallArgs.push_back(
4074 Sema::OriginalCallArg(OrigParamType, DecomposedParam, ArgIdx, ArgType));
4075 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
4076 ArgType, Info, Deduced, TDF);
4077}
4078
4079/// Perform template argument deduction from a function call
4080/// (C++ [temp.deduct.call]).
4081///
4082/// \param FunctionTemplate the function template for which we are performing
4083/// template argument deduction.
4084///
4085/// \param ExplicitTemplateArgs the explicit template arguments provided
4086/// for this call.
4087///
4088/// \param Args the function call arguments
4089///
4090/// \param Specialization if template argument deduction was successful,
4091/// this will be set to the function template specialization produced by
4092/// template argument deduction.
4093///
4094/// \param Info the argument will be updated to provide additional information
4095/// about template argument deduction.
4096///
4097/// \param CheckNonDependent A callback to invoke to check conversions for
4098/// non-dependent parameters, between deduction and substitution, per DR1391.
4099/// If this returns true, substitution will be skipped and we return
4100/// TDK_NonDependentConversionFailure. The callback is passed the parameter
4101/// types (after substituting explicit template arguments).
4102///
4103/// \returns the result of template argument deduction.
4105 FunctionTemplateDecl *FunctionTemplate,
4106 TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args,
4108 bool PartialOverloading, bool AggregateDeductionCandidate,
4109 llvm::function_ref<bool(ArrayRef<QualType>)> CheckNonDependent) {
4110 if (FunctionTemplate->isInvalidDecl())
4111 return TDK_Invalid;
4112
4113 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4114 unsigned NumParams = Function->getNumParams();
4115
4116 unsigned FirstInnerIndex = getFirstInnerIndex(FunctionTemplate);
4117
4118 // C++ [temp.deduct.call]p1:
4119 // Template argument deduction is done by comparing each function template
4120 // parameter type (call it P) with the type of the corresponding argument
4121 // of the call (call it A) as described below.
4122 if (Args.size() < Function->getMinRequiredArguments() && !PartialOverloading)
4123 return TDK_TooFewArguments;
4124 else if (TooManyArguments(NumParams, Args.size(), PartialOverloading)) {
4125 const auto *Proto = Function->getType()->castAs<FunctionProtoType>();
4126 if (Proto->isTemplateVariadic())
4127 /* Do nothing */;
4128 else if (!Proto->isVariadic())
4129 return TDK_TooManyArguments;
4130 }
4131
4132 // The types of the parameters from which we will perform template argument
4133 // deduction.
4134 LocalInstantiationScope InstScope(*this);
4135 TemplateParameterList *TemplateParams
4136 = FunctionTemplate->getTemplateParameters();
4138 SmallVector<QualType, 8> ParamTypes;
4139 unsigned NumExplicitlySpecified = 0;
4140 if (ExplicitTemplateArgs) {
4143 Result = SubstituteExplicitTemplateArguments(
4144 FunctionTemplate, *ExplicitTemplateArgs, Deduced, ParamTypes, nullptr,
4145 Info);
4146 });
4147 if (Result)
4148 return Result;
4149
4150 NumExplicitlySpecified = Deduced.size();
4151 } else {
4152 // Just fill in the parameter types from the function declaration.
4153 for (unsigned I = 0; I != NumParams; ++I)
4154 ParamTypes.push_back(Function->getParamDecl(I)->getType());
4155 }
4156
4157 SmallVector<OriginalCallArg, 8> OriginalCallArgs;
4158
4159 // Deduce an argument of type ParamType from an expression with index ArgIdx.
4160 auto DeduceCallArgument = [&](QualType ParamType, unsigned ArgIdx) {
4161 // C++ [demp.deduct.call]p1: (DR1391)
4162 // Template argument deduction is done by comparing each function template
4163 // parameter that contains template-parameters that participate in
4164 // template argument deduction ...
4165 if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
4166 return Sema::TDK_Success;
4167
4168 // ... with the type of the corresponding argument
4170 *this, TemplateParams, FirstInnerIndex, ParamType, Args[ArgIdx], Info, Deduced,
4171 OriginalCallArgs, /*Decomposed*/false, ArgIdx, /*TDF*/ 0);
4172 };
4173
4174 // Deduce template arguments from the function parameters.
4175 Deduced.resize(TemplateParams->size());
4176 SmallVector<QualType, 8> ParamTypesForArgChecking;
4177 for (unsigned ParamIdx = 0, NumParamTypes = ParamTypes.size(), ArgIdx = 0;
4178 ParamIdx != NumParamTypes; ++ParamIdx) {
4179 QualType ParamType = ParamTypes[ParamIdx];
4180
4181 const PackExpansionType *ParamExpansion =
4182 dyn_cast<PackExpansionType>(ParamType);
4183 if (!ParamExpansion) {
4184 // Simple case: matching a function parameter to a function argument.
4185 if (ArgIdx >= Args.size())
4186 break;
4187
4188 ParamTypesForArgChecking.push_back(ParamType);
4189 if (auto Result = DeduceCallArgument(ParamType, ArgIdx++))
4190 return Result;
4191
4192 continue;
4193 }
4194
4195 bool IsTrailingPack = ParamIdx + 1 == NumParamTypes;
4196
4197 QualType ParamPattern = ParamExpansion->getPattern();
4198 PackDeductionScope PackScope(*this, TemplateParams, Deduced, Info,
4199 ParamPattern,
4200 AggregateDeductionCandidate && IsTrailingPack);
4201
4202 // C++0x [temp.deduct.call]p1:
4203 // For a function parameter pack that occurs at the end of the
4204 // parameter-declaration-list, the type A of each remaining argument of
4205 // the call is compared with the type P of the declarator-id of the
4206 // function parameter pack. Each comparison deduces template arguments
4207 // for subsequent positions in the template parameter packs expanded by
4208 // the function parameter pack. When a function parameter pack appears
4209 // in a non-deduced context [not at the end of the list], the type of
4210 // that parameter pack is never deduced.
4211 //
4212 // FIXME: The above rule allows the size of the parameter pack to change
4213 // after we skip it (in the non-deduced case). That makes no sense, so
4214 // we instead notionally deduce the pack against N arguments, where N is
4215 // the length of the explicitly-specified pack if it's expanded by the
4216 // parameter pack and 0 otherwise, and we treat each deduction as a
4217 // non-deduced context.
4218 if (IsTrailingPack || PackScope.hasFixedArity()) {
4219 for (; ArgIdx < Args.size() && PackScope.hasNextElement();
4220 PackScope.nextPackElement(), ++ArgIdx) {
4221 ParamTypesForArgChecking.push_back(ParamPattern);
4222 if (auto Result = DeduceCallArgument(ParamPattern, ArgIdx))
4223 return Result;
4224 }
4225 } else {
4226 // If the parameter type contains an explicitly-specified pack that we
4227 // could not expand, skip the number of parameters notionally created
4228 // by the expansion.
4229 std::optional<unsigned> NumExpansions =
4230 ParamExpansion->getNumExpansions();
4231 if (NumExpansions && !PackScope.isPartiallyExpanded()) {
4232 for (unsigned I = 0; I != *NumExpansions && ArgIdx < Args.size();
4233 ++I, ++ArgIdx) {
4234 ParamTypesForArgChecking.push_back(ParamPattern);
4235 // FIXME: Should we add OriginalCallArgs for these? What if the
4236 // corresponding argument is a list?
4237 PackScope.nextPackElement();
4238 }
4239 }
4240 }
4241
4242 // Build argument packs for each of the parameter packs expanded by this
4243 // pack expansion.
4244 if (auto Result = PackScope.finish())
4245 return Result;
4246 }
4247
4248 // Capture the context in which the function call is made. This is the context
4249 // that is needed when the accessibility of template arguments is checked.
4250 DeclContext *CallingCtx = CurContext;
4251
4254 Result = FinishTemplateArgumentDeduction(
4255 FunctionTemplate, Deduced, NumExplicitlySpecified, Specialization, Info,
4256 &OriginalCallArgs, PartialOverloading, [&, CallingCtx]() {
4257 ContextRAII SavedContext(*this, CallingCtx);
4258 return CheckNonDependent(ParamTypesForArgChecking);
4259 });
4260 });
4261 return Result;
4262}
4263
4266 bool AdjustExceptionSpec) {
4267 if (ArgFunctionType.isNull())
4268 return ArgFunctionType;
4269
4270 const auto *FunctionTypeP = FunctionType->castAs<FunctionProtoType>();
4271 const auto *ArgFunctionTypeP = ArgFunctionType->castAs<FunctionProtoType>();
4272 FunctionProtoType::ExtProtoInfo EPI = ArgFunctionTypeP->getExtProtoInfo();
4273 bool Rebuild = false;
4274
4275 CallingConv CC = FunctionTypeP->getCallConv();
4276 if (EPI.ExtInfo.getCC() != CC) {
4277 EPI.ExtInfo = EPI.ExtInfo.withCallingConv(CC);
4278 Rebuild = true;
4279 }
4280
4281 bool NoReturn = FunctionTypeP->getNoReturnAttr();
4282 if (EPI.ExtInfo.getNoReturn() != NoReturn) {
4283 EPI.ExtInfo = EPI.ExtInfo.withNoReturn(NoReturn);
4284 Rebuild = true;
4285 }
4286
4287 if (AdjustExceptionSpec && (FunctionTypeP->hasExceptionSpec() ||
4288 ArgFunctionTypeP->hasExceptionSpec())) {
4289 EPI.ExceptionSpec = FunctionTypeP->getExtProtoInfo().ExceptionSpec;
4290 Rebuild = true;
4291 }
4292
4293 if (!Rebuild)
4294 return ArgFunctionType;
4295
4296 return Context.getFunctionType(ArgFunctionTypeP->getReturnType(),
4297 ArgFunctionTypeP->getParamTypes(), EPI);
4298}
4299
4300/// Deduce template arguments when taking the address of a function
4301/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
4302/// a template.
4303///
4304/// \param FunctionTemplate the function template for which we are performing
4305/// template argument deduction.
4306///
4307/// \param ExplicitTemplateArgs the explicitly-specified template
4308/// arguments.
4309///
4310/// \param ArgFunctionType the function type that will be used as the
4311/// "argument" type (A) when performing template argument deduction from the
4312/// function template's function type. This type may be NULL, if there is no
4313/// argument type to compare against, in C++0x [temp.arg.explicit]p3.
4314///
4315/// \param Specialization if template argument deduction was successful,
4316/// this will be set to the function template specialization produced by
4317/// template argument deduction.
4318///
4319/// \param Info the argument will be updated to provide additional information
4320/// about template argument deduction.
4321///
4322/// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4323/// the address of a function template per [temp.deduct.funcaddr] and
4324/// [over.over]. If \c false, we are looking up a function template
4325/// specialization based on its signature, per [temp.deduct.decl].
4326///
4327/// \returns the result of template argument deduction.
4329 FunctionTemplateDecl *FunctionTemplate,
4330 TemplateArgumentListInfo *ExplicitTemplateArgs, QualType ArgFunctionType,
4332 bool IsAddressOfFunction) {
4333 if (FunctionTemplate->isInvalidDecl())
4334 return TDK_Invalid;
4335
4336 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4337 TemplateParameterList *TemplateParams
4338 = FunctionTemplate->getTemplateParameters();
4339 QualType FunctionType = Function->getType();
4340
4341 // Substitute any explicit template arguments.
4342 LocalInstantiationScope InstScope(*this);
4344 unsigned NumExplicitlySpecified = 0;
4345 SmallVector<QualType, 4> ParamTypes;
4346 if (ExplicitTemplateArgs) {
4349 Result = SubstituteExplicitTemplateArguments(
4350 FunctionTemplate, *ExplicitTemplateArgs, Deduced, ParamTypes,
4351 &FunctionType, Info);
4352 });
4353 if (Result)
4354 return Result;
4355
4356 NumExplicitlySpecified = Deduced.size();
4357 }
4358
4359 // When taking the address of a function, we require convertibility of
4360 // the resulting function type. Otherwise, we allow arbitrary mismatches
4361 // of calling convention and noreturn.
4362 if (!IsAddressOfFunction)
4363 ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, FunctionType,
4364 /*AdjustExceptionSpec*/false);
4365
4366 // Unevaluated SFINAE context.
4369 SFINAETrap Trap(*this);
4370
4371 Deduced.resize(TemplateParams->size());
4372
4373 // If the function has a deduced return type, substitute it for a dependent
4374 // type so that we treat it as a non-deduced context in what follows.
4375 bool HasDeducedReturnType = false;
4376 if (getLangOpts().CPlusPlus14 &&
4377 Function->getReturnType()->getContainedAutoType()) {
4379 HasDeducedReturnType = true;
4380 }
4381
4382 if (!ArgFunctionType.isNull() && !FunctionType.isNull()) {
4383 unsigned TDF =
4385 // Deduce template arguments from the function type.
4387 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
4388 FunctionType, ArgFunctionType,
4389 Info, Deduced, TDF))
4390 return Result;
4391 }
4392
4395 Result = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
4396 NumExplicitlySpecified,
4397 Specialization, Info);
4398 });
4399 if (Result)
4400 return Result;
4401
4402 // If the function has a deduced return type, deduce it now, so we can check
4403 // that the deduced function type matches the requested type.
4404 if (HasDeducedReturnType && IsAddressOfFunction &&
4405 Specialization->getReturnType()->isUndeducedType() &&
4408
4409 if (IsAddressOfFunction && getLangOpts().CPlusPlus20 &&
4410 Specialization->isImmediateEscalating() &&
4412 Info.getLocation()))
4414
4415 // If the function has a dependent exception specification, resolve it now,
4416 // so we can check that the exception specification matches.
4417 auto *SpecializationFPT =
4418 Specialization->getType()->castAs<FunctionProtoType>();
4419 if (getLangOpts().CPlusPlus17 &&
4420 isUnresolvedExceptionSpec(SpecializationFPT->getExceptionSpecType()) &&
4421 !ResolveExceptionSpec(Info.getLocation(), SpecializationFPT))
4423
4424 // Adjust the exception specification of the argument to match the
4425 // substituted and resolved type we just formed. (Calling convention and
4426 // noreturn can't be dependent, so we don't actually need this for them
4427 // right now.)
4428 QualType SpecializationType = Specialization->getType();
4429 if (!IsAddressOfFunction) {
4430 ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, SpecializationType,
4431 /*AdjustExceptionSpec*/true);
4432
4433 // Revert placeholder types in the return type back to undeduced types so
4434 // that the comparison below compares the declared return types.
4435 if (HasDeducedReturnType) {
4436 SpecializationType = SubstAutoType(SpecializationType, QualType());
4437 ArgFunctionType = SubstAutoType(ArgFunctionType, QualType());
4438 }
4439 }
4440
4441 // If the requested function type does not match the actual type of the
4442 // specialization with respect to arguments of compatible pointer to function
4443 // types, template argument deduction fails.
4444 if (!ArgFunctionType.isNull()) {
4445 if (IsAddressOfFunction
4447 Context.getCanonicalType(SpecializationType),
4448 Context.getCanonicalType(ArgFunctionType))
4449 : !Context.hasSameType(SpecializationType, ArgFunctionType)) {
4450 Info.FirstArg = TemplateArgument(SpecializationType);
4451 Info.SecondArg = TemplateArgument(ArgFunctionType);
4453 }
4454 }
4455
4456 return TDK_Success;
4457}
4458
4459/// Deduce template arguments for a templated conversion
4460/// function (C++ [temp.deduct.conv]) and, if successful, produce a
4461/// conversion function template specialization.
4464 QualType ToType,
4466 TemplateDeductionInfo &Info) {
4467 if (ConversionTemplate->isInvalidDecl())
4468 return TDK_Invalid;
4469
4470 CXXConversionDecl *ConversionGeneric
4471 = cast<CXXConversionDecl>(ConversionTemplate->getTemplatedDecl());
4472
4473 QualType FromType = ConversionGeneric->getConversionType();
4474
4475 // Canonicalize the types for deduction.
4476 QualType P = Context.getCanonicalType(FromType);
4477 QualType A = Context.getCanonicalType(ToType);
4478
4479 // C++0x [temp.deduct.conv]p2:
4480 // If P is a reference type, the type referred to by P is used for
4481 // type deduction.
4482 if (const ReferenceType *PRef = P->getAs<ReferenceType>())
4483 P = PRef->getPointeeType();
4484
4485 // C++0x [temp.deduct.conv]p4:
4486 // [...] If A is a reference type, the type referred to by A is used
4487 // for type deduction.
4488 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) {
4489 A = ARef->getPointeeType();
4490 // We work around a defect in the standard here: cv-qualifiers are also
4491 // removed from P and A in this case, unless P was a reference type. This
4492 // seems to mostly match what other compilers are doing.
4493 if (!FromType->getAs<ReferenceType>()) {
4494 A = A.getUnqualifiedType();
4495 P = P.getUnqualifiedType();
4496 }
4497
4498 // C++ [temp.deduct.conv]p3:
4499 //
4500 // If A is not a reference type:
4501 } else {
4502 assert(!A->isReferenceType() && "Reference types were handled above");
4503
4504 // - If P is an array type, the pointer type produced by the
4505 // array-to-pointer standard conversion (4.2) is used in place
4506 // of P for type deduction; otherwise,
4507 if (P->isArrayType())
4509 // - If P is a function type, the pointer type produced by the
4510 // function-to-pointer standard conversion (4.3) is used in
4511 // place of P for type deduction; otherwise,
4512 else if (P->isFunctionType())
4514 // - If P is a cv-qualified type, the top level cv-qualifiers of
4515 // P's type are ignored for type deduction.
4516 else
4517 P = P.getUnqualifiedType();
4518
4519 // C++0x [temp.deduct.conv]p4:
4520 // If A is a cv-qualified type, the top level cv-qualifiers of A's
4521 // type are ignored for type deduction. If A is a reference type, the type
4522 // referred to by A is used for type deduction.
4523 A = A.getUnqualifiedType();
4524 }
4525
4526 // Unevaluated SFINAE context.
4529 SFINAETrap Trap(*this);
4530
4531 // C++ [temp.deduct.conv]p1:
4532 // Template argument deduction is done by comparing the return
4533 // type of the template conversion function (call it P) with the
4534 // type that is required as the result of the conversion (call it
4535 // A) as described in 14.8.2.4.
4536 TemplateParameterList *TemplateParams
4537 = ConversionTemplate->getTemplateParameters();
4539 Deduced.resize(TemplateParams->size());
4540
4541 // C++0x [temp.deduct.conv]p4:
4542 // In general, the deduction process attempts to find template
4543 // argument values that will make the deduced A identical to
4544 // A. However, there are two cases that allow a difference:
4545 unsigned TDF = 0;
4546 // - If the original A is a reference type, A can be more
4547 // cv-qualified than the deduced A (i.e., the type referred to
4548 // by the reference)
4549 if (ToType->isReferenceType())
4551 // - The deduced A can be another pointer or pointer to member
4552 // type that can be converted to A via a qualification
4553 // conversion.
4554 //
4555 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
4556 // both P and A are pointers or member pointers. In this case, we
4557 // just ignore cv-qualifiers completely).
4558 if ((P->isPointerType() && A->isPointerType()) ||
4559 (P->isMemberPointerType() && A->isMemberPointerType()))
4560 TDF |= TDF_IgnoreQualifiers;
4562 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
4563 P, A, Info, Deduced, TDF))
4564 return Result;
4565
4566 // Create an Instantiation Scope for finalizing the operator.
4567 LocalInstantiationScope InstScope(*this);
4568 // Finish template argument deduction.
4569 FunctionDecl *ConversionSpecialized = nullptr;
4572 Result = FinishTemplateArgumentDeduction(ConversionTemplate, Deduced, 0,
4573 ConversionSpecialized, Info);
4574 });
4575 Specialization = cast_or_null<CXXConversionDecl>(ConversionSpecialized);
4576 return Result;
4577}
4578
4579/// Deduce template arguments for a function template when there is
4580/// nothing to deduce against (C++0x [temp.arg.explicit]p3).
4581///
4582/// \param FunctionTemplate the function template for which we are performing
4583/// template argument deduction.
4584///
4585/// \param ExplicitTemplateArgs the explicitly-specified template
4586/// arguments.
4587///
4588/// \param Specialization if template argument deduction was successful,
4589/// this will be set to the function template specialization produced by
4590/// template argument deduction.
4591///
4592/// \param Info the argument will be updated to provide additional information
4593/// about template argument deduction.
4594///
4595/// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4596/// the address of a function template in a context where we do not have a
4597/// target type, per [over.over]. If \c false, we are looking up a function
4598/// template specialization based on its signature, which only happens when
4599/// deducing a function parameter type from an argument that is a template-id
4600/// naming a function template specialization.
4601///
4602/// \returns the result of template argument deduction.
4604 FunctionTemplateDecl *FunctionTemplate,
4605 TemplateArgumentListInfo *ExplicitTemplateArgs,
4607 bool IsAddressOfFunction) {
4608 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
4609 QualType(), Specialization, Info,
4610 IsAddressOfFunction);
4611}
4612
4613namespace {
4614 struct DependentAuto { bool IsPack; };
4615
4616 /// Substitute the 'auto' specifier or deduced template specialization type
4617 /// specifier within a type for a given replacement type.
4618 class SubstituteDeducedTypeTransform :
4619 public TreeTransform<SubstituteDeducedTypeTransform> {
4620 QualType Replacement;
4621 bool ReplacementIsPack;
4622 bool UseTypeSugar;
4623
4624 public:
4625 SubstituteDeducedTypeTransform(Sema &SemaRef, DependentAuto DA)
4626 : TreeTransform<SubstituteDeducedTypeTransform>(SemaRef),
4627 ReplacementIsPack(DA.IsPack), UseTypeSugar(true) {}
4628
4629 SubstituteDeducedTypeTransform(Sema &SemaRef, QualType Replacement,
4630 bool UseTypeSugar = true)
4631 : TreeTransform<SubstituteDeducedTypeTransform>(SemaRef),
4632 Replacement(Replacement), ReplacementIsPack(false),
4633 UseTypeSugar(UseTypeSugar) {}
4634
4635 QualType TransformDesugared(TypeLocBuilder &TLB, DeducedTypeLoc TL) {
4636 assert(isa<TemplateTypeParmType>(Replacement) &&
4637 "unexpected unsugared replacement kind");
4638 QualType Result = Replacement;
4640 NewTL.setNameLoc(TL.getNameLoc());
4641 return Result;
4642 }
4643
4644 QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
4645 // If we're building the type pattern to deduce against, don't wrap the
4646 // substituted type in an AutoType. Certain template deduction rules
4647 // apply only when a template type parameter appears directly (and not if
4648 // the parameter is found through desugaring). For instance:
4649 // auto &&lref = lvalue;
4650 // must transform into "rvalue reference to T" not "rvalue reference to
4651 // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
4652 //
4653 // FIXME: Is this still necessary?
4654 if (!UseTypeSugar)
4655 return TransformDesugared(TLB, TL);
4656
4657 QualType Result = SemaRef.Context.getAutoType(
4658 Replacement, TL.getTypePtr()->getKeyword(), Replacement.isNull(),
4659 ReplacementIsPack, TL.getTypePtr()->getTypeConstraintConcept(),
4661 auto NewTL = TLB.push<AutoTypeLoc>(Result);
4662 NewTL.copy(TL);
4663 return Result;
4664 }
4665
4666 QualType TransformDeducedTemplateSpecializationType(
4668 if (!UseTypeSugar)
4669 return TransformDesugared(TLB, TL);
4670
4671 QualType Result = SemaRef.Context.getDeducedTemplateSpecializationType(
4673 Replacement, Replacement.isNull());
4674 auto NewTL = TLB.push<DeducedTemplateSpecializationTypeLoc>(Result);
4675 NewTL.setNameLoc(TL.getNameLoc());
4676 return Result;
4677 }
4678
4679 ExprResult TransformLambdaExpr(LambdaExpr *E) {
4680 // Lambdas never need to be transformed.
4681 return E;
4682 }
4683
4684 QualType Apply(TypeLoc TL) {
4685 // Create some scratch storage for the transformed type locations.
4686 // FIXME: We're just going to throw this information away. Don't build it.
4687 TypeLocBuilder TLB;
4688 TLB.reserve(TL.getFullDataSize());
4689 return TransformType(TLB, TL);
4690 }
4691 };
4692
4693} // namespace
4694
4697 QualType Deduced) {
4698 ConstraintSatisfaction Satisfaction;
4699 ConceptDecl *Concept = Type.getTypeConstraintConcept();
4700 TemplateArgumentListInfo TemplateArgs(TypeLoc.getLAngleLoc(),
4701 TypeLoc.getRAngleLoc());
4702 TemplateArgs.addArgument(
4705 Deduced, TypeLoc.getNameLoc())));
4706 for (unsigned I = 0, C = TypeLoc.getNumArgs(); I != C; ++I)
4707 TemplateArgs.addArgument(TypeLoc.getArgLoc(I));
4708
4709 llvm::SmallVector<TemplateArgument, 4> SugaredConverted, CanonicalConverted;
4710 if (S.CheckTemplateArgumentList(Concept, SourceLocation(), TemplateArgs,
4711 /*PartialTemplateArgs=*/false,
4712 SugaredConverted, CanonicalConverted))
4713 return true;
4714 MultiLevelTemplateArgumentList MLTAL(Concept, CanonicalConverted,
4715 /*Final=*/false);
4716 if (S.CheckConstraintSatisfaction(Concept, {Concept->getConstraintExpr()},
4718 Satisfaction))
4719 return true;
4720 if (!Satisfaction.IsSatisfied) {
4721 std::string Buf;
4722 llvm::raw_string_ostream OS(Buf);
4723 OS << "'" << Concept->getName();
4724 if (TypeLoc.hasExplicitTemplateArgs()) {
4726 OS, Type.getTypeConstraintArguments(), S.getPrintingPolicy(),
4727 Type.getTypeConstraintConcept()->getTemplateParameters());
4728 }
4729 OS << "'";
4730 OS.flush();
4731 S.Diag(TypeLoc.getConceptNameLoc(),
4732 diag::err_placeholder_constraints_not_satisfied)
4733 << Deduced << Buf << TypeLoc.getLocalSourceRange();
4734 S.DiagnoseUnsatisfiedConstraint(Satisfaction);
4735 return true;
4736 }
4737 return false;
4738}
4739
4740/// Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6)
4741///
4742/// Note that this is done even if the initializer is dependent. (This is
4743/// necessary to support partial ordering of templates using 'auto'.)
4744/// A dependent type will be produced when deducing from a dependent type.
4745///
4746/// \param Type the type pattern using the auto type-specifier.
4747/// \param Init the initializer for the variable whose type is to be deduced.
4748/// \param Result if type deduction was successful, this will be set to the
4749/// deduced type.
4750/// \param Info the argument will be updated to provide additional information
4751/// about template argument deduction.
4752/// \param DependentDeduction Set if we should permit deduction in
4753/// dependent cases. This is necessary for template partial ordering with
4754/// 'auto' template parameters. The template parameter depth to be used
4755/// should be specified in the 'Info' parameter.
4756/// \param IgnoreConstraints Set if we should not fail if the deduced type does
4757/// not satisfy the type-constraint in the auto type.
4760 TemplateDeductionInfo &Info, bool DependentDeduction,
4761 bool IgnoreConstraints,
4762 TemplateSpecCandidateSet *FailedTSC) {
4763 assert(DependentDeduction || Info.getDeducedDepth() == 0);
4764 if (Init->containsErrors())
4765 return TDK_AlreadyDiagnosed;
4766
4767 const AutoType *AT = Type.getType()->getContainedAutoType();
4768 assert(AT);
4769
4770 if (Init->getType()->isNonOverloadPlaceholderType() || AT->isDecltypeAuto()) {
4771 ExprResult NonPlaceholder = CheckPlaceholderExpr(Init);
4772 if (NonPlaceholder.isInvalid())
4773 return TDK_AlreadyDiagnosed;
4774 Init = NonPlaceholder.get();
4775 }
4776
4777 DependentAuto DependentResult = {
4778 /*.IsPack = */ (bool)Type.getAs<PackExpansionTypeLoc>()};
4779
4780 if (!DependentDeduction &&
4781 (Type.getType()->isDependentType() || Init->isTypeDependent() ||
4782 Init->containsUnexpandedParameterPack())) {
4783 Result = SubstituteDeducedTypeTransform(*this, DependentResult).Apply(Type);
4784 assert(!Result.isNull() && "substituting DependentTy can't fail");
4785 return TDK_Success;
4786 }
4787
4788 auto *InitList = dyn_cast<InitListExpr>(Init);
4789 if (!getLangOpts().CPlusPlus && InitList) {
4790 Diag(Init->getBeginLoc(), diag::err_auto_init_list_from_c);
4791 return TDK_AlreadyDiagnosed;
4792 }
4793
4794 // Deduce type of TemplParam in Func(Init)
4796 Deduced.resize(1);
4797
4798 // If deduction failed, don't diagnose if the initializer is dependent; it
4799 // might acquire a matching type in the instantiation.
4800 auto DeductionFailed = [&](TemplateDeductionResult TDK) {
4801 if (Init->isTypeDependent()) {
4802 Result =
4803 SubstituteDeducedTypeTransform(*this, DependentResult).Apply(Type);
4804 assert(!Result.isNull() && "substituting DependentTy can't fail");
4805 return TDK_Success;
4806 }
4807 return TDK;
4808 };
4809
4810 SmallVector<OriginalCallArg, 4> OriginalCallArgs;
4811
4813 // If this is a 'decltype(auto)' specifier, do the decltype dance.
4814 if (AT->isDecltypeAuto()) {
4815 if (InitList) {
4816 Diag(Init->getBeginLoc(), diag::err_decltype_auto_initializer_list);
4817 return TDK_AlreadyDiagnosed;
4818 }
4819
4821 assert(!DeducedType.isNull());
4822 } else {
4823 LocalInstantiationScope InstScope(*this);
4824
4825 // Build template<class TemplParam> void Func(FuncParam);
4826 SourceLocation Loc = Init->getExprLoc();
4828 Context, nullptr, SourceLocation(), Loc, Info.getDeducedDepth(), 0,
4829 nullptr, false, false, false);
4830 QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
4831 NamedDecl *TemplParamPtr = TemplParam;
4833 Context, Loc, Loc, TemplParamPtr, Loc, nullptr);
4834
4835 if (InitList) {
4836 // Notionally, we substitute std::initializer_list<T> for 'auto' and
4837 // deduce against that. Such deduction only succeeds if removing
4838 // cv-qualifiers and references results in std::initializer_list<T>.
4839 if (!Type.getType().getNonReferenceType()->getAs<AutoType>())
4840 return TDK_Invalid;
4841
4842 SourceRange DeducedFromInitRange;
4843 for (Expr *Init : InitList->inits()) {
4844 // Resolving a core issue: a braced-init-list containing any designators
4845 // is a non-deduced context.
4846 if (isa<DesignatedInitExpr>(Init))
4847 return TDK_Invalid;
4849 *this, TemplateParamsSt.get(), 0, TemplArg, Init, Info, Deduced,
4850 OriginalCallArgs, /*Decomposed=*/true,
4851 /*ArgIdx=*/0, /*TDF=*/0)) {
4852 if (TDK == TDK_Inconsistent) {
4853 Diag(Info.getLocation(), diag::err_auto_inconsistent_deduction)
4854 << Info.FirstArg << Info.SecondArg << DeducedFromInitRange
4855 << Init->getSourceRange();
4856 return DeductionFailed(TDK_AlreadyDiagnosed);
4857 }
4858 return DeductionFailed(TDK);
4859 }
4860
4861 if (DeducedFromInitRange.isInvalid() &&
4862 Deduced[0].getKind() != TemplateArgument::Null)
4863 DeducedFromInitRange = Init->getSourceRange();
4864 }
4865 } else {
4866 if (!getLangOpts().CPlusPlus && Init->refersToBitField()) {
4867 Diag(Loc, diag::err_auto_bitfield);
4868 return TDK_AlreadyDiagnosed;
4869 }
4870 QualType FuncParam =
4871 SubstituteDeducedTypeTransform(*this, TemplArg).Apply(Type);
4872 assert(!FuncParam.isNull() &&
4873 "substituting template parameter for 'auto' failed");
4875 *this, TemplateParamsSt.get(), 0, FuncParam, Init, Info, Deduced,
4876 OriginalCallArgs, /*Decomposed=*/false, /*ArgIdx=*/0, /*TDF=*/0,
4877 FailedTSC))
4878 return DeductionFailed(TDK);
4879 }
4880
4881 // Could be null if somehow 'auto' appears in a non-deduced context.
4882 if (Deduced[0].getKind() != TemplateArgument::Type)
4883 return DeductionFailed(TDK_Incomplete);
4884 DeducedType = Deduced[0].getAsType();
4885
4886 if (InitList) {
4888 if (DeducedType.isNull())
4889 return TDK_AlreadyDiagnosed;
4890 }
4891 }
4892
4893 if (!Result.isNull()) {
4895 Info.FirstArg = Result;
4896 Info.SecondArg = DeducedType;
4897 return DeductionFailed(TDK_Inconsistent);
4898 }
4900 }
4901
4902 if (AT->isConstrained() && !IgnoreConstraints &&
4904 *this, *AT, Type.getContainedAutoTypeLoc(), DeducedType))
4905 return TDK_AlreadyDiagnosed;
4906
4907 Result = SubstituteDeducedTypeTransform(*this, DeducedType).Apply(Type);
4908 if (Result.isNull())
4909 return TDK_AlreadyDiagnosed;
4910
4911 // Check that the deduced argument type is compatible with the original
4912 // argument type per C++ [temp.deduct.call]p4.
4913 QualType DeducedA = InitList ? Deduced[0].getAsType() : Result;
4914 for (const OriginalCallArg &OriginalArg : OriginalCallArgs) {
4915 assert((bool)InitList == OriginalArg.DecomposedParam &&
4916 "decomposed non-init-list in auto deduction?");
4917 if (auto TDK =
4918 CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA)) {
4919 Result = QualType();
4920 return DeductionFailed(TDK);
4921 }
4922 }
4923
4924 return TDK_Success;
4925}
4926
4928 QualType TypeToReplaceAuto) {
4929 assert(TypeToReplaceAuto != Context.DependentTy);
4930 return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto)
4931 .TransformType(TypeWithAuto);
4932}
4933
4935 QualType TypeToReplaceAuto) {
4936 assert(TypeToReplaceAuto != Context.DependentTy);
4937 return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto)
4938 .TransformType(TypeWithAuto);
4939}
4940
4942 return SubstituteDeducedTypeTransform(*this, DependentAuto{false})
4943 .TransformType(TypeWithAuto);
4944}
4945
4948 return SubstituteDeducedTypeTransform(*this, DependentAuto{false})
4949 .TransformType(TypeWithAuto);
4950}
4951
4953 QualType TypeToReplaceAuto) {
4954 return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto,
4955 /*UseTypeSugar*/ false)
4956 .TransformType(TypeWithAuto);
4957}
4958
4960 QualType TypeToReplaceAuto) {
4961 return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto,
4962 /*UseTypeSugar*/ false)
4963 .TransformType(TypeWithAuto);
4964}
4965
4967 if (isa<InitListExpr>(Init))
4968 Diag(VDecl->getLocation(),
4969 VDecl->isInitCapture()
4970 ? diag::err_init_capture_deduction_failure_from_init_list
4971 : diag::err_auto_var_deduction_failure_from_init_list)
4972 << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange();
4973 else
4974 Diag<