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

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