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