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