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