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