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