SemaTemplateDeduction.cpp revision a085da86242c9b8e3466f8cf6f4397e9f248fd20
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 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 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 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]p2: 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]p4: 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().getUnqualifiedType(); 2859 // C++ [temp.deduct.conv]p3: 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]p4: 2881 // If A is a cv-qualified type, the top level cv-qualifiers of A's 2882 // type are ignored for type deduction. If A is a reference type, the type 2883 // referred to by A is used for type deduction. 2884 A = A.getUnqualifiedType(); 2885 } 2886 2887 // Template argument deduction for function templates in a SFINAE context. 2888 // Trap any errors that might occur. 2889 SFINAETrap Trap(*this); 2890 2891 // C++ [temp.deduct.conv]p1: 2892 // Template argument deduction is done by comparing the return 2893 // type of the template conversion function (call it P) with the 2894 // type that is required as the result of the conversion (call it 2895 // A) as described in 14.8.2.4. 2896 TemplateParameterList *TemplateParams 2897 = FunctionTemplate->getTemplateParameters(); 2898 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2899 Deduced.resize(TemplateParams->size()); 2900 2901 // C++0x [temp.deduct.conv]p4: 2902 // In general, the deduction process attempts to find template 2903 // argument values that will make the deduced A identical to 2904 // A. However, there are two cases that allow a difference: 2905 unsigned TDF = 0; 2906 // - If the original A is a reference type, A can be more 2907 // cv-qualified than the deduced A (i.e., the type referred to 2908 // by the reference) 2909 if (ToType->isReferenceType()) 2910 TDF |= TDF_ParamWithReferenceType; 2911 // - The deduced A can be another pointer or pointer to member 2912 // type that can be converted to A via a qualification 2913 // conversion. 2914 // 2915 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 2916 // both P and A are pointers or member pointers. In this case, we 2917 // just ignore cv-qualifiers completely). 2918 if ((P->isPointerType() && A->isPointerType()) || 2919 (P->isMemberPointerType() && P->isMemberPointerType())) 2920 TDF |= TDF_IgnoreQualifiers; 2921 if (TemplateDeductionResult Result 2922 = ::DeduceTemplateArguments(*this, TemplateParams, 2923 P, A, Info, Deduced, TDF)) 2924 return Result; 2925 2926 // FIXME: we need to check that the deduced A is the same as A, 2927 // modulo the various allowed differences. 2928 2929 // Finish template argument deduction. 2930 LocalInstantiationScope InstScope(*this); 2931 FunctionDecl *Spec = 0; 2932 TemplateDeductionResult Result 2933 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec, 2934 Info); 2935 Specialization = cast_or_null<CXXConversionDecl>(Spec); 2936 return Result; 2937} 2938 2939/// \brief Deduce template arguments for a function template when there is 2940/// nothing to deduce against (C++0x [temp.arg.explicit]p3). 2941/// 2942/// \param FunctionTemplate the function template for which we are performing 2943/// template argument deduction. 2944/// 2945/// \param ExplicitTemplateArguments the explicitly-specified template 2946/// arguments. 2947/// 2948/// \param Specialization if template argument deduction was successful, 2949/// this will be set to the function template specialization produced by 2950/// template argument deduction. 2951/// 2952/// \param Info the argument will be updated to provide additional information 2953/// about template argument deduction. 2954/// 2955/// \returns the result of template argument deduction. 2956Sema::TemplateDeductionResult 2957Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2958 TemplateArgumentListInfo *ExplicitTemplateArgs, 2959 FunctionDecl *&Specialization, 2960 TemplateDeductionInfo &Info) { 2961 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs, 2962 QualType(), Specialization, Info); 2963} 2964 2965namespace { 2966 /// Substitute the 'auto' type specifier within a type for a given replacement 2967 /// type. 2968 class SubstituteAutoTransform : 2969 public TreeTransform<SubstituteAutoTransform> { 2970 QualType Replacement; 2971 public: 2972 SubstituteAutoTransform(Sema &SemaRef, QualType Replacement) : 2973 TreeTransform<SubstituteAutoTransform>(SemaRef), Replacement(Replacement) { 2974 } 2975 QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) { 2976 // If we're building the type pattern to deduce against, don't wrap the 2977 // substituted type in an AutoType. Certain template deduction rules 2978 // apply only when a template type parameter appears directly (and not if 2979 // the parameter is found through desugaring). For instance: 2980 // auto &&lref = lvalue; 2981 // must transform into "rvalue reference to T" not "rvalue reference to 2982 // auto type deduced as T" in order for [temp.deduct.call]p3 to apply. 2983 if (isa<TemplateTypeParmType>(Replacement)) { 2984 QualType Result = Replacement; 2985 TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result); 2986 NewTL.setNameLoc(TL.getNameLoc()); 2987 return Result; 2988 } else { 2989 QualType Result = RebuildAutoType(Replacement); 2990 AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result); 2991 NewTL.setNameLoc(TL.getNameLoc()); 2992 return Result; 2993 } 2994 } 2995 }; 2996} 2997 2998/// \brief Deduce the type for an auto type-specifier (C++0x [dcl.spec.auto]p6) 2999/// 3000/// \param Type the type pattern using the auto type-specifier. 3001/// 3002/// \param Init the initializer for the variable whose type is to be deduced. 3003/// 3004/// \param Result if type deduction was successful, this will be set to the 3005/// deduced type. This may still contain undeduced autos if the type is 3006/// dependent. This will be set to null if deduction succeeded, but auto 3007/// substitution failed; the appropriate diagnostic will already have been 3008/// produced in that case. 3009/// 3010/// \returns true if deduction succeeded, false if it failed. 3011bool 3012Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *Init, 3013 TypeSourceInfo *&Result) { 3014 if (Init->isTypeDependent()) { 3015 Result = Type; 3016 return true; 3017 } 3018 3019 SourceLocation Loc = Init->getExprLoc(); 3020 3021 LocalInstantiationScope InstScope(*this); 3022 3023 // Build template<class TemplParam> void Func(FuncParam); 3024 QualType TemplArg = Context.getTemplateTypeParmType(0, 0, false); 3025 TemplateTypeParmDecl TemplParam(0, SourceLocation(), Loc, 0, false, 3026 TemplArg, false); 3027 NamedDecl *TemplParamPtr = &TemplParam; 3028 FixedSizeTemplateParameterList<1> TemplateParams(Loc, Loc, &TemplParamPtr, 3029 Loc); 3030 3031 TypeSourceInfo *FuncParamInfo = 3032 SubstituteAutoTransform(*this, TemplArg).TransformType(Type); 3033 assert(FuncParamInfo && "substituting template parameter for 'auto' failed"); 3034 QualType FuncParam = FuncParamInfo->getType(); 3035 3036 // Deduce type of TemplParam in Func(Init) 3037 llvm::SmallVector<DeducedTemplateArgument, 1> Deduced; 3038 Deduced.resize(1); 3039 QualType InitType = Init->getType(); 3040 unsigned TDF = 0; 3041 if (AdjustFunctionParmAndArgTypesForDeduction(*this, &TemplateParams, 3042 FuncParam, InitType, Init, 3043 TDF)) 3044 return false; 3045 3046 TemplateDeductionInfo Info(Context, Loc); 3047 if (::DeduceTemplateArguments(*this, &TemplateParams, 3048 FuncParam, InitType, Info, Deduced, 3049 TDF)) 3050 return false; 3051 3052 QualType DeducedType = Deduced[0].getAsType(); 3053 if (DeducedType.isNull()) 3054 return false; 3055 3056 Result = SubstituteAutoTransform(*this, DeducedType).TransformType(Type); 3057 return true; 3058} 3059 3060static void 3061MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 3062 bool OnlyDeduced, 3063 unsigned Level, 3064 llvm::SmallVectorImpl<bool> &Deduced); 3065 3066/// \brief If this is a non-static member function, 3067static void MaybeAddImplicitObjectParameterType(ASTContext &Context, 3068 CXXMethodDecl *Method, 3069 llvm::SmallVectorImpl<QualType> &ArgTypes) { 3070 if (Method->isStatic()) 3071 return; 3072 3073 // C++ [over.match.funcs]p4: 3074 // 3075 // For non-static member functions, the type of the implicit 3076 // object parameter is 3077 // - "lvalue reference to cv X" for functions declared without a 3078 // ref-qualifier or with the & ref-qualifier 3079 // - "rvalue reference to cv X" for functions declared with the 3080 // && ref-qualifier 3081 // 3082 // FIXME: We don't have ref-qualifiers yet, so we don't do that part. 3083 QualType ArgTy = Context.getTypeDeclType(Method->getParent()); 3084 ArgTy = Context.getQualifiedType(ArgTy, 3085 Qualifiers::fromCVRMask(Method->getTypeQualifiers())); 3086 ArgTy = Context.getLValueReferenceType(ArgTy); 3087 ArgTypes.push_back(ArgTy); 3088} 3089 3090/// \brief Determine whether the function template \p FT1 is at least as 3091/// specialized as \p FT2. 3092static bool isAtLeastAsSpecializedAs(Sema &S, 3093 SourceLocation Loc, 3094 FunctionTemplateDecl *FT1, 3095 FunctionTemplateDecl *FT2, 3096 TemplatePartialOrderingContext TPOC, 3097 unsigned NumCallArguments, 3098 llvm::SmallVectorImpl<RefParamPartialOrderingComparison> *RefParamComparisons) { 3099 FunctionDecl *FD1 = FT1->getTemplatedDecl(); 3100 FunctionDecl *FD2 = FT2->getTemplatedDecl(); 3101 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 3102 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 3103 3104 assert(Proto1 && Proto2 && "Function templates must have prototypes"); 3105 TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 3106 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 3107 Deduced.resize(TemplateParams->size()); 3108 3109 // C++0x [temp.deduct.partial]p3: 3110 // The types used to determine the ordering depend on the context in which 3111 // the partial ordering is done: 3112 TemplateDeductionInfo Info(S.Context, Loc); 3113 CXXMethodDecl *Method1 = 0; 3114 CXXMethodDecl *Method2 = 0; 3115 bool IsNonStatic2 = false; 3116 bool IsNonStatic1 = false; 3117 unsigned Skip2 = 0; 3118 switch (TPOC) { 3119 case TPOC_Call: { 3120 // - In the context of a function call, the function parameter types are 3121 // used. 3122 Method1 = dyn_cast<CXXMethodDecl>(FD1); 3123 Method2 = dyn_cast<CXXMethodDecl>(FD2); 3124 IsNonStatic1 = Method1 && !Method1->isStatic(); 3125 IsNonStatic2 = Method2 && !Method2->isStatic(); 3126 3127 // C++0x [temp.func.order]p3: 3128 // [...] If only one of the function templates is a non-static 3129 // member, that function template is considered to have a new 3130 // first parameter inserted in its function parameter list. The 3131 // new parameter is of type "reference to cv A," where cv are 3132 // the cv-qualifiers of the function template (if any) and A is 3133 // the class of which the function template is a member. 3134 // 3135 // C++98/03 doesn't have this provision, so instead we drop the 3136 // first argument of the free function or static member, which 3137 // seems to match existing practice. 3138 llvm::SmallVector<QualType, 4> Args1; 3139 unsigned Skip1 = !S.getLangOptions().CPlusPlus0x && 3140 IsNonStatic2 && !IsNonStatic1; 3141 if (S.getLangOptions().CPlusPlus0x && IsNonStatic1 && !IsNonStatic2) 3142 MaybeAddImplicitObjectParameterType(S.Context, Method1, Args1); 3143 Args1.insert(Args1.end(), 3144 Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end()); 3145 3146 llvm::SmallVector<QualType, 4> Args2; 3147 Skip2 = !S.getLangOptions().CPlusPlus0x && 3148 IsNonStatic1 && !IsNonStatic2; 3149 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1) 3150 MaybeAddImplicitObjectParameterType(S.Context, Method2, Args2); 3151 Args2.insert(Args2.end(), 3152 Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end()); 3153 3154 // C++ [temp.func.order]p5: 3155 // The presence of unused ellipsis and default arguments has no effect on 3156 // the partial ordering of function templates. 3157 if (Args1.size() > NumCallArguments) 3158 Args1.resize(NumCallArguments); 3159 if (Args2.size() > NumCallArguments) 3160 Args2.resize(NumCallArguments); 3161 if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(), 3162 Args1.data(), Args1.size(), Info, Deduced, 3163 TDF_None, /*PartialOrdering=*/true, 3164 RefParamComparisons)) 3165 return false; 3166 3167 break; 3168 } 3169 3170 case TPOC_Conversion: 3171 // - In the context of a call to a conversion operator, the return types 3172 // of the conversion function templates are used. 3173 if (DeduceTemplateArguments(S, TemplateParams, Proto2->getResultType(), 3174 Proto1->getResultType(), Info, Deduced, 3175 TDF_None, /*PartialOrdering=*/true, 3176 RefParamComparisons)) 3177 return false; 3178 break; 3179 3180 case TPOC_Other: 3181 // - In other contexts (14.6.6.2) the function template's function type 3182 // is used. 3183 // FIXME: Don't we actually want to perform the adjustments on the parameter 3184 // types? 3185 if (DeduceTemplateArguments(S, TemplateParams, FD2->getType(), 3186 FD1->getType(), Info, Deduced, TDF_None, 3187 /*PartialOrdering=*/true, RefParamComparisons)) 3188 return false; 3189 break; 3190 } 3191 3192 // C++0x [temp.deduct.partial]p11: 3193 // In most cases, all template parameters must have values in order for 3194 // deduction to succeed, but for partial ordering purposes a template 3195 // parameter may remain without a value provided it is not used in the 3196 // types being used for partial ordering. [ Note: a template parameter used 3197 // in a non-deduced context is considered used. -end note] 3198 unsigned ArgIdx = 0, NumArgs = Deduced.size(); 3199 for (; ArgIdx != NumArgs; ++ArgIdx) 3200 if (Deduced[ArgIdx].isNull()) 3201 break; 3202 3203 if (ArgIdx == NumArgs) { 3204 // All template arguments were deduced. FT1 is at least as specialized 3205 // as FT2. 3206 return true; 3207 } 3208 3209 // Figure out which template parameters were used. 3210 llvm::SmallVector<bool, 4> UsedParameters; 3211 UsedParameters.resize(TemplateParams->size()); 3212 switch (TPOC) { 3213 case TPOC_Call: { 3214 unsigned NumParams = std::min(NumCallArguments, 3215 std::min(Proto1->getNumArgs(), 3216 Proto2->getNumArgs())); 3217 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1) 3218 ::MarkUsedTemplateParameters(S, Method2->getThisType(S.Context), false, 3219 TemplateParams->getDepth(), UsedParameters); 3220 for (unsigned I = Skip2; I < NumParams; ++I) 3221 ::MarkUsedTemplateParameters(S, Proto2->getArgType(I), false, 3222 TemplateParams->getDepth(), 3223 UsedParameters); 3224 break; 3225 } 3226 3227 case TPOC_Conversion: 3228 ::MarkUsedTemplateParameters(S, Proto2->getResultType(), false, 3229 TemplateParams->getDepth(), 3230 UsedParameters); 3231 break; 3232 3233 case TPOC_Other: 3234 ::MarkUsedTemplateParameters(S, FD2->getType(), false, 3235 TemplateParams->getDepth(), 3236 UsedParameters); 3237 break; 3238 } 3239 3240 for (; ArgIdx != NumArgs; ++ArgIdx) 3241 // If this argument had no value deduced but was used in one of the types 3242 // used for partial ordering, then deduction fails. 3243 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 3244 return false; 3245 3246 return true; 3247} 3248 3249/// \brief Determine whether this a function template whose parameter-type-list 3250/// ends with a function parameter pack. 3251static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) { 3252 FunctionDecl *Function = FunTmpl->getTemplatedDecl(); 3253 unsigned NumParams = Function->getNumParams(); 3254 if (NumParams == 0) 3255 return false; 3256 3257 ParmVarDecl *Last = Function->getParamDecl(NumParams - 1); 3258 if (!Last->isParameterPack()) 3259 return false; 3260 3261 // Make sure that no previous parameter is a parameter pack. 3262 while (--NumParams > 0) { 3263 if (Function->getParamDecl(NumParams - 1)->isParameterPack()) 3264 return false; 3265 } 3266 3267 return true; 3268} 3269 3270/// \brief Returns the more specialized function template according 3271/// to the rules of function template partial ordering (C++ [temp.func.order]). 3272/// 3273/// \param FT1 the first function template 3274/// 3275/// \param FT2 the second function template 3276/// 3277/// \param TPOC the context in which we are performing partial ordering of 3278/// function templates. 3279/// 3280/// \param NumCallArguments The number of arguments in a call, used only 3281/// when \c TPOC is \c TPOC_Call. 3282/// 3283/// \returns the more specialized function template. If neither 3284/// template is more specialized, returns NULL. 3285FunctionTemplateDecl * 3286Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, 3287 FunctionTemplateDecl *FT2, 3288 SourceLocation Loc, 3289 TemplatePartialOrderingContext TPOC, 3290 unsigned NumCallArguments) { 3291 llvm::SmallVector<RefParamPartialOrderingComparison, 4> RefParamComparisons; 3292 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC, 3293 NumCallArguments, 0); 3294 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC, 3295 NumCallArguments, 3296 &RefParamComparisons); 3297 3298 if (Better1 != Better2) // We have a clear winner 3299 return Better1? FT1 : FT2; 3300 3301 if (!Better1 && !Better2) // Neither is better than the other 3302 return 0; 3303 3304 // C++0x [temp.deduct.partial]p10: 3305 // If for each type being considered a given template is at least as 3306 // specialized for all types and more specialized for some set of types and 3307 // the other template is not more specialized for any types or is not at 3308 // least as specialized for any types, then the given template is more 3309 // specialized than the other template. Otherwise, neither template is more 3310 // specialized than the other. 3311 Better1 = false; 3312 Better2 = false; 3313 for (unsigned I = 0, N = RefParamComparisons.size(); I != N; ++I) { 3314 // C++0x [temp.deduct.partial]p9: 3315 // If, for a given type, deduction succeeds in both directions (i.e., the 3316 // types are identical after the transformations above) and both P and A 3317 // were reference types (before being replaced with the type referred to 3318 // above): 3319 3320 // -- if the type from the argument template was an lvalue reference 3321 // and the type from the parameter template was not, the argument 3322 // type is considered to be more specialized than the other; 3323 // otherwise, 3324 if (!RefParamComparisons[I].ArgIsRvalueRef && 3325 RefParamComparisons[I].ParamIsRvalueRef) { 3326 Better2 = true; 3327 if (Better1) 3328 return 0; 3329 continue; 3330 } else if (!RefParamComparisons[I].ParamIsRvalueRef && 3331 RefParamComparisons[I].ArgIsRvalueRef) { 3332 Better1 = true; 3333 if (Better2) 3334 return 0; 3335 continue; 3336 } 3337 3338 // -- if the type from the argument template is more cv-qualified than 3339 // the type from the parameter template (as described above), the 3340 // argument type is considered to be more specialized than the 3341 // other; otherwise, 3342 switch (RefParamComparisons[I].Qualifiers) { 3343 case NeitherMoreQualified: 3344 break; 3345 3346 case ParamMoreQualified: 3347 Better1 = true; 3348 if (Better2) 3349 return 0; 3350 continue; 3351 3352 case ArgMoreQualified: 3353 Better2 = true; 3354 if (Better1) 3355 return 0; 3356 continue; 3357 } 3358 3359 // -- neither type is more specialized than the other. 3360 } 3361 3362 assert(!(Better1 && Better2) && "Should have broken out in the loop above"); 3363 if (Better1) 3364 return FT1; 3365 else if (Better2) 3366 return FT2; 3367 3368 // FIXME: This mimics what GCC implements, but doesn't match up with the 3369 // proposed resolution for core issue 692. This area needs to be sorted out, 3370 // but for now we attempt to maintain compatibility. 3371 bool Variadic1 = isVariadicFunctionTemplate(FT1); 3372 bool Variadic2 = isVariadicFunctionTemplate(FT2); 3373 if (Variadic1 != Variadic2) 3374 return Variadic1? FT2 : FT1; 3375 3376 return 0; 3377} 3378 3379/// \brief Determine if the two templates are equivalent. 3380static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) { 3381 if (T1 == T2) 3382 return true; 3383 3384 if (!T1 || !T2) 3385 return false; 3386 3387 return T1->getCanonicalDecl() == T2->getCanonicalDecl(); 3388} 3389 3390/// \brief Retrieve the most specialized of the given function template 3391/// specializations. 3392/// 3393/// \param SpecBegin the start iterator of the function template 3394/// specializations that we will be comparing. 3395/// 3396/// \param SpecEnd the end iterator of the function template 3397/// specializations, paired with \p SpecBegin. 3398/// 3399/// \param TPOC the partial ordering context to use to compare the function 3400/// template specializations. 3401/// 3402/// \param NumCallArguments The number of arguments in a call, used only 3403/// when \c TPOC is \c TPOC_Call. 3404/// 3405/// \param Loc the location where the ambiguity or no-specializations 3406/// diagnostic should occur. 3407/// 3408/// \param NoneDiag partial diagnostic used to diagnose cases where there are 3409/// no matching candidates. 3410/// 3411/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one 3412/// occurs. 3413/// 3414/// \param CandidateDiag partial diagnostic used for each function template 3415/// specialization that is a candidate in the ambiguous ordering. One parameter 3416/// in this diagnostic should be unbound, which will correspond to the string 3417/// describing the template arguments for the function template specialization. 3418/// 3419/// \param Index if non-NULL and the result of this function is non-nULL, 3420/// receives the index corresponding to the resulting function template 3421/// specialization. 3422/// 3423/// \returns the most specialized function template specialization, if 3424/// found. Otherwise, returns SpecEnd. 3425/// 3426/// \todo FIXME: Consider passing in the "also-ran" candidates that failed 3427/// template argument deduction. 3428UnresolvedSetIterator 3429Sema::getMostSpecialized(UnresolvedSetIterator SpecBegin, 3430 UnresolvedSetIterator SpecEnd, 3431 TemplatePartialOrderingContext TPOC, 3432 unsigned NumCallArguments, 3433 SourceLocation Loc, 3434 const PartialDiagnostic &NoneDiag, 3435 const PartialDiagnostic &AmbigDiag, 3436 const PartialDiagnostic &CandidateDiag, 3437 bool Complain) { 3438 if (SpecBegin == SpecEnd) { 3439 if (Complain) 3440 Diag(Loc, NoneDiag); 3441 return SpecEnd; 3442 } 3443 3444 if (SpecBegin + 1 == SpecEnd) 3445 return SpecBegin; 3446 3447 // Find the function template that is better than all of the templates it 3448 // has been compared to. 3449 UnresolvedSetIterator Best = SpecBegin; 3450 FunctionTemplateDecl *BestTemplate 3451 = cast<FunctionDecl>(*Best)->getPrimaryTemplate(); 3452 assert(BestTemplate && "Not a function template specialization?"); 3453 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) { 3454 FunctionTemplateDecl *Challenger 3455 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 3456 assert(Challenger && "Not a function template specialization?"); 3457 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 3458 Loc, TPOC, NumCallArguments), 3459 Challenger)) { 3460 Best = I; 3461 BestTemplate = Challenger; 3462 } 3463 } 3464 3465 // Make sure that the "best" function template is more specialized than all 3466 // of the others. 3467 bool Ambiguous = false; 3468 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 3469 FunctionTemplateDecl *Challenger 3470 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 3471 if (I != Best && 3472 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 3473 Loc, TPOC, NumCallArguments), 3474 BestTemplate)) { 3475 Ambiguous = true; 3476 break; 3477 } 3478 } 3479 3480 if (!Ambiguous) { 3481 // We found an answer. Return it. 3482 return Best; 3483 } 3484 3485 // Diagnose the ambiguity. 3486 if (Complain) 3487 Diag(Loc, AmbigDiag); 3488 3489 if (Complain) 3490 // FIXME: Can we order the candidates in some sane way? 3491 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) 3492 Diag((*I)->getLocation(), CandidateDiag) 3493 << getTemplateArgumentBindingsText( 3494 cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(), 3495 *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs()); 3496 3497 return SpecEnd; 3498} 3499 3500/// \brief Returns the more specialized class template partial specialization 3501/// according to the rules of partial ordering of class template partial 3502/// specializations (C++ [temp.class.order]). 3503/// 3504/// \param PS1 the first class template partial specialization 3505/// 3506/// \param PS2 the second class template partial specialization 3507/// 3508/// \returns the more specialized class template partial specialization. If 3509/// neither partial specialization is more specialized, returns NULL. 3510ClassTemplatePartialSpecializationDecl * 3511Sema::getMoreSpecializedPartialSpecialization( 3512 ClassTemplatePartialSpecializationDecl *PS1, 3513 ClassTemplatePartialSpecializationDecl *PS2, 3514 SourceLocation Loc) { 3515 // C++ [temp.class.order]p1: 3516 // For two class template partial specializations, the first is at least as 3517 // specialized as the second if, given the following rewrite to two 3518 // function templates, the first function template is at least as 3519 // specialized as the second according to the ordering rules for function 3520 // templates (14.6.6.2): 3521 // - the first function template has the same template parameters as the 3522 // first partial specialization and has a single function parameter 3523 // whose type is a class template specialization with the template 3524 // arguments of the first partial specialization, and 3525 // - the second function template has the same template parameters as the 3526 // second partial specialization and has a single function parameter 3527 // whose type is a class template specialization with the template 3528 // arguments of the second partial specialization. 3529 // 3530 // Rather than synthesize function templates, we merely perform the 3531 // equivalent partial ordering by performing deduction directly on 3532 // the template arguments of the class template partial 3533 // specializations. This computation is slightly simpler than the 3534 // general problem of function template partial ordering, because 3535 // class template partial specializations are more constrained. We 3536 // know that every template parameter is deducible from the class 3537 // template partial specialization's template arguments, for 3538 // example. 3539 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 3540 TemplateDeductionInfo Info(Context, Loc); 3541 3542 QualType PT1 = PS1->getInjectedSpecializationType(); 3543 QualType PT2 = PS2->getInjectedSpecializationType(); 3544 3545 // Determine whether PS1 is at least as specialized as PS2 3546 Deduced.resize(PS2->getTemplateParameters()->size()); 3547 bool Better1 = !::DeduceTemplateArguments(*this, PS2->getTemplateParameters(), 3548 PT2, PT1, Info, Deduced, TDF_None, 3549 /*PartialOrdering=*/true, 3550 /*RefParamComparisons=*/0); 3551 if (Better1) { 3552 InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2, 3553 Deduced.data(), Deduced.size(), Info); 3554 Better1 = !::FinishTemplateArgumentDeduction(*this, PS2, 3555 PS1->getTemplateArgs(), 3556 Deduced, Info); 3557 } 3558 3559 // Determine whether PS2 is at least as specialized as PS1 3560 Deduced.clear(); 3561 Deduced.resize(PS1->getTemplateParameters()->size()); 3562 bool Better2 = !::DeduceTemplateArguments(*this, PS1->getTemplateParameters(), 3563 PT1, PT2, Info, Deduced, TDF_None, 3564 /*PartialOrdering=*/true, 3565 /*RefParamComparisons=*/0); 3566 if (Better2) { 3567 InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1, 3568 Deduced.data(), Deduced.size(), Info); 3569 Better2 = !::FinishTemplateArgumentDeduction(*this, PS1, 3570 PS2->getTemplateArgs(), 3571 Deduced, Info); 3572 } 3573 3574 if (Better1 == Better2) 3575 return 0; 3576 3577 return Better1? PS1 : PS2; 3578} 3579 3580static void 3581MarkUsedTemplateParameters(Sema &SemaRef, 3582 const TemplateArgument &TemplateArg, 3583 bool OnlyDeduced, 3584 unsigned Depth, 3585 llvm::SmallVectorImpl<bool> &Used); 3586 3587/// \brief Mark the template parameters that are used by the given 3588/// expression. 3589static void 3590MarkUsedTemplateParameters(Sema &SemaRef, 3591 const Expr *E, 3592 bool OnlyDeduced, 3593 unsigned Depth, 3594 llvm::SmallVectorImpl<bool> &Used) { 3595 // We can deduce from a pack expansion. 3596 if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E)) 3597 E = Expansion->getPattern(); 3598 3599 // Skip through any implicit casts we added while type-checking. 3600 while (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E)) 3601 E = ICE->getSubExpr(); 3602 3603 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to 3604 // find other occurrences of template parameters. 3605 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E); 3606 if (!DRE) 3607 return; 3608 3609 const NonTypeTemplateParmDecl *NTTP 3610 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 3611 if (!NTTP) 3612 return; 3613 3614 if (NTTP->getDepth() == Depth) 3615 Used[NTTP->getIndex()] = true; 3616} 3617 3618/// \brief Mark the template parameters that are used by the given 3619/// nested name specifier. 3620static void 3621MarkUsedTemplateParameters(Sema &SemaRef, 3622 NestedNameSpecifier *NNS, 3623 bool OnlyDeduced, 3624 unsigned Depth, 3625 llvm::SmallVectorImpl<bool> &Used) { 3626 if (!NNS) 3627 return; 3628 3629 MarkUsedTemplateParameters(SemaRef, NNS->getPrefix(), OnlyDeduced, Depth, 3630 Used); 3631 MarkUsedTemplateParameters(SemaRef, QualType(NNS->getAsType(), 0), 3632 OnlyDeduced, Depth, Used); 3633} 3634 3635/// \brief Mark the template parameters that are used by the given 3636/// template name. 3637static void 3638MarkUsedTemplateParameters(Sema &SemaRef, 3639 TemplateName Name, 3640 bool OnlyDeduced, 3641 unsigned Depth, 3642 llvm::SmallVectorImpl<bool> &Used) { 3643 if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 3644 if (TemplateTemplateParmDecl *TTP 3645 = dyn_cast<TemplateTemplateParmDecl>(Template)) { 3646 if (TTP->getDepth() == Depth) 3647 Used[TTP->getIndex()] = true; 3648 } 3649 return; 3650 } 3651 3652 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) 3653 MarkUsedTemplateParameters(SemaRef, QTN->getQualifier(), OnlyDeduced, 3654 Depth, Used); 3655 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 3656 MarkUsedTemplateParameters(SemaRef, DTN->getQualifier(), OnlyDeduced, 3657 Depth, Used); 3658} 3659 3660/// \brief Mark the template parameters that are used by the given 3661/// type. 3662static void 3663MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 3664 bool OnlyDeduced, 3665 unsigned Depth, 3666 llvm::SmallVectorImpl<bool> &Used) { 3667 if (T.isNull()) 3668 return; 3669 3670 // Non-dependent types have nothing deducible 3671 if (!T->isDependentType()) 3672 return; 3673 3674 T = SemaRef.Context.getCanonicalType(T); 3675 switch (T->getTypeClass()) { 3676 case Type::Pointer: 3677 MarkUsedTemplateParameters(SemaRef, 3678 cast<PointerType>(T)->getPointeeType(), 3679 OnlyDeduced, 3680 Depth, 3681 Used); 3682 break; 3683 3684 case Type::BlockPointer: 3685 MarkUsedTemplateParameters(SemaRef, 3686 cast<BlockPointerType>(T)->getPointeeType(), 3687 OnlyDeduced, 3688 Depth, 3689 Used); 3690 break; 3691 3692 case Type::LValueReference: 3693 case Type::RValueReference: 3694 MarkUsedTemplateParameters(SemaRef, 3695 cast<ReferenceType>(T)->getPointeeType(), 3696 OnlyDeduced, 3697 Depth, 3698 Used); 3699 break; 3700 3701 case Type::MemberPointer: { 3702 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 3703 MarkUsedTemplateParameters(SemaRef, MemPtr->getPointeeType(), OnlyDeduced, 3704 Depth, Used); 3705 MarkUsedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0), 3706 OnlyDeduced, Depth, Used); 3707 break; 3708 } 3709 3710 case Type::DependentSizedArray: 3711 MarkUsedTemplateParameters(SemaRef, 3712 cast<DependentSizedArrayType>(T)->getSizeExpr(), 3713 OnlyDeduced, Depth, Used); 3714 // Fall through to check the element type 3715 3716 case Type::ConstantArray: 3717 case Type::IncompleteArray: 3718 MarkUsedTemplateParameters(SemaRef, 3719 cast<ArrayType>(T)->getElementType(), 3720 OnlyDeduced, Depth, Used); 3721 break; 3722 3723 case Type::Vector: 3724 case Type::ExtVector: 3725 MarkUsedTemplateParameters(SemaRef, 3726 cast<VectorType>(T)->getElementType(), 3727 OnlyDeduced, Depth, Used); 3728 break; 3729 3730 case Type::DependentSizedExtVector: { 3731 const DependentSizedExtVectorType *VecType 3732 = cast<DependentSizedExtVectorType>(T); 3733 MarkUsedTemplateParameters(SemaRef, VecType->getElementType(), OnlyDeduced, 3734 Depth, Used); 3735 MarkUsedTemplateParameters(SemaRef, VecType->getSizeExpr(), OnlyDeduced, 3736 Depth, Used); 3737 break; 3738 } 3739 3740 case Type::FunctionProto: { 3741 const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 3742 MarkUsedTemplateParameters(SemaRef, Proto->getResultType(), OnlyDeduced, 3743 Depth, Used); 3744 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I) 3745 MarkUsedTemplateParameters(SemaRef, Proto->getArgType(I), OnlyDeduced, 3746 Depth, Used); 3747 break; 3748 } 3749 3750 case Type::TemplateTypeParm: { 3751 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T); 3752 if (TTP->getDepth() == Depth) 3753 Used[TTP->getIndex()] = true; 3754 break; 3755 } 3756 3757 case Type::SubstTemplateTypeParmPack: { 3758 const SubstTemplateTypeParmPackType *Subst 3759 = cast<SubstTemplateTypeParmPackType>(T); 3760 MarkUsedTemplateParameters(SemaRef, 3761 QualType(Subst->getReplacedParameter(), 0), 3762 OnlyDeduced, Depth, Used); 3763 MarkUsedTemplateParameters(SemaRef, Subst->getArgumentPack(), 3764 OnlyDeduced, Depth, Used); 3765 break; 3766 } 3767 3768 case Type::InjectedClassName: 3769 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType(); 3770 // fall through 3771 3772 case Type::TemplateSpecialization: { 3773 const TemplateSpecializationType *Spec 3774 = cast<TemplateSpecializationType>(T); 3775 MarkUsedTemplateParameters(SemaRef, Spec->getTemplateName(), OnlyDeduced, 3776 Depth, Used); 3777 3778 // C++0x [temp.deduct.type]p9: 3779 // If the template argument list of P contains a pack expansion that is not 3780 // the last template argument, the entire template argument list is a 3781 // non-deduced context. 3782 if (OnlyDeduced && 3783 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 3784 break; 3785 3786 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 3787 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 3788 Used); 3789 break; 3790 } 3791 3792 case Type::Complex: 3793 if (!OnlyDeduced) 3794 MarkUsedTemplateParameters(SemaRef, 3795 cast<ComplexType>(T)->getElementType(), 3796 OnlyDeduced, Depth, Used); 3797 break; 3798 3799 case Type::DependentName: 3800 if (!OnlyDeduced) 3801 MarkUsedTemplateParameters(SemaRef, 3802 cast<DependentNameType>(T)->getQualifier(), 3803 OnlyDeduced, Depth, Used); 3804 break; 3805 3806 case Type::DependentTemplateSpecialization: { 3807 const DependentTemplateSpecializationType *Spec 3808 = cast<DependentTemplateSpecializationType>(T); 3809 if (!OnlyDeduced) 3810 MarkUsedTemplateParameters(SemaRef, Spec->getQualifier(), 3811 OnlyDeduced, Depth, Used); 3812 3813 // C++0x [temp.deduct.type]p9: 3814 // If the template argument list of P contains a pack expansion that is not 3815 // the last template argument, the entire template argument list is a 3816 // non-deduced context. 3817 if (OnlyDeduced && 3818 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 3819 break; 3820 3821 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 3822 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 3823 Used); 3824 break; 3825 } 3826 3827 case Type::TypeOf: 3828 if (!OnlyDeduced) 3829 MarkUsedTemplateParameters(SemaRef, 3830 cast<TypeOfType>(T)->getUnderlyingType(), 3831 OnlyDeduced, Depth, Used); 3832 break; 3833 3834 case Type::TypeOfExpr: 3835 if (!OnlyDeduced) 3836 MarkUsedTemplateParameters(SemaRef, 3837 cast<TypeOfExprType>(T)->getUnderlyingExpr(), 3838 OnlyDeduced, Depth, Used); 3839 break; 3840 3841 case Type::Decltype: 3842 if (!OnlyDeduced) 3843 MarkUsedTemplateParameters(SemaRef, 3844 cast<DecltypeType>(T)->getUnderlyingExpr(), 3845 OnlyDeduced, Depth, Used); 3846 break; 3847 3848 case Type::PackExpansion: 3849 MarkUsedTemplateParameters(SemaRef, 3850 cast<PackExpansionType>(T)->getPattern(), 3851 OnlyDeduced, Depth, Used); 3852 break; 3853 3854 case Type::Auto: 3855 MarkUsedTemplateParameters(SemaRef, 3856 cast<AutoType>(T)->getDeducedType(), 3857 OnlyDeduced, Depth, Used); 3858 3859 // None of these types have any template parameters in them. 3860 case Type::Builtin: 3861 case Type::VariableArray: 3862 case Type::FunctionNoProto: 3863 case Type::Record: 3864 case Type::Enum: 3865 case Type::ObjCInterface: 3866 case Type::ObjCObject: 3867 case Type::ObjCObjectPointer: 3868 case Type::UnresolvedUsing: 3869#define TYPE(Class, Base) 3870#define ABSTRACT_TYPE(Class, Base) 3871#define DEPENDENT_TYPE(Class, Base) 3872#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 3873#include "clang/AST/TypeNodes.def" 3874 break; 3875 } 3876} 3877 3878/// \brief Mark the template parameters that are used by this 3879/// template argument. 3880static void 3881MarkUsedTemplateParameters(Sema &SemaRef, 3882 const TemplateArgument &TemplateArg, 3883 bool OnlyDeduced, 3884 unsigned Depth, 3885 llvm::SmallVectorImpl<bool> &Used) { 3886 switch (TemplateArg.getKind()) { 3887 case TemplateArgument::Null: 3888 case TemplateArgument::Integral: 3889 case TemplateArgument::Declaration: 3890 break; 3891 3892 case TemplateArgument::Type: 3893 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsType(), OnlyDeduced, 3894 Depth, Used); 3895 break; 3896 3897 case TemplateArgument::Template: 3898 case TemplateArgument::TemplateExpansion: 3899 MarkUsedTemplateParameters(SemaRef, 3900 TemplateArg.getAsTemplateOrTemplatePattern(), 3901 OnlyDeduced, Depth, Used); 3902 break; 3903 3904 case TemplateArgument::Expression: 3905 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsExpr(), OnlyDeduced, 3906 Depth, Used); 3907 break; 3908 3909 case TemplateArgument::Pack: 3910 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(), 3911 PEnd = TemplateArg.pack_end(); 3912 P != PEnd; ++P) 3913 MarkUsedTemplateParameters(SemaRef, *P, OnlyDeduced, Depth, Used); 3914 break; 3915 } 3916} 3917 3918/// \brief Mark the template parameters can be deduced by the given 3919/// template argument list. 3920/// 3921/// \param TemplateArgs the template argument list from which template 3922/// parameters will be deduced. 3923/// 3924/// \param Deduced a bit vector whose elements will be set to \c true 3925/// to indicate when the corresponding template parameter will be 3926/// deduced. 3927void 3928Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 3929 bool OnlyDeduced, unsigned Depth, 3930 llvm::SmallVectorImpl<bool> &Used) { 3931 // C++0x [temp.deduct.type]p9: 3932 // If the template argument list of P contains a pack expansion that is not 3933 // the last template argument, the entire template argument list is a 3934 // non-deduced context. 3935 if (OnlyDeduced && 3936 hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size())) 3937 return; 3938 3939 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 3940 ::MarkUsedTemplateParameters(*this, TemplateArgs[I], OnlyDeduced, 3941 Depth, Used); 3942} 3943 3944/// \brief Marks all of the template parameters that will be deduced by a 3945/// call to the given function template. 3946void 3947Sema::MarkDeducedTemplateParameters(FunctionTemplateDecl *FunctionTemplate, 3948 llvm::SmallVectorImpl<bool> &Deduced) { 3949 TemplateParameterList *TemplateParams 3950 = FunctionTemplate->getTemplateParameters(); 3951 Deduced.clear(); 3952 Deduced.resize(TemplateParams->size()); 3953 3954 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 3955 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 3956 ::MarkUsedTemplateParameters(*this, Function->getParamDecl(I)->getType(), 3957 true, TemplateParams->getDepth(), Deduced); 3958} 3959