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