SemaTemplateDeduction.cpp revision 34b41d939a1328f484511c6002ba2456db879a29
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 return TemplateArgumentLoc(Arg, SourceRange(), Loc); 1733 1734 case TemplateArgument::TemplateExpansion: 1735 return TemplateArgumentLoc(Arg, SourceRange(), Loc, Loc); 1736 1737 case TemplateArgument::Expression: 1738 return TemplateArgumentLoc(Arg, Arg.getAsExpr()); 1739 1740 case TemplateArgument::Pack: 1741 return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo()); 1742 } 1743 1744 return TemplateArgumentLoc(); 1745} 1746 1747 1748/// \brief Convert the given deduced template argument and add it to the set of 1749/// fully-converted template arguments. 1750static bool ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param, 1751 DeducedTemplateArgument Arg, 1752 NamedDecl *Template, 1753 QualType NTTPType, 1754 unsigned ArgumentPackIndex, 1755 TemplateDeductionInfo &Info, 1756 bool InFunctionTemplate, 1757 llvm::SmallVectorImpl<TemplateArgument> &Output) { 1758 if (Arg.getKind() == TemplateArgument::Pack) { 1759 // This is a template argument pack, so check each of its arguments against 1760 // the template parameter. 1761 llvm::SmallVector<TemplateArgument, 2> PackedArgsBuilder; 1762 for (TemplateArgument::pack_iterator PA = Arg.pack_begin(), 1763 PAEnd = Arg.pack_end(); 1764 PA != PAEnd; ++PA) { 1765 // When converting the deduced template argument, append it to the 1766 // general output list. We need to do this so that the template argument 1767 // checking logic has all of the prior template arguments available. 1768 DeducedTemplateArgument InnerArg(*PA); 1769 InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound()); 1770 if (ConvertDeducedTemplateArgument(S, Param, InnerArg, Template, 1771 NTTPType, PackedArgsBuilder.size(), 1772 Info, InFunctionTemplate, Output)) 1773 return true; 1774 1775 // Move the converted template argument into our argument pack. 1776 PackedArgsBuilder.push_back(Output.back()); 1777 Output.pop_back(); 1778 } 1779 1780 // Create the resulting argument pack. 1781 Output.push_back(TemplateArgument::CreatePackCopy(S.Context, 1782 PackedArgsBuilder.data(), 1783 PackedArgsBuilder.size())); 1784 return false; 1785 } 1786 1787 // Convert the deduced template argument into a template 1788 // argument that we can check, almost as if the user had written 1789 // the template argument explicitly. 1790 TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType, 1791 Info.getLocation()); 1792 1793 // Check the template argument, converting it as necessary. 1794 return S.CheckTemplateArgument(Param, ArgLoc, 1795 Template, 1796 Template->getLocation(), 1797 Template->getSourceRange().getEnd(), 1798 ArgumentPackIndex, 1799 Output, 1800 InFunctionTemplate 1801 ? (Arg.wasDeducedFromArrayBound() 1802 ? Sema::CTAK_DeducedFromArrayBound 1803 : Sema::CTAK_Deduced) 1804 : Sema::CTAK_Specified); 1805} 1806 1807/// Complete template argument deduction for a class template partial 1808/// specialization. 1809static Sema::TemplateDeductionResult 1810FinishTemplateArgumentDeduction(Sema &S, 1811 ClassTemplatePartialSpecializationDecl *Partial, 1812 const TemplateArgumentList &TemplateArgs, 1813 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1814 TemplateDeductionInfo &Info) { 1815 // Trap errors. 1816 Sema::SFINAETrap Trap(S); 1817 1818 Sema::ContextRAII SavedContext(S, Partial); 1819 1820 // C++ [temp.deduct.type]p2: 1821 // [...] or if any template argument remains neither deduced nor 1822 // explicitly specified, template argument deduction fails. 1823 llvm::SmallVector<TemplateArgument, 4> Builder; 1824 TemplateParameterList *PartialParams = Partial->getTemplateParameters(); 1825 for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) { 1826 NamedDecl *Param = PartialParams->getParam(I); 1827 if (Deduced[I].isNull()) { 1828 Info.Param = makeTemplateParameter(Param); 1829 return Sema::TDK_Incomplete; 1830 } 1831 1832 // We have deduced this argument, so it still needs to be 1833 // checked and converted. 1834 1835 // First, for a non-type template parameter type that is 1836 // initialized by a declaration, we need the type of the 1837 // corresponding non-type template parameter. 1838 QualType NTTPType; 1839 if (NonTypeTemplateParmDecl *NTTP 1840 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 1841 NTTPType = NTTP->getType(); 1842 if (NTTPType->isDependentType()) { 1843 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, 1844 Builder.data(), Builder.size()); 1845 NTTPType = S.SubstType(NTTPType, 1846 MultiLevelTemplateArgumentList(TemplateArgs), 1847 NTTP->getLocation(), 1848 NTTP->getDeclName()); 1849 if (NTTPType.isNull()) { 1850 Info.Param = makeTemplateParameter(Param); 1851 // FIXME: These template arguments are temporary. Free them! 1852 Info.reset(TemplateArgumentList::CreateCopy(S.Context, 1853 Builder.data(), 1854 Builder.size())); 1855 return Sema::TDK_SubstitutionFailure; 1856 } 1857 } 1858 } 1859 1860 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], 1861 Partial, NTTPType, 0, Info, false, 1862 Builder)) { 1863 Info.Param = makeTemplateParameter(Param); 1864 // FIXME: These template arguments are temporary. Free them! 1865 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(), 1866 Builder.size())); 1867 return Sema::TDK_SubstitutionFailure; 1868 } 1869 } 1870 1871 // Form the template argument list from the deduced template arguments. 1872 TemplateArgumentList *DeducedArgumentList 1873 = TemplateArgumentList::CreateCopy(S.Context, Builder.data(), 1874 Builder.size()); 1875 1876 Info.reset(DeducedArgumentList); 1877 1878 // Substitute the deduced template arguments into the template 1879 // arguments of the class template partial specialization, and 1880 // verify that the instantiated template arguments are both valid 1881 // and are equivalent to the template arguments originally provided 1882 // to the class template. 1883 LocalInstantiationScope InstScope(S); 1884 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate(); 1885 const TemplateArgumentLoc *PartialTemplateArgs 1886 = Partial->getTemplateArgsAsWritten(); 1887 1888 // Note that we don't provide the langle and rangle locations. 1889 TemplateArgumentListInfo InstArgs; 1890 1891 if (S.Subst(PartialTemplateArgs, 1892 Partial->getNumTemplateArgsAsWritten(), 1893 InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) { 1894 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx; 1895 if (ParamIdx >= Partial->getTemplateParameters()->size()) 1896 ParamIdx = Partial->getTemplateParameters()->size() - 1; 1897 1898 Decl *Param 1899 = const_cast<NamedDecl *>( 1900 Partial->getTemplateParameters()->getParam(ParamIdx)); 1901 Info.Param = makeTemplateParameter(Param); 1902 Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument(); 1903 return Sema::TDK_SubstitutionFailure; 1904 } 1905 1906 llvm::SmallVector<TemplateArgument, 4> ConvertedInstArgs; 1907 if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(), 1908 InstArgs, false, ConvertedInstArgs)) 1909 return Sema::TDK_SubstitutionFailure; 1910 1911 TemplateParameterList *TemplateParams 1912 = ClassTemplate->getTemplateParameters(); 1913 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) { 1914 TemplateArgument InstArg = ConvertedInstArgs.data()[I]; 1915 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) { 1916 Info.Param = makeTemplateParameter(TemplateParams->getParam(I)); 1917 Info.FirstArg = TemplateArgs[I]; 1918 Info.SecondArg = InstArg; 1919 return Sema::TDK_NonDeducedMismatch; 1920 } 1921 } 1922 1923 if (Trap.hasErrorOccurred()) 1924 return Sema::TDK_SubstitutionFailure; 1925 1926 return Sema::TDK_Success; 1927} 1928 1929/// \brief Perform template argument deduction to determine whether 1930/// the given template arguments match the given class template 1931/// partial specialization per C++ [temp.class.spec.match]. 1932Sema::TemplateDeductionResult 1933Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial, 1934 const TemplateArgumentList &TemplateArgs, 1935 TemplateDeductionInfo &Info) { 1936 // C++ [temp.class.spec.match]p2: 1937 // A partial specialization matches a given actual template 1938 // argument list if the template arguments of the partial 1939 // specialization can be deduced from the actual template argument 1940 // list (14.8.2). 1941 SFINAETrap Trap(*this); 1942 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 1943 Deduced.resize(Partial->getTemplateParameters()->size()); 1944 if (TemplateDeductionResult Result 1945 = ::DeduceTemplateArguments(*this, 1946 Partial->getTemplateParameters(), 1947 Partial->getTemplateArgs(), 1948 TemplateArgs, Info, Deduced)) 1949 return Result; 1950 1951 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial, 1952 Deduced.data(), Deduced.size(), Info); 1953 if (Inst) 1954 return TDK_InstantiationDepth; 1955 1956 if (Trap.hasErrorOccurred()) 1957 return Sema::TDK_SubstitutionFailure; 1958 1959 return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs, 1960 Deduced, Info); 1961} 1962 1963/// \brief Determine whether the given type T is a simple-template-id type. 1964static bool isSimpleTemplateIdType(QualType T) { 1965 if (const TemplateSpecializationType *Spec 1966 = T->getAs<TemplateSpecializationType>()) 1967 return Spec->getTemplateName().getAsTemplateDecl() != 0; 1968 1969 return false; 1970} 1971 1972/// \brief Substitute the explicitly-provided template arguments into the 1973/// given function template according to C++ [temp.arg.explicit]. 1974/// 1975/// \param FunctionTemplate the function template into which the explicit 1976/// template arguments will be substituted. 1977/// 1978/// \param ExplicitTemplateArguments the explicitly-specified template 1979/// arguments. 1980/// 1981/// \param Deduced the deduced template arguments, which will be populated 1982/// with the converted and checked explicit template arguments. 1983/// 1984/// \param ParamTypes will be populated with the instantiated function 1985/// parameters. 1986/// 1987/// \param FunctionType if non-NULL, the result type of the function template 1988/// will also be instantiated and the pointed-to value will be updated with 1989/// the instantiated function type. 1990/// 1991/// \param Info if substitution fails for any reason, this object will be 1992/// populated with more information about the failure. 1993/// 1994/// \returns TDK_Success if substitution was successful, or some failure 1995/// condition. 1996Sema::TemplateDeductionResult 1997Sema::SubstituteExplicitTemplateArguments( 1998 FunctionTemplateDecl *FunctionTemplate, 1999 const TemplateArgumentListInfo &ExplicitTemplateArgs, 2000 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2001 llvm::SmallVectorImpl<QualType> &ParamTypes, 2002 QualType *FunctionType, 2003 TemplateDeductionInfo &Info) { 2004 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2005 TemplateParameterList *TemplateParams 2006 = FunctionTemplate->getTemplateParameters(); 2007 2008 if (ExplicitTemplateArgs.size() == 0) { 2009 // No arguments to substitute; just copy over the parameter types and 2010 // fill in the function type. 2011 for (FunctionDecl::param_iterator P = Function->param_begin(), 2012 PEnd = Function->param_end(); 2013 P != PEnd; 2014 ++P) 2015 ParamTypes.push_back((*P)->getType()); 2016 2017 if (FunctionType) 2018 *FunctionType = Function->getType(); 2019 return TDK_Success; 2020 } 2021 2022 // Substitution of the explicit template arguments into a function template 2023 /// is a SFINAE context. Trap any errors that might occur. 2024 SFINAETrap Trap(*this); 2025 2026 // C++ [temp.arg.explicit]p3: 2027 // Template arguments that are present shall be specified in the 2028 // declaration order of their corresponding template-parameters. The 2029 // template argument list shall not specify more template-arguments than 2030 // there are corresponding template-parameters. 2031 llvm::SmallVector<TemplateArgument, 4> Builder; 2032 2033 // Enter a new template instantiation context where we check the 2034 // explicitly-specified template arguments against this function template, 2035 // and then substitute them into the function parameter types. 2036 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 2037 FunctionTemplate, Deduced.data(), Deduced.size(), 2038 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution, 2039 Info); 2040 if (Inst) 2041 return TDK_InstantiationDepth; 2042 2043 if (CheckTemplateArgumentList(FunctionTemplate, 2044 SourceLocation(), 2045 ExplicitTemplateArgs, 2046 true, 2047 Builder) || Trap.hasErrorOccurred()) { 2048 unsigned Index = Builder.size(); 2049 if (Index >= TemplateParams->size()) 2050 Index = TemplateParams->size() - 1; 2051 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index)); 2052 return TDK_InvalidExplicitArguments; 2053 } 2054 2055 // Form the template argument list from the explicitly-specified 2056 // template arguments. 2057 TemplateArgumentList *ExplicitArgumentList 2058 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size()); 2059 Info.reset(ExplicitArgumentList); 2060 2061 // Template argument deduction and the final substitution should be 2062 // done in the context of the templated declaration. Explicit 2063 // argument substitution, on the other hand, needs to happen in the 2064 // calling context. 2065 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 2066 2067 // If we deduced template arguments for a template parameter pack, 2068 // note that the template argument pack is partially substituted and record 2069 // the explicit template arguments. They'll be used as part of deduction 2070 // for this template parameter pack. 2071 for (unsigned I = 0, N = Builder.size(); I != N; ++I) { 2072 const TemplateArgument &Arg = Builder[I]; 2073 if (Arg.getKind() == TemplateArgument::Pack) { 2074 CurrentInstantiationScope->SetPartiallySubstitutedPack( 2075 TemplateParams->getParam(I), 2076 Arg.pack_begin(), 2077 Arg.pack_size()); 2078 break; 2079 } 2080 } 2081 2082 // Instantiate the types of each of the function parameters given the 2083 // explicitly-specified template arguments. 2084 if (SubstParmTypes(Function->getLocation(), 2085 Function->param_begin(), Function->getNumParams(), 2086 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 2087 ParamTypes)) 2088 return TDK_SubstitutionFailure; 2089 2090 // If the caller wants a full function type back, instantiate the return 2091 // type and form that function type. 2092 if (FunctionType) { 2093 // FIXME: exception-specifications? 2094 const FunctionProtoType *Proto 2095 = Function->getType()->getAs<FunctionProtoType>(); 2096 assert(Proto && "Function template does not have a prototype?"); 2097 2098 QualType ResultType 2099 = SubstType(Proto->getResultType(), 2100 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 2101 Function->getTypeSpecStartLoc(), 2102 Function->getDeclName()); 2103 if (ResultType.isNull() || Trap.hasErrorOccurred()) 2104 return TDK_SubstitutionFailure; 2105 2106 *FunctionType = BuildFunctionType(ResultType, 2107 ParamTypes.data(), ParamTypes.size(), 2108 Proto->isVariadic(), 2109 Proto->getTypeQuals(), 2110 Proto->getRefQualifier(), 2111 Function->getLocation(), 2112 Function->getDeclName(), 2113 Proto->getExtInfo()); 2114 if (FunctionType->isNull() || Trap.hasErrorOccurred()) 2115 return TDK_SubstitutionFailure; 2116 } 2117 2118 // C++ [temp.arg.explicit]p2: 2119 // Trailing template arguments that can be deduced (14.8.2) may be 2120 // omitted from the list of explicit template-arguments. If all of the 2121 // template arguments can be deduced, they may all be omitted; in this 2122 // case, the empty template argument list <> itself may also be omitted. 2123 // 2124 // Take all of the explicitly-specified arguments and put them into 2125 // the set of deduced template arguments. Explicitly-specified 2126 // parameter packs, however, will be set to NULL since the deduction 2127 // mechanisms handle explicitly-specified argument packs directly. 2128 Deduced.reserve(TemplateParams->size()); 2129 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) { 2130 const TemplateArgument &Arg = ExplicitArgumentList->get(I); 2131 if (Arg.getKind() == TemplateArgument::Pack) 2132 Deduced.push_back(DeducedTemplateArgument()); 2133 else 2134 Deduced.push_back(Arg); 2135 } 2136 2137 return TDK_Success; 2138} 2139 2140/// \brief Finish template argument deduction for a function template, 2141/// checking the deduced template arguments for completeness and forming 2142/// the function template specialization. 2143Sema::TemplateDeductionResult 2144Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate, 2145 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2146 unsigned NumExplicitlySpecified, 2147 FunctionDecl *&Specialization, 2148 TemplateDeductionInfo &Info) { 2149 TemplateParameterList *TemplateParams 2150 = FunctionTemplate->getTemplateParameters(); 2151 2152 // Template argument deduction for function templates in a SFINAE context. 2153 // Trap any errors that might occur. 2154 SFINAETrap Trap(*this); 2155 2156 // Enter a new template instantiation context while we instantiate the 2157 // actual function declaration. 2158 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 2159 FunctionTemplate, Deduced.data(), Deduced.size(), 2160 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution, 2161 Info); 2162 if (Inst) 2163 return TDK_InstantiationDepth; 2164 2165 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 2166 2167 // C++ [temp.deduct.type]p2: 2168 // [...] or if any template argument remains neither deduced nor 2169 // explicitly specified, template argument deduction fails. 2170 llvm::SmallVector<TemplateArgument, 4> Builder; 2171 for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) { 2172 NamedDecl *Param = TemplateParams->getParam(I); 2173 2174 if (!Deduced[I].isNull()) { 2175 if (I < NumExplicitlySpecified) { 2176 // We have already fully type-checked and converted this 2177 // argument, because it was explicitly-specified. Just record the 2178 // presence of this argument. 2179 Builder.push_back(Deduced[I]); 2180 continue; 2181 } 2182 2183 // We have deduced this argument, so it still needs to be 2184 // checked and converted. 2185 2186 // First, for a non-type template parameter type that is 2187 // initialized by a declaration, we need the type of the 2188 // corresponding non-type template parameter. 2189 QualType NTTPType; 2190 if (NonTypeTemplateParmDecl *NTTP 2191 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 2192 NTTPType = NTTP->getType(); 2193 if (NTTPType->isDependentType()) { 2194 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, 2195 Builder.data(), Builder.size()); 2196 NTTPType = SubstType(NTTPType, 2197 MultiLevelTemplateArgumentList(TemplateArgs), 2198 NTTP->getLocation(), 2199 NTTP->getDeclName()); 2200 if (NTTPType.isNull()) { 2201 Info.Param = makeTemplateParameter(Param); 2202 // FIXME: These template arguments are temporary. Free them! 2203 Info.reset(TemplateArgumentList::CreateCopy(Context, 2204 Builder.data(), 2205 Builder.size())); 2206 return TDK_SubstitutionFailure; 2207 } 2208 } 2209 } 2210 2211 if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I], 2212 FunctionTemplate, NTTPType, 0, Info, 2213 true, Builder)) { 2214 Info.Param = makeTemplateParameter(Param); 2215 // FIXME: These template arguments are temporary. Free them! 2216 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 2217 Builder.size())); 2218 return TDK_SubstitutionFailure; 2219 } 2220 2221 continue; 2222 } 2223 2224 // C++0x [temp.arg.explicit]p3: 2225 // A trailing template parameter pack (14.5.3) not otherwise deduced will 2226 // be deduced to an empty sequence of template arguments. 2227 // FIXME: Where did the word "trailing" come from? 2228 if (Param->isTemplateParameterPack()) { 2229 // We may have had explicitly-specified template arguments for this 2230 // template parameter pack. If so, our empty deduction extends the 2231 // explicitly-specified set (C++0x [temp.arg.explicit]p9). 2232 const TemplateArgument *ExplicitArgs; 2233 unsigned NumExplicitArgs; 2234 if (CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs, 2235 &NumExplicitArgs) 2236 == Param) 2237 Builder.push_back(TemplateArgument(ExplicitArgs, NumExplicitArgs)); 2238 else 2239 Builder.push_back(TemplateArgument(0, 0)); 2240 2241 continue; 2242 } 2243 2244 // Substitute into the default template argument, if available. 2245 TemplateArgumentLoc DefArg 2246 = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate, 2247 FunctionTemplate->getLocation(), 2248 FunctionTemplate->getSourceRange().getEnd(), 2249 Param, 2250 Builder); 2251 2252 // If there was no default argument, deduction is incomplete. 2253 if (DefArg.getArgument().isNull()) { 2254 Info.Param = makeTemplateParameter( 2255 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 2256 return TDK_Incomplete; 2257 } 2258 2259 // Check whether we can actually use the default argument. 2260 if (CheckTemplateArgument(Param, DefArg, 2261 FunctionTemplate, 2262 FunctionTemplate->getLocation(), 2263 FunctionTemplate->getSourceRange().getEnd(), 2264 0, Builder, 2265 CTAK_Deduced)) { 2266 Info.Param = makeTemplateParameter( 2267 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 2268 // FIXME: These template arguments are temporary. Free them! 2269 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 2270 Builder.size())); 2271 return TDK_SubstitutionFailure; 2272 } 2273 2274 // If we get here, we successfully used the default template argument. 2275 } 2276 2277 // Form the template argument list from the deduced template arguments. 2278 TemplateArgumentList *DeducedArgumentList 2279 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size()); 2280 Info.reset(DeducedArgumentList); 2281 2282 // Substitute the deduced template arguments into the function template 2283 // declaration to produce the function template specialization. 2284 DeclContext *Owner = FunctionTemplate->getDeclContext(); 2285 if (FunctionTemplate->getFriendObjectKind()) 2286 Owner = FunctionTemplate->getLexicalDeclContext(); 2287 Specialization = cast_or_null<FunctionDecl>( 2288 SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner, 2289 MultiLevelTemplateArgumentList(*DeducedArgumentList))); 2290 if (!Specialization) 2291 return TDK_SubstitutionFailure; 2292 2293 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() == 2294 FunctionTemplate->getCanonicalDecl()); 2295 2296 // If the template argument list is owned by the function template 2297 // specialization, release it. 2298 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList && 2299 !Trap.hasErrorOccurred()) 2300 Info.take(); 2301 2302 // There may have been an error that did not prevent us from constructing a 2303 // declaration. Mark the declaration invalid and return with a substitution 2304 // failure. 2305 if (Trap.hasErrorOccurred()) { 2306 Specialization->setInvalidDecl(true); 2307 return TDK_SubstitutionFailure; 2308 } 2309 2310 // If we suppressed any diagnostics while performing template argument 2311 // deduction, and if we haven't already instantiated this declaration, 2312 // keep track of these diagnostics. They'll be emitted if this specialization 2313 // is actually used. 2314 if (Info.diag_begin() != Info.diag_end()) { 2315 llvm::DenseMap<Decl *, llvm::SmallVector<PartialDiagnosticAt, 1> >::iterator 2316 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl()); 2317 if (Pos == SuppressedDiagnostics.end()) 2318 SuppressedDiagnostics[Specialization->getCanonicalDecl()] 2319 .append(Info.diag_begin(), Info.diag_end()); 2320 } 2321 2322 return TDK_Success; 2323} 2324 2325/// Gets the type of a function for template-argument-deducton 2326/// purposes when it's considered as part of an overload set. 2327static QualType GetTypeOfFunction(ASTContext &Context, 2328 const OverloadExpr::FindResult &R, 2329 FunctionDecl *Fn) { 2330 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn)) 2331 if (Method->isInstance()) { 2332 // An instance method that's referenced in a form that doesn't 2333 // look like a member pointer is just invalid. 2334 if (!R.HasFormOfMemberPointer) return QualType(); 2335 2336 return Context.getMemberPointerType(Fn->getType(), 2337 Context.getTypeDeclType(Method->getParent()).getTypePtr()); 2338 } 2339 2340 if (!R.IsAddressOfOperand) return Fn->getType(); 2341 return Context.getPointerType(Fn->getType()); 2342} 2343 2344/// Apply the deduction rules for overload sets. 2345/// 2346/// \return the null type if this argument should be treated as an 2347/// undeduced context 2348static QualType 2349ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams, 2350 Expr *Arg, QualType ParamType, 2351 bool ParamWasReference) { 2352 2353 OverloadExpr::FindResult R = OverloadExpr::find(Arg); 2354 2355 OverloadExpr *Ovl = R.Expression; 2356 2357 // C++0x [temp.deduct.call]p4 2358 unsigned TDF = 0; 2359 if (ParamWasReference) 2360 TDF |= TDF_ParamWithReferenceType; 2361 if (R.IsAddressOfOperand) 2362 TDF |= TDF_IgnoreQualifiers; 2363 2364 // If there were explicit template arguments, we can only find 2365 // something via C++ [temp.arg.explicit]p3, i.e. if the arguments 2366 // unambiguously name a full specialization. 2367 if (Ovl->hasExplicitTemplateArgs()) { 2368 // But we can still look for an explicit specialization. 2369 if (FunctionDecl *ExplicitSpec 2370 = S.ResolveSingleFunctionTemplateSpecialization(Ovl)) 2371 return GetTypeOfFunction(S.Context, R, ExplicitSpec); 2372 return QualType(); 2373 } 2374 2375 // C++0x [temp.deduct.call]p6: 2376 // When P is a function type, pointer to function type, or pointer 2377 // to member function type: 2378 2379 if (!ParamType->isFunctionType() && 2380 !ParamType->isFunctionPointerType() && 2381 !ParamType->isMemberFunctionPointerType()) 2382 return QualType(); 2383 2384 QualType Match; 2385 for (UnresolvedSetIterator I = Ovl->decls_begin(), 2386 E = Ovl->decls_end(); I != E; ++I) { 2387 NamedDecl *D = (*I)->getUnderlyingDecl(); 2388 2389 // - If the argument is an overload set containing one or more 2390 // function templates, the parameter is treated as a 2391 // non-deduced context. 2392 if (isa<FunctionTemplateDecl>(D)) 2393 return QualType(); 2394 2395 FunctionDecl *Fn = cast<FunctionDecl>(D); 2396 QualType ArgType = GetTypeOfFunction(S.Context, R, Fn); 2397 if (ArgType.isNull()) continue; 2398 2399 // Function-to-pointer conversion. 2400 if (!ParamWasReference && ParamType->isPointerType() && 2401 ArgType->isFunctionType()) 2402 ArgType = S.Context.getPointerType(ArgType); 2403 2404 // - If the argument is an overload set (not containing function 2405 // templates), trial argument deduction is attempted using each 2406 // of the members of the set. If deduction succeeds for only one 2407 // of the overload set members, that member is used as the 2408 // argument value for the deduction. If deduction succeeds for 2409 // more than one member of the overload set the parameter is 2410 // treated as a non-deduced context. 2411 2412 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2: 2413 // Type deduction is done independently for each P/A pair, and 2414 // the deduced template argument values are then combined. 2415 // So we do not reject deductions which were made elsewhere. 2416 llvm::SmallVector<DeducedTemplateArgument, 8> 2417 Deduced(TemplateParams->size()); 2418 TemplateDeductionInfo Info(S.Context, Ovl->getNameLoc()); 2419 Sema::TemplateDeductionResult Result 2420 = DeduceTemplateArguments(S, TemplateParams, 2421 ParamType, ArgType, 2422 Info, Deduced, TDF); 2423 if (Result) continue; 2424 if (!Match.isNull()) return QualType(); 2425 Match = ArgType; 2426 } 2427 2428 return Match; 2429} 2430 2431/// \brief Perform the adjustments to the parameter and argument types 2432/// described in C++ [temp.deduct.call]. 2433/// 2434/// \returns true if the caller should not attempt to perform any template 2435/// argument deduction based on this P/A pair. 2436static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S, 2437 TemplateParameterList *TemplateParams, 2438 QualType &ParamType, 2439 QualType &ArgType, 2440 Expr *Arg, 2441 unsigned &TDF) { 2442 // C++0x [temp.deduct.call]p3: 2443 // If P is a cv-qualified type, the top level cv-qualifiers of P's type 2444 // are ignored for type deduction. 2445 if (ParamType.getCVRQualifiers()) 2446 ParamType = ParamType.getLocalUnqualifiedType(); 2447 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>(); 2448 if (ParamRefType) { 2449 QualType PointeeType = ParamRefType->getPointeeType(); 2450 2451 // [C++0x] If P is an rvalue reference to a cv-unqualified 2452 // template parameter and the argument is an lvalue, the type 2453 // "lvalue reference to A" is used in place of A for type 2454 // deduction. 2455 if (isa<RValueReferenceType>(ParamType)) { 2456 if (!PointeeType.getQualifiers() && 2457 isa<TemplateTypeParmType>(PointeeType) && 2458 Arg->Classify(S.Context).isLValue()) 2459 ArgType = S.Context.getLValueReferenceType(ArgType); 2460 } 2461 2462 // [...] If P is a reference type, the type referred to by P is used 2463 // for type deduction. 2464 ParamType = PointeeType; 2465 } 2466 2467 // Overload sets usually make this parameter an undeduced 2468 // context, but there are sometimes special circumstances. 2469 if (ArgType == S.Context.OverloadTy) { 2470 ArgType = ResolveOverloadForDeduction(S, TemplateParams, 2471 Arg, ParamType, 2472 ParamRefType != 0); 2473 if (ArgType.isNull()) 2474 return true; 2475 } 2476 2477 if (ParamRefType) { 2478 // C++0x [temp.deduct.call]p3: 2479 // [...] If P is of the form T&&, where T is a template parameter, and 2480 // the argument is an lvalue, the type A& is used in place of A for 2481 // type deduction. 2482 if (ParamRefType->isRValueReferenceType() && 2483 ParamRefType->getAs<TemplateTypeParmType>() && 2484 Arg->isLValue()) 2485 ArgType = S.Context.getLValueReferenceType(ArgType); 2486 } else { 2487 // C++ [temp.deduct.call]p2: 2488 // If P is not a reference type: 2489 // - If A is an array type, the pointer type produced by the 2490 // array-to-pointer standard conversion (4.2) is used in place of 2491 // A for type deduction; otherwise, 2492 if (ArgType->isArrayType()) 2493 ArgType = S.Context.getArrayDecayedType(ArgType); 2494 // - If A is a function type, the pointer type produced by the 2495 // function-to-pointer standard conversion (4.3) is used in place 2496 // of A for type deduction; otherwise, 2497 else if (ArgType->isFunctionType()) 2498 ArgType = S.Context.getPointerType(ArgType); 2499 else { 2500 // - If A is a cv-qualified type, the top level cv-qualifiers of A's 2501 // type are ignored for type deduction. 2502 if (ArgType.getCVRQualifiers()) 2503 ArgType = ArgType.getUnqualifiedType(); 2504 } 2505 } 2506 2507 // C++0x [temp.deduct.call]p4: 2508 // In general, the deduction process attempts to find template argument 2509 // values that will make the deduced A identical to A (after the type A 2510 // is transformed as described above). [...] 2511 TDF = TDF_SkipNonDependent; 2512 2513 // - If the original P is a reference type, the deduced A (i.e., the 2514 // type referred to by the reference) can be more cv-qualified than 2515 // the transformed A. 2516 if (ParamRefType) 2517 TDF |= TDF_ParamWithReferenceType; 2518 // - The transformed A can be another pointer or pointer to member 2519 // type that can be converted to the deduced A via a qualification 2520 // conversion (4.4). 2521 if (ArgType->isPointerType() || ArgType->isMemberPointerType() || 2522 ArgType->isObjCObjectPointerType()) 2523 TDF |= TDF_IgnoreQualifiers; 2524 // - If P is a class and P has the form simple-template-id, then the 2525 // transformed A can be a derived class of the deduced A. Likewise, 2526 // if P is a pointer to a class of the form simple-template-id, the 2527 // transformed A can be a pointer to a derived class pointed to by 2528 // the deduced A. 2529 if (isSimpleTemplateIdType(ParamType) || 2530 (isa<PointerType>(ParamType) && 2531 isSimpleTemplateIdType( 2532 ParamType->getAs<PointerType>()->getPointeeType()))) 2533 TDF |= TDF_DerivedClass; 2534 2535 return false; 2536} 2537 2538/// \brief Perform template argument deduction from a function call 2539/// (C++ [temp.deduct.call]). 2540/// 2541/// \param FunctionTemplate the function template for which we are performing 2542/// template argument deduction. 2543/// 2544/// \param ExplicitTemplateArguments the explicit template arguments provided 2545/// for this call. 2546/// 2547/// \param Args the function call arguments 2548/// 2549/// \param NumArgs the number of arguments in Args 2550/// 2551/// \param Name the name of the function being called. This is only significant 2552/// when the function template is a conversion function template, in which 2553/// case this routine will also perform template argument deduction based on 2554/// the function to which 2555/// 2556/// \param Specialization if template argument deduction was successful, 2557/// this will be set to the function template specialization produced by 2558/// template argument deduction. 2559/// 2560/// \param Info the argument will be updated to provide additional information 2561/// about template argument deduction. 2562/// 2563/// \returns the result of template argument deduction. 2564Sema::TemplateDeductionResult 2565Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2566 const TemplateArgumentListInfo *ExplicitTemplateArgs, 2567 Expr **Args, unsigned NumArgs, 2568 FunctionDecl *&Specialization, 2569 TemplateDeductionInfo &Info) { 2570 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2571 2572 // C++ [temp.deduct.call]p1: 2573 // Template argument deduction is done by comparing each function template 2574 // parameter type (call it P) with the type of the corresponding argument 2575 // of the call (call it A) as described below. 2576 unsigned CheckArgs = NumArgs; 2577 if (NumArgs < Function->getMinRequiredArguments()) 2578 return TDK_TooFewArguments; 2579 else if (NumArgs > Function->getNumParams()) { 2580 const FunctionProtoType *Proto 2581 = Function->getType()->getAs<FunctionProtoType>(); 2582 if (Proto->isTemplateVariadic()) 2583 /* Do nothing */; 2584 else if (Proto->isVariadic()) 2585 CheckArgs = Function->getNumParams(); 2586 else 2587 return TDK_TooManyArguments; 2588 } 2589 2590 // The types of the parameters from which we will perform template argument 2591 // deduction. 2592 LocalInstantiationScope InstScope(*this); 2593 TemplateParameterList *TemplateParams 2594 = FunctionTemplate->getTemplateParameters(); 2595 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2596 llvm::SmallVector<QualType, 4> ParamTypes; 2597 unsigned NumExplicitlySpecified = 0; 2598 if (ExplicitTemplateArgs) { 2599 TemplateDeductionResult Result = 2600 SubstituteExplicitTemplateArguments(FunctionTemplate, 2601 *ExplicitTemplateArgs, 2602 Deduced, 2603 ParamTypes, 2604 0, 2605 Info); 2606 if (Result) 2607 return Result; 2608 2609 NumExplicitlySpecified = Deduced.size(); 2610 } else { 2611 // Just fill in the parameter types from the function declaration. 2612 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 2613 ParamTypes.push_back(Function->getParamDecl(I)->getType()); 2614 } 2615 2616 // Deduce template arguments from the function parameters. 2617 Deduced.resize(TemplateParams->size()); 2618 unsigned ArgIdx = 0; 2619 for (unsigned ParamIdx = 0, NumParams = ParamTypes.size(); 2620 ParamIdx != NumParams; ++ParamIdx) { 2621 QualType ParamType = ParamTypes[ParamIdx]; 2622 2623 const PackExpansionType *ParamExpansion 2624 = dyn_cast<PackExpansionType>(ParamType); 2625 if (!ParamExpansion) { 2626 // Simple case: matching a function parameter to a function argument. 2627 if (ArgIdx >= CheckArgs) 2628 break; 2629 2630 Expr *Arg = Args[ArgIdx++]; 2631 QualType ArgType = Arg->getType(); 2632 unsigned TDF = 0; 2633 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams, 2634 ParamType, ArgType, Arg, 2635 TDF)) 2636 continue; 2637 2638 if (TemplateDeductionResult Result 2639 = ::DeduceTemplateArguments(*this, TemplateParams, 2640 ParamType, ArgType, Info, Deduced, 2641 TDF)) 2642 return Result; 2643 2644 // FIXME: we need to check that the deduced A is the same as A, 2645 // modulo the various allowed differences. 2646 continue; 2647 } 2648 2649 // C++0x [temp.deduct.call]p1: 2650 // For a function parameter pack that occurs at the end of the 2651 // parameter-declaration-list, the type A of each remaining argument of 2652 // the call is compared with the type P of the declarator-id of the 2653 // function parameter pack. Each comparison deduces template arguments 2654 // for subsequent positions in the template parameter packs expanded by 2655 // the function parameter pack. For a function parameter pack that does 2656 // not occur at the end of the parameter-declaration-list, the type of 2657 // the parameter pack is a non-deduced context. 2658 if (ParamIdx + 1 < NumParams) 2659 break; 2660 2661 QualType ParamPattern = ParamExpansion->getPattern(); 2662 llvm::SmallVector<unsigned, 2> PackIndices; 2663 { 2664 llvm::BitVector SawIndices(TemplateParams->size()); 2665 llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded; 2666 collectUnexpandedParameterPacks(ParamPattern, Unexpanded); 2667 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) { 2668 unsigned Depth, Index; 2669 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]); 2670 if (Depth == 0 && !SawIndices[Index]) { 2671 SawIndices[Index] = true; 2672 PackIndices.push_back(Index); 2673 } 2674 } 2675 } 2676 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?"); 2677 2678 // Keep track of the deduced template arguments for each parameter pack 2679 // expanded by this pack expansion (the outer index) and for each 2680 // template argument (the inner SmallVectors). 2681 llvm::SmallVector<llvm::SmallVector<DeducedTemplateArgument, 4>, 2> 2682 NewlyDeducedPacks(PackIndices.size()); 2683 llvm::SmallVector<DeducedTemplateArgument, 2> 2684 SavedPacks(PackIndices.size()); 2685 PrepareArgumentPackDeduction(*this, Deduced, PackIndices, SavedPacks, 2686 NewlyDeducedPacks); 2687 bool HasAnyArguments = false; 2688 for (; ArgIdx < NumArgs; ++ArgIdx) { 2689 HasAnyArguments = true; 2690 2691 ParamType = ParamPattern; 2692 Expr *Arg = Args[ArgIdx]; 2693 QualType ArgType = Arg->getType(); 2694 unsigned TDF = 0; 2695 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams, 2696 ParamType, ArgType, Arg, 2697 TDF)) { 2698 // We can't actually perform any deduction for this argument, so stop 2699 // deduction at this point. 2700 ++ArgIdx; 2701 break; 2702 } 2703 2704 if (TemplateDeductionResult Result 2705 = ::DeduceTemplateArguments(*this, TemplateParams, 2706 ParamType, ArgType, Info, Deduced, 2707 TDF)) 2708 return Result; 2709 2710 // Capture the deduced template arguments for each parameter pack expanded 2711 // by this pack expansion, add them to the list of arguments we've deduced 2712 // for that pack, then clear out the deduced argument. 2713 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 2714 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]]; 2715 if (!DeducedArg.isNull()) { 2716 NewlyDeducedPacks[I].push_back(DeducedArg); 2717 DeducedArg = DeducedTemplateArgument(); 2718 } 2719 } 2720 } 2721 2722 // Build argument packs for each of the parameter packs expanded by this 2723 // pack expansion. 2724 if (Sema::TemplateDeductionResult Result 2725 = FinishArgumentPackDeduction(*this, TemplateParams, HasAnyArguments, 2726 Deduced, PackIndices, SavedPacks, 2727 NewlyDeducedPacks, Info)) 2728 return Result; 2729 2730 // After we've matching against a parameter pack, we're done. 2731 break; 2732 } 2733 2734 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 2735 NumExplicitlySpecified, 2736 Specialization, Info); 2737} 2738 2739/// \brief Deduce template arguments when taking the address of a function 2740/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to 2741/// a template. 2742/// 2743/// \param FunctionTemplate the function template for which we are performing 2744/// template argument deduction. 2745/// 2746/// \param ExplicitTemplateArguments the explicitly-specified template 2747/// arguments. 2748/// 2749/// \param ArgFunctionType the function type that will be used as the 2750/// "argument" type (A) when performing template argument deduction from the 2751/// function template's function type. This type may be NULL, if there is no 2752/// argument type to compare against, in C++0x [temp.arg.explicit]p3. 2753/// 2754/// \param Specialization if template argument deduction was successful, 2755/// this will be set to the function template specialization produced by 2756/// template argument deduction. 2757/// 2758/// \param Info the argument will be updated to provide additional information 2759/// about template argument deduction. 2760/// 2761/// \returns the result of template argument deduction. 2762Sema::TemplateDeductionResult 2763Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2764 const TemplateArgumentListInfo *ExplicitTemplateArgs, 2765 QualType ArgFunctionType, 2766 FunctionDecl *&Specialization, 2767 TemplateDeductionInfo &Info) { 2768 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2769 TemplateParameterList *TemplateParams 2770 = FunctionTemplate->getTemplateParameters(); 2771 QualType FunctionType = Function->getType(); 2772 2773 // Substitute any explicit template arguments. 2774 LocalInstantiationScope InstScope(*this); 2775 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2776 unsigned NumExplicitlySpecified = 0; 2777 llvm::SmallVector<QualType, 4> ParamTypes; 2778 if (ExplicitTemplateArgs) { 2779 if (TemplateDeductionResult Result 2780 = SubstituteExplicitTemplateArguments(FunctionTemplate, 2781 *ExplicitTemplateArgs, 2782 Deduced, ParamTypes, 2783 &FunctionType, Info)) 2784 return Result; 2785 2786 NumExplicitlySpecified = Deduced.size(); 2787 } 2788 2789 // Template argument deduction for function templates in a SFINAE context. 2790 // Trap any errors that might occur. 2791 SFINAETrap Trap(*this); 2792 2793 Deduced.resize(TemplateParams->size()); 2794 2795 if (!ArgFunctionType.isNull()) { 2796 // Deduce template arguments from the function type. 2797 if (TemplateDeductionResult Result 2798 = ::DeduceTemplateArguments(*this, TemplateParams, 2799 FunctionType, ArgFunctionType, Info, 2800 Deduced, TDF_TopLevelParameterTypeList)) 2801 return Result; 2802 } 2803 2804 if (TemplateDeductionResult Result 2805 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 2806 NumExplicitlySpecified, 2807 Specialization, Info)) 2808 return Result; 2809 2810 // If the requested function type does not match the actual type of the 2811 // specialization, template argument deduction fails. 2812 if (!ArgFunctionType.isNull() && 2813 !Context.hasSameType(ArgFunctionType, Specialization->getType())) 2814 return TDK_NonDeducedMismatch; 2815 2816 return TDK_Success; 2817} 2818 2819/// \brief Deduce template arguments for a templated conversion 2820/// function (C++ [temp.deduct.conv]) and, if successful, produce a 2821/// conversion function template specialization. 2822Sema::TemplateDeductionResult 2823Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2824 QualType ToType, 2825 CXXConversionDecl *&Specialization, 2826 TemplateDeductionInfo &Info) { 2827 CXXConversionDecl *Conv 2828 = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl()); 2829 QualType FromType = Conv->getConversionType(); 2830 2831 // Canonicalize the types for deduction. 2832 QualType P = Context.getCanonicalType(FromType); 2833 QualType A = Context.getCanonicalType(ToType); 2834 2835 // C++0x [temp.deduct.conv]p3: 2836 // If P is a reference type, the type referred to by P is used for 2837 // type deduction. 2838 if (const ReferenceType *PRef = P->getAs<ReferenceType>()) 2839 P = PRef->getPointeeType(); 2840 2841 // C++0x [temp.deduct.conv]p3: 2842 // If A is a reference type, the type referred to by A is used 2843 // for type deduction. 2844 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 2845 A = ARef->getPointeeType(); 2846 // C++ [temp.deduct.conv]p2: 2847 // 2848 // If A is not a reference type: 2849 else { 2850 assert(!A->isReferenceType() && "Reference types were handled above"); 2851 2852 // - If P is an array type, the pointer type produced by the 2853 // array-to-pointer standard conversion (4.2) is used in place 2854 // of P for type deduction; otherwise, 2855 if (P->isArrayType()) 2856 P = Context.getArrayDecayedType(P); 2857 // - If P is a function type, the pointer type produced by the 2858 // function-to-pointer standard conversion (4.3) is used in 2859 // place of P for type deduction; otherwise, 2860 else if (P->isFunctionType()) 2861 P = Context.getPointerType(P); 2862 // - If P is a cv-qualified type, the top level cv-qualifiers of 2863 // P's type are ignored for type deduction. 2864 else 2865 P = P.getUnqualifiedType(); 2866 2867 // C++0x [temp.deduct.conv]p3: 2868 // If A is a cv-qualified type, the top level cv-qualifiers of A's 2869 // type are ignored for type deduction. 2870 A = A.getUnqualifiedType(); 2871 } 2872 2873 // Template argument deduction for function templates in a SFINAE context. 2874 // Trap any errors that might occur. 2875 SFINAETrap Trap(*this); 2876 2877 // C++ [temp.deduct.conv]p1: 2878 // Template argument deduction is done by comparing the return 2879 // type of the template conversion function (call it P) with the 2880 // type that is required as the result of the conversion (call it 2881 // A) as described in 14.8.2.4. 2882 TemplateParameterList *TemplateParams 2883 = FunctionTemplate->getTemplateParameters(); 2884 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2885 Deduced.resize(TemplateParams->size()); 2886 2887 // C++0x [temp.deduct.conv]p4: 2888 // In general, the deduction process attempts to find template 2889 // argument values that will make the deduced A identical to 2890 // A. However, there are two cases that allow a difference: 2891 unsigned TDF = 0; 2892 // - If the original A is a reference type, A can be more 2893 // cv-qualified than the deduced A (i.e., the type referred to 2894 // by the reference) 2895 if (ToType->isReferenceType()) 2896 TDF |= TDF_ParamWithReferenceType; 2897 // - The deduced A can be another pointer or pointer to member 2898 // type that can be converted to A via a qualification 2899 // conversion. 2900 // 2901 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 2902 // both P and A are pointers or member pointers. In this case, we 2903 // just ignore cv-qualifiers completely). 2904 if ((P->isPointerType() && A->isPointerType()) || 2905 (P->isMemberPointerType() && P->isMemberPointerType())) 2906 TDF |= TDF_IgnoreQualifiers; 2907 if (TemplateDeductionResult Result 2908 = ::DeduceTemplateArguments(*this, TemplateParams, 2909 P, A, Info, Deduced, TDF)) 2910 return Result; 2911 2912 // FIXME: we need to check that the deduced A is the same as A, 2913 // modulo the various allowed differences. 2914 2915 // Finish template argument deduction. 2916 LocalInstantiationScope InstScope(*this); 2917 FunctionDecl *Spec = 0; 2918 TemplateDeductionResult Result 2919 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec, 2920 Info); 2921 Specialization = cast_or_null<CXXConversionDecl>(Spec); 2922 return Result; 2923} 2924 2925/// \brief Deduce template arguments for a function template when there is 2926/// nothing to deduce against (C++0x [temp.arg.explicit]p3). 2927/// 2928/// \param FunctionTemplate the function template for which we are performing 2929/// template argument deduction. 2930/// 2931/// \param ExplicitTemplateArguments the explicitly-specified template 2932/// arguments. 2933/// 2934/// \param Specialization if template argument deduction was successful, 2935/// this will be set to the function template specialization produced by 2936/// template argument deduction. 2937/// 2938/// \param Info the argument will be updated to provide additional information 2939/// about template argument deduction. 2940/// 2941/// \returns the result of template argument deduction. 2942Sema::TemplateDeductionResult 2943Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2944 const TemplateArgumentListInfo *ExplicitTemplateArgs, 2945 FunctionDecl *&Specialization, 2946 TemplateDeductionInfo &Info) { 2947 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs, 2948 QualType(), Specialization, Info); 2949} 2950 2951namespace { 2952 /// Substitute the 'auto' type specifier within a type for a given replacement 2953 /// type. 2954 class SubstituteAutoTransform : 2955 public TreeTransform<SubstituteAutoTransform> { 2956 QualType Replacement; 2957 public: 2958 SubstituteAutoTransform(Sema &SemaRef, QualType Replacement) : 2959 TreeTransform<SubstituteAutoTransform>(SemaRef), Replacement(Replacement) { 2960 } 2961 QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) { 2962 // If we're building the type pattern to deduce against, don't wrap the 2963 // substituted type in an AutoType. Certain template deduction rules 2964 // apply only when a template type parameter appears directly (and not if 2965 // the parameter is found through desugaring). For instance: 2966 // auto &&lref = lvalue; 2967 // must transform into "rvalue reference to T" not "rvalue reference to 2968 // auto type deduced as T" in order for [temp.deduct.call]p3 to apply. 2969 if (isa<TemplateTypeParmType>(Replacement)) { 2970 QualType Result = Replacement; 2971 TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result); 2972 NewTL.setNameLoc(TL.getNameLoc()); 2973 return Result; 2974 } else { 2975 QualType Result = RebuildAutoType(Replacement); 2976 AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result); 2977 NewTL.setNameLoc(TL.getNameLoc()); 2978 return Result; 2979 } 2980 } 2981 }; 2982} 2983 2984/// \brief Deduce the type for an auto type-specifier (C++0x [dcl.spec.auto]p6) 2985/// 2986/// \param Type the type pattern using the auto type-specifier. 2987/// 2988/// \param Init the initializer for the variable whose type is to be deduced. 2989/// 2990/// \param Result if type deduction was successful, this will be set to the 2991/// deduced type. This may still contain undeduced autos if the type is 2992/// dependent. 2993/// 2994/// \returns true if deduction succeeded, false if it failed. 2995bool 2996Sema::DeduceAutoType(QualType Type, Expr *Init, QualType &Result) { 2997 if (Init->isTypeDependent()) { 2998 Result = Type; 2999 return true; 3000 } 3001 3002 SourceLocation Loc = Init->getExprLoc(); 3003 3004 LocalInstantiationScope InstScope(*this); 3005 3006 // Build template<class TemplParam> void Func(FuncParam); 3007 NamedDecl *TemplParam 3008 = TemplateTypeParmDecl::Create(Context, 0, Loc, 0, 0, 0, false, false); 3009 TemplateParameterList *TemplateParams 3010 = TemplateParameterList::Create(Context, Loc, Loc, &TemplParam, 1, Loc); 3011 3012 QualType TemplArg = Context.getTemplateTypeParmType(0, 0, false); 3013 QualType FuncParam = 3014 SubstituteAutoTransform(*this, TemplArg).TransformType(Type); 3015 3016 // Deduce type of TemplParam in Func(Init) 3017 llvm::SmallVector<DeducedTemplateArgument, 1> Deduced; 3018 Deduced.resize(1); 3019 QualType InitType = Init->getType(); 3020 unsigned TDF = 0; 3021 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams, 3022 FuncParam, InitType, Init, 3023 TDF)) 3024 return false; 3025 3026 TemplateDeductionInfo Info(Context, Loc); 3027 if (::DeduceTemplateArguments(*this, TemplateParams, 3028 FuncParam, InitType, Info, Deduced, 3029 TDF)) 3030 return false; 3031 3032 QualType DeducedType = Deduced[0].getAsType(); 3033 if (DeducedType.isNull()) 3034 return false; 3035 3036 Result = SubstituteAutoTransform(*this, DeducedType).TransformType(Type); 3037 return true; 3038} 3039 3040static void 3041MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 3042 bool OnlyDeduced, 3043 unsigned Level, 3044 llvm::SmallVectorImpl<bool> &Deduced); 3045 3046/// \brief If this is a non-static member function, 3047static void MaybeAddImplicitObjectParameterType(ASTContext &Context, 3048 CXXMethodDecl *Method, 3049 llvm::SmallVectorImpl<QualType> &ArgTypes) { 3050 if (Method->isStatic()) 3051 return; 3052 3053 // C++ [over.match.funcs]p4: 3054 // 3055 // For non-static member functions, the type of the implicit 3056 // object parameter is 3057 // - "lvalue reference to cv X" for functions declared without a 3058 // ref-qualifier or with the & ref-qualifier 3059 // - "rvalue reference to cv X" for functions declared with the 3060 // && ref-qualifier 3061 // 3062 // FIXME: We don't have ref-qualifiers yet, so we don't do that part. 3063 QualType ArgTy = Context.getTypeDeclType(Method->getParent()); 3064 ArgTy = Context.getQualifiedType(ArgTy, 3065 Qualifiers::fromCVRMask(Method->getTypeQualifiers())); 3066 ArgTy = Context.getLValueReferenceType(ArgTy); 3067 ArgTypes.push_back(ArgTy); 3068} 3069 3070/// \brief Determine whether the function template \p FT1 is at least as 3071/// specialized as \p FT2. 3072static bool isAtLeastAsSpecializedAs(Sema &S, 3073 SourceLocation Loc, 3074 FunctionTemplateDecl *FT1, 3075 FunctionTemplateDecl *FT2, 3076 TemplatePartialOrderingContext TPOC, 3077 unsigned NumCallArguments, 3078 llvm::SmallVectorImpl<RefParamPartialOrderingComparison> *RefParamComparisons) { 3079 FunctionDecl *FD1 = FT1->getTemplatedDecl(); 3080 FunctionDecl *FD2 = FT2->getTemplatedDecl(); 3081 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 3082 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 3083 3084 assert(Proto1 && Proto2 && "Function templates must have prototypes"); 3085 TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 3086 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 3087 Deduced.resize(TemplateParams->size()); 3088 3089 // C++0x [temp.deduct.partial]p3: 3090 // The types used to determine the ordering depend on the context in which 3091 // the partial ordering is done: 3092 TemplateDeductionInfo Info(S.Context, Loc); 3093 CXXMethodDecl *Method1 = 0; 3094 CXXMethodDecl *Method2 = 0; 3095 bool IsNonStatic2 = false; 3096 bool IsNonStatic1 = false; 3097 unsigned Skip2 = 0; 3098 switch (TPOC) { 3099 case TPOC_Call: { 3100 // - In the context of a function call, the function parameter types are 3101 // used. 3102 Method1 = dyn_cast<CXXMethodDecl>(FD1); 3103 Method2 = dyn_cast<CXXMethodDecl>(FD2); 3104 IsNonStatic1 = Method1 && !Method1->isStatic(); 3105 IsNonStatic2 = Method2 && !Method2->isStatic(); 3106 3107 // C++0x [temp.func.order]p3: 3108 // [...] If only one of the function templates is a non-static 3109 // member, that function template is considered to have a new 3110 // first parameter inserted in its function parameter list. The 3111 // new parameter is of type "reference to cv A," where cv are 3112 // the cv-qualifiers of the function template (if any) and A is 3113 // the class of which the function template is a member. 3114 // 3115 // C++98/03 doesn't have this provision, so instead we drop the 3116 // first argument of the free function or static member, which 3117 // seems to match existing practice. 3118 llvm::SmallVector<QualType, 4> Args1; 3119 unsigned Skip1 = !S.getLangOptions().CPlusPlus0x && 3120 IsNonStatic2 && !IsNonStatic1; 3121 if (S.getLangOptions().CPlusPlus0x && IsNonStatic1 && !IsNonStatic2) 3122 MaybeAddImplicitObjectParameterType(S.Context, Method1, Args1); 3123 Args1.insert(Args1.end(), 3124 Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end()); 3125 3126 llvm::SmallVector<QualType, 4> Args2; 3127 Skip2 = !S.getLangOptions().CPlusPlus0x && 3128 IsNonStatic1 && !IsNonStatic2; 3129 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1) 3130 MaybeAddImplicitObjectParameterType(S.Context, Method2, Args2); 3131 Args2.insert(Args2.end(), 3132 Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end()); 3133 3134 // C++ [temp.func.order]p5: 3135 // The presence of unused ellipsis and default arguments has no effect on 3136 // the partial ordering of function templates. 3137 if (Args1.size() > NumCallArguments) 3138 Args1.resize(NumCallArguments); 3139 if (Args2.size() > NumCallArguments) 3140 Args2.resize(NumCallArguments); 3141 if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(), 3142 Args1.data(), Args1.size(), Info, Deduced, 3143 TDF_None, /*PartialOrdering=*/true, 3144 RefParamComparisons)) 3145 return false; 3146 3147 break; 3148 } 3149 3150 case TPOC_Conversion: 3151 // - In the context of a call to a conversion operator, the return types 3152 // of the conversion function templates are used. 3153 if (DeduceTemplateArguments(S, TemplateParams, Proto2->getResultType(), 3154 Proto1->getResultType(), Info, Deduced, 3155 TDF_None, /*PartialOrdering=*/true, 3156 RefParamComparisons)) 3157 return false; 3158 break; 3159 3160 case TPOC_Other: 3161 // - In other contexts (14.6.6.2) the function template's function type 3162 // is used. 3163 // FIXME: Don't we actually want to perform the adjustments on the parameter 3164 // types? 3165 if (DeduceTemplateArguments(S, TemplateParams, FD2->getType(), 3166 FD1->getType(), Info, Deduced, TDF_None, 3167 /*PartialOrdering=*/true, RefParamComparisons)) 3168 return false; 3169 break; 3170 } 3171 3172 // C++0x [temp.deduct.partial]p11: 3173 // In most cases, all template parameters must have values in order for 3174 // deduction to succeed, but for partial ordering purposes a template 3175 // parameter may remain without a value provided it is not used in the 3176 // types being used for partial ordering. [ Note: a template parameter used 3177 // in a non-deduced context is considered used. -end note] 3178 unsigned ArgIdx = 0, NumArgs = Deduced.size(); 3179 for (; ArgIdx != NumArgs; ++ArgIdx) 3180 if (Deduced[ArgIdx].isNull()) 3181 break; 3182 3183 if (ArgIdx == NumArgs) { 3184 // All template arguments were deduced. FT1 is at least as specialized 3185 // as FT2. 3186 return true; 3187 } 3188 3189 // Figure out which template parameters were used. 3190 llvm::SmallVector<bool, 4> UsedParameters; 3191 UsedParameters.resize(TemplateParams->size()); 3192 switch (TPOC) { 3193 case TPOC_Call: { 3194 unsigned NumParams = std::min(NumCallArguments, 3195 std::min(Proto1->getNumArgs(), 3196 Proto2->getNumArgs())); 3197 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1) 3198 ::MarkUsedTemplateParameters(S, Method2->getThisType(S.Context), false, 3199 TemplateParams->getDepth(), UsedParameters); 3200 for (unsigned I = Skip2; I < NumParams; ++I) 3201 ::MarkUsedTemplateParameters(S, Proto2->getArgType(I), false, 3202 TemplateParams->getDepth(), 3203 UsedParameters); 3204 break; 3205 } 3206 3207 case TPOC_Conversion: 3208 ::MarkUsedTemplateParameters(S, Proto2->getResultType(), false, 3209 TemplateParams->getDepth(), 3210 UsedParameters); 3211 break; 3212 3213 case TPOC_Other: 3214 ::MarkUsedTemplateParameters(S, FD2->getType(), false, 3215 TemplateParams->getDepth(), 3216 UsedParameters); 3217 break; 3218 } 3219 3220 for (; ArgIdx != NumArgs; ++ArgIdx) 3221 // If this argument had no value deduced but was used in one of the types 3222 // used for partial ordering, then deduction fails. 3223 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 3224 return false; 3225 3226 return true; 3227} 3228 3229/// \brief Determine whether this a function template whose parameter-type-list 3230/// ends with a function parameter pack. 3231static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) { 3232 FunctionDecl *Function = FunTmpl->getTemplatedDecl(); 3233 unsigned NumParams = Function->getNumParams(); 3234 if (NumParams == 0) 3235 return false; 3236 3237 ParmVarDecl *Last = Function->getParamDecl(NumParams - 1); 3238 if (!Last->isParameterPack()) 3239 return false; 3240 3241 // Make sure that no previous parameter is a parameter pack. 3242 while (--NumParams > 0) { 3243 if (Function->getParamDecl(NumParams - 1)->isParameterPack()) 3244 return false; 3245 } 3246 3247 return true; 3248} 3249 3250/// \brief Returns the more specialized function template according 3251/// to the rules of function template partial ordering (C++ [temp.func.order]). 3252/// 3253/// \param FT1 the first function template 3254/// 3255/// \param FT2 the second function template 3256/// 3257/// \param TPOC the context in which we are performing partial ordering of 3258/// function templates. 3259/// 3260/// \param NumCallArguments The number of arguments in a call, used only 3261/// when \c TPOC is \c TPOC_Call. 3262/// 3263/// \returns the more specialized function template. If neither 3264/// template is more specialized, returns NULL. 3265FunctionTemplateDecl * 3266Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, 3267 FunctionTemplateDecl *FT2, 3268 SourceLocation Loc, 3269 TemplatePartialOrderingContext TPOC, 3270 unsigned NumCallArguments) { 3271 llvm::SmallVector<RefParamPartialOrderingComparison, 4> RefParamComparisons; 3272 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC, 3273 NumCallArguments, 0); 3274 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC, 3275 NumCallArguments, 3276 &RefParamComparisons); 3277 3278 if (Better1 != Better2) // We have a clear winner 3279 return Better1? FT1 : FT2; 3280 3281 if (!Better1 && !Better2) // Neither is better than the other 3282 return 0; 3283 3284 // C++0x [temp.deduct.partial]p10: 3285 // If for each type being considered a given template is at least as 3286 // specialized for all types and more specialized for some set of types and 3287 // the other template is not more specialized for any types or is not at 3288 // least as specialized for any types, then the given template is more 3289 // specialized than the other template. Otherwise, neither template is more 3290 // specialized than the other. 3291 Better1 = false; 3292 Better2 = false; 3293 for (unsigned I = 0, N = RefParamComparisons.size(); I != N; ++I) { 3294 // C++0x [temp.deduct.partial]p9: 3295 // If, for a given type, deduction succeeds in both directions (i.e., the 3296 // types are identical after the transformations above) and both P and A 3297 // were reference types (before being replaced with the type referred to 3298 // above): 3299 3300 // -- if the type from the argument template was an lvalue reference 3301 // and the type from the parameter template was not, the argument 3302 // type is considered to be more specialized than the other; 3303 // otherwise, 3304 if (!RefParamComparisons[I].ArgIsRvalueRef && 3305 RefParamComparisons[I].ParamIsRvalueRef) { 3306 Better2 = true; 3307 if (Better1) 3308 return 0; 3309 continue; 3310 } else if (!RefParamComparisons[I].ParamIsRvalueRef && 3311 RefParamComparisons[I].ArgIsRvalueRef) { 3312 Better1 = true; 3313 if (Better2) 3314 return 0; 3315 continue; 3316 } 3317 3318 // -- if the type from the argument template is more cv-qualified than 3319 // the type from the parameter template (as described above), the 3320 // argument type is considered to be more specialized than the 3321 // other; otherwise, 3322 switch (RefParamComparisons[I].Qualifiers) { 3323 case NeitherMoreQualified: 3324 break; 3325 3326 case ParamMoreQualified: 3327 Better1 = true; 3328 if (Better2) 3329 return 0; 3330 continue; 3331 3332 case ArgMoreQualified: 3333 Better2 = true; 3334 if (Better1) 3335 return 0; 3336 continue; 3337 } 3338 3339 // -- neither type is more specialized than the other. 3340 } 3341 3342 assert(!(Better1 && Better2) && "Should have broken out in the loop above"); 3343 if (Better1) 3344 return FT1; 3345 else if (Better2) 3346 return FT2; 3347 3348 // FIXME: This mimics what GCC implements, but doesn't match up with the 3349 // proposed resolution for core issue 692. This area needs to be sorted out, 3350 // but for now we attempt to maintain compatibility. 3351 bool Variadic1 = isVariadicFunctionTemplate(FT1); 3352 bool Variadic2 = isVariadicFunctionTemplate(FT2); 3353 if (Variadic1 != Variadic2) 3354 return Variadic1? FT2 : FT1; 3355 3356 return 0; 3357} 3358 3359/// \brief Determine if the two templates are equivalent. 3360static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) { 3361 if (T1 == T2) 3362 return true; 3363 3364 if (!T1 || !T2) 3365 return false; 3366 3367 return T1->getCanonicalDecl() == T2->getCanonicalDecl(); 3368} 3369 3370/// \brief Retrieve the most specialized of the given function template 3371/// specializations. 3372/// 3373/// \param SpecBegin the start iterator of the function template 3374/// specializations that we will be comparing. 3375/// 3376/// \param SpecEnd the end iterator of the function template 3377/// specializations, paired with \p SpecBegin. 3378/// 3379/// \param TPOC the partial ordering context to use to compare the function 3380/// template specializations. 3381/// 3382/// \param NumCallArguments The number of arguments in a call, used only 3383/// when \c TPOC is \c TPOC_Call. 3384/// 3385/// \param Loc the location where the ambiguity or no-specializations 3386/// diagnostic should occur. 3387/// 3388/// \param NoneDiag partial diagnostic used to diagnose cases where there are 3389/// no matching candidates. 3390/// 3391/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one 3392/// occurs. 3393/// 3394/// \param CandidateDiag partial diagnostic used for each function template 3395/// specialization that is a candidate in the ambiguous ordering. One parameter 3396/// in this diagnostic should be unbound, which will correspond to the string 3397/// describing the template arguments for the function template specialization. 3398/// 3399/// \param Index if non-NULL and the result of this function is non-nULL, 3400/// receives the index corresponding to the resulting function template 3401/// specialization. 3402/// 3403/// \returns the most specialized function template specialization, if 3404/// found. Otherwise, returns SpecEnd. 3405/// 3406/// \todo FIXME: Consider passing in the "also-ran" candidates that failed 3407/// template argument deduction. 3408UnresolvedSetIterator 3409Sema::getMostSpecialized(UnresolvedSetIterator SpecBegin, 3410 UnresolvedSetIterator SpecEnd, 3411 TemplatePartialOrderingContext TPOC, 3412 unsigned NumCallArguments, 3413 SourceLocation Loc, 3414 const PartialDiagnostic &NoneDiag, 3415 const PartialDiagnostic &AmbigDiag, 3416 const PartialDiagnostic &CandidateDiag, 3417 bool Complain) { 3418 if (SpecBegin == SpecEnd) { 3419 if (Complain) 3420 Diag(Loc, NoneDiag); 3421 return SpecEnd; 3422 } 3423 3424 if (SpecBegin + 1 == SpecEnd) 3425 return SpecBegin; 3426 3427 // Find the function template that is better than all of the templates it 3428 // has been compared to. 3429 UnresolvedSetIterator Best = SpecBegin; 3430 FunctionTemplateDecl *BestTemplate 3431 = cast<FunctionDecl>(*Best)->getPrimaryTemplate(); 3432 assert(BestTemplate && "Not a function template specialization?"); 3433 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) { 3434 FunctionTemplateDecl *Challenger 3435 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 3436 assert(Challenger && "Not a function template specialization?"); 3437 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 3438 Loc, TPOC, NumCallArguments), 3439 Challenger)) { 3440 Best = I; 3441 BestTemplate = Challenger; 3442 } 3443 } 3444 3445 // Make sure that the "best" function template is more specialized than all 3446 // of the others. 3447 bool Ambiguous = false; 3448 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 3449 FunctionTemplateDecl *Challenger 3450 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 3451 if (I != Best && 3452 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 3453 Loc, TPOC, NumCallArguments), 3454 BestTemplate)) { 3455 Ambiguous = true; 3456 break; 3457 } 3458 } 3459 3460 if (!Ambiguous) { 3461 // We found an answer. Return it. 3462 return Best; 3463 } 3464 3465 // Diagnose the ambiguity. 3466 if (Complain) 3467 Diag(Loc, AmbigDiag); 3468 3469 if (Complain) 3470 // FIXME: Can we order the candidates in some sane way? 3471 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) 3472 Diag((*I)->getLocation(), CandidateDiag) 3473 << getTemplateArgumentBindingsText( 3474 cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(), 3475 *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs()); 3476 3477 return SpecEnd; 3478} 3479 3480/// \brief Returns the more specialized class template partial specialization 3481/// according to the rules of partial ordering of class template partial 3482/// specializations (C++ [temp.class.order]). 3483/// 3484/// \param PS1 the first class template partial specialization 3485/// 3486/// \param PS2 the second class template partial specialization 3487/// 3488/// \returns the more specialized class template partial specialization. If 3489/// neither partial specialization is more specialized, returns NULL. 3490ClassTemplatePartialSpecializationDecl * 3491Sema::getMoreSpecializedPartialSpecialization( 3492 ClassTemplatePartialSpecializationDecl *PS1, 3493 ClassTemplatePartialSpecializationDecl *PS2, 3494 SourceLocation Loc) { 3495 // C++ [temp.class.order]p1: 3496 // For two class template partial specializations, the first is at least as 3497 // specialized as the second if, given the following rewrite to two 3498 // function templates, the first function template is at least as 3499 // specialized as the second according to the ordering rules for function 3500 // templates (14.6.6.2): 3501 // - the first function template has the same template parameters as the 3502 // first partial specialization and has a single function parameter 3503 // whose type is a class template specialization with the template 3504 // arguments of the first partial specialization, and 3505 // - the second function template has the same template parameters as the 3506 // second partial specialization and has a single function parameter 3507 // whose type is a class template specialization with the template 3508 // arguments of the second partial specialization. 3509 // 3510 // Rather than synthesize function templates, we merely perform the 3511 // equivalent partial ordering by performing deduction directly on 3512 // the template arguments of the class template partial 3513 // specializations. This computation is slightly simpler than the 3514 // general problem of function template partial ordering, because 3515 // class template partial specializations are more constrained. We 3516 // know that every template parameter is deducible from the class 3517 // template partial specialization's template arguments, for 3518 // example. 3519 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 3520 TemplateDeductionInfo Info(Context, Loc); 3521 3522 QualType PT1 = PS1->getInjectedSpecializationType(); 3523 QualType PT2 = PS2->getInjectedSpecializationType(); 3524 3525 // Determine whether PS1 is at least as specialized as PS2 3526 Deduced.resize(PS2->getTemplateParameters()->size()); 3527 bool Better1 = !::DeduceTemplateArguments(*this, PS2->getTemplateParameters(), 3528 PT2, PT1, Info, Deduced, TDF_None, 3529 /*PartialOrdering=*/true, 3530 /*RefParamComparisons=*/0); 3531 if (Better1) { 3532 InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2, 3533 Deduced.data(), Deduced.size(), Info); 3534 Better1 = !::FinishTemplateArgumentDeduction(*this, PS2, 3535 PS1->getTemplateArgs(), 3536 Deduced, Info); 3537 } 3538 3539 // Determine whether PS2 is at least as specialized as PS1 3540 Deduced.clear(); 3541 Deduced.resize(PS1->getTemplateParameters()->size()); 3542 bool Better2 = !::DeduceTemplateArguments(*this, PS1->getTemplateParameters(), 3543 PT1, PT2, Info, Deduced, TDF_None, 3544 /*PartialOrdering=*/true, 3545 /*RefParamComparisons=*/0); 3546 if (Better2) { 3547 InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1, 3548 Deduced.data(), Deduced.size(), Info); 3549 Better2 = !::FinishTemplateArgumentDeduction(*this, PS1, 3550 PS2->getTemplateArgs(), 3551 Deduced, Info); 3552 } 3553 3554 if (Better1 == Better2) 3555 return 0; 3556 3557 return Better1? PS1 : PS2; 3558} 3559 3560static void 3561MarkUsedTemplateParameters(Sema &SemaRef, 3562 const TemplateArgument &TemplateArg, 3563 bool OnlyDeduced, 3564 unsigned Depth, 3565 llvm::SmallVectorImpl<bool> &Used); 3566 3567/// \brief Mark the template parameters that are used by the given 3568/// expression. 3569static void 3570MarkUsedTemplateParameters(Sema &SemaRef, 3571 const Expr *E, 3572 bool OnlyDeduced, 3573 unsigned Depth, 3574 llvm::SmallVectorImpl<bool> &Used) { 3575 // We can deduce from a pack expansion. 3576 if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E)) 3577 E = Expansion->getPattern(); 3578 3579 // Skip through any implicit casts we added while type-checking. 3580 while (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E)) 3581 E = ICE->getSubExpr(); 3582 3583 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to 3584 // find other occurrences of template parameters. 3585 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E); 3586 if (!DRE) 3587 return; 3588 3589 const NonTypeTemplateParmDecl *NTTP 3590 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 3591 if (!NTTP) 3592 return; 3593 3594 if (NTTP->getDepth() == Depth) 3595 Used[NTTP->getIndex()] = true; 3596} 3597 3598/// \brief Mark the template parameters that are used by the given 3599/// nested name specifier. 3600static void 3601MarkUsedTemplateParameters(Sema &SemaRef, 3602 NestedNameSpecifier *NNS, 3603 bool OnlyDeduced, 3604 unsigned Depth, 3605 llvm::SmallVectorImpl<bool> &Used) { 3606 if (!NNS) 3607 return; 3608 3609 MarkUsedTemplateParameters(SemaRef, NNS->getPrefix(), OnlyDeduced, Depth, 3610 Used); 3611 MarkUsedTemplateParameters(SemaRef, QualType(NNS->getAsType(), 0), 3612 OnlyDeduced, Depth, Used); 3613} 3614 3615/// \brief Mark the template parameters that are used by the given 3616/// template name. 3617static void 3618MarkUsedTemplateParameters(Sema &SemaRef, 3619 TemplateName Name, 3620 bool OnlyDeduced, 3621 unsigned Depth, 3622 llvm::SmallVectorImpl<bool> &Used) { 3623 if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 3624 if (TemplateTemplateParmDecl *TTP 3625 = dyn_cast<TemplateTemplateParmDecl>(Template)) { 3626 if (TTP->getDepth() == Depth) 3627 Used[TTP->getIndex()] = true; 3628 } 3629 return; 3630 } 3631 3632 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) 3633 MarkUsedTemplateParameters(SemaRef, QTN->getQualifier(), OnlyDeduced, 3634 Depth, Used); 3635 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 3636 MarkUsedTemplateParameters(SemaRef, DTN->getQualifier(), OnlyDeduced, 3637 Depth, Used); 3638} 3639 3640/// \brief Mark the template parameters that are used by the given 3641/// type. 3642static void 3643MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 3644 bool OnlyDeduced, 3645 unsigned Depth, 3646 llvm::SmallVectorImpl<bool> &Used) { 3647 if (T.isNull()) 3648 return; 3649 3650 // Non-dependent types have nothing deducible 3651 if (!T->isDependentType()) 3652 return; 3653 3654 T = SemaRef.Context.getCanonicalType(T); 3655 switch (T->getTypeClass()) { 3656 case Type::Pointer: 3657 MarkUsedTemplateParameters(SemaRef, 3658 cast<PointerType>(T)->getPointeeType(), 3659 OnlyDeduced, 3660 Depth, 3661 Used); 3662 break; 3663 3664 case Type::BlockPointer: 3665 MarkUsedTemplateParameters(SemaRef, 3666 cast<BlockPointerType>(T)->getPointeeType(), 3667 OnlyDeduced, 3668 Depth, 3669 Used); 3670 break; 3671 3672 case Type::LValueReference: 3673 case Type::RValueReference: 3674 MarkUsedTemplateParameters(SemaRef, 3675 cast<ReferenceType>(T)->getPointeeType(), 3676 OnlyDeduced, 3677 Depth, 3678 Used); 3679 break; 3680 3681 case Type::MemberPointer: { 3682 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 3683 MarkUsedTemplateParameters(SemaRef, MemPtr->getPointeeType(), OnlyDeduced, 3684 Depth, Used); 3685 MarkUsedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0), 3686 OnlyDeduced, Depth, Used); 3687 break; 3688 } 3689 3690 case Type::DependentSizedArray: 3691 MarkUsedTemplateParameters(SemaRef, 3692 cast<DependentSizedArrayType>(T)->getSizeExpr(), 3693 OnlyDeduced, Depth, Used); 3694 // Fall through to check the element type 3695 3696 case Type::ConstantArray: 3697 case Type::IncompleteArray: 3698 MarkUsedTemplateParameters(SemaRef, 3699 cast<ArrayType>(T)->getElementType(), 3700 OnlyDeduced, Depth, Used); 3701 break; 3702 3703 case Type::Vector: 3704 case Type::ExtVector: 3705 MarkUsedTemplateParameters(SemaRef, 3706 cast<VectorType>(T)->getElementType(), 3707 OnlyDeduced, Depth, Used); 3708 break; 3709 3710 case Type::DependentSizedExtVector: { 3711 const DependentSizedExtVectorType *VecType 3712 = cast<DependentSizedExtVectorType>(T); 3713 MarkUsedTemplateParameters(SemaRef, VecType->getElementType(), OnlyDeduced, 3714 Depth, Used); 3715 MarkUsedTemplateParameters(SemaRef, VecType->getSizeExpr(), OnlyDeduced, 3716 Depth, Used); 3717 break; 3718 } 3719 3720 case Type::FunctionProto: { 3721 const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 3722 MarkUsedTemplateParameters(SemaRef, Proto->getResultType(), OnlyDeduced, 3723 Depth, Used); 3724 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I) 3725 MarkUsedTemplateParameters(SemaRef, Proto->getArgType(I), OnlyDeduced, 3726 Depth, Used); 3727 break; 3728 } 3729 3730 case Type::TemplateTypeParm: { 3731 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T); 3732 if (TTP->getDepth() == Depth) 3733 Used[TTP->getIndex()] = true; 3734 break; 3735 } 3736 3737 case Type::SubstTemplateTypeParmPack: { 3738 const SubstTemplateTypeParmPackType *Subst 3739 = cast<SubstTemplateTypeParmPackType>(T); 3740 MarkUsedTemplateParameters(SemaRef, 3741 QualType(Subst->getReplacedParameter(), 0), 3742 OnlyDeduced, Depth, Used); 3743 MarkUsedTemplateParameters(SemaRef, Subst->getArgumentPack(), 3744 OnlyDeduced, Depth, Used); 3745 break; 3746 } 3747 3748 case Type::InjectedClassName: 3749 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType(); 3750 // fall through 3751 3752 case Type::TemplateSpecialization: { 3753 const TemplateSpecializationType *Spec 3754 = cast<TemplateSpecializationType>(T); 3755 MarkUsedTemplateParameters(SemaRef, Spec->getTemplateName(), OnlyDeduced, 3756 Depth, Used); 3757 3758 // C++0x [temp.deduct.type]p9: 3759 // If the template argument list of P contains a pack expansion that is not 3760 // the last template argument, the entire template argument list is a 3761 // non-deduced context. 3762 if (OnlyDeduced && 3763 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 3764 break; 3765 3766 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 3767 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 3768 Used); 3769 break; 3770 } 3771 3772 case Type::Complex: 3773 if (!OnlyDeduced) 3774 MarkUsedTemplateParameters(SemaRef, 3775 cast<ComplexType>(T)->getElementType(), 3776 OnlyDeduced, Depth, Used); 3777 break; 3778 3779 case Type::DependentName: 3780 if (!OnlyDeduced) 3781 MarkUsedTemplateParameters(SemaRef, 3782 cast<DependentNameType>(T)->getQualifier(), 3783 OnlyDeduced, Depth, Used); 3784 break; 3785 3786 case Type::DependentTemplateSpecialization: { 3787 const DependentTemplateSpecializationType *Spec 3788 = cast<DependentTemplateSpecializationType>(T); 3789 if (!OnlyDeduced) 3790 MarkUsedTemplateParameters(SemaRef, Spec->getQualifier(), 3791 OnlyDeduced, Depth, Used); 3792 3793 // C++0x [temp.deduct.type]p9: 3794 // If the template argument list of P contains a pack expansion that is not 3795 // the last template argument, the entire template argument list is a 3796 // non-deduced context. 3797 if (OnlyDeduced && 3798 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 3799 break; 3800 3801 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 3802 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 3803 Used); 3804 break; 3805 } 3806 3807 case Type::TypeOf: 3808 if (!OnlyDeduced) 3809 MarkUsedTemplateParameters(SemaRef, 3810 cast<TypeOfType>(T)->getUnderlyingType(), 3811 OnlyDeduced, Depth, Used); 3812 break; 3813 3814 case Type::TypeOfExpr: 3815 if (!OnlyDeduced) 3816 MarkUsedTemplateParameters(SemaRef, 3817 cast<TypeOfExprType>(T)->getUnderlyingExpr(), 3818 OnlyDeduced, Depth, Used); 3819 break; 3820 3821 case Type::Decltype: 3822 if (!OnlyDeduced) 3823 MarkUsedTemplateParameters(SemaRef, 3824 cast<DecltypeType>(T)->getUnderlyingExpr(), 3825 OnlyDeduced, Depth, Used); 3826 break; 3827 3828 case Type::PackExpansion: 3829 MarkUsedTemplateParameters(SemaRef, 3830 cast<PackExpansionType>(T)->getPattern(), 3831 OnlyDeduced, Depth, Used); 3832 break; 3833 3834 case Type::Auto: 3835 MarkUsedTemplateParameters(SemaRef, 3836 cast<AutoType>(T)->getDeducedType(), 3837 OnlyDeduced, Depth, Used); 3838 3839 // None of these types have any template parameters in them. 3840 case Type::Builtin: 3841 case Type::VariableArray: 3842 case Type::FunctionNoProto: 3843 case Type::Record: 3844 case Type::Enum: 3845 case Type::ObjCInterface: 3846 case Type::ObjCObject: 3847 case Type::ObjCObjectPointer: 3848 case Type::UnresolvedUsing: 3849#define TYPE(Class, Base) 3850#define ABSTRACT_TYPE(Class, Base) 3851#define DEPENDENT_TYPE(Class, Base) 3852#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 3853#include "clang/AST/TypeNodes.def" 3854 break; 3855 } 3856} 3857 3858/// \brief Mark the template parameters that are used by this 3859/// template argument. 3860static void 3861MarkUsedTemplateParameters(Sema &SemaRef, 3862 const TemplateArgument &TemplateArg, 3863 bool OnlyDeduced, 3864 unsigned Depth, 3865 llvm::SmallVectorImpl<bool> &Used) { 3866 switch (TemplateArg.getKind()) { 3867 case TemplateArgument::Null: 3868 case TemplateArgument::Integral: 3869 case TemplateArgument::Declaration: 3870 break; 3871 3872 case TemplateArgument::Type: 3873 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsType(), OnlyDeduced, 3874 Depth, Used); 3875 break; 3876 3877 case TemplateArgument::Template: 3878 case TemplateArgument::TemplateExpansion: 3879 MarkUsedTemplateParameters(SemaRef, 3880 TemplateArg.getAsTemplateOrTemplatePattern(), 3881 OnlyDeduced, Depth, Used); 3882 break; 3883 3884 case TemplateArgument::Expression: 3885 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsExpr(), OnlyDeduced, 3886 Depth, Used); 3887 break; 3888 3889 case TemplateArgument::Pack: 3890 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(), 3891 PEnd = TemplateArg.pack_end(); 3892 P != PEnd; ++P) 3893 MarkUsedTemplateParameters(SemaRef, *P, OnlyDeduced, Depth, Used); 3894 break; 3895 } 3896} 3897 3898/// \brief Mark the template parameters can be deduced by the given 3899/// template argument list. 3900/// 3901/// \param TemplateArgs the template argument list from which template 3902/// parameters will be deduced. 3903/// 3904/// \param Deduced a bit vector whose elements will be set to \c true 3905/// to indicate when the corresponding template parameter will be 3906/// deduced. 3907void 3908Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 3909 bool OnlyDeduced, unsigned Depth, 3910 llvm::SmallVectorImpl<bool> &Used) { 3911 // C++0x [temp.deduct.type]p9: 3912 // If the template argument list of P contains a pack expansion that is not 3913 // the last template argument, the entire template argument list is a 3914 // non-deduced context. 3915 if (OnlyDeduced && 3916 hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size())) 3917 return; 3918 3919 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 3920 ::MarkUsedTemplateParameters(*this, TemplateArgs[I], OnlyDeduced, 3921 Depth, Used); 3922} 3923 3924/// \brief Marks all of the template parameters that will be deduced by a 3925/// call to the given function template. 3926void 3927Sema::MarkDeducedTemplateParameters(FunctionTemplateDecl *FunctionTemplate, 3928 llvm::SmallVectorImpl<bool> &Deduced) { 3929 TemplateParameterList *TemplateParams 3930 = FunctionTemplate->getTemplateParameters(); 3931 Deduced.clear(); 3932 Deduced.resize(TemplateParams->size()); 3933 3934 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 3935 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 3936 ::MarkUsedTemplateParameters(*this, Function->getParamDecl(I)->getType(), 3937 true, TemplateParams->getDepth(), Deduced); 3938} 3939