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