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