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