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