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

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