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