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