SemaTemplateDeduction.cpp revision 9b1317531d376738fd6631291b0a04109c76a63b
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 TemplateArgumentLoc DefArg 2708 = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate, 2709 FunctionTemplate->getLocation(), 2710 FunctionTemplate->getSourceRange().getEnd(), 2711 Param, 2712 Builder); 2713 2714 // If there was no default argument, deduction is incomplete. 2715 if (DefArg.getArgument().isNull()) { 2716 Info.Param = makeTemplateParameter( 2717 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 2718 return TDK_Incomplete; 2719 } 2720 2721 // Check whether we can actually use the default argument. 2722 if (CheckTemplateArgument(Param, DefArg, 2723 FunctionTemplate, 2724 FunctionTemplate->getLocation(), 2725 FunctionTemplate->getSourceRange().getEnd(), 2726 0, Builder, 2727 CTAK_Specified)) { 2728 Info.Param = makeTemplateParameter( 2729 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 2730 // FIXME: These template arguments are temporary. Free them! 2731 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 2732 Builder.size())); 2733 return TDK_SubstitutionFailure; 2734 } 2735 2736 // If we get here, we successfully used the default template argument. 2737 } 2738 2739 // Form the template argument list from the deduced template arguments. 2740 TemplateArgumentList *DeducedArgumentList 2741 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size()); 2742 Info.reset(DeducedArgumentList); 2743 2744 // Substitute the deduced template arguments into the function template 2745 // declaration to produce the function template specialization. 2746 DeclContext *Owner = FunctionTemplate->getDeclContext(); 2747 if (FunctionTemplate->getFriendObjectKind()) 2748 Owner = FunctionTemplate->getLexicalDeclContext(); 2749 Specialization = cast_or_null<FunctionDecl>( 2750 SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner, 2751 MultiLevelTemplateArgumentList(*DeducedArgumentList))); 2752 if (!Specialization || Specialization->isInvalidDecl()) 2753 return TDK_SubstitutionFailure; 2754 2755 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() == 2756 FunctionTemplate->getCanonicalDecl()); 2757 2758 // If the template argument list is owned by the function template 2759 // specialization, release it. 2760 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList && 2761 !Trap.hasErrorOccurred()) 2762 Info.take(); 2763 2764 // There may have been an error that did not prevent us from constructing a 2765 // declaration. Mark the declaration invalid and return with a substitution 2766 // failure. 2767 if (Trap.hasErrorOccurred()) { 2768 Specialization->setInvalidDecl(true); 2769 return TDK_SubstitutionFailure; 2770 } 2771 2772 if (OriginalCallArgs) { 2773 // C++ [temp.deduct.call]p4: 2774 // In general, the deduction process attempts to find template argument 2775 // values that will make the deduced A identical to A (after the type A 2776 // is transformed as described above). [...] 2777 for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) { 2778 OriginalCallArg OriginalArg = (*OriginalCallArgs)[I]; 2779 unsigned ParamIdx = OriginalArg.ArgIdx; 2780 2781 if (ParamIdx >= Specialization->getNumParams()) 2782 continue; 2783 2784 QualType DeducedA = Specialization->getParamDecl(ParamIdx)->getType(); 2785 if (CheckOriginalCallArgDeduction(*this, OriginalArg, DeducedA)) 2786 return Sema::TDK_SubstitutionFailure; 2787 } 2788 } 2789 2790 // If we suppressed any diagnostics while performing template argument 2791 // deduction, and if we haven't already instantiated this declaration, 2792 // keep track of these diagnostics. They'll be emitted if this specialization 2793 // is actually used. 2794 if (Info.diag_begin() != Info.diag_end()) { 2795 llvm::DenseMap<Decl *, SmallVector<PartialDiagnosticAt, 1> >::iterator 2796 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl()); 2797 if (Pos == SuppressedDiagnostics.end()) 2798 SuppressedDiagnostics[Specialization->getCanonicalDecl()] 2799 .append(Info.diag_begin(), Info.diag_end()); 2800 } 2801 2802 return TDK_Success; 2803} 2804 2805/// Gets the type of a function for template-argument-deducton 2806/// purposes when it's considered as part of an overload set. 2807static QualType GetTypeOfFunction(ASTContext &Context, 2808 const OverloadExpr::FindResult &R, 2809 FunctionDecl *Fn) { 2810 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn)) 2811 if (Method->isInstance()) { 2812 // An instance method that's referenced in a form that doesn't 2813 // look like a member pointer is just invalid. 2814 if (!R.HasFormOfMemberPointer) return QualType(); 2815 2816 return Context.getMemberPointerType(Fn->getType(), 2817 Context.getTypeDeclType(Method->getParent()).getTypePtr()); 2818 } 2819 2820 if (!R.IsAddressOfOperand) return Fn->getType(); 2821 return Context.getPointerType(Fn->getType()); 2822} 2823 2824/// Apply the deduction rules for overload sets. 2825/// 2826/// \return the null type if this argument should be treated as an 2827/// undeduced context 2828static QualType 2829ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams, 2830 Expr *Arg, QualType ParamType, 2831 bool ParamWasReference) { 2832 2833 OverloadExpr::FindResult R = OverloadExpr::find(Arg); 2834 2835 OverloadExpr *Ovl = R.Expression; 2836 2837 // C++0x [temp.deduct.call]p4 2838 unsigned TDF = 0; 2839 if (ParamWasReference) 2840 TDF |= TDF_ParamWithReferenceType; 2841 if (R.IsAddressOfOperand) 2842 TDF |= TDF_IgnoreQualifiers; 2843 2844 // C++0x [temp.deduct.call]p6: 2845 // When P is a function type, pointer to function type, or pointer 2846 // to member function type: 2847 2848 if (!ParamType->isFunctionType() && 2849 !ParamType->isFunctionPointerType() && 2850 !ParamType->isMemberFunctionPointerType()) { 2851 if (Ovl->hasExplicitTemplateArgs()) { 2852 // But we can still look for an explicit specialization. 2853 if (FunctionDecl *ExplicitSpec 2854 = S.ResolveSingleFunctionTemplateSpecialization(Ovl)) 2855 return GetTypeOfFunction(S.Context, R, ExplicitSpec); 2856 } 2857 2858 return QualType(); 2859 } 2860 2861 // Gather the explicit template arguments, if any. 2862 TemplateArgumentListInfo ExplicitTemplateArgs; 2863 if (Ovl->hasExplicitTemplateArgs()) 2864 Ovl->getExplicitTemplateArgs().copyInto(ExplicitTemplateArgs); 2865 QualType Match; 2866 for (UnresolvedSetIterator I = Ovl->decls_begin(), 2867 E = Ovl->decls_end(); I != E; ++I) { 2868 NamedDecl *D = (*I)->getUnderlyingDecl(); 2869 2870 if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) { 2871 // - If the argument is an overload set containing one or more 2872 // function templates, the parameter is treated as a 2873 // non-deduced context. 2874 if (!Ovl->hasExplicitTemplateArgs()) 2875 return QualType(); 2876 2877 // Otherwise, see if we can resolve a function type 2878 FunctionDecl *Specialization = 0; 2879 TemplateDeductionInfo Info(Ovl->getNameLoc()); 2880 if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs, 2881 Specialization, Info)) 2882 continue; 2883 2884 D = Specialization; 2885 } 2886 2887 FunctionDecl *Fn = cast<FunctionDecl>(D); 2888 QualType ArgType = GetTypeOfFunction(S.Context, R, Fn); 2889 if (ArgType.isNull()) continue; 2890 2891 // Function-to-pointer conversion. 2892 if (!ParamWasReference && ParamType->isPointerType() && 2893 ArgType->isFunctionType()) 2894 ArgType = S.Context.getPointerType(ArgType); 2895 2896 // - If the argument is an overload set (not containing function 2897 // templates), trial argument deduction is attempted using each 2898 // of the members of the set. If deduction succeeds for only one 2899 // of the overload set members, that member is used as the 2900 // argument value for the deduction. If deduction succeeds for 2901 // more than one member of the overload set the parameter is 2902 // treated as a non-deduced context. 2903 2904 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2: 2905 // Type deduction is done independently for each P/A pair, and 2906 // the deduced template argument values are then combined. 2907 // So we do not reject deductions which were made elsewhere. 2908 SmallVector<DeducedTemplateArgument, 8> 2909 Deduced(TemplateParams->size()); 2910 TemplateDeductionInfo Info(Ovl->getNameLoc()); 2911 Sema::TemplateDeductionResult Result 2912 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType, 2913 ArgType, Info, Deduced, TDF); 2914 if (Result) continue; 2915 if (!Match.isNull()) return QualType(); 2916 Match = ArgType; 2917 } 2918 2919 return Match; 2920} 2921 2922/// \brief Perform the adjustments to the parameter and argument types 2923/// described in C++ [temp.deduct.call]. 2924/// 2925/// \returns true if the caller should not attempt to perform any template 2926/// argument deduction based on this P/A pair because the argument is an 2927/// overloaded function set that could not be resolved. 2928static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S, 2929 TemplateParameterList *TemplateParams, 2930 QualType &ParamType, 2931 QualType &ArgType, 2932 Expr *Arg, 2933 unsigned &TDF) { 2934 // C++0x [temp.deduct.call]p3: 2935 // If P is a cv-qualified type, the top level cv-qualifiers of P's type 2936 // are ignored for type deduction. 2937 if (ParamType.hasQualifiers()) 2938 ParamType = ParamType.getUnqualifiedType(); 2939 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>(); 2940 if (ParamRefType) { 2941 QualType PointeeType = ParamRefType->getPointeeType(); 2942 2943 // If the argument has incomplete array type, try to complete its type. 2944 if (ArgType->isIncompleteArrayType() && !S.RequireCompleteExprType(Arg, 0)) 2945 ArgType = Arg->getType(); 2946 2947 // [C++0x] If P is an rvalue reference to a cv-unqualified 2948 // template parameter and the argument is an lvalue, the type 2949 // "lvalue reference to A" is used in place of A for type 2950 // deduction. 2951 if (isa<RValueReferenceType>(ParamType)) { 2952 if (!PointeeType.getQualifiers() && 2953 isa<TemplateTypeParmType>(PointeeType) && 2954 Arg->Classify(S.Context).isLValue() && 2955 Arg->getType() != S.Context.OverloadTy && 2956 Arg->getType() != S.Context.BoundMemberTy) 2957 ArgType = S.Context.getLValueReferenceType(ArgType); 2958 } 2959 2960 // [...] If P is a reference type, the type referred to by P is used 2961 // for type deduction. 2962 ParamType = PointeeType; 2963 } 2964 2965 // Overload sets usually make this parameter an undeduced 2966 // context, but there are sometimes special circumstances. 2967 if (ArgType == S.Context.OverloadTy) { 2968 ArgType = ResolveOverloadForDeduction(S, TemplateParams, 2969 Arg, ParamType, 2970 ParamRefType != 0); 2971 if (ArgType.isNull()) 2972 return true; 2973 } 2974 2975 if (ParamRefType) { 2976 // C++0x [temp.deduct.call]p3: 2977 // [...] If P is of the form T&&, where T is a template parameter, and 2978 // the argument is an lvalue, the type A& is used in place of A for 2979 // type deduction. 2980 if (ParamRefType->isRValueReferenceType() && 2981 ParamRefType->getAs<TemplateTypeParmType>() && 2982 Arg->isLValue()) 2983 ArgType = S.Context.getLValueReferenceType(ArgType); 2984 } else { 2985 // C++ [temp.deduct.call]p2: 2986 // If P is not a reference type: 2987 // - If A is an array type, the pointer type produced by the 2988 // array-to-pointer standard conversion (4.2) is used in place of 2989 // A for type deduction; otherwise, 2990 if (ArgType->isArrayType()) 2991 ArgType = S.Context.getArrayDecayedType(ArgType); 2992 // - If A is a function type, the pointer type produced by the 2993 // function-to-pointer standard conversion (4.3) is used in place 2994 // of A for type deduction; otherwise, 2995 else if (ArgType->isFunctionType()) 2996 ArgType = S.Context.getPointerType(ArgType); 2997 else { 2998 // - If A is a cv-qualified type, the top level cv-qualifiers of A's 2999 // type are ignored for type deduction. 3000 ArgType = ArgType.getUnqualifiedType(); 3001 } 3002 } 3003 3004 // C++0x [temp.deduct.call]p4: 3005 // In general, the deduction process attempts to find template argument 3006 // values that will make the deduced A identical to A (after the type A 3007 // is transformed as described above). [...] 3008 TDF = TDF_SkipNonDependent; 3009 3010 // - If the original P is a reference type, the deduced A (i.e., the 3011 // type referred to by the reference) can be more cv-qualified than 3012 // the transformed A. 3013 if (ParamRefType) 3014 TDF |= TDF_ParamWithReferenceType; 3015 // - The transformed A can be another pointer or pointer to member 3016 // type that can be converted to the deduced A via a qualification 3017 // conversion (4.4). 3018 if (ArgType->isPointerType() || ArgType->isMemberPointerType() || 3019 ArgType->isObjCObjectPointerType()) 3020 TDF |= TDF_IgnoreQualifiers; 3021 // - If P is a class and P has the form simple-template-id, then the 3022 // transformed A can be a derived class of the deduced A. Likewise, 3023 // if P is a pointer to a class of the form simple-template-id, the 3024 // transformed A can be a pointer to a derived class pointed to by 3025 // the deduced A. 3026 if (isSimpleTemplateIdType(ParamType) || 3027 (isa<PointerType>(ParamType) && 3028 isSimpleTemplateIdType( 3029 ParamType->getAs<PointerType>()->getPointeeType()))) 3030 TDF |= TDF_DerivedClass; 3031 3032 return false; 3033} 3034 3035static bool hasDeducibleTemplateParameters(Sema &S, 3036 FunctionTemplateDecl *FunctionTemplate, 3037 QualType T); 3038 3039/// \brief Perform template argument deduction by matching a parameter type 3040/// against a single expression, where the expression is an element of 3041/// an initializer list that was originally matched against a parameter 3042/// of type \c initializer_list\<ParamType\>. 3043static Sema::TemplateDeductionResult 3044DeduceTemplateArgumentByListElement(Sema &S, 3045 TemplateParameterList *TemplateParams, 3046 QualType ParamType, Expr *Arg, 3047 TemplateDeductionInfo &Info, 3048 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 3049 unsigned TDF) { 3050 // Handle the case where an init list contains another init list as the 3051 // element. 3052 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) { 3053 QualType X; 3054 if (!S.isStdInitializerList(ParamType.getNonReferenceType(), &X)) 3055 return Sema::TDK_Success; // Just ignore this expression. 3056 3057 // Recurse down into the init list. 3058 for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) { 3059 if (Sema::TemplateDeductionResult Result = 3060 DeduceTemplateArgumentByListElement(S, TemplateParams, X, 3061 ILE->getInit(i), 3062 Info, Deduced, TDF)) 3063 return Result; 3064 } 3065 return Sema::TDK_Success; 3066 } 3067 3068 // For all other cases, just match by type. 3069 QualType ArgType = Arg->getType(); 3070 if (AdjustFunctionParmAndArgTypesForDeduction(S, TemplateParams, ParamType, 3071 ArgType, Arg, TDF)) { 3072 Info.Expression = Arg; 3073 return Sema::TDK_FailedOverloadResolution; 3074 } 3075 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType, 3076 ArgType, Info, Deduced, TDF); 3077} 3078 3079/// \brief Perform template argument deduction from a function call 3080/// (C++ [temp.deduct.call]). 3081/// 3082/// \param FunctionTemplate the function template for which we are performing 3083/// template argument deduction. 3084/// 3085/// \param ExplicitTemplateArgs the explicit template arguments provided 3086/// for this call. 3087/// 3088/// \param Args the function call arguments 3089/// 3090/// \param Specialization if template argument deduction was successful, 3091/// this will be set to the function template specialization produced by 3092/// template argument deduction. 3093/// 3094/// \param Info the argument will be updated to provide additional information 3095/// about template argument deduction. 3096/// 3097/// \returns the result of template argument deduction. 3098Sema::TemplateDeductionResult 3099Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 3100 TemplateArgumentListInfo *ExplicitTemplateArgs, 3101 llvm::ArrayRef<Expr *> Args, 3102 FunctionDecl *&Specialization, 3103 TemplateDeductionInfo &Info) { 3104 if (FunctionTemplate->isInvalidDecl()) 3105 return TDK_Invalid; 3106 3107 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 3108 3109 // C++ [temp.deduct.call]p1: 3110 // Template argument deduction is done by comparing each function template 3111 // parameter type (call it P) with the type of the corresponding argument 3112 // of the call (call it A) as described below. 3113 unsigned CheckArgs = Args.size(); 3114 if (Args.size() < Function->getMinRequiredArguments()) 3115 return TDK_TooFewArguments; 3116 else if (Args.size() > Function->getNumParams()) { 3117 const FunctionProtoType *Proto 3118 = Function->getType()->getAs<FunctionProtoType>(); 3119 if (Proto->isTemplateVariadic()) 3120 /* Do nothing */; 3121 else if (Proto->isVariadic()) 3122 CheckArgs = Function->getNumParams(); 3123 else 3124 return TDK_TooManyArguments; 3125 } 3126 3127 // The types of the parameters from which we will perform template argument 3128 // deduction. 3129 LocalInstantiationScope InstScope(*this); 3130 TemplateParameterList *TemplateParams 3131 = FunctionTemplate->getTemplateParameters(); 3132 SmallVector<DeducedTemplateArgument, 4> Deduced; 3133 SmallVector<QualType, 4> ParamTypes; 3134 unsigned NumExplicitlySpecified = 0; 3135 if (ExplicitTemplateArgs) { 3136 TemplateDeductionResult Result = 3137 SubstituteExplicitTemplateArguments(FunctionTemplate, 3138 *ExplicitTemplateArgs, 3139 Deduced, 3140 ParamTypes, 3141 0, 3142 Info); 3143 if (Result) 3144 return Result; 3145 3146 NumExplicitlySpecified = Deduced.size(); 3147 } else { 3148 // Just fill in the parameter types from the function declaration. 3149 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 3150 ParamTypes.push_back(Function->getParamDecl(I)->getType()); 3151 } 3152 3153 // Deduce template arguments from the function parameters. 3154 Deduced.resize(TemplateParams->size()); 3155 unsigned ArgIdx = 0; 3156 SmallVector<OriginalCallArg, 4> OriginalCallArgs; 3157 for (unsigned ParamIdx = 0, NumParams = ParamTypes.size(); 3158 ParamIdx != NumParams; ++ParamIdx) { 3159 QualType OrigParamType = ParamTypes[ParamIdx]; 3160 QualType ParamType = OrigParamType; 3161 3162 const PackExpansionType *ParamExpansion 3163 = dyn_cast<PackExpansionType>(ParamType); 3164 if (!ParamExpansion) { 3165 // Simple case: matching a function parameter to a function argument. 3166 if (ArgIdx >= CheckArgs) 3167 break; 3168 3169 Expr *Arg = Args[ArgIdx++]; 3170 QualType ArgType = Arg->getType(); 3171 3172 unsigned TDF = 0; 3173 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams, 3174 ParamType, ArgType, Arg, 3175 TDF)) 3176 continue; 3177 3178 // If we have nothing to deduce, we're done. 3179 if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType)) 3180 continue; 3181 3182 // If the argument is an initializer list ... 3183 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) { 3184 // ... then the parameter is an undeduced context, unless the parameter 3185 // type is (reference to cv) std::initializer_list<P'>, in which case 3186 // deduction is done for each element of the initializer list, and the 3187 // result is the deduced type if it's the same for all elements. 3188 QualType X; 3189 // Removing references was already done. 3190 if (!isStdInitializerList(ParamType, &X)) 3191 continue; 3192 3193 for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) { 3194 if (TemplateDeductionResult Result = 3195 DeduceTemplateArgumentByListElement(*this, TemplateParams, X, 3196 ILE->getInit(i), 3197 Info, Deduced, TDF)) 3198 return Result; 3199 } 3200 // Don't track the argument type, since an initializer list has none. 3201 continue; 3202 } 3203 3204 // Keep track of the argument type and corresponding parameter index, 3205 // so we can check for compatibility between the deduced A and A. 3206 OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx-1, 3207 ArgType)); 3208 3209 if (TemplateDeductionResult Result 3210 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3211 ParamType, ArgType, 3212 Info, Deduced, TDF)) 3213 return Result; 3214 3215 continue; 3216 } 3217 3218 // C++0x [temp.deduct.call]p1: 3219 // For a function parameter pack that occurs at the end of the 3220 // parameter-declaration-list, the type A of each remaining argument of 3221 // the call is compared with the type P of the declarator-id of the 3222 // function parameter pack. Each comparison deduces template arguments 3223 // for subsequent positions in the template parameter packs expanded by 3224 // the function parameter pack. For a function parameter pack that does 3225 // not occur at the end of the parameter-declaration-list, the type of 3226 // the parameter pack is a non-deduced context. 3227 if (ParamIdx + 1 < NumParams) 3228 break; 3229 3230 QualType ParamPattern = ParamExpansion->getPattern(); 3231 SmallVector<unsigned, 2> PackIndices; 3232 { 3233 llvm::SmallBitVector SawIndices(TemplateParams->size()); 3234 SmallVector<UnexpandedParameterPack, 2> Unexpanded; 3235 collectUnexpandedParameterPacks(ParamPattern, Unexpanded); 3236 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) { 3237 unsigned Depth, Index; 3238 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]); 3239 if (Depth == 0 && !SawIndices[Index]) { 3240 SawIndices[Index] = true; 3241 PackIndices.push_back(Index); 3242 } 3243 } 3244 } 3245 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?"); 3246 3247 // Keep track of the deduced template arguments for each parameter pack 3248 // expanded by this pack expansion (the outer index) and for each 3249 // template argument (the inner SmallVectors). 3250 SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2> 3251 NewlyDeducedPacks(PackIndices.size()); 3252 SmallVector<DeducedTemplateArgument, 2> 3253 SavedPacks(PackIndices.size()); 3254 PrepareArgumentPackDeduction(*this, Deduced, PackIndices, SavedPacks, 3255 NewlyDeducedPacks); 3256 bool HasAnyArguments = false; 3257 for (; ArgIdx < Args.size(); ++ArgIdx) { 3258 HasAnyArguments = true; 3259 3260 QualType OrigParamType = ParamPattern; 3261 ParamType = OrigParamType; 3262 Expr *Arg = Args[ArgIdx]; 3263 QualType ArgType = Arg->getType(); 3264 3265 unsigned TDF = 0; 3266 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams, 3267 ParamType, ArgType, Arg, 3268 TDF)) { 3269 // We can't actually perform any deduction for this argument, so stop 3270 // deduction at this point. 3271 ++ArgIdx; 3272 break; 3273 } 3274 3275 // As above, initializer lists need special handling. 3276 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) { 3277 QualType X; 3278 if (!isStdInitializerList(ParamType, &X)) { 3279 ++ArgIdx; 3280 break; 3281 } 3282 3283 for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) { 3284 if (TemplateDeductionResult Result = 3285 DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, X, 3286 ILE->getInit(i)->getType(), 3287 Info, Deduced, TDF)) 3288 return Result; 3289 } 3290 } else { 3291 3292 // Keep track of the argument type and corresponding argument index, 3293 // so we can check for compatibility between the deduced A and A. 3294 if (hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType)) 3295 OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx, 3296 ArgType)); 3297 3298 if (TemplateDeductionResult Result 3299 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3300 ParamType, ArgType, Info, 3301 Deduced, TDF)) 3302 return Result; 3303 } 3304 3305 // Capture the deduced template arguments for each parameter pack expanded 3306 // by this pack expansion, add them to the list of arguments we've deduced 3307 // for that pack, then clear out the deduced argument. 3308 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 3309 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]]; 3310 if (!DeducedArg.isNull()) { 3311 NewlyDeducedPacks[I].push_back(DeducedArg); 3312 DeducedArg = DeducedTemplateArgument(); 3313 } 3314 } 3315 } 3316 3317 // Build argument packs for each of the parameter packs expanded by this 3318 // pack expansion. 3319 if (Sema::TemplateDeductionResult Result 3320 = FinishArgumentPackDeduction(*this, TemplateParams, HasAnyArguments, 3321 Deduced, PackIndices, SavedPacks, 3322 NewlyDeducedPacks, Info)) 3323 return Result; 3324 3325 // After we've matching against a parameter pack, we're done. 3326 break; 3327 } 3328 3329 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 3330 NumExplicitlySpecified, 3331 Specialization, Info, &OriginalCallArgs); 3332} 3333 3334/// \brief Deduce template arguments when taking the address of a function 3335/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to 3336/// a template. 3337/// 3338/// \param FunctionTemplate the function template for which we are performing 3339/// template argument deduction. 3340/// 3341/// \param ExplicitTemplateArgs the explicitly-specified template 3342/// arguments. 3343/// 3344/// \param ArgFunctionType the function type that will be used as the 3345/// "argument" type (A) when performing template argument deduction from the 3346/// function template's function type. This type may be NULL, if there is no 3347/// argument type to compare against, in C++0x [temp.arg.explicit]p3. 3348/// 3349/// \param Specialization if template argument deduction was successful, 3350/// this will be set to the function template specialization produced by 3351/// template argument deduction. 3352/// 3353/// \param Info the argument will be updated to provide additional information 3354/// about template argument deduction. 3355/// 3356/// \returns the result of template argument deduction. 3357Sema::TemplateDeductionResult 3358Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 3359 TemplateArgumentListInfo *ExplicitTemplateArgs, 3360 QualType ArgFunctionType, 3361 FunctionDecl *&Specialization, 3362 TemplateDeductionInfo &Info, 3363 bool InOverloadResolution) { 3364 if (FunctionTemplate->isInvalidDecl()) 3365 return TDK_Invalid; 3366 3367 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 3368 TemplateParameterList *TemplateParams 3369 = FunctionTemplate->getTemplateParameters(); 3370 QualType FunctionType = Function->getType(); 3371 3372 // Substitute any explicit template arguments. 3373 LocalInstantiationScope InstScope(*this); 3374 SmallVector<DeducedTemplateArgument, 4> Deduced; 3375 unsigned NumExplicitlySpecified = 0; 3376 SmallVector<QualType, 4> ParamTypes; 3377 if (ExplicitTemplateArgs) { 3378 if (TemplateDeductionResult Result 3379 = SubstituteExplicitTemplateArguments(FunctionTemplate, 3380 *ExplicitTemplateArgs, 3381 Deduced, ParamTypes, 3382 &FunctionType, Info)) 3383 return Result; 3384 3385 NumExplicitlySpecified = Deduced.size(); 3386 } 3387 3388 // Unevaluated SFINAE context. 3389 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 3390 SFINAETrap Trap(*this); 3391 3392 Deduced.resize(TemplateParams->size()); 3393 3394 if (!ArgFunctionType.isNull()) { 3395 unsigned TDF = TDF_TopLevelParameterTypeList; 3396 if (InOverloadResolution) TDF |= TDF_InOverloadResolution; 3397 // Deduce template arguments from the function type. 3398 if (TemplateDeductionResult Result 3399 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3400 FunctionType, ArgFunctionType, 3401 Info, Deduced, TDF)) 3402 return Result; 3403 } 3404 3405 if (TemplateDeductionResult Result 3406 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 3407 NumExplicitlySpecified, 3408 Specialization, Info)) 3409 return Result; 3410 3411 // If the requested function type does not match the actual type of the 3412 // specialization with respect to arguments of compatible pointer to function 3413 // types, template argument deduction fails. 3414 if (!ArgFunctionType.isNull()) { 3415 if (InOverloadResolution && !isSameOrCompatibleFunctionType( 3416 Context.getCanonicalType(Specialization->getType()), 3417 Context.getCanonicalType(ArgFunctionType))) 3418 return TDK_MiscellaneousDeductionFailure; 3419 else if(!InOverloadResolution && 3420 !Context.hasSameType(Specialization->getType(), ArgFunctionType)) 3421 return TDK_MiscellaneousDeductionFailure; 3422 } 3423 3424 return TDK_Success; 3425} 3426 3427/// \brief Deduce template arguments for a templated conversion 3428/// function (C++ [temp.deduct.conv]) and, if successful, produce a 3429/// conversion function template specialization. 3430Sema::TemplateDeductionResult 3431Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 3432 QualType ToType, 3433 CXXConversionDecl *&Specialization, 3434 TemplateDeductionInfo &Info) { 3435 if (FunctionTemplate->isInvalidDecl()) 3436 return TDK_Invalid; 3437 3438 CXXConversionDecl *Conv 3439 = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl()); 3440 QualType FromType = Conv->getConversionType(); 3441 3442 // Canonicalize the types for deduction. 3443 QualType P = Context.getCanonicalType(FromType); 3444 QualType A = Context.getCanonicalType(ToType); 3445 3446 // C++0x [temp.deduct.conv]p2: 3447 // If P is a reference type, the type referred to by P is used for 3448 // type deduction. 3449 if (const ReferenceType *PRef = P->getAs<ReferenceType>()) 3450 P = PRef->getPointeeType(); 3451 3452 // C++0x [temp.deduct.conv]p4: 3453 // [...] If A is a reference type, the type referred to by A is used 3454 // for type deduction. 3455 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 3456 A = ARef->getPointeeType().getUnqualifiedType(); 3457 // C++ [temp.deduct.conv]p3: 3458 // 3459 // If A is not a reference type: 3460 else { 3461 assert(!A->isReferenceType() && "Reference types were handled above"); 3462 3463 // - If P is an array type, the pointer type produced by the 3464 // array-to-pointer standard conversion (4.2) is used in place 3465 // of P for type deduction; otherwise, 3466 if (P->isArrayType()) 3467 P = Context.getArrayDecayedType(P); 3468 // - If P is a function type, the pointer type produced by the 3469 // function-to-pointer standard conversion (4.3) is used in 3470 // place of P for type deduction; otherwise, 3471 else if (P->isFunctionType()) 3472 P = Context.getPointerType(P); 3473 // - If P is a cv-qualified type, the top level cv-qualifiers of 3474 // P's type are ignored for type deduction. 3475 else 3476 P = P.getUnqualifiedType(); 3477 3478 // C++0x [temp.deduct.conv]p4: 3479 // If A is a cv-qualified type, the top level cv-qualifiers of A's 3480 // type are ignored for type deduction. If A is a reference type, the type 3481 // referred to by A is used for type deduction. 3482 A = A.getUnqualifiedType(); 3483 } 3484 3485 // Unevaluated SFINAE context. 3486 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 3487 SFINAETrap Trap(*this); 3488 3489 // C++ [temp.deduct.conv]p1: 3490 // Template argument deduction is done by comparing the return 3491 // type of the template conversion function (call it P) with the 3492 // type that is required as the result of the conversion (call it 3493 // A) as described in 14.8.2.4. 3494 TemplateParameterList *TemplateParams 3495 = FunctionTemplate->getTemplateParameters(); 3496 SmallVector<DeducedTemplateArgument, 4> Deduced; 3497 Deduced.resize(TemplateParams->size()); 3498 3499 // C++0x [temp.deduct.conv]p4: 3500 // In general, the deduction process attempts to find template 3501 // argument values that will make the deduced A identical to 3502 // A. However, there are two cases that allow a difference: 3503 unsigned TDF = 0; 3504 // - If the original A is a reference type, A can be more 3505 // cv-qualified than the deduced A (i.e., the type referred to 3506 // by the reference) 3507 if (ToType->isReferenceType()) 3508 TDF |= TDF_ParamWithReferenceType; 3509 // - The deduced A can be another pointer or pointer to member 3510 // type that can be converted to A via a qualification 3511 // conversion. 3512 // 3513 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 3514 // both P and A are pointers or member pointers. In this case, we 3515 // just ignore cv-qualifiers completely). 3516 if ((P->isPointerType() && A->isPointerType()) || 3517 (P->isMemberPointerType() && A->isMemberPointerType())) 3518 TDF |= TDF_IgnoreQualifiers; 3519 if (TemplateDeductionResult Result 3520 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3521 P, A, Info, Deduced, TDF)) 3522 return Result; 3523 3524 // Finish template argument deduction. 3525 LocalInstantiationScope InstScope(*this); 3526 FunctionDecl *Spec = 0; 3527 TemplateDeductionResult Result 3528 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec, 3529 Info); 3530 Specialization = cast_or_null<CXXConversionDecl>(Spec); 3531 return Result; 3532} 3533 3534/// \brief Deduce template arguments for a function template when there is 3535/// nothing to deduce against (C++0x [temp.arg.explicit]p3). 3536/// 3537/// \param FunctionTemplate the function template for which we are performing 3538/// template argument deduction. 3539/// 3540/// \param ExplicitTemplateArgs the explicitly-specified template 3541/// arguments. 3542/// 3543/// \param Specialization if template argument deduction was successful, 3544/// this will be set to the function template specialization produced by 3545/// template argument deduction. 3546/// 3547/// \param Info the argument will be updated to provide additional information 3548/// about template argument deduction. 3549/// 3550/// \returns the result of template argument deduction. 3551Sema::TemplateDeductionResult 3552Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 3553 TemplateArgumentListInfo *ExplicitTemplateArgs, 3554 FunctionDecl *&Specialization, 3555 TemplateDeductionInfo &Info, 3556 bool InOverloadResolution) { 3557 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs, 3558 QualType(), Specialization, Info, 3559 InOverloadResolution); 3560} 3561 3562namespace { 3563 /// Substitute the 'auto' type specifier within a type for a given replacement 3564 /// type. 3565 class SubstituteAutoTransform : 3566 public TreeTransform<SubstituteAutoTransform> { 3567 QualType Replacement; 3568 public: 3569 SubstituteAutoTransform(Sema &SemaRef, QualType Replacement) : 3570 TreeTransform<SubstituteAutoTransform>(SemaRef), Replacement(Replacement) { 3571 } 3572 QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) { 3573 // If we're building the type pattern to deduce against, don't wrap the 3574 // substituted type in an AutoType. Certain template deduction rules 3575 // apply only when a template type parameter appears directly (and not if 3576 // the parameter is found through desugaring). For instance: 3577 // auto &&lref = lvalue; 3578 // must transform into "rvalue reference to T" not "rvalue reference to 3579 // auto type deduced as T" in order for [temp.deduct.call]p3 to apply. 3580 if (isa<TemplateTypeParmType>(Replacement)) { 3581 QualType Result = Replacement; 3582 TemplateTypeParmTypeLoc NewTL = 3583 TLB.push<TemplateTypeParmTypeLoc>(Result); 3584 NewTL.setNameLoc(TL.getNameLoc()); 3585 return Result; 3586 } else { 3587 bool Dependent = 3588 !Replacement.isNull() && Replacement->isDependentType(); 3589 QualType Result = 3590 SemaRef.Context.getAutoType(Dependent ? QualType() : Replacement, 3591 TL.getTypePtr()->isDecltypeAuto(), 3592 Dependent); 3593 AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result); 3594 NewTL.setNameLoc(TL.getNameLoc()); 3595 return Result; 3596 } 3597 } 3598 3599 ExprResult TransformLambdaExpr(LambdaExpr *E) { 3600 // Lambdas never need to be transformed. 3601 return E; 3602 } 3603 3604 QualType Apply(TypeSourceInfo *TSI) { 3605 if (TypeSourceInfo *Result = TransformType(TSI)) 3606 return Result->getType(); 3607 return QualType(); 3608 } 3609 }; 3610} 3611 3612/// \brief Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6) 3613/// 3614/// \param Type the type pattern using the auto type-specifier. 3615/// \param Init the initializer for the variable whose type is to be deduced. 3616/// \param Result if type deduction was successful, this will be set to the 3617/// deduced type. 3618Sema::DeduceAutoResult 3619Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result) { 3620 if (Init->getType()->isNonOverloadPlaceholderType()) { 3621 ExprResult NonPlaceholder = CheckPlaceholderExpr(Init); 3622 if (NonPlaceholder.isInvalid()) 3623 return DAR_FailedAlreadyDiagnosed; 3624 Init = NonPlaceholder.take(); 3625 } 3626 3627 if (Init->isTypeDependent() || Type->getType()->isDependentType()) { 3628 Result = SubstituteAutoTransform(*this, Context.DependentTy).Apply(Type); 3629 return DAR_Succeeded; 3630 } 3631 3632 // If this is a 'decltype(auto)' specifier, do the decltype dance. 3633 // Since 'decltype(auto)' can only occur at the top of the type, we 3634 // don't need to go digging for it. 3635 if (const AutoType *AT = Type->getType()->getAs<AutoType>()) { 3636 if (AT->isDecltypeAuto()) { 3637 if (isa<InitListExpr>(Init)) { 3638 Diag(Init->getLocStart(), diag::err_decltype_auto_initializer_list); 3639 return DAR_FailedAlreadyDiagnosed; 3640 } 3641 3642 QualType Deduced = BuildDecltypeType(Init, Init->getLocStart()); 3643 // FIXME: Support a non-canonical deduced type for 'auto'. 3644 Deduced = Context.getCanonicalType(Deduced); 3645 Result = SubstituteAutoTransform(*this, Deduced).Apply(Type); 3646 return DAR_Succeeded; 3647 } 3648 } 3649 3650 SourceLocation Loc = Init->getExprLoc(); 3651 3652 LocalInstantiationScope InstScope(*this); 3653 3654 // Build template<class TemplParam> void Func(FuncParam); 3655 TemplateTypeParmDecl *TemplParam = 3656 TemplateTypeParmDecl::Create(Context, 0, SourceLocation(), Loc, 0, 0, 0, 3657 false, false); 3658 QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0); 3659 NamedDecl *TemplParamPtr = TemplParam; 3660 FixedSizeTemplateParameterList<1> TemplateParams(Loc, Loc, &TemplParamPtr, 3661 Loc); 3662 3663 QualType FuncParam = SubstituteAutoTransform(*this, TemplArg).Apply(Type); 3664 assert(!FuncParam.isNull() && 3665 "substituting template parameter for 'auto' failed"); 3666 3667 // Deduce type of TemplParam in Func(Init) 3668 SmallVector<DeducedTemplateArgument, 1> Deduced; 3669 Deduced.resize(1); 3670 QualType InitType = Init->getType(); 3671 unsigned TDF = 0; 3672 3673 TemplateDeductionInfo Info(Loc); 3674 3675 InitListExpr *InitList = dyn_cast<InitListExpr>(Init); 3676 if (InitList) { 3677 for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) { 3678 if (DeduceTemplateArgumentByListElement(*this, &TemplateParams, 3679 TemplArg, 3680 InitList->getInit(i), 3681 Info, Deduced, TDF)) 3682 return DAR_Failed; 3683 } 3684 } else { 3685 if (AdjustFunctionParmAndArgTypesForDeduction(*this, &TemplateParams, 3686 FuncParam, InitType, Init, 3687 TDF)) 3688 return DAR_Failed; 3689 3690 if (DeduceTemplateArgumentsByTypeMatch(*this, &TemplateParams, FuncParam, 3691 InitType, Info, Deduced, TDF)) 3692 return DAR_Failed; 3693 } 3694 3695 if (Deduced[0].getKind() != TemplateArgument::Type) 3696 return DAR_Failed; 3697 3698 QualType DeducedType = Deduced[0].getAsType(); 3699 3700 if (InitList) { 3701 DeducedType = BuildStdInitializerList(DeducedType, Loc); 3702 if (DeducedType.isNull()) 3703 return DAR_FailedAlreadyDiagnosed; 3704 } 3705 3706 Result = SubstituteAutoTransform(*this, DeducedType).Apply(Type); 3707 3708 // Check that the deduced argument type is compatible with the original 3709 // argument type per C++ [temp.deduct.call]p4. 3710 if (!InitList && !Result.isNull() && 3711 CheckOriginalCallArgDeduction(*this, 3712 Sema::OriginalCallArg(FuncParam,0,InitType), 3713 Result)) { 3714 Result = QualType(); 3715 return DAR_Failed; 3716 } 3717 3718 return DAR_Succeeded; 3719} 3720 3721QualType Sema::SubstAutoType(QualType Type, QualType Deduced) { 3722 return SubstituteAutoTransform(*this, Deduced).TransformType(Type); 3723} 3724 3725void Sema::DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init) { 3726 if (isa<InitListExpr>(Init)) 3727 Diag(VDecl->getLocation(), 3728 diag::err_auto_var_deduction_failure_from_init_list) 3729 << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange(); 3730 else 3731 Diag(VDecl->getLocation(), diag::err_auto_var_deduction_failure) 3732 << VDecl->getDeclName() << VDecl->getType() << Init->getType() 3733 << Init->getSourceRange(); 3734} 3735 3736static void 3737MarkUsedTemplateParameters(ASTContext &Ctx, QualType T, 3738 bool OnlyDeduced, 3739 unsigned Level, 3740 llvm::SmallBitVector &Deduced); 3741 3742/// \brief If this is a non-static member function, 3743static void AddImplicitObjectParameterType(ASTContext &Context, 3744 CXXMethodDecl *Method, 3745 SmallVectorImpl<QualType> &ArgTypes) { 3746 // C++11 [temp.func.order]p3: 3747 // [...] The new parameter is of type "reference to cv A," where cv are 3748 // the cv-qualifiers of the function template (if any) and A is 3749 // the class of which the function template is a member. 3750 // 3751 // The standard doesn't say explicitly, but we pick the appropriate kind of 3752 // reference type based on [over.match.funcs]p4. 3753 QualType ArgTy = Context.getTypeDeclType(Method->getParent()); 3754 ArgTy = Context.getQualifiedType(ArgTy, 3755 Qualifiers::fromCVRMask(Method->getTypeQualifiers())); 3756 if (Method->getRefQualifier() == RQ_RValue) 3757 ArgTy = Context.getRValueReferenceType(ArgTy); 3758 else 3759 ArgTy = Context.getLValueReferenceType(ArgTy); 3760 ArgTypes.push_back(ArgTy); 3761} 3762 3763/// \brief Determine whether the function template \p FT1 is at least as 3764/// specialized as \p FT2. 3765static bool isAtLeastAsSpecializedAs(Sema &S, 3766 SourceLocation Loc, 3767 FunctionTemplateDecl *FT1, 3768 FunctionTemplateDecl *FT2, 3769 TemplatePartialOrderingContext TPOC, 3770 unsigned NumCallArguments, 3771 SmallVectorImpl<RefParamPartialOrderingComparison> *RefParamComparisons) { 3772 FunctionDecl *FD1 = FT1->getTemplatedDecl(); 3773 FunctionDecl *FD2 = FT2->getTemplatedDecl(); 3774 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 3775 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 3776 3777 assert(Proto1 && Proto2 && "Function templates must have prototypes"); 3778 TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 3779 SmallVector<DeducedTemplateArgument, 4> Deduced; 3780 Deduced.resize(TemplateParams->size()); 3781 3782 // C++0x [temp.deduct.partial]p3: 3783 // The types used to determine the ordering depend on the context in which 3784 // the partial ordering is done: 3785 TemplateDeductionInfo Info(Loc); 3786 CXXMethodDecl *Method1 = 0; 3787 CXXMethodDecl *Method2 = 0; 3788 bool IsNonStatic2 = false; 3789 bool IsNonStatic1 = false; 3790 unsigned Skip2 = 0; 3791 switch (TPOC) { 3792 case TPOC_Call: { 3793 // - In the context of a function call, the function parameter types are 3794 // used. 3795 Method1 = dyn_cast<CXXMethodDecl>(FD1); 3796 Method2 = dyn_cast<CXXMethodDecl>(FD2); 3797 IsNonStatic1 = Method1 && !Method1->isStatic(); 3798 IsNonStatic2 = Method2 && !Method2->isStatic(); 3799 3800 // C++11 [temp.func.order]p3: 3801 // [...] If only one of the function templates is a non-static 3802 // member, that function template is considered to have a new 3803 // first parameter inserted in its function parameter list. The 3804 // new parameter is of type "reference to cv A," where cv are 3805 // the cv-qualifiers of the function template (if any) and A is 3806 // the class of which the function template is a member. 3807 // 3808 // Note that we interpret this to mean "if one of the function 3809 // templates is a non-static member and the other is a non-member"; 3810 // otherwise, the ordering rules for static functions against non-static 3811 // functions don't make any sense. 3812 // 3813 // C++98/03 doesn't have this provision, so instead we drop the 3814 // first argument of the free function, which seems to match 3815 // existing practice. 3816 SmallVector<QualType, 4> Args1; 3817 unsigned Skip1 = !S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !Method1; 3818 if (S.getLangOpts().CPlusPlus11 && IsNonStatic1 && !Method2) 3819 AddImplicitObjectParameterType(S.Context, Method1, Args1); 3820 Args1.insert(Args1.end(), 3821 Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end()); 3822 3823 SmallVector<QualType, 4> Args2; 3824 Skip2 = !S.getLangOpts().CPlusPlus11 && IsNonStatic1 && !Method2; 3825 if (S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !Method1) 3826 AddImplicitObjectParameterType(S.Context, Method2, Args2); 3827 Args2.insert(Args2.end(), 3828 Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end()); 3829 3830 // C++ [temp.func.order]p5: 3831 // The presence of unused ellipsis and default arguments has no effect on 3832 // the partial ordering of function templates. 3833 if (Args1.size() > NumCallArguments) 3834 Args1.resize(NumCallArguments); 3835 if (Args2.size() > NumCallArguments) 3836 Args2.resize(NumCallArguments); 3837 if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(), 3838 Args1.data(), Args1.size(), Info, Deduced, 3839 TDF_None, /*PartialOrdering=*/true, 3840 RefParamComparisons)) 3841 return false; 3842 3843 break; 3844 } 3845 3846 case TPOC_Conversion: 3847 // - In the context of a call to a conversion operator, the return types 3848 // of the conversion function templates are used. 3849 if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 3850 Proto2->getResultType(), 3851 Proto1->getResultType(), 3852 Info, Deduced, TDF_None, 3853 /*PartialOrdering=*/true, 3854 RefParamComparisons)) 3855 return false; 3856 break; 3857 3858 case TPOC_Other: 3859 // - In other contexts (14.6.6.2) the function template's function type 3860 // is used. 3861 if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 3862 FD2->getType(), FD1->getType(), 3863 Info, Deduced, TDF_None, 3864 /*PartialOrdering=*/true, 3865 RefParamComparisons)) 3866 return false; 3867 break; 3868 } 3869 3870 // C++0x [temp.deduct.partial]p11: 3871 // In most cases, all template parameters must have values in order for 3872 // deduction to succeed, but for partial ordering purposes a template 3873 // parameter may remain without a value provided it is not used in the 3874 // types being used for partial ordering. [ Note: a template parameter used 3875 // in a non-deduced context is considered used. -end note] 3876 unsigned ArgIdx = 0, NumArgs = Deduced.size(); 3877 for (; ArgIdx != NumArgs; ++ArgIdx) 3878 if (Deduced[ArgIdx].isNull()) 3879 break; 3880 3881 if (ArgIdx == NumArgs) { 3882 // All template arguments were deduced. FT1 is at least as specialized 3883 // as FT2. 3884 return true; 3885 } 3886 3887 // Figure out which template parameters were used. 3888 llvm::SmallBitVector UsedParameters(TemplateParams->size()); 3889 switch (TPOC) { 3890 case TPOC_Call: { 3891 unsigned NumParams = std::min(NumCallArguments, 3892 std::min(Proto1->getNumArgs(), 3893 Proto2->getNumArgs())); 3894 if (S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !IsNonStatic1) 3895 ::MarkUsedTemplateParameters(S.Context, Method2->getThisType(S.Context), 3896 false, 3897 TemplateParams->getDepth(), UsedParameters); 3898 for (unsigned I = Skip2; I < NumParams; ++I) 3899 ::MarkUsedTemplateParameters(S.Context, Proto2->getArgType(I), false, 3900 TemplateParams->getDepth(), 3901 UsedParameters); 3902 break; 3903 } 3904 3905 case TPOC_Conversion: 3906 ::MarkUsedTemplateParameters(S.Context, Proto2->getResultType(), false, 3907 TemplateParams->getDepth(), 3908 UsedParameters); 3909 break; 3910 3911 case TPOC_Other: 3912 ::MarkUsedTemplateParameters(S.Context, FD2->getType(), false, 3913 TemplateParams->getDepth(), 3914 UsedParameters); 3915 break; 3916 } 3917 3918 for (; ArgIdx != NumArgs; ++ArgIdx) 3919 // If this argument had no value deduced but was used in one of the types 3920 // used for partial ordering, then deduction fails. 3921 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 3922 return false; 3923 3924 return true; 3925} 3926 3927/// \brief Determine whether this a function template whose parameter-type-list 3928/// ends with a function parameter pack. 3929static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) { 3930 FunctionDecl *Function = FunTmpl->getTemplatedDecl(); 3931 unsigned NumParams = Function->getNumParams(); 3932 if (NumParams == 0) 3933 return false; 3934 3935 ParmVarDecl *Last = Function->getParamDecl(NumParams - 1); 3936 if (!Last->isParameterPack()) 3937 return false; 3938 3939 // Make sure that no previous parameter is a parameter pack. 3940 while (--NumParams > 0) { 3941 if (Function->getParamDecl(NumParams - 1)->isParameterPack()) 3942 return false; 3943 } 3944 3945 return true; 3946} 3947 3948/// \brief Returns the more specialized function template according 3949/// to the rules of function template partial ordering (C++ [temp.func.order]). 3950/// 3951/// \param FT1 the first function template 3952/// 3953/// \param FT2 the second function template 3954/// 3955/// \param TPOC the context in which we are performing partial ordering of 3956/// function templates. 3957/// 3958/// \param NumCallArguments The number of arguments in a call, used only 3959/// when \c TPOC is \c TPOC_Call. 3960/// 3961/// \returns the more specialized function template. If neither 3962/// template is more specialized, returns NULL. 3963FunctionTemplateDecl * 3964Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, 3965 FunctionTemplateDecl *FT2, 3966 SourceLocation Loc, 3967 TemplatePartialOrderingContext TPOC, 3968 unsigned NumCallArguments) { 3969 SmallVector<RefParamPartialOrderingComparison, 4> RefParamComparisons; 3970 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC, 3971 NumCallArguments, 0); 3972 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC, 3973 NumCallArguments, 3974 &RefParamComparisons); 3975 3976 if (Better1 != Better2) // We have a clear winner 3977 return Better1? FT1 : FT2; 3978 3979 if (!Better1 && !Better2) // Neither is better than the other 3980 return 0; 3981 3982 // C++0x [temp.deduct.partial]p10: 3983 // If for each type being considered a given template is at least as 3984 // specialized for all types and more specialized for some set of types and 3985 // the other template is not more specialized for any types or is not at 3986 // least as specialized for any types, then the given template is more 3987 // specialized than the other template. Otherwise, neither template is more 3988 // specialized than the other. 3989 Better1 = false; 3990 Better2 = false; 3991 for (unsigned I = 0, N = RefParamComparisons.size(); I != N; ++I) { 3992 // C++0x [temp.deduct.partial]p9: 3993 // If, for a given type, deduction succeeds in both directions (i.e., the 3994 // types are identical after the transformations above) and both P and A 3995 // were reference types (before being replaced with the type referred to 3996 // above): 3997 3998 // -- if the type from the argument template was an lvalue reference 3999 // and the type from the parameter template was not, the argument 4000 // type is considered to be more specialized than the other; 4001 // otherwise, 4002 if (!RefParamComparisons[I].ArgIsRvalueRef && 4003 RefParamComparisons[I].ParamIsRvalueRef) { 4004 Better2 = true; 4005 if (Better1) 4006 return 0; 4007 continue; 4008 } else if (!RefParamComparisons[I].ParamIsRvalueRef && 4009 RefParamComparisons[I].ArgIsRvalueRef) { 4010 Better1 = true; 4011 if (Better2) 4012 return 0; 4013 continue; 4014 } 4015 4016 // -- if the type from the argument template is more cv-qualified than 4017 // the type from the parameter template (as described above), the 4018 // argument type is considered to be more specialized than the 4019 // other; otherwise, 4020 switch (RefParamComparisons[I].Qualifiers) { 4021 case NeitherMoreQualified: 4022 break; 4023 4024 case ParamMoreQualified: 4025 Better1 = true; 4026 if (Better2) 4027 return 0; 4028 continue; 4029 4030 case ArgMoreQualified: 4031 Better2 = true; 4032 if (Better1) 4033 return 0; 4034 continue; 4035 } 4036 4037 // -- neither type is more specialized than the other. 4038 } 4039 4040 assert(!(Better1 && Better2) && "Should have broken out in the loop above"); 4041 if (Better1) 4042 return FT1; 4043 else if (Better2) 4044 return FT2; 4045 4046 // FIXME: This mimics what GCC implements, but doesn't match up with the 4047 // proposed resolution for core issue 692. This area needs to be sorted out, 4048 // but for now we attempt to maintain compatibility. 4049 bool Variadic1 = isVariadicFunctionTemplate(FT1); 4050 bool Variadic2 = isVariadicFunctionTemplate(FT2); 4051 if (Variadic1 != Variadic2) 4052 return Variadic1? FT2 : FT1; 4053 4054 return 0; 4055} 4056 4057/// \brief Determine if the two templates are equivalent. 4058static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) { 4059 if (T1 == T2) 4060 return true; 4061 4062 if (!T1 || !T2) 4063 return false; 4064 4065 return T1->getCanonicalDecl() == T2->getCanonicalDecl(); 4066} 4067 4068/// \brief Retrieve the most specialized of the given function template 4069/// specializations. 4070/// 4071/// \param SpecBegin the start iterator of the function template 4072/// specializations that we will be comparing. 4073/// 4074/// \param SpecEnd the end iterator of the function template 4075/// specializations, paired with \p SpecBegin. 4076/// 4077/// \param TPOC the partial ordering context to use to compare the function 4078/// template specializations. 4079/// 4080/// \param NumCallArguments The number of arguments in a call, used only 4081/// when \c TPOC is \c TPOC_Call. 4082/// 4083/// \param Loc the location where the ambiguity or no-specializations 4084/// diagnostic should occur. 4085/// 4086/// \param NoneDiag partial diagnostic used to diagnose cases where there are 4087/// no matching candidates. 4088/// 4089/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one 4090/// occurs. 4091/// 4092/// \param CandidateDiag partial diagnostic used for each function template 4093/// specialization that is a candidate in the ambiguous ordering. One parameter 4094/// in this diagnostic should be unbound, which will correspond to the string 4095/// describing the template arguments for the function template specialization. 4096/// 4097/// \returns the most specialized function template specialization, if 4098/// found. Otherwise, returns SpecEnd. 4099/// 4100/// \todo FIXME: Consider passing in the "also-ran" candidates that failed 4101/// template argument deduction. 4102UnresolvedSetIterator 4103Sema::getMostSpecialized(UnresolvedSetIterator SpecBegin, 4104 UnresolvedSetIterator SpecEnd, 4105 TemplatePartialOrderingContext TPOC, 4106 unsigned NumCallArguments, 4107 SourceLocation Loc, 4108 const PartialDiagnostic &NoneDiag, 4109 const PartialDiagnostic &AmbigDiag, 4110 const PartialDiagnostic &CandidateDiag, 4111 bool Complain, 4112 QualType TargetType) { 4113 if (SpecBegin == SpecEnd) { 4114 if (Complain) 4115 Diag(Loc, NoneDiag); 4116 return SpecEnd; 4117 } 4118 4119 if (SpecBegin + 1 == SpecEnd) 4120 return SpecBegin; 4121 4122 // Find the function template that is better than all of the templates it 4123 // has been compared to. 4124 UnresolvedSetIterator Best = SpecBegin; 4125 FunctionTemplateDecl *BestTemplate 4126 = cast<FunctionDecl>(*Best)->getPrimaryTemplate(); 4127 assert(BestTemplate && "Not a function template specialization?"); 4128 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) { 4129 FunctionTemplateDecl *Challenger 4130 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 4131 assert(Challenger && "Not a function template specialization?"); 4132 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 4133 Loc, TPOC, NumCallArguments), 4134 Challenger)) { 4135 Best = I; 4136 BestTemplate = Challenger; 4137 } 4138 } 4139 4140 // Make sure that the "best" function template is more specialized than all 4141 // of the others. 4142 bool Ambiguous = false; 4143 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 4144 FunctionTemplateDecl *Challenger 4145 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 4146 if (I != Best && 4147 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 4148 Loc, TPOC, NumCallArguments), 4149 BestTemplate)) { 4150 Ambiguous = true; 4151 break; 4152 } 4153 } 4154 4155 if (!Ambiguous) { 4156 // We found an answer. Return it. 4157 return Best; 4158 } 4159 4160 // Diagnose the ambiguity. 4161 if (Complain) 4162 Diag(Loc, AmbigDiag); 4163 4164 if (Complain) 4165 // FIXME: Can we order the candidates in some sane way? 4166 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 4167 PartialDiagnostic PD = CandidateDiag; 4168 PD << getTemplateArgumentBindingsText( 4169 cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(), 4170 *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs()); 4171 if (!TargetType.isNull()) 4172 HandleFunctionTypeMismatch(PD, cast<FunctionDecl>(*I)->getType(), 4173 TargetType); 4174 Diag((*I)->getLocation(), PD); 4175 } 4176 4177 return SpecEnd; 4178} 4179 4180/// \brief Returns the more specialized class template partial specialization 4181/// according to the rules of partial ordering of class template partial 4182/// specializations (C++ [temp.class.order]). 4183/// 4184/// \param PS1 the first class template partial specialization 4185/// 4186/// \param PS2 the second class template partial specialization 4187/// 4188/// \returns the more specialized class template partial specialization. If 4189/// neither partial specialization is more specialized, returns NULL. 4190ClassTemplatePartialSpecializationDecl * 4191Sema::getMoreSpecializedPartialSpecialization( 4192 ClassTemplatePartialSpecializationDecl *PS1, 4193 ClassTemplatePartialSpecializationDecl *PS2, 4194 SourceLocation Loc) { 4195 // C++ [temp.class.order]p1: 4196 // For two class template partial specializations, the first is at least as 4197 // specialized as the second if, given the following rewrite to two 4198 // function templates, the first function template is at least as 4199 // specialized as the second according to the ordering rules for function 4200 // templates (14.6.6.2): 4201 // - the first function template has the same template parameters as the 4202 // first partial specialization and has a single function parameter 4203 // whose type is a class template specialization with the template 4204 // arguments of the first partial specialization, and 4205 // - the second function template has the same template parameters as the 4206 // second partial specialization and has a single function parameter 4207 // whose type is a class template specialization with the template 4208 // arguments of the second partial specialization. 4209 // 4210 // Rather than synthesize function templates, we merely perform the 4211 // equivalent partial ordering by performing deduction directly on 4212 // the template arguments of the class template partial 4213 // specializations. This computation is slightly simpler than the 4214 // general problem of function template partial ordering, because 4215 // class template partial specializations are more constrained. We 4216 // know that every template parameter is deducible from the class 4217 // template partial specialization's template arguments, for 4218 // example. 4219 SmallVector<DeducedTemplateArgument, 4> Deduced; 4220 TemplateDeductionInfo Info(Loc); 4221 4222 QualType PT1 = PS1->getInjectedSpecializationType(); 4223 QualType PT2 = PS2->getInjectedSpecializationType(); 4224 4225 // Determine whether PS1 is at least as specialized as PS2 4226 Deduced.resize(PS2->getTemplateParameters()->size()); 4227 bool Better1 = !DeduceTemplateArgumentsByTypeMatch(*this, 4228 PS2->getTemplateParameters(), 4229 PT2, PT1, Info, Deduced, TDF_None, 4230 /*PartialOrdering=*/true, 4231 /*RefParamComparisons=*/0); 4232 if (Better1) { 4233 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end()); 4234 InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2, 4235 DeducedArgs, Info); 4236 Better1 = !::FinishTemplateArgumentDeduction(*this, PS2, 4237 PS1->getTemplateArgs(), 4238 Deduced, Info); 4239 } 4240 4241 // Determine whether PS2 is at least as specialized as PS1 4242 Deduced.clear(); 4243 Deduced.resize(PS1->getTemplateParameters()->size()); 4244 bool Better2 = !DeduceTemplateArgumentsByTypeMatch(*this, 4245 PS1->getTemplateParameters(), 4246 PT1, PT2, Info, Deduced, TDF_None, 4247 /*PartialOrdering=*/true, 4248 /*RefParamComparisons=*/0); 4249 if (Better2) { 4250 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end()); 4251 InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1, 4252 DeducedArgs, Info); 4253 Better2 = !::FinishTemplateArgumentDeduction(*this, PS1, 4254 PS2->getTemplateArgs(), 4255 Deduced, Info); 4256 } 4257 4258 if (Better1 == Better2) 4259 return 0; 4260 4261 return Better1? PS1 : PS2; 4262} 4263 4264static void 4265MarkUsedTemplateParameters(ASTContext &Ctx, 4266 const TemplateArgument &TemplateArg, 4267 bool OnlyDeduced, 4268 unsigned Depth, 4269 llvm::SmallBitVector &Used); 4270 4271/// \brief Mark the template parameters that are used by the given 4272/// expression. 4273static void 4274MarkUsedTemplateParameters(ASTContext &Ctx, 4275 const Expr *E, 4276 bool OnlyDeduced, 4277 unsigned Depth, 4278 llvm::SmallBitVector &Used) { 4279 // We can deduce from a pack expansion. 4280 if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E)) 4281 E = Expansion->getPattern(); 4282 4283 // Skip through any implicit casts we added while type-checking, and any 4284 // substitutions performed by template alias expansion. 4285 while (1) { 4286 if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E)) 4287 E = ICE->getSubExpr(); 4288 else if (const SubstNonTypeTemplateParmExpr *Subst = 4289 dyn_cast<SubstNonTypeTemplateParmExpr>(E)) 4290 E = Subst->getReplacement(); 4291 else 4292 break; 4293 } 4294 4295 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to 4296 // find other occurrences of template parameters. 4297 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E); 4298 if (!DRE) 4299 return; 4300 4301 const NonTypeTemplateParmDecl *NTTP 4302 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 4303 if (!NTTP) 4304 return; 4305 4306 if (NTTP->getDepth() == Depth) 4307 Used[NTTP->getIndex()] = true; 4308} 4309 4310/// \brief Mark the template parameters that are used by the given 4311/// nested name specifier. 4312static void 4313MarkUsedTemplateParameters(ASTContext &Ctx, 4314 NestedNameSpecifier *NNS, 4315 bool OnlyDeduced, 4316 unsigned Depth, 4317 llvm::SmallBitVector &Used) { 4318 if (!NNS) 4319 return; 4320 4321 MarkUsedTemplateParameters(Ctx, NNS->getPrefix(), OnlyDeduced, Depth, 4322 Used); 4323 MarkUsedTemplateParameters(Ctx, QualType(NNS->getAsType(), 0), 4324 OnlyDeduced, Depth, Used); 4325} 4326 4327/// \brief Mark the template parameters that are used by the given 4328/// template name. 4329static void 4330MarkUsedTemplateParameters(ASTContext &Ctx, 4331 TemplateName Name, 4332 bool OnlyDeduced, 4333 unsigned Depth, 4334 llvm::SmallBitVector &Used) { 4335 if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 4336 if (TemplateTemplateParmDecl *TTP 4337 = dyn_cast<TemplateTemplateParmDecl>(Template)) { 4338 if (TTP->getDepth() == Depth) 4339 Used[TTP->getIndex()] = true; 4340 } 4341 return; 4342 } 4343 4344 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) 4345 MarkUsedTemplateParameters(Ctx, QTN->getQualifier(), OnlyDeduced, 4346 Depth, Used); 4347 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 4348 MarkUsedTemplateParameters(Ctx, DTN->getQualifier(), OnlyDeduced, 4349 Depth, Used); 4350} 4351 4352/// \brief Mark the template parameters that are used by the given 4353/// type. 4354static void 4355MarkUsedTemplateParameters(ASTContext &Ctx, QualType T, 4356 bool OnlyDeduced, 4357 unsigned Depth, 4358 llvm::SmallBitVector &Used) { 4359 if (T.isNull()) 4360 return; 4361 4362 // Non-dependent types have nothing deducible 4363 if (!T->isDependentType()) 4364 return; 4365 4366 T = Ctx.getCanonicalType(T); 4367 switch (T->getTypeClass()) { 4368 case Type::Pointer: 4369 MarkUsedTemplateParameters(Ctx, 4370 cast<PointerType>(T)->getPointeeType(), 4371 OnlyDeduced, 4372 Depth, 4373 Used); 4374 break; 4375 4376 case Type::BlockPointer: 4377 MarkUsedTemplateParameters(Ctx, 4378 cast<BlockPointerType>(T)->getPointeeType(), 4379 OnlyDeduced, 4380 Depth, 4381 Used); 4382 break; 4383 4384 case Type::LValueReference: 4385 case Type::RValueReference: 4386 MarkUsedTemplateParameters(Ctx, 4387 cast<ReferenceType>(T)->getPointeeType(), 4388 OnlyDeduced, 4389 Depth, 4390 Used); 4391 break; 4392 4393 case Type::MemberPointer: { 4394 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 4395 MarkUsedTemplateParameters(Ctx, MemPtr->getPointeeType(), OnlyDeduced, 4396 Depth, Used); 4397 MarkUsedTemplateParameters(Ctx, QualType(MemPtr->getClass(), 0), 4398 OnlyDeduced, Depth, Used); 4399 break; 4400 } 4401 4402 case Type::DependentSizedArray: 4403 MarkUsedTemplateParameters(Ctx, 4404 cast<DependentSizedArrayType>(T)->getSizeExpr(), 4405 OnlyDeduced, Depth, Used); 4406 // Fall through to check the element type 4407 4408 case Type::ConstantArray: 4409 case Type::IncompleteArray: 4410 MarkUsedTemplateParameters(Ctx, 4411 cast<ArrayType>(T)->getElementType(), 4412 OnlyDeduced, Depth, Used); 4413 break; 4414 4415 case Type::Vector: 4416 case Type::ExtVector: 4417 MarkUsedTemplateParameters(Ctx, 4418 cast<VectorType>(T)->getElementType(), 4419 OnlyDeduced, Depth, Used); 4420 break; 4421 4422 case Type::DependentSizedExtVector: { 4423 const DependentSizedExtVectorType *VecType 4424 = cast<DependentSizedExtVectorType>(T); 4425 MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced, 4426 Depth, Used); 4427 MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced, 4428 Depth, Used); 4429 break; 4430 } 4431 4432 case Type::FunctionProto: { 4433 const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 4434 MarkUsedTemplateParameters(Ctx, Proto->getResultType(), OnlyDeduced, 4435 Depth, Used); 4436 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I) 4437 MarkUsedTemplateParameters(Ctx, Proto->getArgType(I), OnlyDeduced, 4438 Depth, Used); 4439 break; 4440 } 4441 4442 case Type::TemplateTypeParm: { 4443 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T); 4444 if (TTP->getDepth() == Depth) 4445 Used[TTP->getIndex()] = true; 4446 break; 4447 } 4448 4449 case Type::SubstTemplateTypeParmPack: { 4450 const SubstTemplateTypeParmPackType *Subst 4451 = cast<SubstTemplateTypeParmPackType>(T); 4452 MarkUsedTemplateParameters(Ctx, 4453 QualType(Subst->getReplacedParameter(), 0), 4454 OnlyDeduced, Depth, Used); 4455 MarkUsedTemplateParameters(Ctx, Subst->getArgumentPack(), 4456 OnlyDeduced, Depth, Used); 4457 break; 4458 } 4459 4460 case Type::InjectedClassName: 4461 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType(); 4462 // fall through 4463 4464 case Type::TemplateSpecialization: { 4465 const TemplateSpecializationType *Spec 4466 = cast<TemplateSpecializationType>(T); 4467 MarkUsedTemplateParameters(Ctx, Spec->getTemplateName(), OnlyDeduced, 4468 Depth, Used); 4469 4470 // C++0x [temp.deduct.type]p9: 4471 // If the template argument list of P contains a pack expansion that is not 4472 // the last template argument, the entire template argument list is a 4473 // non-deduced context. 4474 if (OnlyDeduced && 4475 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 4476 break; 4477 4478 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 4479 MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth, 4480 Used); 4481 break; 4482 } 4483 4484 case Type::Complex: 4485 if (!OnlyDeduced) 4486 MarkUsedTemplateParameters(Ctx, 4487 cast<ComplexType>(T)->getElementType(), 4488 OnlyDeduced, Depth, Used); 4489 break; 4490 4491 case Type::Atomic: 4492 if (!OnlyDeduced) 4493 MarkUsedTemplateParameters(Ctx, 4494 cast<AtomicType>(T)->getValueType(), 4495 OnlyDeduced, Depth, Used); 4496 break; 4497 4498 case Type::DependentName: 4499 if (!OnlyDeduced) 4500 MarkUsedTemplateParameters(Ctx, 4501 cast<DependentNameType>(T)->getQualifier(), 4502 OnlyDeduced, Depth, Used); 4503 break; 4504 4505 case Type::DependentTemplateSpecialization: { 4506 const DependentTemplateSpecializationType *Spec 4507 = cast<DependentTemplateSpecializationType>(T); 4508 if (!OnlyDeduced) 4509 MarkUsedTemplateParameters(Ctx, Spec->getQualifier(), 4510 OnlyDeduced, Depth, Used); 4511 4512 // C++0x [temp.deduct.type]p9: 4513 // If the template argument list of P contains a pack expansion that is not 4514 // the last template argument, the entire template argument list is a 4515 // non-deduced context. 4516 if (OnlyDeduced && 4517 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 4518 break; 4519 4520 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 4521 MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth, 4522 Used); 4523 break; 4524 } 4525 4526 case Type::TypeOf: 4527 if (!OnlyDeduced) 4528 MarkUsedTemplateParameters(Ctx, 4529 cast<TypeOfType>(T)->getUnderlyingType(), 4530 OnlyDeduced, Depth, Used); 4531 break; 4532 4533 case Type::TypeOfExpr: 4534 if (!OnlyDeduced) 4535 MarkUsedTemplateParameters(Ctx, 4536 cast<TypeOfExprType>(T)->getUnderlyingExpr(), 4537 OnlyDeduced, Depth, Used); 4538 break; 4539 4540 case Type::Decltype: 4541 if (!OnlyDeduced) 4542 MarkUsedTemplateParameters(Ctx, 4543 cast<DecltypeType>(T)->getUnderlyingExpr(), 4544 OnlyDeduced, Depth, Used); 4545 break; 4546 4547 case Type::UnaryTransform: 4548 if (!OnlyDeduced) 4549 MarkUsedTemplateParameters(Ctx, 4550 cast<UnaryTransformType>(T)->getUnderlyingType(), 4551 OnlyDeduced, Depth, Used); 4552 break; 4553 4554 case Type::PackExpansion: 4555 MarkUsedTemplateParameters(Ctx, 4556 cast<PackExpansionType>(T)->getPattern(), 4557 OnlyDeduced, Depth, Used); 4558 break; 4559 4560 case Type::Auto: 4561 MarkUsedTemplateParameters(Ctx, 4562 cast<AutoType>(T)->getDeducedType(), 4563 OnlyDeduced, Depth, Used); 4564 4565 // None of these types have any template parameters in them. 4566 case Type::Builtin: 4567 case Type::VariableArray: 4568 case Type::FunctionNoProto: 4569 case Type::Record: 4570 case Type::Enum: 4571 case Type::ObjCInterface: 4572 case Type::ObjCObject: 4573 case Type::ObjCObjectPointer: 4574 case Type::UnresolvedUsing: 4575#define TYPE(Class, Base) 4576#define ABSTRACT_TYPE(Class, Base) 4577#define DEPENDENT_TYPE(Class, Base) 4578#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 4579#include "clang/AST/TypeNodes.def" 4580 break; 4581 } 4582} 4583 4584/// \brief Mark the template parameters that are used by this 4585/// template argument. 4586static void 4587MarkUsedTemplateParameters(ASTContext &Ctx, 4588 const TemplateArgument &TemplateArg, 4589 bool OnlyDeduced, 4590 unsigned Depth, 4591 llvm::SmallBitVector &Used) { 4592 switch (TemplateArg.getKind()) { 4593 case TemplateArgument::Null: 4594 case TemplateArgument::Integral: 4595 case TemplateArgument::Declaration: 4596 break; 4597 4598 case TemplateArgument::NullPtr: 4599 MarkUsedTemplateParameters(Ctx, TemplateArg.getNullPtrType(), OnlyDeduced, 4600 Depth, Used); 4601 break; 4602 4603 case TemplateArgument::Type: 4604 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsType(), OnlyDeduced, 4605 Depth, Used); 4606 break; 4607 4608 case TemplateArgument::Template: 4609 case TemplateArgument::TemplateExpansion: 4610 MarkUsedTemplateParameters(Ctx, 4611 TemplateArg.getAsTemplateOrTemplatePattern(), 4612 OnlyDeduced, Depth, Used); 4613 break; 4614 4615 case TemplateArgument::Expression: 4616 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsExpr(), OnlyDeduced, 4617 Depth, Used); 4618 break; 4619 4620 case TemplateArgument::Pack: 4621 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(), 4622 PEnd = TemplateArg.pack_end(); 4623 P != PEnd; ++P) 4624 MarkUsedTemplateParameters(Ctx, *P, OnlyDeduced, Depth, Used); 4625 break; 4626 } 4627} 4628 4629/// \brief Mark which template parameters can be deduced from a given 4630/// template argument list. 4631/// 4632/// \param TemplateArgs the template argument list from which template 4633/// parameters will be deduced. 4634/// 4635/// \param Used a bit vector whose elements will be set to \c true 4636/// to indicate when the corresponding template parameter will be 4637/// deduced. 4638void 4639Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 4640 bool OnlyDeduced, unsigned Depth, 4641 llvm::SmallBitVector &Used) { 4642 // C++0x [temp.deduct.type]p9: 4643 // If the template argument list of P contains a pack expansion that is not 4644 // the last template argument, the entire template argument list is a 4645 // non-deduced context. 4646 if (OnlyDeduced && 4647 hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size())) 4648 return; 4649 4650 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 4651 ::MarkUsedTemplateParameters(Context, TemplateArgs[I], OnlyDeduced, 4652 Depth, Used); 4653} 4654 4655/// \brief Marks all of the template parameters that will be deduced by a 4656/// call to the given function template. 4657void 4658Sema::MarkDeducedTemplateParameters(ASTContext &Ctx, 4659 const FunctionTemplateDecl *FunctionTemplate, 4660 llvm::SmallBitVector &Deduced) { 4661 TemplateParameterList *TemplateParams 4662 = FunctionTemplate->getTemplateParameters(); 4663 Deduced.clear(); 4664 Deduced.resize(TemplateParams->size()); 4665 4666 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 4667 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 4668 ::MarkUsedTemplateParameters(Ctx, Function->getParamDecl(I)->getType(), 4669 true, TemplateParams->getDepth(), Deduced); 4670} 4671 4672bool hasDeducibleTemplateParameters(Sema &S, 4673 FunctionTemplateDecl *FunctionTemplate, 4674 QualType T) { 4675 if (!T->isDependentType()) 4676 return false; 4677 4678 TemplateParameterList *TemplateParams 4679 = FunctionTemplate->getTemplateParameters(); 4680 llvm::SmallBitVector Deduced(TemplateParams->size()); 4681 ::MarkUsedTemplateParameters(S.Context, T, true, TemplateParams->getDepth(), 4682 Deduced); 4683 4684 return Deduced.any(); 4685} 4686