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