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