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