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