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