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