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