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