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