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