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