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(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.RequireCompleteType(Info.getLocation(), Arg, 0))
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       if (Sema::TemplateDeductionResult Result
1521             = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1522                                                  MemPtrParam->getPointeeType(),
1523                                                  MemPtrArg->getPointeeType(),
1524                                                  Info, Deduced,
1525                                                  TDF & TDF_IgnoreQualifiers))
1526         return Result;
1527
1528       return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1529                                            QualType(MemPtrParam->getClass(), 0),
1530                                            QualType(MemPtrArg->getClass(), 0),
1531                                            Info, Deduced,
1532                                            TDF & TDF_IgnoreQualifiers);
1533     }
1534
1535     //     (clang extension)
1536     //
1537     //     type(^)(T)
1538     //     T(^)()
1539     //     T(^)(T)
1540     case Type::BlockPointer: {
1541       const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
1542       const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
1543
1544       if (!BlockPtrArg)
1545         return Sema::TDK_NonDeducedMismatch;
1546
1547       return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1548                                                 BlockPtrParam->getPointeeType(),
1549                                                 BlockPtrArg->getPointeeType(),
1550                                                 Info, Deduced, 0);
1551     }
1552
1553     //     (clang extension)
1554     //
1555     //     T __attribute__(((ext_vector_type(<integral constant>))))
1556     case Type::ExtVector: {
1557       const ExtVectorType *VectorParam = cast<ExtVectorType>(Param);
1558       if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1559         // Make sure that the vectors have the same number of elements.
1560         if (VectorParam->getNumElements() != VectorArg->getNumElements())
1561           return Sema::TDK_NonDeducedMismatch;
1562
1563         // Perform deduction on the element types.
1564         return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1565                                                   VectorParam->getElementType(),
1566                                                   VectorArg->getElementType(),
1567                                                   Info, Deduced, TDF);
1568       }
1569
1570       if (const DependentSizedExtVectorType *VectorArg
1571                                 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1572         // We can't check the number of elements, since the argument has a
1573         // dependent number of elements. This can only occur during partial
1574         // ordering.
1575
1576         // Perform deduction on the element types.
1577         return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1578                                                   VectorParam->getElementType(),
1579                                                   VectorArg->getElementType(),
1580                                                   Info, Deduced, TDF);
1581       }
1582
1583       return Sema::TDK_NonDeducedMismatch;
1584     }
1585
1586     //     (clang extension)
1587     //
1588     //     T __attribute__(((ext_vector_type(N))))
1589     case Type::DependentSizedExtVector: {
1590       const DependentSizedExtVectorType *VectorParam
1591         = cast<DependentSizedExtVectorType>(Param);
1592
1593       if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1594         // Perform deduction on the element types.
1595         if (Sema::TemplateDeductionResult Result
1596               = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1597                                                   VectorParam->getElementType(),
1598                                                    VectorArg->getElementType(),
1599                                                    Info, Deduced, TDF))
1600           return Result;
1601
1602         // Perform deduction on the vector size, if we can.
1603         NonTypeTemplateParmDecl *NTTP
1604           = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1605         if (!NTTP)
1606           return Sema::TDK_Success;
1607
1608         llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1609         ArgSize = VectorArg->getNumElements();
1610         return DeduceNonTypeTemplateArgument(S, NTTP, ArgSize, S.Context.IntTy,
1611                                              false, Info, Deduced);
1612       }
1613
1614       if (const DependentSizedExtVectorType *VectorArg
1615                                 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1616         // Perform deduction on the element types.
1617         if (Sema::TemplateDeductionResult Result
1618             = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1619                                                  VectorParam->getElementType(),
1620                                                  VectorArg->getElementType(),
1621                                                  Info, Deduced, TDF))
1622           return Result;
1623
1624         // Perform deduction on the vector size, if we can.
1625         NonTypeTemplateParmDecl *NTTP
1626           = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1627         if (!NTTP)
1628           return Sema::TDK_Success;
1629
1630         return DeduceNonTypeTemplateArgument(S, NTTP, VectorArg->getSizeExpr(),
1631                                              Info, Deduced);
1632       }
1633
1634       return Sema::TDK_NonDeducedMismatch;
1635     }
1636
1637     case Type::TypeOfExpr:
1638     case Type::TypeOf:
1639     case Type::DependentName:
1640     case Type::UnresolvedUsing:
1641     case Type::Decltype:
1642     case Type::UnaryTransform:
1643     case Type::Auto:
1644     case Type::DependentTemplateSpecialization:
1645     case Type::PackExpansion:
1646       // No template argument deduction for these types
1647       return Sema::TDK_Success;
1648   }
1649
1650   llvm_unreachable("Invalid Type Class!");
1651 }
1652
1653 static Sema::TemplateDeductionResult
1654 DeduceTemplateArguments(Sema &S,
1655                         TemplateParameterList *TemplateParams,
1656                         const TemplateArgument &Param,
1657                         TemplateArgument Arg,
1658                         TemplateDeductionInfo &Info,
1659                         SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1660   // If the template argument is a pack expansion, perform template argument
1661   // deduction against the pattern of that expansion. This only occurs during
1662   // partial ordering.
1663   if (Arg.isPackExpansion())
1664     Arg = Arg.getPackExpansionPattern();
1665
1666   switch (Param.getKind()) {
1667   case TemplateArgument::Null:
1668     llvm_unreachable("Null template argument in parameter list");
1669
1670   case TemplateArgument::Type:
1671     if (Arg.getKind() == TemplateArgument::Type)
1672       return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1673                                                 Param.getAsType(),
1674                                                 Arg.getAsType(),
1675                                                 Info, Deduced, 0);
1676     Info.FirstArg = Param;
1677     Info.SecondArg = Arg;
1678     return Sema::TDK_NonDeducedMismatch;
1679
1680   case TemplateArgument::Template:
1681     if (Arg.getKind() == TemplateArgument::Template)
1682       return DeduceTemplateArguments(S, TemplateParams,
1683                                      Param.getAsTemplate(),
1684                                      Arg.getAsTemplate(), Info, Deduced);
1685     Info.FirstArg = Param;
1686     Info.SecondArg = Arg;
1687     return Sema::TDK_NonDeducedMismatch;
1688
1689   case TemplateArgument::TemplateExpansion:
1690     llvm_unreachable("caller should handle pack expansions");
1691
1692   case TemplateArgument::Declaration:
1693     if (Arg.getKind() == TemplateArgument::Declaration &&
1694         isSameDeclaration(Param.getAsDecl(), Arg.getAsDecl()))
1695       return Sema::TDK_Success;
1696
1697     Info.FirstArg = Param;
1698     Info.SecondArg = Arg;
1699     return Sema::TDK_NonDeducedMismatch;
1700
1701   case TemplateArgument::NullPtr:
1702     if (Arg.getKind() == TemplateArgument::NullPtr &&
1703         S.Context.hasSameType(Param.getNullPtrType(), Arg.getNullPtrType()))
1704       return Sema::TDK_Success;
1705
1706     Info.FirstArg = Param;
1707     Info.SecondArg = Arg;
1708     return Sema::TDK_NonDeducedMismatch;
1709
1710   case TemplateArgument::Integral:
1711     if (Arg.getKind() == TemplateArgument::Integral) {
1712       if (hasSameExtendedValue(Param.getAsIntegral(), Arg.getAsIntegral()))
1713         return Sema::TDK_Success;
1714
1715       Info.FirstArg = Param;
1716       Info.SecondArg = Arg;
1717       return Sema::TDK_NonDeducedMismatch;
1718     }
1719
1720     if (Arg.getKind() == TemplateArgument::Expression) {
1721       Info.FirstArg = Param;
1722       Info.SecondArg = Arg;
1723       return Sema::TDK_NonDeducedMismatch;
1724     }
1725
1726     Info.FirstArg = Param;
1727     Info.SecondArg = Arg;
1728     return Sema::TDK_NonDeducedMismatch;
1729
1730   case TemplateArgument::Expression: {
1731     if (NonTypeTemplateParmDecl *NTTP
1732           = getDeducedParameterFromExpr(Param.getAsExpr())) {
1733       if (Arg.getKind() == TemplateArgument::Integral)
1734         return DeduceNonTypeTemplateArgument(S, NTTP,
1735                                              Arg.getAsIntegral(),
1736                                              Arg.getIntegralType(),
1737                                              /*ArrayBound=*/false,
1738                                              Info, Deduced);
1739       if (Arg.getKind() == TemplateArgument::Expression)
1740         return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(),
1741                                              Info, Deduced);
1742       if (Arg.getKind() == TemplateArgument::Declaration)
1743         return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(),
1744                                              Info, Deduced);
1745
1746       Info.FirstArg = Param;
1747       Info.SecondArg = Arg;
1748       return Sema::TDK_NonDeducedMismatch;
1749     }
1750
1751     // Can't deduce anything, but that's okay.
1752     return Sema::TDK_Success;
1753   }
1754   case TemplateArgument::Pack:
1755     llvm_unreachable("Argument packs should be expanded by the caller!");
1756   }
1757
1758   llvm_unreachable("Invalid TemplateArgument Kind!");
1759 }
1760
1761 /// \brief Determine whether there is a template argument to be used for
1762 /// deduction.
1763 ///
1764 /// This routine "expands" argument packs in-place, overriding its input
1765 /// parameters so that \c Args[ArgIdx] will be the available template argument.
1766 ///
1767 /// \returns true if there is another template argument (which will be at
1768 /// \c Args[ArgIdx]), false otherwise.
1769 static bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args,
1770                                             unsigned &ArgIdx,
1771                                             unsigned &NumArgs) {
1772   if (ArgIdx == NumArgs)
1773     return false;
1774
1775   const TemplateArgument &Arg = Args[ArgIdx];
1776   if (Arg.getKind() != TemplateArgument::Pack)
1777     return true;
1778
1779   assert(ArgIdx == NumArgs - 1 && "Pack not at the end of argument list?");
1780   Args = Arg.pack_begin();
1781   NumArgs = Arg.pack_size();
1782   ArgIdx = 0;
1783   return ArgIdx < NumArgs;
1784 }
1785
1786 /// \brief Determine whether the given set of template arguments has a pack
1787 /// expansion that is not the last template argument.
1788 static bool hasPackExpansionBeforeEnd(const TemplateArgument *Args,
1789                                       unsigned NumArgs) {
1790   unsigned ArgIdx = 0;
1791   while (ArgIdx < NumArgs) {
1792     const TemplateArgument &Arg = Args[ArgIdx];
1793
1794     // Unwrap argument packs.
1795     if (Args[ArgIdx].getKind() == TemplateArgument::Pack) {
1796       Args = Arg.pack_begin();
1797       NumArgs = Arg.pack_size();
1798       ArgIdx = 0;
1799       continue;
1800     }
1801
1802     ++ArgIdx;
1803     if (ArgIdx == NumArgs)
1804       return false;
1805
1806     if (Arg.isPackExpansion())
1807       return true;
1808   }
1809
1810   return false;
1811 }
1812
1813 static Sema::TemplateDeductionResult
1814 DeduceTemplateArguments(Sema &S,
1815                         TemplateParameterList *TemplateParams,
1816                         const TemplateArgument *Params, unsigned NumParams,
1817                         const TemplateArgument *Args, unsigned NumArgs,
1818                         TemplateDeductionInfo &Info,
1819                         SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1820   // C++0x [temp.deduct.type]p9:
1821   //   If the template argument list of P contains a pack expansion that is not
1822   //   the last template argument, the entire template argument list is a
1823   //   non-deduced context.
1824   if (hasPackExpansionBeforeEnd(Params, NumParams))
1825     return Sema::TDK_Success;
1826
1827   // C++0x [temp.deduct.type]p9:
1828   //   If P has a form that contains <T> or <i>, then each argument Pi of the
1829   //   respective template argument list P is compared with the corresponding
1830   //   argument Ai of the corresponding template argument list of A.
1831   unsigned ArgIdx = 0, ParamIdx = 0;
1832   for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams);
1833        ++ParamIdx) {
1834     if (!Params[ParamIdx].isPackExpansion()) {
1835       // The simple case: deduce template arguments by matching Pi and Ai.
1836
1837       // Check whether we have enough arguments.
1838       if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
1839         return Sema::TDK_Success;
1840
1841       if (Args[ArgIdx].isPackExpansion()) {
1842         // FIXME: We follow the logic of C++0x [temp.deduct.type]p22 here,
1843         // but applied to pack expansions that are template arguments.
1844         return Sema::TDK_MiscellaneousDeductionFailure;
1845       }
1846
1847       // Perform deduction for this Pi/Ai pair.
1848       if (Sema::TemplateDeductionResult Result
1849             = DeduceTemplateArguments(S, TemplateParams,
1850                                       Params[ParamIdx], Args[ArgIdx],
1851                                       Info, Deduced))
1852         return Result;
1853
1854       // Move to the next argument.
1855       ++ArgIdx;
1856       continue;
1857     }
1858
1859     // The parameter is a pack expansion.
1860
1861     // C++0x [temp.deduct.type]p9:
1862     //   If Pi is a pack expansion, then the pattern of Pi is compared with
1863     //   each remaining argument in the template argument list of A. Each
1864     //   comparison deduces template arguments for subsequent positions in the
1865     //   template parameter packs expanded by Pi.
1866     TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
1867
1868     // FIXME: If there are no remaining arguments, we can bail out early
1869     // and set any deduced parameter packs to an empty argument pack.
1870     // The latter part of this is a (minor) correctness issue.
1871
1872     // Prepare to deduce the packs within the pattern.
1873     PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
1874
1875     // Keep track of the deduced template arguments for each parameter pack
1876     // expanded by this pack expansion (the outer index) and for each
1877     // template argument (the inner SmallVectors).
1878     bool HasAnyArguments = false;
1879     for (; hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs); ++ArgIdx) {
1880       HasAnyArguments = true;
1881
1882       // Deduce template arguments from the pattern.
1883       if (Sema::TemplateDeductionResult Result
1884             = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
1885                                       Info, Deduced))
1886         return Result;
1887
1888       PackScope.nextPackElement();
1889     }
1890
1891     // Build argument packs for each of the parameter packs expanded by this
1892     // pack expansion.
1893     if (auto Result = PackScope.finish(HasAnyArguments))
1894       return Result;
1895   }
1896
1897   return Sema::TDK_Success;
1898 }
1899
1900 static Sema::TemplateDeductionResult
1901 DeduceTemplateArguments(Sema &S,
1902                         TemplateParameterList *TemplateParams,
1903                         const TemplateArgumentList &ParamList,
1904                         const TemplateArgumentList &ArgList,
1905                         TemplateDeductionInfo &Info,
1906                         SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1907   return DeduceTemplateArguments(S, TemplateParams,
1908                                  ParamList.data(), ParamList.size(),
1909                                  ArgList.data(), ArgList.size(),
1910                                  Info, Deduced);
1911 }
1912
1913 /// \brief Determine whether two template arguments are the same.
1914 static bool isSameTemplateArg(ASTContext &Context,
1915                               const TemplateArgument &X,
1916                               const TemplateArgument &Y) {
1917   if (X.getKind() != Y.getKind())
1918     return false;
1919
1920   switch (X.getKind()) {
1921     case TemplateArgument::Null:
1922       llvm_unreachable("Comparing NULL template argument");
1923
1924     case TemplateArgument::Type:
1925       return Context.getCanonicalType(X.getAsType()) ==
1926              Context.getCanonicalType(Y.getAsType());
1927
1928     case TemplateArgument::Declaration:
1929       return isSameDeclaration(X.getAsDecl(), Y.getAsDecl());
1930
1931     case TemplateArgument::NullPtr:
1932       return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
1933
1934     case TemplateArgument::Template:
1935     case TemplateArgument::TemplateExpansion:
1936       return Context.getCanonicalTemplateName(
1937                     X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
1938              Context.getCanonicalTemplateName(
1939                     Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
1940
1941     case TemplateArgument::Integral:
1942       return X.getAsIntegral() == Y.getAsIntegral();
1943
1944     case TemplateArgument::Expression: {
1945       llvm::FoldingSetNodeID XID, YID;
1946       X.getAsExpr()->Profile(XID, Context, true);
1947       Y.getAsExpr()->Profile(YID, Context, true);
1948       return XID == YID;
1949     }
1950
1951     case TemplateArgument::Pack:
1952       if (X.pack_size() != Y.pack_size())
1953         return false;
1954
1955       for (TemplateArgument::pack_iterator XP = X.pack_begin(),
1956                                         XPEnd = X.pack_end(),
1957                                            YP = Y.pack_begin();
1958            XP != XPEnd; ++XP, ++YP)
1959         if (!isSameTemplateArg(Context, *XP, *YP))
1960           return false;
1961
1962       return true;
1963   }
1964
1965   llvm_unreachable("Invalid TemplateArgument Kind!");
1966 }
1967
1968 /// \brief Allocate a TemplateArgumentLoc where all locations have
1969 /// been initialized to the given location.
1970 ///
1971 /// \param S The semantic analysis object.
1972 ///
1973 /// \param Arg The template argument we are producing template argument
1974 /// location information for.
1975 ///
1976 /// \param NTTPType For a declaration template argument, the type of
1977 /// the non-type template parameter that corresponds to this template
1978 /// argument.
1979 ///
1980 /// \param Loc The source location to use for the resulting template
1981 /// argument.
1982 static TemplateArgumentLoc
1983 getTrivialTemplateArgumentLoc(Sema &S,
1984                               const TemplateArgument &Arg,
1985                               QualType NTTPType,
1986                               SourceLocation Loc) {
1987   switch (Arg.getKind()) {
1988   case TemplateArgument::Null:
1989     llvm_unreachable("Can't get a NULL template argument here");
1990
1991   case TemplateArgument::Type:
1992     return TemplateArgumentLoc(Arg,
1993                      S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
1994
1995   case TemplateArgument::Declaration: {
1996     Expr *E
1997       = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
1998           .getAs<Expr>();
1999     return TemplateArgumentLoc(TemplateArgument(E), E);
2000   }
2001
2002   case TemplateArgument::NullPtr: {
2003     Expr *E
2004       = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2005           .getAs<Expr>();
2006     return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true),
2007                                E);
2008   }
2009
2010   case TemplateArgument::Integral: {
2011     Expr *E
2012       = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).getAs<Expr>();
2013     return TemplateArgumentLoc(TemplateArgument(E), E);
2014   }
2015
2016     case TemplateArgument::Template:
2017     case TemplateArgument::TemplateExpansion: {
2018       NestedNameSpecifierLocBuilder Builder;
2019       TemplateName Template = Arg.getAsTemplate();
2020       if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
2021         Builder.MakeTrivial(S.Context, DTN->getQualifier(), Loc);
2022       else if (QualifiedTemplateName *QTN =
2023                    Template.getAsQualifiedTemplateName())
2024         Builder.MakeTrivial(S.Context, QTN->getQualifier(), Loc);
2025
2026       if (Arg.getKind() == TemplateArgument::Template)
2027         return TemplateArgumentLoc(Arg,
2028                                    Builder.getWithLocInContext(S.Context),
2029                                    Loc);
2030
2031
2032       return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(S.Context),
2033                                  Loc, Loc);
2034     }
2035
2036   case TemplateArgument::Expression:
2037     return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2038
2039   case TemplateArgument::Pack:
2040     return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
2041   }
2042
2043   llvm_unreachable("Invalid TemplateArgument Kind!");
2044 }
2045
2046
2047 /// \brief Convert the given deduced template argument and add it to the set of
2048 /// fully-converted template arguments.
2049 static bool
2050 ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
2051                                DeducedTemplateArgument Arg,
2052                                NamedDecl *Template,
2053                                QualType NTTPType,
2054                                unsigned ArgumentPackIndex,
2055                                TemplateDeductionInfo &Info,
2056                                bool InFunctionTemplate,
2057                                SmallVectorImpl<TemplateArgument> &Output) {
2058   if (Arg.getKind() == TemplateArgument::Pack) {
2059     // This is a template argument pack, so check each of its arguments against
2060     // the template parameter.
2061     SmallVector<TemplateArgument, 2> PackedArgsBuilder;
2062     for (const auto &P : Arg.pack_elements()) {
2063       // When converting the deduced template argument, append it to the
2064       // general output list. We need to do this so that the template argument
2065       // checking logic has all of the prior template arguments available.
2066       DeducedTemplateArgument InnerArg(P);
2067       InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
2068       if (ConvertDeducedTemplateArgument(S, Param, InnerArg, Template,
2069                                          NTTPType, PackedArgsBuilder.size(),
2070                                          Info, InFunctionTemplate, Output))
2071         return true;
2072
2073       // Move the converted template argument into our argument pack.
2074       PackedArgsBuilder.push_back(Output.pop_back_val());
2075     }
2076
2077     // Create the resulting argument pack.
2078     Output.push_back(TemplateArgument::CreatePackCopy(S.Context,
2079                                                       PackedArgsBuilder.data(),
2080                                                      PackedArgsBuilder.size()));
2081     return false;
2082   }
2083
2084   // Convert the deduced template argument into a template
2085   // argument that we can check, almost as if the user had written
2086   // the template argument explicitly.
2087   TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType,
2088                                                              Info.getLocation());
2089
2090   // Check the template argument, converting it as necessary.
2091   return S.CheckTemplateArgument(Param, ArgLoc,
2092                                  Template,
2093                                  Template->getLocation(),
2094                                  Template->getSourceRange().getEnd(),
2095                                  ArgumentPackIndex,
2096                                  Output,
2097                                  InFunctionTemplate
2098                                   ? (Arg.wasDeducedFromArrayBound()
2099                                        ? Sema::CTAK_DeducedFromArrayBound
2100                                        : Sema::CTAK_Deduced)
2101                                  : Sema::CTAK_Specified);
2102 }
2103
2104 /// Complete template argument deduction for a class template partial
2105 /// specialization.
2106 static Sema::TemplateDeductionResult
2107 FinishTemplateArgumentDeduction(Sema &S,
2108                                 ClassTemplatePartialSpecializationDecl *Partial,
2109                                 const TemplateArgumentList &TemplateArgs,
2110                       SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2111                                 TemplateDeductionInfo &Info) {
2112   // Unevaluated SFINAE context.
2113   EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated);
2114   Sema::SFINAETrap Trap(S);
2115
2116   Sema::ContextRAII SavedContext(S, Partial);
2117
2118   // C++ [temp.deduct.type]p2:
2119   //   [...] or if any template argument remains neither deduced nor
2120   //   explicitly specified, template argument deduction fails.
2121   SmallVector<TemplateArgument, 4> Builder;
2122   TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2123   for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2124     NamedDecl *Param = PartialParams->getParam(I);
2125     if (Deduced[I].isNull()) {
2126       Info.Param = makeTemplateParameter(Param);
2127       return Sema::TDK_Incomplete;
2128     }
2129
2130     // We have deduced this argument, so it still needs to be
2131     // checked and converted.
2132
2133     // First, for a non-type template parameter type that is
2134     // initialized by a declaration, we need the type of the
2135     // corresponding non-type template parameter.
2136     QualType NTTPType;
2137     if (NonTypeTemplateParmDecl *NTTP
2138                                   = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2139       NTTPType = NTTP->getType();
2140       if (NTTPType->isDependentType()) {
2141         TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2142                                           Builder.data(), Builder.size());
2143         NTTPType = S.SubstType(NTTPType,
2144                                MultiLevelTemplateArgumentList(TemplateArgs),
2145                                NTTP->getLocation(),
2146                                NTTP->getDeclName());
2147         if (NTTPType.isNull()) {
2148           Info.Param = makeTemplateParameter(Param);
2149           // FIXME: These template arguments are temporary. Free them!
2150           Info.reset(TemplateArgumentList::CreateCopy(S.Context,
2151                                                       Builder.data(),
2152                                                       Builder.size()));
2153           return Sema::TDK_SubstitutionFailure;
2154         }
2155       }
2156     }
2157
2158     if (ConvertDeducedTemplateArgument(S, Param, Deduced[I],
2159                                        Partial, NTTPType, 0, Info, false,
2160                                        Builder)) {
2161       Info.Param = makeTemplateParameter(Param);
2162       // FIXME: These template arguments are temporary. Free them!
2163       Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2164                                                   Builder.size()));
2165       return Sema::TDK_SubstitutionFailure;
2166     }
2167   }
2168
2169   // Form the template argument list from the deduced template arguments.
2170   TemplateArgumentList *DeducedArgumentList
2171     = TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2172                                        Builder.size());
2173
2174   Info.reset(DeducedArgumentList);
2175
2176   // Substitute the deduced template arguments into the template
2177   // arguments of the class template partial specialization, and
2178   // verify that the instantiated template arguments are both valid
2179   // and are equivalent to the template arguments originally provided
2180   // to the class template.
2181   LocalInstantiationScope InstScope(S);
2182   ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
2183   const ASTTemplateArgumentListInfo *PartialTemplArgInfo
2184     = Partial->getTemplateArgsAsWritten();
2185   const TemplateArgumentLoc *PartialTemplateArgs
2186     = PartialTemplArgInfo->getTemplateArgs();
2187
2188   TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2189                                     PartialTemplArgInfo->RAngleLoc);
2190
2191   if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs,
2192               InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2193     unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2194     if (ParamIdx >= Partial->getTemplateParameters()->size())
2195       ParamIdx = Partial->getTemplateParameters()->size() - 1;
2196
2197     Decl *Param
2198       = const_cast<NamedDecl *>(
2199                           Partial->getTemplateParameters()->getParam(ParamIdx));
2200     Info.Param = makeTemplateParameter(Param);
2201     Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2202     return Sema::TDK_SubstitutionFailure;
2203   }
2204
2205   SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2206   if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(),
2207                                   InstArgs, false, ConvertedInstArgs))
2208     return Sema::TDK_SubstitutionFailure;
2209
2210   TemplateParameterList *TemplateParams
2211     = ClassTemplate->getTemplateParameters();
2212   for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2213     TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2214     if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2215       Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2216       Info.FirstArg = TemplateArgs[I];
2217       Info.SecondArg = InstArg;
2218       return Sema::TDK_NonDeducedMismatch;
2219     }
2220   }
2221
2222   if (Trap.hasErrorOccurred())
2223     return Sema::TDK_SubstitutionFailure;
2224
2225   return Sema::TDK_Success;
2226 }
2227
2228 /// \brief Perform template argument deduction to determine whether
2229 /// the given template arguments match the given class template
2230 /// partial specialization per C++ [temp.class.spec.match].
2231 Sema::TemplateDeductionResult
2232 Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
2233                               const TemplateArgumentList &TemplateArgs,
2234                               TemplateDeductionInfo &Info) {
2235   if (Partial->isInvalidDecl())
2236     return TDK_Invalid;
2237
2238   // C++ [temp.class.spec.match]p2:
2239   //   A partial specialization matches a given actual template
2240   //   argument list if the template arguments of the partial
2241   //   specialization can be deduced from the actual template argument
2242   //   list (14.8.2).
2243
2244   // Unevaluated SFINAE context.
2245   EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2246   SFINAETrap Trap(*this);
2247
2248   SmallVector<DeducedTemplateArgument, 4> Deduced;
2249   Deduced.resize(Partial->getTemplateParameters()->size());
2250   if (TemplateDeductionResult Result
2251         = ::DeduceTemplateArguments(*this,
2252                                     Partial->getTemplateParameters(),
2253                                     Partial->getTemplateArgs(),
2254                                     TemplateArgs, Info, Deduced))
2255     return Result;
2256
2257   SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2258   InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2259                              Info);
2260   if (Inst.isInvalid())
2261     return TDK_InstantiationDepth;
2262
2263   if (Trap.hasErrorOccurred())
2264     return Sema::TDK_SubstitutionFailure;
2265
2266   return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2267                                            Deduced, Info);
2268 }
2269
2270 /// Complete template argument deduction for a variable template partial
2271 /// specialization.
2272 /// TODO: Unify with ClassTemplatePartialSpecializationDecl version?
2273 ///       May require unifying ClassTemplate(Partial)SpecializationDecl and
2274 ///        VarTemplate(Partial)SpecializationDecl with a new data
2275 ///        structure Template(Partial)SpecializationDecl, and
2276 ///        using Template(Partial)SpecializationDecl as input type.
2277 static Sema::TemplateDeductionResult FinishTemplateArgumentDeduction(
2278     Sema &S, VarTemplatePartialSpecializationDecl *Partial,
2279     const TemplateArgumentList &TemplateArgs,
2280     SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2281     TemplateDeductionInfo &Info) {
2282   // Unevaluated SFINAE context.
2283   EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated);
2284   Sema::SFINAETrap Trap(S);
2285
2286   // C++ [temp.deduct.type]p2:
2287   //   [...] or if any template argument remains neither deduced nor
2288   //   explicitly specified, template argument deduction fails.
2289   SmallVector<TemplateArgument, 4> Builder;
2290   TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2291   for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2292     NamedDecl *Param = PartialParams->getParam(I);
2293     if (Deduced[I].isNull()) {
2294       Info.Param = makeTemplateParameter(Param);
2295       return Sema::TDK_Incomplete;
2296     }
2297
2298     // We have deduced this argument, so it still needs to be
2299     // checked and converted.
2300
2301     // First, for a non-type template parameter type that is
2302     // initialized by a declaration, we need the type of the
2303     // corresponding non-type template parameter.
2304     QualType NTTPType;
2305     if (NonTypeTemplateParmDecl *NTTP =
2306             dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2307       NTTPType = NTTP->getType();
2308       if (NTTPType->isDependentType()) {
2309         TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2310                                           Builder.data(), Builder.size());
2311         NTTPType =
2312             S.SubstType(NTTPType, MultiLevelTemplateArgumentList(TemplateArgs),
2313                         NTTP->getLocation(), NTTP->getDeclName());
2314         if (NTTPType.isNull()) {
2315           Info.Param = makeTemplateParameter(Param);
2316           // FIXME: These template arguments are temporary. Free them!
2317           Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2318                                                       Builder.size()));
2319           return Sema::TDK_SubstitutionFailure;
2320         }
2321       }
2322     }
2323
2324     if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Partial, NTTPType,
2325                                        0, Info, false, Builder)) {
2326       Info.Param = makeTemplateParameter(Param);
2327       // FIXME: These template arguments are temporary. Free them!
2328       Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2329                                                   Builder.size()));
2330       return Sema::TDK_SubstitutionFailure;
2331     }
2332   }
2333
2334   // Form the template argument list from the deduced template arguments.
2335   TemplateArgumentList *DeducedArgumentList = TemplateArgumentList::CreateCopy(
2336       S.Context, Builder.data(), Builder.size());
2337
2338   Info.reset(DeducedArgumentList);
2339
2340   // Substitute the deduced template arguments into the template
2341   // arguments of the class template partial specialization, and
2342   // verify that the instantiated template arguments are both valid
2343   // and are equivalent to the template arguments originally provided
2344   // to the class template.
2345   LocalInstantiationScope InstScope(S);
2346   VarTemplateDecl *VarTemplate = Partial->getSpecializedTemplate();
2347   const ASTTemplateArgumentListInfo *PartialTemplArgInfo
2348     = Partial->getTemplateArgsAsWritten();
2349   const TemplateArgumentLoc *PartialTemplateArgs
2350     = PartialTemplArgInfo->getTemplateArgs();
2351
2352   TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2353                                     PartialTemplArgInfo->RAngleLoc);
2354
2355   if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs,
2356               InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2357     unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2358     if (ParamIdx >= Partial->getTemplateParameters()->size())
2359       ParamIdx = Partial->getTemplateParameters()->size() - 1;
2360
2361     Decl *Param = const_cast<NamedDecl *>(
2362         Partial->getTemplateParameters()->getParam(ParamIdx));
2363     Info.Param = makeTemplateParameter(Param);
2364     Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2365     return Sema::TDK_SubstitutionFailure;
2366   }
2367   SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2368   if (S.CheckTemplateArgumentList(VarTemplate, Partial->getLocation(), InstArgs,
2369                                   false, ConvertedInstArgs))
2370     return Sema::TDK_SubstitutionFailure;
2371
2372   TemplateParameterList *TemplateParams = VarTemplate->getTemplateParameters();
2373   for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2374     TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2375     if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2376       Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2377       Info.FirstArg = TemplateArgs[I];
2378       Info.SecondArg = InstArg;
2379       return Sema::TDK_NonDeducedMismatch;
2380     }
2381   }
2382
2383   if (Trap.hasErrorOccurred())
2384     return Sema::TDK_SubstitutionFailure;
2385
2386   return Sema::TDK_Success;
2387 }
2388
2389 /// \brief Perform template argument deduction to determine whether
2390 /// the given template arguments match the given variable template
2391 /// partial specialization per C++ [temp.class.spec.match].
2392 /// TODO: Unify with ClassTemplatePartialSpecializationDecl version?
2393 ///       May require unifying ClassTemplate(Partial)SpecializationDecl and
2394 ///        VarTemplate(Partial)SpecializationDecl with a new data
2395 ///        structure Template(Partial)SpecializationDecl, and
2396 ///        using Template(Partial)SpecializationDecl as input type.
2397 Sema::TemplateDeductionResult
2398 Sema::DeduceTemplateArguments(VarTemplatePartialSpecializationDecl *Partial,
2399                               const TemplateArgumentList &TemplateArgs,
2400                               TemplateDeductionInfo &Info) {
2401   if (Partial->isInvalidDecl())
2402     return TDK_Invalid;
2403
2404   // C++ [temp.class.spec.match]p2:
2405   //   A partial specialization matches a given actual template
2406   //   argument list if the template arguments of the partial
2407   //   specialization can be deduced from the actual template argument
2408   //   list (14.8.2).
2409
2410   // Unevaluated SFINAE context.
2411   EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2412   SFINAETrap Trap(*this);
2413
2414   SmallVector<DeducedTemplateArgument, 4> Deduced;
2415   Deduced.resize(Partial->getTemplateParameters()->size());
2416   if (TemplateDeductionResult Result = ::DeduceTemplateArguments(
2417           *this, Partial->getTemplateParameters(), Partial->getTemplateArgs(),
2418           TemplateArgs, Info, Deduced))
2419     return Result;
2420
2421   SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2422   InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2423                              Info);
2424   if (Inst.isInvalid())
2425     return TDK_InstantiationDepth;
2426
2427   if (Trap.hasErrorOccurred())
2428     return Sema::TDK_SubstitutionFailure;
2429
2430   return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2431                                            Deduced, Info);
2432 }
2433
2434 /// \brief Determine whether the given type T is a simple-template-id type.
2435 static bool isSimpleTemplateIdType(QualType T) {
2436   if (const TemplateSpecializationType *Spec
2437         = T->getAs<TemplateSpecializationType>())
2438     return Spec->getTemplateName().getAsTemplateDecl() != nullptr;
2439
2440   return false;
2441 }
2442
2443 /// \brief Substitute the explicitly-provided template arguments into the
2444 /// given function template according to C++ [temp.arg.explicit].
2445 ///
2446 /// \param FunctionTemplate the function template into which the explicit
2447 /// template arguments will be substituted.
2448 ///
2449 /// \param ExplicitTemplateArgs the explicitly-specified template
2450 /// arguments.
2451 ///
2452 /// \param Deduced the deduced template arguments, which will be populated
2453 /// with the converted and checked explicit template arguments.
2454 ///
2455 /// \param ParamTypes will be populated with the instantiated function
2456 /// parameters.
2457 ///
2458 /// \param FunctionType if non-NULL, the result type of the function template
2459 /// will also be instantiated and the pointed-to value will be updated with
2460 /// the instantiated function type.
2461 ///
2462 /// \param Info if substitution fails for any reason, this object will be
2463 /// populated with more information about the failure.
2464 ///
2465 /// \returns TDK_Success if substitution was successful, or some failure
2466 /// condition.
2467 Sema::TemplateDeductionResult
2468 Sema::SubstituteExplicitTemplateArguments(
2469                                       FunctionTemplateDecl *FunctionTemplate,
2470                                TemplateArgumentListInfo &ExplicitTemplateArgs,
2471                        SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2472                                  SmallVectorImpl<QualType> &ParamTypes,
2473                                           QualType *FunctionType,
2474                                           TemplateDeductionInfo &Info) {
2475   FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2476   TemplateParameterList *TemplateParams
2477     = FunctionTemplate->getTemplateParameters();
2478
2479   if (ExplicitTemplateArgs.size() == 0) {
2480     // No arguments to substitute; just copy over the parameter types and
2481     // fill in the function type.
2482     for (auto P : Function->params())
2483       ParamTypes.push_back(P->getType());
2484
2485     if (FunctionType)
2486       *FunctionType = Function->getType();
2487     return TDK_Success;
2488   }
2489
2490   // Unevaluated SFINAE context.
2491   EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2492   SFINAETrap Trap(*this);
2493
2494   // C++ [temp.arg.explicit]p3:
2495   //   Template arguments that are present shall be specified in the
2496   //   declaration order of their corresponding template-parameters. The
2497   //   template argument list shall not specify more template-arguments than
2498   //   there are corresponding template-parameters.
2499   SmallVector<TemplateArgument, 4> Builder;
2500
2501   // Enter a new template instantiation context where we check the
2502   // explicitly-specified template arguments against this function template,
2503   // and then substitute them into the function parameter types.
2504   SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2505   InstantiatingTemplate Inst(*this, Info.getLocation(), FunctionTemplate,
2506                              DeducedArgs,
2507            ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution,
2508                              Info);
2509   if (Inst.isInvalid())
2510     return TDK_InstantiationDepth;
2511
2512   if (CheckTemplateArgumentList(FunctionTemplate,
2513                                 SourceLocation(),
2514                                 ExplicitTemplateArgs,
2515                                 true,
2516                                 Builder) || Trap.hasErrorOccurred()) {
2517     unsigned Index = Builder.size();
2518     if (Index >= TemplateParams->size())
2519       Index = TemplateParams->size() - 1;
2520     Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
2521     return TDK_InvalidExplicitArguments;
2522   }
2523
2524   // Form the template argument list from the explicitly-specified
2525   // template arguments.
2526   TemplateArgumentList *ExplicitArgumentList
2527     = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2528   Info.reset(ExplicitArgumentList);
2529
2530   // Template argument deduction and the final substitution should be
2531   // done in the context of the templated declaration.  Explicit
2532   // argument substitution, on the other hand, needs to happen in the
2533   // calling context.
2534   ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2535
2536   // If we deduced template arguments for a template parameter pack,
2537   // note that the template argument pack is partially substituted and record
2538   // the explicit template arguments. They'll be used as part of deduction
2539   // for this template parameter pack.
2540   for (unsigned I = 0, N = Builder.size(); I != N; ++I) {
2541     const TemplateArgument &Arg = Builder[I];
2542     if (Arg.getKind() == TemplateArgument::Pack) {
2543       CurrentInstantiationScope->SetPartiallySubstitutedPack(
2544                                                  TemplateParams->getParam(I),
2545                                                              Arg.pack_begin(),
2546                                                              Arg.pack_size());
2547       break;
2548     }
2549   }
2550
2551   const FunctionProtoType *Proto
2552     = Function->getType()->getAs<FunctionProtoType>();
2553   assert(Proto && "Function template does not have a prototype?");
2554
2555   // Isolate our substituted parameters from our caller.
2556   LocalInstantiationScope InstScope(*this, /*MergeWithOuterScope*/true);
2557
2558   // Instantiate the types of each of the function parameters given the
2559   // explicitly-specified template arguments. If the function has a trailing
2560   // return type, substitute it after the arguments to ensure we substitute
2561   // in lexical order.
2562   if (Proto->hasTrailingReturn()) {
2563     if (SubstParmTypes(Function->getLocation(),
2564                        Function->param_begin(), Function->getNumParams(),
2565                        MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2566                        ParamTypes))
2567       return TDK_SubstitutionFailure;
2568   }
2569
2570   // Instantiate the return type.
2571   QualType ResultType;
2572   {
2573     // C++11 [expr.prim.general]p3:
2574     //   If a declaration declares a member function or member function
2575     //   template of a class X, the expression this is a prvalue of type
2576     //   "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
2577     //   and the end of the function-definition, member-declarator, or
2578     //   declarator.
2579     unsigned ThisTypeQuals = 0;
2580     CXXRecordDecl *ThisContext = nullptr;
2581     if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
2582       ThisContext = Method->getParent();
2583       ThisTypeQuals = Method->getTypeQualifiers();
2584     }
2585
2586     CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
2587                                getLangOpts().CPlusPlus11);
2588
2589     ResultType =
2590         SubstType(Proto->getReturnType(),
2591                   MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2592                   Function->getTypeSpecStartLoc(), Function->getDeclName());
2593     if (ResultType.isNull() || Trap.hasErrorOccurred())
2594       return TDK_SubstitutionFailure;
2595   }
2596
2597   // Instantiate the types of each of the function parameters given the
2598   // explicitly-specified template arguments if we didn't do so earlier.
2599   if (!Proto->hasTrailingReturn() &&
2600       SubstParmTypes(Function->getLocation(),
2601                      Function->param_begin(), Function->getNumParams(),
2602                      MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2603                      ParamTypes))
2604     return TDK_SubstitutionFailure;
2605
2606   if (FunctionType) {
2607     *FunctionType = BuildFunctionType(ResultType, ParamTypes,
2608                                       Function->getLocation(),
2609                                       Function->getDeclName(),
2610                                       Proto->getExtProtoInfo());
2611     if (FunctionType->isNull() || Trap.hasErrorOccurred())
2612       return TDK_SubstitutionFailure;
2613   }
2614
2615   // C++ [temp.arg.explicit]p2:
2616   //   Trailing template arguments that can be deduced (14.8.2) may be
2617   //   omitted from the list of explicit template-arguments. If all of the
2618   //   template arguments can be deduced, they may all be omitted; in this
2619   //   case, the empty template argument list <> itself may also be omitted.
2620   //
2621   // Take all of the explicitly-specified arguments and put them into
2622   // the set of deduced template arguments. Explicitly-specified
2623   // parameter packs, however, will be set to NULL since the deduction
2624   // mechanisms handle explicitly-specified argument packs directly.
2625   Deduced.reserve(TemplateParams->size());
2626   for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) {
2627     const TemplateArgument &Arg = ExplicitArgumentList->get(I);
2628     if (Arg.getKind() == TemplateArgument::Pack)
2629       Deduced.push_back(DeducedTemplateArgument());
2630     else
2631       Deduced.push_back(Arg);
2632   }
2633
2634   return TDK_Success;
2635 }
2636
2637 /// \brief Check whether the deduced argument type for a call to a function
2638 /// template matches the actual argument type per C++ [temp.deduct.call]p4.
2639 static bool
2640 CheckOriginalCallArgDeduction(Sema &S, Sema::OriginalCallArg OriginalArg,
2641                               QualType DeducedA) {
2642   ASTContext &Context = S.Context;
2643
2644   QualType A = OriginalArg.OriginalArgType;
2645   QualType OriginalParamType = OriginalArg.OriginalParamType;
2646
2647   // Check for type equality (top-level cv-qualifiers are ignored).
2648   if (Context.hasSameUnqualifiedType(A, DeducedA))
2649     return false;
2650
2651   // Strip off references on the argument types; they aren't needed for
2652   // the following checks.
2653   if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
2654     DeducedA = DeducedARef->getPointeeType();
2655   if (const ReferenceType *ARef = A->getAs<ReferenceType>())
2656     A = ARef->getPointeeType();
2657
2658   // C++ [temp.deduct.call]p4:
2659   //   [...] However, there are three cases that allow a difference:
2660   //     - If the original P is a reference type, the deduced A (i.e., the
2661   //       type referred to by the reference) can be more cv-qualified than
2662   //       the transformed A.
2663   if (const ReferenceType *OriginalParamRef
2664       = OriginalParamType->getAs<ReferenceType>()) {
2665     // We don't want to keep the reference around any more.
2666     OriginalParamType = OriginalParamRef->getPointeeType();
2667
2668     Qualifiers AQuals = A.getQualifiers();
2669     Qualifiers DeducedAQuals = DeducedA.getQualifiers();
2670
2671     // Under Objective-C++ ARC, the deduced type may have implicitly
2672     // been given strong or (when dealing with a const reference)
2673     // unsafe_unretained lifetime. If so, update the original
2674     // qualifiers to include this lifetime.
2675     if (S.getLangOpts().ObjCAutoRefCount &&
2676         ((DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong &&
2677           AQuals.getObjCLifetime() == Qualifiers::OCL_None) ||
2678          (DeducedAQuals.hasConst() &&
2679           DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone))) {
2680       AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime());
2681     }
2682
2683     if (AQuals == DeducedAQuals) {
2684       // Qualifiers match; there's nothing to do.
2685     } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) {
2686       return true;
2687     } else {
2688       // Qualifiers are compatible, so have the argument type adopt the
2689       // deduced argument type's qualifiers as if we had performed the
2690       // qualification conversion.
2691       A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
2692     }
2693   }
2694
2695   //    - The transformed A can be another pointer or pointer to member
2696   //      type that can be converted to the deduced A via a qualification
2697   //      conversion.
2698   //
2699   // Also allow conversions which merely strip [[noreturn]] from function types
2700   // (recursively) as an extension.
2701   // FIXME: Currently, this doesn't play nicely with qualification conversions.
2702   bool ObjCLifetimeConversion = false;
2703   QualType ResultTy;
2704   if ((A->isAnyPointerType() || A->isMemberPointerType()) &&
2705       (S.IsQualificationConversion(A, DeducedA, false,
2706                                    ObjCLifetimeConversion) ||
2707        S.IsNoReturnConversion(A, DeducedA, ResultTy)))
2708     return false;
2709
2710
2711   //    - If P is a class and P has the form simple-template-id, then the
2712   //      transformed A can be a derived class of the deduced A. [...]
2713   //     [...] Likewise, if P is a pointer to a class of the form
2714   //      simple-template-id, the transformed A can be a pointer to a
2715   //      derived class pointed to by the deduced A.
2716   if (const PointerType *OriginalParamPtr
2717       = OriginalParamType->getAs<PointerType>()) {
2718     if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
2719       if (const PointerType *APtr = A->getAs<PointerType>()) {
2720         if (A->getPointeeType()->isRecordType()) {
2721           OriginalParamType = OriginalParamPtr->getPointeeType();
2722           DeducedA = DeducedAPtr->getPointeeType();
2723           A = APtr->getPointeeType();
2724         }
2725       }
2726     }
2727   }
2728
2729   if (Context.hasSameUnqualifiedType(A, DeducedA))
2730     return false;
2731
2732   if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) &&
2733       S.IsDerivedFrom(A, DeducedA))
2734     return false;
2735
2736   return true;
2737 }
2738
2739 /// \brief Finish template argument deduction for a function template,
2740 /// checking the deduced template arguments for completeness and forming
2741 /// the function template specialization.
2742 ///
2743 /// \param OriginalCallArgs If non-NULL, the original call arguments against
2744 /// which the deduced argument types should be compared.
2745 Sema::TemplateDeductionResult
2746 Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate,
2747                        SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2748                                       unsigned NumExplicitlySpecified,
2749                                       FunctionDecl *&Specialization,
2750                                       TemplateDeductionInfo &Info,
2751         SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs,
2752                                       bool PartialOverloading) {
2753   TemplateParameterList *TemplateParams
2754     = FunctionTemplate->getTemplateParameters();
2755
2756   // Unevaluated SFINAE context.
2757   EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2758   SFINAETrap Trap(*this);
2759
2760   // Enter a new template instantiation context while we instantiate the
2761   // actual function declaration.
2762   SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2763   InstantiatingTemplate Inst(*this, Info.getLocation(), FunctionTemplate,
2764                              DeducedArgs,
2765               ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution,
2766                              Info);
2767   if (Inst.isInvalid())
2768     return TDK_InstantiationDepth;
2769
2770   ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2771
2772   // C++ [temp.deduct.type]p2:
2773   //   [...] or if any template argument remains neither deduced nor
2774   //   explicitly specified, template argument deduction fails.
2775   SmallVector<TemplateArgument, 4> Builder;
2776   for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2777     NamedDecl *Param = TemplateParams->getParam(I);
2778
2779     if (!Deduced[I].isNull()) {
2780       if (I < NumExplicitlySpecified) {
2781         // We have already fully type-checked and converted this
2782         // argument, because it was explicitly-specified. Just record the
2783         // presence of this argument.
2784         Builder.push_back(Deduced[I]);
2785         // We may have had explicitly-specified template arguments for a
2786         // template parameter pack (that may or may not have been extended
2787         // via additional deduced arguments).
2788         if (Param->isParameterPack() && CurrentInstantiationScope) {
2789           if (CurrentInstantiationScope->getPartiallySubstitutedPack() ==
2790               Param) {
2791             // Forget the partially-substituted pack; its substitution is now
2792             // complete.
2793             CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2794           }
2795         }
2796         continue;
2797       }
2798       // We have deduced this argument, so it still needs to be
2799       // checked and converted.
2800
2801       // First, for a non-type template parameter type that is
2802       // initialized by a declaration, we need the type of the
2803       // corresponding non-type template parameter.
2804       QualType NTTPType;
2805       if (NonTypeTemplateParmDecl *NTTP
2806                                 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2807         NTTPType = NTTP->getType();
2808         if (NTTPType->isDependentType()) {
2809           TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2810                                             Builder.data(), Builder.size());
2811           NTTPType = SubstType(NTTPType,
2812                                MultiLevelTemplateArgumentList(TemplateArgs),
2813                                NTTP->getLocation(),
2814                                NTTP->getDeclName());
2815           if (NTTPType.isNull()) {
2816             Info.Param = makeTemplateParameter(Param);
2817             // FIXME: These template arguments are temporary. Free them!
2818             Info.reset(TemplateArgumentList::CreateCopy(Context,
2819                                                         Builder.data(),
2820                                                         Builder.size()));
2821             return TDK_SubstitutionFailure;
2822           }
2823         }
2824       }
2825
2826       if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I],
2827                                          FunctionTemplate, NTTPType, 0, Info,
2828                                          true, Builder)) {
2829         Info.Param = makeTemplateParameter(Param);
2830         // FIXME: These template arguments are temporary. Free them!
2831         Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2832                                                     Builder.size()));
2833         return TDK_SubstitutionFailure;
2834       }
2835
2836       continue;
2837     }
2838
2839     // C++0x [temp.arg.explicit]p3:
2840     //    A trailing template parameter pack (14.5.3) not otherwise deduced will
2841     //    be deduced to an empty sequence of template arguments.
2842     // FIXME: Where did the word "trailing" come from?
2843     if (Param->isTemplateParameterPack()) {
2844       // We may have had explicitly-specified template arguments for this
2845       // template parameter pack. If so, our empty deduction extends the
2846       // explicitly-specified set (C++0x [temp.arg.explicit]p9).
2847       const TemplateArgument *ExplicitArgs;
2848       unsigned NumExplicitArgs;
2849       if (CurrentInstantiationScope &&
2850           CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs,
2851                                                              &NumExplicitArgs)
2852             == Param) {
2853         Builder.push_back(TemplateArgument(ExplicitArgs, NumExplicitArgs));
2854
2855         // Forget the partially-substituted pack; it's substitution is now
2856         // complete.
2857         CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2858       } else {
2859         Builder.push_back(TemplateArgument::getEmptyPack());
2860       }
2861       continue;
2862     }
2863
2864     // Substitute into the default template argument, if available.
2865     bool HasDefaultArg = false;
2866     TemplateArgumentLoc DefArg
2867       = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate,
2868                                               FunctionTemplate->getLocation(),
2869                                   FunctionTemplate->getSourceRange().getEnd(),
2870                                                 Param,
2871                                                 Builder, HasDefaultArg);
2872
2873     // If there was no default argument, deduction is incomplete.
2874     if (DefArg.getArgument().isNull()) {
2875       Info.Param = makeTemplateParameter(
2876                          const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2877       Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2878                                                   Builder.size()));
2879       if (PartialOverloading) break;
2880
2881       return HasDefaultArg ? TDK_SubstitutionFailure : TDK_Incomplete;
2882     }
2883
2884     // Check whether we can actually use the default argument.
2885     if (CheckTemplateArgument(Param, DefArg,
2886                               FunctionTemplate,
2887                               FunctionTemplate->getLocation(),
2888                               FunctionTemplate->getSourceRange().getEnd(),
2889                               0, Builder,
2890                               CTAK_Specified)) {
2891       Info.Param = makeTemplateParameter(
2892                          const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2893       // FIXME: These template arguments are temporary. Free them!
2894       Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2895                                                   Builder.size()));
2896       return TDK_SubstitutionFailure;
2897     }
2898
2899     // If we get here, we successfully used the default template argument.
2900   }
2901
2902   // Form the template argument list from the deduced template arguments.
2903   TemplateArgumentList *DeducedArgumentList
2904     = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2905   Info.reset(DeducedArgumentList);
2906
2907   // Substitute the deduced template arguments into the function template
2908   // declaration to produce the function template specialization.
2909   DeclContext *Owner = FunctionTemplate->getDeclContext();
2910   if (FunctionTemplate->getFriendObjectKind())
2911     Owner = FunctionTemplate->getLexicalDeclContext();
2912   Specialization = cast_or_null<FunctionDecl>(
2913                       SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner,
2914                          MultiLevelTemplateArgumentList(*DeducedArgumentList)));
2915   if (!Specialization || Specialization->isInvalidDecl())
2916     return TDK_SubstitutionFailure;
2917
2918   assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
2919          FunctionTemplate->getCanonicalDecl());
2920
2921   // If the template argument list is owned by the function template
2922   // specialization, release it.
2923   if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
2924       !Trap.hasErrorOccurred())
2925     Info.take();
2926
2927   // There may have been an error that did not prevent us from constructing a
2928   // declaration. Mark the declaration invalid and return with a substitution
2929   // failure.
2930   if (Trap.hasErrorOccurred()) {
2931     Specialization->setInvalidDecl(true);
2932     return TDK_SubstitutionFailure;
2933   }
2934
2935   if (OriginalCallArgs) {
2936     // C++ [temp.deduct.call]p4:
2937     //   In general, the deduction process attempts to find template argument
2938     //   values that will make the deduced A identical to A (after the type A
2939     //   is transformed as described above). [...]
2940     for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
2941       OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
2942       unsigned ParamIdx = OriginalArg.ArgIdx;
2943
2944       if (ParamIdx >= Specialization->getNumParams())
2945         continue;
2946
2947       QualType DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
2948       if (CheckOriginalCallArgDeduction(*this, OriginalArg, DeducedA))
2949         return Sema::TDK_SubstitutionFailure;
2950     }
2951   }
2952
2953   // If we suppressed any diagnostics while performing template argument
2954   // deduction, and if we haven't already instantiated this declaration,
2955   // keep track of these diagnostics. They'll be emitted if this specialization
2956   // is actually used.
2957   if (Info.diag_begin() != Info.diag_end()) {
2958     SuppressedDiagnosticsMap::iterator
2959       Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
2960     if (Pos == SuppressedDiagnostics.end())
2961         SuppressedDiagnostics[Specialization->getCanonicalDecl()]
2962           .append(Info.diag_begin(), Info.diag_end());
2963   }
2964
2965   return TDK_Success;
2966 }
2967
2968 /// Gets the type of a function for template-argument-deducton
2969 /// purposes when it's considered as part of an overload set.
2970 static QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R,
2971                                   FunctionDecl *Fn) {
2972   // We may need to deduce the return type of the function now.
2973   if (S.getLangOpts().CPlusPlus14 && Fn->getReturnType()->isUndeducedType() &&
2974       S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/ false))
2975     return QualType();
2976
2977   if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
2978     if (Method->isInstance()) {
2979       // An instance method that's referenced in a form that doesn't
2980       // look like a member pointer is just invalid.
2981       if (!R.HasFormOfMemberPointer) return QualType();
2982
2983       return S.Context.getMemberPointerType(Fn->getType(),
2984                S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
2985     }
2986
2987   if (!R.IsAddressOfOperand) return Fn->getType();
2988   return S.Context.getPointerType(Fn->getType());
2989 }
2990
2991 /// Apply the deduction rules for overload sets.
2992 ///
2993 /// \return the null type if this argument should be treated as an
2994 /// undeduced context
2995 static QualType
2996 ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
2997                             Expr *Arg, QualType ParamType,
2998                             bool ParamWasReference) {
2999
3000   OverloadExpr::FindResult R = OverloadExpr::find(Arg);
3001
3002   OverloadExpr *Ovl = R.Expression;
3003
3004   // C++0x [temp.deduct.call]p4
3005   unsigned TDF = 0;
3006   if (ParamWasReference)
3007     TDF |= TDF_ParamWithReferenceType;
3008   if (R.IsAddressOfOperand)
3009     TDF |= TDF_IgnoreQualifiers;
3010
3011   // C++0x [temp.deduct.call]p6:
3012   //   When P is a function type, pointer to function type, or pointer
3013   //   to member function type:
3014
3015   if (!ParamType->isFunctionType() &&
3016       !ParamType->isFunctionPointerType() &&
3017       !ParamType->isMemberFunctionPointerType()) {
3018     if (Ovl->hasExplicitTemplateArgs()) {
3019       // But we can still look for an explicit specialization.
3020       if (FunctionDecl *ExplicitSpec
3021             = S.ResolveSingleFunctionTemplateSpecialization(Ovl))
3022         return GetTypeOfFunction(S, R, ExplicitSpec);
3023     }
3024
3025     return QualType();
3026   }
3027
3028   // Gather the explicit template arguments, if any.
3029   TemplateArgumentListInfo ExplicitTemplateArgs;
3030   if (Ovl->hasExplicitTemplateArgs())
3031     Ovl->getExplicitTemplateArgs().copyInto(ExplicitTemplateArgs);
3032   QualType Match;
3033   for (UnresolvedSetIterator I = Ovl->decls_begin(),
3034          E = Ovl->decls_end(); I != E; ++I) {
3035     NamedDecl *D = (*I)->getUnderlyingDecl();
3036
3037     if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
3038       //   - If the argument is an overload set containing one or more
3039       //     function templates, the parameter is treated as a
3040       //     non-deduced context.
3041       if (!Ovl->hasExplicitTemplateArgs())
3042         return QualType();
3043
3044       // Otherwise, see if we can resolve a function type
3045       FunctionDecl *Specialization = nullptr;
3046       TemplateDeductionInfo Info(Ovl->getNameLoc());
3047       if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
3048                                     Specialization, Info))
3049         continue;
3050
3051       D = Specialization;
3052     }
3053
3054     FunctionDecl *Fn = cast<FunctionDecl>(D);
3055     QualType ArgType = GetTypeOfFunction(S, R, Fn);
3056     if (ArgType.isNull()) continue;
3057
3058     // Function-to-pointer conversion.
3059     if (!ParamWasReference && ParamType->isPointerType() &&
3060         ArgType->isFunctionType())
3061       ArgType = S.Context.getPointerType(ArgType);
3062
3063     //   - If the argument is an overload set (not containing function
3064     //     templates), trial argument deduction is attempted using each
3065     //     of the members of the set. If deduction succeeds for only one
3066     //     of the overload set members, that member is used as the
3067     //     argument value for the deduction. If deduction succeeds for
3068     //     more than one member of the overload set the parameter is
3069     //     treated as a non-deduced context.
3070
3071     // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
3072     //   Type deduction is done independently for each P/A pair, and
3073     //   the deduced template argument values are then combined.
3074     // So we do not reject deductions which were made elsewhere.
3075     SmallVector<DeducedTemplateArgument, 8>
3076       Deduced(TemplateParams->size());
3077     TemplateDeductionInfo Info(Ovl->getNameLoc());
3078     Sema::TemplateDeductionResult Result
3079       = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3080                                            ArgType, Info, Deduced, TDF);
3081     if (Result) continue;
3082     if (!Match.isNull()) return QualType();
3083     Match = ArgType;
3084   }
3085
3086   return Match;
3087 }
3088
3089 /// \brief Perform the adjustments to the parameter and argument types
3090 /// described in C++ [temp.deduct.call].
3091 ///
3092 /// \returns true if the caller should not attempt to perform any template
3093 /// argument deduction based on this P/A pair because the argument is an
3094 /// overloaded function set that could not be resolved.
3095 static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
3096                                           TemplateParameterList *TemplateParams,
3097                                                       QualType &ParamType,
3098                                                       QualType &ArgType,
3099                                                       Expr *Arg,
3100                                                       unsigned &TDF) {
3101   // C++0x [temp.deduct.call]p3:
3102   //   If P is a cv-qualified type, the top level cv-qualifiers of P's type
3103   //   are ignored for type deduction.
3104   if (ParamType.hasQualifiers())
3105     ParamType = ParamType.getUnqualifiedType();
3106
3107   //   [...] If P is a reference type, the type referred to by P is
3108   //   used for type deduction.
3109   const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
3110   if (ParamRefType)
3111     ParamType = ParamRefType->getPointeeType();
3112
3113   // Overload sets usually make this parameter an undeduced context,
3114   // but there are sometimes special circumstances.  Typically
3115   // involving a template-id-expr.
3116   if (ArgType == S.Context.OverloadTy) {
3117     ArgType = ResolveOverloadForDeduction(S, TemplateParams,
3118                                           Arg, ParamType,
3119                                           ParamRefType != nullptr);
3120     if (ArgType.isNull())
3121       return true;
3122   }
3123
3124   if (ParamRefType) {
3125     // If the argument has incomplete array type, try to complete its type.
3126     if (ArgType->isIncompleteArrayType() && !S.RequireCompleteExprType(Arg, 0))
3127       ArgType = Arg->getType();
3128
3129     // C++0x [temp.deduct.call]p3:
3130     //   If P is an rvalue reference to a cv-unqualified template
3131     //   parameter and the argument is an lvalue, the type "lvalue
3132     //   reference to A" is used in place of A for type deduction.
3133     if (ParamRefType->isRValueReferenceType() &&
3134         !ParamType.getQualifiers() &&
3135         isa<TemplateTypeParmType>(ParamType) &&
3136         Arg->isLValue())
3137       ArgType = S.Context.getLValueReferenceType(ArgType);
3138   } else {
3139     // C++ [temp.deduct.call]p2:
3140     //   If P is not a reference type:
3141     //   - If A is an array type, the pointer type produced by the
3142     //     array-to-pointer standard conversion (4.2) is used in place of
3143     //     A for type deduction; otherwise,
3144     if (ArgType->isArrayType())
3145       ArgType = S.Context.getArrayDecayedType(ArgType);
3146     //   - If A is a function type, the pointer type produced by the
3147     //     function-to-pointer standard conversion (4.3) is used in place
3148     //     of A for type deduction; otherwise,
3149     else if (ArgType->isFunctionType())
3150       ArgType = S.Context.getPointerType(ArgType);
3151     else {
3152       // - If A is a cv-qualified type, the top level cv-qualifiers of A's
3153       //   type are ignored for type deduction.
3154       ArgType = ArgType.getUnqualifiedType();
3155     }
3156   }
3157
3158   // C++0x [temp.deduct.call]p4:
3159   //   In general, the deduction process attempts to find template argument
3160   //   values that will make the deduced A identical to A (after the type A
3161   //   is transformed as described above). [...]
3162   TDF = TDF_SkipNonDependent;
3163
3164   //     - If the original P is a reference type, the deduced A (i.e., the
3165   //       type referred to by the reference) can be more cv-qualified than
3166   //       the transformed A.
3167   if (ParamRefType)
3168     TDF |= TDF_ParamWithReferenceType;
3169   //     - The transformed A can be another pointer or pointer to member
3170   //       type that can be converted to the deduced A via a qualification
3171   //       conversion (4.4).
3172   if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
3173       ArgType->isObjCObjectPointerType())
3174     TDF |= TDF_IgnoreQualifiers;
3175   //     - If P is a class and P has the form simple-template-id, then the
3176   //       transformed A can be a derived class of the deduced A. Likewise,
3177   //       if P is a pointer to a class of the form simple-template-id, the
3178   //       transformed A can be a pointer to a derived class pointed to by
3179   //       the deduced A.
3180   if (isSimpleTemplateIdType(ParamType) ||
3181       (isa<PointerType>(ParamType) &&
3182        isSimpleTemplateIdType(
3183                               ParamType->getAs<PointerType>()->getPointeeType())))
3184     TDF |= TDF_DerivedClass;
3185
3186   return false;
3187 }
3188
3189 static bool
3190 hasDeducibleTemplateParameters(Sema &S, FunctionTemplateDecl *FunctionTemplate,
3191                                QualType T);
3192
3193 /// \brief Perform template argument deduction by matching a parameter type
3194 ///        against a single expression, where the expression is an element of
3195 ///        an initializer list that was originally matched against a parameter
3196 ///        of type \c initializer_list\<ParamType\>.
3197 static Sema::TemplateDeductionResult
3198 DeduceTemplateArgumentByListElement(Sema &S,
3199                                     TemplateParameterList *TemplateParams,
3200                                     QualType ParamType, Expr *Arg,
3201                                     TemplateDeductionInfo &Info,
3202                               SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3203                                     unsigned TDF) {
3204   // Handle the case where an init list contains another init list as the
3205   // element.
3206   if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3207     QualType X;
3208     if (!S.isStdInitializerList(ParamType.getNonReferenceType(), &X))
3209       return Sema::TDK_Success; // Just ignore this expression.
3210
3211     // Recurse down into the init list.
3212     for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) {
3213       if (Sema::TemplateDeductionResult Result =
3214             DeduceTemplateArgumentByListElement(S, TemplateParams, X,
3215                                                  ILE->getInit(i),
3216                                                  Info, Deduced, TDF))
3217         return Result;
3218     }
3219     return Sema::TDK_Success;
3220   }
3221
3222   // For all other cases, just match by type.
3223   QualType ArgType = Arg->getType();
3224   if (AdjustFunctionParmAndArgTypesForDeduction(S, TemplateParams, ParamType,
3225                                                 ArgType, Arg, TDF)) {
3226     Info.Expression = Arg;
3227     return Sema::TDK_FailedOverloadResolution;
3228   }
3229   return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3230                                             ArgType, Info, Deduced, TDF);
3231 }
3232
3233 /// \brief Perform template argument deduction from a function call
3234 /// (C++ [temp.deduct.call]).
3235 ///
3236 /// \param FunctionTemplate the function template for which we are performing
3237 /// template argument deduction.
3238 ///
3239 /// \param ExplicitTemplateArgs the explicit template arguments provided
3240 /// for this call.
3241 ///
3242 /// \param Args the function call arguments
3243 ///
3244 /// \param Specialization if template argument deduction was successful,
3245 /// this will be set to the function template specialization produced by
3246 /// template argument deduction.
3247 ///
3248 /// \param Info the argument will be updated to provide additional information
3249 /// about template argument deduction.
3250 ///
3251 /// \returns the result of template argument deduction.
3252 Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
3253     FunctionTemplateDecl *FunctionTemplate,
3254     TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args,
3255     FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
3256     bool PartialOverloading) {
3257   if (FunctionTemplate->isInvalidDecl())
3258     return TDK_Invalid;
3259
3260   FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3261   unsigned NumParams = Function->getNumParams();
3262
3263   // C++ [temp.deduct.call]p1:
3264   //   Template argument deduction is done by comparing each function template
3265   //   parameter type (call it P) with the type of the corresponding argument
3266   //   of the call (call it A) as described below.
3267   unsigned CheckArgs = Args.size();
3268   if (Args.size() < Function->getMinRequiredArguments() && !PartialOverloading)
3269     return TDK_TooFewArguments;
3270   else if (TooManyArguments(NumParams, Args.size(), PartialOverloading)) {
3271     const FunctionProtoType *Proto
3272       = Function->getType()->getAs<FunctionProtoType>();
3273     if (Proto->isTemplateVariadic())
3274       /* Do nothing */;
3275     else if (Proto->isVariadic())
3276       CheckArgs = NumParams;
3277     else
3278       return TDK_TooManyArguments;
3279   }
3280
3281   // The types of the parameters from which we will perform template argument
3282   // deduction.
3283   LocalInstantiationScope InstScope(*this);
3284   TemplateParameterList *TemplateParams
3285     = FunctionTemplate->getTemplateParameters();
3286   SmallVector<DeducedTemplateArgument, 4> Deduced;
3287   SmallVector<QualType, 4> ParamTypes;
3288   unsigned NumExplicitlySpecified = 0;
3289   if (ExplicitTemplateArgs) {
3290     TemplateDeductionResult Result =
3291       SubstituteExplicitTemplateArguments(FunctionTemplate,
3292                                           *ExplicitTemplateArgs,
3293                                           Deduced,
3294                                           ParamTypes,
3295                                           nullptr,
3296                                           Info);
3297     if (Result)
3298       return Result;
3299
3300     NumExplicitlySpecified = Deduced.size();
3301   } else {
3302     // Just fill in the parameter types from the function declaration.
3303     for (unsigned I = 0; I != NumParams; ++I)
3304       ParamTypes.push_back(Function->getParamDecl(I)->getType());
3305   }
3306
3307   // Deduce template arguments from the function parameters.
3308   Deduced.resize(TemplateParams->size());
3309   unsigned ArgIdx = 0;
3310   SmallVector<OriginalCallArg, 4> OriginalCallArgs;
3311   for (unsigned ParamIdx = 0, NumParamTypes = ParamTypes.size();
3312        ParamIdx != NumParamTypes; ++ParamIdx) {
3313     QualType OrigParamType = ParamTypes[ParamIdx];
3314     QualType ParamType = OrigParamType;
3315
3316     const PackExpansionType *ParamExpansion
3317       = dyn_cast<PackExpansionType>(ParamType);
3318     if (!ParamExpansion) {
3319       // Simple case: matching a function parameter to a function argument.
3320       if (ArgIdx >= CheckArgs)
3321         break;
3322
3323       Expr *Arg = Args[ArgIdx++];
3324       QualType ArgType = Arg->getType();
3325
3326       unsigned TDF = 0;
3327       if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
3328                                                     ParamType, ArgType, Arg,
3329                                                     TDF))
3330         continue;
3331
3332       // If we have nothing to deduce, we're done.
3333       if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3334         continue;
3335
3336       // If the argument is an initializer list ...
3337       if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3338         // ... then the parameter is an undeduced context, unless the parameter
3339         // type is (reference to cv) std::initializer_list<P'>, in which case
3340         // deduction is done for each element of the initializer list, and the
3341         // result is the deduced type if it's the same for all elements.
3342         QualType X;
3343         // Removing references was already done.
3344         if (!isStdInitializerList(ParamType, &X))
3345           continue;
3346
3347         for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) {
3348           if (TemplateDeductionResult Result =
3349                 DeduceTemplateArgumentByListElement(*this, TemplateParams, X,
3350                                                      ILE->getInit(i),
3351                                                      Info, Deduced, TDF))
3352             return Result;
3353         }
3354         // Don't track the argument type, since an initializer list has none.
3355         continue;
3356       }
3357
3358       // Keep track of the argument type and corresponding parameter index,
3359       // so we can check for compatibility between the deduced A and A.
3360       OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx-1,
3361                                                  ArgType));
3362
3363       if (TemplateDeductionResult Result
3364             = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3365                                                  ParamType, ArgType,
3366                                                  Info, Deduced, TDF))
3367         return Result;
3368
3369       continue;
3370     }
3371
3372     // C++0x [temp.deduct.call]p1:
3373     //   For a function parameter pack that occurs at the end of the
3374     //   parameter-declaration-list, the type A of each remaining argument of
3375     //   the call is compared with the type P of the declarator-id of the
3376     //   function parameter pack. Each comparison deduces template arguments
3377     //   for subsequent positions in the template parameter packs expanded by
3378     //   the function parameter pack. For a function parameter pack that does
3379     //   not occur at the end of the parameter-declaration-list, the type of
3380     //   the parameter pack is a non-deduced context.
3381     if (ParamIdx + 1 < NumParamTypes)
3382       break;
3383
3384     QualType ParamPattern = ParamExpansion->getPattern();
3385     PackDeductionScope PackScope(*this, TemplateParams, Deduced, Info,
3386                                  ParamPattern);
3387
3388     bool HasAnyArguments = false;
3389     for (; ArgIdx < Args.size(); ++ArgIdx) {
3390       HasAnyArguments = true;
3391
3392       QualType OrigParamType = ParamPattern;
3393       ParamType = OrigParamType;
3394       Expr *Arg = Args[ArgIdx];
3395       QualType ArgType = Arg->getType();
3396
3397       unsigned TDF = 0;
3398       if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
3399                                                     ParamType, ArgType, Arg,
3400                                                     TDF)) {
3401         // We can't actually perform any deduction for this argument, so stop
3402         // deduction at this point.
3403         ++ArgIdx;
3404         break;
3405       }
3406
3407       // As above, initializer lists need special handling.
3408       if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3409         QualType X;
3410         if (!isStdInitializerList(ParamType, &X)) {
3411           ++ArgIdx;
3412           break;
3413         }
3414
3415         for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) {
3416           if (TemplateDeductionResult Result =
3417                 DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, X,
3418                                                    ILE->getInit(i)->getType(),
3419                                                    Info, Deduced, TDF))
3420             return Result;
3421         }
3422       } else {
3423
3424         // Keep track of the argument type and corresponding argument index,
3425         // so we can check for compatibility between the deduced A and A.
3426         if (hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3427           OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx,
3428                                                      ArgType));
3429
3430         if (TemplateDeductionResult Result
3431             = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3432                                                  ParamType, ArgType, Info,
3433                                                  Deduced, TDF))
3434           return Result;
3435       }
3436
3437       PackScope.nextPackElement();
3438     }
3439
3440     // Build argument packs for each of the parameter packs expanded by this
3441     // pack expansion.
3442     if (auto Result = PackScope.finish(HasAnyArguments))
3443       return Result;
3444
3445     // After we've matching against a parameter pack, we're done.
3446     break;
3447   }
3448
3449   return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3450                                          NumExplicitlySpecified, Specialization,
3451                                          Info, &OriginalCallArgs,
3452                                          PartialOverloading);
3453 }
3454
3455 QualType Sema::adjustCCAndNoReturn(QualType ArgFunctionType,
3456                                    QualType FunctionType) {
3457   if (ArgFunctionType.isNull())
3458     return ArgFunctionType;
3459
3460   const FunctionProtoType *FunctionTypeP =
3461       FunctionType->castAs<FunctionProtoType>();
3462   CallingConv CC = FunctionTypeP->getCallConv();
3463   bool NoReturn = FunctionTypeP->getNoReturnAttr();
3464   const FunctionProtoType *ArgFunctionTypeP =
3465       ArgFunctionType->getAs<FunctionProtoType>();
3466   if (ArgFunctionTypeP->getCallConv() == CC &&
3467       ArgFunctionTypeP->getNoReturnAttr() == NoReturn)
3468     return ArgFunctionType;
3469
3470   FunctionType::ExtInfo EI = ArgFunctionTypeP->getExtInfo().withCallingConv(CC);
3471   EI = EI.withNoReturn(NoReturn);
3472   ArgFunctionTypeP =
3473       cast<FunctionProtoType>(Context.adjustFunctionType(ArgFunctionTypeP, EI));
3474   return QualType(ArgFunctionTypeP, 0);
3475 }
3476
3477 /// \brief Deduce template arguments when taking the address of a function
3478 /// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
3479 /// a template.
3480 ///
3481 /// \param FunctionTemplate the function template for which we are performing
3482 /// template argument deduction.
3483 ///
3484 /// \param ExplicitTemplateArgs the explicitly-specified template
3485 /// arguments.
3486 ///
3487 /// \param ArgFunctionType the function type that will be used as the
3488 /// "argument" type (A) when performing template argument deduction from the
3489 /// function template's function type. This type may be NULL, if there is no
3490 /// argument type to compare against, in C++0x [temp.arg.explicit]p3.
3491 ///
3492 /// \param Specialization if template argument deduction was successful,
3493 /// this will be set to the function template specialization produced by
3494 /// template argument deduction.
3495 ///
3496 /// \param Info the argument will be updated to provide additional information
3497 /// about template argument deduction.
3498 ///
3499 /// \returns the result of template argument deduction.
3500 Sema::TemplateDeductionResult
3501 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3502                               TemplateArgumentListInfo *ExplicitTemplateArgs,
3503                               QualType ArgFunctionType,
3504                               FunctionDecl *&Specialization,
3505                               TemplateDeductionInfo &Info,
3506                               bool InOverloadResolution) {
3507   if (FunctionTemplate->isInvalidDecl())
3508     return TDK_Invalid;
3509
3510   FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3511   TemplateParameterList *TemplateParams
3512     = FunctionTemplate->getTemplateParameters();
3513   QualType FunctionType = Function->getType();
3514   if (!InOverloadResolution)
3515     ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, FunctionType);
3516
3517   // Substitute any explicit template arguments.
3518   LocalInstantiationScope InstScope(*this);
3519   SmallVector<DeducedTemplateArgument, 4> Deduced;
3520   unsigned NumExplicitlySpecified = 0;
3521   SmallVector<QualType, 4> ParamTypes;
3522   if (ExplicitTemplateArgs) {
3523     if (TemplateDeductionResult Result
3524           = SubstituteExplicitTemplateArguments(FunctionTemplate,
3525                                                 *ExplicitTemplateArgs,
3526                                                 Deduced, ParamTypes,
3527                                                 &FunctionType, Info))
3528       return Result;
3529
3530     NumExplicitlySpecified = Deduced.size();
3531   }
3532
3533   // Unevaluated SFINAE context.
3534   EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
3535   SFINAETrap Trap(*this);
3536
3537   Deduced.resize(TemplateParams->size());
3538
3539   // If the function has a deduced return type, substitute it for a dependent
3540   // type so that we treat it as a non-deduced context in what follows.
3541   bool HasDeducedReturnType = false;
3542   if (getLangOpts().CPlusPlus14 && InOverloadResolution &&
3543       Function->getReturnType()->getContainedAutoType()) {
3544     FunctionType = SubstAutoType(FunctionType, Context.DependentTy);
3545     HasDeducedReturnType = true;
3546   }
3547
3548   if (!ArgFunctionType.isNull()) {
3549     unsigned TDF = TDF_TopLevelParameterTypeList;
3550     if (InOverloadResolution) TDF |= TDF_InOverloadResolution;
3551     // Deduce template arguments from the function type.
3552     if (TemplateDeductionResult Result
3553           = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3554                                                FunctionType, ArgFunctionType,
3555                                                Info, Deduced, TDF))
3556       return Result;
3557   }
3558
3559   if (TemplateDeductionResult Result
3560         = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3561                                           NumExplicitlySpecified,
3562                                           Specialization, Info))
3563     return Result;
3564
3565   // If the function has a deduced return type, deduce it now, so we can check
3566   // that the deduced function type matches the requested type.
3567   if (HasDeducedReturnType &&
3568       Specialization->getReturnType()->isUndeducedType() &&
3569       DeduceReturnType(Specialization, Info.getLocation(), false))
3570     return TDK_MiscellaneousDeductionFailure;
3571
3572   // If the requested function type does not match the actual type of the
3573   // specialization with respect to arguments of compatible pointer to function
3574   // types, template argument deduction fails.
3575   if (!ArgFunctionType.isNull()) {
3576     if (InOverloadResolution && !isSameOrCompatibleFunctionType(
3577                            Context.getCanonicalType(Specialization->getType()),
3578                            Context.getCanonicalType(ArgFunctionType)))
3579       return TDK_MiscellaneousDeductionFailure;
3580     else if(!InOverloadResolution &&
3581             !Context.hasSameType(Specialization->getType(), ArgFunctionType))
3582       return TDK_MiscellaneousDeductionFailure;
3583   }
3584
3585   return TDK_Success;
3586 }
3587
3588 /// \brief Given a function declaration (e.g. a generic lambda conversion
3589 ///  function) that contains an 'auto' in its result type, substitute it
3590 ///  with TypeToReplaceAutoWith.  Be careful to pass in the type you want
3591 ///  to replace 'auto' with and not the actual result type you want
3592 ///  to set the function to.
3593 static inline void
3594 SubstAutoWithinFunctionReturnType(FunctionDecl *F,
3595                                     QualType TypeToReplaceAutoWith, Sema &S) {
3596   assert(!TypeToReplaceAutoWith->getContainedAutoType());
3597   QualType AutoResultType = F->getReturnType();
3598   assert(AutoResultType->getContainedAutoType());
3599   QualType DeducedResultType = S.SubstAutoType(AutoResultType,
3600                                                TypeToReplaceAutoWith);
3601   S.Context.adjustDeducedFunctionResultType(F, DeducedResultType);
3602 }
3603
3604 /// \brief Given a specialized conversion operator of a generic lambda
3605 /// create the corresponding specializations of the call operator and
3606 /// the static-invoker. If the return type of the call operator is auto,
3607 /// deduce its return type and check if that matches the
3608 /// return type of the destination function ptr.
3609
3610 static inline Sema::TemplateDeductionResult
3611 SpecializeCorrespondingLambdaCallOperatorAndInvoker(
3612     CXXConversionDecl *ConversionSpecialized,
3613     SmallVectorImpl<DeducedTemplateArgument> &DeducedArguments,
3614     QualType ReturnTypeOfDestFunctionPtr,
3615     TemplateDeductionInfo &TDInfo,
3616     Sema &S) {
3617
3618   CXXRecordDecl *LambdaClass = ConversionSpecialized->getParent();
3619   assert(LambdaClass && LambdaClass->isGenericLambda());
3620
3621   CXXMethodDecl *CallOpGeneric = LambdaClass->getLambdaCallOperator();
3622   QualType CallOpResultType = CallOpGeneric->getReturnType();
3623   const bool GenericLambdaCallOperatorHasDeducedReturnType =
3624       CallOpResultType->getContainedAutoType();
3625
3626   FunctionTemplateDecl *CallOpTemplate =
3627       CallOpGeneric->getDescribedFunctionTemplate();
3628
3629   FunctionDecl *CallOpSpecialized = nullptr;
3630   // Use the deduced arguments of the conversion function, to specialize our
3631   // generic lambda's call operator.
3632   if (Sema::TemplateDeductionResult Result
3633       = S.FinishTemplateArgumentDeduction(CallOpTemplate,
3634                                           DeducedArguments,
3635                                           0, CallOpSpecialized, TDInfo))
3636     return Result;
3637
3638   // If we need to deduce the return type, do so (instantiates the callop).
3639   if (GenericLambdaCallOperatorHasDeducedReturnType &&
3640       CallOpSpecialized->getReturnType()->isUndeducedType())
3641     S.DeduceReturnType(CallOpSpecialized,
3642                        CallOpSpecialized->getPointOfInstantiation(),
3643                        /*Diagnose*/ true);
3644
3645   // Check to see if the return type of the destination ptr-to-function
3646   // matches the return type of the call operator.
3647   if (!S.Context.hasSameType(CallOpSpecialized->getReturnType(),
3648                              ReturnTypeOfDestFunctionPtr))
3649     return Sema::TDK_NonDeducedMismatch;
3650   // Since we have succeeded in matching the source and destination
3651   // ptr-to-functions (now including return type), and have successfully
3652   // specialized our corresponding call operator, we are ready to
3653   // specialize the static invoker with the deduced arguments of our
3654   // ptr-to-function.
3655   FunctionDecl *InvokerSpecialized = nullptr;
3656   FunctionTemplateDecl *InvokerTemplate = LambdaClass->
3657                   getLambdaStaticInvoker()->getDescribedFunctionTemplate();
3658
3659 #ifndef NDEBUG
3660   Sema::TemplateDeductionResult LLVM_ATTRIBUTE_UNUSED Result =
3661 #endif
3662     S.FinishTemplateArgumentDeduction(InvokerTemplate, DeducedArguments, 0,
3663           InvokerSpecialized, TDInfo);
3664   assert(Result == Sema::TDK_Success &&
3665     "If the call operator succeeded so should the invoker!");
3666   // Set the result type to match the corresponding call operator
3667   // specialization's result type.
3668   if (GenericLambdaCallOperatorHasDeducedReturnType &&
3669       InvokerSpecialized->getReturnType()->isUndeducedType()) {
3670     // Be sure to get the type to replace 'auto' with and not
3671     // the full result type of the call op specialization
3672     // to substitute into the 'auto' of the invoker and conversion
3673     // function.
3674     // For e.g.
3675     //  int* (*fp)(int*) = [](auto* a) -> auto* { return a; };
3676     // We don't want to subst 'int*' into 'auto' to get int**.
3677
3678     QualType TypeToReplaceAutoWith = CallOpSpecialized->getReturnType()
3679                                          ->getContainedAutoType()
3680                                          ->getDeducedType();
3681     SubstAutoWithinFunctionReturnType(InvokerSpecialized,
3682         TypeToReplaceAutoWith, S);
3683     SubstAutoWithinFunctionReturnType(ConversionSpecialized,
3684         TypeToReplaceAutoWith, S);
3685   }
3686
3687   // Ensure that static invoker doesn't have a const qualifier.
3688   // FIXME: When creating the InvokerTemplate in SemaLambda.cpp
3689   // do not use the CallOperator's TypeSourceInfo which allows
3690   // the const qualifier to leak through.
3691   const FunctionProtoType *InvokerFPT = InvokerSpecialized->
3692                   getType().getTypePtr()->castAs<FunctionProtoType>();
3693   FunctionProtoType::ExtProtoInfo EPI = InvokerFPT->getExtProtoInfo();
3694   EPI.TypeQuals = 0;
3695   InvokerSpecialized->setType(S.Context.getFunctionType(
3696       InvokerFPT->getReturnType(), InvokerFPT->getParamTypes(), EPI));
3697   return Sema::TDK_Success;
3698 }
3699 /// \brief Deduce template arguments for a templated conversion
3700 /// function (C++ [temp.deduct.conv]) and, if successful, produce a
3701 /// conversion function template specialization.
3702 Sema::TemplateDeductionResult
3703 Sema::DeduceTemplateArguments(FunctionTemplateDecl *ConversionTemplate,
3704                               QualType ToType,
3705                               CXXConversionDecl *&Specialization,
3706                               TemplateDeductionInfo &Info) {
3707   if (ConversionTemplate->isInvalidDecl())
3708     return TDK_Invalid;
3709
3710   CXXConversionDecl *ConversionGeneric
3711     = cast<CXXConversionDecl>(ConversionTemplate->getTemplatedDecl());
3712
3713   QualType FromType = ConversionGeneric->getConversionType();
3714
3715   // Canonicalize the types for deduction.
3716   QualType P = Context.getCanonicalType(FromType);
3717   QualType A = Context.getCanonicalType(ToType);
3718
3719   // C++0x [temp.deduct.conv]p2:
3720   //   If P is a reference type, the type referred to by P is used for
3721   //   type deduction.
3722   if (const ReferenceType *PRef = P->getAs<ReferenceType>())
3723     P = PRef->getPointeeType();
3724
3725   // C++0x [temp.deduct.conv]p4:
3726   //   [...] If A is a reference type, the type referred to by A is used
3727   //   for type deduction.
3728   if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3729     A = ARef->getPointeeType().getUnqualifiedType();
3730   // C++ [temp.deduct.conv]p3:
3731   //
3732   //   If A is not a reference type:
3733   else {
3734     assert(!A->isReferenceType() && "Reference types were handled above");
3735
3736     //   - If P is an array type, the pointer type produced by the
3737     //     array-to-pointer standard conversion (4.2) is used in place
3738     //     of P for type deduction; otherwise,
3739     if (P->isArrayType())
3740       P = Context.getArrayDecayedType(P);
3741     //   - If P is a function type, the pointer type produced by the
3742     //     function-to-pointer standard conversion (4.3) is used in
3743     //     place of P for type deduction; otherwise,
3744     else if (P->isFunctionType())
3745       P = Context.getPointerType(P);
3746     //   - If P is a cv-qualified type, the top level cv-qualifiers of
3747     //     P's type are ignored for type deduction.
3748     else
3749       P = P.getUnqualifiedType();
3750
3751     // C++0x [temp.deduct.conv]p4:
3752     //   If A is a cv-qualified type, the top level cv-qualifiers of A's
3753     //   type are ignored for type deduction. If A is a reference type, the type
3754     //   referred to by A is used for type deduction.
3755     A = A.getUnqualifiedType();
3756   }
3757
3758   // Unevaluated SFINAE context.
3759   EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
3760   SFINAETrap Trap(*this);
3761
3762   // C++ [temp.deduct.conv]p1:
3763   //   Template argument deduction is done by comparing the return
3764   //   type of the template conversion function (call it P) with the
3765   //   type that is required as the result of the conversion (call it
3766   //   A) as described in 14.8.2.4.
3767   TemplateParameterList *TemplateParams
3768     = ConversionTemplate->getTemplateParameters();
3769   SmallVector<DeducedTemplateArgument, 4> Deduced;
3770   Deduced.resize(TemplateParams->size());
3771
3772   // C++0x [temp.deduct.conv]p4:
3773   //   In general, the deduction process attempts to find template
3774   //   argument values that will make the deduced A identical to
3775   //   A. However, there are two cases that allow a difference:
3776   unsigned TDF = 0;
3777   //     - If the original A is a reference type, A can be more
3778   //       cv-qualified than the deduced A (i.e., the type referred to
3779   //       by the reference)
3780   if (ToType->isReferenceType())
3781     TDF |= TDF_ParamWithReferenceType;
3782   //     - The deduced A can be another pointer or pointer to member
3783   //       type that can be converted to A via a qualification
3784   //       conversion.
3785   //
3786   // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
3787   // both P and A are pointers or member pointers. In this case, we
3788   // just ignore cv-qualifiers completely).
3789   if ((P->isPointerType() && A->isPointerType()) ||
3790       (P->isMemberPointerType() && A->isMemberPointerType()))
3791     TDF |= TDF_IgnoreQualifiers;
3792   if (TemplateDeductionResult Result
3793         = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3794                                              P, A, Info, Deduced, TDF))
3795     return Result;
3796
3797   // Create an Instantiation Scope for finalizing the operator.
3798   LocalInstantiationScope InstScope(*this);
3799   // Finish template argument deduction.
3800   FunctionDecl *ConversionSpecialized = nullptr;
3801   TemplateDeductionResult Result
3802       = FinishTemplateArgumentDeduction(ConversionTemplate, Deduced, 0,
3803                                         ConversionSpecialized, Info);
3804   Specialization = cast_or_null<CXXConversionDecl>(ConversionSpecialized);
3805
3806   // If the conversion operator is being invoked on a lambda closure to convert
3807   // to a ptr-to-function, use the deduced arguments from the conversion
3808   // function to specialize the corresponding call operator.
3809   //   e.g., int (*fp)(int) = [](auto a) { return a; };
3810   if (Result == TDK_Success && isLambdaConversionOperator(ConversionGeneric)) {
3811
3812     // Get the return type of the destination ptr-to-function we are converting
3813     // to.  This is necessary for matching the lambda call operator's return
3814     // type to that of the destination ptr-to-function's return type.
3815     assert(A->isPointerType() &&
3816         "Can only convert from lambda to ptr-to-function");
3817     const FunctionType *ToFunType =
3818         A->getPointeeType().getTypePtr()->getAs<FunctionType>();
3819     const QualType DestFunctionPtrReturnType = ToFunType->getReturnType();
3820
3821     // Create the corresponding specializations of the call operator and
3822     // the static-invoker; and if the return type is auto,
3823     // deduce the return type and check if it matches the
3824     // DestFunctionPtrReturnType.
3825     // For instance:
3826     //   auto L = [](auto a) { return f(a); };
3827     //   int (*fp)(int) = L;
3828     //   char (*fp2)(int) = L; <-- Not OK.
3829
3830     Result = SpecializeCorrespondingLambdaCallOperatorAndInvoker(
3831         Specialization, Deduced, DestFunctionPtrReturnType,
3832         Info, *this);
3833   }
3834   return Result;
3835 }
3836
3837 /// \brief Deduce template arguments for a function template when there is
3838 /// nothing to deduce against (C++0x [temp.arg.explicit]p3).
3839 ///
3840 /// \param FunctionTemplate the function template for which we are performing
3841 /// template argument deduction.
3842 ///
3843 /// \param ExplicitTemplateArgs the explicitly-specified template
3844 /// arguments.
3845 ///
3846 /// \param Specialization if template argument deduction was successful,
3847 /// this will be set to the function template specialization produced by
3848 /// template argument deduction.
3849 ///
3850 /// \param Info the argument will be updated to provide additional information
3851 /// about template argument deduction.
3852 ///
3853 /// \returns the result of template argument deduction.
3854 Sema::TemplateDeductionResult
3855 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3856                               TemplateArgumentListInfo *ExplicitTemplateArgs,
3857                               FunctionDecl *&Specialization,
3858                               TemplateDeductionInfo &Info,
3859                               bool InOverloadResolution) {
3860   return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
3861                                  QualType(), Specialization, Info,
3862                                  InOverloadResolution);
3863 }
3864
3865 namespace {
3866   /// Substitute the 'auto' type specifier within a type for a given replacement
3867   /// type.
3868   class SubstituteAutoTransform :
3869     public TreeTransform<SubstituteAutoTransform> {
3870     QualType Replacement;
3871   public:
3872     SubstituteAutoTransform(Sema &SemaRef, QualType Replacement)
3873         : TreeTransform<SubstituteAutoTransform>(SemaRef),
3874           Replacement(Replacement) {}
3875
3876     QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
3877       // If we're building the type pattern to deduce against, don't wrap the
3878       // substituted type in an AutoType. Certain template deduction rules
3879       // apply only when a template type parameter appears directly (and not if
3880       // the parameter is found through desugaring). For instance:
3881       //   auto &&lref = lvalue;
3882       // must transform into "rvalue reference to T" not "rvalue reference to
3883       // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
3884       if (!Replacement.isNull() && isa<TemplateTypeParmType>(Replacement)) {
3885         QualType Result = Replacement;
3886         TemplateTypeParmTypeLoc NewTL =
3887           TLB.push<TemplateTypeParmTypeLoc>(Result);
3888         NewTL.setNameLoc(TL.getNameLoc());
3889         return Result;
3890       } else {
3891         bool Dependent =
3892           !Replacement.isNull() && Replacement->isDependentType();
3893         QualType Result =
3894           SemaRef.Context.getAutoType(Dependent ? QualType() : Replacement,
3895                                       TL.getTypePtr()->isDecltypeAuto(),
3896                                       Dependent);
3897         AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result);
3898         NewTL.setNameLoc(TL.getNameLoc());
3899         return Result;
3900       }
3901     }
3902
3903     ExprResult TransformLambdaExpr(LambdaExpr *E) {
3904       // Lambdas never need to be transformed.
3905       return E;
3906     }
3907
3908     QualType Apply(TypeLoc TL) {
3909       // Create some scratch storage for the transformed type locations.
3910       // FIXME: We're just going to throw this information away. Don't build it.
3911       TypeLocBuilder TLB;
3912       TLB.reserve(TL.getFullDataSize());
3913       return TransformType(TLB, TL);
3914     }
3915   };
3916 }
3917
3918 Sema::DeduceAutoResult
3919 Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result) {
3920   return DeduceAutoType(Type->getTypeLoc(), Init, Result);
3921 }
3922
3923 /// \brief Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6)
3924 ///
3925 /// \param Type the type pattern using the auto type-specifier.
3926 /// \param Init the initializer for the variable whose type is to be deduced.
3927 /// \param Result if type deduction was successful, this will be set to the
3928 ///        deduced type.
3929 Sema::DeduceAutoResult
3930 Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
3931   if (Init->getType()->isNonOverloadPlaceholderType()) {
3932     ExprResult NonPlaceholder = CheckPlaceholderExpr(Init);
3933     if (NonPlaceholder.isInvalid())
3934       return DAR_FailedAlreadyDiagnosed;
3935     Init = NonPlaceholder.get();
3936   }
3937
3938   if (Init->isTypeDependent() || Type.getType()->isDependentType()) {
3939     Result = SubstituteAutoTransform(*this, Context.DependentTy).Apply(Type);
3940     assert(!Result.isNull() && "substituting DependentTy can't fail");
3941     return DAR_Succeeded;
3942   }
3943
3944   // If this is a 'decltype(auto)' specifier, do the decltype dance.
3945   // Since 'decltype(auto)' can only occur at the top of the type, we
3946   // don't need to go digging for it.
3947   if (const AutoType *AT = Type.getType()->getAs<AutoType>()) {
3948     if (AT->isDecltypeAuto()) {
3949       if (isa<InitListExpr>(Init)) {
3950         Diag(Init->getLocStart(), diag::err_decltype_auto_initializer_list);
3951         return DAR_FailedAlreadyDiagnosed;
3952       }
3953
3954       QualType Deduced = BuildDecltypeType(Init, Init->getLocStart(), false);
3955       // FIXME: Support a non-canonical deduced type for 'auto'.
3956       Deduced = Context.getCanonicalType(Deduced);
3957       Result = SubstituteAutoTransform(*this, Deduced).Apply(Type);
3958       if (Result.isNull())
3959         return DAR_FailedAlreadyDiagnosed;
3960       return DAR_Succeeded;
3961     }
3962   }
3963
3964   SourceLocation Loc = Init->getExprLoc();
3965
3966   LocalInstantiationScope InstScope(*this);
3967
3968   // Build template<class TemplParam> void Func(FuncParam);
3969   TemplateTypeParmDecl *TemplParam =
3970     TemplateTypeParmDecl::Create(Context, nullptr, SourceLocation(), Loc, 0, 0,
3971                                  nullptr, false, false);
3972   QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
3973   NamedDecl *TemplParamPtr = TemplParam;
3974   FixedSizeTemplateParameterList<1> TemplateParams(Loc, Loc, &TemplParamPtr,
3975                                                    Loc);
3976
3977   QualType FuncParam = SubstituteAutoTransform(*this, TemplArg).Apply(Type);
3978   assert(!FuncParam.isNull() &&
3979          "substituting template parameter for 'auto' failed");
3980
3981   // Deduce type of TemplParam in Func(Init)
3982   SmallVector<DeducedTemplateArgument, 1> Deduced;
3983   Deduced.resize(1);
3984   QualType InitType = Init->getType();
3985   unsigned TDF = 0;
3986
3987   TemplateDeductionInfo Info(Loc);
3988
3989   InitListExpr *InitList = dyn_cast<InitListExpr>(Init);
3990   if (InitList) {
3991     for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) {
3992       if (DeduceTemplateArgumentByListElement(*this, &TemplateParams,
3993                                               TemplArg,
3994                                               InitList->getInit(i),
3995                                               Info, Deduced, TDF))
3996         return DAR_Failed;
3997     }
3998   } else {
3999     if (AdjustFunctionParmAndArgTypesForDeduction(*this, &TemplateParams,
4000                                                   FuncParam, InitType, Init,
4001                                                   TDF))
4002       return DAR_Failed;
4003
4004     if (DeduceTemplateArgumentsByTypeMatch(*this, &TemplateParams, FuncParam,
4005                                            InitType, Info, Deduced, TDF))
4006       return DAR_Failed;
4007   }
4008
4009   if (Deduced[0].getKind() != TemplateArgument::Type)
4010     return DAR_Failed;
4011
4012   QualType DeducedType = Deduced[0].getAsType();
4013
4014   if (InitList) {
4015     DeducedType = BuildStdInitializerList(DeducedType, Loc);
4016     if (DeducedType.isNull())
4017       return DAR_FailedAlreadyDiagnosed;
4018   }
4019
4020   Result = SubstituteAutoTransform(*this, DeducedType).Apply(Type);
4021   if (Result.isNull())
4022    return DAR_FailedAlreadyDiagnosed;
4023
4024   // Check that the deduced argument type is compatible with the original
4025   // argument type per C++ [temp.deduct.call]p4.
4026   if (!InitList && !Result.isNull() &&
4027       CheckOriginalCallArgDeduction(*this,
4028                                     Sema::OriginalCallArg(FuncParam,0,InitType),
4029                                     Result)) {
4030     Result = QualType();
4031     return DAR_Failed;
4032   }
4033
4034   return DAR_Succeeded;
4035 }
4036
4037 QualType Sema::SubstAutoType(QualType TypeWithAuto,
4038                              QualType TypeToReplaceAuto) {
4039   return SubstituteAutoTransform(*this, TypeToReplaceAuto).
4040                TransformType(TypeWithAuto);
4041 }
4042
4043 TypeSourceInfo* Sema::SubstAutoTypeSourceInfo(TypeSourceInfo *TypeWithAuto,
4044                              QualType TypeToReplaceAuto) {
4045     return SubstituteAutoTransform(*this, TypeToReplaceAuto).
4046                TransformType(TypeWithAuto);
4047 }
4048
4049 void Sema::DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init) {
4050   if (isa<InitListExpr>(Init))
4051     Diag(VDecl->getLocation(),
4052          VDecl->isInitCapture()
4053              ? diag::err_init_capture_deduction_failure_from_init_list
4054              : diag::err_auto_var_deduction_failure_from_init_list)
4055       << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange();
4056   else
4057     Diag(VDecl->getLocation(),
4058          VDecl->isInitCapture() ? diag::err_init_capture_deduction_failure
4059                                 : diag::err_auto_var_deduction_failure)
4060       << VDecl->getDeclName() << VDecl->getType() << Init->getType()
4061       << Init->getSourceRange();
4062 }
4063
4064 bool Sema::DeduceReturnType(FunctionDecl *FD, SourceLocation Loc,
4065                             bool Diagnose) {
4066   assert(FD->getReturnType()->isUndeducedType());
4067
4068   if (FD->getTemplateInstantiationPattern())
4069     InstantiateFunctionDefinition(Loc, FD);
4070
4071   bool StillUndeduced = FD->getReturnType()->isUndeducedType();
4072   if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) {
4073     Diag(Loc, diag::err_auto_fn_used_before_defined) << FD;
4074     Diag(FD->getLocation(), diag::note_callee_decl) << FD;
4075   }
4076
4077   return StillUndeduced;
4078 }
4079
4080 static void
4081 MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
4082                            bool OnlyDeduced,
4083                            unsigned Level,
4084                            llvm::SmallBitVector &Deduced);
4085
4086 /// \brief If this is a non-static member function,
4087 static void
4088 AddImplicitObjectParameterType(ASTContext &Context,
4089                                CXXMethodDecl *Method,
4090                                SmallVectorImpl<QualType> &ArgTypes) {
4091   // C++11 [temp.func.order]p3:
4092   //   [...] The new parameter is of type "reference to cv A," where cv are
4093   //   the cv-qualifiers of the function template (if any) and A is
4094   //   the class of which the function template is a member.
4095   //
4096   // The standard doesn't say explicitly, but we pick the appropriate kind of
4097   // reference type based on [over.match.funcs]p4.
4098   QualType ArgTy = Context.getTypeDeclType(Method->getParent());
4099   ArgTy = Context.getQualifiedType(ArgTy,
4100                         Qualifiers::fromCVRMask(Method->getTypeQualifiers()));
4101   if (Method->getRefQualifier() == RQ_RValue)
4102     ArgTy = Context.getRValueReferenceType(ArgTy);
4103   else
4104     ArgTy = Context.getLValueReferenceType(ArgTy);
4105   ArgTypes.push_back(ArgTy);
4106 }
4107
4108 /// \brief Determine whether the function template \p FT1 is at least as
4109 /// specialized as \p FT2.
4110 static bool isAtLeastAsSpecializedAs(Sema &S,
4111                                      SourceLocation Loc,
4112                                      FunctionTemplateDecl *FT1,
4113                                      FunctionTemplateDecl *FT2,
4114                                      TemplatePartialOrderingContext TPOC,
4115                                      unsigned NumCallArguments1) {
4116   FunctionDecl *FD1 = FT1->getTemplatedDecl();
4117   FunctionDecl *FD2 = FT2->getTemplatedDecl();
4118   const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>();
4119   const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>();
4120
4121   assert(Proto1 && Proto2 && "Function templates must have prototypes");
4122   TemplateParameterList *TemplateParams = FT2->getTemplateParameters();
4123   SmallVector<DeducedTemplateArgument, 4> Deduced;
4124   Deduced.resize(TemplateParams->size());
4125
4126   // C++0x [temp.deduct.partial]p3:
4127   //   The types used to determine the ordering depend on the context in which
4128   //   the partial ordering is done:
4129   TemplateDeductionInfo Info(Loc);
4130   SmallVector<QualType, 4> Args2;
4131   switch (TPOC) {
4132   case TPOC_Call: {
4133     //   - In the context of a function call, the function parameter types are
4134     //     used.
4135     CXXMethodDecl *Method1 = dyn_cast<CXXMethodDecl>(FD1);
4136     CXXMethodDecl *Method2 = dyn_cast<CXXMethodDecl>(FD2);
4137
4138     // C++11 [temp.func.order]p3:
4139     //   [...] If only one of the function templates is a non-static
4140     //   member, that function template is considered to have a new
4141     //   first parameter inserted in its function parameter list. The
4142     //   new parameter is of type "reference to cv A," where cv are
4143     //   the cv-qualifiers of the function template (if any) and A is
4144     //   the class of which the function template is a member.
4145     //
4146     // Note that we interpret this to mean "if one of the function
4147     // templates is a non-static member and the other is a non-member";
4148     // otherwise, the ordering rules for static functions against non-static
4149     // functions don't make any sense.
4150     //
4151     // C++98/03 doesn't have this provision but we've extended DR532 to cover
4152     // it as wording was broken prior to it.
4153     SmallVector<QualType, 4> Args1;
4154
4155     unsigned NumComparedArguments = NumCallArguments1;
4156
4157     if (!Method2 && Method1 && !Method1->isStatic()) {
4158       // Compare 'this' from Method1 against first parameter from Method2.
4159       AddImplicitObjectParameterType(S.Context, Method1, Args1);
4160       ++NumComparedArguments;
4161     } else if (!Method1 && Method2 && !Method2->isStatic()) {
4162       // Compare 'this' from Method2 against first parameter from Method1.
4163       AddImplicitObjectParameterType(S.Context, Method2, Args2);
4164     }
4165
4166     Args1.insert(Args1.end(), Proto1->param_type_begin(),
4167                  Proto1->param_type_end());
4168     Args2.insert(Args2.end(), Proto2->param_type_begin(),
4169                  Proto2->param_type_end());
4170
4171     // C++ [temp.func.order]p5:
4172     //   The presence of unused ellipsis and default arguments has no effect on
4173     //   the partial ordering of function templates.
4174     if (Args1.size() > NumComparedArguments)
4175       Args1.resize(NumComparedArguments);
4176     if (Args2.size() > NumComparedArguments)
4177       Args2.resize(NumComparedArguments);
4178     if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(),
4179                                 Args1.data(), Args1.size(), Info, Deduced,
4180                                 TDF_None, /*PartialOrdering=*/true))
4181       return false;
4182
4183     break;
4184   }
4185
4186   case TPOC_Conversion:
4187     //   - In the context of a call to a conversion operator, the return types
4188     //     of the conversion function templates are used.
4189     if (DeduceTemplateArgumentsByTypeMatch(
4190             S, TemplateParams, Proto2->getReturnType(), Proto1->getReturnType(),
4191             Info, Deduced, TDF_None,
4192             /*PartialOrdering=*/true))
4193       return false;
4194     break;
4195
4196   case TPOC_Other:
4197     //   - In other contexts (14.6.6.2) the function template's function type
4198     //     is used.
4199     if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
4200                                            FD2->getType(), FD1->getType(),
4201                                            Info, Deduced, TDF_None,
4202                                            /*PartialOrdering=*/true))
4203       return false;
4204     break;
4205   }
4206
4207   // C++0x [temp.deduct.partial]p11:
4208   //   In most cases, all template parameters must have values in order for
4209   //   deduction to succeed, but for partial ordering purposes a template
4210   //   parameter may remain without a value provided it is not used in the
4211   //   types being used for partial ordering. [ Note: a template parameter used
4212   //   in a non-deduced context is considered used. -end note]
4213   unsigned ArgIdx = 0, NumArgs = Deduced.size();
4214   for (; ArgIdx != NumArgs; ++ArgIdx)
4215     if (Deduced[ArgIdx].isNull())
4216       break;
4217
4218   if (ArgIdx == NumArgs) {
4219     // All template arguments were deduced. FT1 is at least as specialized
4220     // as FT2.
4221     return true;
4222   }
4223
4224   // Figure out which template parameters were used.
4225   llvm::SmallBitVector UsedParameters(TemplateParams->size());
4226   switch (TPOC) {
4227   case TPOC_Call:
4228     for (unsigned I = 0, N = Args2.size(); I != N; ++I)
4229       ::MarkUsedTemplateParameters(S.Context, Args2[I], false,
4230                                    TemplateParams->getDepth(),
4231                                    UsedParameters);
4232     break;
4233
4234   case TPOC_Conversion:
4235     ::MarkUsedTemplateParameters(S.Context, Proto2->getReturnType(), false,
4236                                  TemplateParams->getDepth(), UsedParameters);
4237     break;
4238
4239   case TPOC_Other:
4240     ::MarkUsedTemplateParameters(S.Context, FD2->getType(), false,
4241                                  TemplateParams->getDepth(),
4242                                  UsedParameters);
4243     break;
4244   }
4245
4246   for (; ArgIdx != NumArgs; ++ArgIdx)
4247     // If this argument had no value deduced but was used in one of the types
4248     // used for partial ordering, then deduction fails.
4249     if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
4250       return false;
4251
4252   return true;
4253 }
4254
4255 /// \brief Determine whether this a function template whose parameter-type-list
4256 /// ends with a function parameter pack.
4257 static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) {
4258   FunctionDecl *Function = FunTmpl->getTemplatedDecl();
4259   unsigned NumParams = Function->getNumParams();
4260   if (NumParams == 0)
4261     return false;
4262
4263   ParmVarDecl *Last = Function->getParamDecl(NumParams - 1);
4264   if (!Last->isParameterPack())
4265     return false;
4266
4267   // Make sure that no previous parameter is a parameter pack.
4268   while (--NumParams > 0) {
4269     if (Function->getParamDecl(NumParams - 1)->isParameterPack())
4270       return false;
4271   }
4272
4273   return true;
4274 }
4275
4276 /// \brief Returns the more specialized function template according
4277 /// to the rules of function template partial ordering (C++ [temp.func.order]).
4278 ///
4279 /// \param FT1 the first function template
4280 ///
4281 /// \param FT2 the second function template
4282 ///
4283 /// \param TPOC the context in which we are performing partial ordering of
4284 /// function templates.
4285 ///
4286 /// \param NumCallArguments1 The number of arguments in the call to FT1, used
4287 /// only when \c TPOC is \c TPOC_Call.
4288 ///
4289 /// \param NumCallArguments2 The number of arguments in the call to FT2, used
4290 /// only when \c TPOC is \c TPOC_Call.
4291 ///
4292 /// \returns the more specialized function template. If neither
4293 /// template is more specialized, returns NULL.
4294 FunctionTemplateDecl *
4295 Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1,
4296                                  FunctionTemplateDecl *FT2,
4297                                  SourceLocation Loc,
4298                                  TemplatePartialOrderingContext TPOC,
4299                                  unsigned NumCallArguments1,
4300                                  unsigned NumCallArguments2) {
4301   bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
4302                                           NumCallArguments1);
4303   bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
4304                                           NumCallArguments2);
4305
4306   if (Better1 != Better2) // We have a clear winner
4307     return Better1 ? FT1 : FT2;
4308
4309   if (!Better1 && !Better2) // Neither is better than the other
4310     return nullptr;
4311
4312   // FIXME: This mimics what GCC implements, but doesn't match up with the
4313   // proposed resolution for core issue 692. This area needs to be sorted out,
4314   // but for now we attempt to maintain compatibility.
4315   bool Variadic1 = isVariadicFunctionTemplate(FT1);
4316   bool Variadic2 = isVariadicFunctionTemplate(FT2);
4317   if (Variadic1 != Variadic2)
4318     return Variadic1? FT2 : FT1;
4319
4320   return nullptr;
4321 }
4322
4323 /// \brief Determine if the two templates are equivalent.
4324 static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) {
4325   if (T1 == T2)
4326     return true;
4327
4328   if (!T1 || !T2)
4329     return false;
4330
4331   return T1->getCanonicalDecl() == T2->getCanonicalDecl();
4332 }
4333
4334 /// \brief Retrieve the most specialized of the given function template
4335 /// specializations.
4336 ///
4337 /// \param SpecBegin the start iterator of the function template
4338 /// specializations that we will be comparing.
4339 ///
4340 /// \param SpecEnd the end iterator of the function template
4341 /// specializations, paired with \p SpecBegin.
4342 ///
4343 /// \param Loc the location where the ambiguity or no-specializations
4344 /// diagnostic should occur.
4345 ///
4346 /// \param NoneDiag partial diagnostic used to diagnose cases where there are
4347 /// no matching candidates.
4348 ///
4349 /// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one
4350 /// occurs.
4351 ///
4352 /// \param CandidateDiag partial diagnostic used for each function template
4353 /// specialization that is a candidate in the ambiguous ordering. One parameter
4354 /// in this diagnostic should be unbound, which will correspond to the string
4355 /// describing the template arguments for the function template specialization.
4356 ///
4357 /// \returns the most specialized function template specialization, if
4358 /// found. Otherwise, returns SpecEnd.
4359 UnresolvedSetIterator Sema::getMostSpecialized(
4360     UnresolvedSetIterator SpecBegin, UnresolvedSetIterator SpecEnd,
4361     TemplateSpecCandidateSet &FailedCandidates,
4362     SourceLocation Loc, const PartialDiagnostic &NoneDiag,
4363     const PartialDiagnostic &AmbigDiag, const PartialDiagnostic &CandidateDiag,
4364     bool Complain, QualType TargetType) {
4365   if (SpecBegin == SpecEnd) {
4366     if (Complain) {
4367       Diag(Loc, NoneDiag);
4368       FailedCandidates.NoteCandidates(*this, Loc);
4369     }
4370     return SpecEnd;
4371   }
4372
4373   if (SpecBegin + 1 == SpecEnd)
4374     return SpecBegin;
4375
4376   // Find the function template that is better than all of the templates it
4377   // has been compared to.
4378   UnresolvedSetIterator Best = SpecBegin;
4379   FunctionTemplateDecl *BestTemplate
4380     = cast<FunctionDecl>(*Best)->getPrimaryTemplate();
4381   assert(BestTemplate && "Not a function template specialization?");
4382   for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) {
4383     FunctionTemplateDecl *Challenger
4384       = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4385     assert(Challenger && "Not a function template specialization?");
4386     if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4387                                                   Loc, TPOC_Other, 0, 0),
4388                        Challenger)) {
4389       Best = I;
4390       BestTemplate = Challenger;
4391     }
4392   }
4393
4394   // Make sure that the "best" function template is more specialized than all
4395   // of the others.
4396   bool Ambiguous = false;
4397   for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4398     FunctionTemplateDecl *Challenger
4399       = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4400     if (I != Best &&
4401         !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4402                                                    Loc, TPOC_Other, 0, 0),
4403                         BestTemplate)) {
4404       Ambiguous = true;
4405       break;
4406     }
4407   }
4408
4409   if (!Ambiguous) {
4410     // We found an answer. Return it.
4411     return Best;
4412   }
4413
4414   // Diagnose the ambiguity.
4415   if (Complain) {
4416     Diag(Loc, AmbigDiag);
4417
4418     // FIXME: Can we order the candidates in some sane way?
4419     for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4420       PartialDiagnostic PD = CandidateDiag;
4421       PD << getTemplateArgumentBindingsText(
4422           cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(),
4423                     *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs());
4424       if (!TargetType.isNull())
4425         HandleFunctionTypeMismatch(PD, cast<FunctionDecl>(*I)->getType(),
4426                                    TargetType);
4427       Diag((*I)->getLocation(), PD);
4428     }
4429   }
4430
4431   return SpecEnd;
4432 }
4433
4434 /// \brief Returns the more specialized class template partial specialization
4435 /// according to the rules of partial ordering of class template partial
4436 /// specializations (C++ [temp.class.order]).
4437 ///
4438 /// \param PS1 the first class template partial specialization
4439 ///
4440 /// \param PS2 the second class template partial specialization
4441 ///
4442 /// \returns the more specialized class template partial specialization. If
4443 /// neither partial specialization is more specialized, returns NULL.
4444 ClassTemplatePartialSpecializationDecl *
4445 Sema::getMoreSpecializedPartialSpecialization(
4446                                   ClassTemplatePartialSpecializationDecl *PS1,
4447                                   ClassTemplatePartialSpecializationDecl *PS2,
4448                                               SourceLocation Loc) {
4449   // C++ [temp.class.order]p1:
4450   //   For two class template partial specializations, the first is at least as
4451   //   specialized as the second if, given the following rewrite to two
4452   //   function templates, the first function template is at least as
4453   //   specialized as the second according to the ordering rules for function
4454   //   templates (14.6.6.2):
4455   //     - the first function template has the same template parameters as the
4456   //       first partial specialization and has a single function parameter
4457   //       whose type is a class template specialization with the template
4458   //       arguments of the first partial specialization, and
4459   //     - the second function template has the same template parameters as the
4460   //       second partial specialization and has a single function parameter
4461   //       whose type is a class template specialization with the template
4462   //       arguments of the second partial specialization.
4463   //
4464   // Rather than synthesize function templates, we merely perform the
4465   // equivalent partial ordering by performing deduction directly on
4466   // the template arguments of the class template partial
4467   // specializations. This computation is slightly simpler than the
4468   // general problem of function template partial ordering, because
4469   // class template partial specializations are more constrained. We
4470   // know that every template parameter is deducible from the class
4471   // template partial specialization's template arguments, for
4472   // example.
4473   SmallVector<DeducedTemplateArgument, 4> Deduced;
4474   TemplateDeductionInfo Info(Loc);
4475
4476   QualType PT1 = PS1->getInjectedSpecializationType();
4477   QualType PT2 = PS2->getInjectedSpecializationType();
4478
4479   // Determine whether PS1 is at least as specialized as PS2
4480   Deduced.resize(PS2->getTemplateParameters()->size());
4481   bool Better1 = !DeduceTemplateArgumentsByTypeMatch(*this,
4482                                             PS2->getTemplateParameters(),
4483                                             PT2, PT1, Info, Deduced, TDF_None,
4484                                             /*PartialOrdering=*/true);
4485   if (Better1) {
4486     SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end());
4487     InstantiatingTemplate Inst(*this, Loc, PS2, DeducedArgs, Info);
4488     Better1 = !::FinishTemplateArgumentDeduction(
4489         *this, PS2, PS1->getTemplateArgs(), Deduced, Info);
4490   }
4491
4492   // Determine whether PS2 is at least as specialized as PS1
4493   Deduced.clear();
4494   Deduced.resize(PS1->getTemplateParameters()->size());
4495   bool Better2 = !DeduceTemplateArgumentsByTypeMatch(
4496       *this, PS1->getTemplateParameters(), PT1, PT2, Info, Deduced, TDF_None,
4497       /*PartialOrdering=*/true);
4498   if (Better2) {
4499     SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),
4500                                                  Deduced.end());
4501     InstantiatingTemplate Inst(*this, Loc, PS1, DeducedArgs, Info);
4502     Better2 = !::FinishTemplateArgumentDeduction(
4503         *this, PS1, PS2->getTemplateArgs(), Deduced, Info);
4504   }
4505
4506   if (Better1 == Better2)
4507     return nullptr;
4508
4509   return Better1 ? PS1 : PS2;
4510 }
4511
4512 /// TODO: Unify with ClassTemplatePartialSpecializationDecl version?
4513 ///       May require unifying ClassTemplate(Partial)SpecializationDecl and
4514 ///        VarTemplate(Partial)SpecializationDecl with a new data
4515 ///        structure Template(Partial)SpecializationDecl, and
4516 ///        using Template(Partial)SpecializationDecl as input type.
4517 VarTemplatePartialSpecializationDecl *
4518 Sema::getMoreSpecializedPartialSpecialization(
4519     VarTemplatePartialSpecializationDecl *PS1,
4520     VarTemplatePartialSpecializationDecl *PS2, SourceLocation Loc) {
4521   SmallVector<DeducedTemplateArgument, 4> Deduced;
4522   TemplateDeductionInfo Info(Loc);
4523
4524   assert(PS1->getSpecializedTemplate() == PS2->getSpecializedTemplate() &&
4525          "the partial specializations being compared should specialize"
4526          " the same template.");
4527   TemplateName Name(PS1->getSpecializedTemplate());
4528   TemplateName CanonTemplate = Context.getCanonicalTemplateName(Name);
4529   QualType PT1 = Context.getTemplateSpecializationType(
4530       CanonTemplate, PS1->getTemplateArgs().data(),
4531       PS1->getTemplateArgs().size());
4532   QualType PT2 = Context.getTemplateSpecializationType(
4533       CanonTemplate, PS2->getTemplateArgs().data(),
4534       PS2->getTemplateArgs().size());
4535
4536   // Determine whether PS1 is at least as specialized as PS2
4537   Deduced.resize(PS2->getTemplateParameters()->size());
4538   bool Better1 = !DeduceTemplateArgumentsByTypeMatch(
4539       *this, PS2->getTemplateParameters(), PT2, PT1, Info, Deduced, TDF_None,
4540       /*PartialOrdering=*/true);
4541   if (Better1) {
4542     SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),
4543                                                  Deduced.end());
4544     InstantiatingTemplate Inst(*this, Loc, PS2, DeducedArgs, Info);
4545     Better1 = !::FinishTemplateArgumentDeduction(*this, PS2,
4546                                                  PS1->getTemplateArgs(),
4547                                                  Deduced, Info);
4548   }
4549
4550   // Determine whether PS2 is at least as specialized as PS1
4551   Deduced.clear();
4552   Deduced.resize(PS1->getTemplateParameters()->size());
4553   bool Better2 = !DeduceTemplateArgumentsByTypeMatch(*this,
4554                                             PS1->getTemplateParameters(),
4555                                             PT1, PT2, Info, Deduced, TDF_None,
4556                                             /*PartialOrdering=*/true);
4557   if (Better2) {
4558     SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end());
4559     InstantiatingTemplate Inst(*this, Loc, PS1, DeducedArgs, Info);
4560     Better2 = !::FinishTemplateArgumentDeduction(*this, PS1,
4561                                                  PS2->getTemplateArgs(),
4562                                                  Deduced, Info);
4563   }
4564
4565   if (Better1 == Better2)
4566     return nullptr;
4567
4568   return Better1? PS1 : PS2;
4569 }
4570
4571 static void
4572 MarkUsedTemplateParameters(ASTContext &Ctx,
4573                            const TemplateArgument &TemplateArg,
4574                            bool OnlyDeduced,
4575                            unsigned Depth,
4576                            llvm::SmallBitVector &Used);
4577
4578 /// \brief Mark the template parameters that are used by the given
4579 /// expression.
4580 static void
4581 MarkUsedTemplateParameters(ASTContext &Ctx,
4582                            const Expr *E,
4583                            bool OnlyDeduced,
4584                            unsigned Depth,
4585                            llvm::SmallBitVector &Used) {
4586   // We can deduce from a pack expansion.
4587   if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E))
4588     E = Expansion->getPattern();
4589
4590   // Skip through any implicit casts we added while type-checking, and any
4591   // substitutions performed by template alias expansion.
4592   while (1) {
4593     if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
4594       E = ICE->getSubExpr();
4595     else if (const SubstNonTypeTemplateParmExpr *Subst =
4596                dyn_cast<SubstNonTypeTemplateParmExpr>(E))
4597       E = Subst->getReplacement();
4598     else
4599       break;
4600   }
4601
4602   // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to
4603   // find other occurrences of template parameters.
4604   const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
4605   if (!DRE)
4606     return;
4607
4608   const NonTypeTemplateParmDecl *NTTP
4609     = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
4610   if (!NTTP)
4611     return;
4612
4613   if (NTTP->getDepth() == Depth)
4614     Used[NTTP->getIndex()] = true;
4615 }
4616
4617 /// \brief Mark the template parameters that are used by the given
4618 /// nested name specifier.
4619 static void
4620 MarkUsedTemplateParameters(ASTContext &Ctx,
4621                            NestedNameSpecifier *NNS,
4622                            bool OnlyDeduced,
4623                            unsigned Depth,
4624                            llvm::SmallBitVector &Used) {
4625   if (!NNS)
4626     return;
4627
4628   MarkUsedTemplateParameters(Ctx, NNS->getPrefix(), OnlyDeduced, Depth,
4629                              Used);
4630   MarkUsedTemplateParameters(Ctx, QualType(NNS->getAsType(), 0),
4631                              OnlyDeduced, Depth, Used);
4632 }
4633
4634 /// \brief Mark the template parameters that are used by the given
4635 /// template name.
4636 static void
4637 MarkUsedTemplateParameters(ASTContext &Ctx,
4638                            TemplateName Name,
4639                            bool OnlyDeduced,
4640                            unsigned Depth,
4641                            llvm::SmallBitVector &Used) {
4642   if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
4643     if (TemplateTemplateParmDecl *TTP
4644           = dyn_cast<TemplateTemplateParmDecl>(Template)) {
4645       if (TTP->getDepth() == Depth)
4646         Used[TTP->getIndex()] = true;
4647     }
4648     return;
4649   }
4650
4651   if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName())
4652     MarkUsedTemplateParameters(Ctx, QTN->getQualifier(), OnlyDeduced,
4653                                Depth, Used);
4654   if (DependentTemplateName *DTN = Name.getAsDependentTemplateName())
4655     MarkUsedTemplateParameters(Ctx, DTN->getQualifier(), OnlyDeduced,
4656                                Depth, Used);
4657 }
4658
4659 /// \brief Mark the template parameters that are used by the given
4660 /// type.
4661 static void
4662 MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
4663                            bool OnlyDeduced,
4664                            unsigned Depth,
4665                            llvm::SmallBitVector &Used) {
4666   if (T.isNull())
4667     return;
4668
4669   // Non-dependent types have nothing deducible
4670   if (!T->isDependentType())
4671     return;
4672
4673   T = Ctx.getCanonicalType(T);
4674   switch (T->getTypeClass()) {
4675   case Type::Pointer:
4676     MarkUsedTemplateParameters(Ctx,
4677                                cast<PointerType>(T)->getPointeeType(),
4678                                OnlyDeduced,
4679                                Depth,
4680                                Used);
4681     break;
4682
4683   case Type::BlockPointer:
4684     MarkUsedTemplateParameters(Ctx,
4685                                cast<BlockPointerType>(T)->getPointeeType(),
4686                                OnlyDeduced,
4687                                Depth,
4688                                Used);
4689     break;
4690
4691   case Type::LValueReference:
4692   case Type::RValueReference:
4693     MarkUsedTemplateParameters(Ctx,
4694                                cast<ReferenceType>(T)->getPointeeType(),
4695                                OnlyDeduced,
4696                                Depth,
4697                                Used);
4698     break;
4699
4700   case Type::MemberPointer: {
4701     const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
4702     MarkUsedTemplateParameters(Ctx, MemPtr->getPointeeType(), OnlyDeduced,
4703                                Depth, Used);
4704     MarkUsedTemplateParameters(Ctx, QualType(MemPtr->getClass(), 0),
4705                                OnlyDeduced, Depth, Used);
4706     break;
4707   }
4708
4709   case Type::DependentSizedArray:
4710     MarkUsedTemplateParameters(Ctx,
4711                                cast<DependentSizedArrayType>(T)->getSizeExpr(),
4712                                OnlyDeduced, Depth, Used);
4713     // Fall through to check the element type
4714
4715   case Type::ConstantArray:
4716   case Type::IncompleteArray:
4717     MarkUsedTemplateParameters(Ctx,
4718                                cast<ArrayType>(T)->getElementType(),
4719                                OnlyDeduced, Depth, Used);
4720     break;
4721
4722   case Type::Vector:
4723   case Type::ExtVector:
4724     MarkUsedTemplateParameters(Ctx,
4725                                cast<VectorType>(T)->getElementType(),
4726                                OnlyDeduced, Depth, Used);
4727     break;
4728
4729   case Type::DependentSizedExtVector: {
4730     const DependentSizedExtVectorType *VecType
4731       = cast<DependentSizedExtVectorType>(T);
4732     MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced,
4733                                Depth, Used);
4734     MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced,
4735                                Depth, Used);
4736     break;
4737   }
4738
4739   case Type::FunctionProto: {
4740     const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
4741     MarkUsedTemplateParameters(Ctx, Proto->getReturnType(), OnlyDeduced, Depth,
4742                                Used);
4743     for (unsigned I = 0, N = Proto->getNumParams(); I != N; ++I)
4744       MarkUsedTemplateParameters(Ctx, Proto->getParamType(I), OnlyDeduced,
4745                                  Depth, Used);
4746     break;
4747   }
4748
4749   case Type::TemplateTypeParm: {
4750     const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T);
4751     if (TTP->getDepth() == Depth)
4752       Used[TTP->getIndex()] = true;
4753     break;
4754   }
4755
4756   case Type::SubstTemplateTypeParmPack: {
4757     const SubstTemplateTypeParmPackType *Subst
4758       = cast<SubstTemplateTypeParmPackType>(T);
4759     MarkUsedTemplateParameters(Ctx,
4760                                QualType(Subst->getReplacedParameter(), 0),
4761                                OnlyDeduced, Depth, Used);
4762     MarkUsedTemplateParameters(Ctx, Subst->getArgumentPack(),
4763                                OnlyDeduced, Depth, Used);
4764     break;
4765   }
4766
4767   case Type::InjectedClassName:
4768     T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType();
4769     // fall through
4770
4771   case Type::TemplateSpecialization: {
4772     const TemplateSpecializationType *Spec
4773       = cast<TemplateSpecializationType>(T);
4774     MarkUsedTemplateParameters(Ctx, Spec->getTemplateName(), OnlyDeduced,
4775                                Depth, Used);
4776
4777     // C++0x [temp.deduct.type]p9:
4778     //   If the template argument list of P contains a pack expansion that is
4779     //   not the last template argument, the entire template argument list is a
4780     //   non-deduced context.
4781     if (OnlyDeduced &&
4782         hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
4783       break;
4784
4785     for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4786       MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
4787                                  Used);
4788     break;
4789   }
4790
4791   case Type::Complex:
4792     if (!OnlyDeduced)
4793       MarkUsedTemplateParameters(Ctx,
4794                                  cast<ComplexType>(T)->getElementType(),
4795                                  OnlyDeduced, Depth, Used);
4796     break;
4797
4798   case Type::Atomic:
4799     if (!OnlyDeduced)
4800       MarkUsedTemplateParameters(Ctx,
4801                                  cast<AtomicType>(T)->getValueType(),
4802                                  OnlyDeduced, Depth, Used);
4803     break;
4804
4805   case Type::DependentName:
4806     if (!OnlyDeduced)
4807       MarkUsedTemplateParameters(Ctx,
4808                                  cast<DependentNameType>(T)->getQualifier(),
4809                                  OnlyDeduced, Depth, Used);
4810     break;
4811
4812   case Type::DependentTemplateSpecialization: {
4813     const DependentTemplateSpecializationType *Spec
4814       = cast<DependentTemplateSpecializationType>(T);
4815     if (!OnlyDeduced)
4816       MarkUsedTemplateParameters(Ctx, Spec->getQualifier(),
4817                                  OnlyDeduced, Depth, Used);
4818
4819     // C++0x [temp.deduct.type]p9:
4820     //   If the template argument list of P contains a pack expansion that is not
4821     //   the last template argument, the entire template argument list is a
4822     //   non-deduced context.
4823     if (OnlyDeduced &&
4824         hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
4825       break;
4826
4827     for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4828       MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
4829                                  Used);
4830     break;
4831   }
4832
4833   case Type::TypeOf:
4834     if (!OnlyDeduced)
4835       MarkUsedTemplateParameters(Ctx,
4836                                  cast<TypeOfType>(T)->getUnderlyingType(),
4837                                  OnlyDeduced, Depth, Used);
4838     break;
4839
4840   case Type::TypeOfExpr:
4841     if (!OnlyDeduced)
4842       MarkUsedTemplateParameters(Ctx,
4843                                  cast<TypeOfExprType>(T)->getUnderlyingExpr(),
4844                                  OnlyDeduced, Depth, Used);
4845     break;
4846
4847   case Type::Decltype:
4848     if (!OnlyDeduced)
4849       MarkUsedTemplateParameters(Ctx,
4850                                  cast<DecltypeType>(T)->getUnderlyingExpr(),
4851                                  OnlyDeduced, Depth, Used);
4852     break;
4853
4854   case Type::UnaryTransform:
4855     if (!OnlyDeduced)
4856       MarkUsedTemplateParameters(Ctx,
4857                                cast<UnaryTransformType>(T)->getUnderlyingType(),
4858                                  OnlyDeduced, Depth, Used);
4859     break;
4860
4861   case Type::PackExpansion:
4862     MarkUsedTemplateParameters(Ctx,
4863                                cast<PackExpansionType>(T)->getPattern(),
4864                                OnlyDeduced, Depth, Used);
4865     break;
4866
4867   case Type::Auto:
4868     MarkUsedTemplateParameters(Ctx,
4869                                cast<AutoType>(T)->getDeducedType(),
4870                                OnlyDeduced, Depth, Used);
4871
4872   // None of these types have any template parameters in them.
4873   case Type::Builtin:
4874   case Type::VariableArray:
4875   case Type::FunctionNoProto:
4876   case Type::Record:
4877   case Type::Enum:
4878   case Type::ObjCInterface:
4879   case Type::ObjCObject:
4880   case Type::ObjCObjectPointer:
4881   case Type::UnresolvedUsing:
4882 #define TYPE(Class, Base)
4883 #define ABSTRACT_TYPE(Class, Base)
4884 #define DEPENDENT_TYPE(Class, Base)
4885 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
4886 #include "clang/AST/TypeNodes.def"
4887     break;
4888   }
4889 }
4890
4891 /// \brief Mark the template parameters that are used by this
4892 /// template argument.
4893 static void
4894 MarkUsedTemplateParameters(ASTContext &Ctx,
4895                            const TemplateArgument &TemplateArg,
4896                            bool OnlyDeduced,
4897                            unsigned Depth,
4898                            llvm::SmallBitVector &Used) {
4899   switch (TemplateArg.getKind()) {
4900   case TemplateArgument::Null:
4901   case TemplateArgument::Integral:
4902   case TemplateArgument::Declaration:
4903     break;
4904
4905   case TemplateArgument::NullPtr:
4906     MarkUsedTemplateParameters(Ctx, TemplateArg.getNullPtrType(), OnlyDeduced,
4907                                Depth, Used);
4908     break;
4909
4910   case TemplateArgument::Type:
4911     MarkUsedTemplateParameters(Ctx, TemplateArg.getAsType(), OnlyDeduced,
4912                                Depth, Used);
4913     break;
4914
4915   case TemplateArgument::Template:
4916   case TemplateArgument::TemplateExpansion:
4917     MarkUsedTemplateParameters(Ctx,
4918                                TemplateArg.getAsTemplateOrTemplatePattern(),
4919                                OnlyDeduced, Depth, Used);
4920     break;
4921
4922   case TemplateArgument::Expression:
4923     MarkUsedTemplateParameters(Ctx, TemplateArg.getAsExpr(), OnlyDeduced,
4924                                Depth, Used);
4925     break;
4926
4927   case TemplateArgument::Pack:
4928     for (const auto &P : TemplateArg.pack_elements())
4929       MarkUsedTemplateParameters(Ctx, P, OnlyDeduced, Depth, Used);
4930     break;
4931   }
4932 }
4933
4934 /// \brief Mark which template parameters can be deduced from a given
4935 /// template argument list.
4936 ///
4937 /// \param TemplateArgs the template argument list from which template
4938 /// parameters will be deduced.
4939 ///
4940 /// \param Used a bit vector whose elements will be set to \c true
4941 /// to indicate when the corresponding template parameter will be
4942 /// deduced.
4943 void
4944 Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs,
4945                                  bool OnlyDeduced, unsigned Depth,
4946                                  llvm::SmallBitVector &Used) {
4947   // C++0x [temp.deduct.type]p9:
4948   //   If the template argument list of P contains a pack expansion that is not
4949   //   the last template argument, the entire template argument list is a
4950   //   non-deduced context.
4951   if (OnlyDeduced &&
4952       hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size()))
4953     return;
4954
4955   for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
4956     ::MarkUsedTemplateParameters(Context, TemplateArgs[I], OnlyDeduced,
4957                                  Depth, Used);
4958 }
4959
4960 /// \brief Marks all of the template parameters that will be deduced by a
4961 /// call to the given function template.
4962 void Sema::MarkDeducedTemplateParameters(
4963     ASTContext &Ctx, const FunctionTemplateDecl *FunctionTemplate,
4964     llvm::SmallBitVector &Deduced) {
4965   TemplateParameterList *TemplateParams
4966     = FunctionTemplate->getTemplateParameters();
4967   Deduced.clear();
4968   Deduced.resize(TemplateParams->size());
4969
4970   FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4971   for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
4972     ::MarkUsedTemplateParameters(Ctx, Function->getParamDecl(I)->getType(),
4973                                  true, TemplateParams->getDepth(), Deduced);
4974 }
4975
4976 bool hasDeducibleTemplateParameters(Sema &S,
4977                                     FunctionTemplateDecl *FunctionTemplate,
4978                                     QualType T) {
4979   if (!T->isDependentType())
4980     return false;
4981
4982   TemplateParameterList *TemplateParams
4983     = FunctionTemplate->getTemplateParameters();
4984   llvm::SmallBitVector Deduced(TemplateParams->size());
4985   ::MarkUsedTemplateParameters(S.Context, T, true, TemplateParams->getDepth(),
4986                                Deduced);
4987
4988   return Deduced.any();
4989 }