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