SemaTemplateDeduction.cpp revision 0d432abff06e87a821e4b337339857ff8ea713a4
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 if (S.RequireCompleteType(Info.getLocation(), Arg, 0)) 657 return Result; 658 659 // Use data recursion to crawl through the list of base classes. 660 // Visited contains the set of nodes we have already visited, while 661 // ToVisit is our stack of records that we still need to visit. 662 llvm::SmallPtrSet<const RecordType *, 8> Visited; 663 llvm::SmallVector<const RecordType *, 8> ToVisit; 664 ToVisit.push_back(RecordT); 665 bool Successful = false; 666 while (!ToVisit.empty()) { 667 // Retrieve the next class in the inheritance hierarchy. 668 const RecordType *NextT = ToVisit.back(); 669 ToVisit.pop_back(); 670 671 // If we have already seen this type, skip it. 672 if (!Visited.insert(NextT)) 673 continue; 674 675 // If this is a base class, try to perform template argument 676 // deduction from it. 677 if (NextT != RecordT) { 678 Sema::TemplateDeductionResult BaseResult 679 = DeduceTemplateArguments(S, TemplateParams, SpecParam, 680 QualType(NextT, 0), Info, Deduced); 681 682 // If template argument deduction for this base was successful, 683 // note that we had some success. 684 if (BaseResult == Sema::TDK_Success) 685 Successful = true; 686 } 687 688 // Visit base classes 689 CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl()); 690 for (CXXRecordDecl::base_class_iterator Base = Next->bases_begin(), 691 BaseEnd = Next->bases_end(); 692 Base != BaseEnd; ++Base) { 693 assert(Base->getType()->isRecordType() && 694 "Base class that isn't a record?"); 695 ToVisit.push_back(Base->getType()->getAs<RecordType>()); 696 } 697 } 698 699 if (Successful) 700 return Sema::TDK_Success; 701 } 702 703 } 704 705 return Result; 706 } 707 708 // T type::* 709 // T T::* 710 // T (type::*)() 711 // type (T::*)() 712 // type (type::*)(T) 713 // type (T::*)(T) 714 // T (type::*)(T) 715 // T (T::*)() 716 // T (T::*)(T) 717 case Type::MemberPointer: { 718 const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param); 719 const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg); 720 if (!MemPtrArg) 721 return Sema::TDK_NonDeducedMismatch; 722 723 if (Sema::TemplateDeductionResult Result 724 = DeduceTemplateArguments(S, TemplateParams, 725 MemPtrParam->getPointeeType(), 726 MemPtrArg->getPointeeType(), 727 Info, Deduced, 728 TDF & TDF_IgnoreQualifiers)) 729 return Result; 730 731 return DeduceTemplateArguments(S, TemplateParams, 732 QualType(MemPtrParam->getClass(), 0), 733 QualType(MemPtrArg->getClass(), 0), 734 Info, Deduced, 0); 735 } 736 737 // (clang extension) 738 // 739 // type(^)(T) 740 // T(^)() 741 // T(^)(T) 742 case Type::BlockPointer: { 743 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param); 744 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg); 745 746 if (!BlockPtrArg) 747 return Sema::TDK_NonDeducedMismatch; 748 749 return DeduceTemplateArguments(S, TemplateParams, 750 BlockPtrParam->getPointeeType(), 751 BlockPtrArg->getPointeeType(), Info, 752 Deduced, 0); 753 } 754 755 case Type::TypeOfExpr: 756 case Type::TypeOf: 757 case Type::Typename: 758 // No template argument deduction for these types 759 return Sema::TDK_Success; 760 761 default: 762 break; 763 } 764 765 // FIXME: Many more cases to go (to go). 766 return Sema::TDK_Success; 767} 768 769static Sema::TemplateDeductionResult 770DeduceTemplateArguments(Sema &S, 771 TemplateParameterList *TemplateParams, 772 const TemplateArgument &Param, 773 const TemplateArgument &Arg, 774 Sema::TemplateDeductionInfo &Info, 775 llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 776 switch (Param.getKind()) { 777 case TemplateArgument::Null: 778 assert(false && "Null template argument in parameter list"); 779 break; 780 781 case TemplateArgument::Type: 782 if (Arg.getKind() == TemplateArgument::Type) 783 return DeduceTemplateArguments(S, TemplateParams, Param.getAsType(), 784 Arg.getAsType(), Info, Deduced, 0); 785 Info.FirstArg = Param; 786 Info.SecondArg = Arg; 787 return Sema::TDK_NonDeducedMismatch; 788 789 case TemplateArgument::Template: 790 if (Arg.getKind() == TemplateArgument::Template) 791 return DeduceTemplateArguments(S, TemplateParams, 792 Param.getAsTemplate(), 793 Arg.getAsTemplate(), Info, Deduced); 794 Info.FirstArg = Param; 795 Info.SecondArg = Arg; 796 return Sema::TDK_NonDeducedMismatch; 797 798 case TemplateArgument::Declaration: 799 if (Arg.getKind() == TemplateArgument::Declaration && 800 Param.getAsDecl()->getCanonicalDecl() == 801 Arg.getAsDecl()->getCanonicalDecl()) 802 return Sema::TDK_Success; 803 804 Info.FirstArg = Param; 805 Info.SecondArg = Arg; 806 return Sema::TDK_NonDeducedMismatch; 807 808 case TemplateArgument::Integral: 809 if (Arg.getKind() == TemplateArgument::Integral) { 810 // FIXME: Zero extension + sign checking here? 811 if (*Param.getAsIntegral() == *Arg.getAsIntegral()) 812 return Sema::TDK_Success; 813 814 Info.FirstArg = Param; 815 Info.SecondArg = Arg; 816 return Sema::TDK_NonDeducedMismatch; 817 } 818 819 if (Arg.getKind() == TemplateArgument::Expression) { 820 Info.FirstArg = Param; 821 Info.SecondArg = Arg; 822 return Sema::TDK_NonDeducedMismatch; 823 } 824 825 assert(false && "Type/value mismatch"); 826 Info.FirstArg = Param; 827 Info.SecondArg = Arg; 828 return Sema::TDK_NonDeducedMismatch; 829 830 case TemplateArgument::Expression: { 831 if (NonTypeTemplateParmDecl *NTTP 832 = getDeducedParameterFromExpr(Param.getAsExpr())) { 833 if (Arg.getKind() == TemplateArgument::Integral) 834 // FIXME: Sign problems here 835 return DeduceNonTypeTemplateArgument(S, NTTP, 836 *Arg.getAsIntegral(), 837 Info, Deduced); 838 if (Arg.getKind() == TemplateArgument::Expression) 839 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(), 840 Info, Deduced); 841 if (Arg.getKind() == TemplateArgument::Declaration) 842 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(), 843 Info, Deduced); 844 845 assert(false && "Type/value mismatch"); 846 Info.FirstArg = Param; 847 Info.SecondArg = Arg; 848 return Sema::TDK_NonDeducedMismatch; 849 } 850 851 // Can't deduce anything, but that's okay. 852 return Sema::TDK_Success; 853 } 854 case TemplateArgument::Pack: 855 assert(0 && "FIXME: Implement!"); 856 break; 857 } 858 859 return Sema::TDK_Success; 860} 861 862static Sema::TemplateDeductionResult 863DeduceTemplateArguments(Sema &S, 864 TemplateParameterList *TemplateParams, 865 const TemplateArgumentList &ParamList, 866 const TemplateArgumentList &ArgList, 867 Sema::TemplateDeductionInfo &Info, 868 llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 869 assert(ParamList.size() == ArgList.size()); 870 for (unsigned I = 0, N = ParamList.size(); I != N; ++I) { 871 if (Sema::TemplateDeductionResult Result 872 = DeduceTemplateArguments(S, TemplateParams, 873 ParamList[I], ArgList[I], 874 Info, Deduced)) 875 return Result; 876 } 877 return Sema::TDK_Success; 878} 879 880/// \brief Determine whether two template arguments are the same. 881static bool isSameTemplateArg(ASTContext &Context, 882 const TemplateArgument &X, 883 const TemplateArgument &Y) { 884 if (X.getKind() != Y.getKind()) 885 return false; 886 887 switch (X.getKind()) { 888 case TemplateArgument::Null: 889 assert(false && "Comparing NULL template argument"); 890 break; 891 892 case TemplateArgument::Type: 893 return Context.getCanonicalType(X.getAsType()) == 894 Context.getCanonicalType(Y.getAsType()); 895 896 case TemplateArgument::Declaration: 897 return X.getAsDecl()->getCanonicalDecl() == 898 Y.getAsDecl()->getCanonicalDecl(); 899 900 case TemplateArgument::Template: 901 return Context.getCanonicalTemplateName(X.getAsTemplate()) 902 .getAsVoidPointer() == 903 Context.getCanonicalTemplateName(Y.getAsTemplate()) 904 .getAsVoidPointer(); 905 906 case TemplateArgument::Integral: 907 return *X.getAsIntegral() == *Y.getAsIntegral(); 908 909 case TemplateArgument::Expression: { 910 llvm::FoldingSetNodeID XID, YID; 911 X.getAsExpr()->Profile(XID, Context, true); 912 Y.getAsExpr()->Profile(YID, Context, true); 913 return XID == YID; 914 } 915 916 case TemplateArgument::Pack: 917 if (X.pack_size() != Y.pack_size()) 918 return false; 919 920 for (TemplateArgument::pack_iterator XP = X.pack_begin(), 921 XPEnd = X.pack_end(), 922 YP = Y.pack_begin(); 923 XP != XPEnd; ++XP, ++YP) 924 if (!isSameTemplateArg(Context, *XP, *YP)) 925 return false; 926 927 return true; 928 } 929 930 return false; 931} 932 933/// \brief Helper function to build a TemplateParameter when we don't 934/// know its type statically. 935static TemplateParameter makeTemplateParameter(Decl *D) { 936 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D)) 937 return TemplateParameter(TTP); 938 else if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) 939 return TemplateParameter(NTTP); 940 941 return TemplateParameter(cast<TemplateTemplateParmDecl>(D)); 942} 943 944/// \brief Perform template argument deduction to determine whether 945/// the given template arguments match the given class template 946/// partial specialization per C++ [temp.class.spec.match]. 947Sema::TemplateDeductionResult 948Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial, 949 const TemplateArgumentList &TemplateArgs, 950 TemplateDeductionInfo &Info) { 951 // C++ [temp.class.spec.match]p2: 952 // A partial specialization matches a given actual template 953 // argument list if the template arguments of the partial 954 // specialization can be deduced from the actual template argument 955 // list (14.8.2). 956 SFINAETrap Trap(*this); 957 llvm::SmallVector<TemplateArgument, 4> Deduced; 958 Deduced.resize(Partial->getTemplateParameters()->size()); 959 if (TemplateDeductionResult Result 960 = ::DeduceTemplateArguments(*this, 961 Partial->getTemplateParameters(), 962 Partial->getTemplateArgs(), 963 TemplateArgs, Info, Deduced)) 964 return Result; 965 966 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial, 967 Deduced.data(), Deduced.size()); 968 if (Inst) 969 return TDK_InstantiationDepth; 970 971 // C++ [temp.deduct.type]p2: 972 // [...] or if any template argument remains neither deduced nor 973 // explicitly specified, template argument deduction fails. 974 TemplateArgumentListBuilder Builder(Partial->getTemplateParameters(), 975 Deduced.size()); 976 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 977 if (Deduced[I].isNull()) { 978 Decl *Param 979 = const_cast<NamedDecl *>( 980 Partial->getTemplateParameters()->getParam(I)); 981 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param)) 982 Info.Param = TTP; 983 else if (NonTypeTemplateParmDecl *NTTP 984 = dyn_cast<NonTypeTemplateParmDecl>(Param)) 985 Info.Param = NTTP; 986 else 987 Info.Param = cast<TemplateTemplateParmDecl>(Param); 988 return TDK_Incomplete; 989 } 990 991 Builder.Append(Deduced[I]); 992 } 993 994 // Form the template argument list from the deduced template arguments. 995 TemplateArgumentList *DeducedArgumentList 996 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true); 997 Info.reset(DeducedArgumentList); 998 999 // Substitute the deduced template arguments into the template 1000 // arguments of the class template partial specialization, and 1001 // verify that the instantiated template arguments are both valid 1002 // and are equivalent to the template arguments originally provided 1003 // to the class template. 1004 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate(); 1005 const TemplateArgumentLoc *PartialTemplateArgs 1006 = Partial->getTemplateArgsAsWritten(); 1007 unsigned N = Partial->getNumTemplateArgsAsWritten(); 1008 1009 // Note that we don't provide the langle and rangle locations. 1010 TemplateArgumentListInfo InstArgs; 1011 1012 for (unsigned I = 0; I != N; ++I) { 1013 Decl *Param = const_cast<NamedDecl *>( 1014 ClassTemplate->getTemplateParameters()->getParam(I)); 1015 TemplateArgumentLoc InstArg; 1016 if (Subst(PartialTemplateArgs[I], InstArg, 1017 MultiLevelTemplateArgumentList(*DeducedArgumentList))) { 1018 Info.Param = makeTemplateParameter(Param); 1019 Info.FirstArg = PartialTemplateArgs[I].getArgument(); 1020 return TDK_SubstitutionFailure; 1021 } 1022 InstArgs.addArgument(InstArg); 1023 } 1024 1025 TemplateArgumentListBuilder ConvertedInstArgs( 1026 ClassTemplate->getTemplateParameters(), N); 1027 1028 if (CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(), 1029 InstArgs, false, ConvertedInstArgs)) { 1030 // FIXME: fail with more useful information? 1031 return TDK_SubstitutionFailure; 1032 } 1033 1034 for (unsigned I = 0, E = ConvertedInstArgs.flatSize(); I != E; ++I) { 1035 TemplateArgument InstArg = ConvertedInstArgs.getFlatArguments()[I]; 1036 1037 Decl *Param = const_cast<NamedDecl *>( 1038 ClassTemplate->getTemplateParameters()->getParam(I)); 1039 1040 if (InstArg.getKind() == TemplateArgument::Expression) { 1041 // When the argument is an expression, check the expression result 1042 // against the actual template parameter to get down to the canonical 1043 // template argument. 1044 Expr *InstExpr = InstArg.getAsExpr(); 1045 if (NonTypeTemplateParmDecl *NTTP 1046 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 1047 if (CheckTemplateArgument(NTTP, NTTP->getType(), InstExpr, InstArg)) { 1048 Info.Param = makeTemplateParameter(Param); 1049 Info.FirstArg = Partial->getTemplateArgs()[I]; 1050 return TDK_SubstitutionFailure; 1051 } 1052 } 1053 } 1054 1055 if (!isSameTemplateArg(Context, TemplateArgs[I], InstArg)) { 1056 Info.Param = makeTemplateParameter(Param); 1057 Info.FirstArg = TemplateArgs[I]; 1058 Info.SecondArg = InstArg; 1059 return TDK_NonDeducedMismatch; 1060 } 1061 } 1062 1063 if (Trap.hasErrorOccurred()) 1064 return TDK_SubstitutionFailure; 1065 1066 return TDK_Success; 1067} 1068 1069/// \brief Determine whether the given type T is a simple-template-id type. 1070static bool isSimpleTemplateIdType(QualType T) { 1071 if (const TemplateSpecializationType *Spec 1072 = T->getAs<TemplateSpecializationType>()) 1073 return Spec->getTemplateName().getAsTemplateDecl() != 0; 1074 1075 return false; 1076} 1077 1078/// \brief Substitute the explicitly-provided template arguments into the 1079/// given function template according to C++ [temp.arg.explicit]. 1080/// 1081/// \param FunctionTemplate the function template into which the explicit 1082/// template arguments will be substituted. 1083/// 1084/// \param ExplicitTemplateArguments the explicitly-specified template 1085/// arguments. 1086/// 1087/// \param Deduced the deduced template arguments, which will be populated 1088/// with the converted and checked explicit template arguments. 1089/// 1090/// \param ParamTypes will be populated with the instantiated function 1091/// parameters. 1092/// 1093/// \param FunctionType if non-NULL, the result type of the function template 1094/// will also be instantiated and the pointed-to value will be updated with 1095/// the instantiated function type. 1096/// 1097/// \param Info if substitution fails for any reason, this object will be 1098/// populated with more information about the failure. 1099/// 1100/// \returns TDK_Success if substitution was successful, or some failure 1101/// condition. 1102Sema::TemplateDeductionResult 1103Sema::SubstituteExplicitTemplateArguments( 1104 FunctionTemplateDecl *FunctionTemplate, 1105 const TemplateArgumentListInfo &ExplicitTemplateArgs, 1106 llvm::SmallVectorImpl<TemplateArgument> &Deduced, 1107 llvm::SmallVectorImpl<QualType> &ParamTypes, 1108 QualType *FunctionType, 1109 TemplateDeductionInfo &Info) { 1110 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1111 TemplateParameterList *TemplateParams 1112 = FunctionTemplate->getTemplateParameters(); 1113 1114 if (ExplicitTemplateArgs.size() == 0) { 1115 // No arguments to substitute; just copy over the parameter types and 1116 // fill in the function type. 1117 for (FunctionDecl::param_iterator P = Function->param_begin(), 1118 PEnd = Function->param_end(); 1119 P != PEnd; 1120 ++P) 1121 ParamTypes.push_back((*P)->getType()); 1122 1123 if (FunctionType) 1124 *FunctionType = Function->getType(); 1125 return TDK_Success; 1126 } 1127 1128 // Substitution of the explicit template arguments into a function template 1129 /// is a SFINAE context. Trap any errors that might occur. 1130 SFINAETrap Trap(*this); 1131 1132 // C++ [temp.arg.explicit]p3: 1133 // Template arguments that are present shall be specified in the 1134 // declaration order of their corresponding template-parameters. The 1135 // template argument list shall not specify more template-arguments than 1136 // there are corresponding template-parameters. 1137 TemplateArgumentListBuilder Builder(TemplateParams, 1138 ExplicitTemplateArgs.size()); 1139 1140 // Enter a new template instantiation context where we check the 1141 // explicitly-specified template arguments against this function template, 1142 // and then substitute them into the function parameter types. 1143 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1144 FunctionTemplate, Deduced.data(), Deduced.size(), 1145 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution); 1146 if (Inst) 1147 return TDK_InstantiationDepth; 1148 1149 if (CheckTemplateArgumentList(FunctionTemplate, 1150 SourceLocation(), 1151 ExplicitTemplateArgs, 1152 true, 1153 Builder) || Trap.hasErrorOccurred()) 1154 return TDK_InvalidExplicitArguments; 1155 1156 // Form the template argument list from the explicitly-specified 1157 // template arguments. 1158 TemplateArgumentList *ExplicitArgumentList 1159 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true); 1160 Info.reset(ExplicitArgumentList); 1161 1162 // Instantiate the types of each of the function parameters given the 1163 // explicitly-specified template arguments. 1164 for (FunctionDecl::param_iterator P = Function->param_begin(), 1165 PEnd = Function->param_end(); 1166 P != PEnd; 1167 ++P) { 1168 QualType ParamType 1169 = SubstType((*P)->getType(), 1170 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1171 (*P)->getLocation(), (*P)->getDeclName()); 1172 if (ParamType.isNull() || Trap.hasErrorOccurred()) 1173 return TDK_SubstitutionFailure; 1174 1175 ParamTypes.push_back(ParamType); 1176 } 1177 1178 // If the caller wants a full function type back, instantiate the return 1179 // type and form that function type. 1180 if (FunctionType) { 1181 // FIXME: exception-specifications? 1182 const FunctionProtoType *Proto 1183 = Function->getType()->getAs<FunctionProtoType>(); 1184 assert(Proto && "Function template does not have a prototype?"); 1185 1186 QualType ResultType 1187 = SubstType(Proto->getResultType(), 1188 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1189 Function->getTypeSpecStartLoc(), 1190 Function->getDeclName()); 1191 if (ResultType.isNull() || Trap.hasErrorOccurred()) 1192 return TDK_SubstitutionFailure; 1193 1194 *FunctionType = BuildFunctionType(ResultType, 1195 ParamTypes.data(), ParamTypes.size(), 1196 Proto->isVariadic(), 1197 Proto->getTypeQuals(), 1198 Function->getLocation(), 1199 Function->getDeclName()); 1200 if (FunctionType->isNull() || Trap.hasErrorOccurred()) 1201 return TDK_SubstitutionFailure; 1202 } 1203 1204 // C++ [temp.arg.explicit]p2: 1205 // Trailing template arguments that can be deduced (14.8.2) may be 1206 // omitted from the list of explicit template-arguments. If all of the 1207 // template arguments can be deduced, they may all be omitted; in this 1208 // case, the empty template argument list <> itself may also be omitted. 1209 // 1210 // Take all of the explicitly-specified arguments and put them into the 1211 // set of deduced template arguments. 1212 Deduced.reserve(TemplateParams->size()); 1213 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) 1214 Deduced.push_back(ExplicitArgumentList->get(I)); 1215 1216 return TDK_Success; 1217} 1218 1219/// \brief Finish template argument deduction for a function template, 1220/// checking the deduced template arguments for completeness and forming 1221/// the function template specialization. 1222Sema::TemplateDeductionResult 1223Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate, 1224 llvm::SmallVectorImpl<TemplateArgument> &Deduced, 1225 FunctionDecl *&Specialization, 1226 TemplateDeductionInfo &Info) { 1227 TemplateParameterList *TemplateParams 1228 = FunctionTemplate->getTemplateParameters(); 1229 1230 // Template argument deduction for function templates in a SFINAE context. 1231 // Trap any errors that might occur. 1232 SFINAETrap Trap(*this); 1233 1234 // Enter a new template instantiation context while we instantiate the 1235 // actual function declaration. 1236 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1237 FunctionTemplate, Deduced.data(), Deduced.size(), 1238 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution); 1239 if (Inst) 1240 return TDK_InstantiationDepth; 1241 1242 // C++ [temp.deduct.type]p2: 1243 // [...] or if any template argument remains neither deduced nor 1244 // explicitly specified, template argument deduction fails. 1245 TemplateArgumentListBuilder Builder(TemplateParams, Deduced.size()); 1246 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 1247 if (!Deduced[I].isNull()) { 1248 Builder.Append(Deduced[I]); 1249 continue; 1250 } 1251 1252 // Substitute into the default template argument, if available. 1253 NamedDecl *Param = FunctionTemplate->getTemplateParameters()->getParam(I); 1254 TemplateArgumentLoc DefArg 1255 = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate, 1256 FunctionTemplate->getLocation(), 1257 FunctionTemplate->getSourceRange().getEnd(), 1258 Param, 1259 Builder); 1260 1261 // If there was no default argument, deduction is incomplete. 1262 if (DefArg.getArgument().isNull()) { 1263 Info.Param = makeTemplateParameter( 1264 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1265 return TDK_Incomplete; 1266 } 1267 1268 // Check whether we can actually use the default argument. 1269 if (CheckTemplateArgument(Param, DefArg, 1270 FunctionTemplate, 1271 FunctionTemplate->getLocation(), 1272 FunctionTemplate->getSourceRange().getEnd(), 1273 Builder)) { 1274 Info.Param = makeTemplateParameter( 1275 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1276 return TDK_SubstitutionFailure; 1277 } 1278 1279 // If we get here, we successfully used the default template argument. 1280 } 1281 1282 // Form the template argument list from the deduced template arguments. 1283 TemplateArgumentList *DeducedArgumentList 1284 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true); 1285 Info.reset(DeducedArgumentList); 1286 1287 // Substitute the deduced template arguments into the function template 1288 // declaration to produce the function template specialization. 1289 Specialization = cast_or_null<FunctionDecl>( 1290 SubstDecl(FunctionTemplate->getTemplatedDecl(), 1291 FunctionTemplate->getDeclContext(), 1292 MultiLevelTemplateArgumentList(*DeducedArgumentList))); 1293 if (!Specialization) 1294 return TDK_SubstitutionFailure; 1295 1296 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() == 1297 FunctionTemplate->getCanonicalDecl()); 1298 1299 // If the template argument list is owned by the function template 1300 // specialization, release it. 1301 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList) 1302 Info.take(); 1303 1304 // There may have been an error that did not prevent us from constructing a 1305 // declaration. Mark the declaration invalid and return with a substitution 1306 // failure. 1307 if (Trap.hasErrorOccurred()) { 1308 Specialization->setInvalidDecl(true); 1309 return TDK_SubstitutionFailure; 1310 } 1311 1312 return TDK_Success; 1313} 1314 1315static QualType GetTypeOfFunction(ASTContext &Context, 1316 bool isAddressOfOperand, 1317 FunctionDecl *Fn) { 1318 if (!isAddressOfOperand) return Fn->getType(); 1319 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn)) 1320 if (Method->isInstance()) 1321 return Context.getMemberPointerType(Fn->getType(), 1322 Context.getTypeDeclType(Method->getParent()).getTypePtr()); 1323 return Context.getPointerType(Fn->getType()); 1324} 1325 1326/// Apply the deduction rules for overload sets. 1327/// 1328/// \return the null type if this argument should be treated as an 1329/// undeduced context 1330static QualType 1331ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams, 1332 Expr *Arg, QualType ParamType) { 1333 llvm::PointerIntPair<OverloadExpr*,1> R = OverloadExpr::find(Arg); 1334 1335 bool isAddressOfOperand = bool(R.getInt()); 1336 OverloadExpr *Ovl = R.getPointer(); 1337 1338 // If there were explicit template arguments, we can only find 1339 // something via C++ [temp.arg.explicit]p3, i.e. if the arguments 1340 // unambiguously name a full specialization. 1341 if (Ovl->hasExplicitTemplateArgs()) { 1342 // But we can still look for an explicit specialization. 1343 if (FunctionDecl *ExplicitSpec 1344 = S.ResolveSingleFunctionTemplateSpecialization(Ovl)) 1345 return GetTypeOfFunction(S.Context, isAddressOfOperand, ExplicitSpec); 1346 return QualType(); 1347 } 1348 1349 // C++0x [temp.deduct.call]p6: 1350 // When P is a function type, pointer to function type, or pointer 1351 // to member function type: 1352 1353 if (!ParamType->isFunctionType() && 1354 !ParamType->isFunctionPointerType() && 1355 !ParamType->isMemberFunctionPointerType()) 1356 return QualType(); 1357 1358 QualType Match; 1359 for (UnresolvedSetIterator I = Ovl->decls_begin(), 1360 E = Ovl->decls_end(); I != E; ++I) { 1361 NamedDecl *D = (*I)->getUnderlyingDecl(); 1362 1363 // - If the argument is an overload set containing one or more 1364 // function templates, the parameter is treated as a 1365 // non-deduced context. 1366 if (isa<FunctionTemplateDecl>(D)) 1367 return QualType(); 1368 1369 FunctionDecl *Fn = cast<FunctionDecl>(D); 1370 QualType ArgType = GetTypeOfFunction(S.Context, isAddressOfOperand, Fn); 1371 1372 // - If the argument is an overload set (not containing function 1373 // templates), trial argument deduction is attempted using each 1374 // of the members of the set. If deduction succeeds for only one 1375 // of the overload set members, that member is used as the 1376 // argument value for the deduction. If deduction succeeds for 1377 // more than one member of the overload set the parameter is 1378 // treated as a non-deduced context. 1379 1380 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2: 1381 // Type deduction is done independently for each P/A pair, and 1382 // the deduced template argument values are then combined. 1383 // So we do not reject deductions which were made elsewhere. 1384 llvm::SmallVector<TemplateArgument, 8> Deduced(TemplateParams->size()); 1385 Sema::TemplateDeductionInfo Info(S.Context, Ovl->getNameLoc()); 1386 unsigned TDF = 0; 1387 1388 Sema::TemplateDeductionResult Result 1389 = DeduceTemplateArguments(S, TemplateParams, 1390 ParamType, ArgType, 1391 Info, Deduced, TDF); 1392 if (Result) continue; 1393 if (!Match.isNull()) return QualType(); 1394 Match = ArgType; 1395 } 1396 1397 return Match; 1398} 1399 1400/// \brief Perform template argument deduction from a function call 1401/// (C++ [temp.deduct.call]). 1402/// 1403/// \param FunctionTemplate the function template for which we are performing 1404/// template argument deduction. 1405/// 1406/// \param ExplicitTemplateArguments the explicit template arguments provided 1407/// for this call. 1408/// 1409/// \param Args the function call arguments 1410/// 1411/// \param NumArgs the number of arguments in Args 1412/// 1413/// \param Name the name of the function being called. This is only significant 1414/// when the function template is a conversion function template, in which 1415/// case this routine will also perform template argument deduction based on 1416/// the function to which 1417/// 1418/// \param Specialization if template argument deduction was successful, 1419/// this will be set to the function template specialization produced by 1420/// template argument deduction. 1421/// 1422/// \param Info the argument will be updated to provide additional information 1423/// about template argument deduction. 1424/// 1425/// \returns the result of template argument deduction. 1426Sema::TemplateDeductionResult 1427Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1428 const TemplateArgumentListInfo *ExplicitTemplateArgs, 1429 Expr **Args, unsigned NumArgs, 1430 FunctionDecl *&Specialization, 1431 TemplateDeductionInfo &Info) { 1432 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1433 1434 // C++ [temp.deduct.call]p1: 1435 // Template argument deduction is done by comparing each function template 1436 // parameter type (call it P) with the type of the corresponding argument 1437 // of the call (call it A) as described below. 1438 unsigned CheckArgs = NumArgs; 1439 if (NumArgs < Function->getMinRequiredArguments()) 1440 return TDK_TooFewArguments; 1441 else if (NumArgs > Function->getNumParams()) { 1442 const FunctionProtoType *Proto 1443 = Function->getType()->getAs<FunctionProtoType>(); 1444 if (!Proto->isVariadic()) 1445 return TDK_TooManyArguments; 1446 1447 CheckArgs = Function->getNumParams(); 1448 } 1449 1450 // The types of the parameters from which we will perform template argument 1451 // deduction. 1452 TemplateParameterList *TemplateParams 1453 = FunctionTemplate->getTemplateParameters(); 1454 llvm::SmallVector<TemplateArgument, 4> Deduced; 1455 llvm::SmallVector<QualType, 4> ParamTypes; 1456 if (ExplicitTemplateArgs) { 1457 TemplateDeductionResult Result = 1458 SubstituteExplicitTemplateArguments(FunctionTemplate, 1459 *ExplicitTemplateArgs, 1460 Deduced, 1461 ParamTypes, 1462 0, 1463 Info); 1464 if (Result) 1465 return Result; 1466 } else { 1467 // Just fill in the parameter types from the function declaration. 1468 for (unsigned I = 0; I != CheckArgs; ++I) 1469 ParamTypes.push_back(Function->getParamDecl(I)->getType()); 1470 } 1471 1472 // Deduce template arguments from the function parameters. 1473 Deduced.resize(TemplateParams->size()); 1474 for (unsigned I = 0; I != CheckArgs; ++I) { 1475 QualType ParamType = ParamTypes[I]; 1476 QualType ArgType = Args[I]->getType(); 1477 1478 // Overload sets usually make this parameter an undeduced 1479 // context, but there are sometimes special circumstances. 1480 if (ArgType == Context.OverloadTy) { 1481 ArgType = ResolveOverloadForDeduction(*this, TemplateParams, 1482 Args[I], ParamType); 1483 if (ArgType.isNull()) 1484 continue; 1485 } 1486 1487 // C++ [temp.deduct.call]p2: 1488 // If P is not a reference type: 1489 QualType CanonParamType = Context.getCanonicalType(ParamType); 1490 bool ParamWasReference = isa<ReferenceType>(CanonParamType); 1491 if (!ParamWasReference) { 1492 // - If A is an array type, the pointer type produced by the 1493 // array-to-pointer standard conversion (4.2) is used in place of 1494 // A for type deduction; otherwise, 1495 if (ArgType->isArrayType()) 1496 ArgType = Context.getArrayDecayedType(ArgType); 1497 // - If A is a function type, the pointer type produced by the 1498 // function-to-pointer standard conversion (4.3) is used in place 1499 // of A for type deduction; otherwise, 1500 else if (ArgType->isFunctionType()) 1501 ArgType = Context.getPointerType(ArgType); 1502 else { 1503 // - If A is a cv-qualified type, the top level cv-qualifiers of A’s 1504 // type are ignored for type deduction. 1505 QualType CanonArgType = Context.getCanonicalType(ArgType); 1506 if (CanonArgType.getLocalCVRQualifiers()) 1507 ArgType = CanonArgType.getLocalUnqualifiedType(); 1508 } 1509 } 1510 1511 // C++0x [temp.deduct.call]p3: 1512 // If P is a cv-qualified type, the top level cv-qualifiers of P’s type 1513 // are ignored for type deduction. 1514 if (CanonParamType.getLocalCVRQualifiers()) 1515 ParamType = CanonParamType.getLocalUnqualifiedType(); 1516 if (const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>()) { 1517 // [...] If P is a reference type, the type referred to by P is used 1518 // for type deduction. 1519 ParamType = ParamRefType->getPointeeType(); 1520 1521 // [...] If P is of the form T&&, where T is a template parameter, and 1522 // the argument is an lvalue, the type A& is used in place of A for 1523 // type deduction. 1524 if (isa<RValueReferenceType>(ParamRefType) && 1525 ParamRefType->getAs<TemplateTypeParmType>() && 1526 Args[I]->isLvalue(Context) == Expr::LV_Valid) 1527 ArgType = Context.getLValueReferenceType(ArgType); 1528 } 1529 1530 // C++0x [temp.deduct.call]p4: 1531 // In general, the deduction process attempts to find template argument 1532 // values that will make the deduced A identical to A (after the type A 1533 // is transformed as described above). [...] 1534 unsigned TDF = TDF_SkipNonDependent; 1535 1536 // - If the original P is a reference type, the deduced A (i.e., the 1537 // type referred to by the reference) can be more cv-qualified than 1538 // the transformed A. 1539 if (ParamWasReference) 1540 TDF |= TDF_ParamWithReferenceType; 1541 // - The transformed A can be another pointer or pointer to member 1542 // type that can be converted to the deduced A via a qualification 1543 // conversion (4.4). 1544 if (ArgType->isPointerType() || ArgType->isMemberPointerType()) 1545 TDF |= TDF_IgnoreQualifiers; 1546 // - If P is a class and P has the form simple-template-id, then the 1547 // transformed A can be a derived class of the deduced A. Likewise, 1548 // if P is a pointer to a class of the form simple-template-id, the 1549 // transformed A can be a pointer to a derived class pointed to by 1550 // the deduced A. 1551 if (isSimpleTemplateIdType(ParamType) || 1552 (isa<PointerType>(ParamType) && 1553 isSimpleTemplateIdType( 1554 ParamType->getAs<PointerType>()->getPointeeType()))) 1555 TDF |= TDF_DerivedClass; 1556 1557 if (TemplateDeductionResult Result 1558 = ::DeduceTemplateArguments(*this, TemplateParams, 1559 ParamType, ArgType, Info, Deduced, 1560 TDF)) 1561 return Result; 1562 1563 // FIXME: we need to check that the deduced A is the same as A, 1564 // modulo the various allowed differences. 1565 } 1566 1567 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 1568 Specialization, Info); 1569} 1570 1571/// \brief Deduce template arguments when taking the address of a function 1572/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to 1573/// a template. 1574/// 1575/// \param FunctionTemplate the function template for which we are performing 1576/// template argument deduction. 1577/// 1578/// \param ExplicitTemplateArguments the explicitly-specified template 1579/// arguments. 1580/// 1581/// \param ArgFunctionType the function type that will be used as the 1582/// "argument" type (A) when performing template argument deduction from the 1583/// function template's function type. This type may be NULL, if there is no 1584/// argument type to compare against, in C++0x [temp.arg.explicit]p3. 1585/// 1586/// \param Specialization if template argument deduction was successful, 1587/// this will be set to the function template specialization produced by 1588/// template argument deduction. 1589/// 1590/// \param Info the argument will be updated to provide additional information 1591/// about template argument deduction. 1592/// 1593/// \returns the result of template argument deduction. 1594Sema::TemplateDeductionResult 1595Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1596 const TemplateArgumentListInfo *ExplicitTemplateArgs, 1597 QualType ArgFunctionType, 1598 FunctionDecl *&Specialization, 1599 TemplateDeductionInfo &Info) { 1600 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1601 TemplateParameterList *TemplateParams 1602 = FunctionTemplate->getTemplateParameters(); 1603 QualType FunctionType = Function->getType(); 1604 1605 // Substitute any explicit template arguments. 1606 llvm::SmallVector<TemplateArgument, 4> Deduced; 1607 llvm::SmallVector<QualType, 4> ParamTypes; 1608 if (ExplicitTemplateArgs) { 1609 if (TemplateDeductionResult Result 1610 = SubstituteExplicitTemplateArguments(FunctionTemplate, 1611 *ExplicitTemplateArgs, 1612 Deduced, ParamTypes, 1613 &FunctionType, Info)) 1614 return Result; 1615 } 1616 1617 // Template argument deduction for function templates in a SFINAE context. 1618 // Trap any errors that might occur. 1619 SFINAETrap Trap(*this); 1620 1621 Deduced.resize(TemplateParams->size()); 1622 1623 if (!ArgFunctionType.isNull()) { 1624 // Deduce template arguments from the function type. 1625 if (TemplateDeductionResult Result 1626 = ::DeduceTemplateArguments(*this, TemplateParams, 1627 FunctionType, ArgFunctionType, Info, 1628 Deduced, 0)) 1629 return Result; 1630 } 1631 1632 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 1633 Specialization, Info); 1634} 1635 1636/// \brief Deduce template arguments for a templated conversion 1637/// function (C++ [temp.deduct.conv]) and, if successful, produce a 1638/// conversion function template specialization. 1639Sema::TemplateDeductionResult 1640Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1641 QualType ToType, 1642 CXXConversionDecl *&Specialization, 1643 TemplateDeductionInfo &Info) { 1644 CXXConversionDecl *Conv 1645 = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl()); 1646 QualType FromType = Conv->getConversionType(); 1647 1648 // Canonicalize the types for deduction. 1649 QualType P = Context.getCanonicalType(FromType); 1650 QualType A = Context.getCanonicalType(ToType); 1651 1652 // C++0x [temp.deduct.conv]p3: 1653 // If P is a reference type, the type referred to by P is used for 1654 // type deduction. 1655 if (const ReferenceType *PRef = P->getAs<ReferenceType>()) 1656 P = PRef->getPointeeType(); 1657 1658 // C++0x [temp.deduct.conv]p3: 1659 // If A is a reference type, the type referred to by A is used 1660 // for type deduction. 1661 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 1662 A = ARef->getPointeeType(); 1663 // C++ [temp.deduct.conv]p2: 1664 // 1665 // If A is not a reference type: 1666 else { 1667 assert(!A->isReferenceType() && "Reference types were handled above"); 1668 1669 // - If P is an array type, the pointer type produced by the 1670 // array-to-pointer standard conversion (4.2) is used in place 1671 // of P for type deduction; otherwise, 1672 if (P->isArrayType()) 1673 P = Context.getArrayDecayedType(P); 1674 // - If P is a function type, the pointer type produced by the 1675 // function-to-pointer standard conversion (4.3) is used in 1676 // place of P for type deduction; otherwise, 1677 else if (P->isFunctionType()) 1678 P = Context.getPointerType(P); 1679 // - If P is a cv-qualified type, the top level cv-qualifiers of 1680 // P’s type are ignored for type deduction. 1681 else 1682 P = P.getUnqualifiedType(); 1683 1684 // C++0x [temp.deduct.conv]p3: 1685 // If A is a cv-qualified type, the top level cv-qualifiers of A’s 1686 // type are ignored for type deduction. 1687 A = A.getUnqualifiedType(); 1688 } 1689 1690 // Template argument deduction for function templates in a SFINAE context. 1691 // Trap any errors that might occur. 1692 SFINAETrap Trap(*this); 1693 1694 // C++ [temp.deduct.conv]p1: 1695 // Template argument deduction is done by comparing the return 1696 // type of the template conversion function (call it P) with the 1697 // type that is required as the result of the conversion (call it 1698 // A) as described in 14.8.2.4. 1699 TemplateParameterList *TemplateParams 1700 = FunctionTemplate->getTemplateParameters(); 1701 llvm::SmallVector<TemplateArgument, 4> Deduced; 1702 Deduced.resize(TemplateParams->size()); 1703 1704 // C++0x [temp.deduct.conv]p4: 1705 // In general, the deduction process attempts to find template 1706 // argument values that will make the deduced A identical to 1707 // A. However, there are two cases that allow a difference: 1708 unsigned TDF = 0; 1709 // - If the original A is a reference type, A can be more 1710 // cv-qualified than the deduced A (i.e., the type referred to 1711 // by the reference) 1712 if (ToType->isReferenceType()) 1713 TDF |= TDF_ParamWithReferenceType; 1714 // - The deduced A can be another pointer or pointer to member 1715 // type that can be converted to A via a qualification 1716 // conversion. 1717 // 1718 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 1719 // both P and A are pointers or member pointers. In this case, we 1720 // just ignore cv-qualifiers completely). 1721 if ((P->isPointerType() && A->isPointerType()) || 1722 (P->isMemberPointerType() && P->isMemberPointerType())) 1723 TDF |= TDF_IgnoreQualifiers; 1724 if (TemplateDeductionResult Result 1725 = ::DeduceTemplateArguments(*this, TemplateParams, 1726 P, A, Info, Deduced, TDF)) 1727 return Result; 1728 1729 // FIXME: we need to check that the deduced A is the same as A, 1730 // modulo the various allowed differences. 1731 1732 // Finish template argument deduction. 1733 FunctionDecl *Spec = 0; 1734 TemplateDeductionResult Result 1735 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, Spec, Info); 1736 Specialization = cast_or_null<CXXConversionDecl>(Spec); 1737 return Result; 1738} 1739 1740/// \brief Deduce template arguments for a function template when there is 1741/// nothing to deduce against (C++0x [temp.arg.explicit]p3). 1742/// 1743/// \param FunctionTemplate the function template for which we are performing 1744/// template argument deduction. 1745/// 1746/// \param ExplicitTemplateArguments the explicitly-specified template 1747/// arguments. 1748/// 1749/// \param Specialization if template argument deduction was successful, 1750/// this will be set to the function template specialization produced by 1751/// template argument deduction. 1752/// 1753/// \param Info the argument will be updated to provide additional information 1754/// about template argument deduction. 1755/// 1756/// \returns the result of template argument deduction. 1757Sema::TemplateDeductionResult 1758Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1759 const TemplateArgumentListInfo *ExplicitTemplateArgs, 1760 FunctionDecl *&Specialization, 1761 TemplateDeductionInfo &Info) { 1762 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs, 1763 QualType(), Specialization, Info); 1764} 1765 1766/// \brief Stores the result of comparing the qualifiers of two types. 1767enum DeductionQualifierComparison { 1768 NeitherMoreQualified = 0, 1769 ParamMoreQualified, 1770 ArgMoreQualified 1771}; 1772 1773/// \brief Deduce the template arguments during partial ordering by comparing 1774/// the parameter type and the argument type (C++0x [temp.deduct.partial]). 1775/// 1776/// \param S the semantic analysis object within which we are deducing 1777/// 1778/// \param TemplateParams the template parameters that we are deducing 1779/// 1780/// \param ParamIn the parameter type 1781/// 1782/// \param ArgIn the argument type 1783/// 1784/// \param Info information about the template argument deduction itself 1785/// 1786/// \param Deduced the deduced template arguments 1787/// 1788/// \returns the result of template argument deduction so far. Note that a 1789/// "success" result means that template argument deduction has not yet failed, 1790/// but it may still fail, later, for other reasons. 1791static Sema::TemplateDeductionResult 1792DeduceTemplateArgumentsDuringPartialOrdering(Sema &S, 1793 TemplateParameterList *TemplateParams, 1794 QualType ParamIn, QualType ArgIn, 1795 Sema::TemplateDeductionInfo &Info, 1796 llvm::SmallVectorImpl<TemplateArgument> &Deduced, 1797 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 1798 CanQualType Param = S.Context.getCanonicalType(ParamIn); 1799 CanQualType Arg = S.Context.getCanonicalType(ArgIn); 1800 1801 // C++0x [temp.deduct.partial]p5: 1802 // Before the partial ordering is done, certain transformations are 1803 // performed on the types used for partial ordering: 1804 // - If P is a reference type, P is replaced by the type referred to. 1805 CanQual<ReferenceType> ParamRef = Param->getAs<ReferenceType>(); 1806 if (!ParamRef.isNull()) 1807 Param = ParamRef->getPointeeType(); 1808 1809 // - If A is a reference type, A is replaced by the type referred to. 1810 CanQual<ReferenceType> ArgRef = Arg->getAs<ReferenceType>(); 1811 if (!ArgRef.isNull()) 1812 Arg = ArgRef->getPointeeType(); 1813 1814 if (QualifierComparisons && !ParamRef.isNull() && !ArgRef.isNull()) { 1815 // C++0x [temp.deduct.partial]p6: 1816 // If both P and A were reference types (before being replaced with the 1817 // type referred to above), determine which of the two types (if any) is 1818 // more cv-qualified than the other; otherwise the types are considered to 1819 // be equally cv-qualified for partial ordering purposes. The result of this 1820 // determination will be used below. 1821 // 1822 // We save this information for later, using it only when deduction 1823 // succeeds in both directions. 1824 DeductionQualifierComparison QualifierResult = NeitherMoreQualified; 1825 if (Param.isMoreQualifiedThan(Arg)) 1826 QualifierResult = ParamMoreQualified; 1827 else if (Arg.isMoreQualifiedThan(Param)) 1828 QualifierResult = ArgMoreQualified; 1829 QualifierComparisons->push_back(QualifierResult); 1830 } 1831 1832 // C++0x [temp.deduct.partial]p7: 1833 // Remove any top-level cv-qualifiers: 1834 // - If P is a cv-qualified type, P is replaced by the cv-unqualified 1835 // version of P. 1836 Param = Param.getUnqualifiedType(); 1837 // - If A is a cv-qualified type, A is replaced by the cv-unqualified 1838 // version of A. 1839 Arg = Arg.getUnqualifiedType(); 1840 1841 // C++0x [temp.deduct.partial]p8: 1842 // Using the resulting types P and A the deduction is then done as 1843 // described in 14.9.2.5. If deduction succeeds for a given type, the type 1844 // from the argument template is considered to be at least as specialized 1845 // as the type from the parameter template. 1846 return DeduceTemplateArguments(S, TemplateParams, Param, Arg, Info, 1847 Deduced, TDF_None); 1848} 1849 1850static void 1851MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 1852 bool OnlyDeduced, 1853 unsigned Level, 1854 llvm::SmallVectorImpl<bool> &Deduced); 1855 1856/// \brief Determine whether the function template \p FT1 is at least as 1857/// specialized as \p FT2. 1858static bool isAtLeastAsSpecializedAs(Sema &S, 1859 SourceLocation Loc, 1860 FunctionTemplateDecl *FT1, 1861 FunctionTemplateDecl *FT2, 1862 TemplatePartialOrderingContext TPOC, 1863 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 1864 FunctionDecl *FD1 = FT1->getTemplatedDecl(); 1865 FunctionDecl *FD2 = FT2->getTemplatedDecl(); 1866 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 1867 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 1868 1869 assert(Proto1 && Proto2 && "Function templates must have prototypes"); 1870 TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 1871 llvm::SmallVector<TemplateArgument, 4> Deduced; 1872 Deduced.resize(TemplateParams->size()); 1873 1874 // C++0x [temp.deduct.partial]p3: 1875 // The types used to determine the ordering depend on the context in which 1876 // the partial ordering is done: 1877 Sema::TemplateDeductionInfo Info(S.Context, Loc); 1878 switch (TPOC) { 1879 case TPOC_Call: { 1880 // - In the context of a function call, the function parameter types are 1881 // used. 1882 unsigned NumParams = std::min(Proto1->getNumArgs(), Proto2->getNumArgs()); 1883 for (unsigned I = 0; I != NumParams; ++I) 1884 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 1885 TemplateParams, 1886 Proto2->getArgType(I), 1887 Proto1->getArgType(I), 1888 Info, 1889 Deduced, 1890 QualifierComparisons)) 1891 return false; 1892 1893 break; 1894 } 1895 1896 case TPOC_Conversion: 1897 // - In the context of a call to a conversion operator, the return types 1898 // of the conversion function templates are used. 1899 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 1900 TemplateParams, 1901 Proto2->getResultType(), 1902 Proto1->getResultType(), 1903 Info, 1904 Deduced, 1905 QualifierComparisons)) 1906 return false; 1907 break; 1908 1909 case TPOC_Other: 1910 // - In other contexts (14.6.6.2) the function template’s function type 1911 // is used. 1912 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 1913 TemplateParams, 1914 FD2->getType(), 1915 FD1->getType(), 1916 Info, 1917 Deduced, 1918 QualifierComparisons)) 1919 return false; 1920 break; 1921 } 1922 1923 // C++0x [temp.deduct.partial]p11: 1924 // In most cases, all template parameters must have values in order for 1925 // deduction to succeed, but for partial ordering purposes a template 1926 // parameter may remain without a value provided it is not used in the 1927 // types being used for partial ordering. [ Note: a template parameter used 1928 // in a non-deduced context is considered used. -end note] 1929 unsigned ArgIdx = 0, NumArgs = Deduced.size(); 1930 for (; ArgIdx != NumArgs; ++ArgIdx) 1931 if (Deduced[ArgIdx].isNull()) 1932 break; 1933 1934 if (ArgIdx == NumArgs) { 1935 // All template arguments were deduced. FT1 is at least as specialized 1936 // as FT2. 1937 return true; 1938 } 1939 1940 // Figure out which template parameters were used. 1941 llvm::SmallVector<bool, 4> UsedParameters; 1942 UsedParameters.resize(TemplateParams->size()); 1943 switch (TPOC) { 1944 case TPOC_Call: { 1945 unsigned NumParams = std::min(Proto1->getNumArgs(), Proto2->getNumArgs()); 1946 for (unsigned I = 0; I != NumParams; ++I) 1947 ::MarkUsedTemplateParameters(S, Proto2->getArgType(I), false, 1948 TemplateParams->getDepth(), 1949 UsedParameters); 1950 break; 1951 } 1952 1953 case TPOC_Conversion: 1954 ::MarkUsedTemplateParameters(S, Proto2->getResultType(), false, 1955 TemplateParams->getDepth(), 1956 UsedParameters); 1957 break; 1958 1959 case TPOC_Other: 1960 ::MarkUsedTemplateParameters(S, FD2->getType(), false, 1961 TemplateParams->getDepth(), 1962 UsedParameters); 1963 break; 1964 } 1965 1966 for (; ArgIdx != NumArgs; ++ArgIdx) 1967 // If this argument had no value deduced but was used in one of the types 1968 // used for partial ordering, then deduction fails. 1969 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 1970 return false; 1971 1972 return true; 1973} 1974 1975 1976/// \brief Returns the more specialized function template according 1977/// to the rules of function template partial ordering (C++ [temp.func.order]). 1978/// 1979/// \param FT1 the first function template 1980/// 1981/// \param FT2 the second function template 1982/// 1983/// \param TPOC the context in which we are performing partial ordering of 1984/// function templates. 1985/// 1986/// \returns the more specialized function template. If neither 1987/// template is more specialized, returns NULL. 1988FunctionTemplateDecl * 1989Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, 1990 FunctionTemplateDecl *FT2, 1991 SourceLocation Loc, 1992 TemplatePartialOrderingContext TPOC) { 1993 llvm::SmallVector<DeductionQualifierComparison, 4> QualifierComparisons; 1994 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC, 0); 1995 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, 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 Loc, 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 Loc, 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 SourceLocation Loc) { 2177 // C++ [temp.class.order]p1: 2178 // For two class template partial specializations, the first is at least as 2179 // specialized as the second if, given the following rewrite to two 2180 // function templates, the first function template is at least as 2181 // specialized as the second according to the ordering rules for function 2182 // templates (14.6.6.2): 2183 // - the first function template has the same template parameters as the 2184 // first partial specialization and has a single function parameter 2185 // whose type is a class template specialization with the template 2186 // arguments of the first partial specialization, and 2187 // - the second function template has the same template parameters as the 2188 // second partial specialization and has a single function parameter 2189 // whose type is a class template specialization with the template 2190 // arguments of the second partial specialization. 2191 // 2192 // Rather than synthesize function templates, we merely perform the 2193 // equivalent partial ordering by performing deduction directly on the 2194 // template arguments of the class template partial specializations. This 2195 // computation is slightly simpler than the general problem of function 2196 // template partial ordering, because class template partial specializations 2197 // are more constrained. We know that every template parameter is deduc 2198 llvm::SmallVector<TemplateArgument, 4> Deduced; 2199 Sema::TemplateDeductionInfo Info(Context, Loc); 2200 2201 // Determine whether PS1 is at least as specialized as PS2 2202 Deduced.resize(PS2->getTemplateParameters()->size()); 2203 bool Better1 = !DeduceTemplateArgumentsDuringPartialOrdering(*this, 2204 PS2->getTemplateParameters(), 2205 Context.getTypeDeclType(PS2), 2206 Context.getTypeDeclType(PS1), 2207 Info, 2208 Deduced, 2209 0); 2210 2211 // Determine whether PS2 is at least as specialized as PS1 2212 Deduced.clear(); 2213 Deduced.resize(PS1->getTemplateParameters()->size()); 2214 bool Better2 = !DeduceTemplateArgumentsDuringPartialOrdering(*this, 2215 PS1->getTemplateParameters(), 2216 Context.getTypeDeclType(PS1), 2217 Context.getTypeDeclType(PS2), 2218 Info, 2219 Deduced, 2220 0); 2221 2222 if (Better1 == Better2) 2223 return 0; 2224 2225 return Better1? PS1 : PS2; 2226} 2227 2228static void 2229MarkUsedTemplateParameters(Sema &SemaRef, 2230 const TemplateArgument &TemplateArg, 2231 bool OnlyDeduced, 2232 unsigned Depth, 2233 llvm::SmallVectorImpl<bool> &Used); 2234 2235/// \brief Mark the template parameters that are used by the given 2236/// expression. 2237static void 2238MarkUsedTemplateParameters(Sema &SemaRef, 2239 const Expr *E, 2240 bool OnlyDeduced, 2241 unsigned Depth, 2242 llvm::SmallVectorImpl<bool> &Used) { 2243 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to 2244 // find other occurrences of template parameters. 2245 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E); 2246 if (!DRE) 2247 return; 2248 2249 const NonTypeTemplateParmDecl *NTTP 2250 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 2251 if (!NTTP) 2252 return; 2253 2254 if (NTTP->getDepth() == Depth) 2255 Used[NTTP->getIndex()] = true; 2256} 2257 2258/// \brief Mark the template parameters that are used by the given 2259/// nested name specifier. 2260static void 2261MarkUsedTemplateParameters(Sema &SemaRef, 2262 NestedNameSpecifier *NNS, 2263 bool OnlyDeduced, 2264 unsigned Depth, 2265 llvm::SmallVectorImpl<bool> &Used) { 2266 if (!NNS) 2267 return; 2268 2269 MarkUsedTemplateParameters(SemaRef, NNS->getPrefix(), OnlyDeduced, Depth, 2270 Used); 2271 MarkUsedTemplateParameters(SemaRef, QualType(NNS->getAsType(), 0), 2272 OnlyDeduced, Depth, Used); 2273} 2274 2275/// \brief Mark the template parameters that are used by the given 2276/// template name. 2277static void 2278MarkUsedTemplateParameters(Sema &SemaRef, 2279 TemplateName Name, 2280 bool OnlyDeduced, 2281 unsigned Depth, 2282 llvm::SmallVectorImpl<bool> &Used) { 2283 if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 2284 if (TemplateTemplateParmDecl *TTP 2285 = dyn_cast<TemplateTemplateParmDecl>(Template)) { 2286 if (TTP->getDepth() == Depth) 2287 Used[TTP->getIndex()] = true; 2288 } 2289 return; 2290 } 2291 2292 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) 2293 MarkUsedTemplateParameters(SemaRef, QTN->getQualifier(), OnlyDeduced, 2294 Depth, Used); 2295 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 2296 MarkUsedTemplateParameters(SemaRef, DTN->getQualifier(), OnlyDeduced, 2297 Depth, Used); 2298} 2299 2300/// \brief Mark the template parameters that are used by the given 2301/// type. 2302static void 2303MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 2304 bool OnlyDeduced, 2305 unsigned Depth, 2306 llvm::SmallVectorImpl<bool> &Used) { 2307 if (T.isNull()) 2308 return; 2309 2310 // Non-dependent types have nothing deducible 2311 if (!T->isDependentType()) 2312 return; 2313 2314 T = SemaRef.Context.getCanonicalType(T); 2315 switch (T->getTypeClass()) { 2316 case Type::Pointer: 2317 MarkUsedTemplateParameters(SemaRef, 2318 cast<PointerType>(T)->getPointeeType(), 2319 OnlyDeduced, 2320 Depth, 2321 Used); 2322 break; 2323 2324 case Type::BlockPointer: 2325 MarkUsedTemplateParameters(SemaRef, 2326 cast<BlockPointerType>(T)->getPointeeType(), 2327 OnlyDeduced, 2328 Depth, 2329 Used); 2330 break; 2331 2332 case Type::LValueReference: 2333 case Type::RValueReference: 2334 MarkUsedTemplateParameters(SemaRef, 2335 cast<ReferenceType>(T)->getPointeeType(), 2336 OnlyDeduced, 2337 Depth, 2338 Used); 2339 break; 2340 2341 case Type::MemberPointer: { 2342 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 2343 MarkUsedTemplateParameters(SemaRef, MemPtr->getPointeeType(), OnlyDeduced, 2344 Depth, Used); 2345 MarkUsedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0), 2346 OnlyDeduced, Depth, Used); 2347 break; 2348 } 2349 2350 case Type::DependentSizedArray: 2351 MarkUsedTemplateParameters(SemaRef, 2352 cast<DependentSizedArrayType>(T)->getSizeExpr(), 2353 OnlyDeduced, Depth, Used); 2354 // Fall through to check the element type 2355 2356 case Type::ConstantArray: 2357 case Type::IncompleteArray: 2358 MarkUsedTemplateParameters(SemaRef, 2359 cast<ArrayType>(T)->getElementType(), 2360 OnlyDeduced, Depth, Used); 2361 break; 2362 2363 case Type::Vector: 2364 case Type::ExtVector: 2365 MarkUsedTemplateParameters(SemaRef, 2366 cast<VectorType>(T)->getElementType(), 2367 OnlyDeduced, Depth, Used); 2368 break; 2369 2370 case Type::DependentSizedExtVector: { 2371 const DependentSizedExtVectorType *VecType 2372 = cast<DependentSizedExtVectorType>(T); 2373 MarkUsedTemplateParameters(SemaRef, VecType->getElementType(), OnlyDeduced, 2374 Depth, Used); 2375 MarkUsedTemplateParameters(SemaRef, VecType->getSizeExpr(), OnlyDeduced, 2376 Depth, Used); 2377 break; 2378 } 2379 2380 case Type::FunctionProto: { 2381 const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 2382 MarkUsedTemplateParameters(SemaRef, Proto->getResultType(), OnlyDeduced, 2383 Depth, Used); 2384 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I) 2385 MarkUsedTemplateParameters(SemaRef, Proto->getArgType(I), OnlyDeduced, 2386 Depth, Used); 2387 break; 2388 } 2389 2390 case Type::TemplateTypeParm: { 2391 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T); 2392 if (TTP->getDepth() == Depth) 2393 Used[TTP->getIndex()] = true; 2394 break; 2395 } 2396 2397 case Type::TemplateSpecialization: { 2398 const TemplateSpecializationType *Spec 2399 = cast<TemplateSpecializationType>(T); 2400 MarkUsedTemplateParameters(SemaRef, Spec->getTemplateName(), OnlyDeduced, 2401 Depth, Used); 2402 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 2403 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 2404 Used); 2405 break; 2406 } 2407 2408 case Type::Complex: 2409 if (!OnlyDeduced) 2410 MarkUsedTemplateParameters(SemaRef, 2411 cast<ComplexType>(T)->getElementType(), 2412 OnlyDeduced, Depth, Used); 2413 break; 2414 2415 case Type::Typename: 2416 if (!OnlyDeduced) 2417 MarkUsedTemplateParameters(SemaRef, 2418 cast<TypenameType>(T)->getQualifier(), 2419 OnlyDeduced, Depth, Used); 2420 break; 2421 2422 case Type::TypeOf: 2423 if (!OnlyDeduced) 2424 MarkUsedTemplateParameters(SemaRef, 2425 cast<TypeOfType>(T)->getUnderlyingType(), 2426 OnlyDeduced, Depth, Used); 2427 break; 2428 2429 case Type::TypeOfExpr: 2430 if (!OnlyDeduced) 2431 MarkUsedTemplateParameters(SemaRef, 2432 cast<TypeOfExprType>(T)->getUnderlyingExpr(), 2433 OnlyDeduced, Depth, Used); 2434 break; 2435 2436 case Type::Decltype: 2437 if (!OnlyDeduced) 2438 MarkUsedTemplateParameters(SemaRef, 2439 cast<DecltypeType>(T)->getUnderlyingExpr(), 2440 OnlyDeduced, Depth, Used); 2441 break; 2442 2443 // None of these types have any template parameters in them. 2444 case Type::Builtin: 2445 case Type::VariableArray: 2446 case Type::FunctionNoProto: 2447 case Type::Record: 2448 case Type::Enum: 2449 case Type::ObjCInterface: 2450 case Type::ObjCObjectPointer: 2451 case Type::UnresolvedUsing: 2452#define TYPE(Class, Base) 2453#define ABSTRACT_TYPE(Class, Base) 2454#define DEPENDENT_TYPE(Class, Base) 2455#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 2456#include "clang/AST/TypeNodes.def" 2457 break; 2458 } 2459} 2460 2461/// \brief Mark the template parameters that are used by this 2462/// template argument. 2463static void 2464MarkUsedTemplateParameters(Sema &SemaRef, 2465 const TemplateArgument &TemplateArg, 2466 bool OnlyDeduced, 2467 unsigned Depth, 2468 llvm::SmallVectorImpl<bool> &Used) { 2469 switch (TemplateArg.getKind()) { 2470 case TemplateArgument::Null: 2471 case TemplateArgument::Integral: 2472 case TemplateArgument::Declaration: 2473 break; 2474 2475 case TemplateArgument::Type: 2476 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsType(), OnlyDeduced, 2477 Depth, Used); 2478 break; 2479 2480 case TemplateArgument::Template: 2481 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsTemplate(), 2482 OnlyDeduced, Depth, Used); 2483 break; 2484 2485 case TemplateArgument::Expression: 2486 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsExpr(), OnlyDeduced, 2487 Depth, Used); 2488 break; 2489 2490 case TemplateArgument::Pack: 2491 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(), 2492 PEnd = TemplateArg.pack_end(); 2493 P != PEnd; ++P) 2494 MarkUsedTemplateParameters(SemaRef, *P, OnlyDeduced, Depth, Used); 2495 break; 2496 } 2497} 2498 2499/// \brief Mark the template parameters can be deduced by the given 2500/// template argument list. 2501/// 2502/// \param TemplateArgs the template argument list from which template 2503/// parameters will be deduced. 2504/// 2505/// \param Deduced a bit vector whose elements will be set to \c true 2506/// to indicate when the corresponding template parameter will be 2507/// deduced. 2508void 2509Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 2510 bool OnlyDeduced, unsigned Depth, 2511 llvm::SmallVectorImpl<bool> &Used) { 2512 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 2513 ::MarkUsedTemplateParameters(*this, TemplateArgs[I], OnlyDeduced, 2514 Depth, Used); 2515} 2516 2517/// \brief Marks all of the template parameters that will be deduced by a 2518/// call to the given function template. 2519void Sema::MarkDeducedTemplateParameters(FunctionTemplateDecl *FunctionTemplate, 2520 llvm::SmallVectorImpl<bool> &Deduced) { 2521 TemplateParameterList *TemplateParams 2522 = FunctionTemplate->getTemplateParameters(); 2523 Deduced.clear(); 2524 Deduced.resize(TemplateParams->size()); 2525 2526 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2527 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 2528 ::MarkUsedTemplateParameters(*this, Function->getParamDecl(I)->getType(), 2529 true, TemplateParams->getDepth(), Deduced); 2530} 2531