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