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