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