SemaTemplateDeduction.cpp revision 588613178e3a10e2b840c8f4db9e058f2fec0005
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(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(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(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(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(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(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(ParamIn); 469 Info.SecondArg = TemplateArgument(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 TemplateArgumentLoc *PartialTemplateArgs 986 = Partial->getTemplateArgsAsWritten(); 987 unsigned N = Partial->getNumTemplateArgsAsWritten(); 988 llvm::SmallVector<TemplateArgumentLoc, 16> InstArgs(N); 989 for (unsigned I = 0; I != N; ++I) { 990 Decl *Param = const_cast<NamedDecl *>( 991 ClassTemplate->getTemplateParameters()->getParam(I)); 992 if (Subst(PartialTemplateArgs[I], InstArgs[I], 993 MultiLevelTemplateArgumentList(*DeducedArgumentList))) { 994 Info.Param = makeTemplateParameter(Param); 995 Info.FirstArg = PartialTemplateArgs[I].getArgument(); 996 return TDK_SubstitutionFailure; 997 } 998 } 999 1000 TemplateArgumentListBuilder ConvertedInstArgs( 1001 ClassTemplate->getTemplateParameters(), N); 1002 1003 if (CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(), 1004 /*LAngle*/ SourceLocation(), 1005 InstArgs.data(), N, 1006 /*RAngle*/ SourceLocation(), 1007 false, ConvertedInstArgs)) { 1008 // FIXME: fail with more useful information? 1009 return TDK_SubstitutionFailure; 1010 } 1011 1012 for (unsigned I = 0, E = ConvertedInstArgs.flatSize(); I != E; ++I) { 1013 // We don't really care if we overwrite the internal structures of 1014 // the arg list builder, because we're going to throw it all away. 1015 TemplateArgument &InstArg 1016 = const_cast<TemplateArgument&>(ConvertedInstArgs.getFlatArguments()[I]); 1017 1018 Decl *Param = const_cast<NamedDecl *>( 1019 ClassTemplate->getTemplateParameters()->getParam(I)); 1020 1021 if (InstArg.getKind() == TemplateArgument::Expression) { 1022 // When the argument is an expression, check the expression result 1023 // against the actual template parameter to get down to the canonical 1024 // template argument. 1025 Expr *InstExpr = InstArg.getAsExpr(); 1026 if (NonTypeTemplateParmDecl *NTTP 1027 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 1028 if (CheckTemplateArgument(NTTP, NTTP->getType(), InstExpr, InstArg)) { 1029 Info.Param = makeTemplateParameter(Param); 1030 Info.FirstArg = Partial->getTemplateArgs()[I]; 1031 return TDK_SubstitutionFailure; 1032 } 1033 } else if (TemplateTemplateParmDecl *TTP 1034 = dyn_cast<TemplateTemplateParmDecl>(Param)) { 1035 // FIXME: template template arguments should really resolve to decls 1036 DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(InstExpr); 1037 if (!DRE || CheckTemplateArgument(TTP, DRE)) { 1038 Info.Param = makeTemplateParameter(Param); 1039 Info.FirstArg = Partial->getTemplateArgs()[I]; 1040 return TDK_SubstitutionFailure; 1041 } 1042 } 1043 } 1044 1045 if (!isSameTemplateArg(Context, TemplateArgs[I], InstArg)) { 1046 Info.Param = makeTemplateParameter(Param); 1047 Info.FirstArg = TemplateArgs[I]; 1048 Info.SecondArg = InstArg; 1049 return TDK_NonDeducedMismatch; 1050 } 1051 } 1052 1053 if (Trap.hasErrorOccurred()) 1054 return TDK_SubstitutionFailure; 1055 1056 return TDK_Success; 1057} 1058 1059/// \brief Determine whether the given type T is a simple-template-id type. 1060static bool isSimpleTemplateIdType(QualType T) { 1061 if (const TemplateSpecializationType *Spec 1062 = T->getAs<TemplateSpecializationType>()) 1063 return Spec->getTemplateName().getAsTemplateDecl() != 0; 1064 1065 return false; 1066} 1067 1068/// \brief Substitute the explicitly-provided template arguments into the 1069/// given function template according to C++ [temp.arg.explicit]. 1070/// 1071/// \param FunctionTemplate the function template into which the explicit 1072/// template arguments will be substituted. 1073/// 1074/// \param ExplicitTemplateArguments the explicitly-specified template 1075/// arguments. 1076/// 1077/// \param NumExplicitTemplateArguments the number of explicitly-specified 1078/// template arguments in @p ExplicitTemplateArguments. This value may be zero. 1079/// 1080/// \param Deduced the deduced template arguments, which will be populated 1081/// with the converted and checked explicit template arguments. 1082/// 1083/// \param ParamTypes will be populated with the instantiated function 1084/// parameters. 1085/// 1086/// \param FunctionType if non-NULL, the result type of the function template 1087/// will also be instantiated and the pointed-to value will be updated with 1088/// the instantiated function type. 1089/// 1090/// \param Info if substitution fails for any reason, this object will be 1091/// populated with more information about the failure. 1092/// 1093/// \returns TDK_Success if substitution was successful, or some failure 1094/// condition. 1095Sema::TemplateDeductionResult 1096Sema::SubstituteExplicitTemplateArguments( 1097 FunctionTemplateDecl *FunctionTemplate, 1098 const TemplateArgumentLoc *ExplicitTemplateArgs, 1099 unsigned NumExplicitTemplateArgs, 1100 llvm::SmallVectorImpl<TemplateArgument> &Deduced, 1101 llvm::SmallVectorImpl<QualType> &ParamTypes, 1102 QualType *FunctionType, 1103 TemplateDeductionInfo &Info) { 1104 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1105 TemplateParameterList *TemplateParams 1106 = FunctionTemplate->getTemplateParameters(); 1107 1108 if (NumExplicitTemplateArgs == 0) { 1109 // No arguments to substitute; just copy over the parameter types and 1110 // fill in the function type. 1111 for (FunctionDecl::param_iterator P = Function->param_begin(), 1112 PEnd = Function->param_end(); 1113 P != PEnd; 1114 ++P) 1115 ParamTypes.push_back((*P)->getType()); 1116 1117 if (FunctionType) 1118 *FunctionType = Function->getType(); 1119 return TDK_Success; 1120 } 1121 1122 // Substitution of the explicit template arguments into a function template 1123 /// is a SFINAE context. Trap any errors that might occur. 1124 SFINAETrap Trap(*this); 1125 1126 // C++ [temp.arg.explicit]p3: 1127 // Template arguments that are present shall be specified in the 1128 // declaration order of their corresponding template-parameters. The 1129 // template argument list shall not specify more template-arguments than 1130 // there are corresponding template-parameters. 1131 TemplateArgumentListBuilder Builder(TemplateParams, 1132 NumExplicitTemplateArgs); 1133 1134 // Enter a new template instantiation context where we check the 1135 // explicitly-specified template arguments against this function template, 1136 // and then substitute them into the function parameter types. 1137 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1138 FunctionTemplate, Deduced.data(), Deduced.size(), 1139 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution); 1140 if (Inst) 1141 return TDK_InstantiationDepth; 1142 1143 if (CheckTemplateArgumentList(FunctionTemplate, 1144 SourceLocation(), SourceLocation(), 1145 ExplicitTemplateArgs, 1146 NumExplicitTemplateArgs, 1147 SourceLocation(), 1148 true, 1149 Builder) || Trap.hasErrorOccurred()) 1150 return TDK_InvalidExplicitArguments; 1151 1152 // Form the template argument list from the explicitly-specified 1153 // template arguments. 1154 TemplateArgumentList *ExplicitArgumentList 1155 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true); 1156 Info.reset(ExplicitArgumentList); 1157 1158 // Instantiate the types of each of the function parameters given the 1159 // explicitly-specified template arguments. 1160 for (FunctionDecl::param_iterator P = Function->param_begin(), 1161 PEnd = Function->param_end(); 1162 P != PEnd; 1163 ++P) { 1164 QualType ParamType 1165 = SubstType((*P)->getType(), 1166 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1167 (*P)->getLocation(), (*P)->getDeclName()); 1168 if (ParamType.isNull() || Trap.hasErrorOccurred()) 1169 return TDK_SubstitutionFailure; 1170 1171 ParamTypes.push_back(ParamType); 1172 } 1173 1174 // If the caller wants a full function type back, instantiate the return 1175 // type and form that function type. 1176 if (FunctionType) { 1177 // FIXME: exception-specifications? 1178 const FunctionProtoType *Proto 1179 = Function->getType()->getAs<FunctionProtoType>(); 1180 assert(Proto && "Function template does not have a prototype?"); 1181 1182 QualType ResultType 1183 = SubstType(Proto->getResultType(), 1184 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1185 Function->getTypeSpecStartLoc(), 1186 Function->getDeclName()); 1187 if (ResultType.isNull() || Trap.hasErrorOccurred()) 1188 return TDK_SubstitutionFailure; 1189 1190 *FunctionType = BuildFunctionType(ResultType, 1191 ParamTypes.data(), ParamTypes.size(), 1192 Proto->isVariadic(), 1193 Proto->getTypeQuals(), 1194 Function->getLocation(), 1195 Function->getDeclName()); 1196 if (FunctionType->isNull() || Trap.hasErrorOccurred()) 1197 return TDK_SubstitutionFailure; 1198 } 1199 1200 // C++ [temp.arg.explicit]p2: 1201 // Trailing template arguments that can be deduced (14.8.2) may be 1202 // omitted from the list of explicit template-arguments. If all of the 1203 // template arguments can be deduced, they may all be omitted; in this 1204 // case, the empty template argument list <> itself may also be omitted. 1205 // 1206 // Take all of the explicitly-specified arguments and put them into the 1207 // set of deduced template arguments. 1208 Deduced.reserve(TemplateParams->size()); 1209 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) 1210 Deduced.push_back(ExplicitArgumentList->get(I)); 1211 1212 return TDK_Success; 1213} 1214 1215/// \brief Finish template argument deduction for a function template, 1216/// checking the deduced template arguments for completeness and forming 1217/// the function template specialization. 1218Sema::TemplateDeductionResult 1219Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate, 1220 llvm::SmallVectorImpl<TemplateArgument> &Deduced, 1221 FunctionDecl *&Specialization, 1222 TemplateDeductionInfo &Info) { 1223 TemplateParameterList *TemplateParams 1224 = FunctionTemplate->getTemplateParameters(); 1225 1226 // C++ [temp.deduct.type]p2: 1227 // [...] or if any template argument remains neither deduced nor 1228 // explicitly specified, template argument deduction fails. 1229 TemplateArgumentListBuilder Builder(TemplateParams, Deduced.size()); 1230 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 1231 if (Deduced[I].isNull()) { 1232 Info.Param = makeTemplateParameter( 1233 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1234 return TDK_Incomplete; 1235 } 1236 1237 Builder.Append(Deduced[I]); 1238 } 1239 1240 // Form the template argument list from the deduced template arguments. 1241 TemplateArgumentList *DeducedArgumentList 1242 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true); 1243 Info.reset(DeducedArgumentList); 1244 1245 // Template argument deduction for function templates in a SFINAE context. 1246 // Trap any errors that might occur. 1247 SFINAETrap Trap(*this); 1248 1249 // Enter a new template instantiation context while we instantiate the 1250 // actual function declaration. 1251 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1252 FunctionTemplate, Deduced.data(), Deduced.size(), 1253 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution); 1254 if (Inst) 1255 return TDK_InstantiationDepth; 1256 1257 // Substitute the deduced template arguments into the function template 1258 // declaration to produce the function template specialization. 1259 Specialization = cast_or_null<FunctionDecl>( 1260 SubstDecl(FunctionTemplate->getTemplatedDecl(), 1261 FunctionTemplate->getDeclContext(), 1262 MultiLevelTemplateArgumentList(*DeducedArgumentList))); 1263 if (!Specialization) 1264 return TDK_SubstitutionFailure; 1265 1266 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() == 1267 FunctionTemplate->getCanonicalDecl()); 1268 1269 // If the template argument list is owned by the function template 1270 // specialization, release it. 1271 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList) 1272 Info.take(); 1273 1274 // There may have been an error that did not prevent us from constructing a 1275 // declaration. Mark the declaration invalid and return with a substitution 1276 // failure. 1277 if (Trap.hasErrorOccurred()) { 1278 Specialization->setInvalidDecl(true); 1279 return TDK_SubstitutionFailure; 1280 } 1281 1282 return TDK_Success; 1283} 1284 1285/// \brief Perform template argument deduction from a function call 1286/// (C++ [temp.deduct.call]). 1287/// 1288/// \param FunctionTemplate the function template for which we are performing 1289/// template argument deduction. 1290/// 1291/// \param HasExplicitTemplateArgs whether any template arguments were 1292/// explicitly specified. 1293/// 1294/// \param ExplicitTemplateArguments when @p HasExplicitTemplateArgs is true, 1295/// the explicitly-specified template arguments. 1296/// 1297/// \param NumExplicitTemplateArguments when @p HasExplicitTemplateArgs is true, 1298/// the number of explicitly-specified template arguments in 1299/// @p ExplicitTemplateArguments. This value may be zero. 1300/// 1301/// \param Args the function call arguments 1302/// 1303/// \param NumArgs the number of arguments in Args 1304/// 1305/// \param Specialization if template argument deduction was successful, 1306/// this will be set to the function template specialization produced by 1307/// template argument deduction. 1308/// 1309/// \param Info the argument will be updated to provide additional information 1310/// about template argument deduction. 1311/// 1312/// \returns the result of template argument deduction. 1313Sema::TemplateDeductionResult 1314Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1315 bool HasExplicitTemplateArgs, 1316 const TemplateArgumentLoc *ExplicitTemplateArgs, 1317 unsigned NumExplicitTemplateArgs, 1318 Expr **Args, unsigned NumArgs, 1319 FunctionDecl *&Specialization, 1320 TemplateDeductionInfo &Info) { 1321 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1322 1323 // C++ [temp.deduct.call]p1: 1324 // Template argument deduction is done by comparing each function template 1325 // parameter type (call it P) with the type of the corresponding argument 1326 // of the call (call it A) as described below. 1327 unsigned CheckArgs = NumArgs; 1328 if (NumArgs < Function->getMinRequiredArguments()) 1329 return TDK_TooFewArguments; 1330 else if (NumArgs > Function->getNumParams()) { 1331 const FunctionProtoType *Proto 1332 = Function->getType()->getAs<FunctionProtoType>(); 1333 if (!Proto->isVariadic()) 1334 return TDK_TooManyArguments; 1335 1336 CheckArgs = Function->getNumParams(); 1337 } 1338 1339 // The types of the parameters from which we will perform template argument 1340 // deduction. 1341 TemplateParameterList *TemplateParams 1342 = FunctionTemplate->getTemplateParameters(); 1343 llvm::SmallVector<TemplateArgument, 4> Deduced; 1344 llvm::SmallVector<QualType, 4> ParamTypes; 1345 if (NumExplicitTemplateArgs) { 1346 TemplateDeductionResult Result = 1347 SubstituteExplicitTemplateArguments(FunctionTemplate, 1348 ExplicitTemplateArgs, 1349 NumExplicitTemplateArgs, 1350 Deduced, 1351 ParamTypes, 1352 0, 1353 Info); 1354 if (Result) 1355 return Result; 1356 } else { 1357 // Just fill in the parameter types from the function declaration. 1358 for (unsigned I = 0; I != CheckArgs; ++I) 1359 ParamTypes.push_back(Function->getParamDecl(I)->getType()); 1360 } 1361 1362 // Deduce template arguments from the function parameters. 1363 Deduced.resize(TemplateParams->size()); 1364 for (unsigned I = 0; I != CheckArgs; ++I) { 1365 QualType ParamType = ParamTypes[I]; 1366 QualType ArgType = Args[I]->getType(); 1367 1368 // C++ [temp.deduct.call]p2: 1369 // If P is not a reference type: 1370 QualType CanonParamType = Context.getCanonicalType(ParamType); 1371 bool ParamWasReference = isa<ReferenceType>(CanonParamType); 1372 if (!ParamWasReference) { 1373 // - If A is an array type, the pointer type produced by the 1374 // array-to-pointer standard conversion (4.2) is used in place of 1375 // A for type deduction; otherwise, 1376 if (ArgType->isArrayType()) 1377 ArgType = Context.getArrayDecayedType(ArgType); 1378 // - If A is a function type, the pointer type produced by the 1379 // function-to-pointer standard conversion (4.3) is used in place 1380 // of A for type deduction; otherwise, 1381 else if (ArgType->isFunctionType()) 1382 ArgType = Context.getPointerType(ArgType); 1383 else { 1384 // - If A is a cv-qualified type, the top level cv-qualifiers of A’s 1385 // type are ignored for type deduction. 1386 QualType CanonArgType = Context.getCanonicalType(ArgType); 1387 if (CanonArgType.getCVRQualifiers()) 1388 ArgType = CanonArgType.getUnqualifiedType(); 1389 } 1390 } 1391 1392 // C++0x [temp.deduct.call]p3: 1393 // If P is a cv-qualified type, the top level cv-qualifiers of P’s type 1394 // are ignored for type deduction. 1395 if (CanonParamType.getCVRQualifiers()) 1396 ParamType = CanonParamType.getUnqualifiedType(); 1397 if (const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>()) { 1398 // [...] If P is a reference type, the type referred to by P is used 1399 // for type deduction. 1400 ParamType = ParamRefType->getPointeeType(); 1401 1402 // [...] If P is of the form T&&, where T is a template parameter, and 1403 // the argument is an lvalue, the type A& is used in place of A for 1404 // type deduction. 1405 if (isa<RValueReferenceType>(ParamRefType) && 1406 ParamRefType->getAs<TemplateTypeParmType>() && 1407 Args[I]->isLvalue(Context) == Expr::LV_Valid) 1408 ArgType = Context.getLValueReferenceType(ArgType); 1409 } 1410 1411 // C++0x [temp.deduct.call]p4: 1412 // In general, the deduction process attempts to find template argument 1413 // values that will make the deduced A identical to A (after the type A 1414 // is transformed as described above). [...] 1415 unsigned TDF = TDF_SkipNonDependent; 1416 1417 // - If the original P is a reference type, the deduced A (i.e., the 1418 // type referred to by the reference) can be more cv-qualified than 1419 // the transformed A. 1420 if (ParamWasReference) 1421 TDF |= TDF_ParamWithReferenceType; 1422 // - The transformed A can be another pointer or pointer to member 1423 // type that can be converted to the deduced A via a qualification 1424 // conversion (4.4). 1425 if (ArgType->isPointerType() || ArgType->isMemberPointerType()) 1426 TDF |= TDF_IgnoreQualifiers; 1427 // - If P is a class and P has the form simple-template-id, then the 1428 // transformed A can be a derived class of the deduced A. Likewise, 1429 // if P is a pointer to a class of the form simple-template-id, the 1430 // transformed A can be a pointer to a derived class pointed to by 1431 // the deduced A. 1432 if (isSimpleTemplateIdType(ParamType) || 1433 (isa<PointerType>(ParamType) && 1434 isSimpleTemplateIdType( 1435 ParamType->getAs<PointerType>()->getPointeeType()))) 1436 TDF |= TDF_DerivedClass; 1437 1438 if (TemplateDeductionResult Result 1439 = ::DeduceTemplateArguments(Context, TemplateParams, 1440 ParamType, ArgType, Info, Deduced, 1441 TDF)) 1442 return Result; 1443 1444 // FIXME: C++0x [temp.deduct.call] paragraphs 6-9 deal with function 1445 // pointer parameters. 1446 1447 // FIXME: we need to check that the deduced A is the same as A, 1448 // modulo the various allowed differences. 1449 } 1450 1451 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 1452 Specialization, Info); 1453} 1454 1455/// \brief Deduce template arguments when taking the address of a function 1456/// template (C++ [temp.deduct.funcaddr]) or matching a 1457/// 1458/// \param FunctionTemplate the function template for which we are performing 1459/// template argument deduction. 1460/// 1461/// \param HasExplicitTemplateArgs whether any template arguments were 1462/// explicitly specified. 1463/// 1464/// \param ExplicitTemplateArguments when @p HasExplicitTemplateArgs is true, 1465/// the explicitly-specified template arguments. 1466/// 1467/// \param NumExplicitTemplateArguments when @p HasExplicitTemplateArgs is true, 1468/// the number of explicitly-specified template arguments in 1469/// @p ExplicitTemplateArguments. This value may be zero. 1470/// 1471/// \param ArgFunctionType the function type that will be used as the 1472/// "argument" type (A) when performing template argument deduction from the 1473/// function template's function type. 1474/// 1475/// \param Specialization if template argument deduction was successful, 1476/// this will be set to the function template specialization produced by 1477/// template argument deduction. 1478/// 1479/// \param Info the argument will be updated to provide additional information 1480/// about template argument deduction. 1481/// 1482/// \returns the result of template argument deduction. 1483Sema::TemplateDeductionResult 1484Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1485 bool HasExplicitTemplateArgs, 1486 const TemplateArgumentLoc *ExplicitTemplateArgs, 1487 unsigned NumExplicitTemplateArgs, 1488 QualType ArgFunctionType, 1489 FunctionDecl *&Specialization, 1490 TemplateDeductionInfo &Info) { 1491 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1492 TemplateParameterList *TemplateParams 1493 = FunctionTemplate->getTemplateParameters(); 1494 QualType FunctionType = Function->getType(); 1495 1496 // Substitute any explicit template arguments. 1497 llvm::SmallVector<TemplateArgument, 4> Deduced; 1498 llvm::SmallVector<QualType, 4> ParamTypes; 1499 if (HasExplicitTemplateArgs) { 1500 if (TemplateDeductionResult Result 1501 = SubstituteExplicitTemplateArguments(FunctionTemplate, 1502 ExplicitTemplateArgs, 1503 NumExplicitTemplateArgs, 1504 Deduced, ParamTypes, 1505 &FunctionType, Info)) 1506 return Result; 1507 } 1508 1509 // Template argument deduction for function templates in a SFINAE context. 1510 // Trap any errors that might occur. 1511 SFINAETrap Trap(*this); 1512 1513 // Deduce template arguments from the function type. 1514 Deduced.resize(TemplateParams->size()); 1515 if (TemplateDeductionResult Result 1516 = ::DeduceTemplateArguments(Context, TemplateParams, 1517 FunctionType, ArgFunctionType, Info, 1518 Deduced, 0)) 1519 return Result; 1520 1521 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 1522 Specialization, Info); 1523} 1524 1525/// \brief Deduce template arguments for a templated conversion 1526/// function (C++ [temp.deduct.conv]) and, if successful, produce a 1527/// conversion function template specialization. 1528Sema::TemplateDeductionResult 1529Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1530 QualType ToType, 1531 CXXConversionDecl *&Specialization, 1532 TemplateDeductionInfo &Info) { 1533 CXXConversionDecl *Conv 1534 = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl()); 1535 QualType FromType = Conv->getConversionType(); 1536 1537 // Canonicalize the types for deduction. 1538 QualType P = Context.getCanonicalType(FromType); 1539 QualType A = Context.getCanonicalType(ToType); 1540 1541 // C++0x [temp.deduct.conv]p3: 1542 // If P is a reference type, the type referred to by P is used for 1543 // type deduction. 1544 if (const ReferenceType *PRef = P->getAs<ReferenceType>()) 1545 P = PRef->getPointeeType(); 1546 1547 // C++0x [temp.deduct.conv]p3: 1548 // If A is a reference type, the type referred to by A is used 1549 // for type deduction. 1550 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 1551 A = ARef->getPointeeType(); 1552 // C++ [temp.deduct.conv]p2: 1553 // 1554 // If A is not a reference type: 1555 else { 1556 assert(!A->isReferenceType() && "Reference types were handled above"); 1557 1558 // - If P is an array type, the pointer type produced by the 1559 // array-to-pointer standard conversion (4.2) is used in place 1560 // of P for type deduction; otherwise, 1561 if (P->isArrayType()) 1562 P = Context.getArrayDecayedType(P); 1563 // - If P is a function type, the pointer type produced by the 1564 // function-to-pointer standard conversion (4.3) is used in 1565 // place of P for type deduction; otherwise, 1566 else if (P->isFunctionType()) 1567 P = Context.getPointerType(P); 1568 // - If P is a cv-qualified type, the top level cv-qualifiers of 1569 // P’s type are ignored for type deduction. 1570 else 1571 P = P.getUnqualifiedType(); 1572 1573 // C++0x [temp.deduct.conv]p3: 1574 // If A is a cv-qualified type, the top level cv-qualifiers of A’s 1575 // type are ignored for type deduction. 1576 A = A.getUnqualifiedType(); 1577 } 1578 1579 // Template argument deduction for function templates in a SFINAE context. 1580 // Trap any errors that might occur. 1581 SFINAETrap Trap(*this); 1582 1583 // C++ [temp.deduct.conv]p1: 1584 // Template argument deduction is done by comparing the return 1585 // type of the template conversion function (call it P) with the 1586 // type that is required as the result of the conversion (call it 1587 // A) as described in 14.8.2.4. 1588 TemplateParameterList *TemplateParams 1589 = FunctionTemplate->getTemplateParameters(); 1590 llvm::SmallVector<TemplateArgument, 4> Deduced; 1591 Deduced.resize(TemplateParams->size()); 1592 1593 // C++0x [temp.deduct.conv]p4: 1594 // In general, the deduction process attempts to find template 1595 // argument values that will make the deduced A identical to 1596 // A. However, there are two cases that allow a difference: 1597 unsigned TDF = 0; 1598 // - If the original A is a reference type, A can be more 1599 // cv-qualified than the deduced A (i.e., the type referred to 1600 // by the reference) 1601 if (ToType->isReferenceType()) 1602 TDF |= TDF_ParamWithReferenceType; 1603 // - The deduced A can be another pointer or pointer to member 1604 // type that can be converted to A via a qualification 1605 // conversion. 1606 // 1607 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 1608 // both P and A are pointers or member pointers. In this case, we 1609 // just ignore cv-qualifiers completely). 1610 if ((P->isPointerType() && A->isPointerType()) || 1611 (P->isMemberPointerType() && P->isMemberPointerType())) 1612 TDF |= TDF_IgnoreQualifiers; 1613 if (TemplateDeductionResult Result 1614 = ::DeduceTemplateArguments(Context, TemplateParams, 1615 P, A, Info, Deduced, TDF)) 1616 return Result; 1617 1618 // FIXME: we need to check that the deduced A is the same as A, 1619 // modulo the various allowed differences. 1620 1621 // Finish template argument deduction. 1622 FunctionDecl *Spec = 0; 1623 TemplateDeductionResult Result 1624 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, Spec, Info); 1625 Specialization = cast_or_null<CXXConversionDecl>(Spec); 1626 return Result; 1627} 1628 1629/// \brief Stores the result of comparing the qualifiers of two types. 1630enum DeductionQualifierComparison { 1631 NeitherMoreQualified = 0, 1632 ParamMoreQualified, 1633 ArgMoreQualified 1634}; 1635 1636/// \brief Deduce the template arguments during partial ordering by comparing 1637/// the parameter type and the argument type (C++0x [temp.deduct.partial]). 1638/// 1639/// \param Context the AST context in which this deduction occurs. 1640/// 1641/// \param TemplateParams the template parameters that we are deducing 1642/// 1643/// \param ParamIn the parameter type 1644/// 1645/// \param ArgIn the argument type 1646/// 1647/// \param Info information about the template argument deduction itself 1648/// 1649/// \param Deduced the deduced template arguments 1650/// 1651/// \returns the result of template argument deduction so far. Note that a 1652/// "success" result means that template argument deduction has not yet failed, 1653/// but it may still fail, later, for other reasons. 1654static Sema::TemplateDeductionResult 1655DeduceTemplateArgumentsDuringPartialOrdering(ASTContext &Context, 1656 TemplateParameterList *TemplateParams, 1657 QualType ParamIn, QualType ArgIn, 1658 Sema::TemplateDeductionInfo &Info, 1659 llvm::SmallVectorImpl<TemplateArgument> &Deduced, 1660 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 1661 CanQualType Param = Context.getCanonicalType(ParamIn); 1662 CanQualType Arg = Context.getCanonicalType(ArgIn); 1663 1664 // C++0x [temp.deduct.partial]p5: 1665 // Before the partial ordering is done, certain transformations are 1666 // performed on the types used for partial ordering: 1667 // - If P is a reference type, P is replaced by the type referred to. 1668 CanQual<ReferenceType> ParamRef = Param->getAs<ReferenceType>(); 1669 if (!ParamRef.isNull()) 1670 Param = ParamRef->getPointeeType(); 1671 1672 // - If A is a reference type, A is replaced by the type referred to. 1673 CanQual<ReferenceType> ArgRef = Arg->getAs<ReferenceType>(); 1674 if (!ArgRef.isNull()) 1675 Arg = ArgRef->getPointeeType(); 1676 1677 if (QualifierComparisons && !ParamRef.isNull() && !ArgRef.isNull()) { 1678 // C++0x [temp.deduct.partial]p6: 1679 // If both P and A were reference types (before being replaced with the 1680 // type referred to above), determine which of the two types (if any) is 1681 // more cv-qualified than the other; otherwise the types are considered to 1682 // be equally cv-qualified for partial ordering purposes. The result of this 1683 // determination will be used below. 1684 // 1685 // We save this information for later, using it only when deduction 1686 // succeeds in both directions. 1687 DeductionQualifierComparison QualifierResult = NeitherMoreQualified; 1688 if (Param.isMoreQualifiedThan(Arg)) 1689 QualifierResult = ParamMoreQualified; 1690 else if (Arg.isMoreQualifiedThan(Param)) 1691 QualifierResult = ArgMoreQualified; 1692 QualifierComparisons->push_back(QualifierResult); 1693 } 1694 1695 // C++0x [temp.deduct.partial]p7: 1696 // Remove any top-level cv-qualifiers: 1697 // - If P is a cv-qualified type, P is replaced by the cv-unqualified 1698 // version of P. 1699 Param = Param.getUnqualifiedType(); 1700 // - If A is a cv-qualified type, A is replaced by the cv-unqualified 1701 // version of A. 1702 Arg = Arg.getUnqualifiedType(); 1703 1704 // C++0x [temp.deduct.partial]p8: 1705 // Using the resulting types P and A the deduction is then done as 1706 // described in 14.9.2.5. If deduction succeeds for a given type, the type 1707 // from the argument template is considered to be at least as specialized 1708 // as the type from the parameter template. 1709 return DeduceTemplateArguments(Context, TemplateParams, Param, Arg, Info, 1710 Deduced, TDF_None); 1711} 1712 1713static void 1714MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 1715 bool OnlyDeduced, 1716 unsigned Level, 1717 llvm::SmallVectorImpl<bool> &Deduced); 1718 1719/// \brief Determine whether the function template \p FT1 is at least as 1720/// specialized as \p FT2. 1721static bool isAtLeastAsSpecializedAs(Sema &S, 1722 FunctionTemplateDecl *FT1, 1723 FunctionTemplateDecl *FT2, 1724 TemplatePartialOrderingContext TPOC, 1725 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 1726 FunctionDecl *FD1 = FT1->getTemplatedDecl(); 1727 FunctionDecl *FD2 = FT2->getTemplatedDecl(); 1728 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 1729 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 1730 1731 assert(Proto1 && Proto2 && "Function templates must have prototypes"); 1732 TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 1733 llvm::SmallVector<TemplateArgument, 4> Deduced; 1734 Deduced.resize(TemplateParams->size()); 1735 1736 // C++0x [temp.deduct.partial]p3: 1737 // The types used to determine the ordering depend on the context in which 1738 // the partial ordering is done: 1739 Sema::TemplateDeductionInfo Info(S.Context); 1740 switch (TPOC) { 1741 case TPOC_Call: { 1742 // - In the context of a function call, the function parameter types are 1743 // used. 1744 unsigned NumParams = std::min(Proto1->getNumArgs(), Proto2->getNumArgs()); 1745 for (unsigned I = 0; I != NumParams; ++I) 1746 if (DeduceTemplateArgumentsDuringPartialOrdering(S.Context, 1747 TemplateParams, 1748 Proto2->getArgType(I), 1749 Proto1->getArgType(I), 1750 Info, 1751 Deduced, 1752 QualifierComparisons)) 1753 return false; 1754 1755 break; 1756 } 1757 1758 case TPOC_Conversion: 1759 // - In the context of a call to a conversion operator, the return types 1760 // of the conversion function templates are used. 1761 if (DeduceTemplateArgumentsDuringPartialOrdering(S.Context, 1762 TemplateParams, 1763 Proto2->getResultType(), 1764 Proto1->getResultType(), 1765 Info, 1766 Deduced, 1767 QualifierComparisons)) 1768 return false; 1769 break; 1770 1771 case TPOC_Other: 1772 // - In other contexts (14.6.6.2) the function template’s function type 1773 // is used. 1774 if (DeduceTemplateArgumentsDuringPartialOrdering(S.Context, 1775 TemplateParams, 1776 FD2->getType(), 1777 FD1->getType(), 1778 Info, 1779 Deduced, 1780 QualifierComparisons)) 1781 return false; 1782 break; 1783 } 1784 1785 // C++0x [temp.deduct.partial]p11: 1786 // In most cases, all template parameters must have values in order for 1787 // deduction to succeed, but for partial ordering purposes a template 1788 // parameter may remain without a value provided it is not used in the 1789 // types being used for partial ordering. [ Note: a template parameter used 1790 // in a non-deduced context is considered used. -end note] 1791 unsigned ArgIdx = 0, NumArgs = Deduced.size(); 1792 for (; ArgIdx != NumArgs; ++ArgIdx) 1793 if (Deduced[ArgIdx].isNull()) 1794 break; 1795 1796 if (ArgIdx == NumArgs) { 1797 // All template arguments were deduced. FT1 is at least as specialized 1798 // as FT2. 1799 return true; 1800 } 1801 1802 // Figure out which template parameters were used. 1803 llvm::SmallVector<bool, 4> UsedParameters; 1804 UsedParameters.resize(TemplateParams->size()); 1805 switch (TPOC) { 1806 case TPOC_Call: { 1807 unsigned NumParams = std::min(Proto1->getNumArgs(), Proto2->getNumArgs()); 1808 for (unsigned I = 0; I != NumParams; ++I) 1809 ::MarkUsedTemplateParameters(S, Proto2->getArgType(I), false, 1810 TemplateParams->getDepth(), 1811 UsedParameters); 1812 break; 1813 } 1814 1815 case TPOC_Conversion: 1816 ::MarkUsedTemplateParameters(S, Proto2->getResultType(), false, 1817 TemplateParams->getDepth(), 1818 UsedParameters); 1819 break; 1820 1821 case TPOC_Other: 1822 ::MarkUsedTemplateParameters(S, FD2->getType(), false, 1823 TemplateParams->getDepth(), 1824 UsedParameters); 1825 break; 1826 } 1827 1828 for (; ArgIdx != NumArgs; ++ArgIdx) 1829 // If this argument had no value deduced but was used in one of the types 1830 // used for partial ordering, then deduction fails. 1831 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 1832 return false; 1833 1834 return true; 1835} 1836 1837 1838/// \brief Returns the more specialized function template according 1839/// to the rules of function template partial ordering (C++ [temp.func.order]). 1840/// 1841/// \param FT1 the first function template 1842/// 1843/// \param FT2 the second function template 1844/// 1845/// \param TPOC the context in which we are performing partial ordering of 1846/// function templates. 1847/// 1848/// \returns the more specialized function template. If neither 1849/// template is more specialized, returns NULL. 1850FunctionTemplateDecl * 1851Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, 1852 FunctionTemplateDecl *FT2, 1853 TemplatePartialOrderingContext TPOC) { 1854 llvm::SmallVector<DeductionQualifierComparison, 4> QualifierComparisons; 1855 bool Better1 = isAtLeastAsSpecializedAs(*this, FT1, FT2, TPOC, 0); 1856 bool Better2 = isAtLeastAsSpecializedAs(*this, FT2, FT1, TPOC, 1857 &QualifierComparisons); 1858 1859 if (Better1 != Better2) // We have a clear winner 1860 return Better1? FT1 : FT2; 1861 1862 if (!Better1 && !Better2) // Neither is better than the other 1863 return 0; 1864 1865 1866 // C++0x [temp.deduct.partial]p10: 1867 // If for each type being considered a given template is at least as 1868 // specialized for all types and more specialized for some set of types and 1869 // the other template is not more specialized for any types or is not at 1870 // least as specialized for any types, then the given template is more 1871 // specialized than the other template. Otherwise, neither template is more 1872 // specialized than the other. 1873 Better1 = false; 1874 Better2 = false; 1875 for (unsigned I = 0, N = QualifierComparisons.size(); I != N; ++I) { 1876 // C++0x [temp.deduct.partial]p9: 1877 // If, for a given type, deduction succeeds in both directions (i.e., the 1878 // types are identical after the transformations above) and if the type 1879 // from the argument template is more cv-qualified than the type from the 1880 // parameter template (as described above) that type is considered to be 1881 // more specialized than the other. If neither type is more cv-qualified 1882 // than the other then neither type is more specialized than the other. 1883 switch (QualifierComparisons[I]) { 1884 case NeitherMoreQualified: 1885 break; 1886 1887 case ParamMoreQualified: 1888 Better1 = true; 1889 if (Better2) 1890 return 0; 1891 break; 1892 1893 case ArgMoreQualified: 1894 Better2 = true; 1895 if (Better1) 1896 return 0; 1897 break; 1898 } 1899 } 1900 1901 assert(!(Better1 && Better2) && "Should have broken out in the loop above"); 1902 if (Better1) 1903 return FT1; 1904 else if (Better2) 1905 return FT2; 1906 else 1907 return 0; 1908} 1909 1910/// \brief Determine if the two templates are equivalent. 1911static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) { 1912 if (T1 == T2) 1913 return true; 1914 1915 if (!T1 || !T2) 1916 return false; 1917 1918 return T1->getCanonicalDecl() == T2->getCanonicalDecl(); 1919} 1920 1921/// \brief Retrieve the most specialized of the given function template 1922/// specializations. 1923/// 1924/// \param Specializations the set of function template specializations that 1925/// we will be comparing. 1926/// 1927/// \param NumSpecializations the number of function template specializations in 1928/// \p Specializations 1929/// 1930/// \param TPOC the partial ordering context to use to compare the function 1931/// template specializations. 1932/// 1933/// \param Loc the location where the ambiguity or no-specializations 1934/// diagnostic should occur. 1935/// 1936/// \param NoneDiag partial diagnostic used to diagnose cases where there are 1937/// no matching candidates. 1938/// 1939/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one 1940/// occurs. 1941/// 1942/// \param CandidateDiag partial diagnostic used for each function template 1943/// specialization that is a candidate in the ambiguous ordering. One parameter 1944/// in this diagnostic should be unbound, which will correspond to the string 1945/// describing the template arguments for the function template specialization. 1946/// 1947/// \param Index if non-NULL and the result of this function is non-nULL, 1948/// receives the index corresponding to the resulting function template 1949/// specialization. 1950/// 1951/// \returns the most specialized function template specialization, if 1952/// found. Otherwise, returns NULL. 1953/// 1954/// \todo FIXME: Consider passing in the "also-ran" candidates that failed 1955/// template argument deduction. 1956FunctionDecl *Sema::getMostSpecialized(FunctionDecl **Specializations, 1957 unsigned NumSpecializations, 1958 TemplatePartialOrderingContext TPOC, 1959 SourceLocation Loc, 1960 const PartialDiagnostic &NoneDiag, 1961 const PartialDiagnostic &AmbigDiag, 1962 const PartialDiagnostic &CandidateDiag, 1963 unsigned *Index) { 1964 if (NumSpecializations == 0) { 1965 Diag(Loc, NoneDiag); 1966 return 0; 1967 } 1968 1969 if (NumSpecializations == 1) { 1970 if (Index) 1971 *Index = 0; 1972 1973 return Specializations[0]; 1974 } 1975 1976 1977 // Find the function template that is better than all of the templates it 1978 // has been compared to. 1979 unsigned Best = 0; 1980 FunctionTemplateDecl *BestTemplate 1981 = Specializations[Best]->getPrimaryTemplate(); 1982 assert(BestTemplate && "Not a function template specialization?"); 1983 for (unsigned I = 1; I != NumSpecializations; ++I) { 1984 FunctionTemplateDecl *Challenger = Specializations[I]->getPrimaryTemplate(); 1985 assert(Challenger && "Not a function template specialization?"); 1986 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 1987 TPOC), 1988 Challenger)) { 1989 Best = I; 1990 BestTemplate = Challenger; 1991 } 1992 } 1993 1994 // Make sure that the "best" function template is more specialized than all 1995 // of the others. 1996 bool Ambiguous = false; 1997 for (unsigned I = 0; I != NumSpecializations; ++I) { 1998 FunctionTemplateDecl *Challenger = Specializations[I]->getPrimaryTemplate(); 1999 if (I != Best && 2000 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 2001 TPOC), 2002 BestTemplate)) { 2003 Ambiguous = true; 2004 break; 2005 } 2006 } 2007 2008 if (!Ambiguous) { 2009 // We found an answer. Return it. 2010 if (Index) 2011 *Index = Best; 2012 return Specializations[Best]; 2013 } 2014 2015 // Diagnose the ambiguity. 2016 Diag(Loc, AmbigDiag); 2017 2018 // FIXME: Can we order the candidates in some sane way? 2019 for (unsigned I = 0; I != NumSpecializations; ++I) 2020 Diag(Specializations[I]->getLocation(), CandidateDiag) 2021 << getTemplateArgumentBindingsText( 2022 Specializations[I]->getPrimaryTemplate()->getTemplateParameters(), 2023 *Specializations[I]->getTemplateSpecializationArgs()); 2024 2025 return 0; 2026} 2027 2028/// \brief Returns the more specialized class template partial specialization 2029/// according to the rules of partial ordering of class template partial 2030/// specializations (C++ [temp.class.order]). 2031/// 2032/// \param PS1 the first class template partial specialization 2033/// 2034/// \param PS2 the second class template partial specialization 2035/// 2036/// \returns the more specialized class template partial specialization. If 2037/// neither partial specialization is more specialized, returns NULL. 2038ClassTemplatePartialSpecializationDecl * 2039Sema::getMoreSpecializedPartialSpecialization( 2040 ClassTemplatePartialSpecializationDecl *PS1, 2041 ClassTemplatePartialSpecializationDecl *PS2) { 2042 // C++ [temp.class.order]p1: 2043 // For two class template partial specializations, the first is at least as 2044 // specialized as the second if, given the following rewrite to two 2045 // function templates, the first function template is at least as 2046 // specialized as the second according to the ordering rules for function 2047 // templates (14.6.6.2): 2048 // - the first function template has the same template parameters as the 2049 // first partial specialization and has a single function parameter 2050 // whose type is a class template specialization with the template 2051 // arguments of the first partial specialization, and 2052 // - the second function template has the same template parameters as the 2053 // second partial specialization and has a single function parameter 2054 // whose type is a class template specialization with the template 2055 // arguments of the second partial specialization. 2056 // 2057 // Rather than synthesize function templates, we merely perform the 2058 // equivalent partial ordering by performing deduction directly on the 2059 // template arguments of the class template partial specializations. This 2060 // computation is slightly simpler than the general problem of function 2061 // template partial ordering, because class template partial specializations 2062 // are more constrained. We know that every template parameter is deduc 2063 llvm::SmallVector<TemplateArgument, 4> Deduced; 2064 Sema::TemplateDeductionInfo Info(Context); 2065 2066 // Determine whether PS1 is at least as specialized as PS2 2067 Deduced.resize(PS2->getTemplateParameters()->size()); 2068 bool Better1 = !DeduceTemplateArgumentsDuringPartialOrdering(Context, 2069 PS2->getTemplateParameters(), 2070 Context.getTypeDeclType(PS2), 2071 Context.getTypeDeclType(PS1), 2072 Info, 2073 Deduced, 2074 0); 2075 2076 // Determine whether PS2 is at least as specialized as PS1 2077 Deduced.resize(PS1->getTemplateParameters()->size()); 2078 bool Better2 = !DeduceTemplateArgumentsDuringPartialOrdering(Context, 2079 PS1->getTemplateParameters(), 2080 Context.getTypeDeclType(PS1), 2081 Context.getTypeDeclType(PS2), 2082 Info, 2083 Deduced, 2084 0); 2085 2086 if (Better1 == Better2) 2087 return 0; 2088 2089 return Better1? PS1 : PS2; 2090} 2091 2092static void 2093MarkUsedTemplateParameters(Sema &SemaRef, 2094 const TemplateArgument &TemplateArg, 2095 bool OnlyDeduced, 2096 unsigned Depth, 2097 llvm::SmallVectorImpl<bool> &Used); 2098 2099/// \brief Mark the template parameters that are used by the given 2100/// expression. 2101static void 2102MarkUsedTemplateParameters(Sema &SemaRef, 2103 const Expr *E, 2104 bool OnlyDeduced, 2105 unsigned Depth, 2106 llvm::SmallVectorImpl<bool> &Used) { 2107 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to 2108 // find other occurrences of template parameters. 2109 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E); 2110 if (!E) 2111 return; 2112 2113 const NonTypeTemplateParmDecl *NTTP 2114 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 2115 if (!NTTP) 2116 return; 2117 2118 if (NTTP->getDepth() == Depth) 2119 Used[NTTP->getIndex()] = true; 2120} 2121 2122/// \brief Mark the template parameters that are used by the given 2123/// nested name specifier. 2124static void 2125MarkUsedTemplateParameters(Sema &SemaRef, 2126 NestedNameSpecifier *NNS, 2127 bool OnlyDeduced, 2128 unsigned Depth, 2129 llvm::SmallVectorImpl<bool> &Used) { 2130 if (!NNS) 2131 return; 2132 2133 MarkUsedTemplateParameters(SemaRef, NNS->getPrefix(), OnlyDeduced, Depth, 2134 Used); 2135 MarkUsedTemplateParameters(SemaRef, QualType(NNS->getAsType(), 0), 2136 OnlyDeduced, Depth, Used); 2137} 2138 2139/// \brief Mark the template parameters that are used by the given 2140/// template name. 2141static void 2142MarkUsedTemplateParameters(Sema &SemaRef, 2143 TemplateName Name, 2144 bool OnlyDeduced, 2145 unsigned Depth, 2146 llvm::SmallVectorImpl<bool> &Used) { 2147 if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 2148 if (TemplateTemplateParmDecl *TTP 2149 = dyn_cast<TemplateTemplateParmDecl>(Template)) { 2150 if (TTP->getDepth() == Depth) 2151 Used[TTP->getIndex()] = true; 2152 } 2153 return; 2154 } 2155 2156 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 2157 MarkUsedTemplateParameters(SemaRef, DTN->getQualifier(), OnlyDeduced, 2158 Depth, Used); 2159} 2160 2161/// \brief Mark the template parameters that are used by the given 2162/// type. 2163static void 2164MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 2165 bool OnlyDeduced, 2166 unsigned Depth, 2167 llvm::SmallVectorImpl<bool> &Used) { 2168 if (T.isNull()) 2169 return; 2170 2171 // Non-dependent types have nothing deducible 2172 if (!T->isDependentType()) 2173 return; 2174 2175 T = SemaRef.Context.getCanonicalType(T); 2176 switch (T->getTypeClass()) { 2177 case Type::Pointer: 2178 MarkUsedTemplateParameters(SemaRef, 2179 cast<PointerType>(T)->getPointeeType(), 2180 OnlyDeduced, 2181 Depth, 2182 Used); 2183 break; 2184 2185 case Type::BlockPointer: 2186 MarkUsedTemplateParameters(SemaRef, 2187 cast<BlockPointerType>(T)->getPointeeType(), 2188 OnlyDeduced, 2189 Depth, 2190 Used); 2191 break; 2192 2193 case Type::LValueReference: 2194 case Type::RValueReference: 2195 MarkUsedTemplateParameters(SemaRef, 2196 cast<ReferenceType>(T)->getPointeeType(), 2197 OnlyDeduced, 2198 Depth, 2199 Used); 2200 break; 2201 2202 case Type::MemberPointer: { 2203 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 2204 MarkUsedTemplateParameters(SemaRef, MemPtr->getPointeeType(), OnlyDeduced, 2205 Depth, Used); 2206 MarkUsedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0), 2207 OnlyDeduced, Depth, Used); 2208 break; 2209 } 2210 2211 case Type::DependentSizedArray: 2212 MarkUsedTemplateParameters(SemaRef, 2213 cast<DependentSizedArrayType>(T)->getSizeExpr(), 2214 OnlyDeduced, Depth, Used); 2215 // Fall through to check the element type 2216 2217 case Type::ConstantArray: 2218 case Type::IncompleteArray: 2219 MarkUsedTemplateParameters(SemaRef, 2220 cast<ArrayType>(T)->getElementType(), 2221 OnlyDeduced, Depth, Used); 2222 break; 2223 2224 case Type::Vector: 2225 case Type::ExtVector: 2226 MarkUsedTemplateParameters(SemaRef, 2227 cast<VectorType>(T)->getElementType(), 2228 OnlyDeduced, Depth, Used); 2229 break; 2230 2231 case Type::DependentSizedExtVector: { 2232 const DependentSizedExtVectorType *VecType 2233 = cast<DependentSizedExtVectorType>(T); 2234 MarkUsedTemplateParameters(SemaRef, VecType->getElementType(), OnlyDeduced, 2235 Depth, Used); 2236 MarkUsedTemplateParameters(SemaRef, VecType->getSizeExpr(), OnlyDeduced, 2237 Depth, Used); 2238 break; 2239 } 2240 2241 case Type::FunctionProto: { 2242 const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 2243 MarkUsedTemplateParameters(SemaRef, Proto->getResultType(), OnlyDeduced, 2244 Depth, Used); 2245 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I) 2246 MarkUsedTemplateParameters(SemaRef, Proto->getArgType(I), OnlyDeduced, 2247 Depth, Used); 2248 break; 2249 } 2250 2251 case Type::TemplateTypeParm: { 2252 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T); 2253 if (TTP->getDepth() == Depth) 2254 Used[TTP->getIndex()] = true; 2255 break; 2256 } 2257 2258 case Type::TemplateSpecialization: { 2259 const TemplateSpecializationType *Spec 2260 = cast<TemplateSpecializationType>(T); 2261 MarkUsedTemplateParameters(SemaRef, Spec->getTemplateName(), OnlyDeduced, 2262 Depth, Used); 2263 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 2264 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 2265 Used); 2266 break; 2267 } 2268 2269 case Type::Complex: 2270 if (!OnlyDeduced) 2271 MarkUsedTemplateParameters(SemaRef, 2272 cast<ComplexType>(T)->getElementType(), 2273 OnlyDeduced, Depth, Used); 2274 break; 2275 2276 case Type::Typename: 2277 if (!OnlyDeduced) 2278 MarkUsedTemplateParameters(SemaRef, 2279 cast<TypenameType>(T)->getQualifier(), 2280 OnlyDeduced, Depth, Used); 2281 break; 2282 2283 // None of these types have any template parameters in them. 2284 case Type::Builtin: 2285 case Type::FixedWidthInt: 2286 case Type::VariableArray: 2287 case Type::FunctionNoProto: 2288 case Type::Record: 2289 case Type::Enum: 2290 case Type::ObjCInterface: 2291 case Type::ObjCObjectPointer: 2292#define TYPE(Class, Base) 2293#define ABSTRACT_TYPE(Class, Base) 2294#define DEPENDENT_TYPE(Class, Base) 2295#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 2296#include "clang/AST/TypeNodes.def" 2297 break; 2298 } 2299} 2300 2301/// \brief Mark the template parameters that are used by this 2302/// template argument. 2303static void 2304MarkUsedTemplateParameters(Sema &SemaRef, 2305 const TemplateArgument &TemplateArg, 2306 bool OnlyDeduced, 2307 unsigned Depth, 2308 llvm::SmallVectorImpl<bool> &Used) { 2309 switch (TemplateArg.getKind()) { 2310 case TemplateArgument::Null: 2311 case TemplateArgument::Integral: 2312 break; 2313 2314 case TemplateArgument::Type: 2315 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsType(), OnlyDeduced, 2316 Depth, Used); 2317 break; 2318 2319 case TemplateArgument::Declaration: 2320 if (TemplateTemplateParmDecl *TTP 2321 = dyn_cast<TemplateTemplateParmDecl>(TemplateArg.getAsDecl())) { 2322 if (TTP->getDepth() == Depth) 2323 Used[TTP->getIndex()] = true; 2324 } 2325 break; 2326 2327 case TemplateArgument::Expression: 2328 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsExpr(), OnlyDeduced, 2329 Depth, Used); 2330 break; 2331 2332 case TemplateArgument::Pack: 2333 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(), 2334 PEnd = TemplateArg.pack_end(); 2335 P != PEnd; ++P) 2336 MarkUsedTemplateParameters(SemaRef, *P, OnlyDeduced, Depth, Used); 2337 break; 2338 } 2339} 2340 2341/// \brief Mark the template parameters can be deduced by the given 2342/// template argument list. 2343/// 2344/// \param TemplateArgs the template argument list from which template 2345/// parameters will be deduced. 2346/// 2347/// \param Deduced a bit vector whose elements will be set to \c true 2348/// to indicate when the corresponding template parameter will be 2349/// deduced. 2350void 2351Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 2352 bool OnlyDeduced, unsigned Depth, 2353 llvm::SmallVectorImpl<bool> &Used) { 2354 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 2355 ::MarkUsedTemplateParameters(*this, TemplateArgs[I], OnlyDeduced, 2356 Depth, Used); 2357} 2358 2359/// \brief Marks all of the template parameters that will be deduced by a 2360/// call to the given function template. 2361void Sema::MarkDeducedTemplateParameters(FunctionTemplateDecl *FunctionTemplate, 2362 llvm::SmallVectorImpl<bool> &Deduced) { 2363 TemplateParameterList *TemplateParams 2364 = FunctionTemplate->getTemplateParameters(); 2365 Deduced.clear(); 2366 Deduced.resize(TemplateParams->size()); 2367 2368 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2369 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 2370 ::MarkUsedTemplateParameters(*this, Function->getParamDecl(I)->getType(), 2371 true, TemplateParams->getDepth(), Deduced); 2372} 2373