SemaTemplateDeduction.cpp revision af9bd0d681bb885f7cc43b3585dc8d6d28af4eb9
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 "Sema.h" 14#include "clang/AST/ASTContext.h" 15#include "clang/AST/DeclTemplate.h" 16#include "clang/AST/StmtVisitor.h" 17#include "clang/AST/Expr.h" 18#include "clang/AST/ExprCXX.h" 19#include "clang/Parse/DeclSpec.h" 20#include <algorithm> 21 22namespace clang { 23 /// \brief Various flags that control template argument deduction. 24 /// 25 /// These flags can be bitwise-OR'd together. 26 enum TemplateDeductionFlags { 27 /// \brief No template argument deduction flags, which indicates the 28 /// strictest results for template argument deduction (as used for, e.g., 29 /// matching class template partial specializations). 30 TDF_None = 0, 31 /// \brief Within template argument deduction from a function call, we are 32 /// matching with a parameter type for which the original parameter was 33 /// a reference. 34 TDF_ParamWithReferenceType = 0x1, 35 /// \brief Within template argument deduction from a function call, we 36 /// are matching in a case where we ignore cv-qualifiers. 37 TDF_IgnoreQualifiers = 0x02, 38 /// \brief Within template argument deduction from a function call, 39 /// we are matching in a case where we can perform template argument 40 /// deduction from a template-id of a derived class of the argument type. 41 TDF_DerivedClass = 0x04, 42 /// \brief Allow non-dependent types to differ, e.g., when performing 43 /// template argument deduction from a function call where conversions 44 /// may apply. 45 TDF_SkipNonDependent = 0x08 46 }; 47} 48 49using namespace clang; 50 51/// \brief Compare two APSInts, extending and switching the sign as 52/// necessary to compare their values regardless of underlying type. 53static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) { 54 if (Y.getBitWidth() > X.getBitWidth()) 55 X.extend(Y.getBitWidth()); 56 else if (Y.getBitWidth() < X.getBitWidth()) 57 Y.extend(X.getBitWidth()); 58 59 // If there is a signedness mismatch, correct it. 60 if (X.isSigned() != Y.isSigned()) { 61 // If the signed value is negative, then the values cannot be the same. 62 if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative())) 63 return false; 64 65 Y.setIsSigned(true); 66 X.setIsSigned(true); 67 } 68 69 return X == Y; 70} 71 72static Sema::TemplateDeductionResult 73DeduceTemplateArguments(Sema &S, 74 TemplateParameterList *TemplateParams, 75 const TemplateArgument &Param, 76 const TemplateArgument &Arg, 77 Sema::TemplateDeductionInfo &Info, 78 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced); 79 80/// \brief If the given expression is of a form that permits the deduction 81/// of a non-type template parameter, return the declaration of that 82/// non-type template parameter. 83static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) { 84 if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E)) 85 E = IC->getSubExpr(); 86 87 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E)) 88 return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 89 90 return 0; 91} 92 93/// \brief Deduce the value of the given non-type template parameter 94/// from the given constant. 95static Sema::TemplateDeductionResult 96DeduceNonTypeTemplateArgument(Sema &S, 97 NonTypeTemplateParmDecl *NTTP, 98 llvm::APSInt Value, QualType ValueType, 99 bool DeducedFromArrayBound, 100 Sema::TemplateDeductionInfo &Info, 101 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 102 assert(NTTP->getDepth() == 0 && 103 "Cannot deduce non-type template argument with depth > 0"); 104 105 if (Deduced[NTTP->getIndex()].isNull()) { 106 Deduced[NTTP->getIndex()] = DeducedTemplateArgument(Value, ValueType, 107 DeducedFromArrayBound); 108 return Sema::TDK_Success; 109 } 110 111 if (Deduced[NTTP->getIndex()].getKind() != TemplateArgument::Integral) { 112 Info.Param = NTTP; 113 Info.FirstArg = Deduced[NTTP->getIndex()]; 114 Info.SecondArg = TemplateArgument(Value, ValueType); 115 return Sema::TDK_Inconsistent; 116 } 117 118 // Extent the smaller of the two values. 119 llvm::APSInt PrevValue = *Deduced[NTTP->getIndex()].getAsIntegral(); 120 if (!hasSameExtendedValue(PrevValue, Value)) { 121 Info.Param = NTTP; 122 Info.FirstArg = Deduced[NTTP->getIndex()]; 123 Info.SecondArg = TemplateArgument(Value, ValueType); 124 return Sema::TDK_Inconsistent; 125 } 126 127 if (!DeducedFromArrayBound) 128 Deduced[NTTP->getIndex()].setDeducedFromArrayBound(false); 129 130 return Sema::TDK_Success; 131} 132 133/// \brief Deduce the value of the given non-type template parameter 134/// from the given type- or value-dependent expression. 135/// 136/// \returns true if deduction succeeded, false otherwise. 137static Sema::TemplateDeductionResult 138DeduceNonTypeTemplateArgument(Sema &S, 139 NonTypeTemplateParmDecl *NTTP, 140 Expr *Value, 141 Sema::TemplateDeductionInfo &Info, 142 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 143 assert(NTTP->getDepth() == 0 && 144 "Cannot deduce non-type template argument with depth > 0"); 145 assert((Value->isTypeDependent() || Value->isValueDependent()) && 146 "Expression template argument must be type- or value-dependent."); 147 148 if (Deduced[NTTP->getIndex()].isNull()) { 149 Deduced[NTTP->getIndex()] = TemplateArgument(Value->Retain()); 150 return Sema::TDK_Success; 151 } 152 153 if (Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Integral) { 154 // Okay, we deduced a constant in one case and a dependent expression 155 // in another case. FIXME: Later, we will check that instantiating the 156 // dependent expression gives us the constant value. 157 return Sema::TDK_Success; 158 } 159 160 if (Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Expression) { 161 // Compare the expressions for equality 162 llvm::FoldingSetNodeID ID1, ID2; 163 Deduced[NTTP->getIndex()].getAsExpr()->Profile(ID1, S.Context, true); 164 Value->Profile(ID2, S.Context, true); 165 if (ID1 == ID2) 166 return Sema::TDK_Success; 167 168 // FIXME: Fill in argument mismatch information 169 return Sema::TDK_NonDeducedMismatch; 170 } 171 172 return Sema::TDK_Success; 173} 174 175/// \brief Deduce the value of the given non-type template parameter 176/// from the given declaration. 177/// 178/// \returns true if deduction succeeded, false otherwise. 179static Sema::TemplateDeductionResult 180DeduceNonTypeTemplateArgument(Sema &S, 181 NonTypeTemplateParmDecl *NTTP, 182 Decl *D, 183 Sema::TemplateDeductionInfo &Info, 184 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 185 assert(NTTP->getDepth() == 0 && 186 "Cannot deduce non-type template argument with depth > 0"); 187 188 if (Deduced[NTTP->getIndex()].isNull()) { 189 Deduced[NTTP->getIndex()] = TemplateArgument(D->getCanonicalDecl()); 190 return Sema::TDK_Success; 191 } 192 193 if (Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Expression) { 194 // Okay, we deduced a declaration in one case and a dependent expression 195 // in another case. 196 return Sema::TDK_Success; 197 } 198 199 if (Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Declaration) { 200 // Compare the declarations for equality 201 if (Deduced[NTTP->getIndex()].getAsDecl()->getCanonicalDecl() == 202 D->getCanonicalDecl()) 203 return Sema::TDK_Success; 204 205 // FIXME: Fill in argument mismatch information 206 return Sema::TDK_NonDeducedMismatch; 207 } 208 209 return Sema::TDK_Success; 210} 211 212static Sema::TemplateDeductionResult 213DeduceTemplateArguments(Sema &S, 214 TemplateParameterList *TemplateParams, 215 TemplateName Param, 216 TemplateName Arg, 217 Sema::TemplateDeductionInfo &Info, 218 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 219 TemplateDecl *ParamDecl = Param.getAsTemplateDecl(); 220 if (!ParamDecl) { 221 // The parameter type is dependent and is not a template template parameter, 222 // so there is nothing that we can deduce. 223 return Sema::TDK_Success; 224 } 225 226 if (TemplateTemplateParmDecl *TempParam 227 = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) { 228 // Bind the template template parameter to the given template name. 229 TemplateArgument &ExistingArg = Deduced[TempParam->getIndex()]; 230 if (ExistingArg.isNull()) { 231 // This is the first deduction for this template template parameter. 232 ExistingArg = TemplateArgument(S.Context.getCanonicalTemplateName(Arg)); 233 return Sema::TDK_Success; 234 } 235 236 // Verify that the previous binding matches this deduction. 237 assert(ExistingArg.getKind() == TemplateArgument::Template); 238 if (S.Context.hasSameTemplateName(ExistingArg.getAsTemplate(), Arg)) 239 return Sema::TDK_Success; 240 241 // Inconsistent deduction. 242 Info.Param = TempParam; 243 Info.FirstArg = ExistingArg; 244 Info.SecondArg = TemplateArgument(Arg); 245 return Sema::TDK_Inconsistent; 246 } 247 248 // Verify that the two template names are equivalent. 249 if (S.Context.hasSameTemplateName(Param, Arg)) 250 return Sema::TDK_Success; 251 252 // Mismatch of non-dependent template parameter to argument. 253 Info.FirstArg = TemplateArgument(Param); 254 Info.SecondArg = TemplateArgument(Arg); 255 return Sema::TDK_NonDeducedMismatch; 256} 257 258/// \brief Deduce the template arguments by comparing the template parameter 259/// type (which is a template-id) with the template argument type. 260/// 261/// \param S the Sema 262/// 263/// \param TemplateParams the template parameters that we are deducing 264/// 265/// \param Param the parameter type 266/// 267/// \param Arg the argument type 268/// 269/// \param Info information about the template argument deduction itself 270/// 271/// \param Deduced the deduced template arguments 272/// 273/// \returns the result of template argument deduction so far. Note that a 274/// "success" result means that template argument deduction has not yet failed, 275/// but it may still fail, later, for other reasons. 276static Sema::TemplateDeductionResult 277DeduceTemplateArguments(Sema &S, 278 TemplateParameterList *TemplateParams, 279 const TemplateSpecializationType *Param, 280 QualType Arg, 281 Sema::TemplateDeductionInfo &Info, 282 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 283 assert(Arg.isCanonical() && "Argument type must be canonical"); 284 285 // Check whether the template argument is a dependent template-id. 286 if (const TemplateSpecializationType *SpecArg 287 = dyn_cast<TemplateSpecializationType>(Arg)) { 288 // Perform template argument deduction for the template name. 289 if (Sema::TemplateDeductionResult Result 290 = DeduceTemplateArguments(S, TemplateParams, 291 Param->getTemplateName(), 292 SpecArg->getTemplateName(), 293 Info, Deduced)) 294 return Result; 295 296 297 // Perform template argument deduction on each template 298 // argument. 299 unsigned NumArgs = std::min(SpecArg->getNumArgs(), Param->getNumArgs()); 300 for (unsigned I = 0; I != NumArgs; ++I) 301 if (Sema::TemplateDeductionResult Result 302 = DeduceTemplateArguments(S, TemplateParams, 303 Param->getArg(I), 304 SpecArg->getArg(I), 305 Info, Deduced)) 306 return Result; 307 308 return Sema::TDK_Success; 309 } 310 311 // If the argument type is a class template specialization, we 312 // perform template argument deduction using its template 313 // arguments. 314 const RecordType *RecordArg = dyn_cast<RecordType>(Arg); 315 if (!RecordArg) 316 return Sema::TDK_NonDeducedMismatch; 317 318 ClassTemplateSpecializationDecl *SpecArg 319 = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl()); 320 if (!SpecArg) 321 return Sema::TDK_NonDeducedMismatch; 322 323 // Perform template argument deduction for the template name. 324 if (Sema::TemplateDeductionResult Result 325 = DeduceTemplateArguments(S, 326 TemplateParams, 327 Param->getTemplateName(), 328 TemplateName(SpecArg->getSpecializedTemplate()), 329 Info, Deduced)) 330 return Result; 331 332 unsigned NumArgs = Param->getNumArgs(); 333 const TemplateArgumentList &ArgArgs = SpecArg->getTemplateArgs(); 334 if (NumArgs != ArgArgs.size()) 335 return Sema::TDK_NonDeducedMismatch; 336 337 for (unsigned I = 0; I != NumArgs; ++I) 338 if (Sema::TemplateDeductionResult Result 339 = DeduceTemplateArguments(S, TemplateParams, 340 Param->getArg(I), 341 ArgArgs.get(I), 342 Info, Deduced)) 343 return Result; 344 345 return Sema::TDK_Success; 346} 347 348/// \brief Deduce the template arguments by comparing the parameter type and 349/// the argument type (C++ [temp.deduct.type]). 350/// 351/// \param S the semantic analysis object within which we are deducing 352/// 353/// \param TemplateParams the template parameters that we are deducing 354/// 355/// \param ParamIn the parameter type 356/// 357/// \param ArgIn the argument type 358/// 359/// \param Info information about the template argument deduction itself 360/// 361/// \param Deduced the deduced template arguments 362/// 363/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe 364/// how template argument deduction is performed. 365/// 366/// \returns the result of template argument deduction so far. Note that a 367/// "success" result means that template argument deduction has not yet failed, 368/// but it may still fail, later, for other reasons. 369static Sema::TemplateDeductionResult 370DeduceTemplateArguments(Sema &S, 371 TemplateParameterList *TemplateParams, 372 QualType ParamIn, QualType ArgIn, 373 Sema::TemplateDeductionInfo &Info, 374 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 375 unsigned TDF) { 376 // We only want to look at the canonical types, since typedefs and 377 // sugar are not part of template argument deduction. 378 QualType Param = S.Context.getCanonicalType(ParamIn); 379 QualType Arg = S.Context.getCanonicalType(ArgIn); 380 381 // C++0x [temp.deduct.call]p4 bullet 1: 382 // - If the original P is a reference type, the deduced A (i.e., the type 383 // referred to by the reference) can be more cv-qualified than the 384 // transformed A. 385 if (TDF & TDF_ParamWithReferenceType) { 386 Qualifiers Quals; 387 QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals); 388 Quals.setCVRQualifiers(Quals.getCVRQualifiers() & 389 Arg.getCVRQualifiersThroughArrayTypes()); 390 Param = S.Context.getQualifiedType(UnqualParam, Quals); 391 } 392 393 // If the parameter type is not dependent, there is nothing to deduce. 394 if (!Param->isDependentType()) { 395 if (!(TDF & TDF_SkipNonDependent) && Param != Arg) { 396 397 return Sema::TDK_NonDeducedMismatch; 398 } 399 400 return Sema::TDK_Success; 401 } 402 403 // C++ [temp.deduct.type]p9: 404 // A template type argument T, a template template argument TT or a 405 // template non-type argument i can be deduced if P and A have one of 406 // the following forms: 407 // 408 // T 409 // cv-list T 410 if (const TemplateTypeParmType *TemplateTypeParm 411 = Param->getAs<TemplateTypeParmType>()) { 412 unsigned Index = TemplateTypeParm->getIndex(); 413 bool RecanonicalizeArg = false; 414 415 // If the argument type is an array type, move the qualifiers up to the 416 // top level, so they can be matched with the qualifiers on the parameter. 417 // FIXME: address spaces, ObjC GC qualifiers 418 if (isa<ArrayType>(Arg)) { 419 Qualifiers Quals; 420 Arg = S.Context.getUnqualifiedArrayType(Arg, Quals); 421 if (Quals) { 422 Arg = S.Context.getQualifiedType(Arg, Quals); 423 RecanonicalizeArg = true; 424 } 425 } 426 427 // The argument type can not be less qualified than the parameter 428 // type. 429 if (Param.isMoreQualifiedThan(Arg) && !(TDF & TDF_IgnoreQualifiers)) { 430 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 431 Info.FirstArg = Deduced[Index]; 432 Info.SecondArg = TemplateArgument(Arg); 433 return Sema::TDK_InconsistentQuals; 434 } 435 436 assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0"); 437 assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function"); 438 QualType DeducedType = Arg; 439 DeducedType.removeCVRQualifiers(Param.getCVRQualifiers()); 440 if (RecanonicalizeArg) 441 DeducedType = S.Context.getCanonicalType(DeducedType); 442 443 if (Deduced[Index].isNull()) 444 Deduced[Index] = TemplateArgument(DeducedType); 445 else { 446 // C++ [temp.deduct.type]p2: 447 // [...] If type deduction cannot be done for any P/A pair, or if for 448 // any pair the deduction leads to more than one possible set of 449 // deduced values, or if different pairs yield different deduced 450 // values, or if any template argument remains neither deduced nor 451 // explicitly specified, template argument deduction fails. 452 if (Deduced[Index].getAsType() != DeducedType) { 453 Info.Param 454 = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 455 Info.FirstArg = Deduced[Index]; 456 Info.SecondArg = TemplateArgument(Arg); 457 return Sema::TDK_Inconsistent; 458 } 459 } 460 return Sema::TDK_Success; 461 } 462 463 // Set up the template argument deduction information for a failure. 464 Info.FirstArg = TemplateArgument(ParamIn); 465 Info.SecondArg = TemplateArgument(ArgIn); 466 467 // Check the cv-qualifiers on the parameter and argument types. 468 if (!(TDF & TDF_IgnoreQualifiers)) { 469 if (TDF & TDF_ParamWithReferenceType) { 470 if (Param.isMoreQualifiedThan(Arg)) 471 return Sema::TDK_NonDeducedMismatch; 472 } else { 473 if (Param.getCVRQualifiers() != Arg.getCVRQualifiers()) 474 return Sema::TDK_NonDeducedMismatch; 475 } 476 } 477 478 switch (Param->getTypeClass()) { 479 // No deduction possible for these types 480 case Type::Builtin: 481 return Sema::TDK_NonDeducedMismatch; 482 483 // T * 484 case Type::Pointer: { 485 QualType PointeeType; 486 if (const PointerType *PointerArg = Arg->getAs<PointerType>()) { 487 PointeeType = PointerArg->getPointeeType(); 488 } else if (const ObjCObjectPointerType *PointerArg 489 = Arg->getAs<ObjCObjectPointerType>()) { 490 PointeeType = PointerArg->getPointeeType(); 491 } else { 492 return Sema::TDK_NonDeducedMismatch; 493 } 494 495 unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass); 496 return DeduceTemplateArguments(S, TemplateParams, 497 cast<PointerType>(Param)->getPointeeType(), 498 PointeeType, 499 Info, Deduced, SubTDF); 500 } 501 502 // T & 503 case Type::LValueReference: { 504 const LValueReferenceType *ReferenceArg = Arg->getAs<LValueReferenceType>(); 505 if (!ReferenceArg) 506 return Sema::TDK_NonDeducedMismatch; 507 508 return DeduceTemplateArguments(S, TemplateParams, 509 cast<LValueReferenceType>(Param)->getPointeeType(), 510 ReferenceArg->getPointeeType(), 511 Info, Deduced, 0); 512 } 513 514 // T && [C++0x] 515 case Type::RValueReference: { 516 const RValueReferenceType *ReferenceArg = Arg->getAs<RValueReferenceType>(); 517 if (!ReferenceArg) 518 return Sema::TDK_NonDeducedMismatch; 519 520 return DeduceTemplateArguments(S, TemplateParams, 521 cast<RValueReferenceType>(Param)->getPointeeType(), 522 ReferenceArg->getPointeeType(), 523 Info, Deduced, 0); 524 } 525 526 // T [] (implied, but not stated explicitly) 527 case Type::IncompleteArray: { 528 const IncompleteArrayType *IncompleteArrayArg = 529 S.Context.getAsIncompleteArrayType(Arg); 530 if (!IncompleteArrayArg) 531 return Sema::TDK_NonDeducedMismatch; 532 533 return DeduceTemplateArguments(S, TemplateParams, 534 S.Context.getAsIncompleteArrayType(Param)->getElementType(), 535 IncompleteArrayArg->getElementType(), 536 Info, Deduced, 0); 537 } 538 539 // T [integer-constant] 540 case Type::ConstantArray: { 541 const ConstantArrayType *ConstantArrayArg = 542 S.Context.getAsConstantArrayType(Arg); 543 if (!ConstantArrayArg) 544 return Sema::TDK_NonDeducedMismatch; 545 546 const ConstantArrayType *ConstantArrayParm = 547 S.Context.getAsConstantArrayType(Param); 548 if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize()) 549 return Sema::TDK_NonDeducedMismatch; 550 551 return DeduceTemplateArguments(S, TemplateParams, 552 ConstantArrayParm->getElementType(), 553 ConstantArrayArg->getElementType(), 554 Info, Deduced, 0); 555 } 556 557 // type [i] 558 case Type::DependentSizedArray: { 559 const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg); 560 if (!ArrayArg) 561 return Sema::TDK_NonDeducedMismatch; 562 563 // Check the element type of the arrays 564 const DependentSizedArrayType *DependentArrayParm 565 = S.Context.getAsDependentSizedArrayType(Param); 566 if (Sema::TemplateDeductionResult Result 567 = DeduceTemplateArguments(S, TemplateParams, 568 DependentArrayParm->getElementType(), 569 ArrayArg->getElementType(), 570 Info, Deduced, 0)) 571 return Result; 572 573 // Determine the array bound is something we can deduce. 574 NonTypeTemplateParmDecl *NTTP 575 = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr()); 576 if (!NTTP) 577 return Sema::TDK_Success; 578 579 // We can perform template argument deduction for the given non-type 580 // template parameter. 581 assert(NTTP->getDepth() == 0 && 582 "Cannot deduce non-type template argument at depth > 0"); 583 if (const ConstantArrayType *ConstantArrayArg 584 = dyn_cast<ConstantArrayType>(ArrayArg)) { 585 llvm::APSInt Size(ConstantArrayArg->getSize()); 586 return DeduceNonTypeTemplateArgument(S, NTTP, Size, 587 S.Context.getSizeType(), 588 /*ArrayBound=*/true, 589 Info, Deduced); 590 } 591 if (const DependentSizedArrayType *DependentArrayArg 592 = dyn_cast<DependentSizedArrayType>(ArrayArg)) 593 return DeduceNonTypeTemplateArgument(S, NTTP, 594 DependentArrayArg->getSizeExpr(), 595 Info, Deduced); 596 597 // Incomplete type does not match a dependently-sized array type 598 return Sema::TDK_NonDeducedMismatch; 599 } 600 601 // type(*)(T) 602 // T(*)() 603 // T(*)(T) 604 case Type::FunctionProto: { 605 const FunctionProtoType *FunctionProtoArg = 606 dyn_cast<FunctionProtoType>(Arg); 607 if (!FunctionProtoArg) 608 return Sema::TDK_NonDeducedMismatch; 609 610 const FunctionProtoType *FunctionProtoParam = 611 cast<FunctionProtoType>(Param); 612 613 if (FunctionProtoParam->getTypeQuals() != 614 FunctionProtoArg->getTypeQuals()) 615 return Sema::TDK_NonDeducedMismatch; 616 617 if (FunctionProtoParam->getNumArgs() != FunctionProtoArg->getNumArgs()) 618 return Sema::TDK_NonDeducedMismatch; 619 620 if (FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic()) 621 return Sema::TDK_NonDeducedMismatch; 622 623 // Check return types. 624 if (Sema::TemplateDeductionResult Result 625 = DeduceTemplateArguments(S, TemplateParams, 626 FunctionProtoParam->getResultType(), 627 FunctionProtoArg->getResultType(), 628 Info, Deduced, 0)) 629 return Result; 630 631 for (unsigned I = 0, N = FunctionProtoParam->getNumArgs(); I != N; ++I) { 632 // Check argument types. 633 if (Sema::TemplateDeductionResult Result 634 = DeduceTemplateArguments(S, TemplateParams, 635 FunctionProtoParam->getArgType(I), 636 FunctionProtoArg->getArgType(I), 637 Info, Deduced, 0)) 638 return Result; 639 } 640 641 return Sema::TDK_Success; 642 } 643 644 case Type::InjectedClassName: { 645 // Treat a template's injected-class-name as if the template 646 // specialization type had been used. 647 Param = cast<InjectedClassNameType>(Param) 648 ->getInjectedSpecializationType(); 649 assert(isa<TemplateSpecializationType>(Param) && 650 "injected class name is not a template specialization type"); 651 // fall through 652 } 653 654 // template-name<T> (where template-name refers to a class template) 655 // template-name<i> 656 // TT<T> 657 // TT<i> 658 // TT<> 659 case Type::TemplateSpecialization: { 660 const TemplateSpecializationType *SpecParam 661 = cast<TemplateSpecializationType>(Param); 662 663 // Try to deduce template arguments from the template-id. 664 Sema::TemplateDeductionResult Result 665 = DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg, 666 Info, Deduced); 667 668 if (Result && (TDF & TDF_DerivedClass)) { 669 // C++ [temp.deduct.call]p3b3: 670 // If P is a class, and P has the form template-id, then A can be a 671 // derived class of the deduced A. Likewise, if P is a pointer to a 672 // class of the form template-id, A can be a pointer to a derived 673 // class pointed to by the deduced A. 674 // 675 // More importantly: 676 // These alternatives are considered only if type deduction would 677 // otherwise fail. 678 if (const RecordType *RecordT = Arg->getAs<RecordType>()) { 679 // We cannot inspect base classes as part of deduction when the type 680 // is incomplete, so either instantiate any templates necessary to 681 // complete the type, or skip over it if it cannot be completed. 682 if (S.RequireCompleteType(Info.getLocation(), Arg, 0)) 683 return Result; 684 685 // Use data recursion to crawl through the list of base classes. 686 // Visited contains the set of nodes we have already visited, while 687 // ToVisit is our stack of records that we still need to visit. 688 llvm::SmallPtrSet<const RecordType *, 8> Visited; 689 llvm::SmallVector<const RecordType *, 8> ToVisit; 690 ToVisit.push_back(RecordT); 691 bool Successful = false; 692 while (!ToVisit.empty()) { 693 // Retrieve the next class in the inheritance hierarchy. 694 const RecordType *NextT = ToVisit.back(); 695 ToVisit.pop_back(); 696 697 // If we have already seen this type, skip it. 698 if (!Visited.insert(NextT)) 699 continue; 700 701 // If this is a base class, try to perform template argument 702 // deduction from it. 703 if (NextT != RecordT) { 704 Sema::TemplateDeductionResult BaseResult 705 = DeduceTemplateArguments(S, TemplateParams, SpecParam, 706 QualType(NextT, 0), Info, Deduced); 707 708 // If template argument deduction for this base was successful, 709 // note that we had some success. 710 if (BaseResult == Sema::TDK_Success) 711 Successful = true; 712 } 713 714 // Visit base classes 715 CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl()); 716 for (CXXRecordDecl::base_class_iterator Base = Next->bases_begin(), 717 BaseEnd = Next->bases_end(); 718 Base != BaseEnd; ++Base) { 719 assert(Base->getType()->isRecordType() && 720 "Base class that isn't a record?"); 721 ToVisit.push_back(Base->getType()->getAs<RecordType>()); 722 } 723 } 724 725 if (Successful) 726 return Sema::TDK_Success; 727 } 728 729 } 730 731 return Result; 732 } 733 734 // T type::* 735 // T T::* 736 // T (type::*)() 737 // type (T::*)() 738 // type (type::*)(T) 739 // type (T::*)(T) 740 // T (type::*)(T) 741 // T (T::*)() 742 // T (T::*)(T) 743 case Type::MemberPointer: { 744 const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param); 745 const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg); 746 if (!MemPtrArg) 747 return Sema::TDK_NonDeducedMismatch; 748 749 if (Sema::TemplateDeductionResult Result 750 = DeduceTemplateArguments(S, TemplateParams, 751 MemPtrParam->getPointeeType(), 752 MemPtrArg->getPointeeType(), 753 Info, Deduced, 754 TDF & TDF_IgnoreQualifiers)) 755 return Result; 756 757 return DeduceTemplateArguments(S, TemplateParams, 758 QualType(MemPtrParam->getClass(), 0), 759 QualType(MemPtrArg->getClass(), 0), 760 Info, Deduced, 0); 761 } 762 763 // (clang extension) 764 // 765 // type(^)(T) 766 // T(^)() 767 // T(^)(T) 768 case Type::BlockPointer: { 769 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param); 770 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg); 771 772 if (!BlockPtrArg) 773 return Sema::TDK_NonDeducedMismatch; 774 775 return DeduceTemplateArguments(S, TemplateParams, 776 BlockPtrParam->getPointeeType(), 777 BlockPtrArg->getPointeeType(), Info, 778 Deduced, 0); 779 } 780 781 case Type::TypeOfExpr: 782 case Type::TypeOf: 783 case Type::DependentName: 784 // No template argument deduction for these types 785 return Sema::TDK_Success; 786 787 default: 788 break; 789 } 790 791 // FIXME: Many more cases to go (to go). 792 return Sema::TDK_Success; 793} 794 795static Sema::TemplateDeductionResult 796DeduceTemplateArguments(Sema &S, 797 TemplateParameterList *TemplateParams, 798 const TemplateArgument &Param, 799 const TemplateArgument &Arg, 800 Sema::TemplateDeductionInfo &Info, 801 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 802 switch (Param.getKind()) { 803 case TemplateArgument::Null: 804 assert(false && "Null template argument in parameter list"); 805 break; 806 807 case TemplateArgument::Type: 808 if (Arg.getKind() == TemplateArgument::Type) 809 return DeduceTemplateArguments(S, TemplateParams, Param.getAsType(), 810 Arg.getAsType(), Info, Deduced, 0); 811 Info.FirstArg = Param; 812 Info.SecondArg = Arg; 813 return Sema::TDK_NonDeducedMismatch; 814 815 case TemplateArgument::Template: 816 if (Arg.getKind() == TemplateArgument::Template) 817 return DeduceTemplateArguments(S, TemplateParams, 818 Param.getAsTemplate(), 819 Arg.getAsTemplate(), Info, Deduced); 820 Info.FirstArg = Param; 821 Info.SecondArg = Arg; 822 return Sema::TDK_NonDeducedMismatch; 823 824 case TemplateArgument::Declaration: 825 if (Arg.getKind() == TemplateArgument::Declaration && 826 Param.getAsDecl()->getCanonicalDecl() == 827 Arg.getAsDecl()->getCanonicalDecl()) 828 return Sema::TDK_Success; 829 830 Info.FirstArg = Param; 831 Info.SecondArg = Arg; 832 return Sema::TDK_NonDeducedMismatch; 833 834 case TemplateArgument::Integral: 835 if (Arg.getKind() == TemplateArgument::Integral) { 836 if (hasSameExtendedValue(*Param.getAsIntegral(), *Arg.getAsIntegral())) 837 return Sema::TDK_Success; 838 839 Info.FirstArg = Param; 840 Info.SecondArg = Arg; 841 return Sema::TDK_NonDeducedMismatch; 842 } 843 844 if (Arg.getKind() == TemplateArgument::Expression) { 845 Info.FirstArg = Param; 846 Info.SecondArg = Arg; 847 return Sema::TDK_NonDeducedMismatch; 848 } 849 850 assert(false && "Type/value mismatch"); 851 Info.FirstArg = Param; 852 Info.SecondArg = Arg; 853 return Sema::TDK_NonDeducedMismatch; 854 855 case TemplateArgument::Expression: { 856 if (NonTypeTemplateParmDecl *NTTP 857 = getDeducedParameterFromExpr(Param.getAsExpr())) { 858 if (Arg.getKind() == TemplateArgument::Integral) 859 return DeduceNonTypeTemplateArgument(S, NTTP, 860 *Arg.getAsIntegral(), 861 Arg.getIntegralType(), 862 /*ArrayBound=*/false, 863 Info, Deduced); 864 if (Arg.getKind() == TemplateArgument::Expression) 865 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(), 866 Info, Deduced); 867 if (Arg.getKind() == TemplateArgument::Declaration) 868 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(), 869 Info, Deduced); 870 871 assert(false && "Type/value mismatch"); 872 Info.FirstArg = Param; 873 Info.SecondArg = Arg; 874 return Sema::TDK_NonDeducedMismatch; 875 } 876 877 // Can't deduce anything, but that's okay. 878 return Sema::TDK_Success; 879 } 880 case TemplateArgument::Pack: 881 assert(0 && "FIXME: Implement!"); 882 break; 883 } 884 885 return Sema::TDK_Success; 886} 887 888static Sema::TemplateDeductionResult 889DeduceTemplateArguments(Sema &S, 890 TemplateParameterList *TemplateParams, 891 const TemplateArgumentList &ParamList, 892 const TemplateArgumentList &ArgList, 893 Sema::TemplateDeductionInfo &Info, 894 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 895 assert(ParamList.size() == ArgList.size()); 896 for (unsigned I = 0, N = ParamList.size(); I != N; ++I) { 897 if (Sema::TemplateDeductionResult Result 898 = DeduceTemplateArguments(S, TemplateParams, 899 ParamList[I], ArgList[I], 900 Info, Deduced)) 901 return Result; 902 } 903 return Sema::TDK_Success; 904} 905 906/// \brief Determine whether two template arguments are the same. 907static bool isSameTemplateArg(ASTContext &Context, 908 const TemplateArgument &X, 909 const TemplateArgument &Y) { 910 if (X.getKind() != Y.getKind()) 911 return false; 912 913 switch (X.getKind()) { 914 case TemplateArgument::Null: 915 assert(false && "Comparing NULL template argument"); 916 break; 917 918 case TemplateArgument::Type: 919 return Context.getCanonicalType(X.getAsType()) == 920 Context.getCanonicalType(Y.getAsType()); 921 922 case TemplateArgument::Declaration: 923 return X.getAsDecl()->getCanonicalDecl() == 924 Y.getAsDecl()->getCanonicalDecl(); 925 926 case TemplateArgument::Template: 927 return Context.getCanonicalTemplateName(X.getAsTemplate()) 928 .getAsVoidPointer() == 929 Context.getCanonicalTemplateName(Y.getAsTemplate()) 930 .getAsVoidPointer(); 931 932 case TemplateArgument::Integral: 933 return *X.getAsIntegral() == *Y.getAsIntegral(); 934 935 case TemplateArgument::Expression: { 936 llvm::FoldingSetNodeID XID, YID; 937 X.getAsExpr()->Profile(XID, Context, true); 938 Y.getAsExpr()->Profile(YID, Context, true); 939 return XID == YID; 940 } 941 942 case TemplateArgument::Pack: 943 if (X.pack_size() != Y.pack_size()) 944 return false; 945 946 for (TemplateArgument::pack_iterator XP = X.pack_begin(), 947 XPEnd = X.pack_end(), 948 YP = Y.pack_begin(); 949 XP != XPEnd; ++XP, ++YP) 950 if (!isSameTemplateArg(Context, *XP, *YP)) 951 return false; 952 953 return true; 954 } 955 956 return false; 957} 958 959/// \brief Helper function to build a TemplateParameter when we don't 960/// know its type statically. 961static TemplateParameter makeTemplateParameter(Decl *D) { 962 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D)) 963 return TemplateParameter(TTP); 964 else if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) 965 return TemplateParameter(NTTP); 966 967 return TemplateParameter(cast<TemplateTemplateParmDecl>(D)); 968} 969 970/// Complete template argument deduction for a class template partial 971/// specialization. 972static Sema::TemplateDeductionResult 973FinishTemplateArgumentDeduction(Sema &S, 974 ClassTemplatePartialSpecializationDecl *Partial, 975 const TemplateArgumentList &TemplateArgs, 976 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 977 Sema::TemplateDeductionInfo &Info) { 978 // Trap errors. 979 Sema::SFINAETrap Trap(S); 980 981 Sema::ContextRAII SavedContext(S, Partial); 982 983 // C++ [temp.deduct.type]p2: 984 // [...] or if any template argument remains neither deduced nor 985 // explicitly specified, template argument deduction fails. 986 TemplateArgumentListBuilder Builder(Partial->getTemplateParameters(), 987 Deduced.size()); 988 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 989 if (Deduced[I].isNull()) { 990 Decl *Param 991 = const_cast<NamedDecl *>( 992 Partial->getTemplateParameters()->getParam(I)); 993 Info.Param = makeTemplateParameter(Param); 994 return Sema::TDK_Incomplete; 995 } 996 997 Builder.Append(Deduced[I]); 998 } 999 1000 // Form the template argument list from the deduced template arguments. 1001 TemplateArgumentList *DeducedArgumentList 1002 = new (S.Context) TemplateArgumentList(S.Context, Builder, 1003 /*TakeArgs=*/true); 1004 Info.reset(DeducedArgumentList); 1005 1006 // Substitute the deduced template arguments into the template 1007 // arguments of the class template partial specialization, and 1008 // verify that the instantiated template arguments are both valid 1009 // and are equivalent to the template arguments originally provided 1010 // to the class template. 1011 // FIXME: Do we have to correct the types of deduced non-type template 1012 // arguments (in particular, integral non-type template arguments?). 1013 Sema::LocalInstantiationScope InstScope(S); 1014 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate(); 1015 const TemplateArgumentLoc *PartialTemplateArgs 1016 = Partial->getTemplateArgsAsWritten(); 1017 unsigned N = Partial->getNumTemplateArgsAsWritten(); 1018 1019 // Note that we don't provide the langle and rangle locations. 1020 TemplateArgumentListInfo InstArgs; 1021 1022 for (unsigned I = 0; I != N; ++I) { 1023 Decl *Param = const_cast<NamedDecl *>( 1024 ClassTemplate->getTemplateParameters()->getParam(I)); 1025 TemplateArgumentLoc InstArg; 1026 if (S.Subst(PartialTemplateArgs[I], InstArg, 1027 MultiLevelTemplateArgumentList(*DeducedArgumentList))) { 1028 Info.Param = makeTemplateParameter(Param); 1029 Info.FirstArg = PartialTemplateArgs[I].getArgument(); 1030 return Sema::TDK_SubstitutionFailure; 1031 } 1032 InstArgs.addArgument(InstArg); 1033 } 1034 1035 TemplateArgumentListBuilder ConvertedInstArgs( 1036 ClassTemplate->getTemplateParameters(), N); 1037 1038 if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(), 1039 InstArgs, false, ConvertedInstArgs)) 1040 return Sema::TDK_SubstitutionFailure; 1041 1042 for (unsigned I = 0, E = ConvertedInstArgs.flatSize(); I != E; ++I) { 1043 TemplateArgument InstArg = ConvertedInstArgs.getFlatArguments()[I]; 1044 1045 Decl *Param = const_cast<NamedDecl *>( 1046 ClassTemplate->getTemplateParameters()->getParam(I)); 1047 1048 if (InstArg.getKind() == TemplateArgument::Expression) { 1049 // When the argument is an expression, check the expression result 1050 // against the actual template parameter to get down to the canonical 1051 // template argument. 1052 Expr *InstExpr = InstArg.getAsExpr(); 1053 if (NonTypeTemplateParmDecl *NTTP 1054 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 1055 if (S.CheckTemplateArgument(NTTP, NTTP->getType(), InstExpr, InstArg)) { 1056 Info.Param = makeTemplateParameter(Param); 1057 Info.FirstArg = Partial->getTemplateArgs()[I]; 1058 return Sema::TDK_SubstitutionFailure; 1059 } 1060 } 1061 } 1062 1063 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) { 1064 Info.Param = makeTemplateParameter(Param); 1065 Info.FirstArg = TemplateArgs[I]; 1066 Info.SecondArg = InstArg; 1067 return Sema::TDK_NonDeducedMismatch; 1068 } 1069 } 1070 1071 if (Trap.hasErrorOccurred()) 1072 return Sema::TDK_SubstitutionFailure; 1073 1074 return Sema::TDK_Success; 1075} 1076 1077/// \brief Perform template argument deduction to determine whether 1078/// the given template arguments match the given class template 1079/// partial specialization per C++ [temp.class.spec.match]. 1080Sema::TemplateDeductionResult 1081Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial, 1082 const TemplateArgumentList &TemplateArgs, 1083 TemplateDeductionInfo &Info) { 1084 // C++ [temp.class.spec.match]p2: 1085 // A partial specialization matches a given actual template 1086 // argument list if the template arguments of the partial 1087 // specialization can be deduced from the actual template argument 1088 // list (14.8.2). 1089 SFINAETrap Trap(*this); 1090 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 1091 Deduced.resize(Partial->getTemplateParameters()->size()); 1092 if (TemplateDeductionResult Result 1093 = ::DeduceTemplateArguments(*this, 1094 Partial->getTemplateParameters(), 1095 Partial->getTemplateArgs(), 1096 TemplateArgs, Info, Deduced)) 1097 return Result; 1098 1099 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial, 1100 Deduced.data(), Deduced.size()); 1101 if (Inst) 1102 return TDK_InstantiationDepth; 1103 1104 if (Trap.hasErrorOccurred()) 1105 return Sema::TDK_SubstitutionFailure; 1106 1107 return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs, 1108 Deduced, Info); 1109} 1110 1111/// \brief Determine whether the given type T is a simple-template-id type. 1112static bool isSimpleTemplateIdType(QualType T) { 1113 if (const TemplateSpecializationType *Spec 1114 = T->getAs<TemplateSpecializationType>()) 1115 return Spec->getTemplateName().getAsTemplateDecl() != 0; 1116 1117 return false; 1118} 1119 1120/// \brief Substitute the explicitly-provided template arguments into the 1121/// given function template according to C++ [temp.arg.explicit]. 1122/// 1123/// \param FunctionTemplate the function template into which the explicit 1124/// template arguments will be substituted. 1125/// 1126/// \param ExplicitTemplateArguments the explicitly-specified template 1127/// arguments. 1128/// 1129/// \param Deduced the deduced template arguments, which will be populated 1130/// with the converted and checked explicit template arguments. 1131/// 1132/// \param ParamTypes will be populated with the instantiated function 1133/// parameters. 1134/// 1135/// \param FunctionType if non-NULL, the result type of the function template 1136/// will also be instantiated and the pointed-to value will be updated with 1137/// the instantiated function type. 1138/// 1139/// \param Info if substitution fails for any reason, this object will be 1140/// populated with more information about the failure. 1141/// 1142/// \returns TDK_Success if substitution was successful, or some failure 1143/// condition. 1144Sema::TemplateDeductionResult 1145Sema::SubstituteExplicitTemplateArguments( 1146 FunctionTemplateDecl *FunctionTemplate, 1147 const TemplateArgumentListInfo &ExplicitTemplateArgs, 1148 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1149 llvm::SmallVectorImpl<QualType> &ParamTypes, 1150 QualType *FunctionType, 1151 TemplateDeductionInfo &Info) { 1152 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1153 TemplateParameterList *TemplateParams 1154 = FunctionTemplate->getTemplateParameters(); 1155 1156 if (ExplicitTemplateArgs.size() == 0) { 1157 // No arguments to substitute; just copy over the parameter types and 1158 // fill in the function type. 1159 for (FunctionDecl::param_iterator P = Function->param_begin(), 1160 PEnd = Function->param_end(); 1161 P != PEnd; 1162 ++P) 1163 ParamTypes.push_back((*P)->getType()); 1164 1165 if (FunctionType) 1166 *FunctionType = Function->getType(); 1167 return TDK_Success; 1168 } 1169 1170 // Substitution of the explicit template arguments into a function template 1171 /// is a SFINAE context. Trap any errors that might occur. 1172 SFINAETrap Trap(*this); 1173 1174 // C++ [temp.arg.explicit]p3: 1175 // Template arguments that are present shall be specified in the 1176 // declaration order of their corresponding template-parameters. The 1177 // template argument list shall not specify more template-arguments than 1178 // there are corresponding template-parameters. 1179 TemplateArgumentListBuilder Builder(TemplateParams, 1180 ExplicitTemplateArgs.size()); 1181 1182 // Enter a new template instantiation context where we check the 1183 // explicitly-specified template arguments against this function template, 1184 // and then substitute them into the function parameter types. 1185 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1186 FunctionTemplate, Deduced.data(), Deduced.size(), 1187 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution); 1188 if (Inst) 1189 return TDK_InstantiationDepth; 1190 1191 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 1192 1193 if (CheckTemplateArgumentList(FunctionTemplate, 1194 SourceLocation(), 1195 ExplicitTemplateArgs, 1196 true, 1197 Builder) || Trap.hasErrorOccurred()) { 1198 unsigned Index = Builder.structuredSize(); 1199 if (Index >= TemplateParams->size()) 1200 Index = TemplateParams->size() - 1; 1201 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index)); 1202 return TDK_InvalidExplicitArguments; 1203 } 1204 1205 // Form the template argument list from the explicitly-specified 1206 // template arguments. 1207 TemplateArgumentList *ExplicitArgumentList 1208 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true); 1209 Info.reset(ExplicitArgumentList); 1210 1211 // Instantiate the types of each of the function parameters given the 1212 // explicitly-specified template arguments. 1213 for (FunctionDecl::param_iterator P = Function->param_begin(), 1214 PEnd = Function->param_end(); 1215 P != PEnd; 1216 ++P) { 1217 QualType ParamType 1218 = SubstType((*P)->getType(), 1219 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1220 (*P)->getLocation(), (*P)->getDeclName()); 1221 if (ParamType.isNull() || Trap.hasErrorOccurred()) 1222 return TDK_SubstitutionFailure; 1223 1224 ParamTypes.push_back(ParamType); 1225 } 1226 1227 // If the caller wants a full function type back, instantiate the return 1228 // type and form that function type. 1229 if (FunctionType) { 1230 // FIXME: exception-specifications? 1231 const FunctionProtoType *Proto 1232 = Function->getType()->getAs<FunctionProtoType>(); 1233 assert(Proto && "Function template does not have a prototype?"); 1234 1235 QualType ResultType 1236 = SubstType(Proto->getResultType(), 1237 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1238 Function->getTypeSpecStartLoc(), 1239 Function->getDeclName()); 1240 if (ResultType.isNull() || Trap.hasErrorOccurred()) 1241 return TDK_SubstitutionFailure; 1242 1243 *FunctionType = BuildFunctionType(ResultType, 1244 ParamTypes.data(), ParamTypes.size(), 1245 Proto->isVariadic(), 1246 Proto->getTypeQuals(), 1247 Function->getLocation(), 1248 Function->getDeclName(), 1249 Proto->getExtInfo()); 1250 if (FunctionType->isNull() || Trap.hasErrorOccurred()) 1251 return TDK_SubstitutionFailure; 1252 } 1253 1254 // C++ [temp.arg.explicit]p2: 1255 // Trailing template arguments that can be deduced (14.8.2) may be 1256 // omitted from the list of explicit template-arguments. If all of the 1257 // template arguments can be deduced, they may all be omitted; in this 1258 // case, the empty template argument list <> itself may also be omitted. 1259 // 1260 // Take all of the explicitly-specified arguments and put them into the 1261 // set of deduced template arguments. 1262 Deduced.reserve(TemplateParams->size()); 1263 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) 1264 Deduced.push_back(ExplicitArgumentList->get(I)); 1265 1266 return TDK_Success; 1267} 1268 1269/// \brief Allocate a TemplateArgumentLoc where all locations have 1270/// been initialized to the given location. 1271/// 1272/// \param S The semantic analysis object. 1273/// 1274/// \param The template argument we are producing template argument 1275/// location information for. 1276/// 1277/// \param NTTPType For a declaration template argument, the type of 1278/// the non-type template parameter that corresponds to this template 1279/// argument. 1280/// 1281/// \param Loc The source location to use for the resulting template 1282/// argument. 1283static TemplateArgumentLoc 1284getTrivialTemplateArgumentLoc(Sema &S, 1285 const TemplateArgument &Arg, 1286 QualType NTTPType, 1287 SourceLocation Loc) { 1288 switch (Arg.getKind()) { 1289 case TemplateArgument::Null: 1290 llvm_unreachable("Can't get a NULL template argument here"); 1291 break; 1292 1293 case TemplateArgument::Type: 1294 return TemplateArgumentLoc(Arg, 1295 S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc)); 1296 1297 case TemplateArgument::Declaration: { 1298 Expr *E 1299 = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc) 1300 .takeAs<Expr>(); 1301 return TemplateArgumentLoc(TemplateArgument(E), E); 1302 } 1303 1304 case TemplateArgument::Integral: { 1305 Expr *E 1306 = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).takeAs<Expr>(); 1307 return TemplateArgumentLoc(TemplateArgument(E), E); 1308 } 1309 1310 case TemplateArgument::Template: 1311 return TemplateArgumentLoc(Arg, SourceRange(), Loc); 1312 1313 case TemplateArgument::Expression: 1314 return TemplateArgumentLoc(Arg, Arg.getAsExpr()); 1315 1316 case TemplateArgument::Pack: 1317 llvm_unreachable("Template parameter packs are not yet supported"); 1318 } 1319 1320 return TemplateArgumentLoc(); 1321} 1322 1323/// \brief Finish template argument deduction for a function template, 1324/// checking the deduced template arguments for completeness and forming 1325/// the function template specialization. 1326Sema::TemplateDeductionResult 1327Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate, 1328 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1329 unsigned NumExplicitlySpecified, 1330 FunctionDecl *&Specialization, 1331 TemplateDeductionInfo &Info) { 1332 TemplateParameterList *TemplateParams 1333 = FunctionTemplate->getTemplateParameters(); 1334 1335 // Template argument deduction for function templates in a SFINAE context. 1336 // Trap any errors that might occur. 1337 SFINAETrap Trap(*this); 1338 1339 // Enter a new template instantiation context while we instantiate the 1340 // actual function declaration. 1341 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1342 FunctionTemplate, Deduced.data(), Deduced.size(), 1343 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution); 1344 if (Inst) 1345 return TDK_InstantiationDepth; 1346 1347 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 1348 1349 // C++ [temp.deduct.type]p2: 1350 // [...] or if any template argument remains neither deduced nor 1351 // explicitly specified, template argument deduction fails. 1352 TemplateArgumentListBuilder Builder(TemplateParams, Deduced.size()); 1353 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 1354 NamedDecl *Param = FunctionTemplate->getTemplateParameters()->getParam(I); 1355 if (!Deduced[I].isNull()) { 1356 if (I < NumExplicitlySpecified || 1357 Deduced[I].getKind() == TemplateArgument::Type) { 1358 // We have already fully type-checked and converted this 1359 // argument (because it was explicitly-specified) or no 1360 // additional checking is necessary (because it's a template 1361 // type parameter). Just record the presence of this 1362 // parameter. 1363 Builder.Append(Deduced[I]); 1364 continue; 1365 } 1366 1367 // We have deduced this argument, so it still needs to be 1368 // checked and converted. 1369 1370 // First, for a non-type template parameter type that is 1371 // initialized by a declaration, we need the type of the 1372 // corresponding non-type template parameter. 1373 QualType NTTPType; 1374 if (NonTypeTemplateParmDecl *NTTP 1375 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 1376 if (Deduced[I].getKind() == TemplateArgument::Declaration) { 1377 NTTPType = NTTP->getType(); 1378 if (NTTPType->isDependentType()) { 1379 TemplateArgumentList TemplateArgs(Context, Builder, 1380 /*TakeArgs=*/false); 1381 NTTPType = SubstType(NTTPType, 1382 MultiLevelTemplateArgumentList(TemplateArgs), 1383 NTTP->getLocation(), 1384 NTTP->getDeclName()); 1385 if (NTTPType.isNull()) { 1386 Info.Param = makeTemplateParameter(Param); 1387 Info.reset(new (Context) TemplateArgumentList(Context, Builder, 1388 /*TakeArgs=*/true)); 1389 return TDK_SubstitutionFailure; 1390 } 1391 } 1392 } 1393 } 1394 1395 // Convert the deduced template argument into a template 1396 // argument that we can check, almost as if the user had written 1397 // the template argument explicitly. 1398 TemplateArgumentLoc Arg = getTrivialTemplateArgumentLoc(*this, 1399 Deduced[I], 1400 NTTPType, 1401 SourceLocation()); 1402 1403 // Check the template argument, converting it as necessary. 1404 if (CheckTemplateArgument(Param, Arg, 1405 FunctionTemplate, 1406 FunctionTemplate->getLocation(), 1407 FunctionTemplate->getSourceRange().getEnd(), 1408 Builder, 1409 Deduced[I].wasDeducedFromArrayBound() 1410 ? CTAK_DeducedFromArrayBound 1411 : CTAK_Deduced)) { 1412 Info.Param = makeTemplateParameter( 1413 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1414 Info.reset(new (Context) TemplateArgumentList(Context, Builder, 1415 /*TakeArgs=*/true)); 1416 return TDK_SubstitutionFailure; 1417 } 1418 1419 continue; 1420 } 1421 1422 // Substitute into the default template argument, if available. 1423 TemplateArgumentLoc DefArg 1424 = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate, 1425 FunctionTemplate->getLocation(), 1426 FunctionTemplate->getSourceRange().getEnd(), 1427 Param, 1428 Builder); 1429 1430 // If there was no default argument, deduction is incomplete. 1431 if (DefArg.getArgument().isNull()) { 1432 Info.Param = makeTemplateParameter( 1433 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1434 return TDK_Incomplete; 1435 } 1436 1437 // Check whether we can actually use the default argument. 1438 if (CheckTemplateArgument(Param, DefArg, 1439 FunctionTemplate, 1440 FunctionTemplate->getLocation(), 1441 FunctionTemplate->getSourceRange().getEnd(), 1442 Builder, 1443 CTAK_Deduced)) { 1444 Info.Param = makeTemplateParameter( 1445 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1446 Info.reset(new (Context) TemplateArgumentList(Context, Builder, 1447 /*TakeArgs=*/true)); 1448 return TDK_SubstitutionFailure; 1449 } 1450 1451 // If we get here, we successfully used the default template argument. 1452 } 1453 1454 // Form the template argument list from the deduced template arguments. 1455 TemplateArgumentList *DeducedArgumentList 1456 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true); 1457 Info.reset(DeducedArgumentList); 1458 1459 // Substitute the deduced template arguments into the function template 1460 // declaration to produce the function template specialization. 1461 DeclContext *Owner = FunctionTemplate->getDeclContext(); 1462 if (FunctionTemplate->getFriendObjectKind()) 1463 Owner = FunctionTemplate->getLexicalDeclContext(); 1464 Specialization = cast_or_null<FunctionDecl>( 1465 SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner, 1466 MultiLevelTemplateArgumentList(*DeducedArgumentList))); 1467 if (!Specialization) 1468 return TDK_SubstitutionFailure; 1469 1470 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() == 1471 FunctionTemplate->getCanonicalDecl()); 1472 1473 // If the template argument list is owned by the function template 1474 // specialization, release it. 1475 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList && 1476 !Trap.hasErrorOccurred()) 1477 Info.take(); 1478 1479 // There may have been an error that did not prevent us from constructing a 1480 // declaration. Mark the declaration invalid and return with a substitution 1481 // failure. 1482 if (Trap.hasErrorOccurred()) { 1483 Specialization->setInvalidDecl(true); 1484 return TDK_SubstitutionFailure; 1485 } 1486 1487 return TDK_Success; 1488} 1489 1490static QualType GetTypeOfFunction(ASTContext &Context, 1491 bool isAddressOfOperand, 1492 FunctionDecl *Fn) { 1493 if (!isAddressOfOperand) return Fn->getType(); 1494 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn)) 1495 if (Method->isInstance()) 1496 return Context.getMemberPointerType(Fn->getType(), 1497 Context.getTypeDeclType(Method->getParent()).getTypePtr()); 1498 return Context.getPointerType(Fn->getType()); 1499} 1500 1501/// Apply the deduction rules for overload sets. 1502/// 1503/// \return the null type if this argument should be treated as an 1504/// undeduced context 1505static QualType 1506ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams, 1507 Expr *Arg, QualType ParamType) { 1508 llvm::PointerIntPair<OverloadExpr*,1> R = OverloadExpr::find(Arg); 1509 1510 bool isAddressOfOperand = bool(R.getInt()); 1511 OverloadExpr *Ovl = R.getPointer(); 1512 1513 // If there were explicit template arguments, we can only find 1514 // something via C++ [temp.arg.explicit]p3, i.e. if the arguments 1515 // unambiguously name a full specialization. 1516 if (Ovl->hasExplicitTemplateArgs()) { 1517 // But we can still look for an explicit specialization. 1518 if (FunctionDecl *ExplicitSpec 1519 = S.ResolveSingleFunctionTemplateSpecialization(Ovl)) 1520 return GetTypeOfFunction(S.Context, isAddressOfOperand, ExplicitSpec); 1521 return QualType(); 1522 } 1523 1524 // C++0x [temp.deduct.call]p6: 1525 // When P is a function type, pointer to function type, or pointer 1526 // to member function type: 1527 1528 if (!ParamType->isFunctionType() && 1529 !ParamType->isFunctionPointerType() && 1530 !ParamType->isMemberFunctionPointerType()) 1531 return QualType(); 1532 1533 QualType Match; 1534 for (UnresolvedSetIterator I = Ovl->decls_begin(), 1535 E = Ovl->decls_end(); I != E; ++I) { 1536 NamedDecl *D = (*I)->getUnderlyingDecl(); 1537 1538 // - If the argument is an overload set containing one or more 1539 // function templates, the parameter is treated as a 1540 // non-deduced context. 1541 if (isa<FunctionTemplateDecl>(D)) 1542 return QualType(); 1543 1544 FunctionDecl *Fn = cast<FunctionDecl>(D); 1545 QualType ArgType = GetTypeOfFunction(S.Context, isAddressOfOperand, Fn); 1546 1547 // - If the argument is an overload set (not containing function 1548 // templates), trial argument deduction is attempted using each 1549 // of the members of the set. If deduction succeeds for only one 1550 // of the overload set members, that member is used as the 1551 // argument value for the deduction. If deduction succeeds for 1552 // more than one member of the overload set the parameter is 1553 // treated as a non-deduced context. 1554 1555 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2: 1556 // Type deduction is done independently for each P/A pair, and 1557 // the deduced template argument values are then combined. 1558 // So we do not reject deductions which were made elsewhere. 1559 llvm::SmallVector<DeducedTemplateArgument, 8> 1560 Deduced(TemplateParams->size()); 1561 Sema::TemplateDeductionInfo Info(S.Context, Ovl->getNameLoc()); 1562 unsigned TDF = 0; 1563 1564 Sema::TemplateDeductionResult Result 1565 = DeduceTemplateArguments(S, TemplateParams, 1566 ParamType, ArgType, 1567 Info, Deduced, TDF); 1568 if (Result) continue; 1569 if (!Match.isNull()) return QualType(); 1570 Match = ArgType; 1571 } 1572 1573 return Match; 1574} 1575 1576/// \brief Perform template argument deduction from a function call 1577/// (C++ [temp.deduct.call]). 1578/// 1579/// \param FunctionTemplate the function template for which we are performing 1580/// template argument deduction. 1581/// 1582/// \param ExplicitTemplateArguments the explicit template arguments provided 1583/// for this call. 1584/// 1585/// \param Args the function call arguments 1586/// 1587/// \param NumArgs the number of arguments in Args 1588/// 1589/// \param Name the name of the function being called. This is only significant 1590/// when the function template is a conversion function template, in which 1591/// case this routine will also perform template argument deduction based on 1592/// the function to which 1593/// 1594/// \param Specialization if template argument deduction was successful, 1595/// this will be set to the function template specialization produced by 1596/// template argument deduction. 1597/// 1598/// \param Info the argument will be updated to provide additional information 1599/// about template argument deduction. 1600/// 1601/// \returns the result of template argument deduction. 1602Sema::TemplateDeductionResult 1603Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1604 const TemplateArgumentListInfo *ExplicitTemplateArgs, 1605 Expr **Args, unsigned NumArgs, 1606 FunctionDecl *&Specialization, 1607 TemplateDeductionInfo &Info) { 1608 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1609 1610 // C++ [temp.deduct.call]p1: 1611 // Template argument deduction is done by comparing each function template 1612 // parameter type (call it P) with the type of the corresponding argument 1613 // of the call (call it A) as described below. 1614 unsigned CheckArgs = NumArgs; 1615 if (NumArgs < Function->getMinRequiredArguments()) 1616 return TDK_TooFewArguments; 1617 else if (NumArgs > Function->getNumParams()) { 1618 const FunctionProtoType *Proto 1619 = Function->getType()->getAs<FunctionProtoType>(); 1620 if (!Proto->isVariadic()) 1621 return TDK_TooManyArguments; 1622 1623 CheckArgs = Function->getNumParams(); 1624 } 1625 1626 // The types of the parameters from which we will perform template argument 1627 // deduction. 1628 Sema::LocalInstantiationScope InstScope(*this); 1629 TemplateParameterList *TemplateParams 1630 = FunctionTemplate->getTemplateParameters(); 1631 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 1632 llvm::SmallVector<QualType, 4> ParamTypes; 1633 unsigned NumExplicitlySpecified = 0; 1634 if (ExplicitTemplateArgs) { 1635 TemplateDeductionResult Result = 1636 SubstituteExplicitTemplateArguments(FunctionTemplate, 1637 *ExplicitTemplateArgs, 1638 Deduced, 1639 ParamTypes, 1640 0, 1641 Info); 1642 if (Result) 1643 return Result; 1644 1645 NumExplicitlySpecified = Deduced.size(); 1646 } else { 1647 // Just fill in the parameter types from the function declaration. 1648 for (unsigned I = 0; I != CheckArgs; ++I) 1649 ParamTypes.push_back(Function->getParamDecl(I)->getType()); 1650 } 1651 1652 // Deduce template arguments from the function parameters. 1653 Deduced.resize(TemplateParams->size()); 1654 for (unsigned I = 0; I != CheckArgs; ++I) { 1655 QualType ParamType = ParamTypes[I]; 1656 QualType ArgType = Args[I]->getType(); 1657 1658 // Overload sets usually make this parameter an undeduced 1659 // context, but there are sometimes special circumstances. 1660 if (ArgType == Context.OverloadTy) { 1661 ArgType = ResolveOverloadForDeduction(*this, TemplateParams, 1662 Args[I], ParamType); 1663 if (ArgType.isNull()) 1664 continue; 1665 } 1666 1667 // C++ [temp.deduct.call]p2: 1668 // If P is not a reference type: 1669 QualType CanonParamType = Context.getCanonicalType(ParamType); 1670 bool ParamWasReference = isa<ReferenceType>(CanonParamType); 1671 if (!ParamWasReference) { 1672 // - If A is an array type, the pointer type produced by the 1673 // array-to-pointer standard conversion (4.2) is used in place of 1674 // A for type deduction; otherwise, 1675 if (ArgType->isArrayType()) 1676 ArgType = Context.getArrayDecayedType(ArgType); 1677 // - If A is a function type, the pointer type produced by the 1678 // function-to-pointer standard conversion (4.3) is used in place 1679 // of A for type deduction; otherwise, 1680 else if (ArgType->isFunctionType()) 1681 ArgType = Context.getPointerType(ArgType); 1682 else { 1683 // - If A is a cv-qualified type, the top level cv-qualifiers of A’s 1684 // type are ignored for type deduction. 1685 QualType CanonArgType = Context.getCanonicalType(ArgType); 1686 if (CanonArgType.getLocalCVRQualifiers()) 1687 ArgType = CanonArgType.getLocalUnqualifiedType(); 1688 } 1689 } 1690 1691 // C++0x [temp.deduct.call]p3: 1692 // If P is a cv-qualified type, the top level cv-qualifiers of P’s type 1693 // are ignored for type deduction. 1694 if (CanonParamType.getLocalCVRQualifiers()) 1695 ParamType = CanonParamType.getLocalUnqualifiedType(); 1696 if (const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>()) { 1697 // [...] If P is a reference type, the type referred to by P is used 1698 // for type deduction. 1699 ParamType = ParamRefType->getPointeeType(); 1700 1701 // [...] If P is of the form T&&, where T is a template parameter, and 1702 // the argument is an lvalue, the type A& is used in place of A for 1703 // type deduction. 1704 if (isa<RValueReferenceType>(ParamRefType) && 1705 ParamRefType->getAs<TemplateTypeParmType>() && 1706 Args[I]->isLvalue(Context) == Expr::LV_Valid) 1707 ArgType = Context.getLValueReferenceType(ArgType); 1708 } 1709 1710 // C++0x [temp.deduct.call]p4: 1711 // In general, the deduction process attempts to find template argument 1712 // values that will make the deduced A identical to A (after the type A 1713 // is transformed as described above). [...] 1714 unsigned TDF = TDF_SkipNonDependent; 1715 1716 // - If the original P is a reference type, the deduced A (i.e., the 1717 // type referred to by the reference) can be more cv-qualified than 1718 // the transformed A. 1719 if (ParamWasReference) 1720 TDF |= TDF_ParamWithReferenceType; 1721 // - The transformed A can be another pointer or pointer to member 1722 // type that can be converted to the deduced A via a qualification 1723 // conversion (4.4). 1724 if (ArgType->isPointerType() || ArgType->isMemberPointerType() || 1725 ArgType->isObjCObjectPointerType()) 1726 TDF |= TDF_IgnoreQualifiers; 1727 // - If P is a class and P has the form simple-template-id, then the 1728 // transformed A can be a derived class of the deduced A. Likewise, 1729 // if P is a pointer to a class of the form simple-template-id, the 1730 // transformed A can be a pointer to a derived class pointed to by 1731 // the deduced A. 1732 if (isSimpleTemplateIdType(ParamType) || 1733 (isa<PointerType>(ParamType) && 1734 isSimpleTemplateIdType( 1735 ParamType->getAs<PointerType>()->getPointeeType()))) 1736 TDF |= TDF_DerivedClass; 1737 1738 if (TemplateDeductionResult Result 1739 = ::DeduceTemplateArguments(*this, TemplateParams, 1740 ParamType, ArgType, Info, Deduced, 1741 TDF)) 1742 return Result; 1743 1744 // FIXME: we need to check that the deduced A is the same as A, 1745 // modulo the various allowed differences. 1746 } 1747 1748 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 1749 NumExplicitlySpecified, 1750 Specialization, Info); 1751} 1752 1753/// \brief Deduce template arguments when taking the address of a function 1754/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to 1755/// a template. 1756/// 1757/// \param FunctionTemplate the function template for which we are performing 1758/// template argument deduction. 1759/// 1760/// \param ExplicitTemplateArguments the explicitly-specified template 1761/// arguments. 1762/// 1763/// \param ArgFunctionType the function type that will be used as the 1764/// "argument" type (A) when performing template argument deduction from the 1765/// function template's function type. This type may be NULL, if there is no 1766/// argument type to compare against, in C++0x [temp.arg.explicit]p3. 1767/// 1768/// \param Specialization if template argument deduction was successful, 1769/// this will be set to the function template specialization produced by 1770/// template argument deduction. 1771/// 1772/// \param Info the argument will be updated to provide additional information 1773/// about template argument deduction. 1774/// 1775/// \returns the result of template argument deduction. 1776Sema::TemplateDeductionResult 1777Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1778 const TemplateArgumentListInfo *ExplicitTemplateArgs, 1779 QualType ArgFunctionType, 1780 FunctionDecl *&Specialization, 1781 TemplateDeductionInfo &Info) { 1782 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1783 TemplateParameterList *TemplateParams 1784 = FunctionTemplate->getTemplateParameters(); 1785 QualType FunctionType = Function->getType(); 1786 1787 // Substitute any explicit template arguments. 1788 Sema::LocalInstantiationScope InstScope(*this); 1789 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 1790 unsigned NumExplicitlySpecified = 0; 1791 llvm::SmallVector<QualType, 4> ParamTypes; 1792 if (ExplicitTemplateArgs) { 1793 if (TemplateDeductionResult Result 1794 = SubstituteExplicitTemplateArguments(FunctionTemplate, 1795 *ExplicitTemplateArgs, 1796 Deduced, ParamTypes, 1797 &FunctionType, Info)) 1798 return Result; 1799 1800 NumExplicitlySpecified = Deduced.size(); 1801 } 1802 1803 // Template argument deduction for function templates in a SFINAE context. 1804 // Trap any errors that might occur. 1805 SFINAETrap Trap(*this); 1806 1807 Deduced.resize(TemplateParams->size()); 1808 1809 if (!ArgFunctionType.isNull()) { 1810 // Deduce template arguments from the function type. 1811 if (TemplateDeductionResult Result 1812 = ::DeduceTemplateArguments(*this, TemplateParams, 1813 FunctionType, ArgFunctionType, Info, 1814 Deduced, 0)) 1815 return Result; 1816 } 1817 1818 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 1819 NumExplicitlySpecified, 1820 Specialization, Info); 1821} 1822 1823/// \brief Deduce template arguments for a templated conversion 1824/// function (C++ [temp.deduct.conv]) and, if successful, produce a 1825/// conversion function template specialization. 1826Sema::TemplateDeductionResult 1827Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1828 QualType ToType, 1829 CXXConversionDecl *&Specialization, 1830 TemplateDeductionInfo &Info) { 1831 CXXConversionDecl *Conv 1832 = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl()); 1833 QualType FromType = Conv->getConversionType(); 1834 1835 // Canonicalize the types for deduction. 1836 QualType P = Context.getCanonicalType(FromType); 1837 QualType A = Context.getCanonicalType(ToType); 1838 1839 // C++0x [temp.deduct.conv]p3: 1840 // If P is a reference type, the type referred to by P is used for 1841 // type deduction. 1842 if (const ReferenceType *PRef = P->getAs<ReferenceType>()) 1843 P = PRef->getPointeeType(); 1844 1845 // C++0x [temp.deduct.conv]p3: 1846 // If A is a reference type, the type referred to by A is used 1847 // for type deduction. 1848 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 1849 A = ARef->getPointeeType(); 1850 // C++ [temp.deduct.conv]p2: 1851 // 1852 // If A is not a reference type: 1853 else { 1854 assert(!A->isReferenceType() && "Reference types were handled above"); 1855 1856 // - If P is an array type, the pointer type produced by the 1857 // array-to-pointer standard conversion (4.2) is used in place 1858 // of P for type deduction; otherwise, 1859 if (P->isArrayType()) 1860 P = Context.getArrayDecayedType(P); 1861 // - If P is a function type, the pointer type produced by the 1862 // function-to-pointer standard conversion (4.3) is used in 1863 // place of P for type deduction; otherwise, 1864 else if (P->isFunctionType()) 1865 P = Context.getPointerType(P); 1866 // - If P is a cv-qualified type, the top level cv-qualifiers of 1867 // P’s type are ignored for type deduction. 1868 else 1869 P = P.getUnqualifiedType(); 1870 1871 // C++0x [temp.deduct.conv]p3: 1872 // If A is a cv-qualified type, the top level cv-qualifiers of A’s 1873 // type are ignored for type deduction. 1874 A = A.getUnqualifiedType(); 1875 } 1876 1877 // Template argument deduction for function templates in a SFINAE context. 1878 // Trap any errors that might occur. 1879 SFINAETrap Trap(*this); 1880 1881 // C++ [temp.deduct.conv]p1: 1882 // Template argument deduction is done by comparing the return 1883 // type of the template conversion function (call it P) with the 1884 // type that is required as the result of the conversion (call it 1885 // A) as described in 14.8.2.4. 1886 TemplateParameterList *TemplateParams 1887 = FunctionTemplate->getTemplateParameters(); 1888 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 1889 Deduced.resize(TemplateParams->size()); 1890 1891 // C++0x [temp.deduct.conv]p4: 1892 // In general, the deduction process attempts to find template 1893 // argument values that will make the deduced A identical to 1894 // A. However, there are two cases that allow a difference: 1895 unsigned TDF = 0; 1896 // - If the original A is a reference type, A can be more 1897 // cv-qualified than the deduced A (i.e., the type referred to 1898 // by the reference) 1899 if (ToType->isReferenceType()) 1900 TDF |= TDF_ParamWithReferenceType; 1901 // - The deduced A can be another pointer or pointer to member 1902 // type that can be converted to A via a qualification 1903 // conversion. 1904 // 1905 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 1906 // both P and A are pointers or member pointers. In this case, we 1907 // just ignore cv-qualifiers completely). 1908 if ((P->isPointerType() && A->isPointerType()) || 1909 (P->isMemberPointerType() && P->isMemberPointerType())) 1910 TDF |= TDF_IgnoreQualifiers; 1911 if (TemplateDeductionResult Result 1912 = ::DeduceTemplateArguments(*this, TemplateParams, 1913 P, A, Info, Deduced, TDF)) 1914 return Result; 1915 1916 // FIXME: we need to check that the deduced A is the same as A, 1917 // modulo the various allowed differences. 1918 1919 // Finish template argument deduction. 1920 Sema::LocalInstantiationScope InstScope(*this); 1921 FunctionDecl *Spec = 0; 1922 TemplateDeductionResult Result 1923 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec, 1924 Info); 1925 Specialization = cast_or_null<CXXConversionDecl>(Spec); 1926 return Result; 1927} 1928 1929/// \brief Deduce template arguments for a function template when there is 1930/// nothing to deduce against (C++0x [temp.arg.explicit]p3). 1931/// 1932/// \param FunctionTemplate the function template for which we are performing 1933/// template argument deduction. 1934/// 1935/// \param ExplicitTemplateArguments the explicitly-specified template 1936/// arguments. 1937/// 1938/// \param Specialization if template argument deduction was successful, 1939/// this will be set to the function template specialization produced by 1940/// template argument deduction. 1941/// 1942/// \param Info the argument will be updated to provide additional information 1943/// about template argument deduction. 1944/// 1945/// \returns the result of template argument deduction. 1946Sema::TemplateDeductionResult 1947Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1948 const TemplateArgumentListInfo *ExplicitTemplateArgs, 1949 FunctionDecl *&Specialization, 1950 TemplateDeductionInfo &Info) { 1951 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs, 1952 QualType(), Specialization, Info); 1953} 1954 1955/// \brief Stores the result of comparing the qualifiers of two types. 1956enum DeductionQualifierComparison { 1957 NeitherMoreQualified = 0, 1958 ParamMoreQualified, 1959 ArgMoreQualified 1960}; 1961 1962/// \brief Deduce the template arguments during partial ordering by comparing 1963/// the parameter type and the argument type (C++0x [temp.deduct.partial]). 1964/// 1965/// \param S the semantic analysis object within which we are deducing 1966/// 1967/// \param TemplateParams the template parameters that we are deducing 1968/// 1969/// \param ParamIn the parameter type 1970/// 1971/// \param ArgIn the argument type 1972/// 1973/// \param Info information about the template argument deduction itself 1974/// 1975/// \param Deduced the deduced template arguments 1976/// 1977/// \returns the result of template argument deduction so far. Note that a 1978/// "success" result means that template argument deduction has not yet failed, 1979/// but it may still fail, later, for other reasons. 1980static Sema::TemplateDeductionResult 1981DeduceTemplateArgumentsDuringPartialOrdering(Sema &S, 1982 TemplateParameterList *TemplateParams, 1983 QualType ParamIn, QualType ArgIn, 1984 Sema::TemplateDeductionInfo &Info, 1985 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1986 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 1987 CanQualType Param = S.Context.getCanonicalType(ParamIn); 1988 CanQualType Arg = S.Context.getCanonicalType(ArgIn); 1989 1990 // C++0x [temp.deduct.partial]p5: 1991 // Before the partial ordering is done, certain transformations are 1992 // performed on the types used for partial ordering: 1993 // - If P is a reference type, P is replaced by the type referred to. 1994 CanQual<ReferenceType> ParamRef = Param->getAs<ReferenceType>(); 1995 if (!ParamRef.isNull()) 1996 Param = ParamRef->getPointeeType(); 1997 1998 // - If A is a reference type, A is replaced by the type referred to. 1999 CanQual<ReferenceType> ArgRef = Arg->getAs<ReferenceType>(); 2000 if (!ArgRef.isNull()) 2001 Arg = ArgRef->getPointeeType(); 2002 2003 if (QualifierComparisons && !ParamRef.isNull() && !ArgRef.isNull()) { 2004 // C++0x [temp.deduct.partial]p6: 2005 // If both P and A were reference types (before being replaced with the 2006 // type referred to above), determine which of the two types (if any) is 2007 // more cv-qualified than the other; otherwise the types are considered to 2008 // be equally cv-qualified for partial ordering purposes. The result of this 2009 // determination will be used below. 2010 // 2011 // We save this information for later, using it only when deduction 2012 // succeeds in both directions. 2013 DeductionQualifierComparison QualifierResult = NeitherMoreQualified; 2014 if (Param.isMoreQualifiedThan(Arg)) 2015 QualifierResult = ParamMoreQualified; 2016 else if (Arg.isMoreQualifiedThan(Param)) 2017 QualifierResult = ArgMoreQualified; 2018 QualifierComparisons->push_back(QualifierResult); 2019 } 2020 2021 // C++0x [temp.deduct.partial]p7: 2022 // Remove any top-level cv-qualifiers: 2023 // - If P is a cv-qualified type, P is replaced by the cv-unqualified 2024 // version of P. 2025 Param = Param.getUnqualifiedType(); 2026 // - If A is a cv-qualified type, A is replaced by the cv-unqualified 2027 // version of A. 2028 Arg = Arg.getUnqualifiedType(); 2029 2030 // C++0x [temp.deduct.partial]p8: 2031 // Using the resulting types P and A the deduction is then done as 2032 // described in 14.9.2.5. If deduction succeeds for a given type, the type 2033 // from the argument template is considered to be at least as specialized 2034 // as the type from the parameter template. 2035 return DeduceTemplateArguments(S, TemplateParams, Param, Arg, Info, 2036 Deduced, TDF_None); 2037} 2038 2039static void 2040MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 2041 bool OnlyDeduced, 2042 unsigned Level, 2043 llvm::SmallVectorImpl<bool> &Deduced); 2044 2045/// \brief Determine whether the function template \p FT1 is at least as 2046/// specialized as \p FT2. 2047static bool isAtLeastAsSpecializedAs(Sema &S, 2048 SourceLocation Loc, 2049 FunctionTemplateDecl *FT1, 2050 FunctionTemplateDecl *FT2, 2051 TemplatePartialOrderingContext TPOC, 2052 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 2053 FunctionDecl *FD1 = FT1->getTemplatedDecl(); 2054 FunctionDecl *FD2 = FT2->getTemplatedDecl(); 2055 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 2056 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 2057 2058 assert(Proto1 && Proto2 && "Function templates must have prototypes"); 2059 TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 2060 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2061 Deduced.resize(TemplateParams->size()); 2062 2063 // C++0x [temp.deduct.partial]p3: 2064 // The types used to determine the ordering depend on the context in which 2065 // the partial ordering is done: 2066 Sema::TemplateDeductionInfo Info(S.Context, Loc); 2067 switch (TPOC) { 2068 case TPOC_Call: { 2069 // - In the context of a function call, the function parameter types are 2070 // used. 2071 unsigned NumParams = std::min(Proto1->getNumArgs(), Proto2->getNumArgs()); 2072 for (unsigned I = 0; I != NumParams; ++I) 2073 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 2074 TemplateParams, 2075 Proto2->getArgType(I), 2076 Proto1->getArgType(I), 2077 Info, 2078 Deduced, 2079 QualifierComparisons)) 2080 return false; 2081 2082 break; 2083 } 2084 2085 case TPOC_Conversion: 2086 // - In the context of a call to a conversion operator, the return types 2087 // of the conversion function templates are used. 2088 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 2089 TemplateParams, 2090 Proto2->getResultType(), 2091 Proto1->getResultType(), 2092 Info, 2093 Deduced, 2094 QualifierComparisons)) 2095 return false; 2096 break; 2097 2098 case TPOC_Other: 2099 // - In other contexts (14.6.6.2) the function template’s function type 2100 // is used. 2101 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 2102 TemplateParams, 2103 FD2->getType(), 2104 FD1->getType(), 2105 Info, 2106 Deduced, 2107 QualifierComparisons)) 2108 return false; 2109 break; 2110 } 2111 2112 // C++0x [temp.deduct.partial]p11: 2113 // In most cases, all template parameters must have values in order for 2114 // deduction to succeed, but for partial ordering purposes a template 2115 // parameter may remain without a value provided it is not used in the 2116 // types being used for partial ordering. [ Note: a template parameter used 2117 // in a non-deduced context is considered used. -end note] 2118 unsigned ArgIdx = 0, NumArgs = Deduced.size(); 2119 for (; ArgIdx != NumArgs; ++ArgIdx) 2120 if (Deduced[ArgIdx].isNull()) 2121 break; 2122 2123 if (ArgIdx == NumArgs) { 2124 // All template arguments were deduced. FT1 is at least as specialized 2125 // as FT2. 2126 return true; 2127 } 2128 2129 // Figure out which template parameters were used. 2130 llvm::SmallVector<bool, 4> UsedParameters; 2131 UsedParameters.resize(TemplateParams->size()); 2132 switch (TPOC) { 2133 case TPOC_Call: { 2134 unsigned NumParams = std::min(Proto1->getNumArgs(), Proto2->getNumArgs()); 2135 for (unsigned I = 0; I != NumParams; ++I) 2136 ::MarkUsedTemplateParameters(S, Proto2->getArgType(I), false, 2137 TemplateParams->getDepth(), 2138 UsedParameters); 2139 break; 2140 } 2141 2142 case TPOC_Conversion: 2143 ::MarkUsedTemplateParameters(S, Proto2->getResultType(), false, 2144 TemplateParams->getDepth(), 2145 UsedParameters); 2146 break; 2147 2148 case TPOC_Other: 2149 ::MarkUsedTemplateParameters(S, FD2->getType(), false, 2150 TemplateParams->getDepth(), 2151 UsedParameters); 2152 break; 2153 } 2154 2155 for (; ArgIdx != NumArgs; ++ArgIdx) 2156 // If this argument had no value deduced but was used in one of the types 2157 // used for partial ordering, then deduction fails. 2158 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 2159 return false; 2160 2161 return true; 2162} 2163 2164 2165/// \brief Returns the more specialized function template according 2166/// to the rules of function template partial ordering (C++ [temp.func.order]). 2167/// 2168/// \param FT1 the first function template 2169/// 2170/// \param FT2 the second function template 2171/// 2172/// \param TPOC the context in which we are performing partial ordering of 2173/// function templates. 2174/// 2175/// \returns the more specialized function template. If neither 2176/// template is more specialized, returns NULL. 2177FunctionTemplateDecl * 2178Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, 2179 FunctionTemplateDecl *FT2, 2180 SourceLocation Loc, 2181 TemplatePartialOrderingContext TPOC) { 2182 llvm::SmallVector<DeductionQualifierComparison, 4> QualifierComparisons; 2183 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC, 0); 2184 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC, 2185 &QualifierComparisons); 2186 2187 if (Better1 != Better2) // We have a clear winner 2188 return Better1? FT1 : FT2; 2189 2190 if (!Better1 && !Better2) // Neither is better than the other 2191 return 0; 2192 2193 2194 // C++0x [temp.deduct.partial]p10: 2195 // If for each type being considered a given template is at least as 2196 // specialized for all types and more specialized for some set of types and 2197 // the other template is not more specialized for any types or is not at 2198 // least as specialized for any types, then the given template is more 2199 // specialized than the other template. Otherwise, neither template is more 2200 // specialized than the other. 2201 Better1 = false; 2202 Better2 = false; 2203 for (unsigned I = 0, N = QualifierComparisons.size(); I != N; ++I) { 2204 // C++0x [temp.deduct.partial]p9: 2205 // If, for a given type, deduction succeeds in both directions (i.e., the 2206 // types are identical after the transformations above) and if the type 2207 // from the argument template is more cv-qualified than the type from the 2208 // parameter template (as described above) that type is considered to be 2209 // more specialized than the other. If neither type is more cv-qualified 2210 // than the other then neither type is more specialized than the other. 2211 switch (QualifierComparisons[I]) { 2212 case NeitherMoreQualified: 2213 break; 2214 2215 case ParamMoreQualified: 2216 Better1 = true; 2217 if (Better2) 2218 return 0; 2219 break; 2220 2221 case ArgMoreQualified: 2222 Better2 = true; 2223 if (Better1) 2224 return 0; 2225 break; 2226 } 2227 } 2228 2229 assert(!(Better1 && Better2) && "Should have broken out in the loop above"); 2230 if (Better1) 2231 return FT1; 2232 else if (Better2) 2233 return FT2; 2234 else 2235 return 0; 2236} 2237 2238/// \brief Determine if the two templates are equivalent. 2239static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) { 2240 if (T1 == T2) 2241 return true; 2242 2243 if (!T1 || !T2) 2244 return false; 2245 2246 return T1->getCanonicalDecl() == T2->getCanonicalDecl(); 2247} 2248 2249/// \brief Retrieve the most specialized of the given function template 2250/// specializations. 2251/// 2252/// \param SpecBegin the start iterator of the function template 2253/// specializations that we will be comparing. 2254/// 2255/// \param SpecEnd the end iterator of the function template 2256/// specializations, paired with \p SpecBegin. 2257/// 2258/// \param TPOC the partial ordering context to use to compare the function 2259/// template specializations. 2260/// 2261/// \param Loc the location where the ambiguity or no-specializations 2262/// diagnostic should occur. 2263/// 2264/// \param NoneDiag partial diagnostic used to diagnose cases where there are 2265/// no matching candidates. 2266/// 2267/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one 2268/// occurs. 2269/// 2270/// \param CandidateDiag partial diagnostic used for each function template 2271/// specialization that is a candidate in the ambiguous ordering. One parameter 2272/// in this diagnostic should be unbound, which will correspond to the string 2273/// describing the template arguments for the function template specialization. 2274/// 2275/// \param Index if non-NULL and the result of this function is non-nULL, 2276/// receives the index corresponding to the resulting function template 2277/// specialization. 2278/// 2279/// \returns the most specialized function template specialization, if 2280/// found. Otherwise, returns SpecEnd. 2281/// 2282/// \todo FIXME: Consider passing in the "also-ran" candidates that failed 2283/// template argument deduction. 2284UnresolvedSetIterator 2285Sema::getMostSpecialized(UnresolvedSetIterator SpecBegin, 2286 UnresolvedSetIterator SpecEnd, 2287 TemplatePartialOrderingContext TPOC, 2288 SourceLocation Loc, 2289 const PartialDiagnostic &NoneDiag, 2290 const PartialDiagnostic &AmbigDiag, 2291 const PartialDiagnostic &CandidateDiag) { 2292 if (SpecBegin == SpecEnd) { 2293 Diag(Loc, NoneDiag); 2294 return SpecEnd; 2295 } 2296 2297 if (SpecBegin + 1 == SpecEnd) 2298 return SpecBegin; 2299 2300 // Find the function template that is better than all of the templates it 2301 // has been compared to. 2302 UnresolvedSetIterator Best = SpecBegin; 2303 FunctionTemplateDecl *BestTemplate 2304 = cast<FunctionDecl>(*Best)->getPrimaryTemplate(); 2305 assert(BestTemplate && "Not a function template specialization?"); 2306 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) { 2307 FunctionTemplateDecl *Challenger 2308 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 2309 assert(Challenger && "Not a function template specialization?"); 2310 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 2311 Loc, TPOC), 2312 Challenger)) { 2313 Best = I; 2314 BestTemplate = Challenger; 2315 } 2316 } 2317 2318 // Make sure that the "best" function template is more specialized than all 2319 // of the others. 2320 bool Ambiguous = false; 2321 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 2322 FunctionTemplateDecl *Challenger 2323 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 2324 if (I != Best && 2325 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 2326 Loc, TPOC), 2327 BestTemplate)) { 2328 Ambiguous = true; 2329 break; 2330 } 2331 } 2332 2333 if (!Ambiguous) { 2334 // We found an answer. Return it. 2335 return Best; 2336 } 2337 2338 // Diagnose the ambiguity. 2339 Diag(Loc, AmbigDiag); 2340 2341 // FIXME: Can we order the candidates in some sane way? 2342 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) 2343 Diag((*I)->getLocation(), CandidateDiag) 2344 << getTemplateArgumentBindingsText( 2345 cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(), 2346 *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs()); 2347 2348 return SpecEnd; 2349} 2350 2351/// \brief Returns the more specialized class template partial specialization 2352/// according to the rules of partial ordering of class template partial 2353/// specializations (C++ [temp.class.order]). 2354/// 2355/// \param PS1 the first class template partial specialization 2356/// 2357/// \param PS2 the second class template partial specialization 2358/// 2359/// \returns the more specialized class template partial specialization. If 2360/// neither partial specialization is more specialized, returns NULL. 2361ClassTemplatePartialSpecializationDecl * 2362Sema::getMoreSpecializedPartialSpecialization( 2363 ClassTemplatePartialSpecializationDecl *PS1, 2364 ClassTemplatePartialSpecializationDecl *PS2, 2365 SourceLocation Loc) { 2366 // C++ [temp.class.order]p1: 2367 // For two class template partial specializations, the first is at least as 2368 // specialized as the second if, given the following rewrite to two 2369 // function templates, the first function template is at least as 2370 // specialized as the second according to the ordering rules for function 2371 // templates (14.6.6.2): 2372 // - the first function template has the same template parameters as the 2373 // first partial specialization and has a single function parameter 2374 // whose type is a class template specialization with the template 2375 // arguments of the first partial specialization, and 2376 // - the second function template has the same template parameters as the 2377 // second partial specialization and has a single function parameter 2378 // whose type is a class template specialization with the template 2379 // arguments of the second partial specialization. 2380 // 2381 // Rather than synthesize function templates, we merely perform the 2382 // equivalent partial ordering by performing deduction directly on 2383 // the template arguments of the class template partial 2384 // specializations. This computation is slightly simpler than the 2385 // general problem of function template partial ordering, because 2386 // class template partial specializations are more constrained. We 2387 // know that every template parameter is deducible from the class 2388 // template partial specialization's template arguments, for 2389 // example. 2390 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2391 Sema::TemplateDeductionInfo Info(Context, Loc); 2392 2393 QualType PT1 = PS1->getInjectedSpecializationType(); 2394 QualType PT2 = PS2->getInjectedSpecializationType(); 2395 2396 // Determine whether PS1 is at least as specialized as PS2 2397 Deduced.resize(PS2->getTemplateParameters()->size()); 2398 bool Better1 = !DeduceTemplateArgumentsDuringPartialOrdering(*this, 2399 PS2->getTemplateParameters(), 2400 PT2, 2401 PT1, 2402 Info, 2403 Deduced, 2404 0); 2405 if (Better1) 2406 Better1 = !::FinishTemplateArgumentDeduction(*this, PS2, 2407 PS1->getTemplateArgs(), 2408 Deduced, Info); 2409 2410 // Determine whether PS2 is at least as specialized as PS1 2411 Deduced.clear(); 2412 Deduced.resize(PS1->getTemplateParameters()->size()); 2413 bool Better2 = !DeduceTemplateArgumentsDuringPartialOrdering(*this, 2414 PS1->getTemplateParameters(), 2415 PT1, 2416 PT2, 2417 Info, 2418 Deduced, 2419 0); 2420 if (Better2) 2421 Better2 = !::FinishTemplateArgumentDeduction(*this, PS1, 2422 PS2->getTemplateArgs(), 2423 Deduced, Info); 2424 2425 if (Better1 == Better2) 2426 return 0; 2427 2428 return Better1? PS1 : PS2; 2429} 2430 2431static void 2432MarkUsedTemplateParameters(Sema &SemaRef, 2433 const TemplateArgument &TemplateArg, 2434 bool OnlyDeduced, 2435 unsigned Depth, 2436 llvm::SmallVectorImpl<bool> &Used); 2437 2438/// \brief Mark the template parameters that are used by the given 2439/// expression. 2440static void 2441MarkUsedTemplateParameters(Sema &SemaRef, 2442 const Expr *E, 2443 bool OnlyDeduced, 2444 unsigned Depth, 2445 llvm::SmallVectorImpl<bool> &Used) { 2446 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to 2447 // find other occurrences of template parameters. 2448 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E); 2449 if (!DRE) 2450 return; 2451 2452 const NonTypeTemplateParmDecl *NTTP 2453 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 2454 if (!NTTP) 2455 return; 2456 2457 if (NTTP->getDepth() == Depth) 2458 Used[NTTP->getIndex()] = true; 2459} 2460 2461/// \brief Mark the template parameters that are used by the given 2462/// nested name specifier. 2463static void 2464MarkUsedTemplateParameters(Sema &SemaRef, 2465 NestedNameSpecifier *NNS, 2466 bool OnlyDeduced, 2467 unsigned Depth, 2468 llvm::SmallVectorImpl<bool> &Used) { 2469 if (!NNS) 2470 return; 2471 2472 MarkUsedTemplateParameters(SemaRef, NNS->getPrefix(), OnlyDeduced, Depth, 2473 Used); 2474 MarkUsedTemplateParameters(SemaRef, QualType(NNS->getAsType(), 0), 2475 OnlyDeduced, Depth, Used); 2476} 2477 2478/// \brief Mark the template parameters that are used by the given 2479/// template name. 2480static void 2481MarkUsedTemplateParameters(Sema &SemaRef, 2482 TemplateName Name, 2483 bool OnlyDeduced, 2484 unsigned Depth, 2485 llvm::SmallVectorImpl<bool> &Used) { 2486 if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 2487 if (TemplateTemplateParmDecl *TTP 2488 = dyn_cast<TemplateTemplateParmDecl>(Template)) { 2489 if (TTP->getDepth() == Depth) 2490 Used[TTP->getIndex()] = true; 2491 } 2492 return; 2493 } 2494 2495 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) 2496 MarkUsedTemplateParameters(SemaRef, QTN->getQualifier(), OnlyDeduced, 2497 Depth, Used); 2498 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 2499 MarkUsedTemplateParameters(SemaRef, DTN->getQualifier(), OnlyDeduced, 2500 Depth, Used); 2501} 2502 2503/// \brief Mark the template parameters that are used by the given 2504/// type. 2505static void 2506MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 2507 bool OnlyDeduced, 2508 unsigned Depth, 2509 llvm::SmallVectorImpl<bool> &Used) { 2510 if (T.isNull()) 2511 return; 2512 2513 // Non-dependent types have nothing deducible 2514 if (!T->isDependentType()) 2515 return; 2516 2517 T = SemaRef.Context.getCanonicalType(T); 2518 switch (T->getTypeClass()) { 2519 case Type::Pointer: 2520 MarkUsedTemplateParameters(SemaRef, 2521 cast<PointerType>(T)->getPointeeType(), 2522 OnlyDeduced, 2523 Depth, 2524 Used); 2525 break; 2526 2527 case Type::BlockPointer: 2528 MarkUsedTemplateParameters(SemaRef, 2529 cast<BlockPointerType>(T)->getPointeeType(), 2530 OnlyDeduced, 2531 Depth, 2532 Used); 2533 break; 2534 2535 case Type::LValueReference: 2536 case Type::RValueReference: 2537 MarkUsedTemplateParameters(SemaRef, 2538 cast<ReferenceType>(T)->getPointeeType(), 2539 OnlyDeduced, 2540 Depth, 2541 Used); 2542 break; 2543 2544 case Type::MemberPointer: { 2545 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 2546 MarkUsedTemplateParameters(SemaRef, MemPtr->getPointeeType(), OnlyDeduced, 2547 Depth, Used); 2548 MarkUsedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0), 2549 OnlyDeduced, Depth, Used); 2550 break; 2551 } 2552 2553 case Type::DependentSizedArray: 2554 MarkUsedTemplateParameters(SemaRef, 2555 cast<DependentSizedArrayType>(T)->getSizeExpr(), 2556 OnlyDeduced, Depth, Used); 2557 // Fall through to check the element type 2558 2559 case Type::ConstantArray: 2560 case Type::IncompleteArray: 2561 MarkUsedTemplateParameters(SemaRef, 2562 cast<ArrayType>(T)->getElementType(), 2563 OnlyDeduced, Depth, Used); 2564 break; 2565 2566 case Type::Vector: 2567 case Type::ExtVector: 2568 MarkUsedTemplateParameters(SemaRef, 2569 cast<VectorType>(T)->getElementType(), 2570 OnlyDeduced, Depth, Used); 2571 break; 2572 2573 case Type::DependentSizedExtVector: { 2574 const DependentSizedExtVectorType *VecType 2575 = cast<DependentSizedExtVectorType>(T); 2576 MarkUsedTemplateParameters(SemaRef, VecType->getElementType(), OnlyDeduced, 2577 Depth, Used); 2578 MarkUsedTemplateParameters(SemaRef, VecType->getSizeExpr(), OnlyDeduced, 2579 Depth, Used); 2580 break; 2581 } 2582 2583 case Type::FunctionProto: { 2584 const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 2585 MarkUsedTemplateParameters(SemaRef, Proto->getResultType(), OnlyDeduced, 2586 Depth, Used); 2587 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I) 2588 MarkUsedTemplateParameters(SemaRef, Proto->getArgType(I), OnlyDeduced, 2589 Depth, Used); 2590 break; 2591 } 2592 2593 case Type::TemplateTypeParm: { 2594 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T); 2595 if (TTP->getDepth() == Depth) 2596 Used[TTP->getIndex()] = true; 2597 break; 2598 } 2599 2600 case Type::InjectedClassName: 2601 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType(); 2602 // fall through 2603 2604 case Type::TemplateSpecialization: { 2605 const TemplateSpecializationType *Spec 2606 = cast<TemplateSpecializationType>(T); 2607 MarkUsedTemplateParameters(SemaRef, Spec->getTemplateName(), OnlyDeduced, 2608 Depth, Used); 2609 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 2610 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 2611 Used); 2612 break; 2613 } 2614 2615 case Type::Complex: 2616 if (!OnlyDeduced) 2617 MarkUsedTemplateParameters(SemaRef, 2618 cast<ComplexType>(T)->getElementType(), 2619 OnlyDeduced, Depth, Used); 2620 break; 2621 2622 case Type::DependentName: 2623 if (!OnlyDeduced) 2624 MarkUsedTemplateParameters(SemaRef, 2625 cast<DependentNameType>(T)->getQualifier(), 2626 OnlyDeduced, Depth, Used); 2627 break; 2628 2629 case Type::DependentTemplateSpecialization: { 2630 const DependentTemplateSpecializationType *Spec 2631 = cast<DependentTemplateSpecializationType>(T); 2632 if (!OnlyDeduced) 2633 MarkUsedTemplateParameters(SemaRef, Spec->getQualifier(), 2634 OnlyDeduced, Depth, Used); 2635 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 2636 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 2637 Used); 2638 break; 2639 } 2640 2641 case Type::TypeOf: 2642 if (!OnlyDeduced) 2643 MarkUsedTemplateParameters(SemaRef, 2644 cast<TypeOfType>(T)->getUnderlyingType(), 2645 OnlyDeduced, Depth, Used); 2646 break; 2647 2648 case Type::TypeOfExpr: 2649 if (!OnlyDeduced) 2650 MarkUsedTemplateParameters(SemaRef, 2651 cast<TypeOfExprType>(T)->getUnderlyingExpr(), 2652 OnlyDeduced, Depth, Used); 2653 break; 2654 2655 case Type::Decltype: 2656 if (!OnlyDeduced) 2657 MarkUsedTemplateParameters(SemaRef, 2658 cast<DecltypeType>(T)->getUnderlyingExpr(), 2659 OnlyDeduced, Depth, Used); 2660 break; 2661 2662 // None of these types have any template parameters in them. 2663 case Type::Builtin: 2664 case Type::VariableArray: 2665 case Type::FunctionNoProto: 2666 case Type::Record: 2667 case Type::Enum: 2668 case Type::ObjCInterface: 2669 case Type::ObjCObject: 2670 case Type::ObjCObjectPointer: 2671 case Type::UnresolvedUsing: 2672#define TYPE(Class, Base) 2673#define ABSTRACT_TYPE(Class, Base) 2674#define DEPENDENT_TYPE(Class, Base) 2675#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 2676#include "clang/AST/TypeNodes.def" 2677 break; 2678 } 2679} 2680 2681/// \brief Mark the template parameters that are used by this 2682/// template argument. 2683static void 2684MarkUsedTemplateParameters(Sema &SemaRef, 2685 const TemplateArgument &TemplateArg, 2686 bool OnlyDeduced, 2687 unsigned Depth, 2688 llvm::SmallVectorImpl<bool> &Used) { 2689 switch (TemplateArg.getKind()) { 2690 case TemplateArgument::Null: 2691 case TemplateArgument::Integral: 2692 case TemplateArgument::Declaration: 2693 break; 2694 2695 case TemplateArgument::Type: 2696 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsType(), OnlyDeduced, 2697 Depth, Used); 2698 break; 2699 2700 case TemplateArgument::Template: 2701 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsTemplate(), 2702 OnlyDeduced, Depth, Used); 2703 break; 2704 2705 case TemplateArgument::Expression: 2706 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsExpr(), OnlyDeduced, 2707 Depth, Used); 2708 break; 2709 2710 case TemplateArgument::Pack: 2711 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(), 2712 PEnd = TemplateArg.pack_end(); 2713 P != PEnd; ++P) 2714 MarkUsedTemplateParameters(SemaRef, *P, OnlyDeduced, Depth, Used); 2715 break; 2716 } 2717} 2718 2719/// \brief Mark the template parameters can be deduced by the given 2720/// template argument list. 2721/// 2722/// \param TemplateArgs the template argument list from which template 2723/// parameters will be deduced. 2724/// 2725/// \param Deduced a bit vector whose elements will be set to \c true 2726/// to indicate when the corresponding template parameter will be 2727/// deduced. 2728void 2729Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 2730 bool OnlyDeduced, unsigned Depth, 2731 llvm::SmallVectorImpl<bool> &Used) { 2732 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 2733 ::MarkUsedTemplateParameters(*this, TemplateArgs[I], OnlyDeduced, 2734 Depth, Used); 2735} 2736 2737/// \brief Marks all of the template parameters that will be deduced by a 2738/// call to the given function template. 2739void 2740Sema::MarkDeducedTemplateParameters(FunctionTemplateDecl *FunctionTemplate, 2741 llvm::SmallVectorImpl<bool> &Deduced) { 2742 TemplateParameterList *TemplateParams 2743 = FunctionTemplate->getTemplateParameters(); 2744 Deduced.clear(); 2745 Deduced.resize(TemplateParams->size()); 2746 2747 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2748 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 2749 ::MarkUsedTemplateParameters(*this, Function->getParamDecl(I)->getType(), 2750 true, TemplateParams->getDepth(), Deduced); 2751} 2752