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