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