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