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

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