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