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