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

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