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