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