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