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