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/Sema.h"
  14 #include "clang/Sema/DeclSpec.h"
  15 #include "clang/Sema/SemaDiagnostic.h" // FIXME: temporary!
  16 #include "clang/Sema/Template.h"
  17 #include "clang/Sema/TemplateDeduction.h"
  18 #include "clang/AST/ASTContext.h"
  19 #include "clang/AST/DeclObjC.h"
  20 #include "clang/AST/DeclTemplate.h"
  21 #include "clang/AST/StmtVisitor.h"
  22 #include "clang/AST/Expr.h"
  23 #include "clang/AST/ExprCXX.h"
  24 #include "llvm/ADT/BitVector.h"
  25 #include "TreeTransform.h"
  26 #include <algorithm>
  27
  28 namespace clang {
  29   using namespace sema;
  30
  31   /// \brief Various flags that control template argument deduction.
  32   ///
  33   /// These flags can be bitwise-OR'd together.
  34   enum TemplateDeductionFlags {
  35     /// \brief No template argument deduction flags, which indicates the
  36     /// strictest results for template argument deduction (as used for, e.g.,
  37     /// matching class template partial specializations).
  38     TDF_None = 0,
  39     /// \brief Within template argument deduction from a function call, we are
  40     /// matching with a parameter type for which the original parameter was
  41     /// a reference.
  42     TDF_ParamWithReferenceType = 0x1,
  43     /// \brief Within template argument deduction from a function call, we
  44     /// are matching in a case where we ignore cv-qualifiers.
  45     TDF_IgnoreQualifiers = 0x02,
  46     /// \brief Within template argument deduction from a function call,
  47     /// we are matching in a case where we can perform template argument
  48     /// deduction from a template-id of a derived class of the argument type.
  49     TDF_DerivedClass = 0x04,
  50     /// \brief Allow non-dependent types to differ, e.g., when performing
  51     /// template argument deduction from a function call where conversions
  52     /// may apply.
  53     TDF_SkipNonDependent = 0x08,
  54     /// \brief Whether we are performing template argument deduction for
  55     /// parameters and arguments in a top-level template argument
  56     TDF_TopLevelParameterTypeList = 0x10
  57   };
  58 }
  59
  60 using namespace clang;
  61
  62 /// \brief Compare two APSInts, extending and switching the sign as
  63 /// necessary to compare their values regardless of underlying type.
  64 static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) {
  65   if (Y.getBitWidth() > X.getBitWidth())
  66     X = X.extend(Y.getBitWidth());
  67   else if (Y.getBitWidth() < X.getBitWidth())
  68     Y = Y.extend(X.getBitWidth());
  69
  70   // If there is a signedness mismatch, correct it.
  71   if (X.isSigned() != Y.isSigned()) {
  72     // If the signed value is negative, then the values cannot be the same.
  73     if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative()))
  74       return false;
  75
  76     Y.setIsSigned(true);
  77     X.setIsSigned(true);
  78   }
  79
  80   return X == Y;
  81 }
  82
  83 static Sema::TemplateDeductionResult
  84 DeduceTemplateArguments(Sema &S,
  85                         TemplateParameterList *TemplateParams,
  86                         const TemplateArgument &Param,
  87                         TemplateArgument Arg,
  88                         TemplateDeductionInfo &Info,
  89                       llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced);
  90
  91 /// \brief Whether template argument deduction for two reference parameters
  92 /// resulted in the argument type, parameter type, or neither type being more
  93 /// qualified than the other.
  94 enum DeductionQualifierComparison {
  95   NeitherMoreQualified = 0,
  96   ParamMoreQualified,
  97   ArgMoreQualified
  98 };
  99
 100 /// \brief Stores the result of comparing two reference parameters while
 101 /// performing template argument deduction for partial ordering of function
 102 /// templates.
 103 struct RefParamPartialOrderingComparison {
 104   /// \brief Whether the parameter type is an rvalue reference type.
 105   bool ParamIsRvalueRef;
 106   /// \brief Whether the argument type is an rvalue reference type.
 107   bool ArgIsRvalueRef;
 108
 109   /// \brief Whether the parameter or argument (or neither) is more qualified.
 110   DeductionQualifierComparison Qualifiers;
 111 };
 112
 113
 114
 115 static Sema::TemplateDeductionResult
 116 DeduceTemplateArguments(Sema &S,
 117                         TemplateParameterList *TemplateParams,
 118                         QualType Param,
 119                         QualType Arg,
 120                         TemplateDeductionInfo &Info,
 121                         llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
 122                         unsigned TDF,
 123                         bool PartialOrdering = false,
 124                       llvm::SmallVectorImpl<RefParamPartialOrderingComparison> *
 125                                                       RefParamComparisons = 0);
 126
 127 static Sema::TemplateDeductionResult
 128 DeduceTemplateArguments(Sema &S,
 129                         TemplateParameterList *TemplateParams,
 130                         const TemplateArgument *Params, unsigned NumParams,
 131                         const TemplateArgument *Args, unsigned NumArgs,
 132                         TemplateDeductionInfo &Info,
 133                         llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
 134                         bool NumberOfArgumentsMustMatch = true);
 135
 136 /// \brief If the given expression is of a form that permits the deduction
 137 /// of a non-type template parameter, return the declaration of that
 138 /// non-type template parameter.
 139 static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
 140   if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
 141     E = IC->getSubExpr();
 142
 143   if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
 144     return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
 145
 146   return 0;
 147 }
 148
 149 /// \brief Determine whether two declaration pointers refer to the same
 150 /// declaration.
 151 static bool isSameDeclaration(Decl *X, Decl *Y) {
 152   if (!X || !Y)
 153     return !X && !Y;
 154
 155   if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
 156     X = NX->getUnderlyingDecl();
 157   if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
 158     Y = NY->getUnderlyingDecl();
 159
 160   return X->getCanonicalDecl() == Y->getCanonicalDecl();
 161 }
 162
 163 /// \brief Verify that the given, deduced template arguments are compatible.
 164 ///
 165 /// \returns The deduced template argument, or a NULL template argument if
 166 /// the deduced template arguments were incompatible.
 167 static DeducedTemplateArgument
 168 checkDeducedTemplateArguments(ASTContext &Context,
 169                               const DeducedTemplateArgument &X,
 170                               const DeducedTemplateArgument &Y) {
 171   // We have no deduction for one or both of the arguments; they're compatible.
 172   if (X.isNull())
 173     return Y;
 174   if (Y.isNull())
 175     return X;
 176
 177   switch (X.getKind()) {
 178   case TemplateArgument::Null:
 179     llvm_unreachable("Non-deduced template arguments handled above");
 180
 181   case TemplateArgument::Type:
 182     // If two template type arguments have the same type, they're compatible.
 183     if (Y.getKind() == TemplateArgument::Type &&
 184         Context.hasSameType(X.getAsType(), Y.getAsType()))
 185       return X;
 186
 187     return DeducedTemplateArgument();
 188
 189   case TemplateArgument::Integral:
 190     // If we deduced a constant in one case and either a dependent expression or
 191     // declaration in another case, keep the integral constant.
 192     // If both are integral constants with the same value, keep that value.
 193     if (Y.getKind() == TemplateArgument::Expression ||
 194         Y.getKind() == TemplateArgument::Declaration ||
 195         (Y.getKind() == TemplateArgument::Integral &&
 196          hasSameExtendedValue(*X.getAsIntegral(), *Y.getAsIntegral())))
 197       return DeducedTemplateArgument(X,
 198                                      X.wasDeducedFromArrayBound() &&
 199                                      Y.wasDeducedFromArrayBound());
 200
 201     // All other combinations are incompatible.
 202     return DeducedTemplateArgument();
 203
 204   case TemplateArgument::Template:
 205     if (Y.getKind() == TemplateArgument::Template &&
 206         Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
 207       return X;
 208
 209     // All other combinations are incompatible.
 210     return DeducedTemplateArgument();
 211
 212   case TemplateArgument::TemplateExpansion:
 213     if (Y.getKind() == TemplateArgument::TemplateExpansion &&
 214         Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
 215                                     Y.getAsTemplateOrTemplatePattern()))
 216       return X;
 217
 218     // All other combinations are incompatible.
 219     return DeducedTemplateArgument();
 220
 221   case TemplateArgument::Expression:
 222     // If we deduced a dependent expression in one case and either an integral
 223     // constant or a declaration in another case, keep the integral constant
 224     // or declaration.
 225     if (Y.getKind() == TemplateArgument::Integral ||
 226         Y.getKind() == TemplateArgument::Declaration)
 227       return DeducedTemplateArgument(Y, X.wasDeducedFromArrayBound() &&
 228                                      Y.wasDeducedFromArrayBound());
 229
 230     if (Y.getKind() == TemplateArgument::Expression) {
 231       // Compare the expressions for equality
 232       llvm::FoldingSetNodeID ID1, ID2;
 233       X.getAsExpr()->Profile(ID1, Context, true);
 234       Y.getAsExpr()->Profile(ID2, Context, true);
 235       if (ID1 == ID2)
 236         return X;
 237     }
 238
 239     // All other combinations are incompatible.
 240     return DeducedTemplateArgument();
 241
 242   case TemplateArgument::Declaration:
 243     // If we deduced a declaration and a dependent expression, keep the
 244     // declaration.
 245     if (Y.getKind() == TemplateArgument::Expression)
 246       return X;
 247
 248     // If we deduced a declaration and an integral constant, keep the
 249     // integral constant.
 250     if (Y.getKind() == TemplateArgument::Integral)
 251       return Y;
 252
 253     // If we deduced two declarations, make sure they they refer to the
 254     // same declaration.
 255     if (Y.getKind() == TemplateArgument::Declaration &&
 256         isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))
 257       return X;
 258
 259     // All other combinations are incompatible.
 260     return DeducedTemplateArgument();
 261
 262   case TemplateArgument::Pack:
 263     if (Y.getKind() != TemplateArgument::Pack ||
 264         X.pack_size() != Y.pack_size())
 265       return DeducedTemplateArgument();
 266
 267     for (TemplateArgument::pack_iterator XA = X.pack_begin(),
 268                                       XAEnd = X.pack_end(),
 269                                          YA = Y.pack_begin();
 270          XA != XAEnd; ++XA, ++YA) {
 271       if (checkDeducedTemplateArguments(Context,
 272                     DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
 273                     DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound()))
 274             .isNull())
 275         return DeducedTemplateArgument();
 276     }
 277
 278     return X;
 279   }
 280
 281   return DeducedTemplateArgument();
 282 }
 283
 284 /// \brief Deduce the value of the given non-type template parameter
 285 /// from the given constant.
 286 static Sema::TemplateDeductionResult
 287 DeduceNonTypeTemplateArgument(Sema &S,
 288                               NonTypeTemplateParmDecl *NTTP,
 289                               llvm::APSInt Value, QualType ValueType,
 290                               bool DeducedFromArrayBound,
 291                               TemplateDeductionInfo &Info,
 292                     llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
 293   assert(NTTP->getDepth() == 0 &&
 294          "Cannot deduce non-type template argument with depth > 0");
 295
 296   DeducedTemplateArgument NewDeduced(Value, ValueType, DeducedFromArrayBound);
 297   DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
 298                                                      Deduced[NTTP->getIndex()],
 299                                                                  NewDeduced);
 300   if (Result.isNull()) {
 301     Info.Param = NTTP;
 302     Info.FirstArg = Deduced[NTTP->getIndex()];
 303     Info.SecondArg = NewDeduced;
 304     return Sema::TDK_Inconsistent;
 305   }
 306
 307   Deduced[NTTP->getIndex()] = Result;
 308   return Sema::TDK_Success;
 309 }
 310
 311 /// \brief Deduce the value of the given non-type template parameter
 312 /// from the given type- or value-dependent expression.
 313 ///
 314 /// \returns true if deduction succeeded, false otherwise.
 315 static Sema::TemplateDeductionResult
 316 DeduceNonTypeTemplateArgument(Sema &S,
 317                               NonTypeTemplateParmDecl *NTTP,
 318                               Expr *Value,
 319                               TemplateDeductionInfo &Info,
 320                     llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
 321   assert(NTTP->getDepth() == 0 &&
 322          "Cannot deduce non-type template argument with depth > 0");
 323   assert((Value->isTypeDependent() || Value->isValueDependent()) &&
 324          "Expression template argument must be type- or value-dependent.");
 325
 326   DeducedTemplateArgument NewDeduced(Value);
 327   DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
 328                                                      Deduced[NTTP->getIndex()],
 329                                                                  NewDeduced);
 330
 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 declaration.
 344 ///
 345 /// \returns true if deduction succeeded, false otherwise.
 346 static Sema::TemplateDeductionResult
 347 DeduceNonTypeTemplateArgument(Sema &S,
 348                               NonTypeTemplateParmDecl *NTTP,
 349                               Decl *D,
 350                               TemplateDeductionInfo &Info,
 351                     llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
 352   assert(NTTP->getDepth() == 0 &&
 353          "Cannot deduce non-type template argument with depth > 0");
 354
 355   DeducedTemplateArgument NewDeduced(D? D->getCanonicalDecl() : 0);
 356   DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
 357                                                      Deduced[NTTP->getIndex()],
 358                                                                  NewDeduced);
 359   if (Result.isNull()) {
 360     Info.Param = NTTP;
 361     Info.FirstArg = Deduced[NTTP->getIndex()];
 362     Info.SecondArg = NewDeduced;
 363     return Sema::TDK_Inconsistent;
 364   }
 365
 366   Deduced[NTTP->getIndex()] = Result;
 367   return Sema::TDK_Success;
 368 }
 369
 370 static Sema::TemplateDeductionResult
 371 DeduceTemplateArguments(Sema &S,
 372                         TemplateParameterList *TemplateParams,
 373                         TemplateName Param,
 374                         TemplateName Arg,
 375                         TemplateDeductionInfo &Info,
 376                     llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
 377   TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
 378   if (!ParamDecl) {
 379     // The parameter type is dependent and is not a template template parameter,
 380     // so there is nothing that we can deduce.
 381     return Sema::TDK_Success;
 382   }
 383
 384   if (TemplateTemplateParmDecl *TempParam
 385         = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
 386     DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg));
 387     DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
 388                                                  Deduced[TempParam->getIndex()],
 389                                                                    NewDeduced);
 390     if (Result.isNull()) {
 391       Info.Param = TempParam;
 392       Info.FirstArg = Deduced[TempParam->getIndex()];
 393       Info.SecondArg = NewDeduced;
 394       return Sema::TDK_Inconsistent;
 395     }
 396
 397     Deduced[TempParam->getIndex()] = Result;
 398     return Sema::TDK_Success;
 399   }
 400
 401   // Verify that the two template names are equivalent.
 402   if (S.Context.hasSameTemplateName(Param, Arg))
 403     return Sema::TDK_Success;
 404
 405   // Mismatch of non-dependent template parameter to argument.
 406   Info.FirstArg = TemplateArgument(Param);
 407   Info.SecondArg = TemplateArgument(Arg);
 408   return Sema::TDK_NonDeducedMismatch;
 409 }
 410
 411 /// \brief Deduce the template arguments by comparing the template parameter
 412 /// type (which is a template-id) with the template argument type.
 413 ///
 414 /// \param S the Sema
 415 ///
 416 /// \param TemplateParams the template parameters that we are deducing
 417 ///
 418 /// \param Param the parameter type
 419 ///
 420 /// \param Arg the argument type
 421 ///
 422 /// \param Info information about the template argument deduction itself
 423 ///
 424 /// \param Deduced the deduced template arguments
 425 ///
 426 /// \returns the result of template argument deduction so far. Note that a
 427 /// "success" result means that template argument deduction has not yet failed,
 428 /// but it may still fail, later, for other reasons.
 429 static Sema::TemplateDeductionResult
 430 DeduceTemplateArguments(Sema &S,
 431                         TemplateParameterList *TemplateParams,
 432                         const TemplateSpecializationType *Param,
 433                         QualType Arg,
 434                         TemplateDeductionInfo &Info,
 435                     llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
 436   assert(Arg.isCanonical() && "Argument type must be canonical");
 437
 438   // Check whether the template argument is a dependent template-id.
 439   if (const TemplateSpecializationType *SpecArg
 440         = dyn_cast<TemplateSpecializationType>(Arg)) {
 441     // Perform template argument deduction for the template name.
 442     if (Sema::TemplateDeductionResult Result
 443           = DeduceTemplateArguments(S, TemplateParams,
 444                                     Param->getTemplateName(),
 445                                     SpecArg->getTemplateName(),
 446                                     Info, Deduced))
 447       return Result;
 448
 449
 450     // Perform template argument deduction on each template
 451     // argument. Ignore any missing/extra arguments, since they could be
 452     // filled in by default arguments.
 453     return DeduceTemplateArguments(S, TemplateParams,
 454                                    Param->getArgs(), Param->getNumArgs(),
 455                                    SpecArg->getArgs(), SpecArg->getNumArgs(),
 456                                    Info, Deduced,
 457                                    /*NumberOfArgumentsMustMatch=*/false);
 458   }
 459
 460   // If the argument type is a class template specialization, we
 461   // perform template argument deduction using its template
 462   // arguments.
 463   const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
 464   if (!RecordArg)
 465     return Sema::TDK_NonDeducedMismatch;
 466
 467   ClassTemplateSpecializationDecl *SpecArg
 468     = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
 469   if (!SpecArg)
 470     return Sema::TDK_NonDeducedMismatch;
 471
 472   // Perform template argument deduction for the template name.
 473   if (Sema::TemplateDeductionResult Result
 474         = DeduceTemplateArguments(S,
 475                                   TemplateParams,
 476                                   Param->getTemplateName(),
 477                                TemplateName(SpecArg->getSpecializedTemplate()),
 478                                   Info, Deduced))
 479     return Result;
 480
 481   // Perform template argument deduction for the template arguments.
 482   return DeduceTemplateArguments(S, TemplateParams,
 483                                  Param->getArgs(), Param->getNumArgs(),
 484                                  SpecArg->getTemplateArgs().data(),
 485                                  SpecArg->getTemplateArgs().size(),
 486                                  Info, Deduced);
 487 }
 488
 489 /// \brief Determines whether the given type is an opaque type that
 490 /// might be more qualified when instantiated.
 491 static bool IsPossiblyOpaquelyQualifiedType(QualType T) {
 492   switch (T->getTypeClass()) {
 493   case Type::TypeOfExpr:
 494   case Type::TypeOf:
 495   case Type::DependentName:
 496   case Type::Decltype:
 497   case Type::UnresolvedUsing:
 498   case Type::TemplateTypeParm:
 499     return true;
 500
 501   case Type::ConstantArray:
 502   case Type::IncompleteArray:
 503   case Type::VariableArray:
 504   case Type::DependentSizedArray:
 505     return IsPossiblyOpaquelyQualifiedType(
 506                                       cast<ArrayType>(T)->getElementType());
 507
 508   default:
 509     return false;
 510   }
 511 }
 512
 513 /// \brief Retrieve the depth and index of a template parameter.
 514 static std::pair<unsigned, unsigned>
 515 getDepthAndIndex(NamedDecl *ND) {
 516   if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
 517     return std::make_pair(TTP->getDepth(), TTP->getIndex());
 518
 519   if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
 520     return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
 521
 522   TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
 523   return std::make_pair(TTP->getDepth(), TTP->getIndex());
 524 }
 525
 526 /// \brief Retrieve the depth and index of an unexpanded parameter pack.
 527 static std::pair<unsigned, unsigned>
 528 getDepthAndIndex(UnexpandedParameterPack UPP) {
 529   if (const TemplateTypeParmType *TTP
 530                           = UPP.first.dyn_cast<const TemplateTypeParmType *>())
 531     return std::make_pair(TTP->getDepth(), TTP->getIndex());
 532
 533   return getDepthAndIndex(UPP.first.get<NamedDecl *>());
 534 }
 535
 536 /// \brief Helper function to build a TemplateParameter when we don't
 537 /// know its type statically.
 538 static TemplateParameter makeTemplateParameter(Decl *D) {
 539   if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
 540     return TemplateParameter(TTP);
 541   else if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
 542     return TemplateParameter(NTTP);
 543
 544   return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
 545 }
 546
 547 /// \brief Prepare to perform template argument deduction for all of the
 548 /// arguments in a set of argument packs.
 549 static void PrepareArgumentPackDeduction(Sema &S,
 550                        llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
 551                              const llvm::SmallVectorImpl<unsigned> &PackIndices,
 552                      llvm::SmallVectorImpl<DeducedTemplateArgument> &SavedPacks,
 553          llvm::SmallVectorImpl<
 554            llvm::SmallVector<DeducedTemplateArgument, 4> > &NewlyDeducedPacks) {
 555   // Save the deduced template arguments for each parameter pack expanded
 556   // by this pack expansion, then clear out the deduction.
 557   for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
 558     // Save the previously-deduced argument pack, then clear it out so that we
 559     // can deduce a new argument pack.
 560     SavedPacks[I] = Deduced[PackIndices[I]];
 561     Deduced[PackIndices[I]] = TemplateArgument();
 562
 563     // If the template arugment pack was explicitly specified, add that to
 564     // the set of deduced arguments.
 565     const TemplateArgument *ExplicitArgs;
 566     unsigned NumExplicitArgs;
 567     if (NamedDecl *PartiallySubstitutedPack
 568         = S.CurrentInstantiationScope->getPartiallySubstitutedPack(
 569                                                            &ExplicitArgs,
 570                                                            &NumExplicitArgs)) {
 571       if (getDepthAndIndex(PartiallySubstitutedPack).second == PackIndices[I])
 572         NewlyDeducedPacks[I].append(ExplicitArgs,
 573                                     ExplicitArgs + NumExplicitArgs);
 574     }
 575   }
 576 }
 577
 578 /// \brief Finish template argument deduction for a set of argument packs,
 579 /// producing the argument packs and checking for consistency with prior
 580 /// deductions.
 581 static Sema::TemplateDeductionResult
 582 FinishArgumentPackDeduction(Sema &S,
 583                             TemplateParameterList *TemplateParams,
 584                             bool HasAnyArguments,
 585                         llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
 586                             const llvm::SmallVectorImpl<unsigned> &PackIndices,
 587                     llvm::SmallVectorImpl<DeducedTemplateArgument> &SavedPacks,
 588         llvm::SmallVectorImpl<
 589           llvm::SmallVector<DeducedTemplateArgument, 4> > &NewlyDeducedPacks,
 590                             TemplateDeductionInfo &Info) {
 591   // Build argument packs for each of the parameter packs expanded by this
 592   // pack expansion.
 593   for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
 594     if (HasAnyArguments && NewlyDeducedPacks[I].empty()) {
 595       // We were not able to deduce anything for this parameter pack,
 596       // so just restore the saved argument pack.
 597       Deduced[PackIndices[I]] = SavedPacks[I];
 598       continue;
 599     }
 600
 601     DeducedTemplateArgument NewPack;
 602
 603     if (NewlyDeducedPacks[I].empty()) {
 604       // If we deduced an empty argument pack, create it now.
 605       NewPack = DeducedTemplateArgument(TemplateArgument(0, 0));
 606     } else {
 607       TemplateArgument *ArgumentPack
 608         = new (S.Context) TemplateArgument [NewlyDeducedPacks[I].size()];
 609       std::copy(NewlyDeducedPacks[I].begin(), NewlyDeducedPacks[I].end(),
 610                 ArgumentPack);
 611       NewPack
 612         = DeducedTemplateArgument(TemplateArgument(ArgumentPack,
 613                                                    NewlyDeducedPacks[I].size()),
 614                             NewlyDeducedPacks[I][0].wasDeducedFromArrayBound());
 615     }
 616
 617     DeducedTemplateArgument Result
 618       = checkDeducedTemplateArguments(S.Context, SavedPacks[I], NewPack);
 619     if (Result.isNull()) {
 620       Info.Param
 621         = makeTemplateParameter(TemplateParams->getParam(PackIndices[I]));
 622       Info.FirstArg = SavedPacks[I];
 623       Info.SecondArg = NewPack;
 624       return Sema::TDK_Inconsistent;
 625     }
 626
 627     Deduced[PackIndices[I]] = Result;
 628   }
 629
 630   return Sema::TDK_Success;
 631 }
 632
 633 /// \brief Deduce the template arguments by comparing the list of parameter
 634 /// types to the list of argument types, as in the parameter-type-lists of
 635 /// function types (C++ [temp.deduct.type]p10).
 636 ///
 637 /// \param S The semantic analysis object within which we are deducing
 638 ///
 639 /// \param TemplateParams The template parameters that we are deducing
 640 ///
 641 /// \param Params The list of parameter types
 642 ///
 643 /// \param NumParams The number of types in \c Params
 644 ///
 645 /// \param Args The list of argument types
 646 ///
 647 /// \param NumArgs The number of types in \c Args
 648 ///
 649 /// \param Info information about the template argument deduction itself
 650 ///
 651 /// \param Deduced the deduced template arguments
 652 ///
 653 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
 654 /// how template argument deduction is performed.
 655 ///
 656 /// \param PartialOrdering If true, we are performing template argument
 657 /// deduction for during partial ordering for a call
 658 /// (C++0x [temp.deduct.partial]).
 659 ///
 660 /// \param RefParamComparisons If we're performing template argument deduction
 661 /// in the context of partial ordering, the set of qualifier comparisons.
 662 ///
 663 /// \returns the result of template argument deduction so far. Note that a
 664 /// "success" result means that template argument deduction has not yet failed,
 665 /// but it may still fail, later, for other reasons.
 666 static Sema::TemplateDeductionResult
 667 DeduceTemplateArguments(Sema &S,
 668                         TemplateParameterList *TemplateParams,
 669                         const QualType *Params, unsigned NumParams,
 670                         const QualType *Args, unsigned NumArgs,
 671                         TemplateDeductionInfo &Info,
 672                       llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
 673                         unsigned TDF,
 674                         bool PartialOrdering = false,
 675                         llvm::SmallVectorImpl<RefParamPartialOrderingComparison> *
 676                                                      RefParamComparisons = 0) {
 677   // Fast-path check to see if we have too many/too few arguments.
 678   if (NumParams != NumArgs &&
 679       !(NumParams && isa<PackExpansionType>(Params[NumParams - 1])) &&
 680       !(NumArgs && isa<PackExpansionType>(Args[NumArgs - 1])))
 681     return Sema::TDK_NonDeducedMismatch;
 682
 683   // C++0x [temp.deduct.type]p10:
 684   //   Similarly, if P has a form that contains (T), then each parameter type
 685   //   Pi of the respective parameter-type- list of P is compared with the
 686   //   corresponding parameter type Ai of the corresponding parameter-type-list
 687   //   of A. [...]
 688   unsigned ArgIdx = 0, ParamIdx = 0;
 689   for (; ParamIdx != NumParams; ++ParamIdx) {
 690     // Check argument types.
 691     const PackExpansionType *Expansion
 692                                 = dyn_cast<PackExpansionType>(Params[ParamIdx]);
 693     if (!Expansion) {
 694       // Simple case: compare the parameter and argument types at this point.
 695
 696       // Make sure we have an argument.
 697       if (ArgIdx >= NumArgs)
 698         return Sema::TDK_NonDeducedMismatch;
 699
 700       if (isa<PackExpansionType>(Args[ArgIdx])) {
 701         // C++0x [temp.deduct.type]p22:
 702         //   If the original function parameter associated with A is a function
 703         //   parameter pack and the function parameter associated with P is not
 704         //   a function parameter pack, then template argument deduction fails.
 705         return Sema::TDK_NonDeducedMismatch;
 706       }
 707
 708       if (Sema::TemplateDeductionResult Result
 709             = DeduceTemplateArguments(S, TemplateParams,
 710                                       Params[ParamIdx],
 711                                       Args[ArgIdx],
 712                                       Info, Deduced, TDF,
 713                                       PartialOrdering,
 714                                       RefParamComparisons))
 715         return Result;
 716
 717       ++ArgIdx;
 718       continue;
 719     }
 720
 721     // C++0x [temp.deduct.type]p5:
 722     //   The non-deduced contexts are:
 723     //     - A function parameter pack that does not occur at the end of the
 724     //       parameter-declaration-clause.
 725     if (ParamIdx + 1 < NumParams)
 726       return Sema::TDK_Success;
 727
 728     // C++0x [temp.deduct.type]p10:
 729     //   If the parameter-declaration corresponding to Pi is a function
 730     //   parameter pack, then the type of its declarator- id is compared with
 731     //   each remaining parameter type in the parameter-type-list of A. Each
 732     //   comparison deduces template arguments for subsequent positions in the
 733     //   template parameter packs expanded by the function parameter pack.
 734
 735     // Compute the set of template parameter indices that correspond to
 736     // parameter packs expanded by the pack expansion.
 737     llvm::SmallVector<unsigned, 2> PackIndices;
 738     QualType Pattern = Expansion->getPattern();
 739     {
 740       llvm::BitVector SawIndices(TemplateParams->size());
 741       llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 742       S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
 743       for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
 744         unsigned Depth, Index;
 745         llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
 746         if (Depth == 0 && !SawIndices[Index]) {
 747           SawIndices[Index] = true;
 748           PackIndices.push_back(Index);
 749         }
 750       }
 751     }
 752     assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
 753
 754     // Keep track of the deduced template arguments for each parameter pack
 755     // expanded by this pack expansion (the outer index) and for each
 756     // template argument (the inner SmallVectors).
 757     llvm::SmallVector<llvm::SmallVector<DeducedTemplateArgument, 4>, 2>
 758       NewlyDeducedPacks(PackIndices.size());
 759     llvm::SmallVector<DeducedTemplateArgument, 2>
 760       SavedPacks(PackIndices.size());
 761     PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks,
 762                                  NewlyDeducedPacks);
 763
 764     bool HasAnyArguments = false;
 765     for (; ArgIdx < NumArgs; ++ArgIdx) {
 766       HasAnyArguments = true;
 767
 768       // Deduce template arguments from the pattern.
 769       if (Sema::TemplateDeductionResult Result
 770             = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
 771                                       Info, Deduced, TDF, PartialOrdering,
 772                                       RefParamComparisons))
 773         return Result;
 774
 775       // Capture the deduced template arguments for each parameter pack expanded
 776       // by this pack expansion, add them to the list of arguments we've deduced
 777       // for that pack, then clear out the deduced argument.
 778       for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
 779         DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
 780         if (!DeducedArg.isNull()) {
 781           NewlyDeducedPacks[I].push_back(DeducedArg);
 782           DeducedArg = DeducedTemplateArgument();
 783         }
 784       }
 785     }
 786
 787     // Build argument packs for each of the parameter packs expanded by this
 788     // pack expansion.
 789     if (Sema::TemplateDeductionResult Result
 790           = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments,
 791                                         Deduced, PackIndices, SavedPacks,
 792                                         NewlyDeducedPacks, Info))
 793       return Result;
 794   }
 795
 796   // Make sure we don't have any extra arguments.
 797   if (ArgIdx < NumArgs)
 798     return Sema::TDK_NonDeducedMismatch;
 799
 800   return Sema::TDK_Success;
 801 }
 802
 803 /// \brief Deduce the template arguments by comparing the parameter type and
 804 /// the argument type (C++ [temp.deduct.type]).
 805 ///
 806 /// \param S the semantic analysis object within which we are deducing
 807 ///
 808 /// \param TemplateParams the template parameters that we are deducing
 809 ///
 810 /// \param ParamIn the parameter type
 811 ///
 812 /// \param ArgIn the argument type
 813 ///
 814 /// \param Info information about the template argument deduction itself
 815 ///
 816 /// \param Deduced the deduced template arguments
 817 ///
 818 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
 819 /// how template argument deduction is performed.
 820 ///
 821 /// \param PartialOrdering Whether we're performing template argument deduction
 822 /// in the context of partial ordering (C++0x [temp.deduct.partial]).
 823 ///
 824 /// \param RefParamComparisons If we're performing template argument deduction
 825 /// in the context of partial ordering, the set of qualifier comparisons.
 826 ///
 827 /// \returns the result of template argument deduction so far. Note that a
 828 /// "success" result means that template argument deduction has not yet failed,
 829 /// but it may still fail, later, for other reasons.
 830 static Sema::TemplateDeductionResult
 831 DeduceTemplateArguments(Sema &S,
 832                         TemplateParameterList *TemplateParams,
 833                         QualType ParamIn, QualType ArgIn,
 834                         TemplateDeductionInfo &Info,
 835                      llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
 836                         unsigned TDF,
 837                         bool PartialOrdering,
 838     llvm::SmallVectorImpl<RefParamPartialOrderingComparison> *RefParamComparisons) {
 839   // We only want to look at the canonical types, since typedefs and
 840   // sugar are not part of template argument deduction.
 841   QualType Param = S.Context.getCanonicalType(ParamIn);
 842   QualType Arg = S.Context.getCanonicalType(ArgIn);
 843
 844   // If the argument type is a pack expansion, look at its pattern.
 845   // This isn't explicitly called out
 846   if (const PackExpansionType *ArgExpansion
 847                                             = dyn_cast<PackExpansionType>(Arg))
 848     Arg = ArgExpansion->getPattern();
 849
 850   if (PartialOrdering) {
 851     // C++0x [temp.deduct.partial]p5:
 852     //   Before the partial ordering is done, certain transformations are
 853     //   performed on the types used for partial ordering:
 854     //     - If P is a reference type, P is replaced by the type referred to.
 855     const ReferenceType *ParamRef = Param->getAs<ReferenceType>();
 856     if (ParamRef)
 857       Param = ParamRef->getPointeeType();
 858
 859     //     - If A is a reference type, A is replaced by the type referred to.
 860     const ReferenceType *ArgRef = Arg->getAs<ReferenceType>();
 861     if (ArgRef)
 862       Arg = ArgRef->getPointeeType();
 863
 864     if (RefParamComparisons && ParamRef && ArgRef) {
 865       // C++0x [temp.deduct.partial]p6:
 866       //   If both P and A were reference types (before being replaced with the
 867       //   type referred to above), determine which of the two types (if any) is
 868       //   more cv-qualified than the other; otherwise the types are considered
 869       //   to be equally cv-qualified for partial ordering purposes. The result
 870       //   of this determination will be used below.
 871       //
 872       // We save this information for later, using it only when deduction
 873       // succeeds in both directions.
 874       RefParamPartialOrderingComparison Comparison;
 875       Comparison.ParamIsRvalueRef = ParamRef->getAs<RValueReferenceType>();
 876       Comparison.ArgIsRvalueRef = ArgRef->getAs<RValueReferenceType>();
 877       Comparison.Qualifiers = NeitherMoreQualified;
 878       if (Param.isMoreQualifiedThan(Arg))
 879         Comparison.Qualifiers = ParamMoreQualified;
 880       else if (Arg.isMoreQualifiedThan(Param))
 881         Comparison.Qualifiers = ArgMoreQualified;
 882       RefParamComparisons->push_back(Comparison);
 883     }
 884
 885     // C++0x [temp.deduct.partial]p7:
 886     //   Remove any top-level cv-qualifiers:
 887     //     - If P is a cv-qualified type, P is replaced by the cv-unqualified
 888     //       version of P.
 889     Param = Param.getUnqualifiedType();
 890     //     - If A is a cv-qualified type, A is replaced by the cv-unqualified
 891     //       version of A.
 892     Arg = Arg.getUnqualifiedType();
 893   } else {
 894     // C++0x [temp.deduct.call]p4 bullet 1:
 895     //   - If the original P is a reference type, the deduced A (i.e., the type
 896     //     referred to by the reference) can be more cv-qualified than the
 897     //     transformed A.
 898     if (TDF & TDF_ParamWithReferenceType) {
 899       Qualifiers Quals;
 900       QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals);
 901       Quals.setCVRQualifiers(Quals.getCVRQualifiers() &
 902                              Arg.getCVRQualifiers());
 903       Param = S.Context.getQualifiedType(UnqualParam, Quals);
 904     }
 905
 906     if ((TDF & TDF_TopLevelParameterTypeList) && !Param->isFunctionType()) {
 907       // C++0x [temp.deduct.type]p10:
 908       //   If P and A are function types that originated from deduction when
 909       //   taking the address of a function template (14.8.2.2) or when deducing
 910       //   template arguments from a function declaration (14.8.2.6) and Pi and
 911       //   Ai are parameters of the top-level parameter-type-list of P and A,
 912       //   respectively, Pi is adjusted if it is an rvalue reference to a
 913       //   cv-unqualified template parameter and Ai is an lvalue reference, in
 914       //   which case the type of Pi is changed to be the template parameter
 915       //   type (i.e., T&& is changed to simply T). [ Note: As a result, when
 916       //   Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
 917       //   deduced as X&. - end note ]
 918       TDF &= ~TDF_TopLevelParameterTypeList;
 919
 920       if (const RValueReferenceType *ParamRef
 921                                         = Param->getAs<RValueReferenceType>()) {
 922         if (isa<TemplateTypeParmType>(ParamRef->getPointeeType()) &&
 923             !ParamRef->getPointeeType().getQualifiers())
 924           if (Arg->isLValueReferenceType())
 925             Param = ParamRef->getPointeeType();
 926       }
 927     }
 928   }
 929
 930   // If the parameter type is not dependent, there is nothing to deduce.
 931   if (!Param->isDependentType()) {
 932     if (!(TDF & TDF_SkipNonDependent) && Param != Arg)
 933       return Sema::TDK_NonDeducedMismatch;
 934
 935     return Sema::TDK_Success;
 936   }
 937
 938   // C++ [temp.deduct.type]p9:
 939   //   A template type argument T, a template template argument TT or a
 940   //   template non-type argument i can be deduced if P and A have one of
 941   //   the following forms:
 942   //
 943   //     T
 944   //     cv-list T
 945   if (const TemplateTypeParmType *TemplateTypeParm
 946         = Param->getAs<TemplateTypeParmType>()) {
 947     unsigned Index = TemplateTypeParm->getIndex();
 948     bool RecanonicalizeArg = false;
 949
 950     // If the argument type is an array type, move the qualifiers up to the
 951     // top level, so they can be matched with the qualifiers on the parameter.
 952     // FIXME: address spaces, ObjC GC qualifiers
 953     if (isa<ArrayType>(Arg)) {
 954       Qualifiers Quals;
 955       Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
 956       if (Quals) {
 957         Arg = S.Context.getQualifiedType(Arg, Quals);
 958         RecanonicalizeArg = true;
 959       }
 960     }
 961
 962     // The argument type can not be less qualified than the parameter
 963     // type.
 964     if (Param.isMoreQualifiedThan(Arg) && !(TDF & TDF_IgnoreQualifiers)) {
 965       Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
 966       Info.FirstArg = TemplateArgument(Param);
 967       Info.SecondArg = TemplateArgument(Arg);
 968       return Sema::TDK_Underqualified;
 969     }
 970
 971     assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
 972     assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function");
 973     QualType DeducedType = Arg;
 974
 975     // local manipulation is okay because it's canonical
 976     DeducedType.removeLocalCVRQualifiers(Param.getCVRQualifiers());
 977     if (RecanonicalizeArg)
 978       DeducedType = S.Context.getCanonicalType(DeducedType);
 979
 980     DeducedTemplateArgument NewDeduced(DeducedType);
 981     DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
 982                                                                  Deduced[Index],
 983                                                                    NewDeduced);
 984     if (Result.isNull()) {
 985       Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
 986       Info.FirstArg = Deduced[Index];
 987       Info.SecondArg = NewDeduced;
 988       return Sema::TDK_Inconsistent;
 989     }
 990
 991     Deduced[Index] = Result;
 992     return Sema::TDK_Success;
 993   }
 994
 995   // Set up the template argument deduction information for a failure.
 996   Info.FirstArg = TemplateArgument(ParamIn);
 997   Info.SecondArg = TemplateArgument(ArgIn);
 998
 999   // If the parameter is an already-substituted template parameter
1000   // pack, do nothing: we don't know which of its arguments to look
1001   // at, so we have to wait until all of the parameter packs in this
1002   // expansion have arguments.
1003   if (isa<SubstTemplateTypeParmPackType>(Param))
1004     return Sema::TDK_Success;
1005
1006   // Check the cv-qualifiers on the parameter and argument types.
1007   if (!(TDF & TDF_IgnoreQualifiers)) {
1008     if (TDF & TDF_ParamWithReferenceType) {
1009       if (Param.isMoreQualifiedThan(Arg))
1010         return Sema::TDK_NonDeducedMismatch;
1011     } else if (!IsPossiblyOpaquelyQualifiedType(Param)) {
1012       if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
1013         return Sema::TDK_NonDeducedMismatch;
1014     }
1015   }
1016
1017   switch (Param->getTypeClass()) {
1018     // No deduction possible for these types
1019     case Type::Builtin:
1020       return Sema::TDK_NonDeducedMismatch;
1021
1022     //     T *
1023     case Type::Pointer: {
1024       QualType PointeeType;
1025       if (const PointerType *PointerArg = Arg->getAs<PointerType>()) {
1026         PointeeType = PointerArg->getPointeeType();
1027       } else if (const ObjCObjectPointerType *PointerArg
1028                    = Arg->getAs<ObjCObjectPointerType>()) {
1029         PointeeType = PointerArg->getPointeeType();
1030       } else {
1031         return Sema::TDK_NonDeducedMismatch;
1032       }
1033
1034       unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass);
1035       return DeduceTemplateArguments(S, TemplateParams,
1036                                    cast<PointerType>(Param)->getPointeeType(),
1037                                      PointeeType,
1038                                      Info, Deduced, SubTDF);
1039     }
1040
1041     //     T &
1042     case Type::LValueReference: {
1043       const LValueReferenceType *ReferenceArg = Arg->getAs<LValueReferenceType>();
1044       if (!ReferenceArg)
1045         return Sema::TDK_NonDeducedMismatch;
1046
1047       return DeduceTemplateArguments(S, TemplateParams,
1048                            cast<LValueReferenceType>(Param)->getPointeeType(),
1049                                      ReferenceArg->getPointeeType(),
1050                                      Info, Deduced, 0);
1051     }
1052
1053     //     T && [C++0x]
1054     case Type::RValueReference: {
1055       const RValueReferenceType *ReferenceArg = Arg->getAs<RValueReferenceType>();
1056       if (!ReferenceArg)
1057         return Sema::TDK_NonDeducedMismatch;
1058
1059       return DeduceTemplateArguments(S, TemplateParams,
1060                            cast<RValueReferenceType>(Param)->getPointeeType(),
1061                                      ReferenceArg->getPointeeType(),
1062                                      Info, Deduced, 0);
1063     }
1064
1065     //     T [] (implied, but not stated explicitly)
1066     case Type::IncompleteArray: {
1067       const IncompleteArrayType *IncompleteArrayArg =
1068         S.Context.getAsIncompleteArrayType(Arg);
1069       if (!IncompleteArrayArg)
1070         return Sema::TDK_NonDeducedMismatch;
1071
1072       unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1073       return DeduceTemplateArguments(S, TemplateParams,
1074                      S.Context.getAsIncompleteArrayType(Param)->getElementType(),
1075                                      IncompleteArrayArg->getElementType(),
1076                                      Info, Deduced, SubTDF);
1077     }
1078
1079     //     T [integer-constant]
1080     case Type::ConstantArray: {
1081       const ConstantArrayType *ConstantArrayArg =
1082         S.Context.getAsConstantArrayType(Arg);
1083       if (!ConstantArrayArg)
1084         return Sema::TDK_NonDeducedMismatch;
1085
1086       const ConstantArrayType *ConstantArrayParm =
1087         S.Context.getAsConstantArrayType(Param);
1088       if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
1089         return Sema::TDK_NonDeducedMismatch;
1090
1091       unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1092       return DeduceTemplateArguments(S, TemplateParams,
1093                                      ConstantArrayParm->getElementType(),
1094                                      ConstantArrayArg->getElementType(),
1095                                      Info, Deduced, SubTDF);
1096     }
1097
1098     //     type [i]
1099     case Type::DependentSizedArray: {
1100       const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg);
1101       if (!ArrayArg)
1102         return Sema::TDK_NonDeducedMismatch;
1103
1104       unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1105
1106       // Check the element type of the arrays
1107       const DependentSizedArrayType *DependentArrayParm
1108         = S.Context.getAsDependentSizedArrayType(Param);
1109       if (Sema::TemplateDeductionResult Result
1110             = DeduceTemplateArguments(S, TemplateParams,
1111                                       DependentArrayParm->getElementType(),
1112                                       ArrayArg->getElementType(),
1113                                       Info, Deduced, SubTDF))
1114         return Result;
1115
1116       // Determine the array bound is something we can deduce.
1117       NonTypeTemplateParmDecl *NTTP
1118         = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
1119       if (!NTTP)
1120         return Sema::TDK_Success;
1121
1122       // We can perform template argument deduction for the given non-type
1123       // template parameter.
1124       assert(NTTP->getDepth() == 0 &&
1125              "Cannot deduce non-type template argument at depth > 0");
1126       if (const ConstantArrayType *ConstantArrayArg
1127             = dyn_cast<ConstantArrayType>(ArrayArg)) {
1128         llvm::APSInt Size(ConstantArrayArg->getSize());
1129         return DeduceNonTypeTemplateArgument(S, NTTP, Size,
1130                                              S.Context.getSizeType(),
1131                                              /*ArrayBound=*/true,
1132                                              Info, Deduced);
1133       }
1134       if (const DependentSizedArrayType *DependentArrayArg
1135             = dyn_cast<DependentSizedArrayType>(ArrayArg))
1136         if (DependentArrayArg->getSizeExpr())
1137           return DeduceNonTypeTemplateArgument(S, NTTP,
1138                                                DependentArrayArg->getSizeExpr(),
1139                                                Info, Deduced);
1140
1141       // Incomplete type does not match a dependently-sized array type
1142       return Sema::TDK_NonDeducedMismatch;
1143     }
1144
1145     //     type(*)(T)
1146     //     T(*)()
1147     //     T(*)(T)
1148     case Type::FunctionProto: {
1149       unsigned SubTDF = TDF & TDF_TopLevelParameterTypeList;
1150       const FunctionProtoType *FunctionProtoArg =
1151         dyn_cast<FunctionProtoType>(Arg);
1152       if (!FunctionProtoArg)
1153         return Sema::TDK_NonDeducedMismatch;
1154
1155       const FunctionProtoType *FunctionProtoParam =
1156         cast<FunctionProtoType>(Param);
1157
1158       if (FunctionProtoParam->getTypeQuals()
1159             != FunctionProtoArg->getTypeQuals() ||
1160           FunctionProtoParam->getRefQualifier()
1161             != FunctionProtoArg->getRefQualifier() ||
1162           FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
1163         return Sema::TDK_NonDeducedMismatch;
1164
1165       // Check return types.
1166       if (Sema::TemplateDeductionResult Result
1167             = DeduceTemplateArguments(S, TemplateParams,
1168                                       FunctionProtoParam->getResultType(),
1169                                       FunctionProtoArg->getResultType(),
1170                                       Info, Deduced, 0))
1171         return Result;
1172
1173       return DeduceTemplateArguments(S, TemplateParams,
1174                                      FunctionProtoParam->arg_type_begin(),
1175                                      FunctionProtoParam->getNumArgs(),
1176                                      FunctionProtoArg->arg_type_begin(),
1177                                      FunctionProtoArg->getNumArgs(),
1178                                      Info, Deduced, SubTDF);
1179     }
1180
1181     case Type::InjectedClassName: {
1182       // Treat a template's injected-class-name as if the template
1183       // specialization type had been used.
1184       Param = cast<InjectedClassNameType>(Param)
1185         ->getInjectedSpecializationType();
1186       assert(isa<TemplateSpecializationType>(Param) &&
1187              "injected class name is not a template specialization type");
1188       // fall through
1189     }
1190
1191     //     template-name<T> (where template-name refers to a class template)
1192     //     template-name<i>
1193     //     TT<T>
1194     //     TT<i>
1195     //     TT<>
1196     case Type::TemplateSpecialization: {
1197       const TemplateSpecializationType *SpecParam
1198         = cast<TemplateSpecializationType>(Param);
1199
1200       // Try to deduce template arguments from the template-id.
1201       Sema::TemplateDeductionResult Result
1202         = DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg,
1203                                   Info, Deduced);
1204
1205       if (Result && (TDF & TDF_DerivedClass)) {
1206         // C++ [temp.deduct.call]p3b3:
1207         //   If P is a class, and P has the form template-id, then A can be a
1208         //   derived class of the deduced A. Likewise, if P is a pointer to a
1209         //   class of the form template-id, A can be a pointer to a derived
1210         //   class pointed to by the deduced A.
1211         //
1212         // More importantly:
1213         //   These alternatives are considered only if type deduction would
1214         //   otherwise fail.
1215         if (const RecordType *RecordT = Arg->getAs<RecordType>()) {
1216           // We cannot inspect base classes as part of deduction when the type
1217           // is incomplete, so either instantiate any templates necessary to
1218           // complete the type, or skip over it if it cannot be completed.
1219           if (S.RequireCompleteType(Info.getLocation(), Arg, 0))
1220             return Result;
1221
1222           // Use data recursion to crawl through the list of base classes.
1223           // Visited contains the set of nodes we have already visited, while
1224           // ToVisit is our stack of records that we still need to visit.
1225           llvm::SmallPtrSet<const RecordType *, 8> Visited;
1226           llvm::SmallVector<const RecordType *, 8> ToVisit;
1227           ToVisit.push_back(RecordT);
1228           bool Successful = false;
1229           llvm::SmallVectorImpl<DeducedTemplateArgument> DeducedOrig(0);
1230           DeducedOrig = Deduced;
1231           while (!ToVisit.empty()) {
1232             // Retrieve the next class in the inheritance hierarchy.
1233             const RecordType *NextT = ToVisit.back();
1234             ToVisit.pop_back();
1235
1236             // If we have already seen this type, skip it.
1237             if (!Visited.insert(NextT))
1238               continue;
1239
1240             // If this is a base class, try to perform template argument
1241             // deduction from it.
1242             if (NextT != RecordT) {
1243               Sema::TemplateDeductionResult BaseResult
1244                 = DeduceTemplateArguments(S, TemplateParams, SpecParam,
1245                                           QualType(NextT, 0), Info, Deduced);
1246
1247               // If template argument deduction for this base was successful,
1248               // note that we had some success. Otherwise, ignore any deductions
1249               // from this base class.
1250               if (BaseResult == Sema::TDK_Success) {
1251                 Successful = true;
1252                 DeducedOrig = Deduced;
1253               }
1254               else
1255                 Deduced = DeducedOrig;
1256             }
1257
1258             // Visit base classes
1259             CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
1260             for (CXXRecordDecl::base_class_iterator Base = Next->bases_begin(),
1261                                                  BaseEnd = Next->bases_end();
1262                  Base != BaseEnd; ++Base) {
1263               assert(Base->getType()->isRecordType() &&
1264                      "Base class that isn't a record?");
1265               ToVisit.push_back(Base->getType()->getAs<RecordType>());
1266             }
1267           }
1268
1269           if (Successful)
1270             return Sema::TDK_Success;
1271         }
1272
1273       }
1274
1275       return Result;
1276     }
1277
1278     //     T type::*
1279     //     T T::*
1280     //     T (type::*)()
1281     //     type (T::*)()
1282     //     type (type::*)(T)
1283     //     type (T::*)(T)
1284     //     T (type::*)(T)
1285     //     T (T::*)()
1286     //     T (T::*)(T)
1287     case Type::MemberPointer: {
1288       const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
1289       const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
1290       if (!MemPtrArg)
1291         return Sema::TDK_NonDeducedMismatch;
1292
1293       if (Sema::TemplateDeductionResult Result
1294             = DeduceTemplateArguments(S, TemplateParams,
1295                                       MemPtrParam->getPointeeType(),
1296                                       MemPtrArg->getPointeeType(),
1297                                       Info, Deduced,
1298                                       TDF & TDF_IgnoreQualifiers))
1299         return Result;
1300
1301       return DeduceTemplateArguments(S, TemplateParams,
1302                                      QualType(MemPtrParam->getClass(), 0),
1303                                      QualType(MemPtrArg->getClass(), 0),
1304                                      Info, Deduced, 0);
1305     }
1306
1307     //     (clang extension)
1308     //
1309     //     type(^)(T)
1310     //     T(^)()
1311     //     T(^)(T)
1312     case Type::BlockPointer: {
1313       const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
1314       const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
1315
1316       if (!BlockPtrArg)
1317         return Sema::TDK_NonDeducedMismatch;
1318
1319       return DeduceTemplateArguments(S, TemplateParams,
1320                                      BlockPtrParam->getPointeeType(),
1321                                      BlockPtrArg->getPointeeType(), Info,
1322                                      Deduced, 0);
1323     }
1324
1325     case Type::TypeOfExpr:
1326     case Type::TypeOf:
1327     case Type::DependentName:
1328       // No template argument deduction for these types
1329       return Sema::TDK_Success;
1330
1331     default:
1332       break;
1333   }
1334
1335   // FIXME: Many more cases to go (to go).
1336   return Sema::TDK_Success;
1337 }
1338
1339 static Sema::TemplateDeductionResult
1340 DeduceTemplateArguments(Sema &S,
1341                         TemplateParameterList *TemplateParams,
1342                         const TemplateArgument &Param,
1343                         TemplateArgument Arg,
1344                         TemplateDeductionInfo &Info,
1345                     llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1346   // If the template argument is a pack expansion, perform template argument
1347   // deduction against the pattern of that expansion. This only occurs during
1348   // partial ordering.
1349   if (Arg.isPackExpansion())
1350     Arg = Arg.getPackExpansionPattern();
1351
1352   switch (Param.getKind()) {
1353   case TemplateArgument::Null:
1354     assert(false && "Null template argument in parameter list");
1355     break;
1356
1357   case TemplateArgument::Type:
1358     if (Arg.getKind() == TemplateArgument::Type)
1359       return DeduceTemplateArguments(S, TemplateParams, Param.getAsType(),
1360                                      Arg.getAsType(), Info, Deduced, 0);
1361     Info.FirstArg = Param;
1362     Info.SecondArg = Arg;
1363     return Sema::TDK_NonDeducedMismatch;
1364
1365   case TemplateArgument::Template:
1366     if (Arg.getKind() == TemplateArgument::Template)
1367       return DeduceTemplateArguments(S, TemplateParams,
1368                                      Param.getAsTemplate(),
1369                                      Arg.getAsTemplate(), Info, Deduced);
1370     Info.FirstArg = Param;
1371     Info.SecondArg = Arg;
1372     return Sema::TDK_NonDeducedMismatch;
1373
1374   case TemplateArgument::TemplateExpansion:
1375     llvm_unreachable("caller should handle pack expansions");
1376     break;
1377
1378   case TemplateArgument::Declaration:
1379     if (Arg.getKind() == TemplateArgument::Declaration &&
1380         Param.getAsDecl()->getCanonicalDecl() ==
1381           Arg.getAsDecl()->getCanonicalDecl())
1382       return Sema::TDK_Success;
1383
1384     Info.FirstArg = Param;
1385     Info.SecondArg = Arg;
1386     return Sema::TDK_NonDeducedMismatch;
1387
1388   case TemplateArgument::Integral:
1389     if (Arg.getKind() == TemplateArgument::Integral) {
1390       if (hasSameExtendedValue(*Param.getAsIntegral(), *Arg.getAsIntegral()))
1391         return Sema::TDK_Success;
1392
1393       Info.FirstArg = Param;
1394       Info.SecondArg = Arg;
1395       return Sema::TDK_NonDeducedMismatch;
1396     }
1397
1398     if (Arg.getKind() == TemplateArgument::Expression) {
1399       Info.FirstArg = Param;
1400       Info.SecondArg = Arg;
1401       return Sema::TDK_NonDeducedMismatch;
1402     }
1403
1404     Info.FirstArg = Param;
1405     Info.SecondArg = Arg;
1406     return Sema::TDK_NonDeducedMismatch;
1407
1408   case TemplateArgument::Expression: {
1409     if (NonTypeTemplateParmDecl *NTTP
1410           = getDeducedParameterFromExpr(Param.getAsExpr())) {
1411       if (Arg.getKind() == TemplateArgument::Integral)
1412         return DeduceNonTypeTemplateArgument(S, NTTP,
1413                                              *Arg.getAsIntegral(),
1414                                              Arg.getIntegralType(),
1415                                              /*ArrayBound=*/false,
1416                                              Info, Deduced);
1417       if (Arg.getKind() == TemplateArgument::Expression)
1418         return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(),
1419                                              Info, Deduced);
1420       if (Arg.getKind() == TemplateArgument::Declaration)
1421         return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(),
1422                                              Info, Deduced);
1423
1424       Info.FirstArg = Param;
1425       Info.SecondArg = Arg;
1426       return Sema::TDK_NonDeducedMismatch;
1427     }
1428
1429     // Can't deduce anything, but that's okay.
1430     return Sema::TDK_Success;
1431   }
1432   case TemplateArgument::Pack:
1433     llvm_unreachable("Argument packs should be expanded by the caller!");
1434   }
1435
1436   return Sema::TDK_Success;
1437 }
1438
1439 /// \brief Determine whether there is a template argument to be used for
1440 /// deduction.
1441 ///
1442 /// This routine "expands" argument packs in-place, overriding its input
1443 /// parameters so that \c Args[ArgIdx] will be the available template argument.
1444 ///
1445 /// \returns true if there is another template argument (which will be at
1446 /// \c Args[ArgIdx]), false otherwise.
1447 static bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args,
1448                                             unsigned &ArgIdx,
1449                                             unsigned &NumArgs) {
1450   if (ArgIdx == NumArgs)
1451     return false;
1452
1453   const TemplateArgument &Arg = Args[ArgIdx];
1454   if (Arg.getKind() != TemplateArgument::Pack)
1455     return true;
1456
1457   assert(ArgIdx == NumArgs - 1 && "Pack not at the end of argument list?");
1458   Args = Arg.pack_begin();
1459   NumArgs = Arg.pack_size();
1460   ArgIdx = 0;
1461   return ArgIdx < NumArgs;
1462 }
1463
1464 /// \brief Determine whether the given set of template arguments has a pack
1465 /// expansion that is not the last template argument.
1466 static bool hasPackExpansionBeforeEnd(const TemplateArgument *Args,
1467                                       unsigned NumArgs) {
1468   unsigned ArgIdx = 0;
1469   while (ArgIdx < NumArgs) {
1470     const TemplateArgument &Arg = Args[ArgIdx];
1471
1472     // Unwrap argument packs.
1473     if (Args[ArgIdx].getKind() == TemplateArgument::Pack) {
1474       Args = Arg.pack_begin();
1475       NumArgs = Arg.pack_size();
1476       ArgIdx = 0;
1477       continue;
1478     }
1479
1480     ++ArgIdx;
1481     if (ArgIdx == NumArgs)
1482       return false;
1483
1484     if (Arg.isPackExpansion())
1485       return true;
1486   }
1487
1488   return false;
1489 }
1490
1491 static Sema::TemplateDeductionResult
1492 DeduceTemplateArguments(Sema &S,
1493                         TemplateParameterList *TemplateParams,
1494                         const TemplateArgument *Params, unsigned NumParams,
1495                         const TemplateArgument *Args, unsigned NumArgs,
1496                         TemplateDeductionInfo &Info,
1497                     llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
1498                         bool NumberOfArgumentsMustMatch) {
1499   // C++0x [temp.deduct.type]p9:
1500   //   If the template argument list of P contains a pack expansion that is not
1501   //   the last template argument, the entire template argument list is a
1502   //   non-deduced context.
1503   if (hasPackExpansionBeforeEnd(Params, NumParams))
1504     return Sema::TDK_Success;
1505
1506   // C++0x [temp.deduct.type]p9:
1507   //   If P has a form that contains <T> or <i>, then each argument Pi of the
1508   //   respective template argument list P is compared with the corresponding
1509   //   argument Ai of the corresponding template argument list of A.
1510   unsigned ArgIdx = 0, ParamIdx = 0;
1511   for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams);
1512        ++ParamIdx) {
1513     if (!Params[ParamIdx].isPackExpansion()) {
1514       // The simple case: deduce template arguments by matching Pi and Ai.
1515
1516       // Check whether we have enough arguments.
1517       if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
1518         return NumberOfArgumentsMustMatch? Sema::TDK_NonDeducedMismatch
1519                                          : Sema::TDK_Success;
1520
1521       if (Args[ArgIdx].isPackExpansion()) {
1522         // FIXME: We follow the logic of C++0x [temp.deduct.type]p22 here,
1523         // but applied to pack expansions that are template arguments.
1524         return Sema::TDK_NonDeducedMismatch;
1525       }
1526
1527       // Perform deduction for this Pi/Ai pair.
1528       if (Sema::TemplateDeductionResult Result
1529             = DeduceTemplateArguments(S, TemplateParams,
1530                                       Params[ParamIdx], Args[ArgIdx],
1531                                       Info, Deduced))
1532         return Result;
1533
1534       // Move to the next argument.
1535       ++ArgIdx;
1536       continue;
1537     }
1538
1539     // The parameter is a pack expansion.
1540
1541     // C++0x [temp.deduct.type]p9:
1542     //   If Pi is a pack expansion, then the pattern of Pi is compared with
1543     //   each remaining argument in the template argument list of A. Each
1544     //   comparison deduces template arguments for subsequent positions in the
1545     //   template parameter packs expanded by Pi.
1546     TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
1547
1548     // Compute the set of template parameter indices that correspond to
1549     // parameter packs expanded by the pack expansion.
1550     llvm::SmallVector<unsigned, 2> PackIndices;
1551     {
1552       llvm::BitVector SawIndices(TemplateParams->size());
1553       llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
1554       S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
1555       for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
1556         unsigned Depth, Index;
1557         llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
1558         if (Depth == 0 && !SawIndices[Index]) {
1559           SawIndices[Index] = true;
1560           PackIndices.push_back(Index);
1561         }
1562       }
1563     }
1564     assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
1565
1566     // FIXME: If there are no remaining arguments, we can bail out early
1567     // and set any deduced parameter packs to an empty argument pack.
1568     // The latter part of this is a (minor) correctness issue.
1569
1570     // Save the deduced template arguments for each parameter pack expanded
1571     // by this pack expansion, then clear out the deduction.
1572     llvm::SmallVector<DeducedTemplateArgument, 2>
1573       SavedPacks(PackIndices.size());
1574     llvm::SmallVector<llvm::SmallVector<DeducedTemplateArgument, 4>, 2>
1575       NewlyDeducedPacks(PackIndices.size());
1576     PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks,
1577                                  NewlyDeducedPacks);
1578
1579     // Keep track of the deduced template arguments for each parameter pack
1580     // expanded by this pack expansion (the outer index) and for each
1581     // template argument (the inner SmallVectors).
1582     bool HasAnyArguments = false;
1583     while (hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) {
1584       HasAnyArguments = true;
1585
1586       // Deduce template arguments from the pattern.
1587       if (Sema::TemplateDeductionResult Result
1588             = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
1589                                       Info, Deduced))
1590         return Result;
1591
1592       // Capture the deduced template arguments for each parameter pack expanded
1593       // by this pack expansion, add them to the list of arguments we've deduced
1594       // for that pack, then clear out the deduced argument.
1595       for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
1596         DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
1597         if (!DeducedArg.isNull()) {
1598           NewlyDeducedPacks[I].push_back(DeducedArg);
1599           DeducedArg = DeducedTemplateArgument();
1600         }
1601       }
1602
1603       ++ArgIdx;
1604     }
1605
1606     // Build argument packs for each of the parameter packs expanded by this
1607     // pack expansion.
1608     if (Sema::TemplateDeductionResult Result
1609           = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments,
1610                                         Deduced, PackIndices, SavedPacks,
1611                                         NewlyDeducedPacks, Info))
1612       return Result;
1613   }
1614
1615   // If there is an argument remaining, then we had too many arguments.
1616   if (NumberOfArgumentsMustMatch &&
1617       hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
1618     return Sema::TDK_NonDeducedMismatch;
1619
1620   return Sema::TDK_Success;
1621 }
1622
1623 static Sema::TemplateDeductionResult
1624 DeduceTemplateArguments(Sema &S,
1625                         TemplateParameterList *TemplateParams,
1626                         const TemplateArgumentList &ParamList,
1627                         const TemplateArgumentList &ArgList,
1628                         TemplateDeductionInfo &Info,
1629                     llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1630   return DeduceTemplateArguments(S, TemplateParams,
1631                                  ParamList.data(), ParamList.size(),
1632                                  ArgList.data(), ArgList.size(),
1633                                  Info, Deduced);
1634 }
1635
1636 /// \brief Determine whether two template arguments are the same.
1637 static bool isSameTemplateArg(ASTContext &Context,
1638                               const TemplateArgument &X,
1639                               const TemplateArgument &Y) {
1640   if (X.getKind() != Y.getKind())
1641     return false;
1642
1643   switch (X.getKind()) {
1644     case TemplateArgument::Null:
1645       assert(false && "Comparing NULL template argument");
1646       break;
1647
1648     case TemplateArgument::Type:
1649       return Context.getCanonicalType(X.getAsType()) ==
1650              Context.getCanonicalType(Y.getAsType());
1651
1652     case TemplateArgument::Declaration:
1653       return X.getAsDecl()->getCanonicalDecl() ==
1654              Y.getAsDecl()->getCanonicalDecl();
1655
1656     case TemplateArgument::Template:
1657     case TemplateArgument::TemplateExpansion:
1658       return Context.getCanonicalTemplateName(
1659                     X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
1660              Context.getCanonicalTemplateName(
1661                     Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
1662
1663     case TemplateArgument::Integral:
1664       return *X.getAsIntegral() == *Y.getAsIntegral();
1665
1666     case TemplateArgument::Expression: {
1667       llvm::FoldingSetNodeID XID, YID;
1668       X.getAsExpr()->Profile(XID, Context, true);
1669       Y.getAsExpr()->Profile(YID, Context, true);
1670       return XID == YID;
1671     }
1672
1673     case TemplateArgument::Pack:
1674       if (X.pack_size() != Y.pack_size())
1675         return false;
1676
1677       for (TemplateArgument::pack_iterator XP = X.pack_begin(),
1678                                         XPEnd = X.pack_end(),
1679                                            YP = Y.pack_begin();
1680            XP != XPEnd; ++XP, ++YP)
1681         if (!isSameTemplateArg(Context, *XP, *YP))
1682           return false;
1683
1684       return true;
1685   }
1686
1687   return false;
1688 }
1689
1690 /// \brief Allocate a TemplateArgumentLoc where all locations have
1691 /// been initialized to the given location.
1692 ///
1693 /// \param S The semantic analysis object.
1694 ///
1695 /// \param The template argument we are producing template argument
1696 /// location information for.
1697 ///
1698 /// \param NTTPType For a declaration template argument, the type of
1699 /// the non-type template parameter that corresponds to this template
1700 /// argument.
1701 ///
1702 /// \param Loc The source location to use for the resulting template
1703 /// argument.
1704 static TemplateArgumentLoc
1705 getTrivialTemplateArgumentLoc(Sema &S,
1706                               const TemplateArgument &Arg,
1707                               QualType NTTPType,
1708                               SourceLocation Loc) {
1709   switch (Arg.getKind()) {
1710   case TemplateArgument::Null:
1711     llvm_unreachable("Can't get a NULL template argument here");
1712     break;
1713
1714   case TemplateArgument::Type:
1715     return TemplateArgumentLoc(Arg,
1716                      S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
1717
1718   case TemplateArgument::Declaration: {
1719     Expr *E
1720       = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
1721     .takeAs<Expr>();
1722     return TemplateArgumentLoc(TemplateArgument(E), E);
1723   }
1724
1725   case TemplateArgument::Integral: {
1726     Expr *E
1727       = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).takeAs<Expr>();
1728     return TemplateArgumentLoc(TemplateArgument(E), E);
1729   }
1730
1731   case TemplateArgument::Template:
1732     return TemplateArgumentLoc(Arg, SourceRange(), Loc);
1733
1734   case TemplateArgument::TemplateExpansion:
1735     return TemplateArgumentLoc(Arg, SourceRange(), Loc, Loc);
1736
1737   case TemplateArgument::Expression:
1738     return TemplateArgumentLoc(Arg, Arg.getAsExpr());
1739
1740   case TemplateArgument::Pack:
1741     return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
1742   }
1743
1744   return TemplateArgumentLoc();
1745 }
1746
1747
1748 /// \brief Convert the given deduced template argument and add it to the set of
1749 /// fully-converted template arguments.
1750 static bool ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
1751                                            DeducedTemplateArgument Arg,
1752                                            NamedDecl *Template,
1753                                            QualType NTTPType,
1754                                            unsigned ArgumentPackIndex,
1755                                            TemplateDeductionInfo &Info,
1756                                            bool InFunctionTemplate,
1757                              llvm::SmallVectorImpl<TemplateArgument> &Output) {
1758   if (Arg.getKind() == TemplateArgument::Pack) {
1759     // This is a template argument pack, so check each of its arguments against
1760     // the template parameter.
1761     llvm::SmallVector<TemplateArgument, 2> PackedArgsBuilder;
1762     for (TemplateArgument::pack_iterator PA = Arg.pack_begin(),
1763                                       PAEnd = Arg.pack_end();
1764          PA != PAEnd; ++PA) {
1765       // When converting the deduced template argument, append it to the
1766       // general output list. We need to do this so that the template argument
1767       // checking logic has all of the prior template arguments available.
1768       DeducedTemplateArgument InnerArg(*PA);
1769       InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
1770       if (ConvertDeducedTemplateArgument(S, Param, InnerArg, Template,
1771                                          NTTPType, PackedArgsBuilder.size(),
1772                                          Info, InFunctionTemplate, Output))
1773         return true;
1774
1775       // Move the converted template argument into our argument pack.
1776       PackedArgsBuilder.push_back(Output.back());
1777       Output.pop_back();
1778     }
1779
1780     // Create the resulting argument pack.
1781     Output.push_back(TemplateArgument::CreatePackCopy(S.Context,
1782                                                       PackedArgsBuilder.data(),
1783                                                      PackedArgsBuilder.size()));
1784     return false;
1785   }
1786
1787   // Convert the deduced template argument into a template
1788   // argument that we can check, almost as if the user had written
1789   // the template argument explicitly.
1790   TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType,
1791                                                              Info.getLocation());
1792
1793   // Check the template argument, converting it as necessary.
1794   return S.CheckTemplateArgument(Param, ArgLoc,
1795                                  Template,
1796                                  Template->getLocation(),
1797                                  Template->getSourceRange().getEnd(),
1798                                  ArgumentPackIndex,
1799                                  Output,
1800                                  InFunctionTemplate
1801                                   ? (Arg.wasDeducedFromArrayBound()
1802                                        ? Sema::CTAK_DeducedFromArrayBound
1803                                        : Sema::CTAK_Deduced)
1804                                  : Sema::CTAK_Specified);
1805 }
1806
1807 /// Complete template argument deduction for a class template partial
1808 /// specialization.
1809 static Sema::TemplateDeductionResult
1810 FinishTemplateArgumentDeduction(Sema &S,
1811                                 ClassTemplatePartialSpecializationDecl *Partial,
1812                                 const TemplateArgumentList &TemplateArgs,
1813                       llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
1814                                 TemplateDeductionInfo &Info) {
1815   // Trap errors.
1816   Sema::SFINAETrap Trap(S);
1817
1818   Sema::ContextRAII SavedContext(S, Partial);
1819
1820   // C++ [temp.deduct.type]p2:
1821   //   [...] or if any template argument remains neither deduced nor
1822   //   explicitly specified, template argument deduction fails.
1823   llvm::SmallVector<TemplateArgument, 4> Builder;
1824   TemplateParameterList *PartialParams = Partial->getTemplateParameters();
1825   for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
1826     NamedDecl *Param = PartialParams->getParam(I);
1827     if (Deduced[I].isNull()) {
1828       Info.Param = makeTemplateParameter(Param);
1829       return Sema::TDK_Incomplete;
1830     }
1831
1832     // We have deduced this argument, so it still needs to be
1833     // checked and converted.
1834
1835     // First, for a non-type template parameter type that is
1836     // initialized by a declaration, we need the type of the
1837     // corresponding non-type template parameter.
1838     QualType NTTPType;
1839     if (NonTypeTemplateParmDecl *NTTP
1840                                   = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
1841       NTTPType = NTTP->getType();
1842       if (NTTPType->isDependentType()) {
1843         TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
1844                                           Builder.data(), Builder.size());
1845         NTTPType = S.SubstType(NTTPType,
1846                                MultiLevelTemplateArgumentList(TemplateArgs),
1847                                NTTP->getLocation(),
1848                                NTTP->getDeclName());
1849         if (NTTPType.isNull()) {
1850           Info.Param = makeTemplateParameter(Param);
1851           // FIXME: These template arguments are temporary. Free them!
1852           Info.reset(TemplateArgumentList::CreateCopy(S.Context,
1853                                                       Builder.data(),
1854                                                       Builder.size()));
1855           return Sema::TDK_SubstitutionFailure;
1856         }
1857       }
1858     }
1859
1860     if (ConvertDeducedTemplateArgument(S, Param, Deduced[I],
1861                                        Partial, NTTPType, 0, Info, false,
1862                                        Builder)) {
1863       Info.Param = makeTemplateParameter(Param);
1864       // FIXME: These template arguments are temporary. Free them!
1865       Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
1866                                                   Builder.size()));
1867       return Sema::TDK_SubstitutionFailure;
1868     }
1869   }
1870
1871   // Form the template argument list from the deduced template arguments.
1872   TemplateArgumentList *DeducedArgumentList
1873     = TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
1874                                        Builder.size());
1875
1876   Info.reset(DeducedArgumentList);
1877
1878   // Substitute the deduced template arguments into the template
1879   // arguments of the class template partial specialization, and
1880   // verify that the instantiated template arguments are both valid
1881   // and are equivalent to the template arguments originally provided
1882   // to the class template.
1883   LocalInstantiationScope InstScope(S);
1884   ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
1885   const TemplateArgumentLoc *PartialTemplateArgs
1886     = Partial->getTemplateArgsAsWritten();
1887
1888   // Note that we don't provide the langle and rangle locations.
1889   TemplateArgumentListInfo InstArgs;
1890
1891   if (S.Subst(PartialTemplateArgs,
1892               Partial->getNumTemplateArgsAsWritten(),
1893               InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
1894     unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
1895     if (ParamIdx >= Partial->getTemplateParameters()->size())
1896       ParamIdx = Partial->getTemplateParameters()->size() - 1;
1897
1898     Decl *Param
1899       = const_cast<NamedDecl *>(
1900                           Partial->getTemplateParameters()->getParam(ParamIdx));
1901     Info.Param = makeTemplateParameter(Param);
1902     Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
1903     return Sema::TDK_SubstitutionFailure;
1904   }
1905
1906   llvm::SmallVector<TemplateArgument, 4> ConvertedInstArgs;
1907   if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(),
1908                                   InstArgs, false, ConvertedInstArgs))
1909     return Sema::TDK_SubstitutionFailure;
1910
1911   TemplateParameterList *TemplateParams
1912     = ClassTemplate->getTemplateParameters();
1913   for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
1914     TemplateArgument InstArg = ConvertedInstArgs.data()[I];
1915     if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
1916       Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
1917       Info.FirstArg = TemplateArgs[I];
1918       Info.SecondArg = InstArg;
1919       return Sema::TDK_NonDeducedMismatch;
1920     }
1921   }
1922
1923   if (Trap.hasErrorOccurred())
1924     return Sema::TDK_SubstitutionFailure;
1925
1926   return Sema::TDK_Success;
1927 }
1928
1929 /// \brief Perform template argument deduction to determine whether
1930 /// the given template arguments match the given class template
1931 /// partial specialization per C++ [temp.class.spec.match].
1932 Sema::TemplateDeductionResult
1933 Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
1934                               const TemplateArgumentList &TemplateArgs,
1935                               TemplateDeductionInfo &Info) {
1936   // C++ [temp.class.spec.match]p2:
1937   //   A partial specialization matches a given actual template
1938   //   argument list if the template arguments of the partial
1939   //   specialization can be deduced from the actual template argument
1940   //   list (14.8.2).
1941   SFINAETrap Trap(*this);
1942   llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
1943   Deduced.resize(Partial->getTemplateParameters()->size());
1944   if (TemplateDeductionResult Result
1945         = ::DeduceTemplateArguments(*this,
1946                                     Partial->getTemplateParameters(),
1947                                     Partial->getTemplateArgs(),
1948                                     TemplateArgs, Info, Deduced))
1949     return Result;
1950
1951   InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial,
1952                              Deduced.data(), Deduced.size(), Info);
1953   if (Inst)
1954     return TDK_InstantiationDepth;
1955
1956   if (Trap.hasErrorOccurred())
1957     return Sema::TDK_SubstitutionFailure;
1958
1959   return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
1960                                            Deduced, Info);
1961 }
1962
1963 /// \brief Determine whether the given type T is a simple-template-id type.
1964 static bool isSimpleTemplateIdType(QualType T) {
1965   if (const TemplateSpecializationType *Spec
1966         = T->getAs<TemplateSpecializationType>())
1967     return Spec->getTemplateName().getAsTemplateDecl() != 0;
1968
1969   return false;
1970 }
1971
1972 /// \brief Substitute the explicitly-provided template arguments into the
1973 /// given function template according to C++ [temp.arg.explicit].
1974 ///
1975 /// \param FunctionTemplate the function template into which the explicit
1976 /// template arguments will be substituted.
1977 ///
1978 /// \param ExplicitTemplateArguments the explicitly-specified template
1979 /// arguments.
1980 ///
1981 /// \param Deduced the deduced template arguments, which will be populated
1982 /// with the converted and checked explicit template arguments.
1983 ///
1984 /// \param ParamTypes will be populated with the instantiated function
1985 /// parameters.
1986 ///
1987 /// \param FunctionType if non-NULL, the result type of the function template
1988 /// will also be instantiated and the pointed-to value will be updated with
1989 /// the instantiated function type.
1990 ///
1991 /// \param Info if substitution fails for any reason, this object will be
1992 /// populated with more information about the failure.
1993 ///
1994 /// \returns TDK_Success if substitution was successful, or some failure
1995 /// condition.
1996 Sema::TemplateDeductionResult
1997 Sema::SubstituteExplicitTemplateArguments(
1998                                       FunctionTemplateDecl *FunctionTemplate,
1999                         const TemplateArgumentListInfo &ExplicitTemplateArgs,
2000                        llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2001                                  llvm::SmallVectorImpl<QualType> &ParamTypes,
2002                                           QualType *FunctionType,
2003                                           TemplateDeductionInfo &Info) {
2004   FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2005   TemplateParameterList *TemplateParams
2006     = FunctionTemplate->getTemplateParameters();
2007
2008   if (ExplicitTemplateArgs.size() == 0) {
2009     // No arguments to substitute; just copy over the parameter types and
2010     // fill in the function type.
2011     for (FunctionDecl::param_iterator P = Function->param_begin(),
2012                                    PEnd = Function->param_end();
2013          P != PEnd;
2014          ++P)
2015       ParamTypes.push_back((*P)->getType());
2016
2017     if (FunctionType)
2018       *FunctionType = Function->getType();
2019     return TDK_Success;
2020   }
2021
2022   // Substitution of the explicit template arguments into a function template
2023   /// is a SFINAE context. Trap any errors that might occur.
2024   SFINAETrap Trap(*this);
2025
2026   // C++ [temp.arg.explicit]p3:
2027   //   Template arguments that are present shall be specified in the
2028   //   declaration order of their corresponding template-parameters. The
2029   //   template argument list shall not specify more template-arguments than
2030   //   there are corresponding template-parameters.
2031   llvm::SmallVector<TemplateArgument, 4> Builder;
2032
2033   // Enter a new template instantiation context where we check the
2034   // explicitly-specified template arguments against this function template,
2035   // and then substitute them into the function parameter types.
2036   InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
2037                              FunctionTemplate, Deduced.data(), Deduced.size(),
2038            ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution,
2039                              Info);
2040   if (Inst)
2041     return TDK_InstantiationDepth;
2042
2043   if (CheckTemplateArgumentList(FunctionTemplate,
2044                                 SourceLocation(),
2045                                 ExplicitTemplateArgs,
2046                                 true,
2047                                 Builder) || Trap.hasErrorOccurred()) {
2048     unsigned Index = Builder.size();
2049     if (Index >= TemplateParams->size())
2050       Index = TemplateParams->size() - 1;
2051     Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
2052     return TDK_InvalidExplicitArguments;
2053   }
2054
2055   // Form the template argument list from the explicitly-specified
2056   // template arguments.
2057   TemplateArgumentList *ExplicitArgumentList
2058     = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2059   Info.reset(ExplicitArgumentList);
2060
2061   // Template argument deduction and the final substitution should be
2062   // done in the context of the templated declaration.  Explicit
2063   // argument substitution, on the other hand, needs to happen in the
2064   // calling context.
2065   ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2066
2067   // If we deduced template arguments for a template parameter pack,
2068   // note that the template argument pack is partially substituted and record
2069   // the explicit template arguments. They'll be used as part of deduction
2070   // for this template parameter pack.
2071   for (unsigned I = 0, N = Builder.size(); I != N; ++I) {
2072     const TemplateArgument &Arg = Builder[I];
2073     if (Arg.getKind() == TemplateArgument::Pack) {
2074       CurrentInstantiationScope->SetPartiallySubstitutedPack(
2075                                                  TemplateParams->getParam(I),
2076                                                              Arg.pack_begin(),
2077                                                              Arg.pack_size());
2078       break;
2079     }
2080   }
2081
2082   // Instantiate the types of each of the function parameters given the
2083   // explicitly-specified template arguments.
2084   if (SubstParmTypes(Function->getLocation(),
2085                      Function->param_begin(), Function->getNumParams(),
2086                      MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2087                      ParamTypes))
2088     return TDK_SubstitutionFailure;
2089
2090   // If the caller wants a full function type back, instantiate the return
2091   // type and form that function type.
2092   if (FunctionType) {
2093     // FIXME: exception-specifications?
2094     const FunctionProtoType *Proto
2095       = Function->getType()->getAs<FunctionProtoType>();
2096     assert(Proto && "Function template does not have a prototype?");
2097
2098     QualType ResultType
2099       = SubstType(Proto->getResultType(),
2100                   MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2101                   Function->getTypeSpecStartLoc(),
2102                   Function->getDeclName());
2103     if (ResultType.isNull() || Trap.hasErrorOccurred())
2104       return TDK_SubstitutionFailure;
2105
2106     *FunctionType = BuildFunctionType(ResultType,
2107                                       ParamTypes.data(), ParamTypes.size(),
2108                                       Proto->isVariadic(),
2109                                       Proto->getTypeQuals(),
2110                                       Proto->getRefQualifier(),
2111                                       Function->getLocation(),
2112                                       Function->getDeclName(),
2113                                       Proto->getExtInfo());
2114     if (FunctionType->isNull() || Trap.hasErrorOccurred())
2115       return TDK_SubstitutionFailure;
2116   }
2117
2118   // C++ [temp.arg.explicit]p2:
2119   //   Trailing template arguments that can be deduced (14.8.2) may be
2120   //   omitted from the list of explicit template-arguments. If all of the
2121   //   template arguments can be deduced, they may all be omitted; in this
2122   //   case, the empty template argument list <> itself may also be omitted.
2123   //
2124   // Take all of the explicitly-specified arguments and put them into
2125   // the set of deduced template arguments. Explicitly-specified
2126   // parameter packs, however, will be set to NULL since the deduction
2127   // mechanisms handle explicitly-specified argument packs directly.
2128   Deduced.reserve(TemplateParams->size());
2129   for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) {
2130     const TemplateArgument &Arg = ExplicitArgumentList->get(I);
2131     if (Arg.getKind() == TemplateArgument::Pack)
2132       Deduced.push_back(DeducedTemplateArgument());
2133     else
2134       Deduced.push_back(Arg);
2135   }
2136
2137   return TDK_Success;
2138 }
2139
2140 /// \brief Finish template argument deduction for a function template,
2141 /// checking the deduced template arguments for completeness and forming
2142 /// the function template specialization.
2143 Sema::TemplateDeductionResult
2144 Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate,
2145                        llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2146                                       unsigned NumExplicitlySpecified,
2147                                       FunctionDecl *&Specialization,
2148                                       TemplateDeductionInfo &Info) {
2149   TemplateParameterList *TemplateParams
2150     = FunctionTemplate->getTemplateParameters();
2151
2152   // Template argument deduction for function templates in a SFINAE context.
2153   // Trap any errors that might occur.
2154   SFINAETrap Trap(*this);
2155
2156   // Enter a new template instantiation context while we instantiate the
2157   // actual function declaration.
2158   InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
2159                              FunctionTemplate, Deduced.data(), Deduced.size(),
2160               ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution,
2161                              Info);
2162   if (Inst)
2163     return TDK_InstantiationDepth;
2164
2165   ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2166
2167   // C++ [temp.deduct.type]p2:
2168   //   [...] or if any template argument remains neither deduced nor
2169   //   explicitly specified, template argument deduction fails.
2170   llvm::SmallVector<TemplateArgument, 4> Builder;
2171   for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2172     NamedDecl *Param = TemplateParams->getParam(I);
2173
2174     if (!Deduced[I].isNull()) {
2175       if (I < NumExplicitlySpecified) {
2176         // We have already fully type-checked and converted this
2177         // argument, because it was explicitly-specified. Just record the
2178         // presence of this argument.
2179         Builder.push_back(Deduced[I]);
2180         continue;
2181       }
2182
2183       // We have deduced this argument, so it still needs to be
2184       // checked and converted.
2185
2186       // First, for a non-type template parameter type that is
2187       // initialized by a declaration, we need the type of the
2188       // corresponding non-type template parameter.
2189       QualType NTTPType;
2190       if (NonTypeTemplateParmDecl *NTTP
2191                                 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2192         NTTPType = NTTP->getType();
2193         if (NTTPType->isDependentType()) {
2194           TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2195                                             Builder.data(), Builder.size());
2196           NTTPType = SubstType(NTTPType,
2197                                MultiLevelTemplateArgumentList(TemplateArgs),
2198                                NTTP->getLocation(),
2199                                NTTP->getDeclName());
2200           if (NTTPType.isNull()) {
2201             Info.Param = makeTemplateParameter(Param);
2202             // FIXME: These template arguments are temporary. Free them!
2203             Info.reset(TemplateArgumentList::CreateCopy(Context,
2204                                                         Builder.data(),
2205                                                         Builder.size()));
2206             return TDK_SubstitutionFailure;
2207           }
2208         }
2209       }
2210
2211       if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I],
2212                                          FunctionTemplate, NTTPType, 0, Info,
2213                                          true, Builder)) {
2214         Info.Param = makeTemplateParameter(Param);
2215         // FIXME: These template arguments are temporary. Free them!
2216         Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2217                                                     Builder.size()));
2218         return TDK_SubstitutionFailure;
2219       }
2220
2221       continue;
2222     }
2223
2224     // C++0x [temp.arg.explicit]p3:
2225     //    A trailing template parameter pack (14.5.3) not otherwise deduced will
2226     //    be deduced to an empty sequence of template arguments.
2227     // FIXME: Where did the word "trailing" come from?
2228     if (Param->isTemplateParameterPack()) {
2229       // We may have had explicitly-specified template arguments for this
2230       // template parameter pack. If so, our empty deduction extends the
2231       // explicitly-specified set (C++0x [temp.arg.explicit]p9).
2232       const TemplateArgument *ExplicitArgs;
2233       unsigned NumExplicitArgs;
2234       if (CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs,
2235                                                              &NumExplicitArgs)
2236           == Param)
2237         Builder.push_back(TemplateArgument(ExplicitArgs, NumExplicitArgs));
2238       else
2239         Builder.push_back(TemplateArgument(0, 0));
2240
2241       continue;
2242     }
2243
2244     // Substitute into the default template argument, if available.
2245     TemplateArgumentLoc DefArg
2246       = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate,
2247                                               FunctionTemplate->getLocation(),
2248                                   FunctionTemplate->getSourceRange().getEnd(),
2249                                                 Param,
2250                                                 Builder);
2251
2252     // If there was no default argument, deduction is incomplete.
2253     if (DefArg.getArgument().isNull()) {
2254       Info.Param = makeTemplateParameter(
2255                          const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2256       return TDK_Incomplete;
2257     }
2258
2259     // Check whether we can actually use the default argument.
2260     if (CheckTemplateArgument(Param, DefArg,
2261                               FunctionTemplate,
2262                               FunctionTemplate->getLocation(),
2263                               FunctionTemplate->getSourceRange().getEnd(),
2264                               0, Builder,
2265                               CTAK_Deduced)) {
2266       Info.Param = makeTemplateParameter(
2267                          const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2268       // FIXME: These template arguments are temporary. Free them!
2269       Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2270                                                   Builder.size()));
2271       return TDK_SubstitutionFailure;
2272     }
2273
2274     // If we get here, we successfully used the default template argument.
2275   }
2276
2277   // Form the template argument list from the deduced template arguments.
2278   TemplateArgumentList *DeducedArgumentList
2279     = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2280   Info.reset(DeducedArgumentList);
2281
2282   // Substitute the deduced template arguments into the function template
2283   // declaration to produce the function template specialization.
2284   DeclContext *Owner = FunctionTemplate->getDeclContext();
2285   if (FunctionTemplate->getFriendObjectKind())
2286     Owner = FunctionTemplate->getLexicalDeclContext();
2287   Specialization = cast_or_null<FunctionDecl>(
2288                       SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner,
2289                          MultiLevelTemplateArgumentList(*DeducedArgumentList)));
2290   if (!Specialization)
2291     return TDK_SubstitutionFailure;
2292
2293   assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
2294          FunctionTemplate->getCanonicalDecl());
2295
2296   // If the template argument list is owned by the function template
2297   // specialization, release it.
2298   if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
2299       !Trap.hasErrorOccurred())
2300     Info.take();
2301
2302   // There may have been an error that did not prevent us from constructing a
2303   // declaration. Mark the declaration invalid and return with a substitution
2304   // failure.
2305   if (Trap.hasErrorOccurred()) {
2306     Specialization->setInvalidDecl(true);
2307     return TDK_SubstitutionFailure;
2308   }
2309
2310   // If we suppressed any diagnostics while performing template argument
2311   // deduction, and if we haven't already instantiated this declaration,
2312   // keep track of these diagnostics. They'll be emitted if this specialization
2313   // is actually used.
2314   if (Info.diag_begin() != Info.diag_end()) {
2315     llvm::DenseMap<Decl *, llvm::SmallVector<PartialDiagnosticAt, 1> >::iterator
2316       Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
2317     if (Pos == SuppressedDiagnostics.end())
2318         SuppressedDiagnostics[Specialization->getCanonicalDecl()]
2319           .append(Info.diag_begin(), Info.diag_end());
2320   }
2321
2322   return TDK_Success;
2323 }
2324
2325 /// Gets the type of a function for template-argument-deducton
2326 /// purposes when it's considered as part of an overload set.
2327 static QualType GetTypeOfFunction(ASTContext &Context,
2328                                   const OverloadExpr::FindResult &R,
2329                                   FunctionDecl *Fn) {
2330   if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
2331     if (Method->isInstance()) {
2332       // An instance method that's referenced in a form that doesn't
2333       // look like a member pointer is just invalid.
2334       if (!R.HasFormOfMemberPointer) return QualType();
2335
2336       return Context.getMemberPointerType(Fn->getType(),
2337                Context.getTypeDeclType(Method->getParent()).getTypePtr());
2338     }
2339
2340   if (!R.IsAddressOfOperand) return Fn->getType();
2341   return Context.getPointerType(Fn->getType());
2342 }
2343
2344 /// Apply the deduction rules for overload sets.
2345 ///
2346 /// \return the null type if this argument should be treated as an
2347 /// undeduced context
2348 static QualType
2349 ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
2350                             Expr *Arg, QualType ParamType,
2351                             bool ParamWasReference) {
2352
2353   OverloadExpr::FindResult R = OverloadExpr::find(Arg);
2354
2355   OverloadExpr *Ovl = R.Expression;
2356
2357   // C++0x [temp.deduct.call]p4
2358   unsigned TDF = 0;
2359   if (ParamWasReference)
2360     TDF |= TDF_ParamWithReferenceType;
2361   if (R.IsAddressOfOperand)
2362     TDF |= TDF_IgnoreQualifiers;
2363
2364   // If there were explicit template arguments, we can only find
2365   // something via C++ [temp.arg.explicit]p3, i.e. if the arguments
2366   // unambiguously name a full specialization.
2367   if (Ovl->hasExplicitTemplateArgs()) {
2368     // But we can still look for an explicit specialization.
2369     if (FunctionDecl *ExplicitSpec
2370           = S.ResolveSingleFunctionTemplateSpecialization(Ovl))
2371       return GetTypeOfFunction(S.Context, R, ExplicitSpec);
2372     return QualType();
2373   }
2374
2375   // C++0x [temp.deduct.call]p6:
2376   //   When P is a function type, pointer to function type, or pointer
2377   //   to member function type:
2378
2379   if (!ParamType->isFunctionType() &&
2380       !ParamType->isFunctionPointerType() &&
2381       !ParamType->isMemberFunctionPointerType())
2382     return QualType();
2383
2384   QualType Match;
2385   for (UnresolvedSetIterator I = Ovl->decls_begin(),
2386          E = Ovl->decls_end(); I != E; ++I) {
2387     NamedDecl *D = (*I)->getUnderlyingDecl();
2388
2389     //   - If the argument is an overload set containing one or more
2390     //     function templates, the parameter is treated as a
2391     //     non-deduced context.
2392     if (isa<FunctionTemplateDecl>(D))
2393       return QualType();
2394
2395     FunctionDecl *Fn = cast<FunctionDecl>(D);
2396     QualType ArgType = GetTypeOfFunction(S.Context, R, Fn);
2397     if (ArgType.isNull()) continue;
2398
2399     // Function-to-pointer conversion.
2400     if (!ParamWasReference && ParamType->isPointerType() &&
2401         ArgType->isFunctionType())
2402       ArgType = S.Context.getPointerType(ArgType);
2403
2404     //   - If the argument is an overload set (not containing function
2405     //     templates), trial argument deduction is attempted using each
2406     //     of the members of the set. If deduction succeeds for only one
2407     //     of the overload set members, that member is used as the
2408     //     argument value for the deduction. If deduction succeeds for
2409     //     more than one member of the overload set the parameter is
2410     //     treated as a non-deduced context.
2411
2412     // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
2413     //   Type deduction is done independently for each P/A pair, and
2414     //   the deduced template argument values are then combined.
2415     // So we do not reject deductions which were made elsewhere.
2416     llvm::SmallVector<DeducedTemplateArgument, 8>
2417       Deduced(TemplateParams->size());
2418     TemplateDeductionInfo Info(S.Context, Ovl->getNameLoc());
2419     Sema::TemplateDeductionResult Result
2420       = DeduceTemplateArguments(S, TemplateParams,
2421                                 ParamType, ArgType,
2422                                 Info, Deduced, TDF);
2423     if (Result) continue;
2424     if (!Match.isNull()) return QualType();
2425     Match = ArgType;
2426   }
2427
2428   return Match;
2429 }
2430
2431 /// \brief Perform the adjustments to the parameter and argument types
2432 /// described in C++ [temp.deduct.call].
2433 ///
2434 /// \returns true if the caller should not attempt to perform any template
2435 /// argument deduction based on this P/A pair.
2436 static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
2437                                           TemplateParameterList *TemplateParams,
2438                                                       QualType &ParamType,
2439                                                       QualType &ArgType,
2440                                                       Expr *Arg,
2441                                                       unsigned &TDF) {
2442   // C++0x [temp.deduct.call]p3:
2443   //   If P is a cv-qualified type, the top level cv-qualifiers of P's type
2444   //   are ignored for type deduction.
2445   if (ParamType.getCVRQualifiers())
2446     ParamType = ParamType.getLocalUnqualifiedType();
2447   const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
2448   if (ParamRefType) {
2449     QualType PointeeType = ParamRefType->getPointeeType();
2450
2451     //   [C++0x] If P is an rvalue reference to a cv-unqualified
2452     //   template parameter and the argument is an lvalue, the type
2453     //   "lvalue reference to A" is used in place of A for type
2454     //   deduction.
2455     if (isa<RValueReferenceType>(ParamType)) {
2456       if (!PointeeType.getQualifiers() &&
2457           isa<TemplateTypeParmType>(PointeeType) &&
2458           Arg->Classify(S.Context).isLValue())
2459         ArgType = S.Context.getLValueReferenceType(ArgType);
2460     }
2461
2462     //   [...] If P is a reference type, the type referred to by P is used
2463     //   for type deduction.
2464     ParamType = PointeeType;
2465   }
2466
2467   // Overload sets usually make this parameter an undeduced
2468   // context, but there are sometimes special circumstances.
2469   if (ArgType == S.Context.OverloadTy) {
2470     ArgType = ResolveOverloadForDeduction(S, TemplateParams,
2471                                           Arg, ParamType,
2472                                           ParamRefType != 0);
2473     if (ArgType.isNull())
2474       return true;
2475   }
2476
2477   if (ParamRefType) {
2478     // C++0x [temp.deduct.call]p3:
2479     //   [...] If P is of the form T&&, where T is a template parameter, and
2480     //   the argument is an lvalue, the type A& is used in place of A for
2481     //   type deduction.
2482     if (ParamRefType->isRValueReferenceType() &&
2483         ParamRefType->getAs<TemplateTypeParmType>() &&
2484         Arg->isLValue())
2485       ArgType = S.Context.getLValueReferenceType(ArgType);
2486   } else {
2487     // C++ [temp.deduct.call]p2:
2488     //   If P is not a reference type:
2489     //   - If A is an array type, the pointer type produced by the
2490     //     array-to-pointer standard conversion (4.2) is used in place of
2491     //     A for type deduction; otherwise,
2492     if (ArgType->isArrayType())
2493       ArgType = S.Context.getArrayDecayedType(ArgType);
2494     //   - If A is a function type, the pointer type produced by the
2495     //     function-to-pointer standard conversion (4.3) is used in place
2496     //     of A for type deduction; otherwise,
2497     else if (ArgType->isFunctionType())
2498       ArgType = S.Context.getPointerType(ArgType);
2499     else {
2500       // - If A is a cv-qualified type, the top level cv-qualifiers of A's
2501       //   type are ignored for type deduction.
2502       if (ArgType.getCVRQualifiers())
2503         ArgType = ArgType.getUnqualifiedType();
2504     }
2505   }
2506
2507   // C++0x [temp.deduct.call]p4:
2508   //   In general, the deduction process attempts to find template argument
2509   //   values that will make the deduced A identical to A (after the type A
2510   //   is transformed as described above). [...]
2511   TDF = TDF_SkipNonDependent;
2512
2513   //     - If the original P is a reference type, the deduced A (i.e., the
2514   //       type referred to by the reference) can be more cv-qualified than
2515   //       the transformed A.
2516   if (ParamRefType)
2517     TDF |= TDF_ParamWithReferenceType;
2518   //     - The transformed A can be another pointer or pointer to member
2519   //       type that can be converted to the deduced A via a qualification
2520   //       conversion (4.4).
2521   if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
2522       ArgType->isObjCObjectPointerType())
2523     TDF |= TDF_IgnoreQualifiers;
2524   //     - If P is a class and P has the form simple-template-id, then the
2525   //       transformed A can be a derived class of the deduced A. Likewise,
2526   //       if P is a pointer to a class of the form simple-template-id, the
2527   //       transformed A can be a pointer to a derived class pointed to by
2528   //       the deduced A.
2529   if (isSimpleTemplateIdType(ParamType) ||
2530       (isa<PointerType>(ParamType) &&
2531        isSimpleTemplateIdType(
2532                               ParamType->getAs<PointerType>()->getPointeeType())))
2533     TDF |= TDF_DerivedClass;
2534
2535   return false;
2536 }
2537
2538 /// \brief Perform template argument deduction from a function call
2539 /// (C++ [temp.deduct.call]).
2540 ///
2541 /// \param FunctionTemplate the function template for which we are performing
2542 /// template argument deduction.
2543 ///
2544 /// \param ExplicitTemplateArguments the explicit template arguments provided
2545 /// for this call.
2546 ///
2547 /// \param Args the function call arguments
2548 ///
2549 /// \param NumArgs the number of arguments in Args
2550 ///
2551 /// \param Name the name of the function being called. This is only significant
2552 /// when the function template is a conversion function template, in which
2553 /// case this routine will also perform template argument deduction based on
2554 /// the function to which
2555 ///
2556 /// \param Specialization if template argument deduction was successful,
2557 /// this will be set to the function template specialization produced by
2558 /// template argument deduction.
2559 ///
2560 /// \param Info the argument will be updated to provide additional information
2561 /// about template argument deduction.
2562 ///
2563 /// \returns the result of template argument deduction.
2564 Sema::TemplateDeductionResult
2565 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
2566                           const TemplateArgumentListInfo *ExplicitTemplateArgs,
2567                               Expr **Args, unsigned NumArgs,
2568                               FunctionDecl *&Specialization,
2569                               TemplateDeductionInfo &Info) {
2570   FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2571
2572   // C++ [temp.deduct.call]p1:
2573   //   Template argument deduction is done by comparing each function template
2574   //   parameter type (call it P) with the type of the corresponding argument
2575   //   of the call (call it A) as described below.
2576   unsigned CheckArgs = NumArgs;
2577   if (NumArgs < Function->getMinRequiredArguments())
2578     return TDK_TooFewArguments;
2579   else if (NumArgs > Function->getNumParams()) {
2580     const FunctionProtoType *Proto
2581       = Function->getType()->getAs<FunctionProtoType>();
2582     if (Proto->isTemplateVariadic())
2583       /* Do nothing */;
2584     else if (Proto->isVariadic())
2585       CheckArgs = Function->getNumParams();
2586     else
2587       return TDK_TooManyArguments;
2588   }
2589
2590   // The types of the parameters from which we will perform template argument
2591   // deduction.
2592   LocalInstantiationScope InstScope(*this);
2593   TemplateParameterList *TemplateParams
2594     = FunctionTemplate->getTemplateParameters();
2595   llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
2596   llvm::SmallVector<QualType, 4> ParamTypes;
2597   unsigned NumExplicitlySpecified = 0;
2598   if (ExplicitTemplateArgs) {
2599     TemplateDeductionResult Result =
2600       SubstituteExplicitTemplateArguments(FunctionTemplate,
2601                                           *ExplicitTemplateArgs,
2602                                           Deduced,
2603                                           ParamTypes,
2604                                           0,
2605                                           Info);
2606     if (Result)
2607       return Result;
2608
2609     NumExplicitlySpecified = Deduced.size();
2610   } else {
2611     // Just fill in the parameter types from the function declaration.
2612     for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
2613       ParamTypes.push_back(Function->getParamDecl(I)->getType());
2614   }
2615
2616   // Deduce template arguments from the function parameters.
2617   Deduced.resize(TemplateParams->size());
2618   unsigned ArgIdx = 0;
2619   for (unsigned ParamIdx = 0, NumParams = ParamTypes.size();
2620        ParamIdx != NumParams; ++ParamIdx) {
2621     QualType ParamType = ParamTypes[ParamIdx];
2622
2623     const PackExpansionType *ParamExpansion
2624       = dyn_cast<PackExpansionType>(ParamType);
2625     if (!ParamExpansion) {
2626       // Simple case: matching a function parameter to a function argument.
2627       if (ArgIdx >= CheckArgs)
2628         break;
2629
2630       Expr *Arg = Args[ArgIdx++];
2631       QualType ArgType = Arg->getType();
2632       unsigned TDF = 0;
2633       if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
2634                                                     ParamType, ArgType, Arg,
2635                                                     TDF))
2636         continue;
2637
2638       if (TemplateDeductionResult Result
2639           = ::DeduceTemplateArguments(*this, TemplateParams,
2640                                       ParamType, ArgType, Info, Deduced,
2641                                       TDF))
2642         return Result;
2643
2644       // FIXME: we need to check that the deduced A is the same as A,
2645       // modulo the various allowed differences.
2646       continue;
2647     }
2648
2649     // C++0x [temp.deduct.call]p1:
2650     //   For a function parameter pack that occurs at the end of the
2651     //   parameter-declaration-list, the type A of each remaining argument of
2652     //   the call is compared with the type P of the declarator-id of the
2653     //   function parameter pack. Each comparison deduces template arguments
2654     //   for subsequent positions in the template parameter packs expanded by
2655     //   the function parameter pack. For a function parameter pack that does
2656     //   not occur at the end of the parameter-declaration-list, the type of
2657     //   the parameter pack is a non-deduced context.
2658     if (ParamIdx + 1 < NumParams)
2659       break;
2660
2661     QualType ParamPattern = ParamExpansion->getPattern();
2662     llvm::SmallVector<unsigned, 2> PackIndices;
2663     {
2664       llvm::BitVector SawIndices(TemplateParams->size());
2665       llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
2666       collectUnexpandedParameterPacks(ParamPattern, Unexpanded);
2667       for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
2668         unsigned Depth, Index;
2669         llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
2670         if (Depth == 0 && !SawIndices[Index]) {
2671           SawIndices[Index] = true;
2672           PackIndices.push_back(Index);
2673         }
2674       }
2675     }
2676     assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
2677
2678     // Keep track of the deduced template arguments for each parameter pack
2679     // expanded by this pack expansion (the outer index) and for each
2680     // template argument (the inner SmallVectors).
2681     llvm::SmallVector<llvm::SmallVector<DeducedTemplateArgument, 4>, 2>
2682       NewlyDeducedPacks(PackIndices.size());
2683     llvm::SmallVector<DeducedTemplateArgument, 2>
2684       SavedPacks(PackIndices.size());
2685     PrepareArgumentPackDeduction(*this, Deduced, PackIndices, SavedPacks,
2686                                  NewlyDeducedPacks);
2687     bool HasAnyArguments = false;
2688     for (; ArgIdx < NumArgs; ++ArgIdx) {
2689       HasAnyArguments = true;
2690
2691       ParamType = ParamPattern;
2692       Expr *Arg = Args[ArgIdx];
2693       QualType ArgType = Arg->getType();
2694       unsigned TDF = 0;
2695       if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
2696                                                     ParamType, ArgType, Arg,
2697                                                     TDF)) {
2698         // We can't actually perform any deduction for this argument, so stop
2699         // deduction at this point.
2700         ++ArgIdx;
2701         break;
2702       }
2703
2704       if (TemplateDeductionResult Result
2705           = ::DeduceTemplateArguments(*this, TemplateParams,
2706                                       ParamType, ArgType, Info, Deduced,
2707                                       TDF))
2708         return Result;
2709
2710       // Capture the deduced template arguments for each parameter pack expanded
2711       // by this pack expansion, add them to the list of arguments we've deduced
2712       // for that pack, then clear out the deduced argument.
2713       for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
2714         DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
2715         if (!DeducedArg.isNull()) {
2716           NewlyDeducedPacks[I].push_back(DeducedArg);
2717           DeducedArg = DeducedTemplateArgument();
2718         }
2719       }
2720     }
2721
2722     // Build argument packs for each of the parameter packs expanded by this
2723     // pack expansion.
2724     if (Sema::TemplateDeductionResult Result
2725           = FinishArgumentPackDeduction(*this, TemplateParams, HasAnyArguments,
2726                                         Deduced, PackIndices, SavedPacks,
2727                                         NewlyDeducedPacks, Info))
2728       return Result;
2729
2730     // After we've matching against a parameter pack, we're done.
2731     break;
2732   }
2733
2734   return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
2735                                          NumExplicitlySpecified,
2736                                          Specialization, Info);
2737 }
2738
2739 /// \brief Deduce template arguments when taking the address of a function
2740 /// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
2741 /// a template.
2742 ///
2743 /// \param FunctionTemplate the function template for which we are performing
2744 /// template argument deduction.
2745 ///
2746 /// \param ExplicitTemplateArguments the explicitly-specified template
2747 /// arguments.
2748 ///
2749 /// \param ArgFunctionType the function type that will be used as the
2750 /// "argument" type (A) when performing template argument deduction from the
2751 /// function template's function type. This type may be NULL, if there is no
2752 /// argument type to compare against, in C++0x [temp.arg.explicit]p3.
2753 ///
2754 /// \param Specialization if template argument deduction was successful,
2755 /// this will be set to the function template specialization produced by
2756 /// template argument deduction.
2757 ///
2758 /// \param Info the argument will be updated to provide additional information
2759 /// about template argument deduction.
2760 ///
2761 /// \returns the result of template argument deduction.
2762 Sema::TemplateDeductionResult
2763 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
2764                         const TemplateArgumentListInfo *ExplicitTemplateArgs,
2765                               QualType ArgFunctionType,
2766                               FunctionDecl *&Specialization,
2767                               TemplateDeductionInfo &Info) {
2768   FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2769   TemplateParameterList *TemplateParams
2770     = FunctionTemplate->getTemplateParameters();
2771   QualType FunctionType = Function->getType();
2772
2773   // Substitute any explicit template arguments.
2774   LocalInstantiationScope InstScope(*this);
2775   llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
2776   unsigned NumExplicitlySpecified = 0;
2777   llvm::SmallVector<QualType, 4> ParamTypes;
2778   if (ExplicitTemplateArgs) {
2779     if (TemplateDeductionResult Result
2780           = SubstituteExplicitTemplateArguments(FunctionTemplate,
2781                                                 *ExplicitTemplateArgs,
2782                                                 Deduced, ParamTypes,
2783                                                 &FunctionType, Info))
2784       return Result;
2785
2786     NumExplicitlySpecified = Deduced.size();
2787   }
2788
2789   // Template argument deduction for function templates in a SFINAE context.
2790   // Trap any errors that might occur.
2791   SFINAETrap Trap(*this);
2792
2793   Deduced.resize(TemplateParams->size());
2794
2795   if (!ArgFunctionType.isNull()) {
2796     // Deduce template arguments from the function type.
2797     if (TemplateDeductionResult Result
2798           = ::DeduceTemplateArguments(*this, TemplateParams,
2799                                       FunctionType, ArgFunctionType, Info,
2800                                       Deduced, TDF_TopLevelParameterTypeList))
2801       return Result;
2802   }
2803
2804   if (TemplateDeductionResult Result
2805         = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
2806                                           NumExplicitlySpecified,
2807                                           Specialization, Info))
2808     return Result;
2809
2810   // If the requested function type does not match the actual type of the
2811   // specialization, template argument deduction fails.
2812   if (!ArgFunctionType.isNull() &&
2813       !Context.hasSameType(ArgFunctionType, Specialization->getType()))
2814     return TDK_NonDeducedMismatch;
2815
2816   return TDK_Success;
2817 }
2818
2819 /// \brief Deduce template arguments for a templated conversion
2820 /// function (C++ [temp.deduct.conv]) and, if successful, produce a
2821 /// conversion function template specialization.
2822 Sema::TemplateDeductionResult
2823 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
2824                               QualType ToType,
2825                               CXXConversionDecl *&Specialization,
2826                               TemplateDeductionInfo &Info) {
2827   CXXConversionDecl *Conv
2828     = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl());
2829   QualType FromType = Conv->getConversionType();
2830
2831   // Canonicalize the types for deduction.
2832   QualType P = Context.getCanonicalType(FromType);
2833   QualType A = Context.getCanonicalType(ToType);
2834
2835   // C++0x [temp.deduct.conv]p3:
2836   //   If P is a reference type, the type referred to by P is used for
2837   //   type deduction.
2838   if (const ReferenceType *PRef = P->getAs<ReferenceType>())
2839     P = PRef->getPointeeType();
2840
2841   // C++0x [temp.deduct.conv]p3:
2842   //   If A is a reference type, the type referred to by A is used
2843   //   for type deduction.
2844   if (const ReferenceType *ARef = A->getAs<ReferenceType>())
2845     A = ARef->getPointeeType();
2846   // C++ [temp.deduct.conv]p2:
2847   //
2848   //   If A is not a reference type:
2849   else {
2850     assert(!A->isReferenceType() && "Reference types were handled above");
2851
2852     //   - If P is an array type, the pointer type produced by the
2853     //     array-to-pointer standard conversion (4.2) is used in place
2854     //     of P for type deduction; otherwise,
2855     if (P->isArrayType())
2856       P = Context.getArrayDecayedType(P);
2857     //   - If P is a function type, the pointer type produced by the
2858     //     function-to-pointer standard conversion (4.3) is used in
2859     //     place of P for type deduction; otherwise,
2860     else if (P->isFunctionType())
2861       P = Context.getPointerType(P);
2862     //   - If P is a cv-qualified type, the top level cv-qualifiers of
2863     //     P's type are ignored for type deduction.
2864     else
2865       P = P.getUnqualifiedType();
2866
2867     // C++0x [temp.deduct.conv]p3:
2868     //   If A is a cv-qualified type, the top level cv-qualifiers of A's
2869     //   type are ignored for type deduction.
2870     A = A.getUnqualifiedType();
2871   }
2872
2873   // Template argument deduction for function templates in a SFINAE context.
2874   // Trap any errors that might occur.
2875   SFINAETrap Trap(*this);
2876
2877   // C++ [temp.deduct.conv]p1:
2878   //   Template argument deduction is done by comparing the return
2879   //   type of the template conversion function (call it P) with the
2880   //   type that is required as the result of the conversion (call it
2881   //   A) as described in 14.8.2.4.
2882   TemplateParameterList *TemplateParams
2883     = FunctionTemplate->getTemplateParameters();
2884   llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
2885   Deduced.resize(TemplateParams->size());
2886
2887   // C++0x [temp.deduct.conv]p4:
2888   //   In general, the deduction process attempts to find template
2889   //   argument values that will make the deduced A identical to
2890   //   A. However, there are two cases that allow a difference:
2891   unsigned TDF = 0;
2892   //     - If the original A is a reference type, A can be more
2893   //       cv-qualified than the deduced A (i.e., the type referred to
2894   //       by the reference)
2895   if (ToType->isReferenceType())
2896     TDF |= TDF_ParamWithReferenceType;
2897   //     - The deduced A can be another pointer or pointer to member
2898   //       type that can be converted to A via a qualification
2899   //       conversion.
2900   //
2901   // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
2902   // both P and A are pointers or member pointers. In this case, we
2903   // just ignore cv-qualifiers completely).
2904   if ((P->isPointerType() && A->isPointerType()) ||
2905       (P->isMemberPointerType() && P->isMemberPointerType()))
2906     TDF |= TDF_IgnoreQualifiers;
2907   if (TemplateDeductionResult Result
2908         = ::DeduceTemplateArguments(*this, TemplateParams,
2909                                     P, A, Info, Deduced, TDF))
2910     return Result;
2911
2912   // FIXME: we need to check that the deduced A is the same as A,
2913   // modulo the various allowed differences.
2914
2915   // Finish template argument deduction.
2916   LocalInstantiationScope InstScope(*this);
2917   FunctionDecl *Spec = 0;
2918   TemplateDeductionResult Result
2919     = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec,
2920                                       Info);
2921   Specialization = cast_or_null<CXXConversionDecl>(Spec);
2922   return Result;
2923 }
2924
2925 /// \brief Deduce template arguments for a function template when there is
2926 /// nothing to deduce against (C++0x [temp.arg.explicit]p3).
2927 ///
2928 /// \param FunctionTemplate the function template for which we are performing
2929 /// template argument deduction.
2930 ///
2931 /// \param ExplicitTemplateArguments the explicitly-specified template
2932 /// arguments.
2933 ///
2934 /// \param Specialization if template argument deduction was successful,
2935 /// this will be set to the function template specialization produced by
2936 /// template argument deduction.
2937 ///
2938 /// \param Info the argument will be updated to provide additional information
2939 /// about template argument deduction.
2940 ///
2941 /// \returns the result of template argument deduction.
2942 Sema::TemplateDeductionResult
2943 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
2944                            const TemplateArgumentListInfo *ExplicitTemplateArgs,
2945                               FunctionDecl *&Specialization,
2946                               TemplateDeductionInfo &Info) {
2947   return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
2948                                  QualType(), Specialization, Info);
2949 }
2950
2951 namespace {
2952   /// Substitute the 'auto' type specifier within a type for a given replacement
2953   /// type.
2954   class SubstituteAutoTransform :
2955     public TreeTransform<SubstituteAutoTransform> {
2956     QualType Replacement;
2957   public:
2958     SubstituteAutoTransform(Sema &SemaRef, QualType Replacement) :
2959       TreeTransform<SubstituteAutoTransform>(SemaRef), Replacement(Replacement) {
2960     }
2961     QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
2962       // If we're building the type pattern to deduce against, don't wrap the
2963       // substituted type in an AutoType. Certain template deduction rules
2964       // apply only when a template type parameter appears directly (and not if
2965       // the parameter is found through desugaring). For instance:
2966       //   auto &&lref = lvalue;
2967       // must transform into "rvalue reference to T" not "rvalue reference to
2968       // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
2969       if (isa<TemplateTypeParmType>(Replacement)) {
2970         QualType Result = Replacement;
2971         TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
2972         NewTL.setNameLoc(TL.getNameLoc());
2973         return Result;
2974       } else {
2975         QualType Result = RebuildAutoType(Replacement);
2976         AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result);
2977         NewTL.setNameLoc(TL.getNameLoc());
2978         return Result;
2979       }
2980     }
2981   };
2982 }
2983
2984 /// \brief Deduce the type for an auto type-specifier (C++0x [dcl.spec.auto]p6)
2985 ///
2986 /// \param Type the type pattern using the auto type-specifier.
2987 ///
2988 /// \param Init the initializer for the variable whose type is to be deduced.
2989 ///
2990 /// \param Result if type deduction was successful, this will be set to the
2991 /// deduced type. This may still contain undeduced autos if the type is
2992 /// dependent.
2993 ///
2994 /// \returns true if deduction succeeded, false if it failed.
2995 bool
2996 Sema::DeduceAutoType(QualType Type, Expr *Init, QualType &Result) {
2997   if (Init->isTypeDependent()) {
2998     Result = Type;
2999     return true;
3000   }
3001
3002   SourceLocation Loc = Init->getExprLoc();
3003
3004   LocalInstantiationScope InstScope(*this);
3005
3006   // Build template<class TemplParam> void Func(FuncParam);
3007   QualType TemplArg = Context.getTemplateTypeParmType(0, 0, false);
3008   TemplateTypeParmDecl TemplParam(0, Loc, 0, false, TemplArg, false);
3009   NamedDecl *TemplParamPtr = &TemplParam;
3010   FixedSizeTemplateParameterList<1> TemplateParams(Loc, Loc, &TemplParamPtr,
3011                                                    Loc);
3012
3013   QualType FuncParam =
3014     SubstituteAutoTransform(*this, TemplArg).TransformType(Type);
3015
3016   // Deduce type of TemplParam in Func(Init)
3017   llvm::SmallVector<DeducedTemplateArgument, 1> Deduced;
3018   Deduced.resize(1);
3019   QualType InitType = Init->getType();
3020   unsigned TDF = 0;
3021   if (AdjustFunctionParmAndArgTypesForDeduction(*this, &TemplateParams,
3022                                                 FuncParam, InitType, Init,
3023                                                 TDF))
3024     return false;
3025
3026   TemplateDeductionInfo Info(Context, Loc);
3027   if (::DeduceTemplateArguments(*this, &TemplateParams,
3028                                 FuncParam, InitType, Info, Deduced,
3029                                 TDF))
3030     return false;
3031
3032   QualType DeducedType = Deduced[0].getAsType();
3033   if (DeducedType.isNull())
3034     return false;
3035
3036   Result = SubstituteAutoTransform(*this, DeducedType).TransformType(Type);
3037   return true;
3038 }
3039
3040 static void
3041 MarkUsedTemplateParameters(Sema &SemaRef, QualType T,
3042                            bool OnlyDeduced,
3043                            unsigned Level,
3044                            llvm::SmallVectorImpl<bool> &Deduced);
3045
3046 /// \brief If this is a non-static member function,
3047 static void MaybeAddImplicitObjectParameterType(ASTContext &Context,
3048                                                 CXXMethodDecl *Method,
3049                                  llvm::SmallVectorImpl<QualType> &ArgTypes) {
3050   if (Method->isStatic())
3051     return;
3052
3053   // C++ [over.match.funcs]p4:
3054   //
3055   //   For non-static member functions, the type of the implicit
3056   //   object parameter is
3057   //     - "lvalue reference to cv X" for functions declared without a
3058   //       ref-qualifier or with the & ref-qualifier
3059   //     - "rvalue reference to cv X" for functions declared with the
3060   //       && ref-qualifier
3061   //
3062   // FIXME: We don't have ref-qualifiers yet, so we don't do that part.
3063   QualType ArgTy = Context.getTypeDeclType(Method->getParent());
3064   ArgTy = Context.getQualifiedType(ArgTy,
3065                         Qualifiers::fromCVRMask(Method->getTypeQualifiers()));
3066   ArgTy = Context.getLValueReferenceType(ArgTy);
3067   ArgTypes.push_back(ArgTy);
3068 }
3069
3070 /// \brief Determine whether the function template \p FT1 is at least as
3071 /// specialized as \p FT2.
3072 static bool isAtLeastAsSpecializedAs(Sema &S,
3073                                      SourceLocation Loc,
3074                                      FunctionTemplateDecl *FT1,
3075                                      FunctionTemplateDecl *FT2,
3076                                      TemplatePartialOrderingContext TPOC,
3077                                      unsigned NumCallArguments,
3078     llvm::SmallVectorImpl<RefParamPartialOrderingComparison> *RefParamComparisons) {
3079   FunctionDecl *FD1 = FT1->getTemplatedDecl();
3080   FunctionDecl *FD2 = FT2->getTemplatedDecl();
3081   const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>();
3082   const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>();
3083
3084   assert(Proto1 && Proto2 && "Function templates must have prototypes");
3085   TemplateParameterList *TemplateParams = FT2->getTemplateParameters();
3086   llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
3087   Deduced.resize(TemplateParams->size());
3088
3089   // C++0x [temp.deduct.partial]p3:
3090   //   The types used to determine the ordering depend on the context in which
3091   //   the partial ordering is done:
3092   TemplateDeductionInfo Info(S.Context, Loc);
3093   CXXMethodDecl *Method1 = 0;
3094   CXXMethodDecl *Method2 = 0;
3095   bool IsNonStatic2 = false;
3096   bool IsNonStatic1 = false;
3097   unsigned Skip2 = 0;
3098   switch (TPOC) {
3099   case TPOC_Call: {
3100     //   - In the context of a function call, the function parameter types are
3101     //     used.
3102     Method1 = dyn_cast<CXXMethodDecl>(FD1);
3103     Method2 = dyn_cast<CXXMethodDecl>(FD2);
3104     IsNonStatic1 = Method1 && !Method1->isStatic();
3105     IsNonStatic2 = Method2 && !Method2->isStatic();
3106
3107     // C++0x [temp.func.order]p3:
3108     //   [...] If only one of the function templates is a non-static
3109     //   member, that function template is considered to have a new
3110     //   first parameter inserted in its function parameter list. The
3111     //   new parameter is of type "reference to cv A," where cv are
3112     //   the cv-qualifiers of the function template (if any) and A is
3113     //   the class of which the function template is a member.
3114     //
3115     // C++98/03 doesn't have this provision, so instead we drop the
3116     // first argument of the free function or static member, which
3117     // seems to match existing practice.
3118     llvm::SmallVector<QualType, 4> Args1;
3119     unsigned Skip1 = !S.getLangOptions().CPlusPlus0x &&
3120       IsNonStatic2 && !IsNonStatic1;
3121     if (S.getLangOptions().CPlusPlus0x && IsNonStatic1 && !IsNonStatic2)
3122       MaybeAddImplicitObjectParameterType(S.Context, Method1, Args1);
3123     Args1.insert(Args1.end(),
3124                  Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end());
3125
3126     llvm::SmallVector<QualType, 4> Args2;
3127     Skip2 = !S.getLangOptions().CPlusPlus0x &&
3128       IsNonStatic1 && !IsNonStatic2;
3129     if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1)
3130       MaybeAddImplicitObjectParameterType(S.Context, Method2, Args2);
3131     Args2.insert(Args2.end(),
3132                  Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end());
3133
3134     // C++ [temp.func.order]p5:
3135     //   The presence of unused ellipsis and default arguments has no effect on
3136     //   the partial ordering of function templates.
3137     if (Args1.size() > NumCallArguments)
3138       Args1.resize(NumCallArguments);
3139     if (Args2.size() > NumCallArguments)
3140       Args2.resize(NumCallArguments);
3141     if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(),
3142                                 Args1.data(), Args1.size(), Info, Deduced,
3143                                 TDF_None, /*PartialOrdering=*/true,
3144                                 RefParamComparisons))
3145         return false;
3146
3147     break;
3148   }
3149
3150   case TPOC_Conversion:
3151     //   - In the context of a call to a conversion operator, the return types
3152     //     of the conversion function templates are used.
3153     if (DeduceTemplateArguments(S, TemplateParams, Proto2->getResultType(),
3154                                 Proto1->getResultType(), Info, Deduced,
3155                                 TDF_None, /*PartialOrdering=*/true,
3156                                 RefParamComparisons))
3157       return false;
3158     break;
3159
3160   case TPOC_Other:
3161     //   - In other contexts (14.6.6.2) the function template's function type
3162     //     is used.
3163     // FIXME: Don't we actually want to perform the adjustments on the parameter
3164     // types?
3165     if (DeduceTemplateArguments(S, TemplateParams, FD2->getType(),
3166                                 FD1->getType(), Info, Deduced, TDF_None,
3167                                 /*PartialOrdering=*/true, RefParamComparisons))
3168       return false;
3169     break;
3170   }
3171
3172   // C++0x [temp.deduct.partial]p11:
3173   //   In most cases, all template parameters must have values in order for
3174   //   deduction to succeed, but for partial ordering purposes a template
3175   //   parameter may remain without a value provided it is not used in the
3176   //   types being used for partial ordering. [ Note: a template parameter used
3177   //   in a non-deduced context is considered used. -end note]
3178   unsigned ArgIdx = 0, NumArgs = Deduced.size();
3179   for (; ArgIdx != NumArgs; ++ArgIdx)
3180     if (Deduced[ArgIdx].isNull())
3181       break;
3182
3183   if (ArgIdx == NumArgs) {
3184     // All template arguments were deduced. FT1 is at least as specialized
3185     // as FT2.
3186     return true;
3187   }
3188
3189   // Figure out which template parameters were used.
3190   llvm::SmallVector<bool, 4> UsedParameters;
3191   UsedParameters.resize(TemplateParams->size());
3192   switch (TPOC) {
3193   case TPOC_Call: {
3194     unsigned NumParams = std::min(NumCallArguments,
3195                                   std::min(Proto1->getNumArgs(),
3196                                            Proto2->getNumArgs()));
3197     if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1)
3198       ::MarkUsedTemplateParameters(S, Method2->getThisType(S.Context), false,
3199                                    TemplateParams->getDepth(), UsedParameters);
3200     for (unsigned I = Skip2; I < NumParams; ++I)
3201       ::MarkUsedTemplateParameters(S, Proto2->getArgType(I), false,
3202                                    TemplateParams->getDepth(),
3203                                    UsedParameters);
3204     break;
3205   }
3206
3207   case TPOC_Conversion:
3208     ::MarkUsedTemplateParameters(S, Proto2->getResultType(), false,
3209                                  TemplateParams->getDepth(),
3210                                  UsedParameters);
3211     break;
3212
3213   case TPOC_Other:
3214     ::MarkUsedTemplateParameters(S, FD2->getType(), false,
3215                                  TemplateParams->getDepth(),
3216                                  UsedParameters);
3217     break;
3218   }
3219
3220   for (; ArgIdx != NumArgs; ++ArgIdx)
3221     // If this argument had no value deduced but was used in one of the types
3222     // used for partial ordering, then deduction fails.
3223     if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
3224       return false;
3225
3226   return true;
3227 }
3228
3229 /// \brief Determine whether this a function template whose parameter-type-list
3230 /// ends with a function parameter pack.
3231 static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) {
3232   FunctionDecl *Function = FunTmpl->getTemplatedDecl();
3233   unsigned NumParams = Function->getNumParams();
3234   if (NumParams == 0)
3235     return false;
3236
3237   ParmVarDecl *Last = Function->getParamDecl(NumParams - 1);
3238   if (!Last->isParameterPack())
3239     return false;
3240
3241   // Make sure that no previous parameter is a parameter pack.
3242   while (--NumParams > 0) {
3243     if (Function->getParamDecl(NumParams - 1)->isParameterPack())
3244       return false;
3245   }
3246
3247   return true;
3248 }
3249
3250 /// \brief Returns the more specialized function template according
3251 /// to the rules of function template partial ordering (C++ [temp.func.order]).
3252 ///
3253 /// \param FT1 the first function template
3254 ///
3255 /// \param FT2 the second function template
3256 ///
3257 /// \param TPOC the context in which we are performing partial ordering of
3258 /// function templates.
3259 ///
3260 /// \param NumCallArguments The number of arguments in a call, used only
3261 /// when \c TPOC is \c TPOC_Call.
3262 ///
3263 /// \returns the more specialized function template. If neither
3264 /// template is more specialized, returns NULL.
3265 FunctionTemplateDecl *
3266 Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1,
3267                                  FunctionTemplateDecl *FT2,
3268                                  SourceLocation Loc,
3269                                  TemplatePartialOrderingContext TPOC,
3270                                  unsigned NumCallArguments) {
3271   llvm::SmallVector<RefParamPartialOrderingComparison, 4> RefParamComparisons;
3272   bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
3273                                           NumCallArguments, 0);
3274   bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
3275                                           NumCallArguments,
3276                                           &RefParamComparisons);
3277
3278   if (Better1 != Better2) // We have a clear winner
3279     return Better1? FT1 : FT2;
3280
3281   if (!Better1 && !Better2) // Neither is better than the other
3282     return 0;
3283
3284   // C++0x [temp.deduct.partial]p10:
3285   //   If for each type being considered a given template is at least as
3286   //   specialized for all types and more specialized for some set of types and
3287   //   the other template is not more specialized for any types or is not at
3288   //   least as specialized for any types, then the given template is more
3289   //   specialized than the other template. Otherwise, neither template is more
3290   //   specialized than the other.
3291   Better1 = false;
3292   Better2 = false;
3293   for (unsigned I = 0, N = RefParamComparisons.size(); I != N; ++I) {
3294     // C++0x [temp.deduct.partial]p9:
3295     //   If, for a given type, deduction succeeds in both directions (i.e., the
3296     //   types are identical after the transformations above) and both P and A
3297     //   were reference types (before being replaced with the type referred to
3298     //   above):
3299
3300     //     -- if the type from the argument template was an lvalue reference
3301     //        and the type from the parameter template was not, the argument
3302     //        type is considered to be more specialized than the other;
3303     //        otherwise,
3304     if (!RefParamComparisons[I].ArgIsRvalueRef &&
3305         RefParamComparisons[I].ParamIsRvalueRef) {
3306       Better2 = true;
3307       if (Better1)
3308         return 0;
3309       continue;
3310     } else if (!RefParamComparisons[I].ParamIsRvalueRef &&
3311                RefParamComparisons[I].ArgIsRvalueRef) {
3312       Better1 = true;
3313       if (Better2)
3314         return 0;
3315       continue;
3316     }
3317
3318     //     -- if the type from the argument template is more cv-qualified than
3319     //        the type from the parameter template (as described above), the
3320     //        argument type is considered to be more specialized than the
3321     //        other; otherwise,
3322     switch (RefParamComparisons[I].Qualifiers) {
3323     case NeitherMoreQualified:
3324       break;
3325
3326     case ParamMoreQualified:
3327       Better1 = true;
3328       if (Better2)
3329         return 0;
3330       continue;
3331
3332     case ArgMoreQualified:
3333       Better2 = true;
3334       if (Better1)
3335         return 0;
3336       continue;
3337     }
3338
3339     //     -- neither type is more specialized than the other.
3340   }
3341
3342   assert(!(Better1 && Better2) && "Should have broken out in the loop above");
3343   if (Better1)
3344     return FT1;
3345   else if (Better2)
3346     return FT2;
3347
3348   // FIXME: This mimics what GCC implements, but doesn't match up with the
3349   // proposed resolution for core issue 692. This area needs to be sorted out,
3350   // but for now we attempt to maintain compatibility.
3351   bool Variadic1 = isVariadicFunctionTemplate(FT1);
3352   bool Variadic2 = isVariadicFunctionTemplate(FT2);
3353   if (Variadic1 != Variadic2)
3354     return Variadic1? FT2 : FT1;
3355
3356   return 0;
3357 }
3358
3359 /// \brief Determine if the two templates are equivalent.
3360 static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) {
3361   if (T1 == T2)
3362     return true;
3363
3364   if (!T1 || !T2)
3365     return false;
3366
3367   return T1->getCanonicalDecl() == T2->getCanonicalDecl();
3368 }
3369
3370 /// \brief Retrieve the most specialized of the given function template
3371 /// specializations.
3372 ///
3373 /// \param SpecBegin the start iterator of the function template
3374 /// specializations that we will be comparing.
3375 ///
3376 /// \param SpecEnd the end iterator of the function template
3377 /// specializations, paired with \p SpecBegin.
3378 ///
3379 /// \param TPOC the partial ordering context to use to compare the function
3380 /// template specializations.
3381 ///
3382 /// \param NumCallArguments The number of arguments in a call, used only
3383 /// when \c TPOC is \c TPOC_Call.
3384 ///
3385 /// \param Loc the location where the ambiguity or no-specializations
3386 /// diagnostic should occur.
3387 ///
3388 /// \param NoneDiag partial diagnostic used to diagnose cases where there are
3389 /// no matching candidates.
3390 ///
3391 /// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one
3392 /// occurs.
3393 ///
3394 /// \param CandidateDiag partial diagnostic used for each function template
3395 /// specialization that is a candidate in the ambiguous ordering. One parameter
3396 /// in this diagnostic should be unbound, which will correspond to the string
3397 /// describing the template arguments for the function template specialization.
3398 ///
3399 /// \param Index if non-NULL and the result of this function is non-nULL,
3400 /// receives the index corresponding to the resulting function template
3401 /// specialization.
3402 ///
3403 /// \returns the most specialized function template specialization, if
3404 /// found. Otherwise, returns SpecEnd.
3405 ///
3406 /// \todo FIXME: Consider passing in the "also-ran" candidates that failed
3407 /// template argument deduction.
3408 UnresolvedSetIterator
3409 Sema::getMostSpecialized(UnresolvedSetIterator SpecBegin,
3410                         UnresolvedSetIterator SpecEnd,
3411                          TemplatePartialOrderingContext TPOC,
3412                          unsigned NumCallArguments,
3413                          SourceLocation Loc,
3414                          const PartialDiagnostic &NoneDiag,
3415                          const PartialDiagnostic &AmbigDiag,
3416                          const PartialDiagnostic &CandidateDiag,
3417                          bool Complain) {
3418   if (SpecBegin == SpecEnd) {
3419     if (Complain)
3420       Diag(Loc, NoneDiag);
3421     return SpecEnd;
3422   }
3423
3424   if (SpecBegin + 1 == SpecEnd)
3425     return SpecBegin;
3426
3427   // Find the function template that is better than all of the templates it
3428   // has been compared to.
3429   UnresolvedSetIterator Best = SpecBegin;
3430   FunctionTemplateDecl *BestTemplate
3431     = cast<FunctionDecl>(*Best)->getPrimaryTemplate();
3432   assert(BestTemplate && "Not a function template specialization?");
3433   for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) {
3434     FunctionTemplateDecl *Challenger
3435       = cast<FunctionDecl>(*I)->getPrimaryTemplate();
3436     assert(Challenger && "Not a function template specialization?");
3437     if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
3438                                                   Loc, TPOC, NumCallArguments),
3439                        Challenger)) {
3440       Best = I;
3441       BestTemplate = Challenger;
3442     }
3443   }
3444
3445   // Make sure that the "best" function template is more specialized than all
3446   // of the others.
3447   bool Ambiguous = false;
3448   for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
3449     FunctionTemplateDecl *Challenger
3450       = cast<FunctionDecl>(*I)->getPrimaryTemplate();
3451     if (I != Best &&
3452         !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
3453                                                    Loc, TPOC, NumCallArguments),
3454                         BestTemplate)) {
3455       Ambiguous = true;
3456       break;
3457     }
3458   }
3459
3460   if (!Ambiguous) {
3461     // We found an answer. Return it.
3462     return Best;
3463   }
3464
3465   // Diagnose the ambiguity.
3466   if (Complain)
3467     Diag(Loc, AmbigDiag);
3468
3469   if (Complain)
3470   // FIXME: Can we order the candidates in some sane way?
3471     for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I)
3472       Diag((*I)->getLocation(), CandidateDiag)
3473         << getTemplateArgumentBindingsText(
3474           cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(),
3475                     *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs());
3476
3477   return SpecEnd;
3478 }
3479
3480 /// \brief Returns the more specialized class template partial specialization
3481 /// according to the rules of partial ordering of class template partial
3482 /// specializations (C++ [temp.class.order]).
3483 ///
3484 /// \param PS1 the first class template partial specialization
3485 ///
3486 /// \param PS2 the second class template partial specialization
3487 ///
3488 /// \returns the more specialized class template partial specialization. If
3489 /// neither partial specialization is more specialized, returns NULL.
3490 ClassTemplatePartialSpecializationDecl *
3491 Sema::getMoreSpecializedPartialSpecialization(
3492                                   ClassTemplatePartialSpecializationDecl *PS1,
3493                                   ClassTemplatePartialSpecializationDecl *PS2,
3494                                               SourceLocation Loc) {
3495   // C++ [temp.class.order]p1:
3496   //   For two class template partial specializations, the first is at least as
3497   //   specialized as the second if, given the following rewrite to two
3498   //   function templates, the first function template is at least as
3499   //   specialized as the second according to the ordering rules for function
3500   //   templates (14.6.6.2):
3501   //     - the first function template has the same template parameters as the
3502   //       first partial specialization and has a single function parameter
3503   //       whose type is a class template specialization with the template
3504   //       arguments of the first partial specialization, and
3505   //     - the second function template has the same template parameters as the
3506   //       second partial specialization and has a single function parameter
3507   //       whose type is a class template specialization with the template
3508   //       arguments of the second partial specialization.
3509   //
3510   // Rather than synthesize function templates, we merely perform the
3511   // equivalent partial ordering by performing deduction directly on
3512   // the template arguments of the class template partial
3513   // specializations. This computation is slightly simpler than the
3514   // general problem of function template partial ordering, because
3515   // class template partial specializations are more constrained. We
3516   // know that every template parameter is deducible from the class
3517   // template partial specialization's template arguments, for
3518   // example.
3519   llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
3520   TemplateDeductionInfo Info(Context, Loc);
3521
3522   QualType PT1 = PS1->getInjectedSpecializationType();
3523   QualType PT2 = PS2->getInjectedSpecializationType();
3524
3525   // Determine whether PS1 is at least as specialized as PS2
3526   Deduced.resize(PS2->getTemplateParameters()->size());
3527   bool Better1 = !::DeduceTemplateArguments(*this, PS2->getTemplateParameters(),
3528                                             PT2, PT1, Info, Deduced, TDF_None,
3529                                             /*PartialOrdering=*/true,
3530                                             /*RefParamComparisons=*/0);
3531   if (Better1) {
3532     InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2,
3533                                Deduced.data(), Deduced.size(), Info);
3534     Better1 = !::FinishTemplateArgumentDeduction(*this, PS2,
3535                                                  PS1->getTemplateArgs(),
3536                                                  Deduced, Info);
3537   }
3538
3539   // Determine whether PS2 is at least as specialized as PS1
3540   Deduced.clear();
3541   Deduced.resize(PS1->getTemplateParameters()->size());
3542   bool Better2 = !::DeduceTemplateArguments(*this, PS1->getTemplateParameters(),
3543                                             PT1, PT2, Info, Deduced, TDF_None,
3544                                             /*PartialOrdering=*/true,
3545                                             /*RefParamComparisons=*/0);
3546   if (Better2) {
3547     InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1,
3548                                Deduced.data(), Deduced.size(), Info);
3549     Better2 = !::FinishTemplateArgumentDeduction(*this, PS1,
3550                                                  PS2->getTemplateArgs(),
3551                                                  Deduced, Info);
3552   }
3553
3554   if (Better1 == Better2)
3555     return 0;
3556
3557   return Better1? PS1 : PS2;
3558 }
3559
3560 static void
3561 MarkUsedTemplateParameters(Sema &SemaRef,
3562                            const TemplateArgument &TemplateArg,
3563                            bool OnlyDeduced,
3564                            unsigned Depth,
3565                            llvm::SmallVectorImpl<bool> &Used);
3566
3567 /// \brief Mark the template parameters that are used by the given
3568 /// expression.
3569 static void
3570 MarkUsedTemplateParameters(Sema &SemaRef,
3571                            const Expr *E,
3572                            bool OnlyDeduced,
3573                            unsigned Depth,
3574                            llvm::SmallVectorImpl<bool> &Used) {
3575   // We can deduce from a pack expansion.
3576   if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E))
3577     E = Expansion->getPattern();
3578
3579   // Skip through any implicit casts we added while type-checking.
3580   while (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
3581     E = ICE->getSubExpr();
3582
3583   // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to
3584   // find other occurrences of template parameters.
3585   const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
3586   if (!DRE)
3587     return;
3588
3589   const NonTypeTemplateParmDecl *NTTP
3590     = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
3591   if (!NTTP)
3592     return;
3593
3594   if (NTTP->getDepth() == Depth)
3595     Used[NTTP->getIndex()] = true;
3596 }
3597
3598 /// \brief Mark the template parameters that are used by the given
3599 /// nested name specifier.
3600 static void
3601 MarkUsedTemplateParameters(Sema &SemaRef,
3602                            NestedNameSpecifier *NNS,
3603                            bool OnlyDeduced,
3604                            unsigned Depth,
3605                            llvm::SmallVectorImpl<bool> &Used) {
3606   if (!NNS)
3607     return;
3608
3609   MarkUsedTemplateParameters(SemaRef, NNS->getPrefix(), OnlyDeduced, Depth,
3610                              Used);
3611   MarkUsedTemplateParameters(SemaRef, QualType(NNS->getAsType(), 0),
3612                              OnlyDeduced, Depth, Used);
3613 }
3614
3615 /// \brief Mark the template parameters that are used by the given
3616 /// template name.
3617 static void
3618 MarkUsedTemplateParameters(Sema &SemaRef,
3619                            TemplateName Name,
3620                            bool OnlyDeduced,
3621                            unsigned Depth,
3622                            llvm::SmallVectorImpl<bool> &Used) {
3623   if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
3624     if (TemplateTemplateParmDecl *TTP
3625           = dyn_cast<TemplateTemplateParmDecl>(Template)) {
3626       if (TTP->getDepth() == Depth)
3627         Used[TTP->getIndex()] = true;
3628     }
3629     return;
3630   }
3631
3632   if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName())
3633     MarkUsedTemplateParameters(SemaRef, QTN->getQualifier(), OnlyDeduced,
3634                                Depth, Used);
3635   if (DependentTemplateName *DTN = Name.getAsDependentTemplateName())
3636     MarkUsedTemplateParameters(SemaRef, DTN->getQualifier(), OnlyDeduced,
3637                                Depth, Used);
3638 }
3639
3640 /// \brief Mark the template parameters that are used by the given
3641 /// type.
3642 static void
3643 MarkUsedTemplateParameters(Sema &SemaRef, QualType T,
3644                            bool OnlyDeduced,
3645                            unsigned Depth,
3646                            llvm::SmallVectorImpl<bool> &Used) {
3647   if (T.isNull())
3648     return;
3649
3650   // Non-dependent types have nothing deducible
3651   if (!T->isDependentType())
3652     return;
3653
3654   T = SemaRef.Context.getCanonicalType(T);
3655   switch (T->getTypeClass()) {
3656   case Type::Pointer:
3657     MarkUsedTemplateParameters(SemaRef,
3658                                cast<PointerType>(T)->getPointeeType(),
3659                                OnlyDeduced,
3660                                Depth,
3661                                Used);
3662     break;
3663
3664   case Type::BlockPointer:
3665     MarkUsedTemplateParameters(SemaRef,
3666                                cast<BlockPointerType>(T)->getPointeeType(),
3667                                OnlyDeduced,
3668                                Depth,
3669                                Used);
3670     break;
3671
3672   case Type::LValueReference:
3673   case Type::RValueReference:
3674     MarkUsedTemplateParameters(SemaRef,
3675                                cast<ReferenceType>(T)->getPointeeType(),
3676                                OnlyDeduced,
3677                                Depth,
3678                                Used);
3679     break;
3680
3681   case Type::MemberPointer: {
3682     const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
3683     MarkUsedTemplateParameters(SemaRef, MemPtr->getPointeeType(), OnlyDeduced,
3684                                Depth, Used);
3685     MarkUsedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0),
3686                                OnlyDeduced, Depth, Used);
3687     break;
3688   }
3689
3690   case Type::DependentSizedArray:
3691     MarkUsedTemplateParameters(SemaRef,
3692                                cast<DependentSizedArrayType>(T)->getSizeExpr(),
3693                                OnlyDeduced, Depth, Used);
3694     // Fall through to check the element type
3695
3696   case Type::ConstantArray:
3697   case Type::IncompleteArray:
3698     MarkUsedTemplateParameters(SemaRef,
3699                                cast<ArrayType>(T)->getElementType(),
3700                                OnlyDeduced, Depth, Used);
3701     break;
3702
3703   case Type::Vector:
3704   case Type::ExtVector:
3705     MarkUsedTemplateParameters(SemaRef,
3706                                cast<VectorType>(T)->getElementType(),
3707                                OnlyDeduced, Depth, Used);
3708     break;
3709
3710   case Type::DependentSizedExtVector: {
3711     const DependentSizedExtVectorType *VecType
3712       = cast<DependentSizedExtVectorType>(T);
3713     MarkUsedTemplateParameters(SemaRef, VecType->getElementType(), OnlyDeduced,
3714                                Depth, Used);
3715     MarkUsedTemplateParameters(SemaRef, VecType->getSizeExpr(), OnlyDeduced,
3716                                Depth, Used);
3717     break;
3718   }
3719
3720   case Type::FunctionProto: {
3721     const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
3722     MarkUsedTemplateParameters(SemaRef, Proto->getResultType(), OnlyDeduced,
3723                                Depth, Used);
3724     for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I)
3725       MarkUsedTemplateParameters(SemaRef, Proto->getArgType(I), OnlyDeduced,
3726                                  Depth, Used);
3727     break;
3728   }
3729
3730   case Type::TemplateTypeParm: {
3731     const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T);
3732     if (TTP->getDepth() == Depth)
3733       Used[TTP->getIndex()] = true;
3734     break;
3735   }
3736
3737   case Type::SubstTemplateTypeParmPack: {
3738     const SubstTemplateTypeParmPackType *Subst
3739       = cast<SubstTemplateTypeParmPackType>(T);
3740     MarkUsedTemplateParameters(SemaRef,
3741                                QualType(Subst->getReplacedParameter(), 0),
3742                                OnlyDeduced, Depth, Used);
3743     MarkUsedTemplateParameters(SemaRef, Subst->getArgumentPack(),
3744                                OnlyDeduced, Depth, Used);
3745     break;
3746   }
3747
3748   case Type::InjectedClassName:
3749     T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType();
3750     // fall through
3751
3752   case Type::TemplateSpecialization: {
3753     const TemplateSpecializationType *Spec
3754       = cast<TemplateSpecializationType>(T);
3755     MarkUsedTemplateParameters(SemaRef, Spec->getTemplateName(), OnlyDeduced,
3756                                Depth, Used);
3757
3758     // C++0x [temp.deduct.type]p9:
3759     //   If the template argument list of P contains a pack expansion that is not
3760     //   the last template argument, the entire template argument list is a
3761     //   non-deduced context.
3762     if (OnlyDeduced &&
3763         hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
3764       break;
3765
3766     for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
3767       MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth,
3768                                  Used);
3769     break;
3770   }
3771
3772   case Type::Complex:
3773     if (!OnlyDeduced)
3774       MarkUsedTemplateParameters(SemaRef,
3775                                  cast<ComplexType>(T)->getElementType(),
3776                                  OnlyDeduced, Depth, Used);
3777     break;
3778
3779   case Type::DependentName:
3780     if (!OnlyDeduced)
3781       MarkUsedTemplateParameters(SemaRef,
3782                                  cast<DependentNameType>(T)->getQualifier(),
3783                                  OnlyDeduced, Depth, Used);
3784     break;
3785
3786   case Type::DependentTemplateSpecialization: {
3787     const DependentTemplateSpecializationType *Spec
3788       = cast<DependentTemplateSpecializationType>(T);
3789     if (!OnlyDeduced)
3790       MarkUsedTemplateParameters(SemaRef, Spec->getQualifier(),
3791                                  OnlyDeduced, Depth, Used);
3792
3793     // C++0x [temp.deduct.type]p9:
3794     //   If the template argument list of P contains a pack expansion that is not
3795     //   the last template argument, the entire template argument list is a
3796     //   non-deduced context.
3797     if (OnlyDeduced &&
3798         hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
3799       break;
3800
3801     for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
3802       MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth,
3803                                  Used);
3804     break;
3805   }
3806
3807   case Type::TypeOf:
3808     if (!OnlyDeduced)
3809       MarkUsedTemplateParameters(SemaRef,
3810                                  cast<TypeOfType>(T)->getUnderlyingType(),
3811                                  OnlyDeduced, Depth, Used);
3812     break;
3813
3814   case Type::TypeOfExpr:
3815     if (!OnlyDeduced)
3816       MarkUsedTemplateParameters(SemaRef,
3817                                  cast<TypeOfExprType>(T)->getUnderlyingExpr(),
3818                                  OnlyDeduced, Depth, Used);
3819     break;
3820
3821   case Type::Decltype:
3822     if (!OnlyDeduced)
3823       MarkUsedTemplateParameters(SemaRef,
3824                                  cast<DecltypeType>(T)->getUnderlyingExpr(),
3825                                  OnlyDeduced, Depth, Used);
3826     break;
3827
3828   case Type::PackExpansion:
3829     MarkUsedTemplateParameters(SemaRef,
3830                                cast<PackExpansionType>(T)->getPattern(),
3831                                OnlyDeduced, Depth, Used);
3832     break;
3833
3834   case Type::Auto:
3835     MarkUsedTemplateParameters(SemaRef,
3836                                cast<AutoType>(T)->getDeducedType(),
3837                                OnlyDeduced, Depth, Used);
3838
3839   // None of these types have any template parameters in them.
3840   case Type::Builtin:
3841   case Type::VariableArray:
3842   case Type::FunctionNoProto:
3843   case Type::Record:
3844   case Type::Enum:
3845   case Type::ObjCInterface:
3846   case Type::ObjCObject:
3847   case Type::ObjCObjectPointer:
3848   case Type::UnresolvedUsing:
3849 #define TYPE(Class, Base)
3850 #define ABSTRACT_TYPE(Class, Base)
3851 #define DEPENDENT_TYPE(Class, Base)
3852 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
3853 #include "clang/AST/TypeNodes.def"
3854     break;
3855   }
3856 }
3857
3858 /// \brief Mark the template parameters that are used by this
3859 /// template argument.
3860 static void
3861 MarkUsedTemplateParameters(Sema &SemaRef,
3862                            const TemplateArgument &TemplateArg,
3863                            bool OnlyDeduced,
3864                            unsigned Depth,
3865                            llvm::SmallVectorImpl<bool> &Used) {
3866   switch (TemplateArg.getKind()) {
3867   case TemplateArgument::Null:
3868   case TemplateArgument::Integral:
3869     case TemplateArgument::Declaration:
3870     break;
3871
3872   case TemplateArgument::Type:
3873     MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsType(), OnlyDeduced,
3874                                Depth, Used);
3875     break;
3876
3877   case TemplateArgument::Template:
3878   case TemplateArgument::TemplateExpansion:
3879     MarkUsedTemplateParameters(SemaRef,
3880                                TemplateArg.getAsTemplateOrTemplatePattern(),
3881                                OnlyDeduced, Depth, Used);
3882     break;
3883
3884   case TemplateArgument::Expression:
3885     MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsExpr(), OnlyDeduced,
3886                                Depth, Used);
3887     break;
3888
3889   case TemplateArgument::Pack:
3890     for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(),
3891                                       PEnd = TemplateArg.pack_end();
3892          P != PEnd; ++P)
3893       MarkUsedTemplateParameters(SemaRef, *P, OnlyDeduced, Depth, Used);
3894     break;
3895   }
3896 }
3897
3898 /// \brief Mark the template parameters can be deduced by the given
3899 /// template argument list.
3900 ///
3901 /// \param TemplateArgs the template argument list from which template
3902 /// parameters will be deduced.
3903 ///
3904 /// \param Deduced a bit vector whose elements will be set to \c true
3905 /// to indicate when the corresponding template parameter will be
3906 /// deduced.
3907 void
3908 Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs,
3909                                  bool OnlyDeduced, unsigned Depth,
3910                                  llvm::SmallVectorImpl<bool> &Used) {
3911   // C++0x [temp.deduct.type]p9:
3912   //   If the template argument list of P contains a pack expansion that is not
3913   //   the last template argument, the entire template argument list is a
3914   //   non-deduced context.
3915   if (OnlyDeduced &&
3916       hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size()))
3917     return;
3918
3919   for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
3920     ::MarkUsedTemplateParameters(*this, TemplateArgs[I], OnlyDeduced,
3921                                  Depth, Used);
3922 }
3923
3924 /// \brief Marks all of the template parameters that will be deduced by a
3925 /// call to the given function template.
3926 void
3927 Sema::MarkDeducedTemplateParameters(FunctionTemplateDecl *FunctionTemplate,
3928                                     llvm::SmallVectorImpl<bool> &Deduced) {
3929   TemplateParameterList *TemplateParams
3930     = FunctionTemplate->getTemplateParameters();
3931   Deduced.clear();
3932   Deduced.resize(TemplateParams->size());
3933
3934   FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3935   for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
3936     ::MarkUsedTemplateParameters(*this, Function->getParamDecl(I)->getType(),
3937                                  true, TemplateParams->getDepth(), Deduced);
3938 }