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