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