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