clang  16.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 
14 #include "TreeTransform.h"
15 #include "TypeLocBuilder.h"
16 #include "clang/AST/ASTContext.h"
17 #include "clang/AST/ASTLambda.h"
18 #include "clang/AST/Decl.h"
20 #include "clang/AST/DeclBase.h"
21 #include "clang/AST/DeclCXX.h"
22 #include "clang/AST/DeclTemplate.h"
24 #include "clang/AST/Expr.h"
25 #include "clang/AST/ExprCXX.h"
28 #include "clang/AST/TemplateBase.h"
29 #include "clang/AST/TemplateName.h"
30 #include "clang/AST/Type.h"
31 #include "clang/AST/TypeLoc.h"
35 #include "clang/Basic/LLVM.h"
39 #include "clang/Basic/Specifiers.h"
40 #include "clang/Sema/Ownership.h"
41 #include "clang/Sema/Sema.h"
42 #include "clang/Sema/Template.h"
43 #include "llvm/ADT/APInt.h"
44 #include "llvm/ADT/APSInt.h"
45 #include "llvm/ADT/ArrayRef.h"
46 #include "llvm/ADT/DenseMap.h"
47 #include "llvm/ADT/FoldingSet.h"
48 #include "llvm/ADT/Optional.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 <tuple>
58 #include <type_traits>
59 #include <utility>
60 
61 namespace clang {
62 
63  /// Various flags that control template argument deduction.
64  ///
65  /// These flags can be bitwise-OR'd together.
67  /// No template argument deduction flags, which indicates the
68  /// strictest results for template argument deduction (as used for, e.g.,
69  /// matching class template partial specializations).
70  TDF_None = 0,
71 
72  /// Within template argument deduction from a function call, we are
73  /// matching with a parameter type for which the original parameter was
74  /// a reference.
76 
77  /// Within template argument deduction from a function call, we
78  /// are matching in a case where we ignore cv-qualifiers.
80 
81  /// Within template argument deduction from a function call,
82  /// we are matching in a case where we can perform template argument
83  /// deduction from a template-id of a derived class of the argument type.
85 
86  /// Allow non-dependent types to differ, e.g., when performing
87  /// template argument deduction from a function call where conversions
88  /// may apply.
90 
91  /// Whether we are performing template argument deduction for
92  /// parameters and arguments in a top-level template argument
94 
95  /// Within template argument deduction from overload resolution per
96  /// C++ [over.over] allow matching function types that are compatible in
97  /// terms of noreturn and default calling convention adjustments, or
98  /// similarly matching a declared template specialization against a
99  /// possible template, per C++ [temp.deduct.decl]. In either case, permit
100  /// deduction where the parameter is a function type that can be converted
101  /// to the argument type.
103 
104  /// Within template argument deduction for a conversion function, we are
105  /// matching with an argument type for which the original argument was
106  /// a reference.
108  };
109 }
110 
111 using namespace clang;
112 using namespace sema;
113 
114 /// Compare two APSInts, extending and switching the sign as
115 /// necessary to compare their values regardless of underlying type.
117  if (Y.getBitWidth() > X.getBitWidth())
118  X = X.extend(Y.getBitWidth());
119  else if (Y.getBitWidth() < X.getBitWidth())
120  Y = Y.extend(X.getBitWidth());
121 
122  // If there is a signedness mismatch, correct it.
123  if (X.isSigned() != Y.isSigned()) {
124  // If the signed value is negative, then the values cannot be the same.
125  if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative()))
126  return false;
127 
128  Y.setIsSigned(true);
129  X.setIsSigned(true);
130  }
131 
132  return X == Y;
133 }
134 
136  Sema &S, TemplateParameterList *TemplateParams, QualType Param,
137  QualType Arg, TemplateDeductionInfo &Info,
138  SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF,
139  bool PartialOrdering = false, bool DeducedFromArrayBound = false);
140 
145  TemplateDeductionInfo &Info,
146  SmallVectorImpl<DeducedTemplateArgument> &Deduced,
147  bool NumberOfArgumentsMustMatch);
148 
149 static void MarkUsedTemplateParameters(ASTContext &Ctx,
150  const TemplateArgument &TemplateArg,
151  bool OnlyDeduced, unsigned Depth,
152  llvm::SmallBitVector &Used);
153 
155  bool OnlyDeduced, unsigned Level,
156  llvm::SmallBitVector &Deduced);
157 
158 /// If the given expression is of a form that permits the deduction
159 /// of a non-type template parameter, return the declaration of that
160 /// non-type template parameter.
161 static const NonTypeTemplateParmDecl *
163  // If we are within an alias template, the expression may have undergone
164  // any number of parameter substitutions already.
165  while (true) {
166  if (const auto *IC = dyn_cast<ImplicitCastExpr>(E))
167  E = IC->getSubExpr();
168  else if (const auto *CE = dyn_cast<ConstantExpr>(E))
169  E = CE->getSubExpr();
170  else if (const auto *Subst = dyn_cast<SubstNonTypeTemplateParmExpr>(E))
171  E = Subst->getReplacement();
172  else if (const auto *CCE = dyn_cast<CXXConstructExpr>(E)) {
173  // Look through implicit copy construction from an lvalue of the same type.
174  if (CCE->getParenOrBraceRange().isValid())
175  break;
176  // Note, there could be default arguments.
177  assert(CCE->getNumArgs() >= 1 && "implicit construct expr should have 1 arg");
178  E = CCE->getArg(0);
179  } else
180  break;
181  }
182 
183  if (const auto *DRE = dyn_cast<DeclRefExpr>(E))
184  if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()))
185  if (NTTP->getDepth() == Depth)
186  return NTTP;
187 
188  return nullptr;
189 }
190 
191 static const NonTypeTemplateParmDecl *
194 }
195 
196 /// Determine whether two declaration pointers refer to the same
197 /// declaration.
198 static bool isSameDeclaration(Decl *X, Decl *Y) {
199  if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
200  X = NX->getUnderlyingDecl();
201  if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
202  Y = NY->getUnderlyingDecl();
203 
204  return X->getCanonicalDecl() == Y->getCanonicalDecl();
205 }
206 
207 /// Verify that the given, deduced template arguments are compatible.
208 ///
209 /// \returns The deduced template argument, or a NULL template argument if
210 /// the deduced template arguments were incompatible.
213  const DeducedTemplateArgument &X,
214  const DeducedTemplateArgument &Y) {
215  // We have no deduction for one or both of the arguments; they're compatible.
216  if (X.isNull())
217  return Y;
218  if (Y.isNull())
219  return X;
220 
221  // If we have two non-type template argument values deduced for the same
222  // parameter, they must both match the type of the parameter, and thus must
223  // match each other's type. As we're only keeping one of them, we must check
224  // for that now. The exception is that if either was deduced from an array
225  // bound, the type is permitted to differ.
226  if (!X.wasDeducedFromArrayBound() && !Y.wasDeducedFromArrayBound()) {
227  QualType XType = X.getNonTypeTemplateArgumentType();
228  if (!XType.isNull()) {
230  if (YType.isNull() || !Context.hasSameType(XType, YType))
231  return DeducedTemplateArgument();
232  }
233  }
234 
235  switch (X.getKind()) {
237  llvm_unreachable("Non-deduced template arguments handled above");
238 
239  case TemplateArgument::Type: {
240  // If two template type arguments have the same type, they're compatible.
241  QualType TX = X.getAsType(), TY = Y.getAsType();
242  if (Y.getKind() == TemplateArgument::Type && Context.hasSameType(TX, TY))
243  return DeducedTemplateArgument(Context.getCommonSugaredType(TX, TY),
244  X.wasDeducedFromArrayBound() ||
246 
247  // If one of the two arguments was deduced from an array bound, the other
248  // supersedes it.
249  if (X.wasDeducedFromArrayBound() != Y.wasDeducedFromArrayBound())
250  return X.wasDeducedFromArrayBound() ? Y : X;
251 
252  // The arguments are not compatible.
253  return DeducedTemplateArgument();
254  }
255 
257  // If we deduced a constant in one case and either a dependent expression or
258  // declaration in another case, keep the integral constant.
259  // If both are integral constants with the same value, keep that value.
263  hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral())))
264  return X.wasDeducedFromArrayBound() ? Y : X;
265 
266  // All other combinations are incompatible.
267  return DeducedTemplateArgument();
268 
270  if (Y.getKind() == TemplateArgument::Template &&
271  Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
272  return X;
273 
274  // All other combinations are incompatible.
275  return DeducedTemplateArgument();
276 
279  Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
281  return X;
282 
283  // All other combinations are incompatible.
284  return DeducedTemplateArgument();
285 
288  return checkDeducedTemplateArguments(Context, Y, X);
289 
290  // Compare the expressions for equality
291  llvm::FoldingSetNodeID ID1, ID2;
292  X.getAsExpr()->Profile(ID1, Context, true);
293  Y.getAsExpr()->Profile(ID2, Context, true);
294  if (ID1 == ID2)
295  return X.wasDeducedFromArrayBound() ? Y : X;
296 
297  // Differing dependent expressions are incompatible.
298  return DeducedTemplateArgument();
299  }
300 
302  assert(!X.wasDeducedFromArrayBound());
303 
304  // If we deduced a declaration and a dependent expression, keep the
305  // declaration.
307  return X;
308 
309  // If we deduced a declaration and an integral constant, keep the
310  // integral constant and whichever type did not come from an array
311  // bound.
312  if (Y.getKind() == TemplateArgument::Integral) {
313  if (Y.wasDeducedFromArrayBound())
314  return TemplateArgument(Context, Y.getAsIntegral(),
315  X.getParamTypeForDecl());
316  return Y;
317  }
318 
319  // If we deduced two declarations, make sure that they refer to the
320  // same declaration.
322  isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))
323  return X;
324 
325  // All other combinations are incompatible.
326  return DeducedTemplateArgument();
327 
329  // If we deduced a null pointer and a dependent expression, keep the
330  // null pointer.
332  return TemplateArgument(Context.getCommonSugaredType(
333  X.getNullPtrType(), Y.getAsExpr()->getType()),
334  true);
335 
336  // If we deduced a null pointer and an integral constant, keep the
337  // integral constant.
339  return Y;
340 
341  // If we deduced two null pointers, they are the same.
343  return TemplateArgument(
344  Context.getCommonSugaredType(X.getNullPtrType(), Y.getNullPtrType()),
345  true);
346 
347  // All other combinations are incompatible.
348  return DeducedTemplateArgument();
349 
350  case TemplateArgument::Pack: {
351  if (Y.getKind() != TemplateArgument::Pack ||
352  X.pack_size() != Y.pack_size())
353  return DeducedTemplateArgument();
354 
356  for (TemplateArgument::pack_iterator XA = X.pack_begin(),
357  XAEnd = X.pack_end(),
358  YA = Y.pack_begin();
359  XA != XAEnd; ++XA, ++YA) {
361  Context, DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
363  if (Merged.isNull() && !(XA->isNull() && YA->isNull()))
364  return DeducedTemplateArgument();
365  NewPack.push_back(Merged);
366  }
367 
369  TemplateArgument::CreatePackCopy(Context, NewPack),
370  X.wasDeducedFromArrayBound() && Y.wasDeducedFromArrayBound());
371  }
372  }
373 
374  llvm_unreachable("Invalid TemplateArgument Kind!");
375 }
376 
377 /// Deduce the value of the given non-type template parameter
378 /// as the given deduced template argument. All non-type template parameter
379 /// deduction is funneled through here.
381  Sema &S, TemplateParameterList *TemplateParams,
382  const NonTypeTemplateParmDecl *NTTP, const DeducedTemplateArgument &NewDeduced,
383  QualType ValueType, TemplateDeductionInfo &Info,
384  SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
385  assert(NTTP->getDepth() == Info.getDeducedDepth() &&
386  "deducing non-type template argument with wrong depth");
387 
389  S.Context, Deduced[NTTP->getIndex()], NewDeduced);
390  if (Result.isNull()) {
391  Info.Param = const_cast<NonTypeTemplateParmDecl*>(NTTP);
392  Info.FirstArg = Deduced[NTTP->getIndex()];
393  Info.SecondArg = NewDeduced;
394  return Sema::TDK_Inconsistent;
395  }
396 
397  Deduced[NTTP->getIndex()] = Result;
398  if (!S.getLangOpts().CPlusPlus17)
399  return Sema::TDK_Success;
400 
401  if (NTTP->isExpandedParameterPack())
402  // FIXME: We may still need to deduce parts of the type here! But we
403  // don't have any way to find which slice of the type to use, and the
404  // type stored on the NTTP itself is nonsense. Perhaps the type of an
405  // expanded NTTP should be a pack expansion type?
406  return Sema::TDK_Success;
407 
408  // Get the type of the parameter for deduction. If it's a (dependent) array
409  // or function type, we will not have decayed it yet, so do that now.
410  QualType ParamType = S.Context.getAdjustedParameterType(NTTP->getType());
411  if (auto *Expansion = dyn_cast<PackExpansionType>(ParamType))
412  ParamType = Expansion->getPattern();
413 
414  // FIXME: It's not clear how deduction of a parameter of reference
415  // type from an argument (of non-reference type) should be performed.
416  // For now, we just remove reference types from both sides and let
417  // the final check for matching types sort out the mess.
418  ValueType = ValueType.getNonReferenceType();
419  if (ParamType->isReferenceType())
420  ParamType = ParamType.getNonReferenceType();
421  else
422  // Top-level cv-qualifiers are irrelevant for a non-reference type.
423  ValueType = ValueType.getUnqualifiedType();
424 
426  S, TemplateParams, ParamType, ValueType, Info, Deduced,
427  TDF_SkipNonDependent, /*PartialOrdering=*/false,
428  /*ArrayBound=*/NewDeduced.wasDeducedFromArrayBound());
429 }
430 
431 /// Deduce the value of the given non-type template parameter
432 /// from the given integral constant.
434  Sema &S, TemplateParameterList *TemplateParams,
435  const NonTypeTemplateParmDecl *NTTP, const llvm::APSInt &Value,
436  QualType ValueType, bool DeducedFromArrayBound, TemplateDeductionInfo &Info,
437  SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
439  S, TemplateParams, NTTP,
440  DeducedTemplateArgument(S.Context, Value, ValueType,
441  DeducedFromArrayBound),
442  ValueType, Info, Deduced);
443 }
444 
445 /// Deduce the value of the given non-type template parameter
446 /// from the given null pointer template argument type.
448  Sema &S, TemplateParameterList *TemplateParams,
449  const NonTypeTemplateParmDecl *NTTP, QualType NullPtrType,
450  TemplateDeductionInfo &Info,
451  SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
454  NTTP->getLocation()),
455  NullPtrType,
456  NullPtrType->isMemberPointerType() ? CK_NullToMemberPointer
457  : CK_NullToPointer)
458  .get();
459  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
461  Value->getType(), Info, Deduced);
462 }
463 
464 /// Deduce the value of the given non-type template parameter
465 /// from the given type- or value-dependent expression.
466 ///
467 /// \returns true if deduction succeeded, false otherwise.
469  Sema &S, TemplateParameterList *TemplateParams,
471  SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
472  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
474  Value->getType(), Info, Deduced);
475 }
476 
477 /// Deduce the value of the given non-type template parameter
478 /// from the given declaration.
479 ///
480 /// \returns true if deduction succeeded, false otherwise.
482  Sema &S, TemplateParameterList *TemplateParams,
483  const NonTypeTemplateParmDecl *NTTP, ValueDecl *D, QualType T,
484  TemplateDeductionInfo &Info,
485  SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
486  D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : nullptr;
487  TemplateArgument New(D, T);
489  S, TemplateParams, NTTP, DeducedTemplateArgument(New), T, Info, Deduced);
490 }
491 
494  TemplateParameterList *TemplateParams,
495  TemplateName Param,
496  TemplateName Arg,
497  TemplateDeductionInfo &Info,
498  SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
499  TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
500  if (!ParamDecl) {
501  // The parameter type is dependent and is not a template template parameter,
502  // so there is nothing that we can deduce.
503  return Sema::TDK_Success;
504  }
505 
506  if (TemplateTemplateParmDecl *TempParam
507  = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
508  // If we're not deducing at this depth, there's nothing to deduce.
509  if (TempParam->getDepth() != Info.getDeducedDepth())
510  return Sema::TDK_Success;
511 
514  Deduced[TempParam->getIndex()],
515  NewDeduced);
516  if (Result.isNull()) {
517  Info.Param = TempParam;
518  Info.FirstArg = Deduced[TempParam->getIndex()];
519  Info.SecondArg = NewDeduced;
520  return Sema::TDK_Inconsistent;
521  }
522 
523  Deduced[TempParam->getIndex()] = Result;
524  return Sema::TDK_Success;
525  }
526 
527  // Verify that the two template names are equivalent.
528  if (S.Context.hasSameTemplateName(Param, Arg))
529  return Sema::TDK_Success;
530 
531  // Mismatch of non-dependent template parameter to argument.
532  Info.FirstArg = TemplateArgument(Param);
533  Info.SecondArg = TemplateArgument(Arg);
535 }
536 
537 /// Deduce the template arguments by comparing the template parameter
538 /// type (which is a template-id) with the template argument type.
539 ///
540 /// \param S the Sema
541 ///
542 /// \param TemplateParams the template parameters that we are deducing
543 ///
544 /// \param P the parameter type
545 ///
546 /// \param A the argument type
547 ///
548 /// \param Info information about the template argument deduction itself
549 ///
550 /// \param Deduced the deduced template arguments
551 ///
552 /// \returns the result of template argument deduction so far. Note that a
553 /// "success" result means that template argument deduction has not yet failed,
554 /// but it may still fail, later, for other reasons.
557  const QualType P, QualType A,
558  TemplateDeductionInfo &Info,
559  SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
560  QualType UP = P;
561  if (const auto *IP = P->getAs<InjectedClassNameType>())
562  UP = IP->getInjectedSpecializationType();
563  // FIXME: Try to preserve type sugar here, which is hard
564  // because of the unresolved template arguments.
565  const auto *TP = UP.getCanonicalType()->castAs<TemplateSpecializationType>();
566  TemplateName TNP = TP->getTemplateName();
567 
568  // If the parameter is an alias template, there is nothing to deduce.
569  if (const auto *TD = TNP.getAsTemplateDecl(); TD && TD->isTypeAlias())
570  return Sema::TDK_Success;
571 
572  ArrayRef<TemplateArgument> PResolved = TP->template_arguments();
573 
574  QualType UA = A;
575  // Treat an injected-class-name as its underlying template-id.
576  if (const auto *Injected = A->getAs<InjectedClassNameType>())
577  UA = Injected->getInjectedSpecializationType();
578 
579  // Check whether the template argument is a dependent template-id.
580  // FIXME: Should not lose sugar here.
581  if (const auto *SA =
582  dyn_cast<TemplateSpecializationType>(UA.getCanonicalType())) {
583  TemplateName TNA = SA->getTemplateName();
584 
585  // If the argument is an alias template, there is nothing to deduce.
586  if (const auto *TD = TNA.getAsTemplateDecl(); TD && TD->isTypeAlias())
587  return Sema::TDK_Success;
588 
589  // Perform template argument deduction for the template name.
590  if (auto Result =
591  DeduceTemplateArguments(S, TemplateParams, TNP, TNA, Info, Deduced))
592  return Result;
593  // Perform template argument deduction on each template
594  // argument. Ignore any missing/extra arguments, since they could be
595  // filled in by default arguments.
596  return DeduceTemplateArguments(S, TemplateParams, PResolved,
597  SA->template_arguments(), Info, Deduced,
598  /*NumberOfArgumentsMustMatch=*/false);
599  }
600 
601  // If the argument type is a class template specialization, we
602  // perform template argument deduction using its template
603  // arguments.
604  const auto *RA = UA->getAs<RecordType>();
605  const auto *SA =
606  RA ? dyn_cast<ClassTemplateSpecializationDecl>(RA->getDecl()) : nullptr;
607  if (!SA) {
608  Info.FirstArg = TemplateArgument(P);
609  Info.SecondArg = TemplateArgument(A);
611  }
612 
613  // Perform template argument deduction for the template name.
614  if (auto Result = DeduceTemplateArguments(
615  S, TemplateParams, TP->getTemplateName(),
616  TemplateName(SA->getSpecializedTemplate()), Info, Deduced))
617  return Result;
618 
619  // Perform template argument deduction for the template arguments.
620  return DeduceTemplateArguments(S, TemplateParams, PResolved,
621  SA->getTemplateArgs().asArray(), Info, Deduced,
622  /*NumberOfArgumentsMustMatch=*/true);
623 }
624 
626  assert(T->isCanonicalUnqualified());
627 
628  switch (T->getTypeClass()) {
629  case Type::TypeOfExpr:
630  case Type::TypeOf:
631  case Type::DependentName:
632  case Type::Decltype:
633  case Type::UnresolvedUsing:
634  case Type::TemplateTypeParm:
635  return true;
636 
637  case Type::ConstantArray:
638  case Type::IncompleteArray:
639  case Type::VariableArray:
640  case Type::DependentSizedArray:
642  cast<ArrayType>(T)->getElementType().getTypePtr());
643 
644  default:
645  return false;
646  }
647 }
648 
649 /// Determines whether the given type is an opaque type that
650 /// might be more qualified when instantiated.
654 }
655 
656 /// Helper function to build a TemplateParameter when we don't
657 /// know its type statically.
659  if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
660  return TemplateParameter(TTP);
661  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
662  return TemplateParameter(NTTP);
663 
664  return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
665 }
666 
667 /// A pack that we're currently deducing.
669  // The index of the pack.
670  unsigned Index;
671 
672  // The old value of the pack before we started deducing it.
674 
675  // A deferred value of this pack from an inner deduction, that couldn't be
676  // deduced because this deduction hadn't happened yet.
678 
679  // The new value of the pack.
681 
682  // The outer deduction for this pack, if any.
683  DeducedPack *Outer = nullptr;
684 
685  DeducedPack(unsigned Index) : Index(Index) {}
686 };
687 
688 namespace {
689 
690 /// A scope in which we're performing pack deduction.
691 class PackDeductionScope {
692 public:
693  /// Prepare to deduce the packs named within Pattern.
694  PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
695  SmallVectorImpl<DeducedTemplateArgument> &Deduced,
697  : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
698  unsigned NumNamedPacks = addPacks(Pattern);
699  finishConstruction(NumNamedPacks);
700  }
701 
702  /// Prepare to directly deduce arguments of the parameter with index \p Index.
703  PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
704  SmallVectorImpl<DeducedTemplateArgument> &Deduced,
705  TemplateDeductionInfo &Info, unsigned Index)
706  : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
707  addPack(Index);
708  finishConstruction(1);
709  }
710 
711 private:
712  void addPack(unsigned Index) {
713  // Save the deduced template argument for the parameter pack expanded
714  // by this pack expansion, then clear out the deduction.
715  DeducedPack Pack(Index);
716  Pack.Saved = Deduced[Index];
717  Deduced[Index] = TemplateArgument();
718 
719  // FIXME: What if we encounter multiple packs with different numbers of
720  // pre-expanded expansions? (This should already have been diagnosed
721  // during substitution.)
722  if (Optional<unsigned> ExpandedPackExpansions =
723  getExpandedPackSize(TemplateParams->getParam(Index)))
724  FixedNumExpansions = ExpandedPackExpansions;
725 
726  Packs.push_back(Pack);
727  }
728 
729  unsigned addPacks(TemplateArgument Pattern) {
730  // Compute the set of template parameter indices that correspond to
731  // parameter packs expanded by the pack expansion.
732  llvm::SmallBitVector SawIndices(TemplateParams->size());
734 
735  auto AddPack = [&](unsigned Index) {
736  if (SawIndices[Index])
737  return;
738  SawIndices[Index] = true;
739  addPack(Index);
740 
741  // Deducing a parameter pack that is a pack expansion also constrains the
742  // packs appearing in that parameter to have the same deduced arity. Also,
743  // in C++17 onwards, deducing a non-type template parameter deduces its
744  // type, so we need to collect the pending deduced values for those packs.
745  if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(
746  TemplateParams->getParam(Index))) {
747  if (!NTTP->isExpandedParameterPack())
748  if (auto *Expansion = dyn_cast<PackExpansionType>(NTTP->getType()))
749  ExtraDeductions.push_back(Expansion->getPattern());
750  }
751  // FIXME: Also collect the unexpanded packs in any type and template
752  // parameter packs that are pack expansions.
753  };
754 
755  auto Collect = [&](TemplateArgument Pattern) {
757  S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
758  for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
759  UnexpandedParameterPack U = Unexpanded[I];
760  if (U.first.is<const SubstTemplateTypeParmPackType *>() ||
761  U.first.is<const SubstNonTypeTemplateParmPackExpr *>())
762  continue;
763  auto [Depth, Index] = getDepthAndIndex(U);
764  if (Depth == Info.getDeducedDepth())
765  AddPack(Index);
766  }
767  };
768 
769  // Look for unexpanded packs in the pattern.
770  Collect(Pattern);
771  assert(!Packs.empty() && "Pack expansion without unexpanded packs?");
772 
773  unsigned NumNamedPacks = Packs.size();
774 
775  // Also look for unexpanded packs that are indirectly deduced by deducing
776  // the sizes of the packs in this pattern.
777  while (!ExtraDeductions.empty())
778  Collect(ExtraDeductions.pop_back_val());
779 
780  return NumNamedPacks;
781  }
782 
783  void finishConstruction(unsigned NumNamedPacks) {
784  // Dig out the partially-substituted pack, if there is one.
785  const TemplateArgument *PartialPackArgs = nullptr;
786  unsigned NumPartialPackArgs = 0;
787  std::pair<unsigned, unsigned> PartialPackDepthIndex(-1u, -1u);
788  if (auto *Scope = S.CurrentInstantiationScope)
789  if (auto *Partial = Scope->getPartiallySubstitutedPack(
790  &PartialPackArgs, &NumPartialPackArgs))
791  PartialPackDepthIndex = getDepthAndIndex(Partial);
792 
793  // This pack expansion will have been partially or fully expanded if
794  // it only names explicitly-specified parameter packs (including the
795  // partially-substituted one, if any).
796  bool IsExpanded = true;
797  for (unsigned I = 0; I != NumNamedPacks; ++I) {
798  if (Packs[I].Index >= Info.getNumExplicitArgs()) {
799  IsExpanded = false;
800  IsPartiallyExpanded = false;
801  break;
802  }
803  if (PartialPackDepthIndex ==
804  std::make_pair(Info.getDeducedDepth(), Packs[I].Index)) {
805  IsPartiallyExpanded = true;
806  }
807  }
808 
809  // Skip over the pack elements that were expanded into separate arguments.
810  // If we partially expanded, this is the number of partial arguments.
811  if (IsPartiallyExpanded)
812  PackElements += NumPartialPackArgs;
813  else if (IsExpanded)
814  PackElements += *FixedNumExpansions;
815 
816  for (auto &Pack : Packs) {
817  if (Info.PendingDeducedPacks.size() > Pack.Index)
818  Pack.Outer = Info.PendingDeducedPacks[Pack.Index];
819  else
820  Info.PendingDeducedPacks.resize(Pack.Index + 1);
821  Info.PendingDeducedPacks[Pack.Index] = &Pack;
822 
823  if (PartialPackDepthIndex ==
824  std::make_pair(Info.getDeducedDepth(), Pack.Index)) {
825  Pack.New.append(PartialPackArgs, PartialPackArgs + NumPartialPackArgs);
826  // We pre-populate the deduced value of the partially-substituted
827  // pack with the specified value. This is not entirely correct: the
828  // value is supposed to have been substituted, not deduced, but the
829  // cases where this is observable require an exact type match anyway.
830  //
831  // FIXME: If we could represent a "depth i, index j, pack elem k"
832  // parameter, we could substitute the partially-substituted pack
833  // everywhere and avoid this.
834  if (!IsPartiallyExpanded)
835  Deduced[Pack.Index] = Pack.New[PackElements];
836  }
837  }
838  }
839 
840 public:
841  ~PackDeductionScope() {
842  for (auto &Pack : Packs)
843  Info.PendingDeducedPacks[Pack.Index] = Pack.Outer;
844  }
845 
846  /// Determine whether this pack has already been partially expanded into a
847  /// sequence of (prior) function parameters / template arguments.
848  bool isPartiallyExpanded() { return IsPartiallyExpanded; }
849 
850  /// Determine whether this pack expansion scope has a known, fixed arity.
851  /// This happens if it involves a pack from an outer template that has
852  /// (notionally) already been expanded.
853  bool hasFixedArity() { return FixedNumExpansions.has_value(); }
854 
855  /// Determine whether the next element of the argument is still part of this
856  /// pack. This is the case unless the pack is already expanded to a fixed
857  /// length.
858  bool hasNextElement() {
859  return !FixedNumExpansions || *FixedNumExpansions > PackElements;
860  }
861 
862  /// Move to deducing the next element in each pack that is being deduced.
863  void nextPackElement() {
864  // Capture the deduced template arguments for each parameter pack expanded
865  // by this pack expansion, add them to the list of arguments we've deduced
866  // for that pack, then clear out the deduced argument.
867  for (auto &Pack : Packs) {
868  DeducedTemplateArgument &DeducedArg = Deduced[Pack.Index];
869  if (!Pack.New.empty() || !DeducedArg.isNull()) {
870  while (Pack.New.size() < PackElements)
871  Pack.New.push_back(DeducedTemplateArgument());
872  if (Pack.New.size() == PackElements)
873  Pack.New.push_back(DeducedArg);
874  else
875  Pack.New[PackElements] = DeducedArg;
876  DeducedArg = Pack.New.size() > PackElements + 1
877  ? Pack.New[PackElements + 1]
879  }
880  }
881  ++PackElements;
882  }
883 
884  /// Finish template argument deduction for a set of argument packs,
885  /// producing the argument packs and checking for consistency with prior
886  /// deductions.
888  // Build argument packs for each of the parameter packs expanded by this
889  // pack expansion.
890  for (auto &Pack : Packs) {
891  // Put back the old value for this pack.
892  Deduced[Pack.Index] = Pack.Saved;
893 
894  // Always make sure the size of this pack is correct, even if we didn't
895  // deduce any values for it.
896  //
897  // FIXME: This isn't required by the normative wording, but substitution
898  // and post-substitution checking will always fail if the arity of any
899  // pack is not equal to the number of elements we processed. (Either that
900  // or something else has gone *very* wrong.) We're permitted to skip any
901  // hard errors from those follow-on steps by the intent (but not the
902  // wording) of C++ [temp.inst]p8:
903  //
904  // If the function selected by overload resolution can be determined
905  // without instantiating a class template definition, it is unspecified
906  // whether that instantiation actually takes place
907  Pack.New.resize(PackElements);
908 
909  // Build or find a new value for this pack.
910  DeducedTemplateArgument NewPack;
911  if (Pack.New.empty()) {
912  // If we deduced an empty argument pack, create it now.
914  } else {
915  TemplateArgument *ArgumentPack =
916  new (S.Context) TemplateArgument[Pack.New.size()];
917  std::copy(Pack.New.begin(), Pack.New.end(), ArgumentPack);
918  NewPack = DeducedTemplateArgument(
919  TemplateArgument(llvm::makeArrayRef(ArgumentPack, Pack.New.size())),
920  // FIXME: This is wrong, it's possible that some pack elements are
921  // deduced from an array bound and others are not:
922  // template<typename ...T, T ...V> void g(const T (&...p)[V]);
923  // g({1, 2, 3}, {{}, {}});
924  // ... should deduce T = {int, size_t (from array bound)}.
925  Pack.New[0].wasDeducedFromArrayBound());
926  }
927 
928  // Pick where we're going to put the merged pack.
930  if (Pack.Outer) {
931  if (Pack.Outer->DeferredDeduction.isNull()) {
932  // Defer checking this pack until we have a complete pack to compare
933  // it against.
934  Pack.Outer->DeferredDeduction = NewPack;
935  continue;
936  }
937  Loc = &Pack.Outer->DeferredDeduction;
938  } else {
939  Loc = &Deduced[Pack.Index];
940  }
941 
942  // Check the new pack matches any previous value.
943  DeducedTemplateArgument OldPack = *Loc;
944  DeducedTemplateArgument Result =
945  checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
946 
947  // If we deferred a deduction of this pack, check that one now too.
948  if (!Result.isNull() && !Pack.DeferredDeduction.isNull()) {
949  OldPack = Result;
950  NewPack = Pack.DeferredDeduction;
951  Result = checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
952  }
953 
954  NamedDecl *Param = TemplateParams->getParam(Pack.Index);
955  if (Result.isNull()) {
956  Info.Param = makeTemplateParameter(Param);
957  Info.FirstArg = OldPack;
958  Info.SecondArg = NewPack;
959  return Sema::TDK_Inconsistent;
960  }
961 
962  // If we have a pre-expanded pack and we didn't deduce enough elements
963  // for it, fail deduction.
964  if (Optional<unsigned> Expansions = getExpandedPackSize(Param)) {
965  if (*Expansions != PackElements) {
966  Info.Param = makeTemplateParameter(Param);
967  Info.FirstArg = Result;
969  }
970  }
971 
972  *Loc = Result;
973  }
974 
975  return Sema::TDK_Success;
976  }
977 
978 private:
979  Sema &S;
980  TemplateParameterList *TemplateParams;
981  SmallVectorImpl<DeducedTemplateArgument> &Deduced;
982  TemplateDeductionInfo &Info;
983  unsigned PackElements = 0;
984  bool IsPartiallyExpanded = false;
985  /// The number of expansions, if we have a fully-expanded pack in this scope.
986  Optional<unsigned> FixedNumExpansions;
987 
989 };
990 
991 } // namespace
992 
993 /// Deduce the template arguments by comparing the list of parameter
994 /// types to the list of argument types, as in the parameter-type-lists of
995 /// function types (C++ [temp.deduct.type]p10).
996 ///
997 /// \param S The semantic analysis object within which we are deducing
998 ///
999 /// \param TemplateParams The template parameters that we are deducing
1000 ///
1001 /// \param Params The list of parameter types
1002 ///
1003 /// \param NumParams The number of types in \c Params
1004 ///
1005 /// \param Args The list of argument types
1006 ///
1007 /// \param NumArgs The number of types in \c Args
1008 ///
1009 /// \param Info information about the template argument deduction itself
1010 ///
1011 /// \param Deduced the deduced template arguments
1012 ///
1013 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
1014 /// how template argument deduction is performed.
1015 ///
1016 /// \param PartialOrdering If true, we are performing template argument
1017 /// deduction for during partial ordering for a call
1018 /// (C++0x [temp.deduct.partial]).
1019 ///
1020 /// \returns the result of template argument deduction so far. Note that a
1021 /// "success" result means that template argument deduction has not yet failed,
1022 /// but it may still fail, later, for other reasons.
1025  TemplateParameterList *TemplateParams,
1026  const QualType *Params, unsigned NumParams,
1027  const QualType *Args, unsigned NumArgs,
1028  TemplateDeductionInfo &Info,
1029  SmallVectorImpl<DeducedTemplateArgument> &Deduced,
1030  unsigned TDF,
1031  bool PartialOrdering = false) {
1032  // C++0x [temp.deduct.type]p10:
1033  // Similarly, if P has a form that contains (T), then each parameter type
1034  // Pi of the respective parameter-type- list of P is compared with the
1035  // corresponding parameter type Ai of the corresponding parameter-type-list
1036  // of A. [...]
1037  unsigned ArgIdx = 0, ParamIdx = 0;
1038  for (; ParamIdx != NumParams; ++ParamIdx) {
1039  // Check argument types.
1040  const PackExpansionType *Expansion
1041  = dyn_cast<PackExpansionType>(Params[ParamIdx]);
1042  if (!Expansion) {
1043  // Simple case: compare the parameter and argument types at this point.
1044 
1045  // Make sure we have an argument.
1046  if (ArgIdx >= NumArgs)
1048 
1049  if (isa<PackExpansionType>(Args[ArgIdx])) {
1050  // C++0x [temp.deduct.type]p22:
1051  // If the original function parameter associated with A is a function
1052  // parameter pack and the function parameter associated with P is not
1053  // a function parameter pack, then template argument deduction fails.
1055  }
1056 
1057  if (Sema::TemplateDeductionResult Result =
1059  S, TemplateParams, Params[ParamIdx].getUnqualifiedType(),
1060  Args[ArgIdx].getUnqualifiedType(), Info, Deduced, TDF,
1062  /*DeducedFromArrayBound=*/false))
1063  return Result;
1064 
1065  ++ArgIdx;
1066  continue;
1067  }
1068 
1069  // C++0x [temp.deduct.type]p10:
1070  // If the parameter-declaration corresponding to Pi is a function
1071  // parameter pack, then the type of its declarator- id is compared with
1072  // each remaining parameter type in the parameter-type-list of A. Each
1073  // comparison deduces template arguments for subsequent positions in the
1074  // template parameter packs expanded by the function parameter pack.
1075 
1076  QualType Pattern = Expansion->getPattern();
1077  PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
1078 
1079  // A pack scope with fixed arity is not really a pack any more, so is not
1080  // a non-deduced context.
1081  if (ParamIdx + 1 == NumParams || PackScope.hasFixedArity()) {
1082  for (; ArgIdx < NumArgs && PackScope.hasNextElement(); ++ArgIdx) {
1083  // Deduce template arguments from the pattern.
1084  if (Sema::TemplateDeductionResult Result =
1086  S, TemplateParams, Pattern.getUnqualifiedType(),
1087  Args[ArgIdx].getUnqualifiedType(), Info, Deduced, TDF,
1088  PartialOrdering, /*DeducedFromArrayBound=*/false))
1089  return Result;
1090 
1091  PackScope.nextPackElement();
1092  }
1093  } else {
1094  // C++0x [temp.deduct.type]p5:
1095  // The non-deduced contexts are:
1096  // - A function parameter pack that does not occur at the end of the
1097  // parameter-declaration-clause.
1098  //
1099  // FIXME: There is no wording to say what we should do in this case. We
1100  // choose to resolve this by applying the same rule that is applied for a
1101  // function call: that is, deduce all contained packs to their
1102  // explicitly-specified values (or to <> if there is no such value).
1103  //
1104  // This is seemingly-arbitrarily different from the case of a template-id
1105  // with a non-trailing pack-expansion in its arguments, which renders the
1106  // entire template-argument-list a non-deduced context.
1107 
1108  // If the parameter type contains an explicitly-specified pack that we
1109  // could not expand, skip the number of parameters notionally created
1110  // by the expansion.
1111  Optional<unsigned> NumExpansions = Expansion->getNumExpansions();
1112  if (NumExpansions && !PackScope.isPartiallyExpanded()) {
1113  for (unsigned I = 0; I != *NumExpansions && ArgIdx < NumArgs;
1114  ++I, ++ArgIdx)
1115  PackScope.nextPackElement();
1116  }
1117  }
1118 
1119  // Build argument packs for each of the parameter packs expanded by this
1120  // pack expansion.
1121  if (auto Result = PackScope.finish())
1122  return Result;
1123  }
1124 
1125  // DR692, DR1395
1126  // C++0x [temp.deduct.type]p10:
1127  // If the parameter-declaration corresponding to P_i ...
1128  // During partial ordering, if Ai was originally a function parameter pack:
1129  // - if P does not contain a function parameter type corresponding to Ai then
1130  // Ai is ignored;
1131  if (PartialOrdering && ArgIdx + 1 == NumArgs &&
1132  isa<PackExpansionType>(Args[ArgIdx]))
1133  return Sema::TDK_Success;
1134 
1135  // Make sure we don't have any extra arguments.
1136  if (ArgIdx < NumArgs)
1138 
1139  return Sema::TDK_Success;
1140 }
1141 
1142 /// Determine whether the parameter has qualifiers that the argument
1143 /// lacks. Put another way, determine whether there is no way to add
1144 /// a deduced set of qualifiers to the ParamType that would result in
1145 /// its qualifiers matching those of the ArgType.
1147  QualType ArgType) {
1148  Qualifiers ParamQs = ParamType.getQualifiers();
1149  Qualifiers ArgQs = ArgType.getQualifiers();
1150 
1151  if (ParamQs == ArgQs)
1152  return false;
1153 
1154  // Mismatched (but not missing) Objective-C GC attributes.
1155  if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() &&
1156  ParamQs.hasObjCGCAttr())
1157  return true;
1158 
1159  // Mismatched (but not missing) address spaces.
1160  if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() &&
1161  ParamQs.hasAddressSpace())
1162  return true;
1163 
1164  // Mismatched (but not missing) Objective-C lifetime qualifiers.
1165  if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() &&
1166  ParamQs.hasObjCLifetime())
1167  return true;
1168 
1169  // CVR qualifiers inconsistent or a superset.
1170  return (ParamQs.getCVRQualifiers() & ~ArgQs.getCVRQualifiers()) != 0;
1171 }
1172 
1173 /// Compare types for equality with respect to possibly compatible
1174 /// function types (noreturn adjustment, implicit calling conventions). If any
1175 /// of parameter and argument is not a function, just perform type comparison.
1176 ///
1177 /// \param P the template parameter type.
1178 ///
1179 /// \param A the argument type.
1181  const FunctionType *PF = P->getAs<FunctionType>(),
1182  *AF = A->getAs<FunctionType>();
1183 
1184  // Just compare if not functions.
1185  if (!PF || !AF)
1186  return Context.hasSameType(P, A);
1187 
1188  // Noreturn and noexcept adjustment.
1189  QualType AdjustedParam;
1190  if (IsFunctionConversion(P, A, AdjustedParam))
1191  return Context.hasSameType(AdjustedParam, A);
1192 
1193  // FIXME: Compatible calling conventions.
1194 
1195  return Context.hasSameType(P, A);
1196 }
1197 
1198 /// Get the index of the first template parameter that was originally from the
1199 /// innermost template-parameter-list. This is 0 except when we concatenate
1200 /// the template parameter lists of a class template and a constructor template
1201 /// when forming an implicit deduction guide.
1203  auto *Guide = dyn_cast<CXXDeductionGuideDecl>(FTD->getTemplatedDecl());
1204  if (!Guide || !Guide->isImplicit())
1205  return 0;
1206  return Guide->getDeducedTemplate()->getTemplateParameters()->size();
1207 }
1208 
1209 /// Determine whether a type denotes a forwarding reference.
1210 static bool isForwardingReference(QualType Param, unsigned FirstInnerIndex) {
1211  // C++1z [temp.deduct.call]p3:
1212  // A forwarding reference is an rvalue reference to a cv-unqualified
1213  // template parameter that does not represent a template parameter of a
1214  // class template.
1215  if (auto *ParamRef = Param->getAs<RValueReferenceType>()) {
1216  if (ParamRef->getPointeeType().getQualifiers())
1217  return false;
1218  auto *TypeParm = ParamRef->getPointeeType()->getAs<TemplateTypeParmType>();
1219  return TypeParm && TypeParm->getIndex() >= FirstInnerIndex;
1220  }
1221  return false;
1222 }
1223 
1225  return cast<CXXRecordDecl>(
1227 }
1228 
1229 /// Attempt to deduce the template arguments by checking the base types
1230 /// according to (C++20 [temp.deduct.call] p4b3.
1231 ///
1232 /// \param S the semantic analysis object within which we are deducing.
1233 ///
1234 /// \param RD the top level record object we are deducing against.
1235 ///
1236 /// \param TemplateParams the template parameters that we are deducing.
1237 ///
1238 /// \param P the template specialization parameter type.
1239 ///
1240 /// \param Info information about the template argument deduction itself.
1241 ///
1242 /// \param Deduced the deduced template arguments.
1243 ///
1244 /// \returns the result of template argument deduction with the bases. "invalid"
1245 /// means no matches, "success" found a single item, and the
1246 /// "MiscellaneousDeductionFailure" result happens when the match is ambiguous.
1249  TemplateParameterList *TemplateParams, QualType P,
1250  TemplateDeductionInfo &Info,
1251  SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1252  // C++14 [temp.deduct.call] p4b3:
1253  // If P is a class and P has the form simple-template-id, then the
1254  // transformed A can be a derived class of the deduced A. Likewise if
1255  // P is a pointer to a class of the form simple-template-id, the
1256  // transformed A can be a pointer to a derived class pointed to by the
1257  // deduced A. However, if there is a class C that is a (direct or
1258  // indirect) base class of D and derived (directly or indirectly) from a
1259  // class B and that would be a valid deduced A, the deduced A cannot be
1260  // B or pointer to B, respectively.
1261  //
1262  // These alternatives are considered only if type deduction would
1263  // otherwise fail. If they yield more than one possible deduced A, the
1264  // type deduction fails.
1265 
1266  // Use a breadth-first search through the bases to collect the set of
1267  // successful matches. Visited contains the set of nodes we have already
1268  // visited, while ToVisit is our stack of records that we still need to
1269  // visit. Matches contains a list of matches that have yet to be
1270  // disqualified.
1272  SmallVector<QualType, 8> ToVisit;
1273  // We iterate over this later, so we have to use MapVector to ensure
1274  // determinism.
1275  llvm::MapVector<const CXXRecordDecl *,
1277  Matches;
1278 
1279  auto AddBases = [&Visited, &ToVisit](const CXXRecordDecl *RD) {
1280  for (const auto &Base : RD->bases()) {
1281  QualType T = Base.getType();
1282  assert(T->isRecordType() && "Base class that isn't a record?");
1283  if (Visited.insert(::getCanonicalRD(T)).second)
1284  ToVisit.push_back(T);
1285  }
1286  };
1287 
1288  // Set up the loop by adding all the bases.
1289  AddBases(RD);
1290 
1291  // Search each path of bases until we either run into a successful match
1292  // (where all bases of it are invalid), or we run out of bases.
1293  while (!ToVisit.empty()) {
1294  QualType NextT = ToVisit.pop_back_val();
1295 
1296  SmallVector<DeducedTemplateArgument, 8> DeducedCopy(Deduced.begin(),
1297  Deduced.end());
1300  S, TemplateParams, P, NextT, BaseInfo, DeducedCopy);
1301 
1302  // If this was a successful deduction, add it to the list of matches,
1303  // otherwise we need to continue searching its bases.
1304  const CXXRecordDecl *RD = ::getCanonicalRD(NextT);
1306  Matches.insert({RD, DeducedCopy});
1307  else
1308  AddBases(RD);
1309  }
1310 
1311  // At this point, 'Matches' contains a list of seemingly valid bases, however
1312  // in the event that we have more than 1 match, it is possible that the base
1313  // of one of the matches might be disqualified for being a base of another
1314  // valid match. We can count on cyclical instantiations being invalid to
1315  // simplify the disqualifications. That is, if A & B are both matches, and B
1316  // inherits from A (disqualifying A), we know that A cannot inherit from B.
1317  if (Matches.size() > 1) {
1318  Visited.clear();
1319  for (const auto &Match : Matches)
1320  AddBases(Match.first);
1321 
1322  // We can give up once we have a single item (or have run out of things to
1323  // search) since cyclical inheritance isn't valid.
1324  while (Matches.size() > 1 && !ToVisit.empty()) {
1325  const CXXRecordDecl *RD = ::getCanonicalRD(ToVisit.pop_back_val());
1326  Matches.erase(RD);
1327 
1328  // Always add all bases, since the inheritance tree can contain
1329  // disqualifications for multiple matches.
1330  AddBases(RD);
1331  }
1332  }
1333 
1334  if (Matches.empty())
1335  return Sema::TDK_Invalid;
1336  if (Matches.size() > 1)
1338 
1339  std::swap(Matches.front().second, Deduced);
1340  return Sema::TDK_Success;
1341 }
1342 
1343 /// Deduce the template arguments by comparing the parameter type and
1344 /// the argument type (C++ [temp.deduct.type]).
1345 ///
1346 /// \param S the semantic analysis object within which we are deducing
1347 ///
1348 /// \param TemplateParams the template parameters that we are deducing
1349 ///
1350 /// \param P the parameter type
1351 ///
1352 /// \param A the argument type
1353 ///
1354 /// \param Info information about the template argument deduction itself
1355 ///
1356 /// \param Deduced the deduced template arguments
1357 ///
1358 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
1359 /// how template argument deduction is performed.
1360 ///
1361 /// \param PartialOrdering Whether we're performing template argument deduction
1362 /// in the context of partial ordering (C++0x [temp.deduct.partial]).
1363 ///
1364 /// \returns the result of template argument deduction so far. Note that a
1365 /// "success" result means that template argument deduction has not yet failed,
1366 /// but it may still fail, later, for other reasons.
1368  Sema &S, TemplateParameterList *TemplateParams, QualType P, QualType A,
1369  TemplateDeductionInfo &Info,
1370  SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF,
1371  bool PartialOrdering, bool DeducedFromArrayBound) {
1372 
1373  // If the argument type is a pack expansion, look at its pattern.
1374  // This isn't explicitly called out
1375  if (const auto *AExp = dyn_cast<PackExpansionType>(A))
1376  A = AExp->getPattern();
1377  assert(!isa<PackExpansionType>(A.getCanonicalType()));
1378 
1379  if (PartialOrdering) {
1380  // C++11 [temp.deduct.partial]p5:
1381  // Before the partial ordering is done, certain transformations are
1382  // performed on the types used for partial ordering:
1383  // - If P is a reference type, P is replaced by the type referred to.
1384  const ReferenceType *PRef = P->getAs<ReferenceType>();
1385  if (PRef)
1386  P = PRef->getPointeeType();
1387 
1388  // - If A is a reference type, A is replaced by the type referred to.
1389  const ReferenceType *ARef = A->getAs<ReferenceType>();
1390  if (ARef)
1391  A = A->getPointeeType();
1392 
1393  if (PRef && ARef && S.Context.hasSameUnqualifiedType(P, A)) {
1394  // C++11 [temp.deduct.partial]p9:
1395  // If, for a given type, deduction succeeds in both directions (i.e.,
1396  // the types are identical after the transformations above) and both
1397  // P and A were reference types [...]:
1398  // - if [one type] was an lvalue reference and [the other type] was
1399  // not, [the other type] is not considered to be at least as
1400  // specialized as [the first type]
1401  // - if [one type] is more cv-qualified than [the other type],
1402  // [the other type] is not considered to be at least as specialized
1403  // as [the first type]
1404  // Objective-C ARC adds:
1405  // - [one type] has non-trivial lifetime, [the other type] has
1406  // __unsafe_unretained lifetime, and the types are otherwise
1407  // identical
1408  //
1409  // A is "considered to be at least as specialized" as P iff deduction
1410  // succeeds, so we model this as a deduction failure. Note that
1411  // [the first type] is P and [the other type] is A here; the standard
1412  // gets this backwards.
1413  Qualifiers PQuals = P.getQualifiers(), AQuals = A.getQualifiers();
1414  if ((PRef->isLValueReferenceType() && !ARef->isLValueReferenceType()) ||
1415  PQuals.isStrictSupersetOf(AQuals) ||
1416  (PQuals.hasNonTrivialObjCLifetime() &&
1417  AQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone &&
1418  PQuals.withoutObjCLifetime() == AQuals.withoutObjCLifetime())) {
1419  Info.FirstArg = TemplateArgument(P);
1420  Info.SecondArg = TemplateArgument(A);
1422  }
1423  }
1424  Qualifiers DiscardedQuals;
1425  // C++11 [temp.deduct.partial]p7:
1426  // Remove any top-level cv-qualifiers:
1427  // - If P is a cv-qualified type, P is replaced by the cv-unqualified
1428  // version of P.
1429  P = S.Context.getUnqualifiedArrayType(P, DiscardedQuals);
1430  // - If A is a cv-qualified type, A is replaced by the cv-unqualified
1431  // version of A.
1432  A = S.Context.getUnqualifiedArrayType(A, DiscardedQuals);
1433  } else {
1434  // C++0x [temp.deduct.call]p4 bullet 1:
1435  // - If the original P is a reference type, the deduced A (i.e., the type
1436  // referred to by the reference) can be more cv-qualified than the
1437  // transformed A.
1438  if (TDF & TDF_ParamWithReferenceType) {
1439  Qualifiers Quals;
1440  QualType UnqualP = S.Context.getUnqualifiedArrayType(P, Quals);
1441  Quals.setCVRQualifiers(Quals.getCVRQualifiers() & A.getCVRQualifiers());
1442  P = S.Context.getQualifiedType(UnqualP, Quals);
1443  }
1444 
1445  if ((TDF & TDF_TopLevelParameterTypeList) && !P->isFunctionType()) {
1446  // C++0x [temp.deduct.type]p10:
1447  // If P and A are function types that originated from deduction when
1448  // taking the address of a function template (14.8.2.2) or when deducing
1449  // template arguments from a function declaration (14.8.2.6) and Pi and
1450  // Ai are parameters of the top-level parameter-type-list of P and A,
1451  // respectively, Pi is adjusted if it is a forwarding reference and Ai
1452  // is an lvalue reference, in
1453  // which case the type of Pi is changed to be the template parameter
1454  // type (i.e., T&& is changed to simply T). [ Note: As a result, when
1455  // Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
1456  // deduced as X&. - end note ]
1458  if (isForwardingReference(P, /*FirstInnerIndex=*/0) &&
1459  A->isLValueReferenceType())
1460  P = P->getPointeeType();
1461  }
1462  }
1463 
1464  // C++ [temp.deduct.type]p9:
1465  // A template type argument T, a template template argument TT or a
1466  // template non-type argument i can be deduced if P and A have one of
1467  // the following forms:
1468  //
1469  // T
1470  // cv-list T
1471  if (const auto *TTP = P->getAs<TemplateTypeParmType>()) {
1472  // Just skip any attempts to deduce from a placeholder type or a parameter
1473  // at a different depth.
1474  if (A->isPlaceholderType() || Info.getDeducedDepth() != TTP->getDepth())
1475  return Sema::TDK_Success;
1476 
1477  unsigned Index = TTP->getIndex();
1478 
1479  // If the argument type is an array type, move the qualifiers up to the
1480  // top level, so they can be matched with the qualifiers on the parameter.
1481  if (A->isArrayType()) {
1482  Qualifiers Quals;
1483  A = S.Context.getUnqualifiedArrayType(A, Quals);
1484  if (Quals)
1485  A = S.Context.getQualifiedType(A, Quals);
1486  }
1487 
1488  // The argument type can not be less qualified than the parameter
1489  // type.
1490  if (!(TDF & TDF_IgnoreQualifiers) &&
1492  Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1493  Info.FirstArg = TemplateArgument(P);
1494  Info.SecondArg = TemplateArgument(A);
1495  return Sema::TDK_Underqualified;
1496  }
1497 
1498  // Do not match a function type with a cv-qualified type.
1499  // http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1584
1500  if (A->isFunctionType() && P.hasQualifiers())
1502 
1503  assert(TTP->getDepth() == Info.getDeducedDepth() &&
1504  "saw template type parameter with wrong depth");
1505  assert(A->getCanonicalTypeInternal() != S.Context.OverloadTy &&
1506  "Unresolved overloaded function");
1507  QualType DeducedType = A;
1508 
1509  // Remove any qualifiers on the parameter from the deduced type.
1510  // We checked the qualifiers for consistency above.
1511  Qualifiers DeducedQs = DeducedType.getQualifiers();
1512  Qualifiers ParamQs = P.getQualifiers();
1513  DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers());
1514  if (ParamQs.hasObjCGCAttr())
1515  DeducedQs.removeObjCGCAttr();
1516  if (ParamQs.hasAddressSpace())
1517  DeducedQs.removeAddressSpace();
1518  if (ParamQs.hasObjCLifetime())
1519  DeducedQs.removeObjCLifetime();
1520 
1521  // Objective-C ARC:
1522  // If template deduction would produce a lifetime qualifier on a type
1523  // that is not a lifetime type, template argument deduction fails.
1524  if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() &&
1526  Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1527  Info.FirstArg = TemplateArgument(P);
1528  Info.SecondArg = TemplateArgument(A);
1529  return Sema::TDK_Underqualified;
1530  }
1531 
1532  // Objective-C ARC:
1533  // If template deduction would produce an argument type with lifetime type
1534  // but no lifetime qualifier, the __strong lifetime qualifier is inferred.
1535  if (S.getLangOpts().ObjCAutoRefCount && DeducedType->isObjCLifetimeType() &&
1536  !DeducedQs.hasObjCLifetime())
1538 
1539  DeducedType =
1540  S.Context.getQualifiedType(DeducedType.getUnqualifiedType(), DeducedQs);
1541 
1542  DeducedTemplateArgument NewDeduced(DeducedType, DeducedFromArrayBound);
1543  DeducedTemplateArgument Result =
1544  checkDeducedTemplateArguments(S.Context, Deduced[Index], NewDeduced);
1545  if (Result.isNull()) {
1546  Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1547  Info.FirstArg = Deduced[Index];
1548  Info.SecondArg = NewDeduced;
1549  return Sema::TDK_Inconsistent;
1550  }
1551 
1552  Deduced[Index] = Result;
1553  return Sema::TDK_Success;
1554  }
1555 
1556  // Set up the template argument deduction information for a failure.
1557  Info.FirstArg = TemplateArgument(P);
1558  Info.SecondArg = TemplateArgument(A);
1559 
1560  // If the parameter is an already-substituted template parameter
1561  // pack, do nothing: we don't know which of its arguments to look
1562  // at, so we have to wait until all of the parameter packs in this
1563  // expansion have arguments.
1564  if (P->getAs<SubstTemplateTypeParmPackType>())
1565  return Sema::TDK_Success;
1566 
1567  // Check the cv-qualifiers on the parameter and argument types.
1568  if (!(TDF & TDF_IgnoreQualifiers)) {
1569  if (TDF & TDF_ParamWithReferenceType) {
1572  } else if (TDF & TDF_ArgWithReferenceType) {
1573  // C++ [temp.deduct.conv]p4:
1574  // If the original A is a reference type, A can be more cv-qualified
1575  // than the deduced A
1576  if (!A.getQualifiers().compatiblyIncludes(P.getQualifiers()))
1578 
1579  // Strip out all extra qualifiers from the argument to figure out the
1580  // type we're converting to, prior to the qualification conversion.
1581  Qualifiers Quals;
1582  A = S.Context.getUnqualifiedArrayType(A, Quals);
1583  A = S.Context.getQualifiedType(A, P.getQualifiers());
1584  } else if (!IsPossiblyOpaquelyQualifiedType(P)) {
1585  if (P.getCVRQualifiers() != A.getCVRQualifiers())
1587  }
1588  }
1589 
1590  // If the parameter type is not dependent, there is nothing to deduce.
1591  if (!P->isDependentType()) {
1592  if (TDF & TDF_SkipNonDependent)
1593  return Sema::TDK_Success;
1595  : S.Context.hasSameType(P, A))
1596  return Sema::TDK_Success;
1597  if (TDF & TDF_AllowCompatibleFunctionType &&
1599  return Sema::TDK_Success;
1600  if (!(TDF & TDF_IgnoreQualifiers))
1602  // Otherwise, when ignoring qualifiers, the types not having the same
1603  // unqualified type does not mean they do not match, so in this case we
1604  // must keep going and analyze with a non-dependent parameter type.
1605  }
1606 
1607  switch (P.getCanonicalType()->getTypeClass()) {
1608  // Non-canonical types cannot appear here.
1609 #define NON_CANONICAL_TYPE(Class, Base) \
1610  case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class);
1611 #define TYPE(Class, Base)
1612 #include "clang/AST/TypeNodes.inc"
1613 
1614  case Type::TemplateTypeParm:
1615  case Type::SubstTemplateTypeParmPack:
1616  llvm_unreachable("Type nodes handled above");
1617 
1618  case Type::Auto:
1619  // FIXME: Implement deduction in dependent case.
1620  if (P->isDependentType())
1621  return Sema::TDK_Success;
1622  [[fallthrough]];
1623  case Type::Builtin:
1624  case Type::VariableArray:
1625  case Type::Vector:
1626  case Type::FunctionNoProto:
1627  case Type::Record:
1628  case Type::Enum:
1629  case Type::ObjCObject:
1630  case Type::ObjCInterface:
1631  case Type::ObjCObjectPointer:
1632  case Type::BitInt:
1633  return (TDF & TDF_SkipNonDependent) ||
1634  ((TDF & TDF_IgnoreQualifiers)
1636  : S.Context.hasSameType(P, A))
1639 
1640  // _Complex T [placeholder extension]
1641  case Type::Complex: {
1642  const auto *CP = P->castAs<ComplexType>(), *CA = A->getAs<ComplexType>();
1643  if (!CA)
1646  S, TemplateParams, CP->getElementType(), CA->getElementType(), Info,
1647  Deduced, TDF);
1648  }
1649 
1650  // _Atomic T [extension]
1651  case Type::Atomic: {
1652  const auto *PA = P->castAs<AtomicType>(), *AA = A->getAs<AtomicType>();
1653  if (!AA)
1656  S, TemplateParams, PA->getValueType(), AA->getValueType(), Info,
1657  Deduced, TDF);
1658  }
1659 
1660  // T *
1661  case Type::Pointer: {
1662  QualType PointeeType;
1663  if (const auto *PA = A->getAs<PointerType>()) {
1664  PointeeType = PA->getPointeeType();
1665  } else if (const auto *PA = A->getAs<ObjCObjectPointerType>()) {
1666  PointeeType = PA->getPointeeType();
1667  } else {
1669  }
1671  S, TemplateParams, P->castAs<PointerType>()->getPointeeType(),
1672  PointeeType, Info, Deduced,
1674  }
1675 
1676  // T &
1677  case Type::LValueReference: {
1678  const auto *RP = P->castAs<LValueReferenceType>(),
1679  *RA = A->getAs<LValueReferenceType>();
1680  if (!RA)
1682 
1684  S, TemplateParams, RP->getPointeeType(), RA->getPointeeType(), Info,
1685  Deduced, 0);
1686  }
1687 
1688  // T && [C++0x]
1689  case Type::RValueReference: {
1690  const auto *RP = P->castAs<RValueReferenceType>(),
1691  *RA = A->getAs<RValueReferenceType>();
1692  if (!RA)
1694 
1696  S, TemplateParams, RP->getPointeeType(), RA->getPointeeType(), Info,
1697  Deduced, 0);
1698  }
1699 
1700  // T [] (implied, but not stated explicitly)
1701  case Type::IncompleteArray: {
1702  const auto *IAA = S.Context.getAsIncompleteArrayType(A);
1703  if (!IAA)
1705 
1707  S, TemplateParams,
1709  IAA->getElementType(), Info, Deduced, TDF & TDF_IgnoreQualifiers);
1710  }
1711 
1712  // T [integer-constant]
1713  case Type::ConstantArray: {
1714  const auto *CAA = S.Context.getAsConstantArrayType(A),
1715  *CAP = S.Context.getAsConstantArrayType(P);
1716  assert(CAP);
1717  if (!CAA || CAA->getSize() != CAP->getSize())
1719 
1721  S, TemplateParams, CAP->getElementType(), CAA->getElementType(), Info,
1722  Deduced, TDF & TDF_IgnoreQualifiers);
1723  }
1724 
1725  // type [i]
1726  case Type::DependentSizedArray: {
1727  const auto *AA = S.Context.getAsArrayType(A);
1728  if (!AA)
1730 
1731  // Check the element type of the arrays
1732  const auto *DAP = S.Context.getAsDependentSizedArrayType(P);
1733  assert(DAP);
1734  if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1735  S, TemplateParams, DAP->getElementType(), AA->getElementType(),
1736  Info, Deduced, TDF & TDF_IgnoreQualifiers))
1737  return Result;
1738 
1739  // Determine the array bound is something we can deduce.
1740  const NonTypeTemplateParmDecl *NTTP =
1741  getDeducedParameterFromExpr(Info, DAP->getSizeExpr());
1742  if (!NTTP)
1743  return Sema::TDK_Success;
1744 
1745  // We can perform template argument deduction for the given non-type
1746  // template parameter.
1747  assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1748  "saw non-type template parameter with wrong depth");
1749  if (const auto *CAA = dyn_cast<ConstantArrayType>(AA)) {
1750  llvm::APSInt Size(CAA->getSize());
1752  S, TemplateParams, NTTP, Size, S.Context.getSizeType(),
1753  /*ArrayBound=*/true, Info, Deduced);
1754  }
1755  if (const auto *DAA = dyn_cast<DependentSizedArrayType>(AA))
1756  if (DAA->getSizeExpr())
1758  S, TemplateParams, NTTP, DAA->getSizeExpr(), Info, Deduced);
1759 
1760  // Incomplete type does not match a dependently-sized array type
1762  }
1763 
1764  // type(*)(T)
1765  // T(*)()
1766  // T(*)(T)
1767  case Type::FunctionProto: {
1768  const auto *FPP = P->castAs<FunctionProtoType>(),
1769  *FPA = A->getAs<FunctionProtoType>();
1770  if (!FPA)
1772 
1773  if (FPP->getMethodQuals() != FPA->getMethodQuals() ||
1774  FPP->getRefQualifier() != FPA->getRefQualifier() ||
1775  FPP->isVariadic() != FPA->isVariadic())
1777 
1778  // Check return types.
1779  if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1780  S, TemplateParams, FPP->getReturnType(), FPA->getReturnType(),
1781  Info, Deduced, 0,
1782  /*PartialOrdering=*/false,
1783  /*DeducedFromArrayBound=*/false))
1784  return Result;
1785 
1786  // Check parameter types.
1787  if (auto Result = DeduceTemplateArguments(
1788  S, TemplateParams, FPP->param_type_begin(), FPP->getNumParams(),
1789  FPA->param_type_begin(), FPA->getNumParams(), Info, Deduced,
1791  return Result;
1792 
1794  return Sema::TDK_Success;
1795 
1796  // FIXME: Per core-2016/10/1019 (no corresponding core issue yet), permit
1797  // deducing through the noexcept-specifier if it's part of the canonical
1798  // type. libstdc++ relies on this.
1799  Expr *NoexceptExpr = FPP->getNoexceptExpr();
1800  if (const NonTypeTemplateParmDecl *NTTP =
1801  NoexceptExpr ? getDeducedParameterFromExpr(Info, NoexceptExpr)
1802  : nullptr) {
1803  assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1804  "saw non-type template parameter with wrong depth");
1805 
1806  llvm::APSInt Noexcept(1);
1807  switch (FPA->canThrow()) {
1808  case CT_Cannot:
1809  Noexcept = 1;
1810  [[fallthrough]];
1811 
1812  case CT_Can:
1813  // We give E in noexcept(E) the "deduced from array bound" treatment.
1814  // FIXME: Should we?
1816  S, TemplateParams, NTTP, Noexcept, S.Context.BoolTy,
1817  /*DeducedFromArrayBound=*/true, Info, Deduced);
1818 
1819  case CT_Dependent:
1820  if (Expr *ArgNoexceptExpr = FPA->getNoexceptExpr())
1822  S, TemplateParams, NTTP, ArgNoexceptExpr, Info, Deduced);
1823  // Can't deduce anything from throw(T...).
1824  break;
1825  }
1826  }
1827  // FIXME: Detect non-deduced exception specification mismatches?
1828  //
1829  // Careful about [temp.deduct.call] and [temp.deduct.conv], which allow
1830  // top-level differences in noexcept-specifications.
1831 
1832  return Sema::TDK_Success;
1833  }
1834 
1835  case Type::InjectedClassName:
1836  // Treat a template's injected-class-name as if the template
1837  // specialization type had been used.
1838 
1839  // template-name<T> (where template-name refers to a class template)
1840  // template-name<i>
1841  // TT<T>
1842  // TT<i>
1843  // TT<>
1844  case Type::TemplateSpecialization: {
1845  // When Arg cannot be a derived class, we can just try to deduce template
1846  // arguments from the template-id.
1847  if (!(TDF & TDF_DerivedClass) || !A->isRecordType())
1848  return DeduceTemplateSpecArguments(S, TemplateParams, P, A, Info,
1849  Deduced);
1850 
1851  SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(),
1852  Deduced.end());
1853 
1854  auto Result =
1855  DeduceTemplateSpecArguments(S, TemplateParams, P, A, Info, Deduced);
1856  if (Result == Sema::TDK_Success)
1857  return Result;
1858 
1859  // We cannot inspect base classes as part of deduction when the type
1860  // is incomplete, so either instantiate any templates necessary to
1861  // complete the type, or skip over it if it cannot be completed.
1862  if (!S.isCompleteType(Info.getLocation(), A))
1863  return Result;
1864 
1865  // Reset the incorrectly deduced argument from above.
1866  Deduced = DeducedOrig;
1867 
1868  // Check bases according to C++14 [temp.deduct.call] p4b3:
1870  TemplateParams, P, Info, Deduced);
1871  return BaseResult != Sema::TDK_Invalid ? BaseResult : Result;
1872  }
1873 
1874  // T type::*
1875  // T T::*
1876  // T (type::*)()
1877  // type (T::*)()
1878  // type (type::*)(T)
1879  // type (T::*)(T)
1880  // T (type::*)(T)
1881  // T (T::*)()
1882  // T (T::*)(T)
1883  case Type::MemberPointer: {
1884  const auto *MPP = P->castAs<MemberPointerType>(),
1885  *MPA = A->getAs<MemberPointerType>();
1886  if (!MPA)
1888 
1889  QualType PPT = MPP->getPointeeType();
1890  if (PPT->isFunctionType())
1891  S.adjustMemberFunctionCC(PPT, /*IsStatic=*/true,
1892  /*IsCtorOrDtor=*/false, Info.getLocation());
1893  QualType APT = MPA->getPointeeType();
1894  if (APT->isFunctionType())
1895  S.adjustMemberFunctionCC(APT, /*IsStatic=*/true,
1896  /*IsCtorOrDtor=*/false, Info.getLocation());
1897 
1898  unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1899  if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1900  S, TemplateParams, PPT, APT, Info, Deduced, SubTDF))
1901  return Result;
1903  S, TemplateParams, QualType(MPP->getClass(), 0),
1904  QualType(MPA->getClass(), 0), Info, Deduced, SubTDF);
1905  }
1906 
1907  // (clang extension)
1908  //
1909  // type(^)(T)
1910  // T(^)()
1911  // T(^)(T)
1912  case Type::BlockPointer: {
1913  const auto *BPP = P->castAs<BlockPointerType>(),
1914  *BPA = A->getAs<BlockPointerType>();
1915  if (!BPA)
1918  S, TemplateParams, BPP->getPointeeType(), BPA->getPointeeType(), Info,
1919  Deduced, 0);
1920  }
1921 
1922  // (clang extension)
1923  //
1924  // T __attribute__(((ext_vector_type(<integral constant>))))
1925  case Type::ExtVector: {
1926  const auto *VP = P->castAs<ExtVectorType>();
1927  QualType ElementType;
1928  if (const auto *VA = A->getAs<ExtVectorType>()) {
1929  // Make sure that the vectors have the same number of elements.
1930  if (VP->getNumElements() != VA->getNumElements())
1932  ElementType = VA->getElementType();
1933  } else if (const auto *VA = A->getAs<DependentSizedExtVectorType>()) {
1934  // We can't check the number of elements, since the argument has a
1935  // dependent number of elements. This can only occur during partial
1936  // ordering.
1937  ElementType = VA->getElementType();
1938  } else {
1940  }
1941  // Perform deduction on the element types.
1943  S, TemplateParams, VP->getElementType(), ElementType, Info, Deduced,
1944  TDF);
1945  }
1946 
1947  case Type::DependentVector: {
1948  const auto *VP = P->castAs<DependentVectorType>();
1949 
1950  if (const auto *VA = A->getAs<VectorType>()) {
1951  // Perform deduction on the element types.
1952  if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1953  S, TemplateParams, VP->getElementType(), VA->getElementType(),
1954  Info, Deduced, TDF))
1955  return Result;
1956 
1957  // Perform deduction on the vector size, if we can.
1958  const NonTypeTemplateParmDecl *NTTP =
1959  getDeducedParameterFromExpr(Info, VP->getSizeExpr());
1960  if (!NTTP)
1961  return Sema::TDK_Success;
1962 
1963  llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1964  ArgSize = VA->getNumElements();
1965  // Note that we use the "array bound" rules here; just like in that
1966  // case, we don't have any particular type for the vector size, but
1967  // we can provide one if necessary.
1968  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
1969  S.Context.UnsignedIntTy, true,
1970  Info, Deduced);
1971  }
1972 
1973  if (const auto *VA = A->getAs<DependentVectorType>()) {
1974  // Perform deduction on the element types.
1975  if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1976  S, TemplateParams, VP->getElementType(), VA->getElementType(),
1977  Info, Deduced, TDF))
1978  return Result;
1979 
1980  // Perform deduction on the vector size, if we can.
1981  const NonTypeTemplateParmDecl *NTTP =
1982  getDeducedParameterFromExpr(Info, VP->getSizeExpr());
1983  if (!NTTP)
1984  return Sema::TDK_Success;
1985 
1986  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
1987  VA->getSizeExpr(), Info, Deduced);
1988  }
1989 
1991  }
1992 
1993  // (clang extension)
1994  //
1995  // T __attribute__(((ext_vector_type(N))))
1996  case Type::DependentSizedExtVector: {
1997  const auto *VP = P->castAs<DependentSizedExtVectorType>();
1998 
1999  if (const auto *VA = A->getAs<ExtVectorType>()) {
2000  // Perform deduction on the element types.
2001  if (auto Result = DeduceTemplateArgumentsByTypeMatch(
2002  S, TemplateParams, VP->getElementType(), VA->getElementType(),
2003  Info, Deduced, TDF))
2004  return Result;
2005 
2006  // Perform deduction on the vector size, if we can.
2007  const NonTypeTemplateParmDecl *NTTP =
2008  getDeducedParameterFromExpr(Info, VP->getSizeExpr());
2009  if (!NTTP)
2010  return Sema::TDK_Success;
2011 
2012  llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
2013  ArgSize = VA->getNumElements();
2014  // Note that we use the "array bound" rules here; just like in that
2015  // case, we don't have any particular type for the vector size, but
2016  // we can provide one if necessary.
2017  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
2018  S.Context.IntTy, true, Info,
2019  Deduced);
2020  }
2021 
2022  if (const auto *VA = A->getAs<DependentSizedExtVectorType>()) {
2023  // Perform deduction on the element types.
2024  if (auto Result = DeduceTemplateArgumentsByTypeMatch(
2025  S, TemplateParams, VP->getElementType(), VA->getElementType(),
2026  Info, Deduced, TDF))
2027  return Result;
2028 
2029  // Perform deduction on the vector size, if we can.
2030  const NonTypeTemplateParmDecl *NTTP =
2031  getDeducedParameterFromExpr(Info, VP->getSizeExpr());
2032  if (!NTTP)
2033  return Sema::TDK_Success;
2034 
2035  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2036  VA->getSizeExpr(), Info, Deduced);
2037  }
2038 
2040  }
2041 
2042  // (clang extension)
2043  //
2044  // T __attribute__((matrix_type(<integral constant>,
2045  // <integral constant>)))
2046  case Type::ConstantMatrix: {
2047  const auto *MP = P->castAs<ConstantMatrixType>(),
2048  *MA = A->getAs<ConstantMatrixType>();
2049  if (!MA)
2051 
2052  // Check that the dimensions are the same
2053  if (MP->getNumRows() != MA->getNumRows() ||
2054  MP->getNumColumns() != MA->getNumColumns()) {
2056  }
2057  // Perform deduction on element types.
2059  S, TemplateParams, MP->getElementType(), MA->getElementType(), Info,
2060  Deduced, TDF);
2061  }
2062 
2063  case Type::DependentSizedMatrix: {
2064  const auto *MP = P->castAs<DependentSizedMatrixType>();
2065  const auto *MA = A->getAs<MatrixType>();
2066  if (!MA)
2068 
2069  // Check the element type of the matrixes.
2070  if (auto Result = DeduceTemplateArgumentsByTypeMatch(
2071  S, TemplateParams, MP->getElementType(), MA->getElementType(),
2072  Info, Deduced, TDF))
2073  return Result;
2074 
2075  // Try to deduce a matrix dimension.
2076  auto DeduceMatrixArg =
2077  [&S, &Info, &Deduced, &TemplateParams](
2078  Expr *ParamExpr, const MatrixType *A,
2079  unsigned (ConstantMatrixType::*GetArgDimension)() const,
2080  Expr *(DependentSizedMatrixType::*GetArgDimensionExpr)() const) {
2081  const auto *ACM = dyn_cast<ConstantMatrixType>(A);
2082  const auto *ADM = dyn_cast<DependentSizedMatrixType>(A);
2083  if (!ParamExpr->isValueDependent()) {
2084  Optional<llvm::APSInt> ParamConst =
2085  ParamExpr->getIntegerConstantExpr(S.Context);
2086  if (!ParamConst)
2088 
2089  if (ACM) {
2090  if ((ACM->*GetArgDimension)() == *ParamConst)
2091  return Sema::TDK_Success;
2093  }
2094 
2095  Expr *ArgExpr = (ADM->*GetArgDimensionExpr)();
2096  if (Optional<llvm::APSInt> ArgConst =
2097  ArgExpr->getIntegerConstantExpr(S.Context))
2098  if (*ArgConst == *ParamConst)
2099  return Sema::TDK_Success;
2101  }
2102 
2103  const NonTypeTemplateParmDecl *NTTP =
2104  getDeducedParameterFromExpr(Info, ParamExpr);
2105  if (!NTTP)
2106  return Sema::TDK_Success;
2107 
2108  if (ACM) {
2109  llvm::APSInt ArgConst(
2111  ArgConst = (ACM->*GetArgDimension)();
2113  S, TemplateParams, NTTP, ArgConst, S.Context.getSizeType(),
2114  /*ArrayBound=*/true, Info, Deduced);
2115  }
2116 
2117  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2118  (ADM->*GetArgDimensionExpr)(),
2119  Info, Deduced);
2120  };
2121 
2122  if (auto Result = DeduceMatrixArg(MP->getRowExpr(), MA,
2125  return Result;
2126 
2127  return DeduceMatrixArg(MP->getColumnExpr(), MA,
2130  }
2131 
2132  // (clang extension)
2133  //
2134  // T __attribute__(((address_space(N))))
2135  case Type::DependentAddressSpace: {
2136  const auto *ASP = P->castAs<DependentAddressSpaceType>();
2137 
2138  if (const auto *ASA = A->getAs<DependentAddressSpaceType>()) {
2139  // Perform deduction on the pointer type.
2140  if (auto Result = DeduceTemplateArgumentsByTypeMatch(
2141  S, TemplateParams, ASP->getPointeeType(), ASA->getPointeeType(),
2142  Info, Deduced, TDF))
2143  return Result;
2144 
2145  // Perform deduction on the address space, if we can.
2146  const NonTypeTemplateParmDecl *NTTP =
2147  getDeducedParameterFromExpr(Info, ASP->getAddrSpaceExpr());
2148  if (!NTTP)
2149  return Sema::TDK_Success;
2150 
2152  S, TemplateParams, NTTP, ASA->getAddrSpaceExpr(), Info, Deduced);
2153  }
2154 
2156  llvm::APSInt ArgAddressSpace(S.Context.getTypeSize(S.Context.IntTy),
2157  false);
2158  ArgAddressSpace = toTargetAddressSpace(A.getAddressSpace());
2159 
2160  // Perform deduction on the pointer types.
2161  if (auto Result = DeduceTemplateArgumentsByTypeMatch(
2162  S, TemplateParams, ASP->getPointeeType(),
2163  S.Context.removeAddrSpaceQualType(A), Info, Deduced, TDF))
2164  return Result;
2165 
2166  // Perform deduction on the address space, if we can.
2167  const NonTypeTemplateParmDecl *NTTP =
2168  getDeducedParameterFromExpr(Info, ASP->getAddrSpaceExpr());
2169  if (!NTTP)
2170  return Sema::TDK_Success;
2171 
2172  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2173  ArgAddressSpace, S.Context.IntTy,
2174  true, Info, Deduced);
2175  }
2176 
2178  }
2179  case Type::DependentBitInt: {
2180  const auto *IP = P->castAs<DependentBitIntType>();
2181 
2182  if (const auto *IA = A->getAs<BitIntType>()) {
2183  if (IP->isUnsigned() != IA->isUnsigned())
2185 
2186  const NonTypeTemplateParmDecl *NTTP =
2187  getDeducedParameterFromExpr(Info, IP->getNumBitsExpr());
2188  if (!NTTP)
2189  return Sema::TDK_Success;
2190 
2191  llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
2192  ArgSize = IA->getNumBits();
2193 
2194  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
2195  S.Context.IntTy, true, Info,
2196  Deduced);
2197  }
2198 
2199  if (const auto *IA = A->getAs<DependentBitIntType>()) {
2200  if (IP->isUnsigned() != IA->isUnsigned())
2202  return Sema::TDK_Success;
2203  }
2204 
2206  }
2207 
2208  case Type::TypeOfExpr:
2209  case Type::TypeOf:
2210  case Type::DependentName:
2211  case Type::UnresolvedUsing:
2212  case Type::Decltype:
2213  case Type::UnaryTransform:
2214  case Type::DeducedTemplateSpecialization:
2215  case Type::DependentTemplateSpecialization:
2216  case Type::PackExpansion:
2217  case Type::Pipe:
2218  // No template argument deduction for these types
2219  return Sema::TDK_Success;
2220  }
2221 
2222  llvm_unreachable("Invalid Type Class!");
2223 }
2224 
2228  TemplateDeductionInfo &Info,
2229  SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
2230  // If the template argument is a pack expansion, perform template argument
2231  // deduction against the pattern of that expansion. This only occurs during
2232  // partial ordering.
2233  if (A.isPackExpansion())
2234  A = A.getPackExpansionPattern();
2235 
2236  switch (P.getKind()) {
2238  llvm_unreachable("Null template argument in parameter list");
2239 
2241  if (A.getKind() == TemplateArgument::Type)
2243  S, TemplateParams, P.getAsType(), A.getAsType(), Info, Deduced, 0);
2244  Info.FirstArg = P;
2245  Info.SecondArg = A;
2247 
2250  return DeduceTemplateArguments(S, TemplateParams, P.getAsTemplate(),
2251  A.getAsTemplate(), Info, Deduced);
2252  Info.FirstArg = P;
2253  Info.SecondArg = A;
2255 
2257  llvm_unreachable("caller should handle pack expansions");
2258 
2261  isSameDeclaration(P.getAsDecl(), A.getAsDecl()))
2262  return Sema::TDK_Success;
2263 
2264  Info.FirstArg = P;
2265  Info.SecondArg = A;
2267 
2269  if (A.getKind() == TemplateArgument::NullPtr &&
2270  S.Context.hasSameType(P.getNullPtrType(), A.getNullPtrType()))
2271  return Sema::TDK_Success;
2272 
2273  Info.FirstArg = P;
2274  Info.SecondArg = A;
2276 
2278  if (A.getKind() == TemplateArgument::Integral) {
2279  if (hasSameExtendedValue(P.getAsIntegral(), A.getAsIntegral()))
2280  return Sema::TDK_Success;
2281  }
2282  Info.FirstArg = P;
2283  Info.SecondArg = A;
2285 
2287  if (const NonTypeTemplateParmDecl *NTTP =
2288  getDeducedParameterFromExpr(Info, P.getAsExpr())) {
2291  S, TemplateParams, NTTP, A.getAsIntegral(), A.getIntegralType(),
2292  /*ArrayBound=*/false, Info, Deduced);
2294  return DeduceNullPtrTemplateArgument(S, TemplateParams, NTTP,
2295  A.getNullPtrType(), Info, Deduced);
2297  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2298  A.getAsExpr(), Info, Deduced);
2301  S, TemplateParams, NTTP, A.getAsDecl(), A.getParamTypeForDecl(),
2302  Info, Deduced);
2303 
2304  Info.FirstArg = P;
2305  Info.SecondArg = A;
2307  }
2308 
2309  // Can't deduce anything, but that's okay.
2310  return Sema::TDK_Success;
2312  llvm_unreachable("Argument packs should be expanded by the caller!");
2313  }
2314 
2315  llvm_unreachable("Invalid TemplateArgument Kind!");
2316 }
2317 
2318 /// Determine whether there is a template argument to be used for
2319 /// deduction.
2320 ///
2321 /// This routine "expands" argument packs in-place, overriding its input
2322 /// parameters so that \c Args[ArgIdx] will be the available template argument.
2323 ///
2324 /// \returns true if there is another template argument (which will be at
2325 /// \c Args[ArgIdx]), false otherwise.
2327  unsigned &ArgIdx) {
2328  if (ArgIdx == Args.size())
2329  return false;
2330 
2331  const TemplateArgument &Arg = Args[ArgIdx];
2332  if (Arg.getKind() != TemplateArgument::Pack)
2333  return true;
2334 
2335  assert(ArgIdx == Args.size() - 1 && "Pack not at the end of argument list?");
2336  Args = Arg.pack_elements();
2337  ArgIdx = 0;
2338  return ArgIdx < Args.size();
2339 }
2340 
2341 /// Determine whether the given set of template arguments has a pack
2342 /// expansion that is not the last template argument.
2344  bool FoundPackExpansion = false;
2345  for (const auto &A : Args) {
2346  if (FoundPackExpansion)
2347  return true;
2348 
2349  if (A.getKind() == TemplateArgument::Pack)
2350  return hasPackExpansionBeforeEnd(A.pack_elements());
2351 
2352  // FIXME: If this is a fixed-arity pack expansion from an outer level of
2353  // templates, it should not be treated as a pack expansion.
2354  if (A.isPackExpansion())
2355  FoundPackExpansion = true;
2356  }
2357 
2358  return false;
2359 }
2360 
2365  TemplateDeductionInfo &Info,
2366  SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2367  bool NumberOfArgumentsMustMatch) {
2368  // C++0x [temp.deduct.type]p9:
2369  // If the template argument list of P contains a pack expansion that is not
2370  // the last template argument, the entire template argument list is a
2371  // non-deduced context.
2372  if (hasPackExpansionBeforeEnd(Ps))
2373  return Sema::TDK_Success;
2374 
2375  // C++0x [temp.deduct.type]p9:
2376  // If P has a form that contains <T> or <i>, then each argument Pi of the
2377  // respective template argument list P is compared with the corresponding
2378  // argument Ai of the corresponding template argument list of A.
2379  unsigned ArgIdx = 0, ParamIdx = 0;
2381  const TemplateArgument &P = Ps[ParamIdx];
2382  if (!P.isPackExpansion()) {
2383  // The simple case: deduce template arguments by matching Pi and Ai.
2384 
2385  // Check whether we have enough arguments.
2386  if (!hasTemplateArgumentForDeduction(As, ArgIdx))
2387  return NumberOfArgumentsMustMatch
2390 
2391  // C++1z [temp.deduct.type]p9:
2392  // During partial ordering, if Ai was originally a pack expansion [and]
2393  // Pi is not a pack expansion, template argument deduction fails.
2394  if (As[ArgIdx].isPackExpansion())
2396 
2397  // Perform deduction for this Pi/Ai pair.
2398  if (auto Result = DeduceTemplateArguments(S, TemplateParams, P,
2399  As[ArgIdx], Info, Deduced))
2400  return Result;
2401 
2402  // Move to the next argument.
2403  ++ArgIdx;
2404  continue;
2405  }
2406 
2407  // The parameter is a pack expansion.
2408 
2409  // C++0x [temp.deduct.type]p9:
2410  // If Pi is a pack expansion, then the pattern of Pi is compared with
2411  // each remaining argument in the template argument list of A. Each
2412  // comparison deduces template arguments for subsequent positions in the
2413  // template parameter packs expanded by Pi.
2414  TemplateArgument Pattern = P.getPackExpansionPattern();
2415 
2416  // Prepare to deduce the packs within the pattern.
2417  PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
2418 
2419  // Keep track of the deduced template arguments for each parameter pack
2420  // expanded by this pack expansion (the outer index) and for each
2421  // template argument (the inner SmallVectors).
2422  for (; hasTemplateArgumentForDeduction(As, ArgIdx) &&
2423  PackScope.hasNextElement();
2424  ++ArgIdx) {
2425  // Deduce template arguments from the pattern.
2426  if (auto Result = DeduceTemplateArguments(S, TemplateParams, Pattern,
2427  As[ArgIdx], Info, Deduced))
2428  return Result;
2429 
2430  PackScope.nextPackElement();
2431  }
2432 
2433  // Build argument packs for each of the parameter packs expanded by this
2434  // pack expansion.
2435  if (auto Result = PackScope.finish())
2436  return Result;
2437  }
2438 
2439  return Sema::TDK_Success;
2440 }
2441 
2444  const TemplateArgumentList &ParamList,
2445  const TemplateArgumentList &ArgList,
2446  TemplateDeductionInfo &Info,
2447  SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
2448  return DeduceTemplateArguments(S, TemplateParams, ParamList.asArray(),
2449  ArgList.asArray(), Info, Deduced,
2450  /*NumberOfArgumentsMustMatch=*/false);
2451 }
2452 
2453 /// Determine whether two template arguments are the same.
2454 static bool isSameTemplateArg(ASTContext &Context,
2456  const TemplateArgument &Y,
2457  bool PartialOrdering,
2458  bool PackExpansionMatchesPack = false) {
2459  // If we're checking deduced arguments (X) against original arguments (Y),
2460  // we will have flattened packs to non-expansions in X.
2461  if (PackExpansionMatchesPack && X.isPackExpansion() && !Y.isPackExpansion())
2462  X = X.getPackExpansionPattern();
2463 
2464  if (X.getKind() != Y.getKind())
2465  return false;
2466 
2467  switch (X.getKind()) {
2469  llvm_unreachable("Comparing NULL template argument");
2470 
2472  return Context.getCanonicalType(X.getAsType()) ==
2473  Context.getCanonicalType(Y.getAsType());
2474 
2476  return isSameDeclaration(X.getAsDecl(), Y.getAsDecl());
2477 
2479  return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
2480 
2483  return Context.getCanonicalTemplateName(
2484  X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
2485  Context.getCanonicalTemplateName(
2487 
2489  return hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral());
2490 
2492  llvm::FoldingSetNodeID XID, YID;
2493  X.getAsExpr()->Profile(XID, Context, true);
2494  Y.getAsExpr()->Profile(YID, Context, true);
2495  return XID == YID;
2496  }
2497 
2498  case TemplateArgument::Pack: {
2499  unsigned PackIterationSize = X.pack_size();
2500  if (X.pack_size() != Y.pack_size()) {
2501  if (!PartialOrdering)
2502  return false;
2503 
2504  // C++0x [temp.deduct.type]p9:
2505  // During partial ordering, if Ai was originally a pack expansion:
2506  // - if P does not contain a template argument corresponding to Ai
2507  // then Ai is ignored;
2508  bool XHasMoreArg = X.pack_size() > Y.pack_size();
2509  if (!(XHasMoreArg && X.pack_elements().back().isPackExpansion()) &&
2510  !(!XHasMoreArg && Y.pack_elements().back().isPackExpansion()))
2511  return false;
2512 
2513  if (XHasMoreArg)
2514  PackIterationSize = Y.pack_size();
2515  }
2516 
2517  ArrayRef<TemplateArgument> XP = X.pack_elements();
2519  for (unsigned i = 0; i < PackIterationSize; ++i)
2520  if (!isSameTemplateArg(Context, XP[i], YP[i], PartialOrdering,
2521  PackExpansionMatchesPack))
2522  return false;
2523  return true;
2524  }
2525  }
2526 
2527  llvm_unreachable("Invalid TemplateArgument Kind!");
2528 }
2529 
2530 /// Allocate a TemplateArgumentLoc where all locations have
2531 /// been initialized to the given location.
2532 ///
2533 /// \param Arg The template argument we are producing template argument
2534 /// location information for.
2535 ///
2536 /// \param NTTPType For a declaration template argument, the type of
2537 /// the non-type template parameter that corresponds to this template
2538 /// argument. Can be null if no type sugar is available to add to the
2539 /// type from the template argument.
2540 ///
2541 /// \param Loc The source location to use for the resulting template
2542 /// argument.
2545  QualType NTTPType, SourceLocation Loc) {
2546  switch (Arg.getKind()) {
2548  llvm_unreachable("Can't get a NULL template argument here");
2549 
2551  return TemplateArgumentLoc(
2552  Arg, Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
2553 
2555  if (NTTPType.isNull())
2556  NTTPType = Arg.getParamTypeForDecl();
2557  Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2558  .getAs<Expr>();
2559  return TemplateArgumentLoc(TemplateArgument(E), E);
2560  }
2561 
2563  if (NTTPType.isNull())
2564  NTTPType = Arg.getNullPtrType();
2565  Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2566  .getAs<Expr>();
2567  return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true),
2568  E);
2569  }
2570 
2572  Expr *E =
2573  BuildExpressionFromIntegralTemplateArgument(Arg, Loc).getAs<Expr>();
2574  return TemplateArgumentLoc(TemplateArgument(E), E);
2575  }
2576 
2581  if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
2582  Builder.MakeTrivial(Context, DTN->getQualifier(), Loc);
2583  else if (QualifiedTemplateName *QTN =
2584  Template.getAsQualifiedTemplateName())
2585  Builder.MakeTrivial(Context, QTN->getQualifier(), Loc);
2586 
2587  if (Arg.getKind() == TemplateArgument::Template)
2588  return TemplateArgumentLoc(Context, Arg,
2589  Builder.getWithLocInContext(Context), Loc);
2590 
2591  return TemplateArgumentLoc(
2592  Context, Arg, Builder.getWithLocInContext(Context), Loc, Loc);
2593  }
2594 
2596  return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2597 
2600  }
2601 
2602  llvm_unreachable("Invalid TemplateArgument Kind!");
2603 }
2604 
2607  SourceLocation Location) {
2608  return getTrivialTemplateArgumentLoc(
2609  Context.getInjectedTemplateArg(TemplateParm), QualType(), Location);
2610 }
2611 
2612 /// Convert the given deduced template argument and add it to the set of
2613 /// fully-converted template arguments.
2615  Sema &S, NamedDecl *Param, DeducedTemplateArgument Arg, NamedDecl *Template,
2616  TemplateDeductionInfo &Info, bool IsDeduced,
2617  SmallVectorImpl<TemplateArgument> &SugaredOutput,
2618  SmallVectorImpl<TemplateArgument> &CanonicalOutput) {
2619  auto ConvertArg = [&](DeducedTemplateArgument Arg,
2620  unsigned ArgumentPackIndex) {
2621  // Convert the deduced template argument into a template
2622  // argument that we can check, almost as if the user had written
2623  // the template argument explicitly.
2624  TemplateArgumentLoc ArgLoc =
2626 
2627  // Check the template argument, converting it as necessary.
2628  return S.CheckTemplateArgument(
2629  Param, ArgLoc, Template, Template->getLocation(),
2630  Template->getSourceRange().getEnd(), ArgumentPackIndex, SugaredOutput,
2631  CanonicalOutput,
2632  IsDeduced
2636  };
2637 
2638  if (Arg.getKind() == TemplateArgument::Pack) {
2639  // This is a template argument pack, so check each of its arguments against
2640  // the template parameter.
2641  SmallVector<TemplateArgument, 2> SugaredPackedArgsBuilder,
2642  CanonicalPackedArgsBuilder;
2643  for (const auto &P : Arg.pack_elements()) {
2644  // When converting the deduced template argument, append it to the
2645  // general output list. We need to do this so that the template argument
2646  // checking logic has all of the prior template arguments available.
2647  DeducedTemplateArgument InnerArg(P);
2649  assert(InnerArg.getKind() != TemplateArgument::Pack &&
2650  "deduced nested pack");
2651  if (P.isNull()) {
2652  // We deduced arguments for some elements of this pack, but not for
2653  // all of them. This happens if we get a conditionally-non-deduced
2654  // context in a pack expansion (such as an overload set in one of the
2655  // arguments).
2656  S.Diag(Param->getLocation(),
2657  diag::err_template_arg_deduced_incomplete_pack)
2658  << Arg << Param;
2659  return true;
2660  }
2661  if (ConvertArg(InnerArg, SugaredPackedArgsBuilder.size()))
2662  return true;
2663 
2664  // Move the converted template argument into our argument pack.
2665  SugaredPackedArgsBuilder.push_back(SugaredOutput.pop_back_val());
2666  CanonicalPackedArgsBuilder.push_back(CanonicalOutput.pop_back_val());
2667  }
2668 
2669  // If the pack is empty, we still need to substitute into the parameter
2670  // itself, in case that substitution fails.
2671  if (SugaredPackedArgsBuilder.empty()) {
2673  MultiLevelTemplateArgumentList Args(Template, SugaredOutput,
2674  /*Final=*/true);
2675 
2676  if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2677  Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2678  NTTP, SugaredOutput,
2679  Template->getSourceRange());
2680  if (Inst.isInvalid() ||
2681  S.SubstType(NTTP->getType(), Args, NTTP->getLocation(),
2682  NTTP->getDeclName()).isNull())
2683  return true;
2684  } else if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(Param)) {
2685  Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2686  TTP, SugaredOutput,
2687  Template->getSourceRange());
2688  if (Inst.isInvalid() || !S.SubstDecl(TTP, S.CurContext, Args))
2689  return true;
2690  }
2691  // For type parameters, no substitution is ever required.
2692  }
2693 
2694  // Create the resulting argument pack.
2695  SugaredOutput.push_back(
2696  TemplateArgument::CreatePackCopy(S.Context, SugaredPackedArgsBuilder));
2697  CanonicalOutput.push_back(TemplateArgument::CreatePackCopy(
2698  S.Context, CanonicalPackedArgsBuilder));
2699  return false;
2700  }
2701 
2702  return ConvertArg(Arg, 0);
2703 }
2704 
2705 // FIXME: This should not be a template, but
2706 // ClassTemplatePartialSpecializationDecl sadly does not derive from
2707 // TemplateDecl.
2708 template <typename TemplateDeclT>
2710  Sema &S, TemplateDeclT *Template, bool IsDeduced,
2711  SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2712  TemplateDeductionInfo &Info,
2713  SmallVectorImpl<TemplateArgument> &SugaredBuilder,
2714  SmallVectorImpl<TemplateArgument> &CanonicalBuilder,
2715  LocalInstantiationScope *CurrentInstantiationScope = nullptr,
2716  unsigned NumAlreadyConverted = 0, bool PartialOverloading = false) {
2717  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2718 
2719  for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2720  NamedDecl *Param = TemplateParams->getParam(I);
2721 
2722  // C++0x [temp.arg.explicit]p3:
2723  // A trailing template parameter pack (14.5.3) not otherwise deduced will
2724  // be deduced to an empty sequence of template arguments.
2725  // FIXME: Where did the word "trailing" come from?
2726  if (Deduced[I].isNull() && Param->isTemplateParameterPack()) {
2727  if (auto Result =
2728  PackDeductionScope(S, TemplateParams, Deduced, Info, I).finish())
2729  return Result;
2730  }
2731 
2732  if (!Deduced[I].isNull()) {
2733  if (I < NumAlreadyConverted) {
2734  // We may have had explicitly-specified template arguments for a
2735  // template parameter pack (that may or may not have been extended
2736  // via additional deduced arguments).
2737  if (Param->isParameterPack() && CurrentInstantiationScope &&
2738  CurrentInstantiationScope->getPartiallySubstitutedPack() == Param) {
2739  // Forget the partially-substituted pack; its substitution is now
2740  // complete.
2741  CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2742  // We still need to check the argument in case it was extended by
2743  // deduction.
2744  } else {
2745  // We have already fully type-checked and converted this
2746  // argument, because it was explicitly-specified. Just record the
2747  // presence of this argument.
2748  SugaredBuilder.push_back(Deduced[I]);
2749  CanonicalBuilder.push_back(
2750  S.Context.getCanonicalTemplateArgument(Deduced[I]));
2751  continue;
2752  }
2753  }
2754 
2755  // We may have deduced this argument, so it still needs to be
2756  // checked and converted.
2757  if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info,
2758  IsDeduced, SugaredBuilder,
2759  CanonicalBuilder)) {
2760  Info.Param = makeTemplateParameter(Param);
2761  // FIXME: These template arguments are temporary. Free them!
2762  Info.reset(
2763  TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder),
2764  TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder));
2766  }
2767 
2768  continue;
2769  }
2770 
2771  // Substitute into the default template argument, if available.
2772  bool HasDefaultArg = false;
2773  TemplateDecl *TD = dyn_cast<TemplateDecl>(Template);
2774  if (!TD) {
2775  assert(isa<ClassTemplatePartialSpecializationDecl>(Template) ||
2776  isa<VarTemplatePartialSpecializationDecl>(Template));
2777  return Sema::TDK_Incomplete;
2778  }
2779 
2780  TemplateArgumentLoc DefArg;
2781  {
2782  Qualifiers ThisTypeQuals;
2783  CXXRecordDecl *ThisContext = nullptr;
2784  if (auto *Rec = dyn_cast<CXXRecordDecl>(TD->getDeclContext()))
2785  if (Rec->isLambda())
2786  if (auto *Method = dyn_cast<CXXMethodDecl>(Rec->getDeclContext())) {
2787  ThisContext = Method->getParent();
2788  ThisTypeQuals = Method->getMethodQualifiers();
2789  }
2790 
2791  Sema::CXXThisScopeRAII ThisScope(S, ThisContext, ThisTypeQuals,
2792  S.getLangOpts().CPlusPlus17);
2793 
2795  TD, TD->getLocation(), TD->getSourceRange().getEnd(), Param,
2796  SugaredBuilder, CanonicalBuilder, HasDefaultArg);
2797  }
2798 
2799  // If there was no default argument, deduction is incomplete.
2800  if (DefArg.getArgument().isNull()) {
2802  const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2803  Info.reset(TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder),
2804  TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder));
2805  if (PartialOverloading) break;
2806 
2807  return HasDefaultArg ? Sema::TDK_SubstitutionFailure
2809  }
2810 
2811  // Check whether we can actually use the default argument.
2812  if (S.CheckTemplateArgument(
2813  Param, DefArg, TD, TD->getLocation(), TD->getSourceRange().getEnd(),
2814  0, SugaredBuilder, CanonicalBuilder, Sema::CTAK_Specified)) {
2816  const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2817  // FIXME: These template arguments are temporary. Free them!
2818  Info.reset(TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder),
2819  TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder));
2821  }
2822 
2823  // If we get here, we successfully used the default template argument.
2824  }
2825 
2826  return Sema::TDK_Success;
2827 }
2828 
2830  if (auto *DC = dyn_cast<DeclContext>(D))
2831  return DC;
2832  return D->getDeclContext();
2833 }
2834 
2835 template<typename T> struct IsPartialSpecialization {
2836  static constexpr bool value = false;
2837 };
2838 template<>
2840  static constexpr bool value = true;
2841 };
2842 template<>
2844  static constexpr bool value = true;
2845 };
2846 template <typename TemplateDeclT>
2847 static bool DeducedArgsNeedReplacement(TemplateDeclT *Template) {
2848  return false;
2849 }
2850 template <>
2853  return !Spec->isClassScopeExplicitSpecialization();
2854 }
2855 template <>
2858  return !Spec->isClassScopeExplicitSpecialization();
2859 }
2860 
2861 template <typename TemplateDeclT>
2863 CheckDeducedArgumentConstraints(Sema &S, TemplateDeclT *Template,
2864  ArrayRef<TemplateArgument> SugaredDeducedArgs,
2865  ArrayRef<TemplateArgument> CanonicalDeducedArgs,
2866  TemplateDeductionInfo &Info) {
2867  llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
2868  Template->getAssociatedConstraints(AssociatedConstraints);
2869 
2870  bool NeedsReplacement = DeducedArgsNeedReplacement(Template);
2872  SugaredDeducedArgs};
2873 
2875  Template, /*Final=*/true,
2876  /*InnerMost=*/NeedsReplacement ? nullptr : &DeducedTAL,
2877  /*RelativeToPrimary=*/true, /*Pattern=*/
2878  nullptr, /*ForConstraintInstantiation=*/true);
2879 
2880  // getTemplateInstantiationArgs picks up the non-deduced version of the
2881  // template args when this is a variable template partial specialization and
2882  // not class-scope explicit specialization, so replace with Deduced Args
2883  // instead of adding to inner-most.
2884  if (NeedsReplacement)
2885  MLTAL.replaceInnermostTemplateArguments(SugaredDeducedArgs);
2886 
2887  if (S.CheckConstraintSatisfaction(Template, AssociatedConstraints, MLTAL,
2888  Info.getLocation(),
2891  Info.reset(
2892  TemplateArgumentList::CreateCopy(S.Context, SugaredDeducedArgs),
2893  TemplateArgumentList::CreateCopy(S.Context, CanonicalDeducedArgs));
2895  }
2896  return Sema::TDK_Success;
2897 }
2898 
2899 /// Complete template argument deduction for a partial specialization.
2900 template <typename T>
2901 static std::enable_if_t<IsPartialSpecialization<T>::value,
2904  Sema &S, T *Partial, bool IsPartialOrdering,
2905  const TemplateArgumentList &TemplateArgs,
2906  SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2907  TemplateDeductionInfo &Info) {
2908  // Unevaluated SFINAE context.
2911  Sema::SFINAETrap Trap(S);
2912 
2913  Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Partial));
2914 
2915  // C++ [temp.deduct.type]p2:
2916  // [...] or if any template argument remains neither deduced nor
2917  // explicitly specified, template argument deduction fails.
2918  SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
2919  if (auto Result = ConvertDeducedTemplateArguments(
2920  S, Partial, IsPartialOrdering, Deduced, Info, SugaredBuilder,
2921  CanonicalBuilder))
2922  return Result;
2923 
2924  // Form the template argument list from the deduced template arguments.
2925  TemplateArgumentList *SugaredDeducedArgumentList =
2926  TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder);
2927  TemplateArgumentList *CanonicalDeducedArgumentList =
2928  TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder);
2929 
2930  Info.reset(SugaredDeducedArgumentList, CanonicalDeducedArgumentList);
2931 
2932  // Substitute the deduced template arguments into the template
2933  // arguments of the class template partial specialization, and
2934  // verify that the instantiated template arguments are both valid
2935  // and are equivalent to the template arguments originally provided
2936  // to the class template.
2937  LocalInstantiationScope InstScope(S);
2938  auto *Template = Partial->getSpecializedTemplate();
2939  const ASTTemplateArgumentListInfo *PartialTemplArgInfo =
2940  Partial->getTemplateArgsAsWritten();
2941 
2942  TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2943  PartialTemplArgInfo->RAngleLoc);
2944 
2945  if (S.SubstTemplateArguments(PartialTemplArgInfo->arguments(),
2947  SugaredBuilder,
2948  /*Final=*/true),
2949  InstArgs)) {
2950  unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2951  if (ParamIdx >= Partial->getTemplateParameters()->size())
2952  ParamIdx = Partial->getTemplateParameters()->size() - 1;
2953 
2954  Decl *Param = const_cast<NamedDecl *>(
2955  Partial->getTemplateParameters()->getParam(ParamIdx));
2956  Info.Param = makeTemplateParameter(Param);
2957  Info.FirstArg = (*PartialTemplArgInfo)[ArgIdx].getArgument();
2959  }
2960 
2961  bool ConstraintsNotSatisfied;
2962  SmallVector<TemplateArgument, 4> SugaredConvertedInstArgs,
2963  CanonicalConvertedInstArgs;
2965  Template, Partial->getLocation(), InstArgs, false,
2966  SugaredConvertedInstArgs, CanonicalConvertedInstArgs,
2967  /*UpdateArgsWithConversions=*/true, &ConstraintsNotSatisfied))
2968  return ConstraintsNotSatisfied ? Sema::TDK_ConstraintsNotSatisfied
2970 
2971  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2972  for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2973  TemplateArgument InstArg = SugaredConvertedInstArgs.data()[I];
2974  if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg,
2975  IsPartialOrdering)) {
2976  Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2977  Info.FirstArg = TemplateArgs[I];
2978  Info.SecondArg = InstArg;
2980  }
2981  }
2982 
2983  if (Trap.hasErrorOccurred())
2985 
2986  if (auto Result = CheckDeducedArgumentConstraints(S, Partial, SugaredBuilder,
2987  CanonicalBuilder, Info))
2988  return Result;
2989 
2990  return Sema::TDK_Success;
2991 }
2992 
2993 /// Complete template argument deduction for a class or variable template,
2994 /// when partial ordering against a partial specialization.
2995 // FIXME: Factor out duplication with partial specialization version above.
2997  Sema &S, TemplateDecl *Template, bool PartialOrdering,
2998  const TemplateArgumentList &TemplateArgs,
2999  SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3000  TemplateDeductionInfo &Info) {
3001  // Unevaluated SFINAE context.
3004  Sema::SFINAETrap Trap(S);
3005 
3006  Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Template));
3007 
3008  // C++ [temp.deduct.type]p2:
3009  // [...] or if any template argument remains neither deduced nor
3010  // explicitly specified, template argument deduction fails.
3011  SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
3012  if (auto Result = ConvertDeducedTemplateArguments(
3013  S, Template, /*IsDeduced*/ PartialOrdering, Deduced, Info,
3014  SugaredBuilder, CanonicalBuilder,
3015  /*CurrentInstantiationScope=*/nullptr,
3016  /*NumAlreadyConverted=*/0U, /*PartialOverloading=*/false))
3017  return Result;
3018 
3019  // Check that we produced the correct argument list.
3020  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
3021  for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
3022  TemplateArgument InstArg = CanonicalBuilder[I];
3023  if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg, PartialOrdering,
3024  /*PackExpansionMatchesPack=*/true)) {
3025  Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
3026  Info.FirstArg = TemplateArgs[I];
3027  Info.SecondArg = InstArg;
3029  }
3030  }
3031 
3032  if (Trap.hasErrorOccurred())
3034 
3035  if (auto Result = CheckDeducedArgumentConstraints(S, Template, SugaredBuilder,
3036  CanonicalBuilder, Info))
3037  return Result;
3038 
3039  return Sema::TDK_Success;
3040 }
3041 
3042 /// Perform template argument deduction to determine whether
3043 /// the given template arguments match the given class template
3044 /// partial specialization per C++ [temp.class.spec.match].
3047  const TemplateArgumentList &TemplateArgs,
3048  TemplateDeductionInfo &Info) {
3049  if (Partial->isInvalidDecl())
3050  return TDK_Invalid;
3051 
3052  // C++ [temp.class.spec.match]p2:
3053  // A partial specialization matches a given actual template
3054  // argument list if the template arguments of the partial
3055  // specialization can be deduced from the actual template argument
3056  // list (14.8.2).
3057 
3058  // Unevaluated SFINAE context.
3061  SFINAETrap Trap(*this);
3062 
3063  // This deduction has no relation to any outer instantiation we might be
3064  // performing.
3065  LocalInstantiationScope InstantiationScope(*this);
3066 
3068  Deduced.resize(Partial->getTemplateParameters()->size());
3069  if (TemplateDeductionResult Result
3070  = ::DeduceTemplateArguments(*this,
3071  Partial->getTemplateParameters(),
3072  Partial->getTemplateArgs(),
3073  TemplateArgs, Info, Deduced))
3074  return Result;
3075 
3076  SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3077  InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
3078  Info);
3079  if (Inst.isInvalid())
3080  return TDK_InstantiationDepth;
3081 
3082  if (Trap.hasErrorOccurred())
3084 
3085  TemplateDeductionResult Result;
3087  Result = ::FinishTemplateArgumentDeduction(*this, Partial,
3088  /*IsPartialOrdering=*/false,
3089  TemplateArgs, Deduced, Info);
3090  });
3091  return Result;
3092 }
3093 
3094 /// Perform template argument deduction to determine whether
3095 /// the given template arguments match the given variable template
3096 /// partial specialization per C++ [temp.class.spec.match].
3099  const TemplateArgumentList &TemplateArgs,
3100  TemplateDeductionInfo &Info) {
3101  if (Partial->isInvalidDecl())
3102  return TDK_Invalid;
3103 
3104  // C++ [temp.class.spec.match]p2:
3105  // A partial specialization matches a given actual template
3106  // argument list if the template arguments of the partial
3107  // specialization can be deduced from the actual template argument
3108  // list (14.8.2).
3109 
3110  // Unevaluated SFINAE context.
3113  SFINAETrap Trap(*this);
3114 
3115  // This deduction has no relation to any outer instantiation we might be
3116  // performing.
3117  LocalInstantiationScope InstantiationScope(*this);
3118 
3120  Deduced.resize(Partial->getTemplateParameters()->size());
3122  *this, Partial->getTemplateParameters(), Partial->getTemplateArgs(),
3123  TemplateArgs, Info, Deduced))
3124  return Result;
3125 
3126  SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3127  InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
3128  Info);
3129  if (Inst.isInvalid())
3130  return TDK_InstantiationDepth;
3131 
3132  if (Trap.hasErrorOccurred())
3134 
3135  TemplateDeductionResult Result;
3137  Result = ::FinishTemplateArgumentDeduction(*this, Partial,
3138  /*IsPartialOrdering=*/false,
3139  TemplateArgs, Deduced, Info);
3140  });
3141  return Result;
3142 }
3143 
3144 /// Determine whether the given type T is a simple-template-id type.
3146  if (const TemplateSpecializationType *Spec
3148  return Spec->getTemplateName().getAsTemplateDecl() != nullptr;
3149 
3150  // C++17 [temp.local]p2:
3151  // the injected-class-name [...] is equivalent to the template-name followed
3152  // by the template-arguments of the class template specialization or partial
3153  // specialization enclosed in <>
3154  // ... which means it's equivalent to a simple-template-id.
3155  //
3156  // This only arises during class template argument deduction for a copy
3157  // deduction candidate, where it permits slicing.
3158  if (T->getAs<InjectedClassNameType>())
3159  return true;
3160 
3161  return false;
3162 }
3163 
3164 /// Substitute the explicitly-provided template arguments into the
3165 /// given function template according to C++ [temp.arg.explicit].
3166 ///
3167 /// \param FunctionTemplate the function template into which the explicit
3168 /// template arguments will be substituted.
3169 ///
3170 /// \param ExplicitTemplateArgs the explicitly-specified template
3171 /// arguments.
3172 ///
3173 /// \param Deduced the deduced template arguments, which will be populated
3174 /// with the converted and checked explicit template arguments.
3175 ///
3176 /// \param ParamTypes will be populated with the instantiated function
3177 /// parameters.
3178 ///
3179 /// \param FunctionType if non-NULL, the result type of the function template
3180 /// will also be instantiated and the pointed-to value will be updated with
3181 /// the instantiated function type.
3182 ///
3183 /// \param Info if substitution fails for any reason, this object will be
3184 /// populated with more information about the failure.
3185 ///
3186 /// \returns TDK_Success if substitution was successful, or some failure
3187 /// condition.
3189  FunctionTemplateDecl *FunctionTemplate,
3190  TemplateArgumentListInfo &ExplicitTemplateArgs,
3193  TemplateDeductionInfo &Info) {
3194  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3195  TemplateParameterList *TemplateParams
3196  = FunctionTemplate->getTemplateParameters();
3197 
3198  if (ExplicitTemplateArgs.size() == 0) {
3199  // No arguments to substitute; just copy over the parameter types and
3200  // fill in the function type.
3201  for (auto *P : Function->parameters())
3202  ParamTypes.push_back(P->getType());
3203 
3204  if (FunctionType)
3205  *FunctionType = Function->getType();
3206  return TDK_Success;
3207  }
3208 
3209  // Unevaluated SFINAE context.
3212  SFINAETrap Trap(*this);
3213 
3214  // C++ [temp.arg.explicit]p3:
3215  // Template arguments that are present shall be specified in the
3216  // declaration order of their corresponding template-parameters. The
3217  // template argument list shall not specify more template-arguments than
3218  // there are corresponding template-parameters.
3219  SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
3220 
3221  // Enter a new template instantiation context where we check the
3222  // explicitly-specified template arguments against this function template,
3223  // and then substitute them into the function parameter types.
3225  InstantiatingTemplate Inst(
3226  *this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3227  CodeSynthesisContext::ExplicitTemplateArgumentSubstitution, Info);
3228  if (Inst.isInvalid())
3229  return TDK_InstantiationDepth;
3230 
3231  if (CheckTemplateArgumentList(FunctionTemplate, SourceLocation(),
3232  ExplicitTemplateArgs, true, SugaredBuilder,
3233  CanonicalBuilder,
3234  /*UpdateArgsWithConversions=*/false) ||
3235  Trap.hasErrorOccurred()) {
3236  unsigned Index = SugaredBuilder.size();
3237  if (Index >= TemplateParams->size())
3238  return TDK_SubstitutionFailure;
3239  Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
3240  return TDK_InvalidExplicitArguments;
3241  }
3242 
3243  // Form the template argument list from the explicitly-specified
3244  // template arguments.
3245  TemplateArgumentList *SugaredExplicitArgumentList =
3246  TemplateArgumentList::CreateCopy(Context, SugaredBuilder);
3247  TemplateArgumentList *CanonicalExplicitArgumentList =
3248  TemplateArgumentList::CreateCopy(Context, CanonicalBuilder);
3249  Info.setExplicitArgs(SugaredExplicitArgumentList,
3250  CanonicalExplicitArgumentList);
3251 
3252  // Template argument deduction and the final substitution should be
3253  // done in the context of the templated declaration. Explicit
3254  // argument substitution, on the other hand, needs to happen in the
3255  // calling context.
3256  ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3257 
3258  // If we deduced template arguments for a template parameter pack,
3259  // note that the template argument pack is partially substituted and record
3260  // the explicit template arguments. They'll be used as part of deduction
3261  // for this template parameter pack.
3262  unsigned PartiallySubstitutedPackIndex = -1u;
3263  if (!CanonicalBuilder.empty()) {
3264  const TemplateArgument &Arg = CanonicalBuilder.back();
3265  if (Arg.getKind() == TemplateArgument::Pack) {
3266  auto *Param = TemplateParams->getParam(CanonicalBuilder.size() - 1);
3267  // If this is a fully-saturated fixed-size pack, it should be
3268  // fully-substituted, not partially-substituted.
3269  Optional<unsigned> Expansions = getExpandedPackSize(Param);
3270  if (!Expansions || Arg.pack_size() < *Expansions) {
3271  PartiallySubstitutedPackIndex = CanonicalBuilder.size() - 1;
3272  CurrentInstantiationScope->SetPartiallySubstitutedPack(
3273  Param, Arg.pack_begin(), Arg.pack_size());
3274  }
3275  }
3276  }
3277 
3278  const FunctionProtoType *Proto
3279  = Function->getType()->getAs<FunctionProtoType>();
3280  assert(Proto && "Function template does not have a prototype?");
3281 
3282  // Isolate our substituted parameters from our caller.
3283  LocalInstantiationScope InstScope(*this, /*MergeWithOuterScope*/true);
3284 
3285  ExtParameterInfoBuilder ExtParamInfos;
3286 
3287  MultiLevelTemplateArgumentList MLTAL(FunctionTemplate,
3288  SugaredExplicitArgumentList->asArray(),
3289  /*Final=*/true);
3290 
3291  // Instantiate the types of each of the function parameters given the
3292  // explicitly-specified template arguments. If the function has a trailing
3293  // return type, substitute it after the arguments to ensure we substitute
3294  // in lexical order.
3295  if (Proto->hasTrailingReturn()) {
3296  if (SubstParmTypes(Function->getLocation(), Function->parameters(),
3297  Proto->getExtParameterInfosOrNull(), MLTAL, ParamTypes,
3298  /*params=*/nullptr, ExtParamInfos))
3299  return TDK_SubstitutionFailure;
3300  }
3301 
3302  // Instantiate the return type.
3303  QualType ResultType;
3304  {
3305  // C++11 [expr.prim.general]p3:
3306  // If a declaration declares a member function or member function
3307  // template of a class X, the expression this is a prvalue of type
3308  // "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
3309  // and the end of the function-definition, member-declarator, or
3310  // declarator.
3311  Qualifiers ThisTypeQuals;
3312  CXXRecordDecl *ThisContext = nullptr;
3313  if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
3314  ThisContext = Method->getParent();
3315  ThisTypeQuals = Method->getMethodQualifiers();
3316  }
3317 
3318  CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
3319  getLangOpts().CPlusPlus11);
3320 
3321  ResultType =
3322  SubstType(Proto->getReturnType(), MLTAL,
3323  Function->getTypeSpecStartLoc(), Function->getDeclName());
3324  if (ResultType.isNull() || Trap.hasErrorOccurred())
3325  return TDK_SubstitutionFailure;
3326  // CUDA: Kernel function must have 'void' return type.
3327  if (getLangOpts().CUDA)
3328  if (Function->hasAttr<CUDAGlobalAttr>() && !ResultType->isVoidType()) {
3329  Diag(Function->getLocation(), diag::err_kern_type_not_void_return)
3330  << Function->getType() << Function->getSourceRange();
3331  return TDK_SubstitutionFailure;
3332  }
3333  }
3334 
3335  // Instantiate the types of each of the function parameters given the
3336  // explicitly-specified template arguments if we didn't do so earlier.
3337  if (!Proto->hasTrailingReturn() &&
3338  SubstParmTypes(Function->getLocation(), Function->parameters(),
3339  Proto->getExtParameterInfosOrNull(), MLTAL, ParamTypes,
3340  /*params*/ nullptr, ExtParamInfos))
3341  return TDK_SubstitutionFailure;
3342 
3343  if (FunctionType) {
3344  auto EPI = Proto->getExtProtoInfo();
3345  EPI.ExtParameterInfos = ExtParamInfos.getPointerOrNull(ParamTypes.size());
3346 
3347  // In C++1z onwards, exception specifications are part of the function type,
3348  // so substitution into the type must also substitute into the exception
3349  // specification.
3350  SmallVector<QualType, 4> ExceptionStorage;
3351  if (getLangOpts().CPlusPlus17 &&
3352  SubstExceptionSpec(Function->getLocation(), EPI.ExceptionSpec,
3353  ExceptionStorage, MLTAL))
3354  return TDK_SubstitutionFailure;
3355 
3356  *FunctionType = BuildFunctionType(ResultType, ParamTypes,
3357  Function->getLocation(),
3358  Function->getDeclName(),
3359  EPI);
3360  if (FunctionType->isNull() || Trap.hasErrorOccurred())
3361  return TDK_SubstitutionFailure;
3362  }
3363 
3364  // C++ [temp.arg.explicit]p2:
3365  // Trailing template arguments that can be deduced (14.8.2) may be
3366  // omitted from the list of explicit template-arguments. If all of the
3367  // template arguments can be deduced, they may all be omitted; in this
3368  // case, the empty template argument list <> itself may also be omitted.
3369  //
3370  // Take all of the explicitly-specified arguments and put them into
3371  // the set of deduced template arguments. The partially-substituted
3372  // parameter pack, however, will be set to NULL since the deduction
3373  // mechanism handles the partially-substituted argument pack directly.
3374  Deduced.reserve(TemplateParams->size());
3375  for (unsigned I = 0, N = SugaredExplicitArgumentList->size(); I != N; ++I) {
3376  const TemplateArgument &Arg = SugaredExplicitArgumentList->get(I);
3377  if (I == PartiallySubstitutedPackIndex)
3378  Deduced.push_back(DeducedTemplateArgument());
3379  else
3380  Deduced.push_back(Arg);
3381  }
3382 
3383  return TDK_Success;
3384 }
3385 
3386 /// Check whether the deduced argument type for a call to a function
3387 /// template matches the actual argument type per C++ [temp.deduct.call]p4.
3390  Sema::OriginalCallArg OriginalArg,
3391  QualType DeducedA) {
3392  ASTContext &Context = S.Context;
3393 
3394  auto Failed = [&]() -> Sema::TemplateDeductionResult {
3395  Info.FirstArg = TemplateArgument(DeducedA);
3396  Info.SecondArg = TemplateArgument(OriginalArg.OriginalArgType);
3397  Info.CallArgIndex = OriginalArg.ArgIdx;
3400  };
3401 
3402  QualType A = OriginalArg.OriginalArgType;
3403  QualType OriginalParamType = OriginalArg.OriginalParamType;
3404 
3405  // Check for type equality (top-level cv-qualifiers are ignored).
3406  if (Context.hasSameUnqualifiedType(A, DeducedA))
3407  return Sema::TDK_Success;
3408 
3409  // Strip off references on the argument types; they aren't needed for
3410  // the following checks.
3411  if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
3412  DeducedA = DeducedARef->getPointeeType();
3413  if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3414  A = ARef->getPointeeType();
3415 
3416  // C++ [temp.deduct.call]p4:
3417  // [...] However, there are three cases that allow a difference:
3418  // - If the original P is a reference type, the deduced A (i.e., the
3419  // type referred to by the reference) can be more cv-qualified than
3420  // the transformed A.
3421  if (const ReferenceType *OriginalParamRef
3422  = OriginalParamType->getAs<ReferenceType>()) {
3423  // We don't want to keep the reference around any more.
3424  OriginalParamType = OriginalParamRef->getPointeeType();
3425 
3426  // FIXME: Resolve core issue (no number yet): if the original P is a
3427  // reference type and the transformed A is function type "noexcept F",
3428  // the deduced A can be F.
3429  QualType Tmp;
3430  if (A->isFunctionType() && S.IsFunctionConversion(A, DeducedA, Tmp))
3431  return Sema::TDK_Success;
3432 
3433  Qualifiers AQuals = A.getQualifiers();
3434  Qualifiers DeducedAQuals = DeducedA.getQualifiers();
3435 
3436  // Under Objective-C++ ARC, the deduced type may have implicitly
3437  // been given strong or (when dealing with a const reference)
3438  // unsafe_unretained lifetime. If so, update the original
3439  // qualifiers to include this lifetime.
3440  if (S.getLangOpts().ObjCAutoRefCount &&
3441  ((DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong &&
3442  AQuals.getObjCLifetime() == Qualifiers::OCL_None) ||
3443  (DeducedAQuals.hasConst() &&
3444  DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone))) {
3445  AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime());
3446  }
3447 
3448  if (AQuals == DeducedAQuals) {
3449  // Qualifiers match; there's nothing to do.
3450  } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) {
3451  return Failed();
3452  } else {
3453  // Qualifiers are compatible, so have the argument type adopt the
3454  // deduced argument type's qualifiers as if we had performed the
3455  // qualification conversion.
3456  A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
3457  }
3458  }
3459 
3460  // - The transformed A can be another pointer or pointer to member
3461  // type that can be converted to the deduced A via a function pointer
3462  // conversion and/or a qualification conversion.
3463  //
3464  // Also allow conversions which merely strip __attribute__((noreturn)) from
3465  // function types (recursively).
3466  bool ObjCLifetimeConversion = false;
3467  QualType ResultTy;
3468  if ((A->isAnyPointerType() || A->isMemberPointerType()) &&
3469  (S.IsQualificationConversion(A, DeducedA, false,
3470  ObjCLifetimeConversion) ||
3471  S.IsFunctionConversion(A, DeducedA, ResultTy)))
3472  return Sema::TDK_Success;
3473 
3474  // - If P is a class and P has the form simple-template-id, then the
3475  // transformed A can be a derived class of the deduced A. [...]
3476  // [...] Likewise, if P is a pointer to a class of the form
3477  // simple-template-id, the transformed A can be a pointer to a
3478  // derived class pointed to by the deduced A.
3479  if (const PointerType *OriginalParamPtr
3480  = OriginalParamType->getAs<PointerType>()) {
3481  if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
3482  if (const PointerType *APtr = A->getAs<PointerType>()) {
3483  if (A->getPointeeType()->isRecordType()) {
3484  OriginalParamType = OriginalParamPtr->getPointeeType();
3485  DeducedA = DeducedAPtr->getPointeeType();
3486  A = APtr->getPointeeType();
3487  }
3488  }
3489  }
3490  }
3491 
3492  if (Context.hasSameUnqualifiedType(A, DeducedA))
3493  return Sema::TDK_Success;
3494 
3495  if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) &&
3496  S.IsDerivedFrom(Info.getLocation(), A, DeducedA))
3497  return Sema::TDK_Success;
3498 
3499  return Failed();
3500 }
3501 
3502 /// Find the pack index for a particular parameter index in an instantiation of
3503 /// a function template with specific arguments.
3504 ///
3505 /// \return The pack index for whichever pack produced this parameter, or -1
3506 /// if this was not produced by a parameter. Intended to be used as the
3507 /// ArgumentPackSubstitutionIndex for further substitutions.
3508 // FIXME: We should track this in OriginalCallArgs so we don't need to
3509 // reconstruct it here.
3510 static unsigned getPackIndexForParam(Sema &S,
3511  FunctionTemplateDecl *FunctionTemplate,
3512  const MultiLevelTemplateArgumentList &Args,
3513  unsigned ParamIdx) {
3514  unsigned Idx = 0;
3515  for (auto *PD : FunctionTemplate->getTemplatedDecl()->parameters()) {
3516  if (PD->isParameterPack()) {
3517  unsigned NumExpansions =
3518  S.getNumArgumentsInExpansion(PD->getType(), Args).value_or(1);
3519  if (Idx + NumExpansions > ParamIdx)
3520  return ParamIdx - Idx;
3521  Idx += NumExpansions;
3522  } else {
3523  if (Idx == ParamIdx)
3524  return -1; // Not a pack expansion
3525  ++Idx;
3526  }
3527  }
3528 
3529  llvm_unreachable("parameter index would not be produced from template");
3530 }
3531 
3532 /// Finish template argument deduction for a function template,
3533 /// checking the deduced template arguments for completeness and forming
3534 /// the function template specialization.
3535 ///
3536 /// \param OriginalCallArgs If non-NULL, the original call arguments against
3537 /// which the deduced argument types should be compared.
3539  FunctionTemplateDecl *FunctionTemplate,
3541  unsigned NumExplicitlySpecified, FunctionDecl *&Specialization,
3542  TemplateDeductionInfo &Info,
3543  SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs,
3544  bool PartialOverloading, llvm::function_ref<bool()> CheckNonDependent) {
3545  // Unevaluated SFINAE context.
3548  SFINAETrap Trap(*this);
3549 
3550  // Enter a new template instantiation context while we instantiate the
3551  // actual function declaration.
3552  SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3553  InstantiatingTemplate Inst(
3554  *this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3555  CodeSynthesisContext::DeducedTemplateArgumentSubstitution, Info);
3556  if (Inst.isInvalid())
3557  return TDK_InstantiationDepth;
3558 
3559  ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3560 
3561  // C++ [temp.deduct.type]p2:
3562  // [...] or if any template argument remains neither deduced nor
3563  // explicitly specified, template argument deduction fails.
3564  SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder;
3565  if (auto Result = ConvertDeducedTemplateArguments(
3566  *this, FunctionTemplate, /*IsDeduced*/ true, Deduced, Info,
3567  SugaredBuilder, CanonicalBuilder, CurrentInstantiationScope,
3568  NumExplicitlySpecified, PartialOverloading))
3569  return Result;
3570 
3571  // C++ [temp.deduct.call]p10: [DR1391]
3572  // If deduction succeeds for all parameters that contain
3573  // template-parameters that participate in template argument deduction,
3574  // and all template arguments are explicitly specified, deduced, or
3575  // obtained from default template arguments, remaining parameters are then
3576  // compared with the corresponding arguments. For each remaining parameter
3577  // P with a type that was non-dependent before substitution of any
3578  // explicitly-specified template arguments, if the corresponding argument
3579  // A cannot be implicitly converted to P, deduction fails.
3580  if (CheckNonDependent())
3581  return TDK_NonDependentConversionFailure;
3582 
3583  // Form the template argument list from the deduced template arguments.
3584  TemplateArgumentList *SugaredDeducedArgumentList =
3585  TemplateArgumentList::CreateCopy(Context, SugaredBuilder);
3586  TemplateArgumentList *CanonicalDeducedArgumentList =
3587  TemplateArgumentList::CreateCopy(Context, CanonicalBuilder);
3588  Info.reset(SugaredDeducedArgumentList, CanonicalDeducedArgumentList);
3589 
3590  // Substitute the deduced template arguments into the function template
3591  // declaration to produce the function template specialization.
3592  DeclContext *Owner = FunctionTemplate->getDeclContext();
3593  if (FunctionTemplate->getFriendObjectKind())
3594  Owner = FunctionTemplate->getLexicalDeclContext();
3596  FunctionTemplate, CanonicalDeducedArgumentList->asArray(),
3597  /*Final=*/false);
3598  Specialization = cast_or_null<FunctionDecl>(
3599  SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner, SubstArgs));
3600  if (!Specialization || Specialization->isInvalidDecl())
3601  return TDK_SubstitutionFailure;
3602 
3603  assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
3604  FunctionTemplate->getCanonicalDecl());
3605 
3606  // If the template argument list is owned by the function template
3607  // specialization, release it.
3608  if (Specialization->getTemplateSpecializationArgs() ==
3609  CanonicalDeducedArgumentList &&
3610  !Trap.hasErrorOccurred())
3611  Info.takeCanonical();
3612 
3613  // There may have been an error that did not prevent us from constructing a
3614  // declaration. Mark the declaration invalid and return with a substitution
3615  // failure.
3616  if (Trap.hasErrorOccurred()) {
3617  Specialization->setInvalidDecl(true);
3618  return TDK_SubstitutionFailure;
3619  }
3620 
3621  // C++2a [temp.deduct]p5
3622  // [...] When all template arguments have been deduced [...] all uses of
3623  // template parameters [...] are replaced with the corresponding deduced
3624  // or default argument values.
3625  // [...] If the function template has associated constraints
3626  // ([temp.constr.decl]), those constraints are checked for satisfaction
3627  // ([temp.constr.constr]). If the constraints are not satisfied, type
3628  // deduction fails.
3629  if (!PartialOverloading ||
3630  (CanonicalBuilder.size() ==
3631  FunctionTemplate->getTemplateParameters()->size())) {
3632  if (CheckInstantiatedFunctionTemplateConstraints(
3633  Info.getLocation(), Specialization, CanonicalBuilder,
3635  return TDK_MiscellaneousDeductionFailure;
3636 
3638  Info.reset(Info.takeSugared(),
3639  TemplateArgumentList::CreateCopy(Context, CanonicalBuilder));
3640  return TDK_ConstraintsNotSatisfied;
3641  }
3642  }
3643 
3644  if (OriginalCallArgs) {
3645  // C++ [temp.deduct.call]p4:
3646  // In general, the deduction process attempts to find template argument
3647  // values that will make the deduced A identical to A (after the type A
3648  // is transformed as described above). [...]
3649  llvm::SmallDenseMap<std::pair<unsigned, QualType>, QualType> DeducedATypes;
3650  for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
3651  OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
3652 
3653  auto ParamIdx = OriginalArg.ArgIdx;
3654  if (ParamIdx >= Specialization->getNumParams())
3655  // FIXME: This presumably means a pack ended up smaller than we
3656  // expected while deducing. Should this not result in deduction
3657  // failure? Can it even happen?
3658  continue;
3659 
3660  QualType DeducedA;
3661  if (!OriginalArg.DecomposedParam) {
3662  // P is one of the function parameters, just look up its substituted
3663  // type.
3664  DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
3665  } else {
3666  // P is a decomposed element of a parameter corresponding to a
3667  // braced-init-list argument. Substitute back into P to find the
3668  // deduced A.
3669  QualType &CacheEntry =
3670  DeducedATypes[{ParamIdx, OriginalArg.OriginalParamType}];
3671  if (CacheEntry.isNull()) {
3673  *this, getPackIndexForParam(*this, FunctionTemplate, SubstArgs,
3674  ParamIdx));
3675  CacheEntry =
3676  SubstType(OriginalArg.OriginalParamType, SubstArgs,
3677  Specialization->getTypeSpecStartLoc(),
3678  Specialization->getDeclName());
3679  }
3680  DeducedA = CacheEntry;
3681  }
3682 
3683  if (auto TDK =
3684  CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA))
3685  return TDK;
3686  }
3687  }
3688 
3689  // If we suppressed any diagnostics while performing template argument
3690  // deduction, and if we haven't already instantiated this declaration,
3691  // keep track of these diagnostics. They'll be emitted if this specialization
3692  // is actually used.
3693  if (Info.diag_begin() != Info.diag_end()) {
3694  SuppressedDiagnosticsMap::iterator
3695  Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
3696  if (Pos == SuppressedDiagnostics.end())
3697  SuppressedDiagnostics[Specialization->getCanonicalDecl()]
3698  .append(Info.diag_begin(), Info.diag_end());
3699  }
3700 
3701  return TDK_Success;
3702 }
3703 
3704 /// Gets the type of a function for template-argument-deducton
3705 /// purposes when it's considered as part of an overload set.
3707  FunctionDecl *Fn) {
3708  // We may need to deduce the return type of the function now.
3709  if (S.getLangOpts().CPlusPlus14 && Fn->getReturnType()->isUndeducedType() &&
3710  S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/ false))
3711  return {};
3712 
3713  if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
3714  if (Method->isInstance()) {
3715  // An instance method that's referenced in a form that doesn't
3716  // look like a member pointer is just invalid.
3717  if (!R.HasFormOfMemberPointer)
3718  return {};
3719 
3720  return S.Context.getMemberPointerType(Fn->getType(),
3721  S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
3722  }
3723 
3724  if (!R.IsAddressOfOperand) return Fn->getType();
3725  return S.Context.getPointerType(Fn->getType());
3726 }
3727 
3728 /// Apply the deduction rules for overload sets.
3729 ///
3730 /// \return the null type if this argument should be treated as an
3731 /// undeduced context
3732 static QualType
3734  Expr *Arg, QualType ParamType,
3735  bool ParamWasReference) {
3736 
3738 
3739  OverloadExpr *Ovl = R.Expression;
3740 
3741  // C++0x [temp.deduct.call]p4
3742  unsigned TDF = 0;
3743  if (ParamWasReference)
3745  if (R.IsAddressOfOperand)
3746  TDF |= TDF_IgnoreQualifiers;
3747 
3748  // C++0x [temp.deduct.call]p6:
3749  // When P is a function type, pointer to function type, or pointer
3750  // to member function type:
3751 
3752  if (!ParamType->isFunctionType() &&
3753  !ParamType->isFunctionPointerType() &&
3754  !ParamType->isMemberFunctionPointerType()) {
3755  if (Ovl->hasExplicitTemplateArgs()) {
3756  // But we can still look for an explicit specialization.
3757  if (FunctionDecl *ExplicitSpec
3759  return GetTypeOfFunction(S, R, ExplicitSpec);
3760  }
3761 
3762  DeclAccessPair DAP;
3763  if (FunctionDecl *Viable =
3765  return GetTypeOfFunction(S, R, Viable);
3766 
3767  return {};
3768  }
3769 
3770  // Gather the explicit template arguments, if any.
3771  TemplateArgumentListInfo ExplicitTemplateArgs;
3772  if (Ovl->hasExplicitTemplateArgs())
3773  Ovl->copyTemplateArgumentsInto(ExplicitTemplateArgs);
3774  QualType Match;
3775  for (UnresolvedSetIterator I = Ovl->decls_begin(),
3776  E = Ovl->decls_end(); I != E; ++I) {
3777  NamedDecl *D = (*I)->getUnderlyingDecl();
3778 
3779  if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
3780  // - If the argument is an overload set containing one or more
3781  // function templates, the parameter is treated as a
3782  // non-deduced context.
3783  if (!Ovl->hasExplicitTemplateArgs())
3784  return {};
3785 
3786  // Otherwise, see if we can resolve a function type
3787  FunctionDecl *Specialization = nullptr;
3788  TemplateDeductionInfo Info(Ovl->getNameLoc());
3789  if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
3790  Specialization, Info))
3791  continue;
3792 
3793  D = Specialization;
3794  }
3795 
3796  FunctionDecl *Fn = cast<FunctionDecl>(D);
3797  QualType ArgType = GetTypeOfFunction(S, R, Fn);
3798  if (ArgType.isNull()) continue;
3799 
3800  // Function-to-pointer conversion.
3801  if (!ParamWasReference && ParamType->isPointerType() &&
3802  ArgType->isFunctionType())
3803  ArgType = S.Context.getPointerType(ArgType);
3804 
3805  // - If the argument is an overload set (not containing function
3806  // templates), trial argument deduction is attempted using each
3807  // of the members of the set. If deduction succeeds for only one
3808  // of the overload set members, that member is used as the
3809  // argument value for the deduction. If deduction succeeds for
3810  // more than one member of the overload set the parameter is
3811  // treated as a non-deduced context.
3812 
3813  // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
3814  // Type deduction is done independently for each P/A pair, and
3815  // the deduced template argument values are then combined.
3816  // So we do not reject deductions which were made elsewhere.
3818  Deduced(TemplateParams->size());
3819  TemplateDeductionInfo Info(Ovl->getNameLoc());
3821  = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3822  ArgType, Info, Deduced, TDF);
3823  if (Result) continue;
3824  if (!Match.isNull())
3825  return {};
3826  Match = ArgType;
3827  }
3828 
3829  return Match;
3830 }
3831 
3832 /// Perform the adjustments to the parameter and argument types
3833 /// described in C++ [temp.deduct.call].
3834 ///
3835 /// \returns true if the caller should not attempt to perform any template
3836 /// argument deduction based on this P/A pair because the argument is an
3837 /// overloaded function set that could not be resolved.
3839  Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3840  QualType &ParamType, QualType &ArgType, Expr *Arg, unsigned &TDF) {
3841  // C++0x [temp.deduct.call]p3:
3842  // If P is a cv-qualified type, the top level cv-qualifiers of P's type
3843  // are ignored for type deduction.
3844  if (ParamType.hasQualifiers())
3845  ParamType = ParamType.getUnqualifiedType();
3846 
3847  // [...] If P is a reference type, the type referred to by P is
3848  // used for type deduction.
3849  const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
3850  if (ParamRefType)
3851  ParamType = ParamRefType->getPointeeType();
3852 
3853  // Overload sets usually make this parameter an undeduced context,
3854  // but there are sometimes special circumstances. Typically
3855  // involving a template-id-expr.
3856  if (ArgType == S.Context.OverloadTy) {
3857  ArgType = ResolveOverloadForDeduction(S, TemplateParams,
3858  Arg, ParamType,
3859  ParamRefType != nullptr);
3860  if (ArgType.isNull())
3861  return true;
3862  }
3863 
3864  if (ParamRefType) {
3865  // If the argument has incomplete array type, try to complete its type.
3866  if (ArgType->isIncompleteArrayType())
3867  ArgType = S.getCompletedType(Arg);
3868 
3869  // C++1z [temp.deduct.call]p3:
3870  // If P is a forwarding reference and the argument is an lvalue, the type
3871  // "lvalue reference to A" is used in place of A for type deduction.
3872  if (isForwardingReference(QualType(ParamRefType, 0), FirstInnerIndex) &&
3873  Arg->isLValue()) {
3874  if (S.getLangOpts().OpenCL && !ArgType.hasAddressSpace())
3875  ArgType = S.Context.getAddrSpaceQualType(
3877  ArgType = S.Context.getLValueReferenceType(ArgType);
3878  }
3879  } else {
3880  // C++ [temp.deduct.call]p2:
3881  // If P is not a reference type:
3882  // - If A is an array type, the pointer type produced by the
3883  // array-to-pointer standard conversion (4.2) is used in place of
3884  // A for type deduction; otherwise,
3885  // - If A is a function type, the pointer type produced by the
3886  // function-to-pointer standard conversion (4.3) is used in place
3887  // of A for type deduction; otherwise,
3888  if (ArgType->canDecayToPointerType())
3889  ArgType = S.Context.getDecayedType(ArgType);
3890  else {
3891  // - If A is a cv-qualified type, the top level cv-qualifiers of A's
3892  // type are ignored for type deduction.
3893  ArgType = ArgType.getUnqualifiedType();
3894  }
3895  }
3896 
3897  // C++0x [temp.deduct.call]p4:
3898  // In general, the deduction process attempts to find template argument
3899  // values that will make the deduced A identical to A (after the type A
3900  // is transformed as described above). [...]
3901  TDF = TDF_SkipNonDependent;
3902 
3903  // - If the original P is a reference type, the deduced A (i.e., the
3904  // type referred to by the reference) can be more cv-qualified than
3905  // the transformed A.
3906  if (ParamRefType)
3908  // - The transformed A can be another pointer or pointer to member
3909  // type that can be converted to the deduced A via a qualification
3910  // conversion (4.4).
3911  if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
3912  ArgType->isObjCObjectPointerType())
3913  TDF |= TDF_IgnoreQualifiers;
3914  // - If P is a class and P has the form simple-template-id, then the
3915  // transformed A can be a derived class of the deduced A. Likewise,
3916  // if P is a pointer to a class of the form simple-template-id, the
3917  // transformed A can be a pointer to a derived class pointed to by
3918  // the deduced A.
3919  if (isSimpleTemplateIdType(ParamType) ||
3920  (isa<PointerType>(ParamType) &&
3922  ParamType->castAs<PointerType>()->getPointeeType())))
3923  TDF |= TDF_DerivedClass;
3924 
3925  return false;
3926 }
3927 
3928 static bool
3930  QualType T);
3931 
3933  Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3934  QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
3935  SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3936  SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs,
3937  bool DecomposedParam, unsigned ArgIdx, unsigned TDF);
3938 
3939 /// Attempt template argument deduction from an initializer list
3940 /// deemed to be an argument in a function call.
3942  Sema &S, TemplateParameterList *TemplateParams, QualType AdjustedParamType,
3943  InitListExpr *ILE, TemplateDeductionInfo &Info,
3944  SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3945  SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs, unsigned ArgIdx,
3946  unsigned TDF) {
3947  // C++ [temp.deduct.call]p1: (CWG 1591)
3948  // If removing references and cv-qualifiers from P gives
3949  // std::initializer_list<P0> or P0[N] for some P0 and N and the argument is
3950  // a non-empty initializer list, then deduction is performed instead for
3951  // each element of the initializer list, taking P0 as a function template
3952  // parameter type and the initializer element as its argument
3953  //
3954  // We've already removed references and cv-qualifiers here.
3955  if (!ILE->getNumInits())
3956  return Sema::TDK_Success;
3957 
3958  QualType ElTy;
3959  auto *ArrTy = S.Context.getAsArrayType(AdjustedParamType);
3960  if (ArrTy)
3961  ElTy = ArrTy->getElementType();
3962  else if (!S.isStdInitializerList(AdjustedParamType, &ElTy)) {
3963  // Otherwise, an initializer list argument causes the parameter to be
3964  // considered a non-deduced context
3965  return Sema::TDK_Success;
3966  }
3967 
3968  // Resolving a core issue: a braced-init-list containing any designators is
3969  // a non-deduced context.
3970  for (Expr *E : ILE->inits())
3971  if (isa<DesignatedInitExpr>(E))
3972  return Sema::TDK_Success;
3973 
3974  // Deduction only needs to be done for dependent types.
3975  if (ElTy->isDependentType()) {
3976  for (Expr *E : ILE->inits()) {
3977  if (auto Result = DeduceTemplateArgumentsFromCallArgument(
3978  S, TemplateParams, 0, ElTy, E, Info, Deduced, OriginalCallArgs, true,
3979  ArgIdx, TDF))
3980  return Result;
3981  }
3982  }
3983 
3984  // in the P0[N] case, if N is a non-type template parameter, N is deduced
3985  // from the length of the initializer list.
3986  if (auto *DependentArrTy = dyn_cast_or_null<DependentSizedArrayType>(ArrTy)) {
3987  // Determine the array bound is something we can deduce.
3988  if (const NonTypeTemplateParmDecl *NTTP =
3989  getDeducedParameterFromExpr(Info, DependentArrTy->getSizeExpr())) {
3990  // We can perform template argument deduction for the given non-type
3991  // template parameter.
3992  // C++ [temp.deduct.type]p13:
3993  // The type of N in the type T[N] is std::size_t.
3994  QualType T = S.Context.getSizeType();
3995  llvm::APInt Size(S.Context.getIntWidth(T), ILE->getNumInits());
3996  if (auto Result = DeduceNonTypeTemplateArgument(
3997  S, TemplateParams, NTTP, llvm::APSInt(Size), T,
3998  /*ArrayBound=*/true, Info, Deduced))
3999  return Result;
4000  }
4001  }
4002 
4003  return Sema::TDK_Success;
4004 }
4005 
4006 /// Perform template argument deduction per [temp.deduct.call] for a
4007 /// single parameter / argument pair.
4009  Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
4010  QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
4011  SmallVectorImpl<DeducedTemplateArgument> &Deduced,
4012  SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs,
4013  bool DecomposedParam, unsigned ArgIdx, unsigned TDF) {
4014  QualType ArgType = Arg->getType();
4015  QualType OrigParamType = ParamType;
4016 
4017  // If P is a reference type [...]
4018  // If P is a cv-qualified type [...]
4020  S, TemplateParams, FirstInnerIndex, ParamType, ArgType, Arg, TDF))
4021  return Sema::TDK_Success;
4022 
4023  // If [...] the argument is a non-empty initializer list [...]
4024  if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg))
4025  return DeduceFromInitializerList(S, TemplateParams, ParamType, ILE, Info,
4026  Deduced, OriginalCallArgs, ArgIdx, TDF);
4027 
4028  // [...] the deduction process attempts to find template argument values
4029  // that will make the deduced A identical to A
4030  //
4031  // Keep track of the argument type and corresponding parameter index,
4032  // so we can check for compatibility between the deduced A and A.
4033  OriginalCallArgs.push_back(
4034  Sema::OriginalCallArg(OrigParamType, DecomposedParam, ArgIdx, ArgType));
4035  return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
4036  ArgType, Info, Deduced, TDF);
4037 }
4038 
4039 /// Perform template argument deduction from a function call
4040 /// (C++ [temp.deduct.call]).
4041 ///
4042 /// \param FunctionTemplate the function template for which we are performing
4043 /// template argument deduction.
4044 ///
4045 /// \param ExplicitTemplateArgs the explicit template arguments provided
4046 /// for this call.
4047 ///
4048 /// \param Args the function call arguments
4049 ///
4050 /// \param Specialization if template argument deduction was successful,
4051 /// this will be set to the function template specialization produced by
4052 /// template argument deduction.
4053 ///
4054 /// \param Info the argument will be updated to provide additional information
4055 /// about template argument deduction.
4056 ///
4057 /// \param CheckNonDependent A callback to invoke to check conversions for
4058 /// non-dependent parameters, between deduction and substitution, per DR1391.
4059 /// If this returns true, substitution will be skipped and we return
4060 /// TDK_NonDependentConversionFailure. The callback is passed the parameter
4061 /// types (after substituting explicit template arguments).
4062 ///
4063 /// \returns the result of template argument deduction.
4065  FunctionTemplateDecl *FunctionTemplate,
4066  TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args,
4067  FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
4068  bool PartialOverloading,
4069  llvm::function_ref<bool(ArrayRef<QualType>)> CheckNonDependent) {
4070  if (FunctionTemplate->isInvalidDecl())
4071  return TDK_Invalid;
4072 
4073  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4074  unsigned NumParams = Function->getNumParams();
4075 
4076  unsigned FirstInnerIndex = getFirstInnerIndex(FunctionTemplate);
4077 
4078  // C++ [temp.deduct.call]p1:
4079  // Template argument deduction is done by comparing each function template
4080  // parameter type (call it P) with the type of the corresponding argument
4081  // of the call (call it A) as described below.
4082  if (Args.size() < Function->getMinRequiredArguments() && !PartialOverloading)
4083  return TDK_TooFewArguments;
4084  else if (TooManyArguments(NumParams, Args.size(), PartialOverloading)) {
4085  const auto *Proto = Function->getType()->castAs<FunctionProtoType>();
4086  if (Proto->isTemplateVariadic())
4087  /* Do nothing */;
4088  else if (!Proto->isVariadic())
4089  return TDK_TooManyArguments;
4090  }
4091 
4092  // The types of the parameters from which we will perform template argument
4093  // deduction.
4094  LocalInstantiationScope InstScope(*this);
4095  TemplateParameterList *TemplateParams
4096  = FunctionTemplate->getTemplateParameters();
4098  SmallVector<QualType, 8> ParamTypes;
4099  unsigned NumExplicitlySpecified = 0;
4100  if (ExplicitTemplateArgs) {
4101  TemplateDeductionResult Result;
4103  Result = SubstituteExplicitTemplateArguments(
4104  FunctionTemplate, *ExplicitTemplateArgs, Deduced, ParamTypes, nullptr,
4105  Info);
4106  });
4107  if (Result)
4108  return Result;
4109 
4110  NumExplicitlySpecified = Deduced.size();
4111  } else {
4112  // Just fill in the parameter types from the function declaration.
4113  for (unsigned I = 0; I != NumParams; ++I)
4114  ParamTypes.push_back(Function->getParamDecl(I)->getType());
4115  }
4116 
4117  SmallVector<OriginalCallArg, 8> OriginalCallArgs;
4118 
4119  // Deduce an argument of type ParamType from an expression with index ArgIdx.
4120  auto DeduceCallArgument = [&](QualType ParamType, unsigned ArgIdx) {
4121  // C++ [demp.deduct.call]p1: (DR1391)
4122  // Template argument deduction is done by comparing each function template
4123  // parameter that contains template-parameters that participate in
4124  // template argument deduction ...
4125  if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
4126  return Sema::TDK_Success;
4127 
4128  // ... with the type of the corresponding argument
4130  *this, TemplateParams, FirstInnerIndex, ParamType, Args[ArgIdx], Info, Deduced,
4131  OriginalCallArgs, /*Decomposed*/false, ArgIdx, /*TDF*/ 0);
4132  };
4133 
4134  // Deduce template arguments from the function parameters.
4135  Deduced.resize(TemplateParams->size());
4136  SmallVector<QualType, 8> ParamTypesForArgChecking;
4137  for (unsigned ParamIdx = 0, NumParamTypes = ParamTypes.size(), ArgIdx = 0;
4138  ParamIdx != NumParamTypes; ++ParamIdx) {
4139  QualType ParamType = ParamTypes[ParamIdx];
4140 
4141  const PackExpansionType *ParamExpansion =
4142  dyn_cast<PackExpansionType>(ParamType);
4143  if (!ParamExpansion) {
4144  // Simple case: matching a function parameter to a function argument.
4145  if (ArgIdx >= Args.size())
4146  break;
4147 
4148  ParamTypesForArgChecking.push_back(ParamType);
4149  if (auto Result = DeduceCallArgument(ParamType, ArgIdx++))
4150  return Result;
4151 
4152  continue;
4153  }
4154 
4155  QualType ParamPattern = ParamExpansion->getPattern();
4156  PackDeductionScope PackScope(*this, TemplateParams, Deduced, Info,
4157  ParamPattern);
4158 
4159  // C++0x [temp.deduct.call]p1:
4160  // For a function parameter pack that occurs at the end of the
4161  // parameter-declaration-list, the type A of each remaining argument of
4162  // the call is compared with the type P of the declarator-id of the
4163  // function parameter pack. Each comparison deduces template arguments
4164  // for subsequent positions in the template parameter packs expanded by
4165  // the function parameter pack. When a function parameter pack appears
4166  // in a non-deduced context [not at the end of the list], the type of
4167  // that parameter pack is never deduced.
4168  //
4169  // FIXME: The above rule allows the size of the parameter pack to change
4170  // after we skip it (in the non-deduced case). That makes no sense, so
4171  // we instead notionally deduce the pack against N arguments, where N is
4172  // the length of the explicitly-specified pack if it's expanded by the
4173  // parameter pack and 0 otherwise, and we treat each deduction as a
4174  // non-deduced context.
4175  if (ParamIdx + 1 == NumParamTypes || PackScope.hasFixedArity()) {
4176  for (; ArgIdx < Args.size() && PackScope.hasNextElement();
4177  PackScope.nextPackElement(), ++ArgIdx) {
4178  ParamTypesForArgChecking.push_back(ParamPattern);
4179  if (auto Result = DeduceCallArgument(ParamPattern, ArgIdx))
4180  return Result;
4181  }
4182  } else {
4183  // If the parameter type contains an explicitly-specified pack that we
4184  // could not expand, skip the number of parameters notionally created
4185  // by the expansion.
4186  Optional<unsigned> NumExpansions = ParamExpansion->getNumExpansions();
4187  if (NumExpansions && !PackScope.isPartiallyExpanded()) {
4188  for (unsigned I = 0; I != *NumExpansions && ArgIdx < Args.size();
4189  ++I, ++ArgIdx) {
4190  ParamTypesForArgChecking.push_back(ParamPattern);
4191  // FIXME: Should we add OriginalCallArgs for these? What if the
4192  // corresponding argument is a list?
4193  PackScope.nextPackElement();
4194  }
4195  }
4196  }
4197 
4198  // Build argument packs for each of the parameter packs expanded by this
4199  // pack expansion.
4200  if (auto Result = PackScope.finish())
4201  return Result;
4202  }
4203 
4204  // Capture the context in which the function call is made. This is the context
4205  // that is needed when the accessibility of template arguments is checked.
4206  DeclContext *CallingCtx = CurContext;
4207 
4208  TemplateDeductionResult Result;
4210  Result = FinishTemplateArgumentDeduction(
4211  FunctionTemplate, Deduced, NumExplicitlySpecified, Specialization, Info,
4212  &OriginalCallArgs, PartialOverloading, [&, CallingCtx]() {
4213  ContextRAII SavedContext(*this, CallingCtx);
4214  return CheckNonDependent(ParamTypesForArgChecking);
4215  });
4216  });
4217  return Result;
4218 }
4219 
4222  bool AdjustExceptionSpec) {
4223  if (ArgFunctionType.isNull())
4224  return ArgFunctionType;
4225 
4226  const auto *FunctionTypeP = FunctionType->castAs<FunctionProtoType>();
4227  const auto *ArgFunctionTypeP = ArgFunctionType->castAs<FunctionProtoType>();
4228  FunctionProtoType::ExtProtoInfo EPI = ArgFunctionTypeP->getExtProtoInfo();
4229  bool Rebuild = false;
4230 
4231  CallingConv CC = FunctionTypeP->getCallConv();
4232  if (EPI.ExtInfo.getCC() != CC) {
4233  EPI.ExtInfo = EPI.ExtInfo.withCallingConv(CC);
4234  Rebuild = true;
4235  }
4236 
4237  bool NoReturn = FunctionTypeP->getNoReturnAttr();
4238  if (EPI.ExtInfo.getNoReturn() != NoReturn) {
4239  EPI.ExtInfo = EPI.ExtInfo.withNoReturn(NoReturn);
4240  Rebuild = true;
4241  }
4242 
4243  if (AdjustExceptionSpec && (FunctionTypeP->hasExceptionSpec() ||
4244  ArgFunctionTypeP->hasExceptionSpec())) {
4245  EPI.ExceptionSpec = FunctionTypeP->getExtProtoInfo().ExceptionSpec;
4246  Rebuild = true;
4247  }
4248 
4249  if (!Rebuild)
4250  return ArgFunctionType;
4251 
4252  return Context.getFunctionType(ArgFunctionTypeP->getReturnType(),
4253  ArgFunctionTypeP->getParamTypes(), EPI);
4254 }
4255 
4256 /// Deduce template arguments when taking the address of a function
4257 /// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
4258 /// a template.
4259 ///
4260 /// \param FunctionTemplate the function template for which we are performing
4261 /// template argument deduction.
4262 ///
4263 /// \param ExplicitTemplateArgs the explicitly-specified template
4264 /// arguments.
4265 ///
4266 /// \param ArgFunctionType the function type that will be used as the
4267 /// "argument" type (A) when performing template argument deduction from the
4268 /// function template's function type. This type may be NULL, if there is no
4269 /// argument type to compare against, in C++0x [temp.arg.explicit]p3.
4270 ///
4271 /// \param Specialization if template argument deduction was successful,
4272 /// this will be set to the function template specialization produced by
4273 /// template argument deduction.
4274 ///
4275 /// \param Info the argument will be updated to provide additional information
4276 /// about template argument deduction.
4277 ///
4278 /// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4279 /// the address of a function template per [temp.deduct.funcaddr] and
4280 /// [over.over]. If \c false, we are looking up a function template
4281 /// specialization based on its signature, per [temp.deduct.decl].
4282 ///
4283 /// \returns the result of template argument deduction.
4285  FunctionTemplateDecl *FunctionTemplate,
4286  TemplateArgumentListInfo *ExplicitTemplateArgs, QualType ArgFunctionType,
4287  FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
4288  bool IsAddressOfFunction) {
4289  if (FunctionTemplate->isInvalidDecl())
4290  return TDK_Invalid;
4291 
4292  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4293  TemplateParameterList *TemplateParams
4294  = FunctionTemplate->getTemplateParameters();
4295  QualType FunctionType = Function->getType();
4296 
4297  // Substitute any explicit template arguments.
4298  LocalInstantiationScope InstScope(*this);
4300  unsigned NumExplicitlySpecified = 0;
4301  SmallVector<QualType, 4> ParamTypes;
4302  if (ExplicitTemplateArgs) {
4303  TemplateDeductionResult Result;
4305  Result = SubstituteExplicitTemplateArguments(
4306  FunctionTemplate, *ExplicitTemplateArgs, Deduced, ParamTypes,
4307  &FunctionType, Info);
4308  });
4309  if (Result)
4310  return Result;
4311 
4312  NumExplicitlySpecified = Deduced.size();
4313  }
4314 
4315  // When taking the address of a function, we require convertibility of
4316  // the resulting function type. Otherwise, we allow arbitrary mismatches
4317  // of calling convention and noreturn.
4318  if (!IsAddressOfFunction)
4319  ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, FunctionType,
4320  /*AdjustExceptionSpec*/false);
4321 
4322  // Unevaluated SFINAE context.
4325  SFINAETrap Trap(*this);
4326 
4327  Deduced.resize(TemplateParams->size());
4328 
4329  // If the function has a deduced return type, substitute it for a dependent
4330  // type so that we treat it as a non-deduced context in what follows. If we
4331  // are looking up by signature, the signature type should also have a deduced
4332  // return type, which we instead expect to exactly match.
4333  bool HasDeducedReturnType = false;
4334  if (getLangOpts().CPlusPlus14 && IsAddressOfFunction &&
4335  Function->getReturnType()->getContainedAutoType()) {
4337  HasDeducedReturnType = true;
4338  }
4339 
4340  if (!ArgFunctionType.isNull() && !FunctionType.isNull()) {
4341  unsigned TDF =
4343  // Deduce template arguments from the function type.
4344  if (TemplateDeductionResult Result
4345  = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
4346  FunctionType, ArgFunctionType,
4347  Info, Deduced, TDF))
4348  return Result;
4349  }
4350 
4351  TemplateDeductionResult Result;
4353  Result = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
4354  NumExplicitlySpecified,
4355  Specialization, Info);
4356  });
4357  if (Result)
4358  return Result;
4359 
4360  // If the function has a deduced return type, deduce it now, so we can check
4361  // that the deduced function type matches the requested type.
4362  if (HasDeducedReturnType &&
4363  Specialization->getReturnType()->isUndeducedType() &&
4366 
4367  // If the function has a dependent exception specification, resolve it now,
4368  // so we can check that the exception specification matches.
4369  auto *SpecializationFPT =
4370  Specialization->getType()->castAs<FunctionProtoType>();
4371  if (getLangOpts().CPlusPlus17 &&
4372  isUnresolvedExceptionSpec(SpecializationFPT->getExceptionSpecType()) &&
4373  !ResolveExceptionSpec(Info.getLocation(), SpecializationFPT))
4375 
4376  // Adjust the exception specification of the argument to match the
4377  // substituted and resolved type we just formed. (Calling convention and
4378  // noreturn can't be dependent, so we don't actually need this for them
4379  // right now.)
4380  QualType SpecializationType = Specialization->getType();
4381  if (!IsAddressOfFunction)
4382  ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, SpecializationType,
4383  /*AdjustExceptionSpec*/true);
4384 
4385  // If the requested function type does not match the actual type of the
4386  // specialization with respect to arguments of compatible pointer to function
4387  // types, template argument deduction fails.
4388  if (!ArgFunctionType.isNull()) {
4389  if (IsAddressOfFunction &&
4391  Context.getCanonicalType(SpecializationType),
4392  Context.getCanonicalType(ArgFunctionType)))
4394 
4395  if (!IsAddressOfFunction &&
4396  !Context.hasSameType(SpecializationType, ArgFunctionType))
4398  }
4399 
4400  return TDK_Success;
4401 }
4402 
4403 /// Deduce template arguments for a templated conversion
4404 /// function (C++ [temp.deduct.conv]) and, if successful, produce a
4405 /// conversion function template specialization.
4408  QualType ToType,
4409  CXXConversionDecl *&Specialization,
4410  TemplateDeductionInfo &Info) {
4411  if (ConversionTemplate->isInvalidDecl())
4412  return TDK_Invalid;
4413 
4414  CXXConversionDecl *ConversionGeneric
4415  = cast<CXXConversionDecl>(ConversionTemplate->getTemplatedDecl());
4416 
4417  QualType FromType = ConversionGeneric->getConversionType();
4418 
4419  // Canonicalize the types for deduction.
4420  QualType P = Context.getCanonicalType(FromType);
4421  QualType A = Context.getCanonicalType(ToType);
4422 
4423  // C++0x [temp.deduct.conv]p2:
4424  // If P is a reference type, the type referred to by P is used for
4425  // type deduction.
4426  if (const ReferenceType *PRef = P->getAs<ReferenceType>())
4427  P = PRef->getPointeeType();
4428 
4429  // C++0x [temp.deduct.conv]p4:
4430  // [...] If A is a reference type, the type referred to by A is used
4431  // for type deduction.
4432  if (const ReferenceType *ARef = A->getAs<ReferenceType>()) {
4433  A = ARef->getPointeeType();
4434  // We work around a defect in the standard here: cv-qualifiers are also
4435  // removed from P and A in this case, unless P was a reference type. This
4436  // seems to mostly match what other compilers are doing.
4437  if (!FromType->getAs<ReferenceType>()) {
4438  A = A.getUnqualifiedType();
4439  P = P.getUnqualifiedType();
4440  }
4441 
4442  // C++ [temp.deduct.conv]p3:
4443  //
4444  // If A is not a reference type:
4445  } else {
4446  assert(!A->isReferenceType() && "Reference types were handled above");
4447 
4448  // - If P is an array type, the pointer type produced by the
4449  // array-to-pointer standard conversion (4.2) is used in place
4450  // of P for type deduction; otherwise,
4451  if (P->isArrayType())
4453  // - If P is a function type, the pointer type produced by the
4454  // function-to-pointer standard conversion (4.3) is used in
4455  // place of P for type deduction; otherwise,
4456  else if (P->isFunctionType())
4458  // - If P is a cv-qualified type, the top level cv-qualifiers of
4459  // P's type are ignored for type deduction.
4460  else
4461  P = P.getUnqualifiedType();
4462 
4463  // C++0x [temp.deduct.conv]p4:
4464  // If A is a cv-qualified type, the top level cv-qualifiers of A's
4465  // type are ignored for type deduction. If A is a reference type, the type
4466  // referred to by A is used for type deduction.
4467  A = A.getUnqualifiedType();
4468  }
4469 
4470  // Unevaluated SFINAE context.
4473  SFINAETrap Trap(*this);
4474 
4475  // C++ [temp.deduct.conv]p1:
4476  // Template argument deduction is done by comparing the return
4477  // type of the template conversion function (call it P) with the
4478  // type that is required as the result of the conversion (call it
4479  // A) as described in 14.8.2.4.
4480  TemplateParameterList *TemplateParams
4481  = ConversionTemplate->getTemplateParameters();
4483  Deduced.resize(TemplateParams->size());
4484 
4485  // C++0x [temp.deduct.conv]p4:
4486  // In general, the deduction process attempts to find template
4487  // argument values that will make the deduced A identical to
4488  // A. However, there are two cases that allow a difference:
4489  unsigned TDF = 0;
4490  // - If the original A is a reference type, A can be more
4491  // cv-qualified than the deduced A (i.e., the type referred to
4492  // by the reference)
4493  if (ToType->isReferenceType())
4494  TDF |= TDF_ArgWithReferenceType;
4495  // - The deduced A can be another pointer or pointer to member
4496  // type that can be converted to A via a qualification
4497  // conversion.
4498  //
4499  // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
4500  // both P and A are pointers or member pointers. In this case, we
4501  // just ignore cv-qualifiers completely).
4502  if ((P->isPointerType() && A->isPointerType()) ||
4503  (P->isMemberPointerType() && A->isMemberPointerType()))
4504  TDF |= TDF_IgnoreQualifiers;
4505  if (TemplateDeductionResult Result
4506  = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
4507  P, A, Info, Deduced, TDF))
4508  return Result;
4509 
4510  // Create an Instantiation Scope for finalizing the operator.
4511  LocalInstantiationScope InstScope(*this);
4512  // Finish template argument deduction.
4513  FunctionDecl *ConversionSpecialized = nullptr;
4514  TemplateDeductionResult Result;
4516  Result = FinishTemplateArgumentDeduction(ConversionTemplate, Deduced, 0,
4517  ConversionSpecialized, Info);
4518  });
4519  Specialization = cast_or_null<CXXConversionDecl>(ConversionSpecialized);
4520  return Result;
4521 }
4522 
4523 /// Deduce template arguments for a function template when there is
4524 /// nothing to deduce against (C++0x [temp.arg.explicit]p3).
4525 ///
4526 /// \param FunctionTemplate the function template for which we are performing
4527 /// template argument deduction.
4528 ///
4529 /// \param ExplicitTemplateArgs the explicitly-specified template
4530 /// arguments.
4531 ///
4532 /// \param Specialization if template argument deduction was successful,
4533 /// this will be set to the function template specialization produced by
4534 /// template argument deduction.
4535 ///
4536 /// \param Info the argument will be updated to provide additional information
4537 /// about template argument deduction.
4538 ///
4539 /// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4540 /// the address of a function template in a context where we do not have a
4541 /// target type, per [over.over]. If \c false, we are looking up a function
4542 /// template specialization based on its signature, which only happens when
4543 /// deducing a function parameter type from an argument that is a template-id
4544 /// naming a function template specialization.
4545 ///
4546 /// \returns the result of template argument deduction.
4548  FunctionTemplateDecl *FunctionTemplate,
4549  TemplateArgumentListInfo *ExplicitTemplateArgs,
4550  FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
4551  bool IsAddressOfFunction) {
4552  return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
4553  QualType(), Specialization, Info,
4554  IsAddressOfFunction);
4555 }
4556 
4557 namespace {
4558  struct DependentAuto { bool IsPack; };
4559 
4560  /// Substitute the 'auto' specifier or deduced template specialization type
4561  /// specifier within a type for a given replacement type.
4562  class SubstituteDeducedTypeTransform :
4563  public TreeTransform<SubstituteDeducedTypeTransform> {
4564  QualType Replacement;
4565  bool ReplacementIsPack;
4566  bool UseTypeSugar;
4567 
4568  public:
4569  SubstituteDeducedTypeTransform(Sema &SemaRef, DependentAuto DA)
4570  : TreeTransform<SubstituteDeducedTypeTransform>(SemaRef),
4571  ReplacementIsPack(DA.IsPack), UseTypeSugar(true) {}
4572 
4573  SubstituteDeducedTypeTransform(Sema &SemaRef, QualType Replacement,
4574  bool UseTypeSugar = true)
4575  : TreeTransform<SubstituteDeducedTypeTransform>(SemaRef),
4576  Replacement(Replacement), ReplacementIsPack(false),
4577  UseTypeSugar(UseTypeSugar) {}
4578 
4579  QualType TransformDesugared(TypeLocBuilder &TLB, DeducedTypeLoc TL) {
4580  assert(isa<TemplateTypeParmType>(Replacement) &&
4581  "unexpected unsugared replacement kind");
4582  QualType Result = Replacement;
4584  NewTL.setNameLoc(TL.getNameLoc());
4585  return Result;
4586  }
4587 
4588  QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
4589  // If we're building the type pattern to deduce against, don't wrap the
4590  // substituted type in an AutoType. Certain template deduction rules
4591  // apply only when a template type parameter appears directly (and not if
4592  // the parameter is found through desugaring). For instance:
4593  // auto &&lref = lvalue;
4594  // must transform into "rvalue reference to T" not "rvalue reference to
4595  // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
4596  //
4597  // FIXME: Is this still necessary?
4598  if (!UseTypeSugar)
4599  return TransformDesugared(TLB, TL);
4600 
4601  QualType Result = SemaRef.Context.getAutoType(
4602  Replacement, TL.getTypePtr()->getKeyword(), Replacement.isNull(),
4603  ReplacementIsPack, TL.getTypePtr()->getTypeConstraintConcept(),
4605  auto NewTL = TLB.push<AutoTypeLoc>(Result);
4606  NewTL.copy(TL);
4607  return Result;
4608  }
4609 
4610  QualType TransformDeducedTemplateSpecializationType(
4612  if (!UseTypeSugar)
4613  return TransformDesugared(TLB, TL);
4614 
4615  QualType Result = SemaRef.Context.getDeducedTemplateSpecializationType(
4616  TL.getTypePtr()->getTemplateName(),
4617  Replacement, Replacement.isNull());
4618  auto NewTL = TLB.push<DeducedTemplateSpecializationTypeLoc>(Result);
4619  NewTL.setNameLoc(TL.getNameLoc());
4620  return Result;
4621  }
4622 
4623  ExprResult TransformLambdaExpr(LambdaExpr *E) {
4624  // Lambdas never need to be transformed.
4625  return E;
4626  }
4627 
4628  QualType Apply(TypeLoc TL) {
4629  // Create some scratch storage for the transformed type locations.
4630  // FIXME: We're just going to throw this information away. Don't build it.
4631  TypeLocBuilder TLB;
4632  TLB.reserve(TL.getFullDataSize());
4633  return TransformType(TLB, TL);
4634  }
4635  };
4636 
4637 } // namespace
4638 
4641  QualType Deduced) {
4642  ConstraintSatisfaction Satisfaction;
4643  ConceptDecl *Concept = Type.getTypeConstraintConcept();
4644  TemplateArgumentListInfo TemplateArgs(TypeLoc.getLAngleLoc(),
4645  TypeLoc.getRAngleLoc());
4646  TemplateArgs.addArgument(
4649  Deduced, TypeLoc.getNameLoc())));
4650  for (unsigned I = 0, C = TypeLoc.getNumArgs(); I != C; ++I)
4651  TemplateArgs.addArgument(TypeLoc.getArgLoc(I));
4652 
4653  llvm::SmallVector<TemplateArgument, 4> SugaredConverted, CanonicalConverted;
4654  if (S.CheckTemplateArgumentList(Concept, SourceLocation(), TemplateArgs,
4655  /*PartialTemplateArgs=*/false,
4656  SugaredConverted, CanonicalConverted))
4657  return true;
4658  MultiLevelTemplateArgumentList MLTAL(Concept, SugaredConverted,
4659  /*Final=*/true);
4660  if (S.CheckConstraintSatisfaction(Concept, {Concept->getConstraintExpr()},
4661  MLTAL, TypeLoc.getLocalSourceRange(),
4662  Satisfaction))
4663  return true;
4664  if (!Satisfaction.IsSatisfied) {
4665  std::string Buf;
4666  llvm::raw_string_ostream OS(Buf);
4667  OS << "'" << Concept->getName();
4668  if (TypeLoc.hasExplicitTemplateArgs()) {
4670  OS, Type.getTypeConstraintArguments(), S.getPrintingPolicy(),
4671  Type.getTypeConstraintConcept()->getTemplateParameters());
4672  }
4673  OS << "'";
4674  OS.flush();
4675  S.Diag(TypeLoc.getConceptNameLoc(),
4676  diag::err_placeholder_constraints_not_satisfied)
4677  << Deduced << Buf << TypeLoc.getLocalSourceRange();
4678  S.DiagnoseUnsatisfiedConstraint(Satisfaction);
4679  return true;
4680  }
4681  return false;
4682 }
4683 
4684 /// Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6)
4685 ///
4686 /// Note that this is done even if the initializer is dependent. (This is
4687 /// necessary to support partial ordering of templates using 'auto'.)
4688 /// A dependent type will be produced when deducing from a dependent type.
4689 ///
4690 /// \param Type the type pattern using the auto type-specifier.
4691 /// \param Init the initializer for the variable whose type is to be deduced.
4692 /// \param Result if type deduction was successful, this will be set to the
4693 /// deduced type.
4694 /// \param Info the argument will be updated to provide additional information
4695 /// about template argument deduction.
4696 /// \param DependentDeduction Set if we should permit deduction in
4697 /// dependent cases. This is necessary for template partial ordering with
4698 /// 'auto' template parameters. The template parameter depth to be used
4699 /// should be specified in the 'Info' parameter.
4700 /// \param IgnoreConstraints Set if we should not fail if the deduced type does
4701 /// not satisfy the type-constraint in the auto type.
4703  QualType &Result,
4704  TemplateDeductionInfo &Info,
4705  bool DependentDeduction,
4706  bool IgnoreConstraints) {
4707  assert(DependentDeduction || Info.getDeducedDepth() == 0);
4708  if (Init->containsErrors())
4709  return TDK_AlreadyDiagnosed;
4710 
4711  const AutoType *AT = Type.getType()->getContainedAutoType();
4712  assert(AT);
4713 
4714  if (Init->getType()->isNonOverloadPlaceholderType() || AT->isDecltypeAuto()) {
4715  ExprResult NonPlaceholder = CheckPlaceholderExpr(Init);
4716  if (NonPlaceholder.isInvalid())
4717  return TDK_AlreadyDiagnosed;
4718  Init = NonPlaceholder.get();
4719  }
4720 
4721  DependentAuto DependentResult = {
4722  /*.IsPack = */ (bool)Type.getAs<PackExpansionTypeLoc>()};
4723 
4724  if (!DependentDeduction &&
4725  (Type.getType()->isDependentType() || Init->isTypeDependent() ||
4726  Init->containsUnexpandedParameterPack())) {
4727  Result = SubstituteDeducedTypeTransform(*this, DependentResult).Apply(Type);
4728  assert(!Result.isNull() && "substituting DependentTy can't fail");
4729  return TDK_Success;
4730  }
4731 
4732  auto *InitList = dyn_cast<InitListExpr>(Init);
4733  if (!getLangOpts().CPlusPlus && InitList) {
4734  Diag(Init->getBeginLoc(), diag::err_auto_init_list_from_c);
4735  return TDK_AlreadyDiagnosed;
4736  }
4737 
4738  // Deduce type of TemplParam in Func(Init)
4740  Deduced.resize(1);
4741 
4742  // If deduction failed, don't diagnose if the initializer is dependent; it
4743  // might acquire a matching type in the instantiation.
4744  auto DeductionFailed = [&](TemplateDeductionResult TDK) {
4745  if (Init->isTypeDependent()) {
4746  Result =
4747  SubstituteDeducedTypeTransform(*this, DependentResult).Apply(Type);
4748  assert(!Result.isNull() && "substituting DependentTy can't fail");
4749  return TDK_Success;
4750  }
4751  return TDK;
4752  };
4753 
4754  SmallVector<OriginalCallArg, 4> OriginalCallArgs;
4755 
4757  // If this is a 'decltype(auto)' specifier, do the decltype dance.
4758  if (AT->isDecltypeAuto()) {
4759  if (InitList) {
4760  Diag(Init->getBeginLoc(), diag::err_decltype_auto_initializer_list);
4761  return TDK_AlreadyDiagnosed;
4762  }
4763 
4765  assert(!DeducedType.isNull());
4766  } else {
4767  LocalInstantiationScope InstScope(*this);
4768 
4769  // Build template<class TemplParam> void Func(FuncParam);
4770  SourceLocation Loc = Init->getExprLoc();
4772  Context, nullptr, SourceLocation(), Loc, Info.getDeducedDepth(), 0,
4773  nullptr, false, false, false);
4774  QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
4775  NamedDecl *TemplParamPtr = TemplParam;
4777  Context, Loc, Loc, TemplParamPtr, Loc, nullptr);
4778 
4779  if (InitList) {
4780  // Notionally, we substitute std::initializer_list<T> for 'auto' and
4781  // deduce against that. Such deduction only succeeds if removing
4782  // cv-qualifiers and references results in std::initializer_list<T>.
4783  if (!Type.getType().getNonReferenceType()->getAs<AutoType>())
4784  return TDK_Invalid;
4785 
4786  SourceRange DeducedFromInitRange;
4787  for (Expr *Init : InitList->inits()) {
4788  // Resolving a core issue: a braced-init-list containing any designators
4789  // is a non-deduced context.
4790  if (isa<DesignatedInitExpr>(Init))
4791  return TDK_Invalid;
4793  *this, TemplateParamsSt.get(), 0, TemplArg, Init, Info, Deduced,
4794  OriginalCallArgs, /*Decomposed=*/true,
4795  /*ArgIdx=*/0, /*TDF=*/0)) {
4796  if (TDK == TDK_Inconsistent) {
4797  Diag(Info.getLocation(), diag::err_auto_inconsistent_deduction)
4798  << Info.FirstArg << Info.SecondArg << DeducedFromInitRange
4799  << Init->getSourceRange();
4800  return DeductionFailed(TDK_AlreadyDiagnosed);
4801  }
4802  return DeductionFailed(TDK);
4803  }
4804 
4805  if (DeducedFromInitRange.isInvalid() &&
4806  Deduced[0].getKind() != TemplateArgument::Null)
4807  DeducedFromInitRange = Init->getSourceRange();
4808  }
4809  } else {
4810  if (!getLangOpts().CPlusPlus && Init->refersToBitField()) {
4811  Diag(Loc, diag::err_auto_bitfield);
4812  return TDK_AlreadyDiagnosed;
4813  }
4814  QualType FuncParam =
4815  SubstituteDeducedTypeTransform(*this, TemplArg).Apply(Type);
4816  assert(!FuncParam.isNull() &&
4817  "substituting template parameter for 'auto' failed");
4819  *this, TemplateParamsSt.get(), 0, FuncParam, Init, Info, Deduced,
4820  OriginalCallArgs, /*Decomposed=*/false, /*ArgIdx=*/0, /*TDF=*/0))
4821  return DeductionFailed(TDK);
4822  }
4823 
4824  // Could be null if somehow 'auto' appears in a non-deduced context.
4825  if (Deduced[0].getKind() != TemplateArgument::Type)
4826  return DeductionFailed(TDK_Incomplete);
4827  DeducedType = Deduced[0].getAsType();
4828 
4829  if (InitList) {
4831  if (DeducedType.isNull())
4832  return TDK_AlreadyDiagnosed;
4833  }
4834  }
4835 
4836  if (!Result.isNull()) {
4837  if (!Context.hasSameType(DeducedType, Result)) {
4838  Info.FirstArg = Result;
4839  Info.SecondArg = DeducedType;
4840  return DeductionFailed(TDK_Inconsistent);
4841  }
4843  }
4844 
4845  if (AT->isConstrained() && !IgnoreConstraints &&
4847  *this, *AT, Type.getContainedAutoTypeLoc(), DeducedType))
4848  return TDK_AlreadyDiagnosed;
4849 
4850  Result = SubstituteDeducedTypeTransform(*this, DeducedType).Apply(Type);
4851  if (Result.isNull())
4852  return TDK_AlreadyDiagnosed;
4853 
4854  // Check that the deduced argument type is compatible with the original
4855  // argument type per C++ [temp.deduct.call]p4.
4856  QualType DeducedA = InitList ? Deduced[0].getAsType() : Result;
4857  for (const OriginalCallArg &OriginalArg : OriginalCallArgs) {
4858  assert((bool)InitList == OriginalArg.DecomposedParam &&
4859  "decomposed non-init-list in auto deduction?");
4860  if (auto TDK =
4861  CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA)) {
4862  Result = QualType();
4863  return DeductionFailed(TDK);
4864  }
4865  }
4866 
4867  return TDK_Success;
4868 }
4869 
4871  QualType TypeToReplaceAuto) {
4872  assert(TypeToReplaceAuto != Context.DependentTy);
4873  return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto)
4874  .TransformType(TypeWithAuto);
4875 }
4876 
4878  QualType TypeToReplaceAuto) {
4879  assert(TypeToReplaceAuto != Context.DependentTy);
4880  return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto)
4881  .TransformType(TypeWithAuto);
4882 }
4883 
4885  return SubstituteDeducedTypeTransform(*this, DependentAuto{false})
4886  .TransformType(TypeWithAuto);
4887 }
4888 
4891  return SubstituteDeducedTypeTransform(*this, DependentAuto{false})
4892  .TransformType(TypeWithAuto);
4893 }
4894 
4896  QualType TypeToReplaceAuto) {
4897  return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto,
4898  /*UseTypeSugar*/ false)
4899  .TransformType(TypeWithAuto);
4900 }
4901 
4903  QualType TypeToReplaceAuto) {
4904  return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto,
4905  /*UseTypeSugar*/ false)
4906  .TransformType(TypeWithAuto);
4907 }
4908 
4910  if (isa<InitListExpr>(Init))
4911  Diag(VDecl->getLocation(),
4912  VDecl->isInitCapture()
4913  ? diag::err_init_capture_deduction_failure_from_init_list
4914  : diag::err_auto_var_deduction_failure_from_init_list)
4915  << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange();
4916  else
4917  Diag(VDecl->getLocation(),
4918  VDecl->isInitCapture() ? diag::err_init_capture_deduction_failure
4919  : diag::err_auto_var_deduction_failure)
4920  << VDecl->getDeclName() << VDecl->getType() << Init->getType()
4921  << Init->getSourceRange();
4922 }
4923 
4925  bool Diagnose) {
4926  assert(FD->getReturnType()->isUndeducedType());
4927 
4928  // For a lambda's conversion operator, deduce any 'auto' or 'decltype(auto)'
4929  // within the return type from the call operator's type.
4930  if (isLambdaConversionOperator(FD)) {
4931  CXXRecordDecl *Lambda = cast<CXXMethodDecl>(FD)->getParent();
4932  FunctionDecl *CallOp = Lambda->getLambdaCallOperator();
4933 
4934  // For a generic lambda, instantiate the call operator if needed.
4935  if (auto *Args = FD->getTemplateSpecializationArgs()) {
4937  CallOp->getDescribedFunctionTemplate(), Args, Loc);
4938  if (!CallOp || CallOp->isInvalidDecl())
4939  return true;
4940 
4941  // We might need to deduce the return type by instantiating the definition
4942  // of the operator() function.
4943  if (CallOp->getReturnType()->isUndeducedType()) {
4944  runWithSufficientStackSpace(Loc, [&] {
4945  InstantiateFunctionDefinition(Loc, CallOp);
4946  });
4947  }
4948  }
4949 
4950  if (CallOp->isInvalidDecl())
4951  return true;
4952  assert(!CallOp->getReturnType()->isUndeducedType() &&
4953  "failed to deduce lambda return type");
4954 
4955  // Build the new return type from scratch.
4956  CallingConv RetTyCC = FD->getReturnType()
4957  ->getPointeeType()
4958  ->castAs<FunctionType>()
4959  ->getCallConv();
4961  CallOp->getType()->castAs<FunctionProtoType>(), RetTyCC);
4962  if (FD->getReturnType()->getAs<PointerType>())
4963  RetType = Context.getPointerType(RetType);
4964  else {
4965  assert(FD->getReturnType()->getAs<BlockPointerType>());
4966  RetType = Context.getBlockPointerType(RetType);
4967  }
4969  return false;
4970  }
4971 
4972  if (FD->getTemplateInstantiationPattern()) {
4973  runWithSufficientStackSpace(Loc, [&] {
4975  });
4976  }
4977 
4978  bool StillUndeduced = FD->getReturnType()->isUndeducedType();
4979  if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) {
4980  Diag(Loc, diag::err_auto_fn_used_before_defined) << FD;
4981  Diag(FD->getLocation(), diag::note_callee_decl) << FD;
4982  }
4983 
4984  return StillUndeduced;
4985 }
4986 
4987 /// If this is a non-static member function,
4988 static void
4990  CXXMethodDecl *Method,
4991  SmallVectorImpl<QualType> &ArgTypes) {
4992  // C++11 [temp.func.order]p3:
4993  // [...] The new parameter is of type "reference to cv A," where cv are
4994  // the cv-qualifiers of the function template (if any) and A is
4995  // the class of which the function template is a member.
4996  //
4997  // The standard doesn't say explicitly, but we pick the appropriate kind of
4998  // reference type based on [over.match.funcs]p4.
4999  QualType ArgTy = Context.getTypeDeclType(Method->getParent());
5000  ArgTy = Context.getQualifiedType(ArgTy, Method->getMethodQualifiers());
5001  if (Method->getRefQualifier() == RQ_RValue)
5002  ArgTy = Context.getRValueReferenceType(ArgTy);
5003  else
5004  ArgTy = Context.getLValueReferenceType(ArgTy);
5005  ArgTypes.push_back(ArgTy);
5006 }
5007 
5008 /// Determine whether the function template \p FT1 is at least as
5009 /// specialized as \p FT2.
5011  SourceLocation Loc,
5012  FunctionTemplateDecl *FT1,
5013  FunctionTemplateDecl *FT2,
5015  unsigned NumCallArguments1,
5016  bool Reversed) {
5017  assert(!Reversed || TPOC == TPOC_Call);
5018 
5019  FunctionDecl *FD1 = FT1->getTemplatedDecl();
5020  FunctionDecl *FD2 = FT2->getTemplatedDecl();
5021  const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>();
5022  const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>();
5023 
5024  assert(Proto1 && Proto2 && "Function templates must have prototypes");
5025  TemplateParameterList *TemplateParams = FT2->getTemplateParameters();
5027  Deduced.resize(TemplateParams->size());
5028 
5029  // C++0x [temp.deduct.partial]p3:
5030  // The types used to determine the ordering depend on the context in which
5031  // the partial ordering is done:
5032  TemplateDeductionInfo Info(Loc);
5034  switch (TPOC) {
5035  case TPOC_Call: {
5036  // - In the context of a function call, the function parameter types are
5037  // used.
5038  CXXMethodDecl *Method1 = dyn_cast<CXXMethodDecl>(FD1);
5039  CXXMethodDecl *Method2 = dyn_cast<CXXMethodDecl>(FD2);
5040 
5041  // C++11 [temp.func.order]p3:
5042  // [...] If only one of the function templates is a non-static
5043  // member, that function template is considered to have a new
5044  // first parameter inserted in its function parameter list. The
5045  // new parameter is of type "reference to cv A," where cv are
5046  // the cv-qualifiers of the function template (if any) and A is
5047  // the class of which the function template is a member.
5048  //
5049  // Note that we interpret this to mean "if one of the function
5050  // templates is a non-static member and the other is a non-member";
5051  // otherwise, the ordering rules for static functions against non-static
5052  // functions don't make any sense.
5053  //
5054  // C++98/03 doesn't have this provision but we've extended DR532 to cover
5055  // it as wording was broken prior to it.
5057 
5058  unsigned NumComparedArguments = NumCallArguments1;
5059 
5060  if (!Method2 && Method1 && !Method1->isStatic()) {
5061  // Compare 'this' from Method1 against first parameter from Method2.
5062  AddImplicitObjectParameterType(S.Context, Method1, Args1);
5063  ++NumComparedArguments;
5064  } else if (!Method1 && Method2 && !Method2->isStatic()) {
5065  // Compare 'this' from Method2 against first parameter from Method1.
5066  AddImplicitObjectParameterType(S.Context, Method2, Args2);
5067  } else if (Method1 && Method2 && Reversed) {
5068  // Compare 'this' from Method1 against second parameter from Method2
5069  // and 'this' from Method2 against second parameter from Method1.
5070  AddImplicitObjectParameterType(S.Context, Method1, Args1);
5071  AddImplicitObjectParameterType(S.Context, Method2, Args2);
5072  ++NumComparedArguments;
5073  }
5074 
5075  Args1.insert(Args1.end(), Proto1->param_type_begin(),
5076  Proto1->param_type_end());
5077  Args2.insert(Args2.end(), Proto2->param_type_begin(),
5078  Proto2->param_type_end());
5079 
5080  // C++ [temp.func.order]p5:
5081  // The presence of unused ellipsis and default arguments has no effect on
5082  // the partial ordering of function templates.
5083  if (Args1.size() > NumComparedArguments)
5084  Args1.resize(NumComparedArguments);
5085  if (Args2.size() > NumComparedArguments)
5086  Args2.resize(NumComparedArguments);
5087  if (Reversed)
5088  std::reverse(Args2.begin(), Args2.end());
5089 
5090  if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(),
5091  Args1.data(), Args1.size(), Info, Deduced,
5092  TDF_None, /*PartialOrdering=*/true))
5093  return false;
5094 
5095  break;
5096  }
5097 
5098  case TPOC_Conversion:
5099  // - In the context of a call to a conversion operator, the return types
5100  // of the conversion function templates are used.
5102  S, TemplateParams, Proto2->getReturnType(), Proto1->getReturnType(),
5103  Info, Deduced, TDF_None,
5104  /*PartialOrdering=*/true))
5105  return false;
5106  break;
5107 
5108  case TPOC_Other:
5109  // - In other contexts (14.6.6.2) the function template's function type
5110  // is used.
5111  if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
5112  FD2->getType(), FD1->getType(),
5113  Info, Deduced, TDF_None,
5114  /*PartialOrdering=*/true))
5115  return false;
5116  break;
5117  }
5118 
5119  // C++0x [temp.deduct.partial]p11:
5120  // In most cases, all template parameters must have values in order for
5121  // deduction to succeed, but for partial ordering purposes a template
5122  // parameter may remain without a value provided it is not used in the
5123  // types being used for partial ordering. [ Note: a template parameter used
5124  // in a non-deduced context is considered used. -end note]
5125  unsigned ArgIdx = 0, NumArgs = Deduced.size();
5126  for (; ArgIdx != NumArgs; ++ArgIdx)
5127  if (Deduced[ArgIdx].isNull())
5128  break;
5129 
5130  // FIXME: We fail to implement [temp.deduct.type]p1 along this path. We need
5131  // to substitute the deduced arguments back into the template and check that
5132  // we get the right type.
5133 
5134  if (ArgIdx == NumArgs) {
5135  // All template arguments were deduced. FT1 is at least as specialized
5136  // as FT2.
5137  return true;
5138  }
5139 
5140  // Figure out which template parameters were used.
5141  llvm::SmallBitVector UsedParameters(TemplateParams->size());
5142  switch (TPOC) {
5143  case TPOC_Call:
5144  for (unsigned I = 0, N = Args2.size(); I != N; ++I)
5145  ::MarkUsedTemplateParameters(S.Context, Args2[I], false,
5146  TemplateParams->getDepth(),
5147  UsedParameters);
5148  break;
5149 
5150  case TPOC_Conversion:
5151  ::MarkUsedTemplateParameters(S.Context, Proto2->getReturnType(), false,
5152  TemplateParams->getDepth(), UsedParameters);
5153  break;
5154 
5155  case TPOC_Other:
5156  ::MarkUsedTemplateParameters(S.Context, FD2->getType(), false,
5157  TemplateParams->getDepth(),
5158  UsedParameters);
5159  break;
5160  }
5161 
5162  for (; ArgIdx != NumArgs; ++ArgIdx)
5163  // If this argument had no value deduced but was used in one of the types
5164  // used for partial ordering, then deduction fails.
5165  if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
5166  return false;
5167 
5168  return true;
5169 }
5170 
5171 /// Returns the more specialized function template according
5172 /// to the rules of function template partial ordering (C++ [temp.func.order]).
5173 ///
5174 /// \param FT1 the first function template
5175 ///
5176 /// \param FT2 the second function template
5177 ///
5178 /// \param TPOC the context in which we are performing partial ordering of
5179 /// function templates.
5180 ///
5181 /// \param NumCallArguments1 The number of arguments in the call to FT1, used
5182 /// only when \c TPOC is \c TPOC_Call.
5183 ///
5184 /// \param NumCallArguments2 The number of arguments in the call to FT2, used
5185 /// only when \c TPOC is \c TPOC_Call.
5186 ///
5187 /// \param Reversed If \c true, exactly one of FT1 and FT2 is an overload
5188 /// candidate with a reversed parameter order. In this case, the corresponding
5189 /// P/A pairs between FT1 and FT2 are reversed.
5190 ///
5191 /// \returns the more specialized function template. If neither
5192 /// template is more specialized, returns NULL.
5195  TemplatePartialOrderingContext TPOC, unsigned NumCallArguments1,
5196  unsigned NumCallArguments2, bool Reversed) {
5197 
5198  bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
5199  NumCallArguments1, Reversed);
5200  bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
5201  NumCallArguments2, Reversed);
5202 
5203  // C++ [temp.deduct.partial]p10:
5204  // F is more specialized than G if F is at least as specialized as G and G
5205  // is not at least as specialized as F.
5206  if (Better1 != Better2) // We have a clear winner
5207  return Better1 ? FT1 : FT2;
5208 
5209  if (!Better1 && !Better2) // Neither is better than the other
5210  return nullptr;
5211 
5212  // C++ [temp.deduct.partial]p11:
5213  // ... and if G has a trailing function parameter pack for which F does not
5214  // have a corresponding parameter, and if F does not have a trailing
5215  // function parameter pack, then F is more specialized than G.
5216  FunctionDecl *FD1 = FT1->getTemplatedDecl();
5217  FunctionDecl *FD2 = FT2->getTemplatedDecl();
5218  unsigned NumParams1 = FD1->getNumParams();
5219  unsigned NumParams2 = FD2->getNumParams();
5220  bool Variadic1 = NumParams1 && FD1->parameters().back()->isParameterPack();
5221  bool Variadic2 = NumParams2 && FD2->parameters().back()->isParameterPack();
5222  if (Variadic1 != Variadic2) {
5223  if (Variadic1 && NumParams1 > NumParams2)
5224  return FT2;
5225  if (Variadic2 && NumParams2 > NumParams1)
5226  return FT1;
5227  }
5228 
5229  // This a speculative fix for CWG1432 (Similar to the fix for CWG1395) that
5230  // there is no wording or even resolution for this issue.
5231  for (int i = 0, e = std::min(NumParams1, NumParams2); i < e; ++i) {
5232  QualType T1 = FD1->getParamDecl(i)->getType().getCanonicalType();
5233  QualType T2 = FD2->getParamDecl(i)->getType().getCanonicalType();
5234  auto *TST1 = dyn_cast<TemplateSpecializationType>(T1);
5235  auto *TST2 = dyn_cast<TemplateSpecializationType>(T2);
5236  if (!TST1 || !TST2)
5237  continue;
5238  const TemplateArgument &TA1 = TST1->template_arguments().back();
5239  if (TA1.getKind() == TemplateArgument::Pack) {
5240  assert(TST1->template_arguments().size() ==
5241  TST2->template_arguments().size());
5242  const TemplateArgument &TA2 = TST2->template_arguments().back();
5243  assert(TA2.getKind() == TemplateArgument::Pack);
5244  unsigned PackSize1 = TA1.pack_size();
5245  unsigned PackSize2 = TA2.pack_size();
5246  bool IsPackExpansion1 =
5247  PackSize1 && TA1.pack_elements().back().isPackExpansion();
5248  bool IsPackExpansion2 =
5249  PackSize2 && TA2.pack_elements().back().isPackExpansion();
5250  if (PackSize1 != PackSize2 && IsPackExpansion1 != IsPackExpansion2) {
5251  if (PackSize1 > PackSize2 && IsPackExpansion1)
5252  return FT2;
5253  if (PackSize1 < PackSize2 && IsPackExpansion2)
5254  return FT1;
5255  }
5256  }
5257  }
5258 
5259  if (!Context.getLangOpts().CPlusPlus20)
5260  return nullptr;
5261 
5262  // Match GCC on not implementing [temp.func.order]p6.2.1.
5263 
5264  // C++20 [temp.func.order]p6:
5265  // If deduction against the other template succeeds for both transformed
5266  // templates, constraints can be considered as follows:
5267 
5268  // C++20 [temp.func.order]p6.1:
5269  // If their template-parameter-lists (possibly including template-parameters
5270  // invented for an abbreviated function template ([dcl.fct])) or function
5271  // parameter lists differ in length, neither template is more specialized
5272  // than the other.
5275  if (TPL1->size() != TPL2->size() || NumParams1 != NumParams2)
5276  return nullptr;
5277 
5278  // C++20 [temp.func.order]p6.2.2:
5279  // Otherwise, if the corresponding template-parameters of the
5280  // template-parameter-lists are not equivalent ([temp.over.link]) or if the
5281  // function parameters that positionally correspond between the two
5282  // templates are not of the same type, neither template is more specialized
5283  // than the other.
5285  TPL1, TPL2, false, Sema::TPL_TemplateMatch, SourceLocation(), true))
5286  return nullptr;
5287 
5288  for (unsigned i = 0; i < NumParams1; ++i)
5289  if (!Context.hasSameType(FD1->getParamDecl(i)->getType(),
5290  FD2->getParamDecl(i)->getType()))
5291  return nullptr;
5292 
5293  // C++20 [temp.func.order]p6.3:
5294  // Otherwise, if the context in which the partial ordering is done is
5295  // that of a call to a conversion function and the return types of the
5296  // templates are not the same, then neither template is more specialized
5297  // than the other.
5298  if (TPOC == TPOC_Conversion &&
5300  return nullptr;
5301 
5303  FT1->getAssociatedConstraints(AC1);
5304  FT2->getAssociatedConstraints(AC2);
5305  bool AtLeastAsConstrained1, AtLeastAsConstrained2;
5306  if (IsAtLeastAsConstrained(FT1, AC1, FT2, AC2, AtLeastAsConstrained1))
5307  return nullptr;
5308  if (IsAtLeastAsConstrained(FT2, AC2, FT1, AC1, AtLeastAsConstrained2))
5309  return nullptr;
5310  if (AtLeastAsConstrained1 == AtLeastAsConstrained2)
5311  return nullptr;
5312  return AtLeastAsConstrained1 ? FT1 : FT2;
5313 }
5314 
5315 /// Determine if the two templates are equivalent.
5317  if (T1 == T2)
5318  return true;
5319 
5320  if (!T1 || !T2)
5321  return false;
5322 
5323  return T1->getCanonicalDecl() == T2->getCanonicalDecl();
5324 }
5325 
5326 /// Retrieve the most specialized of the given function template
5327 /// specializations.
5328 ///
5329 /// \param SpecBegin the start iterator of the function template
5330 /// specializations that we will be comparing.
5331 ///
5332 /// \param SpecEnd the end iterator of the function template
5333 /// specializations, paired with \p SpecBegin.
5334 ///
5335 /// \param Loc the location where the ambiguity or no-specializations
5336 /// diagnostic should occur.
5337 ///
5338 /// \param NoneDiag partial diagnostic used to diagnose cases where there are
5339 /// no matching candidates.
5340 ///
5341 /// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one
5342 /// occurs.
5343 ///
5344 /// \param CandidateDiag partial diagnostic used for each function template
5345 /// specialization that is a candidate in the ambiguous ordering. One parameter
5346 /// in this diagnostic should be unbound, which will correspond to the string
5347 /// describing the template arguments for the function template specialization.
5348 ///
5349 /// \returns the most specialized function template specialization, if
5350 /// found. Otherwise, returns SpecEnd.
5352  UnresolvedSetIterator SpecBegin, UnresolvedSetIterator SpecEnd,
5353  TemplateSpecCandidateSet &FailedCandidates,
5354  SourceLocation Loc, const PartialDiagnostic &NoneDiag,
5355  const PartialDiagnostic &AmbigDiag, const PartialDiagnostic &CandidateDiag,
5356  bool Complain, QualType TargetType) {
5357  if (SpecBegin == SpecEnd) {
5358  if (Complain) {
5359  Diag(Loc, NoneDiag);
5360  FailedCandidates.NoteCandidates(*this, Loc);
5361  }
5362  return SpecEnd;
5363  }
5364 
5365  if (SpecBegin + 1 == SpecEnd)
5366  return SpecBegin;
5367 
5368  // Find the function template that is better than all of the templates it
5369  // has been compared to.
5370  UnresolvedSetIterator Best = SpecBegin;
5371  FunctionTemplateDecl *BestTemplate
5372  = cast<FunctionDecl>(*Best)->getPrimaryTemplate();
5373  assert(BestTemplate && "Not a function template specialization?");
5374  for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) {
5375  FunctionTemplateDecl *Challenger
5376  = cast<FunctionDecl>(*I)->getPrimaryTemplate();
5377  assert(Challenger && "Not a function template specialization?");
5378  if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
5379  Loc, TPOC_Other, 0, 0),
5380  Challenger)) {
5381  Best = I;
5382  BestTemplate = Challenger;
5383  }
5384  }
5385 
5386  // Make sure that the "best" function template is more specialized than all
5387  // of the others.
5388  bool Ambiguous = false;
5389  for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
5390  FunctionTemplateDecl *Challenger
5391  = cast<FunctionDecl>(*I)->getPrimaryTemplate();
5392  if (I != Best &&
5393  !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
5394  Loc, TPOC_Other, 0, 0),
5395  BestTemplate)) {
5396  Ambiguous = true;
5397  break;
5398  }
5399  }
5400 
5401  if (!Ambiguous) {
5402  // We found an answer. Return it.
5403  return Best;
5404  }
5405 
5406  // Diagnose the ambiguity.
5407  if (Complain) {
5408