SemaTemplateDeduction.cpp revision 3ddc81456e4ee7e1017f17860053f3eec505a50e
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 Result != Sema::TDK_Inconsistent) { 656 // C++ [temp.deduct.call]p3b3: 657 // If P is a class, and P has the form template-id, then A can be a 658 // derived class of the deduced A. Likewise, if P is a pointer to a 659 // class of the form template-id, A can be a pointer to a derived 660 // class pointed to by the deduced A. 661 // 662 // More importantly: 663 // These alternatives are considered only if type deduction would 664 // otherwise fail. 665 if (const RecordType *RecordT = dyn_cast<RecordType>(Arg)) { 666 // Use data recursion to crawl through the list of base classes. 667 // Visited contains the set of nodes we have already visited, while 668 // ToVisit is our stack of records that we still need to visit. 669 llvm::SmallPtrSet<const RecordType *, 8> Visited; 670 llvm::SmallVector<const RecordType *, 8> ToVisit; 671 ToVisit.push_back(RecordT); 672 bool Successful = false; 673 while (!ToVisit.empty()) { 674 // Retrieve the next class in the inheritance hierarchy. 675 const RecordType *NextT = ToVisit.back(); 676 ToVisit.pop_back(); 677 678 // If we have already seen this type, skip it. 679 if (!Visited.insert(NextT)) 680 continue; 681 682 // If this is a base class, try to perform template argument 683 // deduction from it. 684 if (NextT != RecordT) { 685 Sema::TemplateDeductionResult BaseResult 686 = DeduceTemplateArguments(Context, TemplateParams, SpecParam, 687 QualType(NextT, 0), Info, Deduced); 688 689 // If template argument deduction for this base was successful, 690 // note that we had some success. 691 if (BaseResult == Sema::TDK_Success) 692 Successful = true; 693 // If deduction against this base resulted in an inconsistent 694 // set of deduced template arguments, template argument 695 // deduction fails. 696 else if (BaseResult == Sema::TDK_Inconsistent) 697 return BaseResult; 698 } 699 700 // Visit base classes 701 CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl()); 702 for (CXXRecordDecl::base_class_iterator Base = Next->bases_begin(), 703 BaseEnd = Next->bases_end(); 704 Base != BaseEnd; ++Base) { 705 assert(Base->getType()->isRecordType() && 706 "Base class that isn't a record?"); 707 ToVisit.push_back(Base->getType()->getAs<RecordType>()); 708 } 709 } 710 711 if (Successful) 712 return Sema::TDK_Success; 713 } 714 715 } 716 717 return Result; 718 } 719 720 // T type::* 721 // T T::* 722 // T (type::*)() 723 // type (T::*)() 724 // type (type::*)(T) 725 // type (T::*)(T) 726 // T (type::*)(T) 727 // T (T::*)() 728 // T (T::*)(T) 729 case Type::MemberPointer: { 730 const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param); 731 const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg); 732 if (!MemPtrArg) 733 return Sema::TDK_NonDeducedMismatch; 734 735 if (Sema::TemplateDeductionResult Result 736 = DeduceTemplateArguments(Context, TemplateParams, 737 MemPtrParam->getPointeeType(), 738 MemPtrArg->getPointeeType(), 739 Info, Deduced, 740 TDF & TDF_IgnoreQualifiers)) 741 return Result; 742 743 return DeduceTemplateArguments(Context, TemplateParams, 744 QualType(MemPtrParam->getClass(), 0), 745 QualType(MemPtrArg->getClass(), 0), 746 Info, Deduced, 0); 747 } 748 749 // (clang extension) 750 // 751 // type(^)(T) 752 // T(^)() 753 // T(^)(T) 754 case Type::BlockPointer: { 755 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param); 756 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg); 757 758 if (!BlockPtrArg) 759 return Sema::TDK_NonDeducedMismatch; 760 761 return DeduceTemplateArguments(Context, TemplateParams, 762 BlockPtrParam->getPointeeType(), 763 BlockPtrArg->getPointeeType(), Info, 764 Deduced, 0); 765 } 766 767 case Type::TypeOfExpr: 768 case Type::TypeOf: 769 case Type::Typename: 770 // No template argument deduction for these types 771 return Sema::TDK_Success; 772 773 default: 774 break; 775 } 776 777 // FIXME: Many more cases to go (to go). 778 return Sema::TDK_Success; 779} 780 781static Sema::TemplateDeductionResult 782DeduceTemplateArguments(ASTContext &Context, 783 TemplateParameterList *TemplateParams, 784 const TemplateArgument &Param, 785 const TemplateArgument &Arg, 786 Sema::TemplateDeductionInfo &Info, 787 llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 788 switch (Param.getKind()) { 789 case TemplateArgument::Null: 790 assert(false && "Null template argument in parameter list"); 791 break; 792 793 case TemplateArgument::Type: 794 assert(Arg.getKind() == TemplateArgument::Type && "Type/value mismatch"); 795 return DeduceTemplateArguments(Context, TemplateParams, Param.getAsType(), 796 Arg.getAsType(), Info, Deduced, 0); 797 798 case TemplateArgument::Declaration: 799 // FIXME: Implement this check 800 assert(false && "Unimplemented template argument deduction case"); 801 Info.FirstArg = Param; 802 Info.SecondArg = Arg; 803 return Sema::TDK_NonDeducedMismatch; 804 805 case TemplateArgument::Integral: 806 if (Arg.getKind() == TemplateArgument::Integral) { 807 // FIXME: Zero extension + sign checking here? 808 if (*Param.getAsIntegral() == *Arg.getAsIntegral()) 809 return Sema::TDK_Success; 810 811 Info.FirstArg = Param; 812 Info.SecondArg = Arg; 813 return Sema::TDK_NonDeducedMismatch; 814 } 815 816 if (Arg.getKind() == TemplateArgument::Expression) { 817 Info.FirstArg = Param; 818 Info.SecondArg = Arg; 819 return Sema::TDK_NonDeducedMismatch; 820 } 821 822 assert(false && "Type/value mismatch"); 823 Info.FirstArg = Param; 824 Info.SecondArg = Arg; 825 return Sema::TDK_NonDeducedMismatch; 826 827 case TemplateArgument::Expression: { 828 if (NonTypeTemplateParmDecl *NTTP 829 = getDeducedParameterFromExpr(Param.getAsExpr())) { 830 if (Arg.getKind() == TemplateArgument::Integral) 831 // FIXME: Sign problems here 832 return DeduceNonTypeTemplateArgument(Context, NTTP, 833 *Arg.getAsIntegral(), 834 Info, Deduced); 835 if (Arg.getKind() == TemplateArgument::Expression) 836 return DeduceNonTypeTemplateArgument(Context, NTTP, Arg.getAsExpr(), 837 Info, Deduced); 838 839 assert(false && "Type/value mismatch"); 840 Info.FirstArg = Param; 841 Info.SecondArg = Arg; 842 return Sema::TDK_NonDeducedMismatch; 843 } 844 845 // Can't deduce anything, but that's okay. 846 return Sema::TDK_Success; 847 } 848 case TemplateArgument::Pack: 849 assert(0 && "FIXME: Implement!"); 850 break; 851 } 852 853 return Sema::TDK_Success; 854} 855 856static Sema::TemplateDeductionResult 857DeduceTemplateArguments(ASTContext &Context, 858 TemplateParameterList *TemplateParams, 859 const TemplateArgumentList &ParamList, 860 const TemplateArgumentList &ArgList, 861 Sema::TemplateDeductionInfo &Info, 862 llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 863 assert(ParamList.size() == ArgList.size()); 864 for (unsigned I = 0, N = ParamList.size(); I != N; ++I) { 865 if (Sema::TemplateDeductionResult Result 866 = DeduceTemplateArguments(Context, TemplateParams, 867 ParamList[I], ArgList[I], 868 Info, Deduced)) 869 return Result; 870 } 871 return Sema::TDK_Success; 872} 873 874/// \brief Determine whether two template arguments are the same. 875static bool isSameTemplateArg(ASTContext &Context, 876 const TemplateArgument &X, 877 const TemplateArgument &Y) { 878 if (X.getKind() != Y.getKind()) 879 return false; 880 881 switch (X.getKind()) { 882 case TemplateArgument::Null: 883 assert(false && "Comparing NULL template argument"); 884 break; 885 886 case TemplateArgument::Type: 887 return Context.getCanonicalType(X.getAsType()) == 888 Context.getCanonicalType(Y.getAsType()); 889 890 case TemplateArgument::Declaration: 891 return X.getAsDecl()->getCanonicalDecl() == 892 Y.getAsDecl()->getCanonicalDecl(); 893 894 case TemplateArgument::Integral: 895 return *X.getAsIntegral() == *Y.getAsIntegral(); 896 897 case TemplateArgument::Expression: 898 // FIXME: We assume that all expressions are distinct, but we should 899 // really check their canonical forms. 900 return false; 901 902 case TemplateArgument::Pack: 903 if (X.pack_size() != Y.pack_size()) 904 return false; 905 906 for (TemplateArgument::pack_iterator XP = X.pack_begin(), 907 XPEnd = X.pack_end(), 908 YP = Y.pack_begin(); 909 XP != XPEnd; ++XP, ++YP) 910 if (!isSameTemplateArg(Context, *XP, *YP)) 911 return false; 912 913 return true; 914 } 915 916 return false; 917} 918 919/// \brief Helper function to build a TemplateParameter when we don't 920/// know its type statically. 921static TemplateParameter makeTemplateParameter(Decl *D) { 922 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D)) 923 return TemplateParameter(TTP); 924 else if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) 925 return TemplateParameter(NTTP); 926 927 return TemplateParameter(cast<TemplateTemplateParmDecl>(D)); 928} 929 930/// \brief Perform template argument deduction to determine whether 931/// the given template arguments match the given class template 932/// partial specialization per C++ [temp.class.spec.match]. 933Sema::TemplateDeductionResult 934Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial, 935 const TemplateArgumentList &TemplateArgs, 936 TemplateDeductionInfo &Info) { 937 // C++ [temp.class.spec.match]p2: 938 // A partial specialization matches a given actual template 939 // argument list if the template arguments of the partial 940 // specialization can be deduced from the actual template argument 941 // list (14.8.2). 942 SFINAETrap Trap(*this); 943 llvm::SmallVector<TemplateArgument, 4> Deduced; 944 Deduced.resize(Partial->getTemplateParameters()->size()); 945 if (TemplateDeductionResult Result 946 = ::DeduceTemplateArguments(Context, 947 Partial->getTemplateParameters(), 948 Partial->getTemplateArgs(), 949 TemplateArgs, Info, Deduced)) 950 return Result; 951 952 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial, 953 Deduced.data(), Deduced.size()); 954 if (Inst) 955 return TDK_InstantiationDepth; 956 957 // C++ [temp.deduct.type]p2: 958 // [...] or if any template argument remains neither deduced nor 959 // explicitly specified, template argument deduction fails. 960 TemplateArgumentListBuilder Builder(Partial->getTemplateParameters(), 961 Deduced.size()); 962 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 963 if (Deduced[I].isNull()) { 964 Decl *Param 965 = const_cast<NamedDecl *>( 966 Partial->getTemplateParameters()->getParam(I)); 967 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param)) 968 Info.Param = TTP; 969 else if (NonTypeTemplateParmDecl *NTTP 970 = dyn_cast<NonTypeTemplateParmDecl>(Param)) 971 Info.Param = NTTP; 972 else 973 Info.Param = cast<TemplateTemplateParmDecl>(Param); 974 return TDK_Incomplete; 975 } 976 977 Builder.Append(Deduced[I]); 978 } 979 980 // Form the template argument list from the deduced template arguments. 981 TemplateArgumentList *DeducedArgumentList 982 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true); 983 Info.reset(DeducedArgumentList); 984 985 // Substitute the deduced template arguments into the template 986 // arguments of the class template partial specialization, and 987 // verify that the instantiated template arguments are both valid 988 // and are equivalent to the template arguments originally provided 989 // to the class template. 990 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate(); 991 const TemplateArgumentList &PartialTemplateArgs = Partial->getTemplateArgs(); 992 for (unsigned I = 0, N = PartialTemplateArgs.flat_size(); I != N; ++I) { 993 Decl *Param = const_cast<NamedDecl *>( 994 ClassTemplate->getTemplateParameters()->getParam(I)); 995 TemplateArgument InstArg 996 = Subst(PartialTemplateArgs[I], 997 MultiLevelTemplateArgumentList(*DeducedArgumentList)); 998 if (InstArg.isNull()) { 999 Info.Param = makeTemplateParameter(Param); 1000 Info.FirstArg = PartialTemplateArgs[I]; 1001 return TDK_SubstitutionFailure; 1002 } 1003 1004 if (InstArg.getKind() == TemplateArgument::Expression) { 1005 // When the argument is an expression, check the expression result 1006 // against the actual template parameter to get down to the canonical 1007 // template argument. 1008 Expr *InstExpr = InstArg.getAsExpr(); 1009 if (NonTypeTemplateParmDecl *NTTP 1010 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 1011 if (CheckTemplateArgument(NTTP, NTTP->getType(), InstExpr, InstArg)) { 1012 Info.Param = makeTemplateParameter(Param); 1013 Info.FirstArg = PartialTemplateArgs[I]; 1014 return TDK_SubstitutionFailure; 1015 } 1016 } else if (TemplateTemplateParmDecl *TTP 1017 = dyn_cast<TemplateTemplateParmDecl>(Param)) { 1018 // FIXME: template template arguments should really resolve to decls 1019 DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(InstExpr); 1020 if (!DRE || CheckTemplateArgument(TTP, DRE)) { 1021 Info.Param = makeTemplateParameter(Param); 1022 Info.FirstArg = PartialTemplateArgs[I]; 1023 return TDK_SubstitutionFailure; 1024 } 1025 } 1026 } 1027 1028 if (!isSameTemplateArg(Context, TemplateArgs[I], InstArg)) { 1029 Info.Param = makeTemplateParameter(Param); 1030 Info.FirstArg = TemplateArgs[I]; 1031 Info.SecondArg = InstArg; 1032 return TDK_NonDeducedMismatch; 1033 } 1034 } 1035 1036 if (Trap.hasErrorOccurred()) 1037 return TDK_SubstitutionFailure; 1038 1039 return TDK_Success; 1040} 1041 1042/// \brief Determine whether the given type T is a simple-template-id type. 1043static bool isSimpleTemplateIdType(QualType T) { 1044 if (const TemplateSpecializationType *Spec 1045 = T->getAs<TemplateSpecializationType>()) 1046 return Spec->getTemplateName().getAsTemplateDecl() != 0; 1047 1048 return false; 1049} 1050 1051/// \brief Substitute the explicitly-provided template arguments into the 1052/// given function template according to C++ [temp.arg.explicit]. 1053/// 1054/// \param FunctionTemplate the function template into which the explicit 1055/// template arguments will be substituted. 1056/// 1057/// \param ExplicitTemplateArguments the explicitly-specified template 1058/// arguments. 1059/// 1060/// \param NumExplicitTemplateArguments the number of explicitly-specified 1061/// template arguments in @p ExplicitTemplateArguments. This value may be zero. 1062/// 1063/// \param Deduced the deduced template arguments, which will be populated 1064/// with the converted and checked explicit template arguments. 1065/// 1066/// \param ParamTypes will be populated with the instantiated function 1067/// parameters. 1068/// 1069/// \param FunctionType if non-NULL, the result type of the function template 1070/// will also be instantiated and the pointed-to value will be updated with 1071/// the instantiated function type. 1072/// 1073/// \param Info if substitution fails for any reason, this object will be 1074/// populated with more information about the failure. 1075/// 1076/// \returns TDK_Success if substitution was successful, or some failure 1077/// condition. 1078Sema::TemplateDeductionResult 1079Sema::SubstituteExplicitTemplateArguments( 1080 FunctionTemplateDecl *FunctionTemplate, 1081 const TemplateArgument *ExplicitTemplateArgs, 1082 unsigned NumExplicitTemplateArgs, 1083 llvm::SmallVectorImpl<TemplateArgument> &Deduced, 1084 llvm::SmallVectorImpl<QualType> &ParamTypes, 1085 QualType *FunctionType, 1086 TemplateDeductionInfo &Info) { 1087 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1088 TemplateParameterList *TemplateParams 1089 = FunctionTemplate->getTemplateParameters(); 1090 1091 if (NumExplicitTemplateArgs == 0) { 1092 // No arguments to substitute; just copy over the parameter types and 1093 // fill in the function type. 1094 for (FunctionDecl::param_iterator P = Function->param_begin(), 1095 PEnd = Function->param_end(); 1096 P != PEnd; 1097 ++P) 1098 ParamTypes.push_back((*P)->getType()); 1099 1100 if (FunctionType) 1101 *FunctionType = Function->getType(); 1102 return TDK_Success; 1103 } 1104 1105 // Substitution of the explicit template arguments into a function template 1106 /// is a SFINAE context. Trap any errors that might occur. 1107 SFINAETrap Trap(*this); 1108 1109 // C++ [temp.arg.explicit]p3: 1110 // Template arguments that are present shall be specified in the 1111 // declaration order of their corresponding template-parameters. The 1112 // template argument list shall not specify more template-arguments than 1113 // there are corresponding template-parameters. 1114 TemplateArgumentListBuilder Builder(TemplateParams, 1115 NumExplicitTemplateArgs); 1116 1117 // Enter a new template instantiation context where we check the 1118 // explicitly-specified template arguments against this function template, 1119 // and then substitute them into the function parameter types. 1120 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1121 FunctionTemplate, Deduced.data(), Deduced.size(), 1122 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution); 1123 if (Inst) 1124 return TDK_InstantiationDepth; 1125 1126 if (CheckTemplateArgumentList(FunctionTemplate, 1127 SourceLocation(), SourceLocation(), 1128 ExplicitTemplateArgs, 1129 NumExplicitTemplateArgs, 1130 SourceLocation(), 1131 true, 1132 Builder) || Trap.hasErrorOccurred()) 1133 return TDK_InvalidExplicitArguments; 1134 1135 // Form the template argument list from the explicitly-specified 1136 // template arguments. 1137 TemplateArgumentList *ExplicitArgumentList 1138 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true); 1139 Info.reset(ExplicitArgumentList); 1140 1141 // Instantiate the types of each of the function parameters given the 1142 // explicitly-specified template arguments. 1143 for (FunctionDecl::param_iterator P = Function->param_begin(), 1144 PEnd = Function->param_end(); 1145 P != PEnd; 1146 ++P) { 1147 QualType ParamType 1148 = SubstType((*P)->getType(), 1149 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1150 (*P)->getLocation(), (*P)->getDeclName()); 1151 if (ParamType.isNull() || Trap.hasErrorOccurred()) 1152 return TDK_SubstitutionFailure; 1153 1154 ParamTypes.push_back(ParamType); 1155 } 1156 1157 // If the caller wants a full function type back, instantiate the return 1158 // type and form that function type. 1159 if (FunctionType) { 1160 // FIXME: exception-specifications? 1161 const FunctionProtoType *Proto 1162 = Function->getType()->getAs<FunctionProtoType>(); 1163 assert(Proto && "Function template does not have a prototype?"); 1164 1165 QualType ResultType 1166 = SubstType(Proto->getResultType(), 1167 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1168 Function->getTypeSpecStartLoc(), 1169 Function->getDeclName()); 1170 if (ResultType.isNull() || Trap.hasErrorOccurred()) 1171 return TDK_SubstitutionFailure; 1172 1173 *FunctionType = BuildFunctionType(ResultType, 1174 ParamTypes.data(), ParamTypes.size(), 1175 Proto->isVariadic(), 1176 Proto->getTypeQuals(), 1177 Function->getLocation(), 1178 Function->getDeclName()); 1179 if (FunctionType->isNull() || Trap.hasErrorOccurred()) 1180 return TDK_SubstitutionFailure; 1181 } 1182 1183 // C++ [temp.arg.explicit]p2: 1184 // Trailing template arguments that can be deduced (14.8.2) may be 1185 // omitted from the list of explicit template-arguments. If all of the 1186 // template arguments can be deduced, they may all be omitted; in this 1187 // case, the empty template argument list <> itself may also be omitted. 1188 // 1189 // Take all of the explicitly-specified arguments and put them into the 1190 // set of deduced template arguments. 1191 Deduced.reserve(TemplateParams->size()); 1192 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) 1193 Deduced.push_back(ExplicitArgumentList->get(I)); 1194 1195 return TDK_Success; 1196} 1197 1198/// \brief Finish template argument deduction for a function template, 1199/// checking the deduced template arguments for completeness and forming 1200/// the function template specialization. 1201Sema::TemplateDeductionResult 1202Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate, 1203 llvm::SmallVectorImpl<TemplateArgument> &Deduced, 1204 FunctionDecl *&Specialization, 1205 TemplateDeductionInfo &Info) { 1206 TemplateParameterList *TemplateParams 1207 = FunctionTemplate->getTemplateParameters(); 1208 1209 // C++ [temp.deduct.type]p2: 1210 // [...] or if any template argument remains neither deduced nor 1211 // explicitly specified, template argument deduction fails. 1212 TemplateArgumentListBuilder Builder(TemplateParams, Deduced.size()); 1213 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 1214 if (Deduced[I].isNull()) { 1215 Info.Param = makeTemplateParameter( 1216 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1217 return TDK_Incomplete; 1218 } 1219 1220 Builder.Append(Deduced[I]); 1221 } 1222 1223 // Form the template argument list from the deduced template arguments. 1224 TemplateArgumentList *DeducedArgumentList 1225 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true); 1226 Info.reset(DeducedArgumentList); 1227 1228 // Template argument deduction for function templates in a SFINAE context. 1229 // Trap any errors that might occur. 1230 SFINAETrap Trap(*this); 1231 1232 // Enter a new template instantiation context while we instantiate the 1233 // actual function declaration. 1234 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1235 FunctionTemplate, Deduced.data(), Deduced.size(), 1236 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution); 1237 if (Inst) 1238 return TDK_InstantiationDepth; 1239 1240 // Substitute the deduced template arguments into the function template 1241 // declaration to produce the function template specialization. 1242 Specialization = cast_or_null<FunctionDecl>( 1243 SubstDecl(FunctionTemplate->getTemplatedDecl(), 1244 FunctionTemplate->getDeclContext(), 1245 MultiLevelTemplateArgumentList(*DeducedArgumentList))); 1246 if (!Specialization) 1247 return TDK_SubstitutionFailure; 1248 1249 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() == 1250 FunctionTemplate->getCanonicalDecl()); 1251 1252 // If the template argument list is owned by the function template 1253 // specialization, release it. 1254 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList) 1255 Info.take(); 1256 1257 // There may have been an error that did not prevent us from constructing a 1258 // declaration. Mark the declaration invalid and return with a substitution 1259 // failure. 1260 if (Trap.hasErrorOccurred()) { 1261 Specialization->setInvalidDecl(true); 1262 return TDK_SubstitutionFailure; 1263 } 1264 1265 return TDK_Success; 1266} 1267 1268/// \brief Perform template argument deduction from a function call 1269/// (C++ [temp.deduct.call]). 1270/// 1271/// \param FunctionTemplate the function template for which we are performing 1272/// template argument deduction. 1273/// 1274/// \param HasExplicitTemplateArgs whether any template arguments were 1275/// explicitly specified. 1276/// 1277/// \param ExplicitTemplateArguments when @p HasExplicitTemplateArgs is true, 1278/// the explicitly-specified template arguments. 1279/// 1280/// \param NumExplicitTemplateArguments when @p HasExplicitTemplateArgs is true, 1281/// the number of explicitly-specified template arguments in 1282/// @p ExplicitTemplateArguments. This value may be zero. 1283/// 1284/// \param Args the function call arguments 1285/// 1286/// \param NumArgs the number of arguments in Args 1287/// 1288/// \param Specialization if template argument deduction was successful, 1289/// this will be set to the function template specialization produced by 1290/// template argument deduction. 1291/// 1292/// \param Info the argument will be updated to provide additional information 1293/// about template argument deduction. 1294/// 1295/// \returns the result of template argument deduction. 1296Sema::TemplateDeductionResult 1297Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1298 bool HasExplicitTemplateArgs, 1299 const TemplateArgument *ExplicitTemplateArgs, 1300 unsigned NumExplicitTemplateArgs, 1301 Expr **Args, unsigned NumArgs, 1302 FunctionDecl *&Specialization, 1303 TemplateDeductionInfo &Info) { 1304 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1305 1306 // C++ [temp.deduct.call]p1: 1307 // Template argument deduction is done by comparing each function template 1308 // parameter type (call it P) with the type of the corresponding argument 1309 // of the call (call it A) as described below. 1310 unsigned CheckArgs = NumArgs; 1311 if (NumArgs < Function->getMinRequiredArguments()) 1312 return TDK_TooFewArguments; 1313 else if (NumArgs > Function->getNumParams()) { 1314 const FunctionProtoType *Proto 1315 = Function->getType()->getAs<FunctionProtoType>(); 1316 if (!Proto->isVariadic()) 1317 return TDK_TooManyArguments; 1318 1319 CheckArgs = Function->getNumParams(); 1320 } 1321 1322 // The types of the parameters from which we will perform template argument 1323 // deduction. 1324 TemplateParameterList *TemplateParams 1325 = FunctionTemplate->getTemplateParameters(); 1326 llvm::SmallVector<TemplateArgument, 4> Deduced; 1327 llvm::SmallVector<QualType, 4> ParamTypes; 1328 if (NumExplicitTemplateArgs) { 1329 TemplateDeductionResult Result = 1330 SubstituteExplicitTemplateArguments(FunctionTemplate, 1331 ExplicitTemplateArgs, 1332 NumExplicitTemplateArgs, 1333 Deduced, 1334 ParamTypes, 1335 0, 1336 Info); 1337 if (Result) 1338 return Result; 1339 } else { 1340 // Just fill in the parameter types from the function declaration. 1341 for (unsigned I = 0; I != CheckArgs; ++I) 1342 ParamTypes.push_back(Function->getParamDecl(I)->getType()); 1343 } 1344 1345 // Deduce template arguments from the function parameters. 1346 Deduced.resize(TemplateParams->size()); 1347 for (unsigned I = 0; I != CheckArgs; ++I) { 1348 QualType ParamType = ParamTypes[I]; 1349 QualType ArgType = Args[I]->getType(); 1350 1351 // C++ [temp.deduct.call]p2: 1352 // If P is not a reference type: 1353 QualType CanonParamType = Context.getCanonicalType(ParamType); 1354 bool ParamWasReference = isa<ReferenceType>(CanonParamType); 1355 if (!ParamWasReference) { 1356 // - If A is an array type, the pointer type produced by the 1357 // array-to-pointer standard conversion (4.2) is used in place of 1358 // A for type deduction; otherwise, 1359 if (ArgType->isArrayType()) 1360 ArgType = Context.getArrayDecayedType(ArgType); 1361 // - If A is a function type, the pointer type produced by the 1362 // function-to-pointer standard conversion (4.3) is used in place 1363 // of A for type deduction; otherwise, 1364 else if (ArgType->isFunctionType()) 1365 ArgType = Context.getPointerType(ArgType); 1366 else { 1367 // - If A is a cv-qualified type, the top level cv-qualifiers of A’s 1368 // type are ignored for type deduction. 1369 QualType CanonArgType = Context.getCanonicalType(ArgType); 1370 if (CanonArgType.getCVRQualifiers()) 1371 ArgType = CanonArgType.getUnqualifiedType(); 1372 } 1373 } 1374 1375 // C++0x [temp.deduct.call]p3: 1376 // If P is a cv-qualified type, the top level cv-qualifiers of P’s type 1377 // are ignored for type deduction. 1378 if (CanonParamType.getCVRQualifiers()) 1379 ParamType = CanonParamType.getUnqualifiedType(); 1380 if (const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>()) { 1381 // [...] If P is a reference type, the type referred to by P is used 1382 // for type deduction. 1383 ParamType = ParamRefType->getPointeeType(); 1384 1385 // [...] If P is of the form T&&, where T is a template parameter, and 1386 // the argument is an lvalue, the type A& is used in place of A for 1387 // type deduction. 1388 if (isa<RValueReferenceType>(ParamRefType) && 1389 ParamRefType->getAs<TemplateTypeParmType>() && 1390 Args[I]->isLvalue(Context) == Expr::LV_Valid) 1391 ArgType = Context.getLValueReferenceType(ArgType); 1392 } 1393 1394 // C++0x [temp.deduct.call]p4: 1395 // In general, the deduction process attempts to find template argument 1396 // values that will make the deduced A identical to A (after the type A 1397 // is transformed as described above). [...] 1398 unsigned TDF = TDF_SkipNonDependent; 1399 1400 // - If the original P is a reference type, the deduced A (i.e., the 1401 // type referred to by the reference) can be more cv-qualified than 1402 // the transformed A. 1403 if (ParamWasReference) 1404 TDF |= TDF_ParamWithReferenceType; 1405 // - The transformed A can be another pointer or pointer to member 1406 // type that can be converted to the deduced A via a qualification 1407 // conversion (4.4). 1408 if (ArgType->isPointerType() || ArgType->isMemberPointerType()) 1409 TDF |= TDF_IgnoreQualifiers; 1410 // - If P is a class and P has the form simple-template-id, then the 1411 // transformed A can be a derived class of the deduced A. Likewise, 1412 // if P is a pointer to a class of the form simple-template-id, the 1413 // transformed A can be a pointer to a derived class pointed to by 1414 // the deduced A. 1415 if (isSimpleTemplateIdType(ParamType) || 1416 (isa<PointerType>(ParamType) && 1417 isSimpleTemplateIdType( 1418 ParamType->getAs<PointerType>()->getPointeeType()))) 1419 TDF |= TDF_DerivedClass; 1420 1421 if (TemplateDeductionResult Result 1422 = ::DeduceTemplateArguments(Context, TemplateParams, 1423 ParamType, ArgType, Info, Deduced, 1424 TDF)) 1425 return Result; 1426 1427 // FIXME: C++0x [temp.deduct.call] paragraphs 6-9 deal with function 1428 // pointer parameters. 1429 1430 // FIXME: we need to check that the deduced A is the same as A, 1431 // modulo the various allowed differences. 1432 } 1433 1434 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 1435 Specialization, Info); 1436} 1437 1438/// \brief Deduce template arguments when taking the address of a function 1439/// template (C++ [temp.deduct.funcaddr]). 1440/// 1441/// \param FunctionTemplate the function template for which we are performing 1442/// template argument deduction. 1443/// 1444/// \param HasExplicitTemplateArgs whether any template arguments were 1445/// explicitly specified. 1446/// 1447/// \param ExplicitTemplateArguments when @p HasExplicitTemplateArgs is true, 1448/// the explicitly-specified template arguments. 1449/// 1450/// \param NumExplicitTemplateArguments when @p HasExplicitTemplateArgs is true, 1451/// the number of explicitly-specified template arguments in 1452/// @p ExplicitTemplateArguments. This value may be zero. 1453/// 1454/// \param ArgFunctionType the function type that will be used as the 1455/// "argument" type (A) when performing template argument deduction from the 1456/// function template's function type. 1457/// 1458/// \param Specialization if template argument deduction was successful, 1459/// this will be set to the function template specialization produced by 1460/// template argument deduction. 1461/// 1462/// \param Info the argument will be updated to provide additional information 1463/// about template argument deduction. 1464/// 1465/// \returns the result of template argument deduction. 1466Sema::TemplateDeductionResult 1467Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1468 bool HasExplicitTemplateArgs, 1469 const TemplateArgument *ExplicitTemplateArgs, 1470 unsigned NumExplicitTemplateArgs, 1471 QualType ArgFunctionType, 1472 FunctionDecl *&Specialization, 1473 TemplateDeductionInfo &Info) { 1474 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1475 TemplateParameterList *TemplateParams 1476 = FunctionTemplate->getTemplateParameters(); 1477 QualType FunctionType = Function->getType(); 1478 1479 // Substitute any explicit template arguments. 1480 llvm::SmallVector<TemplateArgument, 4> Deduced; 1481 llvm::SmallVector<QualType, 4> ParamTypes; 1482 if (HasExplicitTemplateArgs) { 1483 if (TemplateDeductionResult Result 1484 = SubstituteExplicitTemplateArguments(FunctionTemplate, 1485 ExplicitTemplateArgs, 1486 NumExplicitTemplateArgs, 1487 Deduced, ParamTypes, 1488 &FunctionType, Info)) 1489 return Result; 1490 } 1491 1492 // Template argument deduction for function templates in a SFINAE context. 1493 // Trap any errors that might occur. 1494 SFINAETrap Trap(*this); 1495 1496 // Deduce template arguments from the function type. 1497 Deduced.resize(TemplateParams->size()); 1498 if (TemplateDeductionResult Result 1499 = ::DeduceTemplateArguments(Context, TemplateParams, 1500 FunctionType, ArgFunctionType, Info, 1501 Deduced, 0)) 1502 return Result; 1503 1504 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 1505 Specialization, Info); 1506} 1507 1508/// \brief Deduce template arguments for a templated conversion 1509/// function (C++ [temp.deduct.conv]) and, if successful, produce a 1510/// conversion function template specialization. 1511Sema::TemplateDeductionResult 1512Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1513 QualType ToType, 1514 CXXConversionDecl *&Specialization, 1515 TemplateDeductionInfo &Info) { 1516 CXXConversionDecl *Conv 1517 = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl()); 1518 QualType FromType = Conv->getConversionType(); 1519 1520 // Canonicalize the types for deduction. 1521 QualType P = Context.getCanonicalType(FromType); 1522 QualType A = Context.getCanonicalType(ToType); 1523 1524 // C++0x [temp.deduct.conv]p3: 1525 // If P is a reference type, the type referred to by P is used for 1526 // type deduction. 1527 if (const ReferenceType *PRef = P->getAs<ReferenceType>()) 1528 P = PRef->getPointeeType(); 1529 1530 // C++0x [temp.deduct.conv]p3: 1531 // If A is a reference type, the type referred to by A is used 1532 // for type deduction. 1533 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 1534 A = ARef->getPointeeType(); 1535 // C++ [temp.deduct.conv]p2: 1536 // 1537 // If A is not a reference type: 1538 else { 1539 assert(!A->isReferenceType() && "Reference types were handled above"); 1540 1541 // - If P is an array type, the pointer type produced by the 1542 // array-to-pointer standard conversion (4.2) is used in place 1543 // of P for type deduction; otherwise, 1544 if (P->isArrayType()) 1545 P = Context.getArrayDecayedType(P); 1546 // - If P is a function type, the pointer type produced by the 1547 // function-to-pointer standard conversion (4.3) is used in 1548 // place of P for type deduction; otherwise, 1549 else if (P->isFunctionType()) 1550 P = Context.getPointerType(P); 1551 // - If P is a cv-qualified type, the top level cv-qualifiers of 1552 // P’s type are ignored for type deduction. 1553 else 1554 P = P.getUnqualifiedType(); 1555 1556 // C++0x [temp.deduct.conv]p3: 1557 // If A is a cv-qualified type, the top level cv-qualifiers of A’s 1558 // type are ignored for type deduction. 1559 A = A.getUnqualifiedType(); 1560 } 1561 1562 // Template argument deduction for function templates in a SFINAE context. 1563 // Trap any errors that might occur. 1564 SFINAETrap Trap(*this); 1565 1566 // C++ [temp.deduct.conv]p1: 1567 // Template argument deduction is done by comparing the return 1568 // type of the template conversion function (call it P) with the 1569 // type that is required as the result of the conversion (call it 1570 // A) as described in 14.8.2.4. 1571 TemplateParameterList *TemplateParams 1572 = FunctionTemplate->getTemplateParameters(); 1573 llvm::SmallVector<TemplateArgument, 4> Deduced; 1574 Deduced.resize(TemplateParams->size()); 1575 1576 // C++0x [temp.deduct.conv]p4: 1577 // In general, the deduction process attempts to find template 1578 // argument values that will make the deduced A identical to 1579 // A. However, there are two cases that allow a difference: 1580 unsigned TDF = 0; 1581 // - If the original A is a reference type, A can be more 1582 // cv-qualified than the deduced A (i.e., the type referred to 1583 // by the reference) 1584 if (ToType->isReferenceType()) 1585 TDF |= TDF_ParamWithReferenceType; 1586 // - The deduced A can be another pointer or pointer to member 1587 // type that can be converted to A via a qualification 1588 // conversion. 1589 // 1590 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 1591 // both P and A are pointers or member pointers. In this case, we 1592 // just ignore cv-qualifiers completely). 1593 if ((P->isPointerType() && A->isPointerType()) || 1594 (P->isMemberPointerType() && P->isMemberPointerType())) 1595 TDF |= TDF_IgnoreQualifiers; 1596 if (TemplateDeductionResult Result 1597 = ::DeduceTemplateArguments(Context, TemplateParams, 1598 P, A, Info, Deduced, TDF)) 1599 return Result; 1600 1601 // FIXME: we need to check that the deduced A is the same as A, 1602 // modulo the various allowed differences. 1603 1604 // Finish template argument deduction. 1605 FunctionDecl *Spec = 0; 1606 TemplateDeductionResult Result 1607 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, Spec, Info); 1608 Specialization = cast_or_null<CXXConversionDecl>(Spec); 1609 return Result; 1610} 1611 1612/// \brief Stores the result of comparing the qualifiers of two types. 1613enum DeductionQualifierComparison { 1614 NeitherMoreQualified = 0, 1615 ParamMoreQualified, 1616 ArgMoreQualified 1617}; 1618 1619/// \brief Deduce the template arguments during partial ordering by comparing 1620/// the parameter type and the argument type (C++0x [temp.deduct.partial]). 1621/// 1622/// \param Context the AST context in which this deduction occurs. 1623/// 1624/// \param TemplateParams the template parameters that we are deducing 1625/// 1626/// \param ParamIn the parameter type 1627/// 1628/// \param ArgIn the argument type 1629/// 1630/// \param Info information about the template argument deduction itself 1631/// 1632/// \param Deduced the deduced template arguments 1633/// 1634/// \returns the result of template argument deduction so far. Note that a 1635/// "success" result means that template argument deduction has not yet failed, 1636/// but it may still fail, later, for other reasons. 1637static Sema::TemplateDeductionResult 1638DeduceTemplateArgumentsDuringPartialOrdering(ASTContext &Context, 1639 TemplateParameterList *TemplateParams, 1640 QualType ParamIn, QualType ArgIn, 1641 Sema::TemplateDeductionInfo &Info, 1642 llvm::SmallVectorImpl<TemplateArgument> &Deduced, 1643 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 1644 CanQualType Param = Context.getCanonicalType(ParamIn); 1645 CanQualType Arg = Context.getCanonicalType(ArgIn); 1646 1647 // C++0x [temp.deduct.partial]p5: 1648 // Before the partial ordering is done, certain transformations are 1649 // performed on the types used for partial ordering: 1650 // - If P is a reference type, P is replaced by the type referred to. 1651 CanQual<ReferenceType> ParamRef = Param->getAs<ReferenceType>(); 1652 if (ParamRef) 1653 Param = ParamRef->getPointeeType(); 1654 1655 // - If A is a reference type, A is replaced by the type referred to. 1656 CanQual<ReferenceType> ArgRef = Arg->getAs<ReferenceType>(); 1657 if (ArgRef) 1658 Arg = ArgRef->getPointeeType(); 1659 1660 if (QualifierComparisons && ParamRef && ArgRef) { 1661 // C++0x [temp.deduct.partial]p6: 1662 // If both P and A were reference types (before being replaced with the 1663 // type referred to above), determine which of the two types (if any) is 1664 // more cv-qualified than the other; otherwise the types are considered to 1665 // be equally cv-qualified for partial ordering purposes. The result of this 1666 // determination will be used below. 1667 // 1668 // We save this information for later, using it only when deduction 1669 // succeeds in both directions. 1670 DeductionQualifierComparison QualifierResult = NeitherMoreQualified; 1671 if (Param.isMoreQualifiedThan(Arg)) 1672 QualifierResult = ParamMoreQualified; 1673 else if (Arg.isMoreQualifiedThan(Param)) 1674 QualifierResult = ArgMoreQualified; 1675 QualifierComparisons->push_back(QualifierResult); 1676 } 1677 1678 // C++0x [temp.deduct.partial]p7: 1679 // Remove any top-level cv-qualifiers: 1680 // - If P is a cv-qualified type, P is replaced by the cv-unqualified 1681 // version of P. 1682 Param = Param.getUnqualifiedType(); 1683 // - If A is a cv-qualified type, A is replaced by the cv-unqualified 1684 // version of A. 1685 Arg = Arg.getUnqualifiedType(); 1686 1687 // C++0x [temp.deduct.partial]p8: 1688 // Using the resulting types P and A the deduction is then done as 1689 // described in 14.9.2.5. If deduction succeeds for a given type, the type 1690 // from the argument template is considered to be at least as specialized 1691 // as the type from the parameter template. 1692 return DeduceTemplateArguments(Context, TemplateParams, Param, Arg, Info, 1693 Deduced, TDF_None); 1694} 1695 1696static void 1697MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 1698 bool OnlyDeduced, 1699 llvm::SmallVectorImpl<bool> &Deduced); 1700 1701/// \brief Determine whether the function template \p FT1 is at least as 1702/// specialized as \p FT2. 1703static bool isAtLeastAsSpecializedAs(Sema &S, 1704 FunctionTemplateDecl *FT1, 1705 FunctionTemplateDecl *FT2, 1706 TemplatePartialOrderingContext TPOC, 1707 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 1708 FunctionDecl *FD1 = FT1->getTemplatedDecl(); 1709 FunctionDecl *FD2 = FT2->getTemplatedDecl(); 1710 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 1711 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 1712 1713 assert(Proto1 && Proto2 && "Function templates must have prototypes"); 1714 TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 1715 llvm::SmallVector<TemplateArgument, 4> Deduced; 1716 Deduced.resize(TemplateParams->size()); 1717 1718 // C++0x [temp.deduct.partial]p3: 1719 // The types used to determine the ordering depend on the context in which 1720 // the partial ordering is done: 1721 Sema::TemplateDeductionInfo Info(S.Context); 1722 switch (TPOC) { 1723 case TPOC_Call: { 1724 // - In the context of a function call, the function parameter types are 1725 // used. 1726 unsigned NumParams = std::min(Proto1->getNumArgs(), Proto2->getNumArgs()); 1727 for (unsigned I = 0; I != NumParams; ++I) 1728 if (DeduceTemplateArgumentsDuringPartialOrdering(S.Context, 1729 TemplateParams, 1730 Proto2->getArgType(I), 1731 Proto1->getArgType(I), 1732 Info, 1733 Deduced, 1734 QualifierComparisons)) 1735 return false; 1736 1737 break; 1738 } 1739 1740 case TPOC_Conversion: 1741 // - In the context of a call to a conversion operator, the return types 1742 // of the conversion function templates are used. 1743 if (DeduceTemplateArgumentsDuringPartialOrdering(S.Context, 1744 TemplateParams, 1745 Proto2->getResultType(), 1746 Proto1->getResultType(), 1747 Info, 1748 Deduced, 1749 QualifierComparisons)) 1750 return false; 1751 break; 1752 1753 case TPOC_Other: 1754 // - In other contexts (14.6.6.2) the function template’s function type 1755 // is used. 1756 if (DeduceTemplateArgumentsDuringPartialOrdering(S.Context, 1757 TemplateParams, 1758 FD2->getType(), 1759 FD1->getType(), 1760 Info, 1761 Deduced, 1762 QualifierComparisons)) 1763 return false; 1764 break; 1765 } 1766 1767 // C++0x [temp.deduct.partial]p11: 1768 // In most cases, all template parameters must have values in order for 1769 // deduction to succeed, but for partial ordering purposes a template 1770 // parameter may remain without a value provided it is not used in the 1771 // types being used for partial ordering. [ Note: a template parameter used 1772 // in a non-deduced context is considered used. -end note] 1773 unsigned ArgIdx = 0, NumArgs = Deduced.size(); 1774 for (; ArgIdx != NumArgs; ++ArgIdx) 1775 if (Deduced[ArgIdx].isNull()) 1776 break; 1777 1778 if (ArgIdx == NumArgs) { 1779 // All template arguments were deduced. FT1 is at least as specialized 1780 // as FT2. 1781 return true; 1782 } 1783 1784 // Figure out which template parameters were used. 1785 llvm::SmallVector<bool, 4> UsedParameters; 1786 UsedParameters.resize(TemplateParams->size()); 1787 switch (TPOC) { 1788 case TPOC_Call: { 1789 unsigned NumParams = std::min(Proto1->getNumArgs(), Proto2->getNumArgs()); 1790 for (unsigned I = 0; I != NumParams; ++I) 1791 ::MarkUsedTemplateParameters(S, Proto2->getArgType(I), false, 1792 UsedParameters); 1793 break; 1794 } 1795 1796 case TPOC_Conversion: 1797 ::MarkUsedTemplateParameters(S, Proto2->getResultType(), false, 1798 UsedParameters); 1799 break; 1800 1801 case TPOC_Other: 1802 ::MarkUsedTemplateParameters(S, FD2->getType(), false, UsedParameters); 1803 break; 1804 } 1805 1806 for (; ArgIdx != NumArgs; ++ArgIdx) 1807 // If this argument had no value deduced but was used in one of the types 1808 // used for partial ordering, then deduction fails. 1809 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 1810 return false; 1811 1812 return true; 1813} 1814 1815 1816/// \brief Returns the more specialized function template according 1817/// to the rules of function template partial ordering (C++ [temp.func.order]). 1818/// 1819/// \param FT1 the first function template 1820/// 1821/// \param FT2 the second function template 1822/// 1823/// \param TPOC the context in which we are performing partial ordering of 1824/// function templates. 1825/// 1826/// \returns the more specialized function template. If neither 1827/// template is more specialized, returns NULL. 1828FunctionTemplateDecl * 1829Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, 1830 FunctionTemplateDecl *FT2, 1831 TemplatePartialOrderingContext TPOC) { 1832 llvm::SmallVector<DeductionQualifierComparison, 4> QualifierComparisons; 1833 bool Better1 = isAtLeastAsSpecializedAs(*this, FT1, FT2, TPOC, 0); 1834 bool Better2 = isAtLeastAsSpecializedAs(*this, FT2, FT1, TPOC, 1835 &QualifierComparisons); 1836 1837 if (Better1 != Better2) // We have a clear winner 1838 return Better1? FT1 : FT2; 1839 1840 if (!Better1 && !Better2) // Neither is better than the other 1841 return 0; 1842 1843 1844 // C++0x [temp.deduct.partial]p10: 1845 // If for each type being considered a given template is at least as 1846 // specialized for all types and more specialized for some set of types and 1847 // the other template is not more specialized for any types or is not at 1848 // least as specialized for any types, then the given template is more 1849 // specialized than the other template. Otherwise, neither template is more 1850 // specialized than the other. 1851 Better1 = false; 1852 Better2 = false; 1853 for (unsigned I = 0, N = QualifierComparisons.size(); I != N; ++I) { 1854 // C++0x [temp.deduct.partial]p9: 1855 // If, for a given type, deduction succeeds in both directions (i.e., the 1856 // types are identical after the transformations above) and if the type 1857 // from the argument template is more cv-qualified than the type from the 1858 // parameter template (as described above) that type is considered to be 1859 // more specialized than the other. If neither type is more cv-qualified 1860 // than the other then neither type is more specialized than the other. 1861 switch (QualifierComparisons[I]) { 1862 case NeitherMoreQualified: 1863 break; 1864 1865 case ParamMoreQualified: 1866 Better1 = true; 1867 if (Better2) 1868 return 0; 1869 break; 1870 1871 case ArgMoreQualified: 1872 Better2 = true; 1873 if (Better1) 1874 return 0; 1875 break; 1876 } 1877 } 1878 1879 assert(!(Better1 && Better2) && "Should have broken out in the loop above"); 1880 if (Better1) 1881 return FT1; 1882 else if (Better2) 1883 return FT2; 1884 else 1885 return 0; 1886} 1887 1888/// \brief Returns the more specialized class template partial specialization 1889/// according to the rules of partial ordering of class template partial 1890/// specializations (C++ [temp.class.order]). 1891/// 1892/// \param PS1 the first class template partial specialization 1893/// 1894/// \param PS2 the second class template partial specialization 1895/// 1896/// \returns the more specialized class template partial specialization. If 1897/// neither partial specialization is more specialized, returns NULL. 1898ClassTemplatePartialSpecializationDecl * 1899Sema::getMoreSpecializedPartialSpecialization( 1900 ClassTemplatePartialSpecializationDecl *PS1, 1901 ClassTemplatePartialSpecializationDecl *PS2) { 1902 // C++ [temp.class.order]p1: 1903 // For two class template partial specializations, the first is at least as 1904 // specialized as the second if, given the following rewrite to two 1905 // function templates, the first function template is at least as 1906 // specialized as the second according to the ordering rules for function 1907 // templates (14.6.6.2): 1908 // - the first function template has the same template parameters as the 1909 // first partial specialization and has a single function parameter 1910 // whose type is a class template specialization with the template 1911 // arguments of the first partial specialization, and 1912 // - the second function template has the same template parameters as the 1913 // second partial specialization and has a single function parameter 1914 // whose type is a class template specialization with the template 1915 // arguments of the second partial specialization. 1916 // 1917 // Rather than synthesize function templates, we merely perform the 1918 // equivalent partial ordering by performing deduction directly on the 1919 // template arguments of the class template partial specializations. This 1920 // computation is slightly simpler than the general problem of function 1921 // template partial ordering, because class template partial specializations 1922 // are more constrained. We know that every template parameter is deduc 1923 llvm::SmallVector<TemplateArgument, 4> Deduced; 1924 Sema::TemplateDeductionInfo Info(Context); 1925 1926 // Determine whether PS1 is at least as specialized as PS2 1927 Deduced.resize(PS2->getTemplateParameters()->size()); 1928 bool Better1 = !DeduceTemplateArgumentsDuringPartialOrdering(Context, 1929 PS2->getTemplateParameters(), 1930 Context.getTypeDeclType(PS2), 1931 Context.getTypeDeclType(PS1), 1932 Info, 1933 Deduced, 1934 0); 1935 1936 // Determine whether PS2 is at least as specialized as PS1 1937 Deduced.resize(PS1->getTemplateParameters()->size()); 1938 bool Better2 = !DeduceTemplateArgumentsDuringPartialOrdering(Context, 1939 PS1->getTemplateParameters(), 1940 Context.getTypeDeclType(PS1), 1941 Context.getTypeDeclType(PS2), 1942 Info, 1943 Deduced, 1944 0); 1945 1946 if (Better1 == Better2) 1947 return 0; 1948 1949 return Better1? PS1 : PS2; 1950} 1951 1952static void 1953MarkUsedTemplateParameters(Sema &SemaRef, 1954 const TemplateArgument &TemplateArg, 1955 bool OnlyDeduced, 1956 llvm::SmallVectorImpl<bool> &Used); 1957 1958/// \brief Mark the template parameters that are used by the given 1959/// expression. 1960static void 1961MarkUsedTemplateParameters(Sema &SemaRef, 1962 const Expr *E, 1963 bool OnlyDeduced, 1964 llvm::SmallVectorImpl<bool> &Used) { 1965 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to 1966 // find other occurrences of template parameters. 1967 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E); 1968 if (!E) 1969 return; 1970 1971 const NonTypeTemplateParmDecl *NTTP 1972 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 1973 if (!NTTP) 1974 return; 1975 1976 Used[NTTP->getIndex()] = true; 1977} 1978 1979/// \brief Mark the template parameters that are used by the given 1980/// nested name specifier. 1981static void 1982MarkUsedTemplateParameters(Sema &SemaRef, 1983 NestedNameSpecifier *NNS, 1984 bool OnlyDeduced, 1985 llvm::SmallVectorImpl<bool> &Used) { 1986 if (!NNS) 1987 return; 1988 1989 MarkUsedTemplateParameters(SemaRef, NNS->getPrefix(), OnlyDeduced, Used); 1990 MarkUsedTemplateParameters(SemaRef, QualType(NNS->getAsType(), 0), 1991 OnlyDeduced, Used); 1992} 1993 1994/// \brief Mark the template parameters that are used by the given 1995/// template name. 1996static void 1997MarkUsedTemplateParameters(Sema &SemaRef, 1998 TemplateName Name, 1999 bool OnlyDeduced, 2000 llvm::SmallVectorImpl<bool> &Used) { 2001 if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 2002 if (TemplateTemplateParmDecl *TTP 2003 = dyn_cast<TemplateTemplateParmDecl>(Template)) 2004 Used[TTP->getIndex()] = true; 2005 return; 2006 } 2007 2008 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 2009 MarkUsedTemplateParameters(SemaRef, DTN->getQualifier(), OnlyDeduced, Used); 2010} 2011 2012/// \brief Mark the template parameters that are used by the given 2013/// type. 2014static void 2015MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 2016 bool OnlyDeduced, 2017 llvm::SmallVectorImpl<bool> &Used) { 2018 if (T.isNull()) 2019 return; 2020 2021 // Non-dependent types have nothing deducible 2022 if (!T->isDependentType()) 2023 return; 2024 2025 T = SemaRef.Context.getCanonicalType(T); 2026 switch (T->getTypeClass()) { 2027 case Type::Pointer: 2028 MarkUsedTemplateParameters(SemaRef, 2029 cast<PointerType>(T)->getPointeeType(), 2030 OnlyDeduced, 2031 Used); 2032 break; 2033 2034 case Type::BlockPointer: 2035 MarkUsedTemplateParameters(SemaRef, 2036 cast<BlockPointerType>(T)->getPointeeType(), 2037 OnlyDeduced, 2038 Used); 2039 break; 2040 2041 case Type::LValueReference: 2042 case Type::RValueReference: 2043 MarkUsedTemplateParameters(SemaRef, 2044 cast<ReferenceType>(T)->getPointeeType(), 2045 OnlyDeduced, 2046 Used); 2047 break; 2048 2049 case Type::MemberPointer: { 2050 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 2051 MarkUsedTemplateParameters(SemaRef, MemPtr->getPointeeType(), OnlyDeduced, 2052 Used); 2053 MarkUsedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0), 2054 OnlyDeduced, Used); 2055 break; 2056 } 2057 2058 case Type::DependentSizedArray: 2059 MarkUsedTemplateParameters(SemaRef, 2060 cast<DependentSizedArrayType>(T)->getSizeExpr(), 2061 OnlyDeduced, Used); 2062 // Fall through to check the element type 2063 2064 case Type::ConstantArray: 2065 case Type::IncompleteArray: 2066 MarkUsedTemplateParameters(SemaRef, 2067 cast<ArrayType>(T)->getElementType(), 2068 OnlyDeduced, Used); 2069 break; 2070 2071 case Type::Vector: 2072 case Type::ExtVector: 2073 MarkUsedTemplateParameters(SemaRef, 2074 cast<VectorType>(T)->getElementType(), 2075 OnlyDeduced, Used); 2076 break; 2077 2078 case Type::DependentSizedExtVector: { 2079 const DependentSizedExtVectorType *VecType 2080 = cast<DependentSizedExtVectorType>(T); 2081 MarkUsedTemplateParameters(SemaRef, VecType->getElementType(), OnlyDeduced, 2082 Used); 2083 MarkUsedTemplateParameters(SemaRef, VecType->getSizeExpr(), OnlyDeduced, 2084 Used); 2085 break; 2086 } 2087 2088 case Type::FunctionProto: { 2089 const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 2090 MarkUsedTemplateParameters(SemaRef, Proto->getResultType(), OnlyDeduced, 2091 Used); 2092 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I) 2093 MarkUsedTemplateParameters(SemaRef, Proto->getArgType(I), OnlyDeduced, 2094 Used); 2095 break; 2096 } 2097 2098 case Type::TemplateTypeParm: 2099 Used[cast<TemplateTypeParmType>(T)->getIndex()] = true; 2100 break; 2101 2102 case Type::TemplateSpecialization: { 2103 const TemplateSpecializationType *Spec 2104 = cast<TemplateSpecializationType>(T); 2105 MarkUsedTemplateParameters(SemaRef, Spec->getTemplateName(), OnlyDeduced, 2106 Used); 2107 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 2108 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Used); 2109 break; 2110 } 2111 2112 case Type::Complex: 2113 if (!OnlyDeduced) 2114 MarkUsedTemplateParameters(SemaRef, 2115 cast<ComplexType>(T)->getElementType(), 2116 OnlyDeduced, Used); 2117 break; 2118 2119 case Type::Typename: 2120 if (!OnlyDeduced) 2121 MarkUsedTemplateParameters(SemaRef, 2122 cast<TypenameType>(T)->getQualifier(), 2123 OnlyDeduced, Used); 2124 break; 2125 2126 // None of these types have any template parameters in them. 2127 case Type::Builtin: 2128 case Type::FixedWidthInt: 2129 case Type::VariableArray: 2130 case Type::FunctionNoProto: 2131 case Type::Record: 2132 case Type::Enum: 2133 case Type::ObjCInterface: 2134 case Type::ObjCObjectPointer: 2135#define TYPE(Class, Base) 2136#define ABSTRACT_TYPE(Class, Base) 2137#define DEPENDENT_TYPE(Class, Base) 2138#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 2139#include "clang/AST/TypeNodes.def" 2140 break; 2141 } 2142} 2143 2144/// \brief Mark the template parameters that are used by this 2145/// template argument. 2146static void 2147MarkUsedTemplateParameters(Sema &SemaRef, 2148 const TemplateArgument &TemplateArg, 2149 bool OnlyDeduced, 2150 llvm::SmallVectorImpl<bool> &Used) { 2151 switch (TemplateArg.getKind()) { 2152 case TemplateArgument::Null: 2153 case TemplateArgument::Integral: 2154 break; 2155 2156 case TemplateArgument::Type: 2157 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsType(), OnlyDeduced, 2158 Used); 2159 break; 2160 2161 case TemplateArgument::Declaration: 2162 if (TemplateTemplateParmDecl *TTP 2163 = dyn_cast<TemplateTemplateParmDecl>(TemplateArg.getAsDecl())) 2164 Used[TTP->getIndex()] = true; 2165 break; 2166 2167 case TemplateArgument::Expression: 2168 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsExpr(), OnlyDeduced, 2169 Used); 2170 break; 2171 2172 case TemplateArgument::Pack: 2173 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(), 2174 PEnd = TemplateArg.pack_end(); 2175 P != PEnd; ++P) 2176 MarkUsedTemplateParameters(SemaRef, *P, OnlyDeduced, Used); 2177 break; 2178 } 2179} 2180 2181/// \brief Mark the template parameters can be deduced by the given 2182/// template argument list. 2183/// 2184/// \param TemplateArgs the template argument list from which template 2185/// parameters will be deduced. 2186/// 2187/// \param Deduced a bit vector whose elements will be set to \c true 2188/// to indicate when the corresponding template parameter will be 2189/// deduced. 2190void 2191Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 2192 bool OnlyDeduced, 2193 llvm::SmallVectorImpl<bool> &Used) { 2194 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 2195 ::MarkUsedTemplateParameters(*this, TemplateArgs[I], OnlyDeduced, Used); 2196} 2197 2198/// \brief Marks all of the template parameters that will be deduced by a 2199/// call to the given function template. 2200void Sema::MarkDeducedTemplateParameters(FunctionTemplateDecl *FunctionTemplate, 2201 llvm::SmallVectorImpl<bool> &Deduced) { 2202 TemplateParameterList *TemplateParams 2203 = FunctionTemplate->getTemplateParameters(); 2204 Deduced.clear(); 2205 Deduced.resize(TemplateParams->size()); 2206 2207 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2208 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 2209 ::MarkUsedTemplateParameters(*this, Function->getParamDecl(I)->getType(), 2210 true, Deduced); 2211} 2212