SemaTemplateDeduction.cpp revision ea6c96f63a45b4ffdcdf9824a9cf31a32825c0f6
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 "clang/Sema/Sema.h" 14#include "clang/Sema/DeclSpec.h" 15#include "clang/Sema/SemaDiagnostic.h" // FIXME: temporary! 16#include "clang/Sema/Template.h" 17#include "clang/Sema/TemplateDeduction.h" 18#include "clang/AST/ASTContext.h" 19#include "clang/AST/DeclObjC.h" 20#include "clang/AST/DeclTemplate.h" 21#include "clang/AST/StmtVisitor.h" 22#include "clang/AST/Expr.h" 23#include "clang/AST/ExprCXX.h" 24#include "llvm/ADT/BitVector.h" 25#include <algorithm> 26 27namespace clang { 28 using namespace sema; 29 30 /// \brief Various flags that control template argument deduction. 31 /// 32 /// These flags can be bitwise-OR'd together. 33 enum TemplateDeductionFlags { 34 /// \brief No template argument deduction flags, which indicates the 35 /// strictest results for template argument deduction (as used for, e.g., 36 /// matching class template partial specializations). 37 TDF_None = 0, 38 /// \brief Within template argument deduction from a function call, we are 39 /// matching with a parameter type for which the original parameter was 40 /// a reference. 41 TDF_ParamWithReferenceType = 0x1, 42 /// \brief Within template argument deduction from a function call, we 43 /// are matching in a case where we ignore cv-qualifiers. 44 TDF_IgnoreQualifiers = 0x02, 45 /// \brief Within template argument deduction from a function call, 46 /// we are matching in a case where we can perform template argument 47 /// deduction from a template-id of a derived class of the argument type. 48 TDF_DerivedClass = 0x04, 49 /// \brief Allow non-dependent types to differ, e.g., when performing 50 /// template argument deduction from a function call where conversions 51 /// may apply. 52 TDF_SkipNonDependent = 0x08 53 }; 54} 55 56using namespace clang; 57 58/// \brief Compare two APSInts, extending and switching the sign as 59/// necessary to compare their values regardless of underlying type. 60static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) { 61 if (Y.getBitWidth() > X.getBitWidth()) 62 X = X.extend(Y.getBitWidth()); 63 else if (Y.getBitWidth() < X.getBitWidth()) 64 Y = Y.extend(X.getBitWidth()); 65 66 // If there is a signedness mismatch, correct it. 67 if (X.isSigned() != Y.isSigned()) { 68 // If the signed value is negative, then the values cannot be the same. 69 if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative())) 70 return false; 71 72 Y.setIsSigned(true); 73 X.setIsSigned(true); 74 } 75 76 return X == Y; 77} 78 79static Sema::TemplateDeductionResult 80DeduceTemplateArguments(Sema &S, 81 TemplateParameterList *TemplateParams, 82 const TemplateArgument &Param, 83 const TemplateArgument &Arg, 84 TemplateDeductionInfo &Info, 85 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced); 86 87static Sema::TemplateDeductionResult 88DeduceTemplateArguments(Sema &S, 89 TemplateParameterList *TemplateParams, 90 const TemplateArgument *Params, unsigned NumParams, 91 const TemplateArgument *Args, unsigned NumArgs, 92 TemplateDeductionInfo &Info, 93 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 94 bool NumberOfArgumentsMustMatch = true); 95 96/// \brief If the given expression is of a form that permits the deduction 97/// of a non-type template parameter, return the declaration of that 98/// non-type template parameter. 99static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) { 100 if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E)) 101 E = IC->getSubExpr(); 102 103 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E)) 104 return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 105 106 return 0; 107} 108 109/// \brief Determine whether two declaration pointers refer to the same 110/// declaration. 111static bool isSameDeclaration(Decl *X, Decl *Y) { 112 if (!X || !Y) 113 return !X && !Y; 114 115 if (NamedDecl *NX = dyn_cast<NamedDecl>(X)) 116 X = NX->getUnderlyingDecl(); 117 if (NamedDecl *NY = dyn_cast<NamedDecl>(Y)) 118 Y = NY->getUnderlyingDecl(); 119 120 return X->getCanonicalDecl() == Y->getCanonicalDecl(); 121} 122 123/// \brief Verify that the given, deduced template arguments are compatible. 124/// 125/// \returns The deduced template argument, or a NULL template argument if 126/// the deduced template arguments were incompatible. 127static DeducedTemplateArgument 128checkDeducedTemplateArguments(ASTContext &Context, 129 const DeducedTemplateArgument &X, 130 const DeducedTemplateArgument &Y) { 131 // We have no deduction for one or both of the arguments; they're compatible. 132 if (X.isNull()) 133 return Y; 134 if (Y.isNull()) 135 return X; 136 137 switch (X.getKind()) { 138 case TemplateArgument::Null: 139 llvm_unreachable("Non-deduced template arguments handled above"); 140 141 case TemplateArgument::Type: 142 // If two template type arguments have the same type, they're compatible. 143 if (Y.getKind() == TemplateArgument::Type && 144 Context.hasSameType(X.getAsType(), Y.getAsType())) 145 return X; 146 147 return DeducedTemplateArgument(); 148 149 case TemplateArgument::Integral: 150 // If we deduced a constant in one case and either a dependent expression or 151 // declaration in another case, keep the integral constant. 152 // If both are integral constants with the same value, keep that value. 153 if (Y.getKind() == TemplateArgument::Expression || 154 Y.getKind() == TemplateArgument::Declaration || 155 (Y.getKind() == TemplateArgument::Integral && 156 hasSameExtendedValue(*X.getAsIntegral(), *Y.getAsIntegral()))) 157 return DeducedTemplateArgument(X, 158 X.wasDeducedFromArrayBound() && 159 Y.wasDeducedFromArrayBound()); 160 161 // All other combinations are incompatible. 162 return DeducedTemplateArgument(); 163 164 case TemplateArgument::Template: 165 if (Y.getKind() == TemplateArgument::Template && 166 Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate())) 167 return X; 168 169 // All other combinations are incompatible. 170 return DeducedTemplateArgument(); 171 172 case TemplateArgument::Expression: 173 // If we deduced a dependent expression in one case and either an integral 174 // constant or a declaration in another case, keep the integral constant 175 // or declaration. 176 if (Y.getKind() == TemplateArgument::Integral || 177 Y.getKind() == TemplateArgument::Declaration) 178 return DeducedTemplateArgument(Y, X.wasDeducedFromArrayBound() && 179 Y.wasDeducedFromArrayBound()); 180 181 if (Y.getKind() == TemplateArgument::Expression) { 182 // Compare the expressions for equality 183 llvm::FoldingSetNodeID ID1, ID2; 184 X.getAsExpr()->Profile(ID1, Context, true); 185 Y.getAsExpr()->Profile(ID2, Context, true); 186 if (ID1 == ID2) 187 return X; 188 } 189 190 // All other combinations are incompatible. 191 return DeducedTemplateArgument(); 192 193 case TemplateArgument::Declaration: 194 // If we deduced a declaration and a dependent expression, keep the 195 // declaration. 196 if (Y.getKind() == TemplateArgument::Expression) 197 return X; 198 199 // If we deduced a declaration and an integral constant, keep the 200 // integral constant. 201 if (Y.getKind() == TemplateArgument::Integral) 202 return Y; 203 204 // If we deduced two declarations, make sure they they refer to the 205 // same declaration. 206 if (Y.getKind() == TemplateArgument::Declaration && 207 isSameDeclaration(X.getAsDecl(), Y.getAsDecl())) 208 return X; 209 210 // All other combinations are incompatible. 211 return DeducedTemplateArgument(); 212 213 case TemplateArgument::Pack: 214 if (Y.getKind() != TemplateArgument::Pack || 215 X.pack_size() != Y.pack_size()) 216 return DeducedTemplateArgument(); 217 218 for (TemplateArgument::pack_iterator XA = X.pack_begin(), 219 XAEnd = X.pack_end(), 220 YA = Y.pack_begin(); 221 XA != XAEnd; ++XA, ++YA) { 222 // FIXME: We've lost the "deduced from array bound" bit. 223 if (checkDeducedTemplateArguments(Context, *XA, *YA).isNull()) 224 return DeducedTemplateArgument(); 225 } 226 227 return X; 228 } 229 230 return DeducedTemplateArgument(); 231} 232 233/// \brief Deduce the value of the given non-type template parameter 234/// from the given constant. 235static Sema::TemplateDeductionResult 236DeduceNonTypeTemplateArgument(Sema &S, 237 NonTypeTemplateParmDecl *NTTP, 238 llvm::APSInt Value, QualType ValueType, 239 bool DeducedFromArrayBound, 240 TemplateDeductionInfo &Info, 241 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 242 assert(NTTP->getDepth() == 0 && 243 "Cannot deduce non-type template argument with depth > 0"); 244 245 DeducedTemplateArgument NewDeduced(Value, ValueType, DeducedFromArrayBound); 246 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 247 Deduced[NTTP->getIndex()], 248 NewDeduced); 249 if (Result.isNull()) { 250 Info.Param = NTTP; 251 Info.FirstArg = Deduced[NTTP->getIndex()]; 252 Info.SecondArg = NewDeduced; 253 return Sema::TDK_Inconsistent; 254 } 255 256 Deduced[NTTP->getIndex()] = Result; 257 return Sema::TDK_Success; 258} 259 260/// \brief Deduce the value of the given non-type template parameter 261/// from the given type- or value-dependent expression. 262/// 263/// \returns true if deduction succeeded, false otherwise. 264static Sema::TemplateDeductionResult 265DeduceNonTypeTemplateArgument(Sema &S, 266 NonTypeTemplateParmDecl *NTTP, 267 Expr *Value, 268 TemplateDeductionInfo &Info, 269 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 270 assert(NTTP->getDepth() == 0 && 271 "Cannot deduce non-type template argument with depth > 0"); 272 assert((Value->isTypeDependent() || Value->isValueDependent()) && 273 "Expression template argument must be type- or value-dependent."); 274 275 DeducedTemplateArgument NewDeduced(Value); 276 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 277 Deduced[NTTP->getIndex()], 278 NewDeduced); 279 280 if (Result.isNull()) { 281 Info.Param = NTTP; 282 Info.FirstArg = Deduced[NTTP->getIndex()]; 283 Info.SecondArg = NewDeduced; 284 return Sema::TDK_Inconsistent; 285 } 286 287 Deduced[NTTP->getIndex()] = Result; 288 return Sema::TDK_Success; 289} 290 291/// \brief Deduce the value of the given non-type template parameter 292/// from the given declaration. 293/// 294/// \returns true if deduction succeeded, false otherwise. 295static Sema::TemplateDeductionResult 296DeduceNonTypeTemplateArgument(Sema &S, 297 NonTypeTemplateParmDecl *NTTP, 298 Decl *D, 299 TemplateDeductionInfo &Info, 300 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 301 assert(NTTP->getDepth() == 0 && 302 "Cannot deduce non-type template argument with depth > 0"); 303 304 DeducedTemplateArgument NewDeduced(D? D->getCanonicalDecl() : 0); 305 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 306 Deduced[NTTP->getIndex()], 307 NewDeduced); 308 if (Result.isNull()) { 309 Info.Param = NTTP; 310 Info.FirstArg = Deduced[NTTP->getIndex()]; 311 Info.SecondArg = NewDeduced; 312 return Sema::TDK_Inconsistent; 313 } 314 315 Deduced[NTTP->getIndex()] = Result; 316 return Sema::TDK_Success; 317} 318 319static Sema::TemplateDeductionResult 320DeduceTemplateArguments(Sema &S, 321 TemplateParameterList *TemplateParams, 322 TemplateName Param, 323 TemplateName Arg, 324 TemplateDeductionInfo &Info, 325 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 326 TemplateDecl *ParamDecl = Param.getAsTemplateDecl(); 327 if (!ParamDecl) { 328 // The parameter type is dependent and is not a template template parameter, 329 // so there is nothing that we can deduce. 330 return Sema::TDK_Success; 331 } 332 333 if (TemplateTemplateParmDecl *TempParam 334 = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) { 335 DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg)); 336 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 337 Deduced[TempParam->getIndex()], 338 NewDeduced); 339 if (Result.isNull()) { 340 Info.Param = TempParam; 341 Info.FirstArg = Deduced[TempParam->getIndex()]; 342 Info.SecondArg = NewDeduced; 343 return Sema::TDK_Inconsistent; 344 } 345 346 Deduced[TempParam->getIndex()] = Result; 347 return Sema::TDK_Success; 348 } 349 350 // Verify that the two template names are equivalent. 351 if (S.Context.hasSameTemplateName(Param, Arg)) 352 return Sema::TDK_Success; 353 354 // Mismatch of non-dependent template parameter to argument. 355 Info.FirstArg = TemplateArgument(Param); 356 Info.SecondArg = TemplateArgument(Arg); 357 return Sema::TDK_NonDeducedMismatch; 358} 359 360/// \brief Deduce the template arguments by comparing the template parameter 361/// type (which is a template-id) with the template argument type. 362/// 363/// \param S the Sema 364/// 365/// \param TemplateParams the template parameters that we are deducing 366/// 367/// \param Param the parameter type 368/// 369/// \param Arg the argument type 370/// 371/// \param Info information about the template argument deduction itself 372/// 373/// \param Deduced the deduced template arguments 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(Sema &S, 380 TemplateParameterList *TemplateParams, 381 const TemplateSpecializationType *Param, 382 QualType Arg, 383 TemplateDeductionInfo &Info, 384 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 385 assert(Arg.isCanonical() && "Argument type must be canonical"); 386 387 // Check whether the template argument is a dependent template-id. 388 if (const TemplateSpecializationType *SpecArg 389 = dyn_cast<TemplateSpecializationType>(Arg)) { 390 // Perform template argument deduction for the template name. 391 if (Sema::TemplateDeductionResult Result 392 = DeduceTemplateArguments(S, TemplateParams, 393 Param->getTemplateName(), 394 SpecArg->getTemplateName(), 395 Info, Deduced)) 396 return Result; 397 398 399 // Perform template argument deduction on each template 400 // argument. Ignore any missing/extra arguments, since they could be 401 // filled in by default arguments. 402 return DeduceTemplateArguments(S, TemplateParams, 403 Param->getArgs(), Param->getNumArgs(), 404 SpecArg->getArgs(), SpecArg->getNumArgs(), 405 Info, Deduced, 406 /*NumberOfArgumentsMustMatch=*/false); 407 } 408 409 // If the argument type is a class template specialization, we 410 // perform template argument deduction using its template 411 // arguments. 412 const RecordType *RecordArg = dyn_cast<RecordType>(Arg); 413 if (!RecordArg) 414 return Sema::TDK_NonDeducedMismatch; 415 416 ClassTemplateSpecializationDecl *SpecArg 417 = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl()); 418 if (!SpecArg) 419 return Sema::TDK_NonDeducedMismatch; 420 421 // Perform template argument deduction for the template name. 422 if (Sema::TemplateDeductionResult Result 423 = DeduceTemplateArguments(S, 424 TemplateParams, 425 Param->getTemplateName(), 426 TemplateName(SpecArg->getSpecializedTemplate()), 427 Info, Deduced)) 428 return Result; 429 430 // Perform template argument deduction for the template arguments. 431 return DeduceTemplateArguments(S, TemplateParams, 432 Param->getArgs(), Param->getNumArgs(), 433 SpecArg->getTemplateArgs().data(), 434 SpecArg->getTemplateArgs().size(), 435 Info, Deduced); 436} 437 438/// \brief Determines whether the given type is an opaque type that 439/// might be more qualified when instantiated. 440static bool IsPossiblyOpaquelyQualifiedType(QualType T) { 441 switch (T->getTypeClass()) { 442 case Type::TypeOfExpr: 443 case Type::TypeOf: 444 case Type::DependentName: 445 case Type::Decltype: 446 case Type::UnresolvedUsing: 447 return true; 448 449 case Type::ConstantArray: 450 case Type::IncompleteArray: 451 case Type::VariableArray: 452 case Type::DependentSizedArray: 453 return IsPossiblyOpaquelyQualifiedType( 454 cast<ArrayType>(T)->getElementType()); 455 456 default: 457 return false; 458 } 459} 460 461/// \brief Deduce the template arguments by comparing the parameter type and 462/// the argument type (C++ [temp.deduct.type]). 463/// 464/// \param S the semantic analysis object within which we are deducing 465/// 466/// \param TemplateParams the template parameters that we are deducing 467/// 468/// \param ParamIn the parameter type 469/// 470/// \param ArgIn the argument type 471/// 472/// \param Info information about the template argument deduction itself 473/// 474/// \param Deduced the deduced template arguments 475/// 476/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe 477/// how template argument deduction is performed. 478/// 479/// \returns the result of template argument deduction so far. Note that a 480/// "success" result means that template argument deduction has not yet failed, 481/// but it may still fail, later, for other reasons. 482static Sema::TemplateDeductionResult 483DeduceTemplateArguments(Sema &S, 484 TemplateParameterList *TemplateParams, 485 QualType ParamIn, QualType ArgIn, 486 TemplateDeductionInfo &Info, 487 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 488 unsigned TDF) { 489 // We only want to look at the canonical types, since typedefs and 490 // sugar are not part of template argument deduction. 491 QualType Param = S.Context.getCanonicalType(ParamIn); 492 QualType Arg = S.Context.getCanonicalType(ArgIn); 493 494 // C++0x [temp.deduct.call]p4 bullet 1: 495 // - If the original P is a reference type, the deduced A (i.e., the type 496 // referred to by the reference) can be more cv-qualified than the 497 // transformed A. 498 if (TDF & TDF_ParamWithReferenceType) { 499 Qualifiers Quals; 500 QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals); 501 Quals.setCVRQualifiers(Quals.getCVRQualifiers() & 502 Arg.getCVRQualifiersThroughArrayTypes()); 503 Param = S.Context.getQualifiedType(UnqualParam, Quals); 504 } 505 506 // If the parameter type is not dependent, there is nothing to deduce. 507 if (!Param->isDependentType()) { 508 if (!(TDF & TDF_SkipNonDependent) && Param != Arg) { 509 510 return Sema::TDK_NonDeducedMismatch; 511 } 512 513 return Sema::TDK_Success; 514 } 515 516 // C++ [temp.deduct.type]p9: 517 // A template type argument T, a template template argument TT or a 518 // template non-type argument i can be deduced if P and A have one of 519 // the following forms: 520 // 521 // T 522 // cv-list T 523 if (const TemplateTypeParmType *TemplateTypeParm 524 = Param->getAs<TemplateTypeParmType>()) { 525 unsigned Index = TemplateTypeParm->getIndex(); 526 bool RecanonicalizeArg = false; 527 528 // If the argument type is an array type, move the qualifiers up to the 529 // top level, so they can be matched with the qualifiers on the parameter. 530 // FIXME: address spaces, ObjC GC qualifiers 531 if (isa<ArrayType>(Arg)) { 532 Qualifiers Quals; 533 Arg = S.Context.getUnqualifiedArrayType(Arg, Quals); 534 if (Quals) { 535 Arg = S.Context.getQualifiedType(Arg, Quals); 536 RecanonicalizeArg = true; 537 } 538 } 539 540 // The argument type can not be less qualified than the parameter 541 // type. 542 if (Param.isMoreQualifiedThan(Arg) && !(TDF & TDF_IgnoreQualifiers)) { 543 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 544 Info.FirstArg = TemplateArgument(Param); 545 Info.SecondArg = TemplateArgument(Arg); 546 return Sema::TDK_Underqualified; 547 } 548 549 assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0"); 550 assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function"); 551 QualType DeducedType = Arg; 552 553 // local manipulation is okay because it's canonical 554 DeducedType.removeLocalCVRQualifiers(Param.getCVRQualifiers()); 555 if (RecanonicalizeArg) 556 DeducedType = S.Context.getCanonicalType(DeducedType); 557 558 DeducedTemplateArgument NewDeduced(DeducedType); 559 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 560 Deduced[Index], 561 NewDeduced); 562 if (Result.isNull()) { 563 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 564 Info.FirstArg = Deduced[Index]; 565 Info.SecondArg = NewDeduced; 566 return Sema::TDK_Inconsistent; 567 } 568 569 Deduced[Index] = Result; 570 return Sema::TDK_Success; 571 } 572 573 // Set up the template argument deduction information for a failure. 574 Info.FirstArg = TemplateArgument(ParamIn); 575 Info.SecondArg = TemplateArgument(ArgIn); 576 577 // Check the cv-qualifiers on the parameter and argument types. 578 if (!(TDF & TDF_IgnoreQualifiers)) { 579 if (TDF & TDF_ParamWithReferenceType) { 580 if (Param.isMoreQualifiedThan(Arg)) 581 return Sema::TDK_NonDeducedMismatch; 582 } else if (!IsPossiblyOpaquelyQualifiedType(Param)) { 583 if (Param.getCVRQualifiers() != Arg.getCVRQualifiers()) 584 return Sema::TDK_NonDeducedMismatch; 585 } 586 } 587 588 switch (Param->getTypeClass()) { 589 // No deduction possible for these types 590 case Type::Builtin: 591 return Sema::TDK_NonDeducedMismatch; 592 593 // T * 594 case Type::Pointer: { 595 QualType PointeeType; 596 if (const PointerType *PointerArg = Arg->getAs<PointerType>()) { 597 PointeeType = PointerArg->getPointeeType(); 598 } else if (const ObjCObjectPointerType *PointerArg 599 = Arg->getAs<ObjCObjectPointerType>()) { 600 PointeeType = PointerArg->getPointeeType(); 601 } else { 602 return Sema::TDK_NonDeducedMismatch; 603 } 604 605 unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass); 606 return DeduceTemplateArguments(S, TemplateParams, 607 cast<PointerType>(Param)->getPointeeType(), 608 PointeeType, 609 Info, Deduced, SubTDF); 610 } 611 612 // T & 613 case Type::LValueReference: { 614 const LValueReferenceType *ReferenceArg = Arg->getAs<LValueReferenceType>(); 615 if (!ReferenceArg) 616 return Sema::TDK_NonDeducedMismatch; 617 618 return DeduceTemplateArguments(S, TemplateParams, 619 cast<LValueReferenceType>(Param)->getPointeeType(), 620 ReferenceArg->getPointeeType(), 621 Info, Deduced, 0); 622 } 623 624 // T && [C++0x] 625 case Type::RValueReference: { 626 const RValueReferenceType *ReferenceArg = Arg->getAs<RValueReferenceType>(); 627 if (!ReferenceArg) 628 return Sema::TDK_NonDeducedMismatch; 629 630 return DeduceTemplateArguments(S, TemplateParams, 631 cast<RValueReferenceType>(Param)->getPointeeType(), 632 ReferenceArg->getPointeeType(), 633 Info, Deduced, 0); 634 } 635 636 // T [] (implied, but not stated explicitly) 637 case Type::IncompleteArray: { 638 const IncompleteArrayType *IncompleteArrayArg = 639 S.Context.getAsIncompleteArrayType(Arg); 640 if (!IncompleteArrayArg) 641 return Sema::TDK_NonDeducedMismatch; 642 643 unsigned SubTDF = TDF & TDF_IgnoreQualifiers; 644 return DeduceTemplateArguments(S, TemplateParams, 645 S.Context.getAsIncompleteArrayType(Param)->getElementType(), 646 IncompleteArrayArg->getElementType(), 647 Info, Deduced, SubTDF); 648 } 649 650 // T [integer-constant] 651 case Type::ConstantArray: { 652 const ConstantArrayType *ConstantArrayArg = 653 S.Context.getAsConstantArrayType(Arg); 654 if (!ConstantArrayArg) 655 return Sema::TDK_NonDeducedMismatch; 656 657 const ConstantArrayType *ConstantArrayParm = 658 S.Context.getAsConstantArrayType(Param); 659 if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize()) 660 return Sema::TDK_NonDeducedMismatch; 661 662 unsigned SubTDF = TDF & TDF_IgnoreQualifiers; 663 return DeduceTemplateArguments(S, TemplateParams, 664 ConstantArrayParm->getElementType(), 665 ConstantArrayArg->getElementType(), 666 Info, Deduced, SubTDF); 667 } 668 669 // type [i] 670 case Type::DependentSizedArray: { 671 const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg); 672 if (!ArrayArg) 673 return Sema::TDK_NonDeducedMismatch; 674 675 unsigned SubTDF = TDF & TDF_IgnoreQualifiers; 676 677 // Check the element type of the arrays 678 const DependentSizedArrayType *DependentArrayParm 679 = S.Context.getAsDependentSizedArrayType(Param); 680 if (Sema::TemplateDeductionResult Result 681 = DeduceTemplateArguments(S, TemplateParams, 682 DependentArrayParm->getElementType(), 683 ArrayArg->getElementType(), 684 Info, Deduced, SubTDF)) 685 return Result; 686 687 // Determine the array bound is something we can deduce. 688 NonTypeTemplateParmDecl *NTTP 689 = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr()); 690 if (!NTTP) 691 return Sema::TDK_Success; 692 693 // We can perform template argument deduction for the given non-type 694 // template parameter. 695 assert(NTTP->getDepth() == 0 && 696 "Cannot deduce non-type template argument at depth > 0"); 697 if (const ConstantArrayType *ConstantArrayArg 698 = dyn_cast<ConstantArrayType>(ArrayArg)) { 699 llvm::APSInt Size(ConstantArrayArg->getSize()); 700 return DeduceNonTypeTemplateArgument(S, NTTP, Size, 701 S.Context.getSizeType(), 702 /*ArrayBound=*/true, 703 Info, Deduced); 704 } 705 if (const DependentSizedArrayType *DependentArrayArg 706 = dyn_cast<DependentSizedArrayType>(ArrayArg)) 707 if (DependentArrayArg->getSizeExpr()) 708 return DeduceNonTypeTemplateArgument(S, NTTP, 709 DependentArrayArg->getSizeExpr(), 710 Info, Deduced); 711 712 // Incomplete type does not match a dependently-sized array type 713 return Sema::TDK_NonDeducedMismatch; 714 } 715 716 // type(*)(T) 717 // T(*)() 718 // T(*)(T) 719 case Type::FunctionProto: { 720 const FunctionProtoType *FunctionProtoArg = 721 dyn_cast<FunctionProtoType>(Arg); 722 if (!FunctionProtoArg) 723 return Sema::TDK_NonDeducedMismatch; 724 725 const FunctionProtoType *FunctionProtoParam = 726 cast<FunctionProtoType>(Param); 727 728 if (FunctionProtoParam->getTypeQuals() != 729 FunctionProtoArg->getTypeQuals()) 730 return Sema::TDK_NonDeducedMismatch; 731 732 if (FunctionProtoParam->getNumArgs() != FunctionProtoArg->getNumArgs()) 733 return Sema::TDK_NonDeducedMismatch; 734 735 if (FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic()) 736 return Sema::TDK_NonDeducedMismatch; 737 738 // Check return types. 739 if (Sema::TemplateDeductionResult Result 740 = DeduceTemplateArguments(S, TemplateParams, 741 FunctionProtoParam->getResultType(), 742 FunctionProtoArg->getResultType(), 743 Info, Deduced, 0)) 744 return Result; 745 746 for (unsigned I = 0, N = FunctionProtoParam->getNumArgs(); I != N; ++I) { 747 // Check argument types. 748 // FIXME: Variadic templates. 749 if (Sema::TemplateDeductionResult Result 750 = DeduceTemplateArguments(S, TemplateParams, 751 FunctionProtoParam->getArgType(I), 752 FunctionProtoArg->getArgType(I), 753 Info, Deduced, 0)) 754 return Result; 755 } 756 757 return Sema::TDK_Success; 758 } 759 760 case Type::InjectedClassName: { 761 // Treat a template's injected-class-name as if the template 762 // specialization type had been used. 763 Param = cast<InjectedClassNameType>(Param) 764 ->getInjectedSpecializationType(); 765 assert(isa<TemplateSpecializationType>(Param) && 766 "injected class name is not a template specialization type"); 767 // fall through 768 } 769 770 // template-name<T> (where template-name refers to a class template) 771 // template-name<i> 772 // TT<T> 773 // TT<i> 774 // TT<> 775 case Type::TemplateSpecialization: { 776 const TemplateSpecializationType *SpecParam 777 = cast<TemplateSpecializationType>(Param); 778 779 // Try to deduce template arguments from the template-id. 780 Sema::TemplateDeductionResult Result 781 = DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg, 782 Info, Deduced); 783 784 if (Result && (TDF & TDF_DerivedClass)) { 785 // C++ [temp.deduct.call]p3b3: 786 // If P is a class, and P has the form template-id, then A can be a 787 // derived class of the deduced A. Likewise, if P is a pointer to a 788 // class of the form template-id, A can be a pointer to a derived 789 // class pointed to by the deduced A. 790 // 791 // More importantly: 792 // These alternatives are considered only if type deduction would 793 // otherwise fail. 794 if (const RecordType *RecordT = Arg->getAs<RecordType>()) { 795 // We cannot inspect base classes as part of deduction when the type 796 // is incomplete, so either instantiate any templates necessary to 797 // complete the type, or skip over it if it cannot be completed. 798 if (S.RequireCompleteType(Info.getLocation(), Arg, 0)) 799 return Result; 800 801 // Use data recursion to crawl through the list of base classes. 802 // Visited contains the set of nodes we have already visited, while 803 // ToVisit is our stack of records that we still need to visit. 804 llvm::SmallPtrSet<const RecordType *, 8> Visited; 805 llvm::SmallVector<const RecordType *, 8> ToVisit; 806 ToVisit.push_back(RecordT); 807 bool Successful = false; 808 llvm::SmallVectorImpl<DeducedTemplateArgument> DeducedOrig(0); 809 DeducedOrig = Deduced; 810 while (!ToVisit.empty()) { 811 // Retrieve the next class in the inheritance hierarchy. 812 const RecordType *NextT = ToVisit.back(); 813 ToVisit.pop_back(); 814 815 // If we have already seen this type, skip it. 816 if (!Visited.insert(NextT)) 817 continue; 818 819 // If this is a base class, try to perform template argument 820 // deduction from it. 821 if (NextT != RecordT) { 822 Sema::TemplateDeductionResult BaseResult 823 = DeduceTemplateArguments(S, TemplateParams, SpecParam, 824 QualType(NextT, 0), Info, Deduced); 825 826 // If template argument deduction for this base was successful, 827 // note that we had some success. Otherwise, ignore any deductions 828 // from this base class. 829 if (BaseResult == Sema::TDK_Success) { 830 Successful = true; 831 DeducedOrig = Deduced; 832 } 833 else 834 Deduced = DeducedOrig; 835 } 836 837 // Visit base classes 838 CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl()); 839 for (CXXRecordDecl::base_class_iterator Base = Next->bases_begin(), 840 BaseEnd = Next->bases_end(); 841 Base != BaseEnd; ++Base) { 842 assert(Base->getType()->isRecordType() && 843 "Base class that isn't a record?"); 844 ToVisit.push_back(Base->getType()->getAs<RecordType>()); 845 } 846 } 847 848 if (Successful) 849 return Sema::TDK_Success; 850 } 851 852 } 853 854 return Result; 855 } 856 857 // T type::* 858 // T T::* 859 // T (type::*)() 860 // type (T::*)() 861 // type (type::*)(T) 862 // type (T::*)(T) 863 // T (type::*)(T) 864 // T (T::*)() 865 // T (T::*)(T) 866 case Type::MemberPointer: { 867 const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param); 868 const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg); 869 if (!MemPtrArg) 870 return Sema::TDK_NonDeducedMismatch; 871 872 if (Sema::TemplateDeductionResult Result 873 = DeduceTemplateArguments(S, TemplateParams, 874 MemPtrParam->getPointeeType(), 875 MemPtrArg->getPointeeType(), 876 Info, Deduced, 877 TDF & TDF_IgnoreQualifiers)) 878 return Result; 879 880 return DeduceTemplateArguments(S, TemplateParams, 881 QualType(MemPtrParam->getClass(), 0), 882 QualType(MemPtrArg->getClass(), 0), 883 Info, Deduced, 0); 884 } 885 886 // (clang extension) 887 // 888 // type(^)(T) 889 // T(^)() 890 // T(^)(T) 891 case Type::BlockPointer: { 892 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param); 893 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg); 894 895 if (!BlockPtrArg) 896 return Sema::TDK_NonDeducedMismatch; 897 898 return DeduceTemplateArguments(S, TemplateParams, 899 BlockPtrParam->getPointeeType(), 900 BlockPtrArg->getPointeeType(), Info, 901 Deduced, 0); 902 } 903 904 case Type::TypeOfExpr: 905 case Type::TypeOf: 906 case Type::DependentName: 907 // No template argument deduction for these types 908 return Sema::TDK_Success; 909 910 default: 911 break; 912 } 913 914 // FIXME: Many more cases to go (to go). 915 return Sema::TDK_Success; 916} 917 918static Sema::TemplateDeductionResult 919DeduceTemplateArguments(Sema &S, 920 TemplateParameterList *TemplateParams, 921 const TemplateArgument &Param, 922 const TemplateArgument &Arg, 923 TemplateDeductionInfo &Info, 924 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 925 switch (Param.getKind()) { 926 case TemplateArgument::Null: 927 assert(false && "Null template argument in parameter list"); 928 break; 929 930 case TemplateArgument::Type: 931 if (Arg.getKind() == TemplateArgument::Type) 932 return DeduceTemplateArguments(S, TemplateParams, Param.getAsType(), 933 Arg.getAsType(), Info, Deduced, 0); 934 Info.FirstArg = Param; 935 Info.SecondArg = Arg; 936 return Sema::TDK_NonDeducedMismatch; 937 938 case TemplateArgument::Template: 939 if (Arg.getKind() == TemplateArgument::Template) 940 return DeduceTemplateArguments(S, TemplateParams, 941 Param.getAsTemplate(), 942 Arg.getAsTemplate(), Info, Deduced); 943 Info.FirstArg = Param; 944 Info.SecondArg = Arg; 945 return Sema::TDK_NonDeducedMismatch; 946 947 case TemplateArgument::Declaration: 948 if (Arg.getKind() == TemplateArgument::Declaration && 949 Param.getAsDecl()->getCanonicalDecl() == 950 Arg.getAsDecl()->getCanonicalDecl()) 951 return Sema::TDK_Success; 952 953 Info.FirstArg = Param; 954 Info.SecondArg = Arg; 955 return Sema::TDK_NonDeducedMismatch; 956 957 case TemplateArgument::Integral: 958 if (Arg.getKind() == TemplateArgument::Integral) { 959 if (hasSameExtendedValue(*Param.getAsIntegral(), *Arg.getAsIntegral())) 960 return Sema::TDK_Success; 961 962 Info.FirstArg = Param; 963 Info.SecondArg = Arg; 964 return Sema::TDK_NonDeducedMismatch; 965 } 966 967 if (Arg.getKind() == TemplateArgument::Expression) { 968 Info.FirstArg = Param; 969 Info.SecondArg = Arg; 970 return Sema::TDK_NonDeducedMismatch; 971 } 972 973 Info.FirstArg = Param; 974 Info.SecondArg = Arg; 975 return Sema::TDK_NonDeducedMismatch; 976 977 case TemplateArgument::Expression: { 978 if (NonTypeTemplateParmDecl *NTTP 979 = getDeducedParameterFromExpr(Param.getAsExpr())) { 980 if (Arg.getKind() == TemplateArgument::Integral) 981 return DeduceNonTypeTemplateArgument(S, NTTP, 982 *Arg.getAsIntegral(), 983 Arg.getIntegralType(), 984 /*ArrayBound=*/false, 985 Info, Deduced); 986 if (Arg.getKind() == TemplateArgument::Expression) 987 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(), 988 Info, Deduced); 989 if (Arg.getKind() == TemplateArgument::Declaration) 990 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(), 991 Info, Deduced); 992 993 Info.FirstArg = Param; 994 Info.SecondArg = Arg; 995 return Sema::TDK_NonDeducedMismatch; 996 } 997 998 // Can't deduce anything, but that's okay. 999 return Sema::TDK_Success; 1000 } 1001 case TemplateArgument::Pack: 1002 llvm_unreachable("Argument packs should be expanded by the caller!"); 1003 } 1004 1005 return Sema::TDK_Success; 1006} 1007 1008/// \brief Determine whether there is a template argument to be used for 1009/// deduction. 1010/// 1011/// This routine "expands" argument packs in-place, overriding its input 1012/// parameters so that \c Args[ArgIdx] will be the available template argument. 1013/// 1014/// \returns true if there is another template argument (which will be at 1015/// \c Args[ArgIdx]), false otherwise. 1016static bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args, 1017 unsigned &ArgIdx, 1018 unsigned &NumArgs) { 1019 if (ArgIdx == NumArgs) 1020 return false; 1021 1022 const TemplateArgument &Arg = Args[ArgIdx]; 1023 if (Arg.getKind() != TemplateArgument::Pack) 1024 return true; 1025 1026 assert(ArgIdx == NumArgs - 1 && "Pack not at the end of argument list?"); 1027 Args = Arg.pack_begin(); 1028 NumArgs = Arg.pack_size(); 1029 ArgIdx = 0; 1030 return ArgIdx < NumArgs; 1031} 1032 1033/// \brief Retrieve the depth and index of an unexpanded parameter pack. 1034static std::pair<unsigned, unsigned> 1035getDepthAndIndex(UnexpandedParameterPack UPP) { 1036 if (const TemplateTypeParmType *TTP 1037 = UPP.first.dyn_cast<const TemplateTypeParmType *>()) 1038 return std::make_pair(TTP->getDepth(), TTP->getIndex()); 1039 1040 if (TemplateTypeParmDecl *TTP = UPP.first.dyn_cast<TemplateTypeParmDecl *>()) 1041 return std::make_pair(TTP->getDepth(), TTP->getIndex()); 1042 1043 if (NonTypeTemplateParmDecl *NTTP 1044 = UPP.first.dyn_cast<NonTypeTemplateParmDecl *>()) 1045 return std::make_pair(NTTP->getDepth(), NTTP->getIndex()); 1046 1047 TemplateTemplateParmDecl *TTP = UPP.first.get<TemplateTemplateParmDecl *>(); 1048 return std::make_pair(TTP->getDepth(), TTP->getIndex()); 1049} 1050 1051/// \brief Helper function to build a TemplateParameter when we don't 1052/// know its type statically. 1053static TemplateParameter makeTemplateParameter(Decl *D) { 1054 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D)) 1055 return TemplateParameter(TTP); 1056 else if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) 1057 return TemplateParameter(NTTP); 1058 1059 return TemplateParameter(cast<TemplateTemplateParmDecl>(D)); 1060} 1061 1062/// \brief Determine whether the given set of template arguments has a pack 1063/// expansion that is not the last template argument. 1064static bool hasPackExpansionBeforeEnd(const TemplateArgument *Args, 1065 unsigned NumArgs) { 1066 unsigned ArgIdx = 0; 1067 while (ArgIdx < NumArgs) { 1068 const TemplateArgument &Arg = Args[ArgIdx]; 1069 1070 // Unwrap argument packs. 1071 if (Args[ArgIdx].getKind() == TemplateArgument::Pack) { 1072 Args = Arg.pack_begin(); 1073 NumArgs = Arg.pack_size(); 1074 ArgIdx = 0; 1075 continue; 1076 } 1077 1078 ++ArgIdx; 1079 if (ArgIdx == NumArgs) 1080 return false; 1081 1082 if (Arg.isPackExpansion()) 1083 return true; 1084 } 1085 1086 return false; 1087} 1088 1089static Sema::TemplateDeductionResult 1090DeduceTemplateArguments(Sema &S, 1091 TemplateParameterList *TemplateParams, 1092 const TemplateArgument *Params, unsigned NumParams, 1093 const TemplateArgument *Args, unsigned NumArgs, 1094 TemplateDeductionInfo &Info, 1095 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1096 bool NumberOfArgumentsMustMatch) { 1097 // C++0x [temp.deduct.type]p9: 1098 // If the template argument list of P contains a pack expansion that is not 1099 // the last template argument, the entire template argument list is a 1100 // non-deduced context. 1101 if (hasPackExpansionBeforeEnd(Params, NumParams)) 1102 return Sema::TDK_Success; 1103 1104 // C++0x [temp.deduct.type]p9: 1105 // If P has a form that contains <T> or <i>, then each argument Pi of the 1106 // respective template argument list P is compared with the corresponding 1107 // argument Ai of the corresponding template argument list of A. 1108 unsigned ArgIdx = 0, ParamIdx = 0; 1109 for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams); 1110 ++ParamIdx) { 1111 // FIXME: Variadic templates. 1112 // What do we do if the argument is a pack expansion? 1113 1114 if (!Params[ParamIdx].isPackExpansion()) { 1115 // The simple case: deduce template arguments by matching Pi and Ai. 1116 1117 // Check whether we have enough arguments. 1118 if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) 1119 return NumberOfArgumentsMustMatch? Sema::TDK_TooFewArguments 1120 : Sema::TDK_Success; 1121 1122 // Perform deduction for this Pi/Ai pair. 1123 if (Sema::TemplateDeductionResult Result 1124 = DeduceTemplateArguments(S, TemplateParams, 1125 Params[ParamIdx], Args[ArgIdx], 1126 Info, Deduced)) 1127 return Result; 1128 1129 // Move to the next argument. 1130 ++ArgIdx; 1131 continue; 1132 } 1133 1134 // The parameter is a pack expansion. 1135 1136 // C++0x [temp.deduct.type]p9: 1137 // If Pi is a pack expansion, then the pattern of Pi is compared with 1138 // each remaining argument in the template argument list of A. Each 1139 // comparison deduces template arguments for subsequent positions in the 1140 // template parameter packs expanded by Pi. 1141 TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern(); 1142 1143 // Compute the set of template parameter indices that correspond to 1144 // parameter packs expanded by the pack expansion. 1145 llvm::SmallVector<unsigned, 2> PackIndices; 1146 { 1147 llvm::BitVector SawIndices(TemplateParams->size()); 1148 llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded; 1149 S.collectUnexpandedParameterPacks(Pattern, Unexpanded); 1150 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) { 1151 unsigned Depth, Index; 1152 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]); 1153 if (Depth == 0 && !SawIndices[Index]) { 1154 SawIndices[Index] = true; 1155 PackIndices.push_back(Index); 1156 } 1157 } 1158 } 1159 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?"); 1160 1161 // FIXME: If there are no remaining arguments, we can bail out early 1162 // and set any deduced parameter packs to an empty argument pack. 1163 // The latter part of this is a (minor) correctness issue. 1164 1165 // Save the deduced template arguments for each parameter pack expanded 1166 // by this pack expansion, then clear out the deduction. 1167 llvm::SmallVector<DeducedTemplateArgument, 2> 1168 SavedPacks(PackIndices.size()); 1169 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 1170 SavedPacks[I] = Deduced[PackIndices[I]]; 1171 Deduced[PackIndices[I]] = DeducedTemplateArgument(); 1172 } 1173 1174 // Keep track of the deduced template arguments for each parameter pack 1175 // expanded by this pack expansion (the outer index) and for each 1176 // template argument (the inner SmallVectors). 1177 llvm::SmallVector<llvm::SmallVector<DeducedTemplateArgument, 4>, 2> 1178 NewlyDeducedPacks(PackIndices.size()); 1179 bool HasAnyArguments = false; 1180 while (hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) { 1181 HasAnyArguments = true; 1182 1183 // Deduce template arguments from the pattern. 1184 if (Sema::TemplateDeductionResult Result 1185 = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx], 1186 Info, Deduced)) 1187 return Result; 1188 1189 // Capture the deduced template arguments for each parameter pack expanded 1190 // by this pack expansion, add them to the list of arguments we've deduced 1191 // for that pack, then clear out the deduced argument. 1192 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 1193 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]]; 1194 if (!DeducedArg.isNull()) { 1195 NewlyDeducedPacks[I].push_back(DeducedArg); 1196 DeducedArg = DeducedTemplateArgument(); 1197 } 1198 } 1199 1200 ++ArgIdx; 1201 } 1202 1203 // Build argument packs for each of the parameter packs expanded by this 1204 // pack expansion. 1205 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 1206 if (HasAnyArguments && NewlyDeducedPacks[I].empty()) { 1207 // We were not able to deduce anything for this parameter pack, 1208 // so just restore the saved argument pack. 1209 Deduced[PackIndices[I]] = SavedPacks[I]; 1210 continue; 1211 } 1212 1213 DeducedTemplateArgument NewPack; 1214 1215 if (NewlyDeducedPacks[I].empty()) { 1216 // If we deduced an empty argument pack, create it now. 1217 NewPack = DeducedTemplateArgument(TemplateArgument(0, 0)); 1218 } else { 1219 TemplateArgument *ArgumentPack 1220 = new (S.Context) TemplateArgument [NewlyDeducedPacks[I].size()]; 1221 std::copy(NewlyDeducedPacks[I].begin(), NewlyDeducedPacks[I].end(), 1222 ArgumentPack); 1223 NewPack 1224 = DeducedTemplateArgument(TemplateArgument(ArgumentPack, 1225 NewlyDeducedPacks[I].size()), 1226 NewlyDeducedPacks[I][0].wasDeducedFromArrayBound()); 1227 } 1228 1229 DeducedTemplateArgument Result 1230 = checkDeducedTemplateArguments(S.Context, SavedPacks[I], NewPack); 1231 if (Result.isNull()) { 1232 Info.Param 1233 = makeTemplateParameter(TemplateParams->getParam(PackIndices[I])); 1234 Info.FirstArg = SavedPacks[I]; 1235 Info.SecondArg = NewPack; 1236 return Sema::TDK_Inconsistent; 1237 } 1238 1239 Deduced[PackIndices[I]] = Result; 1240 } 1241 } 1242 1243 // If there is an argument remaining, then we had too many arguments. 1244 if (NumberOfArgumentsMustMatch && 1245 hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) 1246 return Sema::TDK_TooManyArguments; 1247 1248 return Sema::TDK_Success; 1249} 1250 1251static Sema::TemplateDeductionResult 1252DeduceTemplateArguments(Sema &S, 1253 TemplateParameterList *TemplateParams, 1254 const TemplateArgumentList &ParamList, 1255 const TemplateArgumentList &ArgList, 1256 TemplateDeductionInfo &Info, 1257 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 1258 return DeduceTemplateArguments(S, TemplateParams, 1259 ParamList.data(), ParamList.size(), 1260 ArgList.data(), ArgList.size(), 1261 Info, Deduced); 1262} 1263 1264/// \brief Determine whether two template arguments are the same. 1265static bool isSameTemplateArg(ASTContext &Context, 1266 const TemplateArgument &X, 1267 const TemplateArgument &Y) { 1268 if (X.getKind() != Y.getKind()) 1269 return false; 1270 1271 switch (X.getKind()) { 1272 case TemplateArgument::Null: 1273 assert(false && "Comparing NULL template argument"); 1274 break; 1275 1276 case TemplateArgument::Type: 1277 return Context.getCanonicalType(X.getAsType()) == 1278 Context.getCanonicalType(Y.getAsType()); 1279 1280 case TemplateArgument::Declaration: 1281 return X.getAsDecl()->getCanonicalDecl() == 1282 Y.getAsDecl()->getCanonicalDecl(); 1283 1284 case TemplateArgument::Template: 1285 return Context.getCanonicalTemplateName(X.getAsTemplate()) 1286 .getAsVoidPointer() == 1287 Context.getCanonicalTemplateName(Y.getAsTemplate()) 1288 .getAsVoidPointer(); 1289 1290 case TemplateArgument::Integral: 1291 return *X.getAsIntegral() == *Y.getAsIntegral(); 1292 1293 case TemplateArgument::Expression: { 1294 llvm::FoldingSetNodeID XID, YID; 1295 X.getAsExpr()->Profile(XID, Context, true); 1296 Y.getAsExpr()->Profile(YID, Context, true); 1297 return XID == YID; 1298 } 1299 1300 case TemplateArgument::Pack: 1301 if (X.pack_size() != Y.pack_size()) 1302 return false; 1303 1304 for (TemplateArgument::pack_iterator XP = X.pack_begin(), 1305 XPEnd = X.pack_end(), 1306 YP = Y.pack_begin(); 1307 XP != XPEnd; ++XP, ++YP) 1308 if (!isSameTemplateArg(Context, *XP, *YP)) 1309 return false; 1310 1311 return true; 1312 } 1313 1314 return false; 1315} 1316 1317/// Complete template argument deduction for a class template partial 1318/// specialization. 1319static Sema::TemplateDeductionResult 1320FinishTemplateArgumentDeduction(Sema &S, 1321 ClassTemplatePartialSpecializationDecl *Partial, 1322 const TemplateArgumentList &TemplateArgs, 1323 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1324 TemplateDeductionInfo &Info) { 1325 // Trap errors. 1326 Sema::SFINAETrap Trap(S); 1327 1328 Sema::ContextRAII SavedContext(S, Partial); 1329 1330 // C++ [temp.deduct.type]p2: 1331 // [...] or if any template argument remains neither deduced nor 1332 // explicitly specified, template argument deduction fails. 1333 // FIXME: Variadic templates Empty parameter packs? 1334 llvm::SmallVector<TemplateArgument, 4> Builder; 1335 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 1336 if (Deduced[I].isNull()) { 1337 unsigned ParamIdx = I; 1338 if (ParamIdx >= Partial->getTemplateParameters()->size()) 1339 ParamIdx = Partial->getTemplateParameters()->size() - 1; 1340 Decl *Param 1341 = const_cast<NamedDecl *>( 1342 Partial->getTemplateParameters()->getParam(ParamIdx)); 1343 Info.Param = makeTemplateParameter(Param); 1344 return Sema::TDK_Incomplete; 1345 } 1346 1347 Builder.push_back(Deduced[I]); 1348 } 1349 1350 // Form the template argument list from the deduced template arguments. 1351 TemplateArgumentList *DeducedArgumentList 1352 = TemplateArgumentList::CreateCopy(S.Context, Builder.data(), 1353 Builder.size()); 1354 1355 Info.reset(DeducedArgumentList); 1356 1357 // Substitute the deduced template arguments into the template 1358 // arguments of the class template partial specialization, and 1359 // verify that the instantiated template arguments are both valid 1360 // and are equivalent to the template arguments originally provided 1361 // to the class template. 1362 // FIXME: Do we have to correct the types of deduced non-type template 1363 // arguments (in particular, integral non-type template arguments?). 1364 LocalInstantiationScope InstScope(S); 1365 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate(); 1366 const TemplateArgumentLoc *PartialTemplateArgs 1367 = Partial->getTemplateArgsAsWritten(); 1368 1369 // Note that we don't provide the langle and rangle locations. 1370 TemplateArgumentListInfo InstArgs; 1371 1372 if (S.Subst(PartialTemplateArgs, 1373 Partial->getNumTemplateArgsAsWritten(), 1374 InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) { 1375 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx; 1376 if (ParamIdx >= Partial->getTemplateParameters()->size()) 1377 ParamIdx = Partial->getTemplateParameters()->size() - 1; 1378 1379 Decl *Param 1380 = const_cast<NamedDecl *>( 1381 Partial->getTemplateParameters()->getParam(ParamIdx)); 1382 Info.Param = makeTemplateParameter(Param); 1383 Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument(); 1384 return Sema::TDK_SubstitutionFailure; 1385 } 1386 1387 llvm::SmallVector<TemplateArgument, 4> ConvertedInstArgs; 1388 if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(), 1389 InstArgs, false, ConvertedInstArgs)) 1390 return Sema::TDK_SubstitutionFailure; 1391 1392 for (unsigned I = 0, E = ConvertedInstArgs.size(); I != E; ++I) { 1393 TemplateArgument InstArg = ConvertedInstArgs.data()[I]; 1394 1395 Decl *Param = const_cast<NamedDecl *>( 1396 ClassTemplate->getTemplateParameters()->getParam(I)); 1397 1398 if (InstArg.getKind() == TemplateArgument::Expression) { 1399 // When the argument is an expression, check the expression result 1400 // against the actual template parameter to get down to the canonical 1401 // template argument. 1402 // FIXME: Variadic templates. 1403 Expr *InstExpr = InstArg.getAsExpr(); 1404 if (NonTypeTemplateParmDecl *NTTP 1405 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 1406 if (S.CheckTemplateArgument(NTTP, NTTP->getType(), InstExpr, InstArg)) { 1407 Info.Param = makeTemplateParameter(Param); 1408 Info.FirstArg = Partial->getTemplateArgs()[I]; 1409 return Sema::TDK_SubstitutionFailure; 1410 } 1411 } 1412 } 1413 1414 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) { 1415 Info.Param = makeTemplateParameter(Param); 1416 Info.FirstArg = TemplateArgs[I]; 1417 Info.SecondArg = InstArg; 1418 return Sema::TDK_NonDeducedMismatch; 1419 } 1420 } 1421 1422 if (Trap.hasErrorOccurred()) 1423 return Sema::TDK_SubstitutionFailure; 1424 1425 return Sema::TDK_Success; 1426} 1427 1428/// \brief Perform template argument deduction to determine whether 1429/// the given template arguments match the given class template 1430/// partial specialization per C++ [temp.class.spec.match]. 1431Sema::TemplateDeductionResult 1432Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial, 1433 const TemplateArgumentList &TemplateArgs, 1434 TemplateDeductionInfo &Info) { 1435 // C++ [temp.class.spec.match]p2: 1436 // A partial specialization matches a given actual template 1437 // argument list if the template arguments of the partial 1438 // specialization can be deduced from the actual template argument 1439 // list (14.8.2). 1440 SFINAETrap Trap(*this); 1441 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 1442 Deduced.resize(Partial->getTemplateParameters()->size()); 1443 if (TemplateDeductionResult Result 1444 = ::DeduceTemplateArguments(*this, 1445 Partial->getTemplateParameters(), 1446 Partial->getTemplateArgs(), 1447 TemplateArgs, Info, Deduced)) 1448 return Result; 1449 1450 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial, 1451 Deduced.data(), Deduced.size(), Info); 1452 if (Inst) 1453 return TDK_InstantiationDepth; 1454 1455 if (Trap.hasErrorOccurred()) 1456 return Sema::TDK_SubstitutionFailure; 1457 1458 return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs, 1459 Deduced, Info); 1460} 1461 1462/// \brief Determine whether the given type T is a simple-template-id type. 1463static bool isSimpleTemplateIdType(QualType T) { 1464 if (const TemplateSpecializationType *Spec 1465 = T->getAs<TemplateSpecializationType>()) 1466 return Spec->getTemplateName().getAsTemplateDecl() != 0; 1467 1468 return false; 1469} 1470 1471/// \brief Substitute the explicitly-provided template arguments into the 1472/// given function template according to C++ [temp.arg.explicit]. 1473/// 1474/// \param FunctionTemplate the function template into which the explicit 1475/// template arguments will be substituted. 1476/// 1477/// \param ExplicitTemplateArguments the explicitly-specified template 1478/// arguments. 1479/// 1480/// \param Deduced the deduced template arguments, which will be populated 1481/// with the converted and checked explicit template arguments. 1482/// 1483/// \param ParamTypes will be populated with the instantiated function 1484/// parameters. 1485/// 1486/// \param FunctionType if non-NULL, the result type of the function template 1487/// will also be instantiated and the pointed-to value will be updated with 1488/// the instantiated function type. 1489/// 1490/// \param Info if substitution fails for any reason, this object will be 1491/// populated with more information about the failure. 1492/// 1493/// \returns TDK_Success if substitution was successful, or some failure 1494/// condition. 1495Sema::TemplateDeductionResult 1496Sema::SubstituteExplicitTemplateArguments( 1497 FunctionTemplateDecl *FunctionTemplate, 1498 const TemplateArgumentListInfo &ExplicitTemplateArgs, 1499 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1500 llvm::SmallVectorImpl<QualType> &ParamTypes, 1501 QualType *FunctionType, 1502 TemplateDeductionInfo &Info) { 1503 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1504 TemplateParameterList *TemplateParams 1505 = FunctionTemplate->getTemplateParameters(); 1506 1507 if (ExplicitTemplateArgs.size() == 0) { 1508 // No arguments to substitute; just copy over the parameter types and 1509 // fill in the function type. 1510 for (FunctionDecl::param_iterator P = Function->param_begin(), 1511 PEnd = Function->param_end(); 1512 P != PEnd; 1513 ++P) 1514 ParamTypes.push_back((*P)->getType()); 1515 1516 if (FunctionType) 1517 *FunctionType = Function->getType(); 1518 return TDK_Success; 1519 } 1520 1521 // Substitution of the explicit template arguments into a function template 1522 /// is a SFINAE context. Trap any errors that might occur. 1523 SFINAETrap Trap(*this); 1524 1525 // C++ [temp.arg.explicit]p3: 1526 // Template arguments that are present shall be specified in the 1527 // declaration order of their corresponding template-parameters. The 1528 // template argument list shall not specify more template-arguments than 1529 // there are corresponding template-parameters. 1530 llvm::SmallVector<TemplateArgument, 4> Builder; 1531 1532 // Enter a new template instantiation context where we check the 1533 // explicitly-specified template arguments against this function template, 1534 // and then substitute them into the function parameter types. 1535 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1536 FunctionTemplate, Deduced.data(), Deduced.size(), 1537 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution, 1538 Info); 1539 if (Inst) 1540 return TDK_InstantiationDepth; 1541 1542 if (CheckTemplateArgumentList(FunctionTemplate, 1543 SourceLocation(), 1544 ExplicitTemplateArgs, 1545 true, 1546 Builder) || Trap.hasErrorOccurred()) { 1547 unsigned Index = Builder.size(); 1548 if (Index >= TemplateParams->size()) 1549 Index = TemplateParams->size() - 1; 1550 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index)); 1551 return TDK_InvalidExplicitArguments; 1552 } 1553 1554 // Form the template argument list from the explicitly-specified 1555 // template arguments. 1556 TemplateArgumentList *ExplicitArgumentList 1557 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size()); 1558 Info.reset(ExplicitArgumentList); 1559 1560 // Template argument deduction and the final substitution should be 1561 // done in the context of the templated declaration. Explicit 1562 // argument substitution, on the other hand, needs to happen in the 1563 // calling context. 1564 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 1565 1566 // Instantiate the types of each of the function parameters given the 1567 // explicitly-specified template arguments. 1568 for (FunctionDecl::param_iterator P = Function->param_begin(), 1569 PEnd = Function->param_end(); 1570 P != PEnd; 1571 ++P) { 1572 QualType ParamType 1573 = SubstType((*P)->getType(), 1574 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1575 (*P)->getLocation(), (*P)->getDeclName()); 1576 if (ParamType.isNull() || Trap.hasErrorOccurred()) 1577 return TDK_SubstitutionFailure; 1578 1579 ParamTypes.push_back(ParamType); 1580 } 1581 1582 // If the caller wants a full function type back, instantiate the return 1583 // type and form that function type. 1584 if (FunctionType) { 1585 // FIXME: exception-specifications? 1586 const FunctionProtoType *Proto 1587 = Function->getType()->getAs<FunctionProtoType>(); 1588 assert(Proto && "Function template does not have a prototype?"); 1589 1590 QualType ResultType 1591 = SubstType(Proto->getResultType(), 1592 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1593 Function->getTypeSpecStartLoc(), 1594 Function->getDeclName()); 1595 if (ResultType.isNull() || Trap.hasErrorOccurred()) 1596 return TDK_SubstitutionFailure; 1597 1598 *FunctionType = BuildFunctionType(ResultType, 1599 ParamTypes.data(), ParamTypes.size(), 1600 Proto->isVariadic(), 1601 Proto->getTypeQuals(), 1602 Function->getLocation(), 1603 Function->getDeclName(), 1604 Proto->getExtInfo()); 1605 if (FunctionType->isNull() || Trap.hasErrorOccurred()) 1606 return TDK_SubstitutionFailure; 1607 } 1608 1609 // C++ [temp.arg.explicit]p2: 1610 // Trailing template arguments that can be deduced (14.8.2) may be 1611 // omitted from the list of explicit template-arguments. If all of the 1612 // template arguments can be deduced, they may all be omitted; in this 1613 // case, the empty template argument list <> itself may also be omitted. 1614 // 1615 // Take all of the explicitly-specified arguments and put them into the 1616 // set of deduced template arguments. 1617 // 1618 // FIXME: Variadic templates? 1619 Deduced.reserve(TemplateParams->size()); 1620 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) 1621 Deduced.push_back(ExplicitArgumentList->get(I)); 1622 1623 return TDK_Success; 1624} 1625 1626/// \brief Allocate a TemplateArgumentLoc where all locations have 1627/// been initialized to the given location. 1628/// 1629/// \param S The semantic analysis object. 1630/// 1631/// \param The template argument we are producing template argument 1632/// location information for. 1633/// 1634/// \param NTTPType For a declaration template argument, the type of 1635/// the non-type template parameter that corresponds to this template 1636/// argument. 1637/// 1638/// \param Loc The source location to use for the resulting template 1639/// argument. 1640static TemplateArgumentLoc 1641getTrivialTemplateArgumentLoc(Sema &S, 1642 const TemplateArgument &Arg, 1643 QualType NTTPType, 1644 SourceLocation Loc) { 1645 switch (Arg.getKind()) { 1646 case TemplateArgument::Null: 1647 llvm_unreachable("Can't get a NULL template argument here"); 1648 break; 1649 1650 case TemplateArgument::Type: 1651 return TemplateArgumentLoc(Arg, 1652 S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc)); 1653 1654 case TemplateArgument::Declaration: { 1655 Expr *E 1656 = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc) 1657 .takeAs<Expr>(); 1658 return TemplateArgumentLoc(TemplateArgument(E), E); 1659 } 1660 1661 case TemplateArgument::Integral: { 1662 Expr *E 1663 = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).takeAs<Expr>(); 1664 return TemplateArgumentLoc(TemplateArgument(E), E); 1665 } 1666 1667 case TemplateArgument::Template: 1668 return TemplateArgumentLoc(Arg, SourceRange(), Loc); 1669 1670 case TemplateArgument::Expression: 1671 return TemplateArgumentLoc(Arg, Arg.getAsExpr()); 1672 1673 case TemplateArgument::Pack: 1674 return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo()); 1675 } 1676 1677 return TemplateArgumentLoc(); 1678} 1679 1680/// \brief Finish template argument deduction for a function template, 1681/// checking the deduced template arguments for completeness and forming 1682/// the function template specialization. 1683Sema::TemplateDeductionResult 1684Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate, 1685 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1686 unsigned NumExplicitlySpecified, 1687 FunctionDecl *&Specialization, 1688 TemplateDeductionInfo &Info) { 1689 TemplateParameterList *TemplateParams 1690 = FunctionTemplate->getTemplateParameters(); 1691 1692 // Template argument deduction for function templates in a SFINAE context. 1693 // Trap any errors that might occur. 1694 SFINAETrap Trap(*this); 1695 1696 // Enter a new template instantiation context while we instantiate the 1697 // actual function declaration. 1698 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1699 FunctionTemplate, Deduced.data(), Deduced.size(), 1700 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution, 1701 Info); 1702 if (Inst) 1703 return TDK_InstantiationDepth; 1704 1705 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 1706 1707 // C++ [temp.deduct.type]p2: 1708 // [...] or if any template argument remains neither deduced nor 1709 // explicitly specified, template argument deduction fails. 1710 llvm::SmallVector<TemplateArgument, 4> Builder; 1711 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 1712 // FIXME: Variadic templates. Unwrap argument packs? 1713 NamedDecl *Param = FunctionTemplate->getTemplateParameters()->getParam(I); 1714 1715 if (!Deduced[I].isNull()) { 1716 if (I < NumExplicitlySpecified) { 1717 // We have already fully type-checked and converted this 1718 // argument, because it was explicitly-specified. Just record the 1719 // presence of this argument. 1720 Builder.push_back(Deduced[I]); 1721 continue; 1722 } 1723 1724 // We have deduced this argument, so it still needs to be 1725 // checked and converted. 1726 1727 // First, for a non-type template parameter type that is 1728 // initialized by a declaration, we need the type of the 1729 // corresponding non-type template parameter. 1730 QualType NTTPType; 1731 if (NonTypeTemplateParmDecl *NTTP 1732 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 1733 if (Deduced[I].getKind() == TemplateArgument::Declaration) { 1734 NTTPType = NTTP->getType(); 1735 if (NTTPType->isDependentType()) { 1736 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, 1737 Builder.data(), Builder.size()); 1738 NTTPType = SubstType(NTTPType, 1739 MultiLevelTemplateArgumentList(TemplateArgs), 1740 NTTP->getLocation(), 1741 NTTP->getDeclName()); 1742 if (NTTPType.isNull()) { 1743 Info.Param = makeTemplateParameter(Param); 1744 // FIXME: These template arguments are temporary. Free them! 1745 Info.reset(TemplateArgumentList::CreateCopy(Context, 1746 Builder.data(), 1747 Builder.size())); 1748 return TDK_SubstitutionFailure; 1749 } 1750 } 1751 } 1752 } 1753 1754 // Convert the deduced template argument into a template 1755 // argument that we can check, almost as if the user had written 1756 // the template argument explicitly. 1757 TemplateArgumentLoc Arg = getTrivialTemplateArgumentLoc(*this, 1758 Deduced[I], 1759 NTTPType, 1760 Info.getLocation()); 1761 1762 // Check the template argument, converting it as necessary. 1763 if (CheckTemplateArgument(Param, Arg, 1764 FunctionTemplate, 1765 FunctionTemplate->getLocation(), 1766 FunctionTemplate->getSourceRange().getEnd(), 1767 Builder, 1768 Deduced[I].wasDeducedFromArrayBound() 1769 ? CTAK_DeducedFromArrayBound 1770 : CTAK_Deduced)) { 1771 Info.Param = makeTemplateParameter( 1772 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1773 // FIXME: These template arguments are temporary. Free them! 1774 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 1775 Builder.size())); 1776 return TDK_SubstitutionFailure; 1777 } 1778 1779 continue; 1780 } 1781 1782 // C++0x [temp.arg.explicit]p3: 1783 // A trailing template parameter pack (14.5.3) not otherwise deduced will 1784 // be deduced to an empty sequence of template arguments. 1785 // FIXME: Where did the word "trailing" come from? 1786 if (Param->isTemplateParameterPack()) { 1787 Builder.push_back(TemplateArgument(0, 0)); 1788 continue; 1789 } 1790 1791 // Substitute into the default template argument, if available. 1792 TemplateArgumentLoc DefArg 1793 = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate, 1794 FunctionTemplate->getLocation(), 1795 FunctionTemplate->getSourceRange().getEnd(), 1796 Param, 1797 Builder); 1798 1799 // If there was no default argument, deduction is incomplete. 1800 if (DefArg.getArgument().isNull()) { 1801 Info.Param = makeTemplateParameter( 1802 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1803 return TDK_Incomplete; 1804 } 1805 1806 // Check whether we can actually use the default argument. 1807 if (CheckTemplateArgument(Param, DefArg, 1808 FunctionTemplate, 1809 FunctionTemplate->getLocation(), 1810 FunctionTemplate->getSourceRange().getEnd(), 1811 Builder, 1812 CTAK_Deduced)) { 1813 Info.Param = makeTemplateParameter( 1814 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1815 // FIXME: These template arguments are temporary. Free them! 1816 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 1817 Builder.size())); 1818 return TDK_SubstitutionFailure; 1819 } 1820 1821 // If we get here, we successfully used the default template argument. 1822 } 1823 1824 // Form the template argument list from the deduced template arguments. 1825 TemplateArgumentList *DeducedArgumentList 1826 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size()); 1827 Info.reset(DeducedArgumentList); 1828 1829 // Substitute the deduced template arguments into the function template 1830 // declaration to produce the function template specialization. 1831 DeclContext *Owner = FunctionTemplate->getDeclContext(); 1832 if (FunctionTemplate->getFriendObjectKind()) 1833 Owner = FunctionTemplate->getLexicalDeclContext(); 1834 Specialization = cast_or_null<FunctionDecl>( 1835 SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner, 1836 MultiLevelTemplateArgumentList(*DeducedArgumentList))); 1837 if (!Specialization) 1838 return TDK_SubstitutionFailure; 1839 1840 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() == 1841 FunctionTemplate->getCanonicalDecl()); 1842 1843 // If the template argument list is owned by the function template 1844 // specialization, release it. 1845 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList && 1846 !Trap.hasErrorOccurred()) 1847 Info.take(); 1848 1849 // There may have been an error that did not prevent us from constructing a 1850 // declaration. Mark the declaration invalid and return with a substitution 1851 // failure. 1852 if (Trap.hasErrorOccurred()) { 1853 Specialization->setInvalidDecl(true); 1854 return TDK_SubstitutionFailure; 1855 } 1856 1857 // If we suppressed any diagnostics while performing template argument 1858 // deduction, and if we haven't already instantiated this declaration, 1859 // keep track of these diagnostics. They'll be emitted if this specialization 1860 // is actually used. 1861 if (Info.diag_begin() != Info.diag_end()) { 1862 llvm::DenseMap<Decl *, llvm::SmallVector<PartialDiagnosticAt, 1> >::iterator 1863 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl()); 1864 if (Pos == SuppressedDiagnostics.end()) 1865 SuppressedDiagnostics[Specialization->getCanonicalDecl()] 1866 .append(Info.diag_begin(), Info.diag_end()); 1867 } 1868 1869 return TDK_Success; 1870} 1871 1872/// Gets the type of a function for template-argument-deducton 1873/// purposes when it's considered as part of an overload set. 1874static QualType GetTypeOfFunction(ASTContext &Context, 1875 const OverloadExpr::FindResult &R, 1876 FunctionDecl *Fn) { 1877 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn)) 1878 if (Method->isInstance()) { 1879 // An instance method that's referenced in a form that doesn't 1880 // look like a member pointer is just invalid. 1881 if (!R.HasFormOfMemberPointer) return QualType(); 1882 1883 return Context.getMemberPointerType(Fn->getType(), 1884 Context.getTypeDeclType(Method->getParent()).getTypePtr()); 1885 } 1886 1887 if (!R.IsAddressOfOperand) return Fn->getType(); 1888 return Context.getPointerType(Fn->getType()); 1889} 1890 1891/// Apply the deduction rules for overload sets. 1892/// 1893/// \return the null type if this argument should be treated as an 1894/// undeduced context 1895static QualType 1896ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams, 1897 Expr *Arg, QualType ParamType, 1898 bool ParamWasReference) { 1899 1900 OverloadExpr::FindResult R = OverloadExpr::find(Arg); 1901 1902 OverloadExpr *Ovl = R.Expression; 1903 1904 // C++0x [temp.deduct.call]p4 1905 unsigned TDF = 0; 1906 if (ParamWasReference) 1907 TDF |= TDF_ParamWithReferenceType; 1908 if (R.IsAddressOfOperand) 1909 TDF |= TDF_IgnoreQualifiers; 1910 1911 // If there were explicit template arguments, we can only find 1912 // something via C++ [temp.arg.explicit]p3, i.e. if the arguments 1913 // unambiguously name a full specialization. 1914 if (Ovl->hasExplicitTemplateArgs()) { 1915 // But we can still look for an explicit specialization. 1916 if (FunctionDecl *ExplicitSpec 1917 = S.ResolveSingleFunctionTemplateSpecialization(Ovl)) 1918 return GetTypeOfFunction(S.Context, R, ExplicitSpec); 1919 return QualType(); 1920 } 1921 1922 // C++0x [temp.deduct.call]p6: 1923 // When P is a function type, pointer to function type, or pointer 1924 // to member function type: 1925 1926 if (!ParamType->isFunctionType() && 1927 !ParamType->isFunctionPointerType() && 1928 !ParamType->isMemberFunctionPointerType()) 1929 return QualType(); 1930 1931 QualType Match; 1932 for (UnresolvedSetIterator I = Ovl->decls_begin(), 1933 E = Ovl->decls_end(); I != E; ++I) { 1934 NamedDecl *D = (*I)->getUnderlyingDecl(); 1935 1936 // - If the argument is an overload set containing one or more 1937 // function templates, the parameter is treated as a 1938 // non-deduced context. 1939 if (isa<FunctionTemplateDecl>(D)) 1940 return QualType(); 1941 1942 FunctionDecl *Fn = cast<FunctionDecl>(D); 1943 QualType ArgType = GetTypeOfFunction(S.Context, R, Fn); 1944 if (ArgType.isNull()) continue; 1945 1946 // Function-to-pointer conversion. 1947 if (!ParamWasReference && ParamType->isPointerType() && 1948 ArgType->isFunctionType()) 1949 ArgType = S.Context.getPointerType(ArgType); 1950 1951 // - If the argument is an overload set (not containing function 1952 // templates), trial argument deduction is attempted using each 1953 // of the members of the set. If deduction succeeds for only one 1954 // of the overload set members, that member is used as the 1955 // argument value for the deduction. If deduction succeeds for 1956 // more than one member of the overload set the parameter is 1957 // treated as a non-deduced context. 1958 1959 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2: 1960 // Type deduction is done independently for each P/A pair, and 1961 // the deduced template argument values are then combined. 1962 // So we do not reject deductions which were made elsewhere. 1963 llvm::SmallVector<DeducedTemplateArgument, 8> 1964 Deduced(TemplateParams->size()); 1965 TemplateDeductionInfo Info(S.Context, Ovl->getNameLoc()); 1966 Sema::TemplateDeductionResult Result 1967 = DeduceTemplateArguments(S, TemplateParams, 1968 ParamType, ArgType, 1969 Info, Deduced, TDF); 1970 if (Result) continue; 1971 if (!Match.isNull()) return QualType(); 1972 Match = ArgType; 1973 } 1974 1975 return Match; 1976} 1977 1978/// \brief Perform template argument deduction from a function call 1979/// (C++ [temp.deduct.call]). 1980/// 1981/// \param FunctionTemplate the function template for which we are performing 1982/// template argument deduction. 1983/// 1984/// \param ExplicitTemplateArguments the explicit template arguments provided 1985/// for this call. 1986/// 1987/// \param Args the function call arguments 1988/// 1989/// \param NumArgs the number of arguments in Args 1990/// 1991/// \param Name the name of the function being called. This is only significant 1992/// when the function template is a conversion function template, in which 1993/// case this routine will also perform template argument deduction based on 1994/// the function to which 1995/// 1996/// \param Specialization if template argument deduction was successful, 1997/// this will be set to the function template specialization produced by 1998/// template argument deduction. 1999/// 2000/// \param Info the argument will be updated to provide additional information 2001/// about template argument deduction. 2002/// 2003/// \returns the result of template argument deduction. 2004Sema::TemplateDeductionResult 2005Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2006 const TemplateArgumentListInfo *ExplicitTemplateArgs, 2007 Expr **Args, unsigned NumArgs, 2008 FunctionDecl *&Specialization, 2009 TemplateDeductionInfo &Info) { 2010 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2011 2012 // C++ [temp.deduct.call]p1: 2013 // Template argument deduction is done by comparing each function template 2014 // parameter type (call it P) with the type of the corresponding argument 2015 // of the call (call it A) as described below. 2016 unsigned CheckArgs = NumArgs; 2017 if (NumArgs < Function->getMinRequiredArguments()) 2018 return TDK_TooFewArguments; 2019 else if (NumArgs > Function->getNumParams()) { 2020 const FunctionProtoType *Proto 2021 = Function->getType()->getAs<FunctionProtoType>(); 2022 if (!Proto->isVariadic()) 2023 return TDK_TooManyArguments; 2024 2025 CheckArgs = Function->getNumParams(); 2026 } 2027 2028 // The types of the parameters from which we will perform template argument 2029 // deduction. 2030 LocalInstantiationScope InstScope(*this); 2031 TemplateParameterList *TemplateParams 2032 = FunctionTemplate->getTemplateParameters(); 2033 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2034 llvm::SmallVector<QualType, 4> ParamTypes; 2035 unsigned NumExplicitlySpecified = 0; 2036 if (ExplicitTemplateArgs) { 2037 TemplateDeductionResult Result = 2038 SubstituteExplicitTemplateArguments(FunctionTemplate, 2039 *ExplicitTemplateArgs, 2040 Deduced, 2041 ParamTypes, 2042 0, 2043 Info); 2044 if (Result) 2045 return Result; 2046 2047 NumExplicitlySpecified = Deduced.size(); 2048 } else { 2049 // Just fill in the parameter types from the function declaration. 2050 for (unsigned I = 0; I != CheckArgs; ++I) 2051 ParamTypes.push_back(Function->getParamDecl(I)->getType()); 2052 } 2053 2054 // Deduce template arguments from the function parameters. 2055 Deduced.resize(TemplateParams->size()); 2056 for (unsigned I = 0; I != CheckArgs; ++I) { 2057 QualType ParamType = ParamTypes[I]; 2058 QualType ArgType = Args[I]->getType(); 2059 2060 // C++0x [temp.deduct.call]p3: 2061 // If P is a cv-qualified type, the top level cv-qualifiers of P’s type 2062 // are ignored for type deduction. 2063 if (ParamType.getCVRQualifiers()) 2064 ParamType = ParamType.getLocalUnqualifiedType(); 2065 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>(); 2066 if (ParamRefType) { 2067 // [...] If P is a reference type, the type referred to by P is used 2068 // for type deduction. 2069 ParamType = ParamRefType->getPointeeType(); 2070 } 2071 2072 // Overload sets usually make this parameter an undeduced 2073 // context, but there are sometimes special circumstances. 2074 if (ArgType == Context.OverloadTy) { 2075 ArgType = ResolveOverloadForDeduction(*this, TemplateParams, 2076 Args[I], ParamType, 2077 ParamRefType != 0); 2078 if (ArgType.isNull()) 2079 continue; 2080 } 2081 2082 if (ParamRefType) { 2083 // C++0x [temp.deduct.call]p3: 2084 // [...] If P is of the form T&&, where T is a template parameter, and 2085 // the argument is an lvalue, the type A& is used in place of A for 2086 // type deduction. 2087 if (ParamRefType->isRValueReferenceType() && 2088 ParamRefType->getAs<TemplateTypeParmType>() && 2089 Args[I]->isLValue()) 2090 ArgType = Context.getLValueReferenceType(ArgType); 2091 } else { 2092 // C++ [temp.deduct.call]p2: 2093 // If P is not a reference type: 2094 // - If A is an array type, the pointer type produced by the 2095 // array-to-pointer standard conversion (4.2) is used in place of 2096 // A for type deduction; otherwise, 2097 if (ArgType->isArrayType()) 2098 ArgType = Context.getArrayDecayedType(ArgType); 2099 // - If A is a function type, the pointer type produced by the 2100 // function-to-pointer standard conversion (4.3) is used in place 2101 // of A for type deduction; otherwise, 2102 else if (ArgType->isFunctionType()) 2103 ArgType = Context.getPointerType(ArgType); 2104 else { 2105 // - If A is a cv-qualified type, the top level cv-qualifiers of A’s 2106 // type are ignored for type deduction. 2107 QualType CanonArgType = Context.getCanonicalType(ArgType); 2108 if (ArgType.getCVRQualifiers()) 2109 ArgType = ArgType.getUnqualifiedType(); 2110 } 2111 } 2112 2113 // C++0x [temp.deduct.call]p4: 2114 // In general, the deduction process attempts to find template argument 2115 // values that will make the deduced A identical to A (after the type A 2116 // is transformed as described above). [...] 2117 unsigned TDF = TDF_SkipNonDependent; 2118 2119 // - If the original P is a reference type, the deduced A (i.e., the 2120 // type referred to by the reference) can be more cv-qualified than 2121 // the transformed A. 2122 if (ParamRefType) 2123 TDF |= TDF_ParamWithReferenceType; 2124 // - The transformed A can be another pointer or pointer to member 2125 // type that can be converted to the deduced A via a qualification 2126 // conversion (4.4). 2127 if (ArgType->isPointerType() || ArgType->isMemberPointerType() || 2128 ArgType->isObjCObjectPointerType()) 2129 TDF |= TDF_IgnoreQualifiers; 2130 // - If P is a class and P has the form simple-template-id, then the 2131 // transformed A can be a derived class of the deduced A. Likewise, 2132 // if P is a pointer to a class of the form simple-template-id, the 2133 // transformed A can be a pointer to a derived class pointed to by 2134 // the deduced A. 2135 if (isSimpleTemplateIdType(ParamType) || 2136 (isa<PointerType>(ParamType) && 2137 isSimpleTemplateIdType( 2138 ParamType->getAs<PointerType>()->getPointeeType()))) 2139 TDF |= TDF_DerivedClass; 2140 2141 if (TemplateDeductionResult Result 2142 = ::DeduceTemplateArguments(*this, TemplateParams, 2143 ParamType, ArgType, Info, Deduced, 2144 TDF)) 2145 return Result; 2146 2147 // FIXME: we need to check that the deduced A is the same as A, 2148 // modulo the various allowed differences. 2149 } 2150 2151 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 2152 NumExplicitlySpecified, 2153 Specialization, Info); 2154} 2155 2156/// \brief Deduce template arguments when taking the address of a function 2157/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to 2158/// a template. 2159/// 2160/// \param FunctionTemplate the function template for which we are performing 2161/// template argument deduction. 2162/// 2163/// \param ExplicitTemplateArguments the explicitly-specified template 2164/// arguments. 2165/// 2166/// \param ArgFunctionType the function type that will be used as the 2167/// "argument" type (A) when performing template argument deduction from the 2168/// function template's function type. This type may be NULL, if there is no 2169/// argument type to compare against, in C++0x [temp.arg.explicit]p3. 2170/// 2171/// \param Specialization if template argument deduction was successful, 2172/// this will be set to the function template specialization produced by 2173/// template argument deduction. 2174/// 2175/// \param Info the argument will be updated to provide additional information 2176/// about template argument deduction. 2177/// 2178/// \returns the result of template argument deduction. 2179Sema::TemplateDeductionResult 2180Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2181 const TemplateArgumentListInfo *ExplicitTemplateArgs, 2182 QualType ArgFunctionType, 2183 FunctionDecl *&Specialization, 2184 TemplateDeductionInfo &Info) { 2185 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2186 TemplateParameterList *TemplateParams 2187 = FunctionTemplate->getTemplateParameters(); 2188 QualType FunctionType = Function->getType(); 2189 2190 // Substitute any explicit template arguments. 2191 LocalInstantiationScope InstScope(*this); 2192 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2193 unsigned NumExplicitlySpecified = 0; 2194 llvm::SmallVector<QualType, 4> ParamTypes; 2195 if (ExplicitTemplateArgs) { 2196 if (TemplateDeductionResult Result 2197 = SubstituteExplicitTemplateArguments(FunctionTemplate, 2198 *ExplicitTemplateArgs, 2199 Deduced, ParamTypes, 2200 &FunctionType, Info)) 2201 return Result; 2202 2203 NumExplicitlySpecified = Deduced.size(); 2204 } 2205 2206 // Template argument deduction for function templates in a SFINAE context. 2207 // Trap any errors that might occur. 2208 SFINAETrap Trap(*this); 2209 2210 Deduced.resize(TemplateParams->size()); 2211 2212 if (!ArgFunctionType.isNull()) { 2213 // Deduce template arguments from the function type. 2214 if (TemplateDeductionResult Result 2215 = ::DeduceTemplateArguments(*this, TemplateParams, 2216 FunctionType, ArgFunctionType, Info, 2217 Deduced, 0)) 2218 return Result; 2219 } 2220 2221 if (TemplateDeductionResult Result 2222 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 2223 NumExplicitlySpecified, 2224 Specialization, Info)) 2225 return Result; 2226 2227 // If the requested function type does not match the actual type of the 2228 // specialization, template argument deduction fails. 2229 if (!ArgFunctionType.isNull() && 2230 !Context.hasSameType(ArgFunctionType, Specialization->getType())) 2231 return TDK_NonDeducedMismatch; 2232 2233 return TDK_Success; 2234} 2235 2236/// \brief Deduce template arguments for a templated conversion 2237/// function (C++ [temp.deduct.conv]) and, if successful, produce a 2238/// conversion function template specialization. 2239Sema::TemplateDeductionResult 2240Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2241 QualType ToType, 2242 CXXConversionDecl *&Specialization, 2243 TemplateDeductionInfo &Info) { 2244 CXXConversionDecl *Conv 2245 = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl()); 2246 QualType FromType = Conv->getConversionType(); 2247 2248 // Canonicalize the types for deduction. 2249 QualType P = Context.getCanonicalType(FromType); 2250 QualType A = Context.getCanonicalType(ToType); 2251 2252 // C++0x [temp.deduct.conv]p3: 2253 // If P is a reference type, the type referred to by P is used for 2254 // type deduction. 2255 if (const ReferenceType *PRef = P->getAs<ReferenceType>()) 2256 P = PRef->getPointeeType(); 2257 2258 // C++0x [temp.deduct.conv]p3: 2259 // If A is a reference type, the type referred to by A is used 2260 // for type deduction. 2261 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 2262 A = ARef->getPointeeType(); 2263 // C++ [temp.deduct.conv]p2: 2264 // 2265 // If A is not a reference type: 2266 else { 2267 assert(!A->isReferenceType() && "Reference types were handled above"); 2268 2269 // - If P is an array type, the pointer type produced by the 2270 // array-to-pointer standard conversion (4.2) is used in place 2271 // of P for type deduction; otherwise, 2272 if (P->isArrayType()) 2273 P = Context.getArrayDecayedType(P); 2274 // - If P is a function type, the pointer type produced by the 2275 // function-to-pointer standard conversion (4.3) is used in 2276 // place of P for type deduction; otherwise, 2277 else if (P->isFunctionType()) 2278 P = Context.getPointerType(P); 2279 // - If P is a cv-qualified type, the top level cv-qualifiers of 2280 // P’s type are ignored for type deduction. 2281 else 2282 P = P.getUnqualifiedType(); 2283 2284 // C++0x [temp.deduct.conv]p3: 2285 // If A is a cv-qualified type, the top level cv-qualifiers of A’s 2286 // type are ignored for type deduction. 2287 A = A.getUnqualifiedType(); 2288 } 2289 2290 // Template argument deduction for function templates in a SFINAE context. 2291 // Trap any errors that might occur. 2292 SFINAETrap Trap(*this); 2293 2294 // C++ [temp.deduct.conv]p1: 2295 // Template argument deduction is done by comparing the return 2296 // type of the template conversion function (call it P) with the 2297 // type that is required as the result of the conversion (call it 2298 // A) as described in 14.8.2.4. 2299 TemplateParameterList *TemplateParams 2300 = FunctionTemplate->getTemplateParameters(); 2301 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2302 Deduced.resize(TemplateParams->size()); 2303 2304 // C++0x [temp.deduct.conv]p4: 2305 // In general, the deduction process attempts to find template 2306 // argument values that will make the deduced A identical to 2307 // A. However, there are two cases that allow a difference: 2308 unsigned TDF = 0; 2309 // - If the original A is a reference type, A can be more 2310 // cv-qualified than the deduced A (i.e., the type referred to 2311 // by the reference) 2312 if (ToType->isReferenceType()) 2313 TDF |= TDF_ParamWithReferenceType; 2314 // - The deduced A can be another pointer or pointer to member 2315 // type that can be converted to A via a qualification 2316 // conversion. 2317 // 2318 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 2319 // both P and A are pointers or member pointers. In this case, we 2320 // just ignore cv-qualifiers completely). 2321 if ((P->isPointerType() && A->isPointerType()) || 2322 (P->isMemberPointerType() && P->isMemberPointerType())) 2323 TDF |= TDF_IgnoreQualifiers; 2324 if (TemplateDeductionResult Result 2325 = ::DeduceTemplateArguments(*this, TemplateParams, 2326 P, A, Info, Deduced, TDF)) 2327 return Result; 2328 2329 // FIXME: we need to check that the deduced A is the same as A, 2330 // modulo the various allowed differences. 2331 2332 // Finish template argument deduction. 2333 LocalInstantiationScope InstScope(*this); 2334 FunctionDecl *Spec = 0; 2335 TemplateDeductionResult Result 2336 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec, 2337 Info); 2338 Specialization = cast_or_null<CXXConversionDecl>(Spec); 2339 return Result; 2340} 2341 2342/// \brief Deduce template arguments for a function template when there is 2343/// nothing to deduce against (C++0x [temp.arg.explicit]p3). 2344/// 2345/// \param FunctionTemplate the function template for which we are performing 2346/// template argument deduction. 2347/// 2348/// \param ExplicitTemplateArguments the explicitly-specified template 2349/// arguments. 2350/// 2351/// \param Specialization if template argument deduction was successful, 2352/// this will be set to the function template specialization produced by 2353/// template argument deduction. 2354/// 2355/// \param Info the argument will be updated to provide additional information 2356/// about template argument deduction. 2357/// 2358/// \returns the result of template argument deduction. 2359Sema::TemplateDeductionResult 2360Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2361 const TemplateArgumentListInfo *ExplicitTemplateArgs, 2362 FunctionDecl *&Specialization, 2363 TemplateDeductionInfo &Info) { 2364 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs, 2365 QualType(), Specialization, Info); 2366} 2367 2368/// \brief Stores the result of comparing the qualifiers of two types. 2369enum DeductionQualifierComparison { 2370 NeitherMoreQualified = 0, 2371 ParamMoreQualified, 2372 ArgMoreQualified 2373}; 2374 2375/// \brief Deduce the template arguments during partial ordering by comparing 2376/// the parameter type and the argument type (C++0x [temp.deduct.partial]). 2377/// 2378/// \param S the semantic analysis object within which we are deducing 2379/// 2380/// \param TemplateParams the template parameters that we are deducing 2381/// 2382/// \param ParamIn the parameter type 2383/// 2384/// \param ArgIn the argument type 2385/// 2386/// \param Info information about the template argument deduction itself 2387/// 2388/// \param Deduced the deduced template arguments 2389/// 2390/// \returns the result of template argument deduction so far. Note that a 2391/// "success" result means that template argument deduction has not yet failed, 2392/// but it may still fail, later, for other reasons. 2393static Sema::TemplateDeductionResult 2394DeduceTemplateArgumentsDuringPartialOrdering(Sema &S, 2395 TemplateParameterList *TemplateParams, 2396 QualType ParamIn, QualType ArgIn, 2397 TemplateDeductionInfo &Info, 2398 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2399 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 2400 CanQualType Param = S.Context.getCanonicalType(ParamIn); 2401 CanQualType Arg = S.Context.getCanonicalType(ArgIn); 2402 2403 // C++0x [temp.deduct.partial]p5: 2404 // Before the partial ordering is done, certain transformations are 2405 // performed on the types used for partial ordering: 2406 // - If P is a reference type, P is replaced by the type referred to. 2407 CanQual<ReferenceType> ParamRef = Param->getAs<ReferenceType>(); 2408 if (!ParamRef.isNull()) 2409 Param = ParamRef->getPointeeType(); 2410 2411 // - If A is a reference type, A is replaced by the type referred to. 2412 CanQual<ReferenceType> ArgRef = Arg->getAs<ReferenceType>(); 2413 if (!ArgRef.isNull()) 2414 Arg = ArgRef->getPointeeType(); 2415 2416 if (QualifierComparisons && !ParamRef.isNull() && !ArgRef.isNull()) { 2417 // C++0x [temp.deduct.partial]p6: 2418 // If both P and A were reference types (before being replaced with the 2419 // type referred to above), determine which of the two types (if any) is 2420 // more cv-qualified than the other; otherwise the types are considered to 2421 // be equally cv-qualified for partial ordering purposes. The result of this 2422 // determination will be used below. 2423 // 2424 // We save this information for later, using it only when deduction 2425 // succeeds in both directions. 2426 DeductionQualifierComparison QualifierResult = NeitherMoreQualified; 2427 if (Param.isMoreQualifiedThan(Arg)) 2428 QualifierResult = ParamMoreQualified; 2429 else if (Arg.isMoreQualifiedThan(Param)) 2430 QualifierResult = ArgMoreQualified; 2431 QualifierComparisons->push_back(QualifierResult); 2432 } 2433 2434 // C++0x [temp.deduct.partial]p7: 2435 // Remove any top-level cv-qualifiers: 2436 // - If P is a cv-qualified type, P is replaced by the cv-unqualified 2437 // version of P. 2438 Param = Param.getUnqualifiedType(); 2439 // - If A is a cv-qualified type, A is replaced by the cv-unqualified 2440 // version of A. 2441 Arg = Arg.getUnqualifiedType(); 2442 2443 // C++0x [temp.deduct.partial]p8: 2444 // Using the resulting types P and A the deduction is then done as 2445 // described in 14.9.2.5. If deduction succeeds for a given type, the type 2446 // from the argument template is considered to be at least as specialized 2447 // as the type from the parameter template. 2448 return DeduceTemplateArguments(S, TemplateParams, Param, Arg, Info, 2449 Deduced, TDF_None); 2450} 2451 2452static void 2453MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 2454 bool OnlyDeduced, 2455 unsigned Level, 2456 llvm::SmallVectorImpl<bool> &Deduced); 2457 2458/// \brief If this is a non-static member function, 2459static void MaybeAddImplicitObjectParameterType(ASTContext &Context, 2460 CXXMethodDecl *Method, 2461 llvm::SmallVectorImpl<QualType> &ArgTypes) { 2462 if (Method->isStatic()) 2463 return; 2464 2465 // C++ [over.match.funcs]p4: 2466 // 2467 // For non-static member functions, the type of the implicit 2468 // object parameter is 2469 // — "lvalue reference to cv X" for functions declared without a 2470 // ref-qualifier or with the & ref-qualifier 2471 // - "rvalue reference to cv X" for functions declared with the 2472 // && ref-qualifier 2473 // 2474 // FIXME: We don't have ref-qualifiers yet, so we don't do that part. 2475 QualType ArgTy = Context.getTypeDeclType(Method->getParent()); 2476 ArgTy = Context.getQualifiedType(ArgTy, 2477 Qualifiers::fromCVRMask(Method->getTypeQualifiers())); 2478 ArgTy = Context.getLValueReferenceType(ArgTy); 2479 ArgTypes.push_back(ArgTy); 2480} 2481 2482/// \brief Determine whether the function template \p FT1 is at least as 2483/// specialized as \p FT2. 2484static bool isAtLeastAsSpecializedAs(Sema &S, 2485 SourceLocation Loc, 2486 FunctionTemplateDecl *FT1, 2487 FunctionTemplateDecl *FT2, 2488 TemplatePartialOrderingContext TPOC, 2489 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 2490 FunctionDecl *FD1 = FT1->getTemplatedDecl(); 2491 FunctionDecl *FD2 = FT2->getTemplatedDecl(); 2492 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 2493 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 2494 2495 assert(Proto1 && Proto2 && "Function templates must have prototypes"); 2496 TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 2497 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2498 Deduced.resize(TemplateParams->size()); 2499 2500 // C++0x [temp.deduct.partial]p3: 2501 // The types used to determine the ordering depend on the context in which 2502 // the partial ordering is done: 2503 TemplateDeductionInfo Info(S.Context, Loc); 2504 CXXMethodDecl *Method1 = 0; 2505 CXXMethodDecl *Method2 = 0; 2506 bool IsNonStatic2 = false; 2507 bool IsNonStatic1 = false; 2508 unsigned Skip2 = 0; 2509 switch (TPOC) { 2510 case TPOC_Call: { 2511 // - In the context of a function call, the function parameter types are 2512 // used. 2513 Method1 = dyn_cast<CXXMethodDecl>(FD1); 2514 Method2 = dyn_cast<CXXMethodDecl>(FD2); 2515 IsNonStatic1 = Method1 && !Method1->isStatic(); 2516 IsNonStatic2 = Method2 && !Method2->isStatic(); 2517 2518 // C++0x [temp.func.order]p3: 2519 // [...] If only one of the function templates is a non-static 2520 // member, that function template is considered to have a new 2521 // first parameter inserted in its function parameter list. The 2522 // new parameter is of type "reference to cv A," where cv are 2523 // the cv-qualifiers of the function template (if any) and A is 2524 // the class of which the function template is a member. 2525 // 2526 // C++98/03 doesn't have this provision, so instead we drop the 2527 // first argument of the free function or static member, which 2528 // seems to match existing practice. 2529 llvm::SmallVector<QualType, 4> Args1; 2530 unsigned Skip1 = !S.getLangOptions().CPlusPlus0x && 2531 IsNonStatic2 && !IsNonStatic1; 2532 if (S.getLangOptions().CPlusPlus0x && IsNonStatic1 && !IsNonStatic2) 2533 MaybeAddImplicitObjectParameterType(S.Context, Method1, Args1); 2534 Args1.insert(Args1.end(), 2535 Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end()); 2536 2537 llvm::SmallVector<QualType, 4> Args2; 2538 Skip2 = !S.getLangOptions().CPlusPlus0x && 2539 IsNonStatic1 && !IsNonStatic2; 2540 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1) 2541 MaybeAddImplicitObjectParameterType(S.Context, Method2, Args2); 2542 Args2.insert(Args2.end(), 2543 Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end()); 2544 2545 unsigned NumParams = std::min(Args1.size(), Args2.size()); 2546 for (unsigned I = 0; I != NumParams; ++I) 2547 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 2548 TemplateParams, 2549 Args2[I], 2550 Args1[I], 2551 Info, 2552 Deduced, 2553 QualifierComparisons)) 2554 return false; 2555 2556 break; 2557 } 2558 2559 case TPOC_Conversion: 2560 // - In the context of a call to a conversion operator, the return types 2561 // of the conversion function templates are used. 2562 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 2563 TemplateParams, 2564 Proto2->getResultType(), 2565 Proto1->getResultType(), 2566 Info, 2567 Deduced, 2568 QualifierComparisons)) 2569 return false; 2570 break; 2571 2572 case TPOC_Other: 2573 // - In other contexts (14.6.6.2) the function template’s function type 2574 // is used. 2575 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 2576 TemplateParams, 2577 FD2->getType(), 2578 FD1->getType(), 2579 Info, 2580 Deduced, 2581 QualifierComparisons)) 2582 return false; 2583 break; 2584 } 2585 2586 // C++0x [temp.deduct.partial]p11: 2587 // In most cases, all template parameters must have values in order for 2588 // deduction to succeed, but for partial ordering purposes a template 2589 // parameter may remain without a value provided it is not used in the 2590 // types being used for partial ordering. [ Note: a template parameter used 2591 // in a non-deduced context is considered used. -end note] 2592 unsigned ArgIdx = 0, NumArgs = Deduced.size(); 2593 for (; ArgIdx != NumArgs; ++ArgIdx) 2594 if (Deduced[ArgIdx].isNull()) 2595 break; 2596 2597 if (ArgIdx == NumArgs) { 2598 // All template arguments were deduced. FT1 is at least as specialized 2599 // as FT2. 2600 return true; 2601 } 2602 2603 // Figure out which template parameters were used. 2604 llvm::SmallVector<bool, 4> UsedParameters; 2605 UsedParameters.resize(TemplateParams->size()); 2606 switch (TPOC) { 2607 case TPOC_Call: { 2608 unsigned NumParams = std::min(Proto1->getNumArgs(), Proto2->getNumArgs()); 2609 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1) 2610 ::MarkUsedTemplateParameters(S, Method2->getThisType(S.Context), false, 2611 TemplateParams->getDepth(), UsedParameters); 2612 for (unsigned I = Skip2; I < NumParams; ++I) 2613 ::MarkUsedTemplateParameters(S, Proto2->getArgType(I), false, 2614 TemplateParams->getDepth(), 2615 UsedParameters); 2616 break; 2617 } 2618 2619 case TPOC_Conversion: 2620 ::MarkUsedTemplateParameters(S, Proto2->getResultType(), false, 2621 TemplateParams->getDepth(), 2622 UsedParameters); 2623 break; 2624 2625 case TPOC_Other: 2626 ::MarkUsedTemplateParameters(S, FD2->getType(), false, 2627 TemplateParams->getDepth(), 2628 UsedParameters); 2629 break; 2630 } 2631 2632 for (; ArgIdx != NumArgs; ++ArgIdx) 2633 // If this argument had no value deduced but was used in one of the types 2634 // used for partial ordering, then deduction fails. 2635 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 2636 return false; 2637 2638 return true; 2639} 2640 2641 2642/// \brief Returns the more specialized function template according 2643/// to the rules of function template partial ordering (C++ [temp.func.order]). 2644/// 2645/// \param FT1 the first function template 2646/// 2647/// \param FT2 the second function template 2648/// 2649/// \param TPOC the context in which we are performing partial ordering of 2650/// function templates. 2651/// 2652/// \returns the more specialized function template. If neither 2653/// template is more specialized, returns NULL. 2654FunctionTemplateDecl * 2655Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, 2656 FunctionTemplateDecl *FT2, 2657 SourceLocation Loc, 2658 TemplatePartialOrderingContext TPOC) { 2659 llvm::SmallVector<DeductionQualifierComparison, 4> QualifierComparisons; 2660 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC, 0); 2661 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC, 2662 &QualifierComparisons); 2663 2664 if (Better1 != Better2) // We have a clear winner 2665 return Better1? FT1 : FT2; 2666 2667 if (!Better1 && !Better2) // Neither is better than the other 2668 return 0; 2669 2670 2671 // C++0x [temp.deduct.partial]p10: 2672 // If for each type being considered a given template is at least as 2673 // specialized for all types and more specialized for some set of types and 2674 // the other template is not more specialized for any types or is not at 2675 // least as specialized for any types, then the given template is more 2676 // specialized than the other template. Otherwise, neither template is more 2677 // specialized than the other. 2678 Better1 = false; 2679 Better2 = false; 2680 for (unsigned I = 0, N = QualifierComparisons.size(); I != N; ++I) { 2681 // C++0x [temp.deduct.partial]p9: 2682 // If, for a given type, deduction succeeds in both directions (i.e., the 2683 // types are identical after the transformations above) and if the type 2684 // from the argument template is more cv-qualified than the type from the 2685 // parameter template (as described above) that type is considered to be 2686 // more specialized than the other. If neither type is more cv-qualified 2687 // than the other then neither type is more specialized than the other. 2688 switch (QualifierComparisons[I]) { 2689 case NeitherMoreQualified: 2690 break; 2691 2692 case ParamMoreQualified: 2693 Better1 = true; 2694 if (Better2) 2695 return 0; 2696 break; 2697 2698 case ArgMoreQualified: 2699 Better2 = true; 2700 if (Better1) 2701 return 0; 2702 break; 2703 } 2704 } 2705 2706 assert(!(Better1 && Better2) && "Should have broken out in the loop above"); 2707 if (Better1) 2708 return FT1; 2709 else if (Better2) 2710 return FT2; 2711 else 2712 return 0; 2713} 2714 2715/// \brief Determine if the two templates are equivalent. 2716static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) { 2717 if (T1 == T2) 2718 return true; 2719 2720 if (!T1 || !T2) 2721 return false; 2722 2723 return T1->getCanonicalDecl() == T2->getCanonicalDecl(); 2724} 2725 2726/// \brief Retrieve the most specialized of the given function template 2727/// specializations. 2728/// 2729/// \param SpecBegin the start iterator of the function template 2730/// specializations that we will be comparing. 2731/// 2732/// \param SpecEnd the end iterator of the function template 2733/// specializations, paired with \p SpecBegin. 2734/// 2735/// \param TPOC the partial ordering context to use to compare the function 2736/// template specializations. 2737/// 2738/// \param Loc the location where the ambiguity or no-specializations 2739/// diagnostic should occur. 2740/// 2741/// \param NoneDiag partial diagnostic used to diagnose cases where there are 2742/// no matching candidates. 2743/// 2744/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one 2745/// occurs. 2746/// 2747/// \param CandidateDiag partial diagnostic used for each function template 2748/// specialization that is a candidate in the ambiguous ordering. One parameter 2749/// in this diagnostic should be unbound, which will correspond to the string 2750/// describing the template arguments for the function template specialization. 2751/// 2752/// \param Index if non-NULL and the result of this function is non-nULL, 2753/// receives the index corresponding to the resulting function template 2754/// specialization. 2755/// 2756/// \returns the most specialized function template specialization, if 2757/// found. Otherwise, returns SpecEnd. 2758/// 2759/// \todo FIXME: Consider passing in the "also-ran" candidates that failed 2760/// template argument deduction. 2761UnresolvedSetIterator 2762Sema::getMostSpecialized(UnresolvedSetIterator SpecBegin, 2763 UnresolvedSetIterator SpecEnd, 2764 TemplatePartialOrderingContext TPOC, 2765 SourceLocation Loc, 2766 const PartialDiagnostic &NoneDiag, 2767 const PartialDiagnostic &AmbigDiag, 2768 const PartialDiagnostic &CandidateDiag) { 2769 if (SpecBegin == SpecEnd) { 2770 Diag(Loc, NoneDiag); 2771 return SpecEnd; 2772 } 2773 2774 if (SpecBegin + 1 == SpecEnd) 2775 return SpecBegin; 2776 2777 // Find the function template that is better than all of the templates it 2778 // has been compared to. 2779 UnresolvedSetIterator Best = SpecBegin; 2780 FunctionTemplateDecl *BestTemplate 2781 = cast<FunctionDecl>(*Best)->getPrimaryTemplate(); 2782 assert(BestTemplate && "Not a function template specialization?"); 2783 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) { 2784 FunctionTemplateDecl *Challenger 2785 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 2786 assert(Challenger && "Not a function template specialization?"); 2787 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 2788 Loc, TPOC), 2789 Challenger)) { 2790 Best = I; 2791 BestTemplate = Challenger; 2792 } 2793 } 2794 2795 // Make sure that the "best" function template is more specialized than all 2796 // of the others. 2797 bool Ambiguous = false; 2798 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 2799 FunctionTemplateDecl *Challenger 2800 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 2801 if (I != Best && 2802 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 2803 Loc, TPOC), 2804 BestTemplate)) { 2805 Ambiguous = true; 2806 break; 2807 } 2808 } 2809 2810 if (!Ambiguous) { 2811 // We found an answer. Return it. 2812 return Best; 2813 } 2814 2815 // Diagnose the ambiguity. 2816 Diag(Loc, AmbigDiag); 2817 2818 // FIXME: Can we order the candidates in some sane way? 2819 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) 2820 Diag((*I)->getLocation(), CandidateDiag) 2821 << getTemplateArgumentBindingsText( 2822 cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(), 2823 *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs()); 2824 2825 return SpecEnd; 2826} 2827 2828/// \brief Returns the more specialized class template partial specialization 2829/// according to the rules of partial ordering of class template partial 2830/// specializations (C++ [temp.class.order]). 2831/// 2832/// \param PS1 the first class template partial specialization 2833/// 2834/// \param PS2 the second class template partial specialization 2835/// 2836/// \returns the more specialized class template partial specialization. If 2837/// neither partial specialization is more specialized, returns NULL. 2838ClassTemplatePartialSpecializationDecl * 2839Sema::getMoreSpecializedPartialSpecialization( 2840 ClassTemplatePartialSpecializationDecl *PS1, 2841 ClassTemplatePartialSpecializationDecl *PS2, 2842 SourceLocation Loc) { 2843 // C++ [temp.class.order]p1: 2844 // For two class template partial specializations, the first is at least as 2845 // specialized as the second if, given the following rewrite to two 2846 // function templates, the first function template is at least as 2847 // specialized as the second according to the ordering rules for function 2848 // templates (14.6.6.2): 2849 // - the first function template has the same template parameters as the 2850 // first partial specialization and has a single function parameter 2851 // whose type is a class template specialization with the template 2852 // arguments of the first partial specialization, and 2853 // - the second function template has the same template parameters as the 2854 // second partial specialization and has a single function parameter 2855 // whose type is a class template specialization with the template 2856 // arguments of the second partial specialization. 2857 // 2858 // Rather than synthesize function templates, we merely perform the 2859 // equivalent partial ordering by performing deduction directly on 2860 // the template arguments of the class template partial 2861 // specializations. This computation is slightly simpler than the 2862 // general problem of function template partial ordering, because 2863 // class template partial specializations are more constrained. We 2864 // know that every template parameter is deducible from the class 2865 // template partial specialization's template arguments, for 2866 // example. 2867 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2868 TemplateDeductionInfo Info(Context, Loc); 2869 2870 QualType PT1 = PS1->getInjectedSpecializationType(); 2871 QualType PT2 = PS2->getInjectedSpecializationType(); 2872 2873 // Determine whether PS1 is at least as specialized as PS2 2874 Deduced.resize(PS2->getTemplateParameters()->size()); 2875 bool Better1 = !DeduceTemplateArgumentsDuringPartialOrdering(*this, 2876 PS2->getTemplateParameters(), 2877 PT2, 2878 PT1, 2879 Info, 2880 Deduced, 2881 0); 2882 if (Better1) { 2883 InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2, 2884 Deduced.data(), Deduced.size(), Info); 2885 Better1 = !::FinishTemplateArgumentDeduction(*this, PS2, 2886 PS1->getTemplateArgs(), 2887 Deduced, Info); 2888 } 2889 2890 // Determine whether PS2 is at least as specialized as PS1 2891 Deduced.clear(); 2892 Deduced.resize(PS1->getTemplateParameters()->size()); 2893 bool Better2 = !DeduceTemplateArgumentsDuringPartialOrdering(*this, 2894 PS1->getTemplateParameters(), 2895 PT1, 2896 PT2, 2897 Info, 2898 Deduced, 2899 0); 2900 if (Better2) { 2901 InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1, 2902 Deduced.data(), Deduced.size(), Info); 2903 Better2 = !::FinishTemplateArgumentDeduction(*this, PS1, 2904 PS2->getTemplateArgs(), 2905 Deduced, Info); 2906 } 2907 2908 if (Better1 == Better2) 2909 return 0; 2910 2911 return Better1? PS1 : PS2; 2912} 2913 2914static void 2915MarkUsedTemplateParameters(Sema &SemaRef, 2916 const TemplateArgument &TemplateArg, 2917 bool OnlyDeduced, 2918 unsigned Depth, 2919 llvm::SmallVectorImpl<bool> &Used); 2920 2921/// \brief Mark the template parameters that are used by the given 2922/// expression. 2923static void 2924MarkUsedTemplateParameters(Sema &SemaRef, 2925 const Expr *E, 2926 bool OnlyDeduced, 2927 unsigned Depth, 2928 llvm::SmallVectorImpl<bool> &Used) { 2929 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to 2930 // find other occurrences of template parameters. 2931 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E); 2932 if (!DRE) 2933 return; 2934 2935 const NonTypeTemplateParmDecl *NTTP 2936 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 2937 if (!NTTP) 2938 return; 2939 2940 if (NTTP->getDepth() == Depth) 2941 Used[NTTP->getIndex()] = true; 2942} 2943 2944/// \brief Mark the template parameters that are used by the given 2945/// nested name specifier. 2946static void 2947MarkUsedTemplateParameters(Sema &SemaRef, 2948 NestedNameSpecifier *NNS, 2949 bool OnlyDeduced, 2950 unsigned Depth, 2951 llvm::SmallVectorImpl<bool> &Used) { 2952 if (!NNS) 2953 return; 2954 2955 MarkUsedTemplateParameters(SemaRef, NNS->getPrefix(), OnlyDeduced, Depth, 2956 Used); 2957 MarkUsedTemplateParameters(SemaRef, QualType(NNS->getAsType(), 0), 2958 OnlyDeduced, Depth, Used); 2959} 2960 2961/// \brief Mark the template parameters that are used by the given 2962/// template name. 2963static void 2964MarkUsedTemplateParameters(Sema &SemaRef, 2965 TemplateName Name, 2966 bool OnlyDeduced, 2967 unsigned Depth, 2968 llvm::SmallVectorImpl<bool> &Used) { 2969 if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 2970 if (TemplateTemplateParmDecl *TTP 2971 = dyn_cast<TemplateTemplateParmDecl>(Template)) { 2972 if (TTP->getDepth() == Depth) 2973 Used[TTP->getIndex()] = true; 2974 } 2975 return; 2976 } 2977 2978 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) 2979 MarkUsedTemplateParameters(SemaRef, QTN->getQualifier(), OnlyDeduced, 2980 Depth, Used); 2981 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 2982 MarkUsedTemplateParameters(SemaRef, DTN->getQualifier(), OnlyDeduced, 2983 Depth, Used); 2984} 2985 2986/// \brief Mark the template parameters that are used by the given 2987/// type. 2988static void 2989MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 2990 bool OnlyDeduced, 2991 unsigned Depth, 2992 llvm::SmallVectorImpl<bool> &Used) { 2993 if (T.isNull()) 2994 return; 2995 2996 // Non-dependent types have nothing deducible 2997 if (!T->isDependentType()) 2998 return; 2999 3000 T = SemaRef.Context.getCanonicalType(T); 3001 switch (T->getTypeClass()) { 3002 case Type::Pointer: 3003 MarkUsedTemplateParameters(SemaRef, 3004 cast<PointerType>(T)->getPointeeType(), 3005 OnlyDeduced, 3006 Depth, 3007 Used); 3008 break; 3009 3010 case Type::BlockPointer: 3011 MarkUsedTemplateParameters(SemaRef, 3012 cast<BlockPointerType>(T)->getPointeeType(), 3013 OnlyDeduced, 3014 Depth, 3015 Used); 3016 break; 3017 3018 case Type::LValueReference: 3019 case Type::RValueReference: 3020 MarkUsedTemplateParameters(SemaRef, 3021 cast<ReferenceType>(T)->getPointeeType(), 3022 OnlyDeduced, 3023 Depth, 3024 Used); 3025 break; 3026 3027 case Type::MemberPointer: { 3028 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 3029 MarkUsedTemplateParameters(SemaRef, MemPtr->getPointeeType(), OnlyDeduced, 3030 Depth, Used); 3031 MarkUsedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0), 3032 OnlyDeduced, Depth, Used); 3033 break; 3034 } 3035 3036 case Type::DependentSizedArray: 3037 MarkUsedTemplateParameters(SemaRef, 3038 cast<DependentSizedArrayType>(T)->getSizeExpr(), 3039 OnlyDeduced, Depth, Used); 3040 // Fall through to check the element type 3041 3042 case Type::ConstantArray: 3043 case Type::IncompleteArray: 3044 MarkUsedTemplateParameters(SemaRef, 3045 cast<ArrayType>(T)->getElementType(), 3046 OnlyDeduced, Depth, Used); 3047 break; 3048 3049 case Type::Vector: 3050 case Type::ExtVector: 3051 MarkUsedTemplateParameters(SemaRef, 3052 cast<VectorType>(T)->getElementType(), 3053 OnlyDeduced, Depth, Used); 3054 break; 3055 3056 case Type::DependentSizedExtVector: { 3057 const DependentSizedExtVectorType *VecType 3058 = cast<DependentSizedExtVectorType>(T); 3059 MarkUsedTemplateParameters(SemaRef, VecType->getElementType(), OnlyDeduced, 3060 Depth, Used); 3061 MarkUsedTemplateParameters(SemaRef, VecType->getSizeExpr(), OnlyDeduced, 3062 Depth, Used); 3063 break; 3064 } 3065 3066 case Type::FunctionProto: { 3067 const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 3068 MarkUsedTemplateParameters(SemaRef, Proto->getResultType(), OnlyDeduced, 3069 Depth, Used); 3070 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I) 3071 MarkUsedTemplateParameters(SemaRef, Proto->getArgType(I), OnlyDeduced, 3072 Depth, Used); 3073 break; 3074 } 3075 3076 case Type::TemplateTypeParm: { 3077 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T); 3078 if (TTP->getDepth() == Depth) 3079 Used[TTP->getIndex()] = true; 3080 break; 3081 } 3082 3083 case Type::InjectedClassName: 3084 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType(); 3085 // fall through 3086 3087 case Type::TemplateSpecialization: { 3088 const TemplateSpecializationType *Spec 3089 = cast<TemplateSpecializationType>(T); 3090 MarkUsedTemplateParameters(SemaRef, Spec->getTemplateName(), OnlyDeduced, 3091 Depth, Used); 3092 3093 // C++0x [temp.deduct.type]p9: 3094 // If the template argument list of P contains a pack expansion that is not 3095 // the last template argument, the entire template argument list is a 3096 // non-deduced context. 3097 if (OnlyDeduced && 3098 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 3099 break; 3100 3101 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 3102 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 3103 Used); 3104 break; 3105 } 3106 3107 case Type::Complex: 3108 if (!OnlyDeduced) 3109 MarkUsedTemplateParameters(SemaRef, 3110 cast<ComplexType>(T)->getElementType(), 3111 OnlyDeduced, Depth, Used); 3112 break; 3113 3114 case Type::DependentName: 3115 if (!OnlyDeduced) 3116 MarkUsedTemplateParameters(SemaRef, 3117 cast<DependentNameType>(T)->getQualifier(), 3118 OnlyDeduced, Depth, Used); 3119 break; 3120 3121 case Type::DependentTemplateSpecialization: { 3122 const DependentTemplateSpecializationType *Spec 3123 = cast<DependentTemplateSpecializationType>(T); 3124 if (!OnlyDeduced) 3125 MarkUsedTemplateParameters(SemaRef, Spec->getQualifier(), 3126 OnlyDeduced, Depth, Used); 3127 3128 // C++0x [temp.deduct.type]p9: 3129 // If the template argument list of P contains a pack expansion that is not 3130 // the last template argument, the entire template argument list is a 3131 // non-deduced context. 3132 if (OnlyDeduced && 3133 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 3134 break; 3135 3136 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 3137 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 3138 Used); 3139 break; 3140 } 3141 3142 case Type::TypeOf: 3143 if (!OnlyDeduced) 3144 MarkUsedTemplateParameters(SemaRef, 3145 cast<TypeOfType>(T)->getUnderlyingType(), 3146 OnlyDeduced, Depth, Used); 3147 break; 3148 3149 case Type::TypeOfExpr: 3150 if (!OnlyDeduced) 3151 MarkUsedTemplateParameters(SemaRef, 3152 cast<TypeOfExprType>(T)->getUnderlyingExpr(), 3153 OnlyDeduced, Depth, Used); 3154 break; 3155 3156 case Type::Decltype: 3157 if (!OnlyDeduced) 3158 MarkUsedTemplateParameters(SemaRef, 3159 cast<DecltypeType>(T)->getUnderlyingExpr(), 3160 OnlyDeduced, Depth, Used); 3161 break; 3162 3163 case Type::PackExpansion: 3164 MarkUsedTemplateParameters(SemaRef, 3165 cast<PackExpansionType>(T)->getPattern(), 3166 OnlyDeduced, Depth, Used); 3167 break; 3168 3169 // None of these types have any template parameters in them. 3170 case Type::Builtin: 3171 case Type::VariableArray: 3172 case Type::FunctionNoProto: 3173 case Type::Record: 3174 case Type::Enum: 3175 case Type::ObjCInterface: 3176 case Type::ObjCObject: 3177 case Type::ObjCObjectPointer: 3178 case Type::UnresolvedUsing: 3179#define TYPE(Class, Base) 3180#define ABSTRACT_TYPE(Class, Base) 3181#define DEPENDENT_TYPE(Class, Base) 3182#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 3183#include "clang/AST/TypeNodes.def" 3184 break; 3185 } 3186} 3187 3188/// \brief Mark the template parameters that are used by this 3189/// template argument. 3190static void 3191MarkUsedTemplateParameters(Sema &SemaRef, 3192 const TemplateArgument &TemplateArg, 3193 bool OnlyDeduced, 3194 unsigned Depth, 3195 llvm::SmallVectorImpl<bool> &Used) { 3196 switch (TemplateArg.getKind()) { 3197 case TemplateArgument::Null: 3198 case TemplateArgument::Integral: 3199 case TemplateArgument::Declaration: 3200 break; 3201 3202 case TemplateArgument::Type: 3203 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsType(), OnlyDeduced, 3204 Depth, Used); 3205 break; 3206 3207 case TemplateArgument::Template: 3208 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsTemplate(), 3209 OnlyDeduced, Depth, Used); 3210 break; 3211 3212 case TemplateArgument::Expression: 3213 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsExpr(), OnlyDeduced, 3214 Depth, Used); 3215 break; 3216 3217 case TemplateArgument::Pack: 3218 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(), 3219 PEnd = TemplateArg.pack_end(); 3220 P != PEnd; ++P) 3221 MarkUsedTemplateParameters(SemaRef, *P, OnlyDeduced, Depth, Used); 3222 break; 3223 } 3224} 3225 3226/// \brief Mark the template parameters can be deduced by the given 3227/// template argument list. 3228/// 3229/// \param TemplateArgs the template argument list from which template 3230/// parameters will be deduced. 3231/// 3232/// \param Deduced a bit vector whose elements will be set to \c true 3233/// to indicate when the corresponding template parameter will be 3234/// deduced. 3235void 3236Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 3237 bool OnlyDeduced, unsigned Depth, 3238 llvm::SmallVectorImpl<bool> &Used) { 3239 // C++0x [temp.deduct.type]p9: 3240 // If the template argument list of P contains a pack expansion that is not 3241 // the last template argument, the entire template argument list is a 3242 // non-deduced context. 3243 if (OnlyDeduced && 3244 hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size())) 3245 return; 3246 3247 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 3248 ::MarkUsedTemplateParameters(*this, TemplateArgs[I], OnlyDeduced, 3249 Depth, Used); 3250} 3251 3252/// \brief Marks all of the template parameters that will be deduced by a 3253/// call to the given function template. 3254void 3255Sema::MarkDeducedTemplateParameters(FunctionTemplateDecl *FunctionTemplate, 3256 llvm::SmallVectorImpl<bool> &Deduced) { 3257 TemplateParameterList *TemplateParams 3258 = FunctionTemplate->getTemplateParameters(); 3259 Deduced.clear(); 3260 Deduced.resize(TemplateParams->size()); 3261 3262 // FIXME: Variadic templates. 3263 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 3264 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 3265 ::MarkUsedTemplateParameters(*this, Function->getParamDecl(I)->getType(), 3266 true, TemplateParams->getDepth(), Deduced); 3267} 3268