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