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