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