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