contrib/llvm/tools/clang/lib/Sema/SemaTemplateDeduction.cpp

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