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