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