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