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