SemaTemplateDeduction.cpp revision 34c2f8c8a16226f757947bf08c5f799d99c9ac1e
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 1062static Sema::TemplateDeductionResult 1063DeduceTemplateArguments(Sema &S, 1064 TemplateParameterList *TemplateParams, 1065 const TemplateArgument *Params, unsigned NumParams, 1066 const TemplateArgument *Args, unsigned NumArgs, 1067 TemplateDeductionInfo &Info, 1068 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1069 bool NumberOfArgumentsMustMatch) { 1070 // C++0x [temp.deduct.type]p9: 1071 // If the template argument list of P contains a pack expansion that is not 1072 // the last template argument, the entire template argument list is a 1073 // non-deduced context. 1074 // FIXME: Implement this. 1075 1076 1077 // C++0x [temp.deduct.type]p9: 1078 // If P has a form that contains <T> or <i>, then each argument Pi of the 1079 // respective template argument list P is compared with the corresponding 1080 // argument Ai of the corresponding template argument list of A. 1081 unsigned ArgIdx = 0, ParamIdx = 0; 1082 for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams); 1083 ++ParamIdx) { 1084 // FIXME: Variadic templates. 1085 // What do we do if the argument is a pack expansion? 1086 1087 if (!Params[ParamIdx].isPackExpansion()) { 1088 // The simple case: deduce template arguments by matching Pi and Ai. 1089 1090 // Check whether we have enough arguments. 1091 if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) 1092 return NumberOfArgumentsMustMatch? Sema::TDK_TooFewArguments 1093 : Sema::TDK_Success; 1094 1095 // Perform deduction for this Pi/Ai pair. 1096 if (Sema::TemplateDeductionResult Result 1097 = DeduceTemplateArguments(S, TemplateParams, 1098 Params[ParamIdx], Args[ArgIdx], 1099 Info, Deduced)) 1100 return Result; 1101 1102 // Move to the next argument. 1103 ++ArgIdx; 1104 continue; 1105 } 1106 1107 // The parameter is a pack expansion. 1108 1109 // C++0x [temp.deduct.type]p9: 1110 // If Pi is a pack expansion, then the pattern of Pi is compared with 1111 // each remaining argument in the template argument list of A. Each 1112 // comparison deduces template arguments for subsequent positions in the 1113 // template parameter packs expanded by Pi. 1114 TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern(); 1115 1116 // Compute the set of template parameter indices that correspond to 1117 // parameter packs expanded by the pack expansion. 1118 llvm::SmallVector<unsigned, 2> PackIndices; 1119 { 1120 llvm::BitVector SawIndices(TemplateParams->size()); 1121 llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded; 1122 S.collectUnexpandedParameterPacks(Pattern, Unexpanded); 1123 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) { 1124 unsigned Depth, Index; 1125 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]); 1126 if (Depth == 0 && !SawIndices[Index]) { 1127 SawIndices[Index] = true; 1128 PackIndices.push_back(Index); 1129 } 1130 } 1131 } 1132 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?"); 1133 1134 // FIXME: If there are no remaining arguments, we can bail out early 1135 // and set any deduced parameter packs to an empty argument pack. 1136 // The latter part of this is a (minor) correctness issue. 1137 1138 // Save the deduced template arguments for each parameter pack expanded 1139 // by this pack expansion, then clear out the deduction. 1140 llvm::SmallVector<DeducedTemplateArgument, 2> 1141 SavedPacks(PackIndices.size()); 1142 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 1143 SavedPacks[I] = Deduced[PackIndices[I]]; 1144 Deduced[PackIndices[I]] = DeducedTemplateArgument(); 1145 } 1146 1147 // Keep track of the deduced template arguments for each parameter pack 1148 // expanded by this pack expansion (the outer index) and for each 1149 // template argument (the inner SmallVectors). 1150 llvm::SmallVector<llvm::SmallVector<DeducedTemplateArgument, 4>, 2> 1151 NewlyDeducedPacks(PackIndices.size()); 1152 bool HasAnyArguments = false; 1153 while (hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) { 1154 HasAnyArguments = true; 1155 1156 // Deduce template arguments from the pattern. 1157 if (Sema::TemplateDeductionResult Result 1158 = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx], 1159 Info, Deduced)) 1160 return Result; 1161 1162 // Capture the deduced template arguments for each parameter pack expanded 1163 // by this pack expansion, add them to the list of arguments we've deduced 1164 // for that pack, then clear out the deduced argument. 1165 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 1166 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]]; 1167 if (!DeducedArg.isNull()) { 1168 NewlyDeducedPacks[I].push_back(DeducedArg); 1169 DeducedArg = DeducedTemplateArgument(); 1170 } 1171 } 1172 1173 ++ArgIdx; 1174 } 1175 1176 // Build argument packs for each of the parameter packs expanded by this 1177 // pack expansion. 1178 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 1179 if (HasAnyArguments && NewlyDeducedPacks[I].empty()) { 1180 // We were not able to deduce anything for this parameter pack, 1181 // so just restore the saved argument pack. 1182 Deduced[PackIndices[I]] = SavedPacks[I]; 1183 continue; 1184 } 1185 1186 DeducedTemplateArgument NewPack; 1187 1188 if (NewlyDeducedPacks[I].empty()) { 1189 // If we deduced an empty argument pack, create it now. 1190 NewPack = DeducedTemplateArgument(TemplateArgument(0, 0)); 1191 } else { 1192 TemplateArgument *ArgumentPack 1193 = new (S.Context) TemplateArgument [NewlyDeducedPacks[I].size()]; 1194 std::copy(NewlyDeducedPacks[I].begin(), NewlyDeducedPacks[I].end(), 1195 ArgumentPack); 1196 NewPack 1197 = DeducedTemplateArgument(TemplateArgument(ArgumentPack, 1198 NewlyDeducedPacks[I].size()), 1199 NewlyDeducedPacks[I][0].wasDeducedFromArrayBound()); 1200 } 1201 1202 DeducedTemplateArgument Result 1203 = checkDeducedTemplateArguments(S.Context, SavedPacks[I], NewPack); 1204 if (Result.isNull()) { 1205 Info.Param 1206 = makeTemplateParameter(TemplateParams->getParam(PackIndices[I])); 1207 Info.FirstArg = SavedPacks[I]; 1208 Info.SecondArg = NewPack; 1209 return Sema::TDK_Inconsistent; 1210 } 1211 1212 Deduced[PackIndices[I]] = Result; 1213 } 1214 } 1215 1216 // If there is an argument remaining, then we had too many arguments. 1217 if (NumberOfArgumentsMustMatch && 1218 hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) 1219 return Sema::TDK_TooManyArguments; 1220 1221 return Sema::TDK_Success; 1222} 1223 1224static Sema::TemplateDeductionResult 1225DeduceTemplateArguments(Sema &S, 1226 TemplateParameterList *TemplateParams, 1227 const TemplateArgumentList &ParamList, 1228 const TemplateArgumentList &ArgList, 1229 TemplateDeductionInfo &Info, 1230 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 1231 return DeduceTemplateArguments(S, TemplateParams, 1232 ParamList.data(), ParamList.size(), 1233 ArgList.data(), ArgList.size(), 1234 Info, Deduced); 1235} 1236 1237/// \brief Determine whether two template arguments are the same. 1238static bool isSameTemplateArg(ASTContext &Context, 1239 const TemplateArgument &X, 1240 const TemplateArgument &Y) { 1241 if (X.getKind() != Y.getKind()) 1242 return false; 1243 1244 switch (X.getKind()) { 1245 case TemplateArgument::Null: 1246 assert(false && "Comparing NULL template argument"); 1247 break; 1248 1249 case TemplateArgument::Type: 1250 return Context.getCanonicalType(X.getAsType()) == 1251 Context.getCanonicalType(Y.getAsType()); 1252 1253 case TemplateArgument::Declaration: 1254 return X.getAsDecl()->getCanonicalDecl() == 1255 Y.getAsDecl()->getCanonicalDecl(); 1256 1257 case TemplateArgument::Template: 1258 return Context.getCanonicalTemplateName(X.getAsTemplate()) 1259 .getAsVoidPointer() == 1260 Context.getCanonicalTemplateName(Y.getAsTemplate()) 1261 .getAsVoidPointer(); 1262 1263 case TemplateArgument::Integral: 1264 return *X.getAsIntegral() == *Y.getAsIntegral(); 1265 1266 case TemplateArgument::Expression: { 1267 llvm::FoldingSetNodeID XID, YID; 1268 X.getAsExpr()->Profile(XID, Context, true); 1269 Y.getAsExpr()->Profile(YID, Context, true); 1270 return XID == YID; 1271 } 1272 1273 case TemplateArgument::Pack: 1274 if (X.pack_size() != Y.pack_size()) 1275 return false; 1276 1277 for (TemplateArgument::pack_iterator XP = X.pack_begin(), 1278 XPEnd = X.pack_end(), 1279 YP = Y.pack_begin(); 1280 XP != XPEnd; ++XP, ++YP) 1281 if (!isSameTemplateArg(Context, *XP, *YP)) 1282 return false; 1283 1284 return true; 1285 } 1286 1287 return false; 1288} 1289 1290/// Complete template argument deduction for a class template partial 1291/// specialization. 1292static Sema::TemplateDeductionResult 1293FinishTemplateArgumentDeduction(Sema &S, 1294 ClassTemplatePartialSpecializationDecl *Partial, 1295 const TemplateArgumentList &TemplateArgs, 1296 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1297 TemplateDeductionInfo &Info) { 1298 // Trap errors. 1299 Sema::SFINAETrap Trap(S); 1300 1301 Sema::ContextRAII SavedContext(S, Partial); 1302 1303 // C++ [temp.deduct.type]p2: 1304 // [...] or if any template argument remains neither deduced nor 1305 // explicitly specified, template argument deduction fails. 1306 // FIXME: Variadic templates Empty parameter packs? 1307 llvm::SmallVector<TemplateArgument, 4> Builder; 1308 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 1309 if (Deduced[I].isNull()) { 1310 unsigned ParamIdx = I; 1311 if (ParamIdx >= Partial->getTemplateParameters()->size()) 1312 ParamIdx = Partial->getTemplateParameters()->size() - 1; 1313 Decl *Param 1314 = const_cast<NamedDecl *>( 1315 Partial->getTemplateParameters()->getParam(ParamIdx)); 1316 Info.Param = makeTemplateParameter(Param); 1317 return Sema::TDK_Incomplete; 1318 } 1319 1320 Builder.push_back(Deduced[I]); 1321 } 1322 1323 // Form the template argument list from the deduced template arguments. 1324 TemplateArgumentList *DeducedArgumentList 1325 = TemplateArgumentList::CreateCopy(S.Context, Builder.data(), 1326 Builder.size()); 1327 1328 Info.reset(DeducedArgumentList); 1329 1330 // Substitute the deduced template arguments into the template 1331 // arguments of the class template partial specialization, and 1332 // verify that the instantiated template arguments are both valid 1333 // and are equivalent to the template arguments originally provided 1334 // to the class template. 1335 // FIXME: Do we have to correct the types of deduced non-type template 1336 // arguments (in particular, integral non-type template arguments?). 1337 LocalInstantiationScope InstScope(S); 1338 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate(); 1339 const TemplateArgumentLoc *PartialTemplateArgs 1340 = Partial->getTemplateArgsAsWritten(); 1341 1342 // Note that we don't provide the langle and rangle locations. 1343 TemplateArgumentListInfo InstArgs; 1344 1345 if (S.Subst(PartialTemplateArgs, 1346 Partial->getNumTemplateArgsAsWritten(), 1347 InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) { 1348 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx; 1349 if (ParamIdx >= Partial->getTemplateParameters()->size()) 1350 ParamIdx = Partial->getTemplateParameters()->size() - 1; 1351 1352 Decl *Param 1353 = const_cast<NamedDecl *>( 1354 Partial->getTemplateParameters()->getParam(ParamIdx)); 1355 Info.Param = makeTemplateParameter(Param); 1356 Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument(); 1357 return Sema::TDK_SubstitutionFailure; 1358 } 1359 1360 llvm::SmallVector<TemplateArgument, 4> ConvertedInstArgs; 1361 if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(), 1362 InstArgs, false, ConvertedInstArgs)) 1363 return Sema::TDK_SubstitutionFailure; 1364 1365 for (unsigned I = 0, E = ConvertedInstArgs.size(); I != E; ++I) { 1366 TemplateArgument InstArg = ConvertedInstArgs.data()[I]; 1367 1368 Decl *Param = const_cast<NamedDecl *>( 1369 ClassTemplate->getTemplateParameters()->getParam(I)); 1370 1371 if (InstArg.getKind() == TemplateArgument::Expression) { 1372 // When the argument is an expression, check the expression result 1373 // against the actual template parameter to get down to the canonical 1374 // template argument. 1375 // FIXME: Variadic templates. 1376 Expr *InstExpr = InstArg.getAsExpr(); 1377 if (NonTypeTemplateParmDecl *NTTP 1378 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 1379 if (S.CheckTemplateArgument(NTTP, NTTP->getType(), InstExpr, InstArg)) { 1380 Info.Param = makeTemplateParameter(Param); 1381 Info.FirstArg = Partial->getTemplateArgs()[I]; 1382 return Sema::TDK_SubstitutionFailure; 1383 } 1384 } 1385 } 1386 1387 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) { 1388 Info.Param = makeTemplateParameter(Param); 1389 Info.FirstArg = TemplateArgs[I]; 1390 Info.SecondArg = InstArg; 1391 return Sema::TDK_NonDeducedMismatch; 1392 } 1393 } 1394 1395 if (Trap.hasErrorOccurred()) 1396 return Sema::TDK_SubstitutionFailure; 1397 1398 return Sema::TDK_Success; 1399} 1400 1401/// \brief Perform template argument deduction to determine whether 1402/// the given template arguments match the given class template 1403/// partial specialization per C++ [temp.class.spec.match]. 1404Sema::TemplateDeductionResult 1405Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial, 1406 const TemplateArgumentList &TemplateArgs, 1407 TemplateDeductionInfo &Info) { 1408 // C++ [temp.class.spec.match]p2: 1409 // A partial specialization matches a given actual template 1410 // argument list if the template arguments of the partial 1411 // specialization can be deduced from the actual template argument 1412 // list (14.8.2). 1413 SFINAETrap Trap(*this); 1414 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 1415 Deduced.resize(Partial->getTemplateParameters()->size()); 1416 if (TemplateDeductionResult Result 1417 = ::DeduceTemplateArguments(*this, 1418 Partial->getTemplateParameters(), 1419 Partial->getTemplateArgs(), 1420 TemplateArgs, Info, Deduced)) 1421 return Result; 1422 1423 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial, 1424 Deduced.data(), Deduced.size(), Info); 1425 if (Inst) 1426 return TDK_InstantiationDepth; 1427 1428 if (Trap.hasErrorOccurred()) 1429 return Sema::TDK_SubstitutionFailure; 1430 1431 return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs, 1432 Deduced, Info); 1433} 1434 1435/// \brief Determine whether the given type T is a simple-template-id type. 1436static bool isSimpleTemplateIdType(QualType T) { 1437 if (const TemplateSpecializationType *Spec 1438 = T->getAs<TemplateSpecializationType>()) 1439 return Spec->getTemplateName().getAsTemplateDecl() != 0; 1440 1441 return false; 1442} 1443 1444/// \brief Substitute the explicitly-provided template arguments into the 1445/// given function template according to C++ [temp.arg.explicit]. 1446/// 1447/// \param FunctionTemplate the function template into which the explicit 1448/// template arguments will be substituted. 1449/// 1450/// \param ExplicitTemplateArguments the explicitly-specified template 1451/// arguments. 1452/// 1453/// \param Deduced the deduced template arguments, which will be populated 1454/// with the converted and checked explicit template arguments. 1455/// 1456/// \param ParamTypes will be populated with the instantiated function 1457/// parameters. 1458/// 1459/// \param FunctionType if non-NULL, the result type of the function template 1460/// will also be instantiated and the pointed-to value will be updated with 1461/// the instantiated function type. 1462/// 1463/// \param Info if substitution fails for any reason, this object will be 1464/// populated with more information about the failure. 1465/// 1466/// \returns TDK_Success if substitution was successful, or some failure 1467/// condition. 1468Sema::TemplateDeductionResult 1469Sema::SubstituteExplicitTemplateArguments( 1470 FunctionTemplateDecl *FunctionTemplate, 1471 const TemplateArgumentListInfo &ExplicitTemplateArgs, 1472 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1473 llvm::SmallVectorImpl<QualType> &ParamTypes, 1474 QualType *FunctionType, 1475 TemplateDeductionInfo &Info) { 1476 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1477 TemplateParameterList *TemplateParams 1478 = FunctionTemplate->getTemplateParameters(); 1479 1480 if (ExplicitTemplateArgs.size() == 0) { 1481 // No arguments to substitute; just copy over the parameter types and 1482 // fill in the function type. 1483 for (FunctionDecl::param_iterator P = Function->param_begin(), 1484 PEnd = Function->param_end(); 1485 P != PEnd; 1486 ++P) 1487 ParamTypes.push_back((*P)->getType()); 1488 1489 if (FunctionType) 1490 *FunctionType = Function->getType(); 1491 return TDK_Success; 1492 } 1493 1494 // Substitution of the explicit template arguments into a function template 1495 /// is a SFINAE context. Trap any errors that might occur. 1496 SFINAETrap Trap(*this); 1497 1498 // C++ [temp.arg.explicit]p3: 1499 // Template arguments that are present shall be specified in the 1500 // declaration order of their corresponding template-parameters. The 1501 // template argument list shall not specify more template-arguments than 1502 // there are corresponding template-parameters. 1503 llvm::SmallVector<TemplateArgument, 4> Builder; 1504 1505 // Enter a new template instantiation context where we check the 1506 // explicitly-specified template arguments against this function template, 1507 // and then substitute them into the function parameter types. 1508 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1509 FunctionTemplate, Deduced.data(), Deduced.size(), 1510 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution, 1511 Info); 1512 if (Inst) 1513 return TDK_InstantiationDepth; 1514 1515 if (CheckTemplateArgumentList(FunctionTemplate, 1516 SourceLocation(), 1517 ExplicitTemplateArgs, 1518 true, 1519 Builder) || Trap.hasErrorOccurred()) { 1520 unsigned Index = Builder.size(); 1521 if (Index >= TemplateParams->size()) 1522 Index = TemplateParams->size() - 1; 1523 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index)); 1524 return TDK_InvalidExplicitArguments; 1525 } 1526 1527 // Form the template argument list from the explicitly-specified 1528 // template arguments. 1529 TemplateArgumentList *ExplicitArgumentList 1530 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size()); 1531 Info.reset(ExplicitArgumentList); 1532 1533 // Template argument deduction and the final substitution should be 1534 // done in the context of the templated declaration. Explicit 1535 // argument substitution, on the other hand, needs to happen in the 1536 // calling context. 1537 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 1538 1539 // Instantiate the types of each of the function parameters given the 1540 // explicitly-specified template arguments. 1541 for (FunctionDecl::param_iterator P = Function->param_begin(), 1542 PEnd = Function->param_end(); 1543 P != PEnd; 1544 ++P) { 1545 QualType ParamType 1546 = SubstType((*P)->getType(), 1547 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1548 (*P)->getLocation(), (*P)->getDeclName()); 1549 if (ParamType.isNull() || Trap.hasErrorOccurred()) 1550 return TDK_SubstitutionFailure; 1551 1552 ParamTypes.push_back(ParamType); 1553 } 1554 1555 // If the caller wants a full function type back, instantiate the return 1556 // type and form that function type. 1557 if (FunctionType) { 1558 // FIXME: exception-specifications? 1559 const FunctionProtoType *Proto 1560 = Function->getType()->getAs<FunctionProtoType>(); 1561 assert(Proto && "Function template does not have a prototype?"); 1562 1563 QualType ResultType 1564 = SubstType(Proto->getResultType(), 1565 MultiLevelTemplateArgumentList(*ExplicitArgumentList), 1566 Function->getTypeSpecStartLoc(), 1567 Function->getDeclName()); 1568 if (ResultType.isNull() || Trap.hasErrorOccurred()) 1569 return TDK_SubstitutionFailure; 1570 1571 *FunctionType = BuildFunctionType(ResultType, 1572 ParamTypes.data(), ParamTypes.size(), 1573 Proto->isVariadic(), 1574 Proto->getTypeQuals(), 1575 Function->getLocation(), 1576 Function->getDeclName(), 1577 Proto->getExtInfo()); 1578 if (FunctionType->isNull() || Trap.hasErrorOccurred()) 1579 return TDK_SubstitutionFailure; 1580 } 1581 1582 // C++ [temp.arg.explicit]p2: 1583 // Trailing template arguments that can be deduced (14.8.2) may be 1584 // omitted from the list of explicit template-arguments. If all of the 1585 // template arguments can be deduced, they may all be omitted; in this 1586 // case, the empty template argument list <> itself may also be omitted. 1587 // 1588 // Take all of the explicitly-specified arguments and put them into the 1589 // set of deduced template arguments. 1590 // 1591 // FIXME: Variadic templates? 1592 Deduced.reserve(TemplateParams->size()); 1593 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) 1594 Deduced.push_back(ExplicitArgumentList->get(I)); 1595 1596 return TDK_Success; 1597} 1598 1599/// \brief Allocate a TemplateArgumentLoc where all locations have 1600/// been initialized to the given location. 1601/// 1602/// \param S The semantic analysis object. 1603/// 1604/// \param The template argument we are producing template argument 1605/// location information for. 1606/// 1607/// \param NTTPType For a declaration template argument, the type of 1608/// the non-type template parameter that corresponds to this template 1609/// argument. 1610/// 1611/// \param Loc The source location to use for the resulting template 1612/// argument. 1613static TemplateArgumentLoc 1614getTrivialTemplateArgumentLoc(Sema &S, 1615 const TemplateArgument &Arg, 1616 QualType NTTPType, 1617 SourceLocation Loc) { 1618 switch (Arg.getKind()) { 1619 case TemplateArgument::Null: 1620 llvm_unreachable("Can't get a NULL template argument here"); 1621 break; 1622 1623 case TemplateArgument::Type: 1624 return TemplateArgumentLoc(Arg, 1625 S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc)); 1626 1627 case TemplateArgument::Declaration: { 1628 Expr *E 1629 = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc) 1630 .takeAs<Expr>(); 1631 return TemplateArgumentLoc(TemplateArgument(E), E); 1632 } 1633 1634 case TemplateArgument::Integral: { 1635 Expr *E 1636 = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).takeAs<Expr>(); 1637 return TemplateArgumentLoc(TemplateArgument(E), E); 1638 } 1639 1640 case TemplateArgument::Template: 1641 return TemplateArgumentLoc(Arg, SourceRange(), Loc); 1642 1643 case TemplateArgument::Expression: 1644 return TemplateArgumentLoc(Arg, Arg.getAsExpr()); 1645 1646 case TemplateArgument::Pack: 1647 return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo()); 1648 } 1649 1650 return TemplateArgumentLoc(); 1651} 1652 1653/// \brief Finish template argument deduction for a function template, 1654/// checking the deduced template arguments for completeness and forming 1655/// the function template specialization. 1656Sema::TemplateDeductionResult 1657Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate, 1658 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1659 unsigned NumExplicitlySpecified, 1660 FunctionDecl *&Specialization, 1661 TemplateDeductionInfo &Info) { 1662 TemplateParameterList *TemplateParams 1663 = FunctionTemplate->getTemplateParameters(); 1664 1665 // Template argument deduction for function templates in a SFINAE context. 1666 // Trap any errors that might occur. 1667 SFINAETrap Trap(*this); 1668 1669 // Enter a new template instantiation context while we instantiate the 1670 // actual function declaration. 1671 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 1672 FunctionTemplate, Deduced.data(), Deduced.size(), 1673 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution, 1674 Info); 1675 if (Inst) 1676 return TDK_InstantiationDepth; 1677 1678 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 1679 1680 // C++ [temp.deduct.type]p2: 1681 // [...] or if any template argument remains neither deduced nor 1682 // explicitly specified, template argument deduction fails. 1683 llvm::SmallVector<TemplateArgument, 4> Builder; 1684 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 1685 // FIXME: Variadic templates. Unwrap argument packs? 1686 NamedDecl *Param = FunctionTemplate->getTemplateParameters()->getParam(I); 1687 if (!Deduced[I].isNull()) { 1688 if (I < NumExplicitlySpecified) { 1689 // We have already fully type-checked and converted this 1690 // argument, because it was explicitly-specified. Just record the 1691 // presence of this argument. 1692 Builder.push_back(Deduced[I]); 1693 continue; 1694 } 1695 1696 // We have deduced this argument, so it still needs to be 1697 // checked and converted. 1698 1699 // First, for a non-type template parameter type that is 1700 // initialized by a declaration, we need the type of the 1701 // corresponding non-type template parameter. 1702 QualType NTTPType; 1703 if (NonTypeTemplateParmDecl *NTTP 1704 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 1705 if (Deduced[I].getKind() == TemplateArgument::Declaration) { 1706 NTTPType = NTTP->getType(); 1707 if (NTTPType->isDependentType()) { 1708 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, 1709 Builder.data(), Builder.size()); 1710 NTTPType = SubstType(NTTPType, 1711 MultiLevelTemplateArgumentList(TemplateArgs), 1712 NTTP->getLocation(), 1713 NTTP->getDeclName()); 1714 if (NTTPType.isNull()) { 1715 Info.Param = makeTemplateParameter(Param); 1716 // FIXME: These template arguments are temporary. Free them! 1717 Info.reset(TemplateArgumentList::CreateCopy(Context, 1718 Builder.data(), 1719 Builder.size())); 1720 return TDK_SubstitutionFailure; 1721 } 1722 } 1723 } 1724 } 1725 1726 // Convert the deduced template argument into a template 1727 // argument that we can check, almost as if the user had written 1728 // the template argument explicitly. 1729 TemplateArgumentLoc Arg = getTrivialTemplateArgumentLoc(*this, 1730 Deduced[I], 1731 NTTPType, 1732 Info.getLocation()); 1733 1734 // Check the template argument, converting it as necessary. 1735 if (CheckTemplateArgument(Param, Arg, 1736 FunctionTemplate, 1737 FunctionTemplate->getLocation(), 1738 FunctionTemplate->getSourceRange().getEnd(), 1739 Builder, 1740 Deduced[I].wasDeducedFromArrayBound() 1741 ? CTAK_DeducedFromArrayBound 1742 : CTAK_Deduced)) { 1743 Info.Param = makeTemplateParameter( 1744 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1745 // FIXME: These template arguments are temporary. Free them! 1746 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 1747 Builder.size())); 1748 return TDK_SubstitutionFailure; 1749 } 1750 1751 continue; 1752 } 1753 1754 // Substitute into the default template argument, if available. 1755 TemplateArgumentLoc DefArg 1756 = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate, 1757 FunctionTemplate->getLocation(), 1758 FunctionTemplate->getSourceRange().getEnd(), 1759 Param, 1760 Builder); 1761 1762 // If there was no default argument, deduction is incomplete. 1763 if (DefArg.getArgument().isNull()) { 1764 Info.Param = makeTemplateParameter( 1765 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1766 return TDK_Incomplete; 1767 } 1768 1769 // Check whether we can actually use the default argument. 1770 if (CheckTemplateArgument(Param, DefArg, 1771 FunctionTemplate, 1772 FunctionTemplate->getLocation(), 1773 FunctionTemplate->getSourceRange().getEnd(), 1774 Builder, 1775 CTAK_Deduced)) { 1776 Info.Param = makeTemplateParameter( 1777 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 1778 // FIXME: These template arguments are temporary. Free them! 1779 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 1780 Builder.size())); 1781 return TDK_SubstitutionFailure; 1782 } 1783 1784 // If we get here, we successfully used the default template argument. 1785 } 1786 1787 // Form the template argument list from the deduced template arguments. 1788 TemplateArgumentList *DeducedArgumentList 1789 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size()); 1790 Info.reset(DeducedArgumentList); 1791 1792 // Substitute the deduced template arguments into the function template 1793 // declaration to produce the function template specialization. 1794 DeclContext *Owner = FunctionTemplate->getDeclContext(); 1795 if (FunctionTemplate->getFriendObjectKind()) 1796 Owner = FunctionTemplate->getLexicalDeclContext(); 1797 Specialization = cast_or_null<FunctionDecl>( 1798 SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner, 1799 MultiLevelTemplateArgumentList(*DeducedArgumentList))); 1800 if (!Specialization) 1801 return TDK_SubstitutionFailure; 1802 1803 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() == 1804 FunctionTemplate->getCanonicalDecl()); 1805 1806 // If the template argument list is owned by the function template 1807 // specialization, release it. 1808 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList && 1809 !Trap.hasErrorOccurred()) 1810 Info.take(); 1811 1812 // There may have been an error that did not prevent us from constructing a 1813 // declaration. Mark the declaration invalid and return with a substitution 1814 // failure. 1815 if (Trap.hasErrorOccurred()) { 1816 Specialization->setInvalidDecl(true); 1817 return TDK_SubstitutionFailure; 1818 } 1819 1820 // If we suppressed any diagnostics while performing template argument 1821 // deduction, and if we haven't already instantiated this declaration, 1822 // keep track of these diagnostics. They'll be emitted if this specialization 1823 // is actually used. 1824 if (Info.diag_begin() != Info.diag_end()) { 1825 llvm::DenseMap<Decl *, llvm::SmallVector<PartialDiagnosticAt, 1> >::iterator 1826 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl()); 1827 if (Pos == SuppressedDiagnostics.end()) 1828 SuppressedDiagnostics[Specialization->getCanonicalDecl()] 1829 .append(Info.diag_begin(), Info.diag_end()); 1830 } 1831 1832 return TDK_Success; 1833} 1834 1835/// Gets the type of a function for template-argument-deducton 1836/// purposes when it's considered as part of an overload set. 1837static QualType GetTypeOfFunction(ASTContext &Context, 1838 const OverloadExpr::FindResult &R, 1839 FunctionDecl *Fn) { 1840 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn)) 1841 if (Method->isInstance()) { 1842 // An instance method that's referenced in a form that doesn't 1843 // look like a member pointer is just invalid. 1844 if (!R.HasFormOfMemberPointer) return QualType(); 1845 1846 return Context.getMemberPointerType(Fn->getType(), 1847 Context.getTypeDeclType(Method->getParent()).getTypePtr()); 1848 } 1849 1850 if (!R.IsAddressOfOperand) return Fn->getType(); 1851 return Context.getPointerType(Fn->getType()); 1852} 1853 1854/// Apply the deduction rules for overload sets. 1855/// 1856/// \return the null type if this argument should be treated as an 1857/// undeduced context 1858static QualType 1859ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams, 1860 Expr *Arg, QualType ParamType, 1861 bool ParamWasReference) { 1862 1863 OverloadExpr::FindResult R = OverloadExpr::find(Arg); 1864 1865 OverloadExpr *Ovl = R.Expression; 1866 1867 // C++0x [temp.deduct.call]p4 1868 unsigned TDF = 0; 1869 if (ParamWasReference) 1870 TDF |= TDF_ParamWithReferenceType; 1871 if (R.IsAddressOfOperand) 1872 TDF |= TDF_IgnoreQualifiers; 1873 1874 // If there were explicit template arguments, we can only find 1875 // something via C++ [temp.arg.explicit]p3, i.e. if the arguments 1876 // unambiguously name a full specialization. 1877 if (Ovl->hasExplicitTemplateArgs()) { 1878 // But we can still look for an explicit specialization. 1879 if (FunctionDecl *ExplicitSpec 1880 = S.ResolveSingleFunctionTemplateSpecialization(Ovl)) 1881 return GetTypeOfFunction(S.Context, R, ExplicitSpec); 1882 return QualType(); 1883 } 1884 1885 // C++0x [temp.deduct.call]p6: 1886 // When P is a function type, pointer to function type, or pointer 1887 // to member function type: 1888 1889 if (!ParamType->isFunctionType() && 1890 !ParamType->isFunctionPointerType() && 1891 !ParamType->isMemberFunctionPointerType()) 1892 return QualType(); 1893 1894 QualType Match; 1895 for (UnresolvedSetIterator I = Ovl->decls_begin(), 1896 E = Ovl->decls_end(); I != E; ++I) { 1897 NamedDecl *D = (*I)->getUnderlyingDecl(); 1898 1899 // - If the argument is an overload set containing one or more 1900 // function templates, the parameter is treated as a 1901 // non-deduced context. 1902 if (isa<FunctionTemplateDecl>(D)) 1903 return QualType(); 1904 1905 FunctionDecl *Fn = cast<FunctionDecl>(D); 1906 QualType ArgType = GetTypeOfFunction(S.Context, R, Fn); 1907 if (ArgType.isNull()) continue; 1908 1909 // Function-to-pointer conversion. 1910 if (!ParamWasReference && ParamType->isPointerType() && 1911 ArgType->isFunctionType()) 1912 ArgType = S.Context.getPointerType(ArgType); 1913 1914 // - If the argument is an overload set (not containing function 1915 // templates), trial argument deduction is attempted using each 1916 // of the members of the set. If deduction succeeds for only one 1917 // of the overload set members, that member is used as the 1918 // argument value for the deduction. If deduction succeeds for 1919 // more than one member of the overload set the parameter is 1920 // treated as a non-deduced context. 1921 1922 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2: 1923 // Type deduction is done independently for each P/A pair, and 1924 // the deduced template argument values are then combined. 1925 // So we do not reject deductions which were made elsewhere. 1926 llvm::SmallVector<DeducedTemplateArgument, 8> 1927 Deduced(TemplateParams->size()); 1928 TemplateDeductionInfo Info(S.Context, Ovl->getNameLoc()); 1929 Sema::TemplateDeductionResult Result 1930 = DeduceTemplateArguments(S, TemplateParams, 1931 ParamType, ArgType, 1932 Info, Deduced, TDF); 1933 if (Result) continue; 1934 if (!Match.isNull()) return QualType(); 1935 Match = ArgType; 1936 } 1937 1938 return Match; 1939} 1940 1941/// \brief Perform template argument deduction from a function call 1942/// (C++ [temp.deduct.call]). 1943/// 1944/// \param FunctionTemplate the function template for which we are performing 1945/// template argument deduction. 1946/// 1947/// \param ExplicitTemplateArguments the explicit template arguments provided 1948/// for this call. 1949/// 1950/// \param Args the function call arguments 1951/// 1952/// \param NumArgs the number of arguments in Args 1953/// 1954/// \param Name the name of the function being called. This is only significant 1955/// when the function template is a conversion function template, in which 1956/// case this routine will also perform template argument deduction based on 1957/// the function to which 1958/// 1959/// \param Specialization if template argument deduction was successful, 1960/// this will be set to the function template specialization produced by 1961/// template argument deduction. 1962/// 1963/// \param Info the argument will be updated to provide additional information 1964/// about template argument deduction. 1965/// 1966/// \returns the result of template argument deduction. 1967Sema::TemplateDeductionResult 1968Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 1969 const TemplateArgumentListInfo *ExplicitTemplateArgs, 1970 Expr **Args, unsigned NumArgs, 1971 FunctionDecl *&Specialization, 1972 TemplateDeductionInfo &Info) { 1973 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 1974 1975 // C++ [temp.deduct.call]p1: 1976 // Template argument deduction is done by comparing each function template 1977 // parameter type (call it P) with the type of the corresponding argument 1978 // of the call (call it A) as described below. 1979 unsigned CheckArgs = NumArgs; 1980 if (NumArgs < Function->getMinRequiredArguments()) 1981 return TDK_TooFewArguments; 1982 else if (NumArgs > Function->getNumParams()) { 1983 const FunctionProtoType *Proto 1984 = Function->getType()->getAs<FunctionProtoType>(); 1985 if (!Proto->isVariadic()) 1986 return TDK_TooManyArguments; 1987 1988 CheckArgs = Function->getNumParams(); 1989 } 1990 1991 // The types of the parameters from which we will perform template argument 1992 // deduction. 1993 LocalInstantiationScope InstScope(*this); 1994 TemplateParameterList *TemplateParams 1995 = FunctionTemplate->getTemplateParameters(); 1996 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 1997 llvm::SmallVector<QualType, 4> ParamTypes; 1998 unsigned NumExplicitlySpecified = 0; 1999 if (ExplicitTemplateArgs) { 2000 TemplateDeductionResult Result = 2001 SubstituteExplicitTemplateArguments(FunctionTemplate, 2002 *ExplicitTemplateArgs, 2003 Deduced, 2004 ParamTypes, 2005 0, 2006 Info); 2007 if (Result) 2008 return Result; 2009 2010 NumExplicitlySpecified = Deduced.size(); 2011 } else { 2012 // Just fill in the parameter types from the function declaration. 2013 for (unsigned I = 0; I != CheckArgs; ++I) 2014 ParamTypes.push_back(Function->getParamDecl(I)->getType()); 2015 } 2016 2017 // Deduce template arguments from the function parameters. 2018 Deduced.resize(TemplateParams->size()); 2019 for (unsigned I = 0; I != CheckArgs; ++I) { 2020 QualType ParamType = ParamTypes[I]; 2021 QualType ArgType = Args[I]->getType(); 2022 2023 // C++0x [temp.deduct.call]p3: 2024 // If P is a cv-qualified type, the top level cv-qualifiers of P’s type 2025 // are ignored for type deduction. 2026 if (ParamType.getCVRQualifiers()) 2027 ParamType = ParamType.getLocalUnqualifiedType(); 2028 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>(); 2029 if (ParamRefType) { 2030 // [...] If P is a reference type, the type referred to by P is used 2031 // for type deduction. 2032 ParamType = ParamRefType->getPointeeType(); 2033 } 2034 2035 // Overload sets usually make this parameter an undeduced 2036 // context, but there are sometimes special circumstances. 2037 if (ArgType == Context.OverloadTy) { 2038 ArgType = ResolveOverloadForDeduction(*this, TemplateParams, 2039 Args[I], ParamType, 2040 ParamRefType != 0); 2041 if (ArgType.isNull()) 2042 continue; 2043 } 2044 2045 if (ParamRefType) { 2046 // C++0x [temp.deduct.call]p3: 2047 // [...] If P is of the form T&&, where T is a template parameter, and 2048 // the argument is an lvalue, the type A& is used in place of A for 2049 // type deduction. 2050 if (ParamRefType->isRValueReferenceType() && 2051 ParamRefType->getAs<TemplateTypeParmType>() && 2052 Args[I]->isLValue()) 2053 ArgType = Context.getLValueReferenceType(ArgType); 2054 } else { 2055 // C++ [temp.deduct.call]p2: 2056 // If P is not a reference type: 2057 // - If A is an array type, the pointer type produced by the 2058 // array-to-pointer standard conversion (4.2) is used in place of 2059 // A for type deduction; otherwise, 2060 if (ArgType->isArrayType()) 2061 ArgType = Context.getArrayDecayedType(ArgType); 2062 // - If A is a function type, the pointer type produced by the 2063 // function-to-pointer standard conversion (4.3) is used in place 2064 // of A for type deduction; otherwise, 2065 else if (ArgType->isFunctionType()) 2066 ArgType = Context.getPointerType(ArgType); 2067 else { 2068 // - If A is a cv-qualified type, the top level cv-qualifiers of A’s 2069 // type are ignored for type deduction. 2070 QualType CanonArgType = Context.getCanonicalType(ArgType); 2071 if (ArgType.getCVRQualifiers()) 2072 ArgType = ArgType.getUnqualifiedType(); 2073 } 2074 } 2075 2076 // C++0x [temp.deduct.call]p4: 2077 // In general, the deduction process attempts to find template argument 2078 // values that will make the deduced A identical to A (after the type A 2079 // is transformed as described above). [...] 2080 unsigned TDF = TDF_SkipNonDependent; 2081 2082 // - If the original P is a reference type, the deduced A (i.e., the 2083 // type referred to by the reference) can be more cv-qualified than 2084 // the transformed A. 2085 if (ParamRefType) 2086 TDF |= TDF_ParamWithReferenceType; 2087 // - The transformed A can be another pointer or pointer to member 2088 // type that can be converted to the deduced A via a qualification 2089 // conversion (4.4). 2090 if (ArgType->isPointerType() || ArgType->isMemberPointerType() || 2091 ArgType->isObjCObjectPointerType()) 2092 TDF |= TDF_IgnoreQualifiers; 2093 // - If P is a class and P has the form simple-template-id, then the 2094 // transformed A can be a derived class of the deduced A. Likewise, 2095 // if P is a pointer to a class of the form simple-template-id, the 2096 // transformed A can be a pointer to a derived class pointed to by 2097 // the deduced A. 2098 if (isSimpleTemplateIdType(ParamType) || 2099 (isa<PointerType>(ParamType) && 2100 isSimpleTemplateIdType( 2101 ParamType->getAs<PointerType>()->getPointeeType()))) 2102 TDF |= TDF_DerivedClass; 2103 2104 if (TemplateDeductionResult Result 2105 = ::DeduceTemplateArguments(*this, TemplateParams, 2106 ParamType, ArgType, Info, Deduced, 2107 TDF)) 2108 return Result; 2109 2110 // FIXME: we need to check that the deduced A is the same as A, 2111 // modulo the various allowed differences. 2112 } 2113 2114 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 2115 NumExplicitlySpecified, 2116 Specialization, Info); 2117} 2118 2119/// \brief Deduce template arguments when taking the address of a function 2120/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to 2121/// a template. 2122/// 2123/// \param FunctionTemplate the function template for which we are performing 2124/// template argument deduction. 2125/// 2126/// \param ExplicitTemplateArguments the explicitly-specified template 2127/// arguments. 2128/// 2129/// \param ArgFunctionType the function type that will be used as the 2130/// "argument" type (A) when performing template argument deduction from the 2131/// function template's function type. This type may be NULL, if there is no 2132/// argument type to compare against, in C++0x [temp.arg.explicit]p3. 2133/// 2134/// \param Specialization if template argument deduction was successful, 2135/// this will be set to the function template specialization produced by 2136/// template argument deduction. 2137/// 2138/// \param Info the argument will be updated to provide additional information 2139/// about template argument deduction. 2140/// 2141/// \returns the result of template argument deduction. 2142Sema::TemplateDeductionResult 2143Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2144 const TemplateArgumentListInfo *ExplicitTemplateArgs, 2145 QualType ArgFunctionType, 2146 FunctionDecl *&Specialization, 2147 TemplateDeductionInfo &Info) { 2148 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2149 TemplateParameterList *TemplateParams 2150 = FunctionTemplate->getTemplateParameters(); 2151 QualType FunctionType = Function->getType(); 2152 2153 // Substitute any explicit template arguments. 2154 LocalInstantiationScope InstScope(*this); 2155 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2156 unsigned NumExplicitlySpecified = 0; 2157 llvm::SmallVector<QualType, 4> ParamTypes; 2158 if (ExplicitTemplateArgs) { 2159 if (TemplateDeductionResult Result 2160 = SubstituteExplicitTemplateArguments(FunctionTemplate, 2161 *ExplicitTemplateArgs, 2162 Deduced, ParamTypes, 2163 &FunctionType, Info)) 2164 return Result; 2165 2166 NumExplicitlySpecified = Deduced.size(); 2167 } 2168 2169 // Template argument deduction for function templates in a SFINAE context. 2170 // Trap any errors that might occur. 2171 SFINAETrap Trap(*this); 2172 2173 Deduced.resize(TemplateParams->size()); 2174 2175 if (!ArgFunctionType.isNull()) { 2176 // Deduce template arguments from the function type. 2177 if (TemplateDeductionResult Result 2178 = ::DeduceTemplateArguments(*this, TemplateParams, 2179 FunctionType, ArgFunctionType, Info, 2180 Deduced, 0)) 2181 return Result; 2182 } 2183 2184 if (TemplateDeductionResult Result 2185 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 2186 NumExplicitlySpecified, 2187 Specialization, Info)) 2188 return Result; 2189 2190 // If the requested function type does not match the actual type of the 2191 // specialization, template argument deduction fails. 2192 if (!ArgFunctionType.isNull() && 2193 !Context.hasSameType(ArgFunctionType, Specialization->getType())) 2194 return TDK_NonDeducedMismatch; 2195 2196 return TDK_Success; 2197} 2198 2199/// \brief Deduce template arguments for a templated conversion 2200/// function (C++ [temp.deduct.conv]) and, if successful, produce a 2201/// conversion function template specialization. 2202Sema::TemplateDeductionResult 2203Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2204 QualType ToType, 2205 CXXConversionDecl *&Specialization, 2206 TemplateDeductionInfo &Info) { 2207 CXXConversionDecl *Conv 2208 = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl()); 2209 QualType FromType = Conv->getConversionType(); 2210 2211 // Canonicalize the types for deduction. 2212 QualType P = Context.getCanonicalType(FromType); 2213 QualType A = Context.getCanonicalType(ToType); 2214 2215 // C++0x [temp.deduct.conv]p3: 2216 // If P is a reference type, the type referred to by P is used for 2217 // type deduction. 2218 if (const ReferenceType *PRef = P->getAs<ReferenceType>()) 2219 P = PRef->getPointeeType(); 2220 2221 // C++0x [temp.deduct.conv]p3: 2222 // If A is a reference type, the type referred to by A is used 2223 // for type deduction. 2224 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 2225 A = ARef->getPointeeType(); 2226 // C++ [temp.deduct.conv]p2: 2227 // 2228 // If A is not a reference type: 2229 else { 2230 assert(!A->isReferenceType() && "Reference types were handled above"); 2231 2232 // - If P is an array type, the pointer type produced by the 2233 // array-to-pointer standard conversion (4.2) is used in place 2234 // of P for type deduction; otherwise, 2235 if (P->isArrayType()) 2236 P = Context.getArrayDecayedType(P); 2237 // - If P is a function type, the pointer type produced by the 2238 // function-to-pointer standard conversion (4.3) is used in 2239 // place of P for type deduction; otherwise, 2240 else if (P->isFunctionType()) 2241 P = Context.getPointerType(P); 2242 // - If P is a cv-qualified type, the top level cv-qualifiers of 2243 // P’s type are ignored for type deduction. 2244 else 2245 P = P.getUnqualifiedType(); 2246 2247 // C++0x [temp.deduct.conv]p3: 2248 // If A is a cv-qualified type, the top level cv-qualifiers of A’s 2249 // type are ignored for type deduction. 2250 A = A.getUnqualifiedType(); 2251 } 2252 2253 // Template argument deduction for function templates in a SFINAE context. 2254 // Trap any errors that might occur. 2255 SFINAETrap Trap(*this); 2256 2257 // C++ [temp.deduct.conv]p1: 2258 // Template argument deduction is done by comparing the return 2259 // type of the template conversion function (call it P) with the 2260 // type that is required as the result of the conversion (call it 2261 // A) as described in 14.8.2.4. 2262 TemplateParameterList *TemplateParams 2263 = FunctionTemplate->getTemplateParameters(); 2264 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2265 Deduced.resize(TemplateParams->size()); 2266 2267 // C++0x [temp.deduct.conv]p4: 2268 // In general, the deduction process attempts to find template 2269 // argument values that will make the deduced A identical to 2270 // A. However, there are two cases that allow a difference: 2271 unsigned TDF = 0; 2272 // - If the original A is a reference type, A can be more 2273 // cv-qualified than the deduced A (i.e., the type referred to 2274 // by the reference) 2275 if (ToType->isReferenceType()) 2276 TDF |= TDF_ParamWithReferenceType; 2277 // - The deduced A can be another pointer or pointer to member 2278 // type that can be converted to A via a qualification 2279 // conversion. 2280 // 2281 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 2282 // both P and A are pointers or member pointers. In this case, we 2283 // just ignore cv-qualifiers completely). 2284 if ((P->isPointerType() && A->isPointerType()) || 2285 (P->isMemberPointerType() && P->isMemberPointerType())) 2286 TDF |= TDF_IgnoreQualifiers; 2287 if (TemplateDeductionResult Result 2288 = ::DeduceTemplateArguments(*this, TemplateParams, 2289 P, A, Info, Deduced, TDF)) 2290 return Result; 2291 2292 // FIXME: we need to check that the deduced A is the same as A, 2293 // modulo the various allowed differences. 2294 2295 // Finish template argument deduction. 2296 LocalInstantiationScope InstScope(*this); 2297 FunctionDecl *Spec = 0; 2298 TemplateDeductionResult Result 2299 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec, 2300 Info); 2301 Specialization = cast_or_null<CXXConversionDecl>(Spec); 2302 return Result; 2303} 2304 2305/// \brief Deduce template arguments for a function template when there is 2306/// nothing to deduce against (C++0x [temp.arg.explicit]p3). 2307/// 2308/// \param FunctionTemplate the function template for which we are performing 2309/// template argument deduction. 2310/// 2311/// \param ExplicitTemplateArguments the explicitly-specified template 2312/// arguments. 2313/// 2314/// \param Specialization if template argument deduction was successful, 2315/// this will be set to the function template specialization produced by 2316/// template argument deduction. 2317/// 2318/// \param Info the argument will be updated to provide additional information 2319/// about template argument deduction. 2320/// 2321/// \returns the result of template argument deduction. 2322Sema::TemplateDeductionResult 2323Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 2324 const TemplateArgumentListInfo *ExplicitTemplateArgs, 2325 FunctionDecl *&Specialization, 2326 TemplateDeductionInfo &Info) { 2327 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs, 2328 QualType(), Specialization, Info); 2329} 2330 2331/// \brief Stores the result of comparing the qualifiers of two types. 2332enum DeductionQualifierComparison { 2333 NeitherMoreQualified = 0, 2334 ParamMoreQualified, 2335 ArgMoreQualified 2336}; 2337 2338/// \brief Deduce the template arguments during partial ordering by comparing 2339/// the parameter type and the argument type (C++0x [temp.deduct.partial]). 2340/// 2341/// \param S the semantic analysis object within which we are deducing 2342/// 2343/// \param TemplateParams the template parameters that we are deducing 2344/// 2345/// \param ParamIn the parameter type 2346/// 2347/// \param ArgIn the argument type 2348/// 2349/// \param Info information about the template argument deduction itself 2350/// 2351/// \param Deduced the deduced template arguments 2352/// 2353/// \returns the result of template argument deduction so far. Note that a 2354/// "success" result means that template argument deduction has not yet failed, 2355/// but it may still fail, later, for other reasons. 2356static Sema::TemplateDeductionResult 2357DeduceTemplateArgumentsDuringPartialOrdering(Sema &S, 2358 TemplateParameterList *TemplateParams, 2359 QualType ParamIn, QualType ArgIn, 2360 TemplateDeductionInfo &Info, 2361 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2362 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 2363 CanQualType Param = S.Context.getCanonicalType(ParamIn); 2364 CanQualType Arg = S.Context.getCanonicalType(ArgIn); 2365 2366 // C++0x [temp.deduct.partial]p5: 2367 // Before the partial ordering is done, certain transformations are 2368 // performed on the types used for partial ordering: 2369 // - If P is a reference type, P is replaced by the type referred to. 2370 CanQual<ReferenceType> ParamRef = Param->getAs<ReferenceType>(); 2371 if (!ParamRef.isNull()) 2372 Param = ParamRef->getPointeeType(); 2373 2374 // - If A is a reference type, A is replaced by the type referred to. 2375 CanQual<ReferenceType> ArgRef = Arg->getAs<ReferenceType>(); 2376 if (!ArgRef.isNull()) 2377 Arg = ArgRef->getPointeeType(); 2378 2379 if (QualifierComparisons && !ParamRef.isNull() && !ArgRef.isNull()) { 2380 // C++0x [temp.deduct.partial]p6: 2381 // If both P and A were reference types (before being replaced with the 2382 // type referred to above), determine which of the two types (if any) is 2383 // more cv-qualified than the other; otherwise the types are considered to 2384 // be equally cv-qualified for partial ordering purposes. The result of this 2385 // determination will be used below. 2386 // 2387 // We save this information for later, using it only when deduction 2388 // succeeds in both directions. 2389 DeductionQualifierComparison QualifierResult = NeitherMoreQualified; 2390 if (Param.isMoreQualifiedThan(Arg)) 2391 QualifierResult = ParamMoreQualified; 2392 else if (Arg.isMoreQualifiedThan(Param)) 2393 QualifierResult = ArgMoreQualified; 2394 QualifierComparisons->push_back(QualifierResult); 2395 } 2396 2397 // C++0x [temp.deduct.partial]p7: 2398 // Remove any top-level cv-qualifiers: 2399 // - If P is a cv-qualified type, P is replaced by the cv-unqualified 2400 // version of P. 2401 Param = Param.getUnqualifiedType(); 2402 // - If A is a cv-qualified type, A is replaced by the cv-unqualified 2403 // version of A. 2404 Arg = Arg.getUnqualifiedType(); 2405 2406 // C++0x [temp.deduct.partial]p8: 2407 // Using the resulting types P and A the deduction is then done as 2408 // described in 14.9.2.5. If deduction succeeds for a given type, the type 2409 // from the argument template is considered to be at least as specialized 2410 // as the type from the parameter template. 2411 return DeduceTemplateArguments(S, TemplateParams, Param, Arg, Info, 2412 Deduced, TDF_None); 2413} 2414 2415static void 2416MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 2417 bool OnlyDeduced, 2418 unsigned Level, 2419 llvm::SmallVectorImpl<bool> &Deduced); 2420 2421/// \brief If this is a non-static member function, 2422static void MaybeAddImplicitObjectParameterType(ASTContext &Context, 2423 CXXMethodDecl *Method, 2424 llvm::SmallVectorImpl<QualType> &ArgTypes) { 2425 if (Method->isStatic()) 2426 return; 2427 2428 // C++ [over.match.funcs]p4: 2429 // 2430 // For non-static member functions, the type of the implicit 2431 // object parameter is 2432 // — "lvalue reference to cv X" for functions declared without a 2433 // ref-qualifier or with the & ref-qualifier 2434 // - "rvalue reference to cv X" for functions declared with the 2435 // && ref-qualifier 2436 // 2437 // FIXME: We don't have ref-qualifiers yet, so we don't do that part. 2438 QualType ArgTy = Context.getTypeDeclType(Method->getParent()); 2439 ArgTy = Context.getQualifiedType(ArgTy, 2440 Qualifiers::fromCVRMask(Method->getTypeQualifiers())); 2441 ArgTy = Context.getLValueReferenceType(ArgTy); 2442 ArgTypes.push_back(ArgTy); 2443} 2444 2445/// \brief Determine whether the function template \p FT1 is at least as 2446/// specialized as \p FT2. 2447static bool isAtLeastAsSpecializedAs(Sema &S, 2448 SourceLocation Loc, 2449 FunctionTemplateDecl *FT1, 2450 FunctionTemplateDecl *FT2, 2451 TemplatePartialOrderingContext TPOC, 2452 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) { 2453 FunctionDecl *FD1 = FT1->getTemplatedDecl(); 2454 FunctionDecl *FD2 = FT2->getTemplatedDecl(); 2455 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 2456 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 2457 2458 assert(Proto1 && Proto2 && "Function templates must have prototypes"); 2459 TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 2460 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2461 Deduced.resize(TemplateParams->size()); 2462 2463 // C++0x [temp.deduct.partial]p3: 2464 // The types used to determine the ordering depend on the context in which 2465 // the partial ordering is done: 2466 TemplateDeductionInfo Info(S.Context, Loc); 2467 CXXMethodDecl *Method1 = 0; 2468 CXXMethodDecl *Method2 = 0; 2469 bool IsNonStatic2 = false; 2470 bool IsNonStatic1 = false; 2471 unsigned Skip2 = 0; 2472 switch (TPOC) { 2473 case TPOC_Call: { 2474 // - In the context of a function call, the function parameter types are 2475 // used. 2476 Method1 = dyn_cast<CXXMethodDecl>(FD1); 2477 Method2 = dyn_cast<CXXMethodDecl>(FD2); 2478 IsNonStatic1 = Method1 && !Method1->isStatic(); 2479 IsNonStatic2 = Method2 && !Method2->isStatic(); 2480 2481 // C++0x [temp.func.order]p3: 2482 // [...] If only one of the function templates is a non-static 2483 // member, that function template is considered to have a new 2484 // first parameter inserted in its function parameter list. The 2485 // new parameter is of type "reference to cv A," where cv are 2486 // the cv-qualifiers of the function template (if any) and A is 2487 // the class of which the function template is a member. 2488 // 2489 // C++98/03 doesn't have this provision, so instead we drop the 2490 // first argument of the free function or static member, which 2491 // seems to match existing practice. 2492 llvm::SmallVector<QualType, 4> Args1; 2493 unsigned Skip1 = !S.getLangOptions().CPlusPlus0x && 2494 IsNonStatic2 && !IsNonStatic1; 2495 if (S.getLangOptions().CPlusPlus0x && IsNonStatic1 && !IsNonStatic2) 2496 MaybeAddImplicitObjectParameterType(S.Context, Method1, Args1); 2497 Args1.insert(Args1.end(), 2498 Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end()); 2499 2500 llvm::SmallVector<QualType, 4> Args2; 2501 Skip2 = !S.getLangOptions().CPlusPlus0x && 2502 IsNonStatic1 && !IsNonStatic2; 2503 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1) 2504 MaybeAddImplicitObjectParameterType(S.Context, Method2, Args2); 2505 Args2.insert(Args2.end(), 2506 Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end()); 2507 2508 unsigned NumParams = std::min(Args1.size(), Args2.size()); 2509 for (unsigned I = 0; I != NumParams; ++I) 2510 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 2511 TemplateParams, 2512 Args2[I], 2513 Args1[I], 2514 Info, 2515 Deduced, 2516 QualifierComparisons)) 2517 return false; 2518 2519 break; 2520 } 2521 2522 case TPOC_Conversion: 2523 // - In the context of a call to a conversion operator, the return types 2524 // of the conversion function templates are used. 2525 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 2526 TemplateParams, 2527 Proto2->getResultType(), 2528 Proto1->getResultType(), 2529 Info, 2530 Deduced, 2531 QualifierComparisons)) 2532 return false; 2533 break; 2534 2535 case TPOC_Other: 2536 // - In other contexts (14.6.6.2) the function template’s function type 2537 // is used. 2538 if (DeduceTemplateArgumentsDuringPartialOrdering(S, 2539 TemplateParams, 2540 FD2->getType(), 2541 FD1->getType(), 2542 Info, 2543 Deduced, 2544 QualifierComparisons)) 2545 return false; 2546 break; 2547 } 2548 2549 // C++0x [temp.deduct.partial]p11: 2550 // In most cases, all template parameters must have values in order for 2551 // deduction to succeed, but for partial ordering purposes a template 2552 // parameter may remain without a value provided it is not used in the 2553 // types being used for partial ordering. [ Note: a template parameter used 2554 // in a non-deduced context is considered used. -end note] 2555 unsigned ArgIdx = 0, NumArgs = Deduced.size(); 2556 for (; ArgIdx != NumArgs; ++ArgIdx) 2557 if (Deduced[ArgIdx].isNull()) 2558 break; 2559 2560 if (ArgIdx == NumArgs) { 2561 // All template arguments were deduced. FT1 is at least as specialized 2562 // as FT2. 2563 return true; 2564 } 2565 2566 // Figure out which template parameters were used. 2567 llvm::SmallVector<bool, 4> UsedParameters; 2568 UsedParameters.resize(TemplateParams->size()); 2569 switch (TPOC) { 2570 case TPOC_Call: { 2571 unsigned NumParams = std::min(Proto1->getNumArgs(), Proto2->getNumArgs()); 2572 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1) 2573 ::MarkUsedTemplateParameters(S, Method2->getThisType(S.Context), false, 2574 TemplateParams->getDepth(), UsedParameters); 2575 for (unsigned I = Skip2; I < NumParams; ++I) 2576 ::MarkUsedTemplateParameters(S, Proto2->getArgType(I), false, 2577 TemplateParams->getDepth(), 2578 UsedParameters); 2579 break; 2580 } 2581 2582 case TPOC_Conversion: 2583 ::MarkUsedTemplateParameters(S, Proto2->getResultType(), false, 2584 TemplateParams->getDepth(), 2585 UsedParameters); 2586 break; 2587 2588 case TPOC_Other: 2589 ::MarkUsedTemplateParameters(S, FD2->getType(), false, 2590 TemplateParams->getDepth(), 2591 UsedParameters); 2592 break; 2593 } 2594 2595 for (; ArgIdx != NumArgs; ++ArgIdx) 2596 // If this argument had no value deduced but was used in one of the types 2597 // used for partial ordering, then deduction fails. 2598 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 2599 return false; 2600 2601 return true; 2602} 2603 2604 2605/// \brief Returns the more specialized function template according 2606/// to the rules of function template partial ordering (C++ [temp.func.order]). 2607/// 2608/// \param FT1 the first function template 2609/// 2610/// \param FT2 the second function template 2611/// 2612/// \param TPOC the context in which we are performing partial ordering of 2613/// function templates. 2614/// 2615/// \returns the more specialized function template. If neither 2616/// template is more specialized, returns NULL. 2617FunctionTemplateDecl * 2618Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, 2619 FunctionTemplateDecl *FT2, 2620 SourceLocation Loc, 2621 TemplatePartialOrderingContext TPOC) { 2622 llvm::SmallVector<DeductionQualifierComparison, 4> QualifierComparisons; 2623 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC, 0); 2624 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC, 2625 &QualifierComparisons); 2626 2627 if (Better1 != Better2) // We have a clear winner 2628 return Better1? FT1 : FT2; 2629 2630 if (!Better1 && !Better2) // Neither is better than the other 2631 return 0; 2632 2633 2634 // C++0x [temp.deduct.partial]p10: 2635 // If for each type being considered a given template is at least as 2636 // specialized for all types and more specialized for some set of types and 2637 // the other template is not more specialized for any types or is not at 2638 // least as specialized for any types, then the given template is more 2639 // specialized than the other template. Otherwise, neither template is more 2640 // specialized than the other. 2641 Better1 = false; 2642 Better2 = false; 2643 for (unsigned I = 0, N = QualifierComparisons.size(); I != N; ++I) { 2644 // C++0x [temp.deduct.partial]p9: 2645 // If, for a given type, deduction succeeds in both directions (i.e., the 2646 // types are identical after the transformations above) and if the type 2647 // from the argument template is more cv-qualified than the type from the 2648 // parameter template (as described above) that type is considered to be 2649 // more specialized than the other. If neither type is more cv-qualified 2650 // than the other then neither type is more specialized than the other. 2651 switch (QualifierComparisons[I]) { 2652 case NeitherMoreQualified: 2653 break; 2654 2655 case ParamMoreQualified: 2656 Better1 = true; 2657 if (Better2) 2658 return 0; 2659 break; 2660 2661 case ArgMoreQualified: 2662 Better2 = true; 2663 if (Better1) 2664 return 0; 2665 break; 2666 } 2667 } 2668 2669 assert(!(Better1 && Better2) && "Should have broken out in the loop above"); 2670 if (Better1) 2671 return FT1; 2672 else if (Better2) 2673 return FT2; 2674 else 2675 return 0; 2676} 2677 2678/// \brief Determine if the two templates are equivalent. 2679static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) { 2680 if (T1 == T2) 2681 return true; 2682 2683 if (!T1 || !T2) 2684 return false; 2685 2686 return T1->getCanonicalDecl() == T2->getCanonicalDecl(); 2687} 2688 2689/// \brief Retrieve the most specialized of the given function template 2690/// specializations. 2691/// 2692/// \param SpecBegin the start iterator of the function template 2693/// specializations that we will be comparing. 2694/// 2695/// \param SpecEnd the end iterator of the function template 2696/// specializations, paired with \p SpecBegin. 2697/// 2698/// \param TPOC the partial ordering context to use to compare the function 2699/// template specializations. 2700/// 2701/// \param Loc the location where the ambiguity or no-specializations 2702/// diagnostic should occur. 2703/// 2704/// \param NoneDiag partial diagnostic used to diagnose cases where there are 2705/// no matching candidates. 2706/// 2707/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one 2708/// occurs. 2709/// 2710/// \param CandidateDiag partial diagnostic used for each function template 2711/// specialization that is a candidate in the ambiguous ordering. One parameter 2712/// in this diagnostic should be unbound, which will correspond to the string 2713/// describing the template arguments for the function template specialization. 2714/// 2715/// \param Index if non-NULL and the result of this function is non-nULL, 2716/// receives the index corresponding to the resulting function template 2717/// specialization. 2718/// 2719/// \returns the most specialized function template specialization, if 2720/// found. Otherwise, returns SpecEnd. 2721/// 2722/// \todo FIXME: Consider passing in the "also-ran" candidates that failed 2723/// template argument deduction. 2724UnresolvedSetIterator 2725Sema::getMostSpecialized(UnresolvedSetIterator SpecBegin, 2726 UnresolvedSetIterator SpecEnd, 2727 TemplatePartialOrderingContext TPOC, 2728 SourceLocation Loc, 2729 const PartialDiagnostic &NoneDiag, 2730 const PartialDiagnostic &AmbigDiag, 2731 const PartialDiagnostic &CandidateDiag) { 2732 if (SpecBegin == SpecEnd) { 2733 Diag(Loc, NoneDiag); 2734 return SpecEnd; 2735 } 2736 2737 if (SpecBegin + 1 == SpecEnd) 2738 return SpecBegin; 2739 2740 // Find the function template that is better than all of the templates it 2741 // has been compared to. 2742 UnresolvedSetIterator Best = SpecBegin; 2743 FunctionTemplateDecl *BestTemplate 2744 = cast<FunctionDecl>(*Best)->getPrimaryTemplate(); 2745 assert(BestTemplate && "Not a function template specialization?"); 2746 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) { 2747 FunctionTemplateDecl *Challenger 2748 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 2749 assert(Challenger && "Not a function template specialization?"); 2750 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 2751 Loc, TPOC), 2752 Challenger)) { 2753 Best = I; 2754 BestTemplate = Challenger; 2755 } 2756 } 2757 2758 // Make sure that the "best" function template is more specialized than all 2759 // of the others. 2760 bool Ambiguous = false; 2761 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 2762 FunctionTemplateDecl *Challenger 2763 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 2764 if (I != Best && 2765 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 2766 Loc, TPOC), 2767 BestTemplate)) { 2768 Ambiguous = true; 2769 break; 2770 } 2771 } 2772 2773 if (!Ambiguous) { 2774 // We found an answer. Return it. 2775 return Best; 2776 } 2777 2778 // Diagnose the ambiguity. 2779 Diag(Loc, AmbigDiag); 2780 2781 // FIXME: Can we order the candidates in some sane way? 2782 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) 2783 Diag((*I)->getLocation(), CandidateDiag) 2784 << getTemplateArgumentBindingsText( 2785 cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(), 2786 *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs()); 2787 2788 return SpecEnd; 2789} 2790 2791/// \brief Returns the more specialized class template partial specialization 2792/// according to the rules of partial ordering of class template partial 2793/// specializations (C++ [temp.class.order]). 2794/// 2795/// \param PS1 the first class template partial specialization 2796/// 2797/// \param PS2 the second class template partial specialization 2798/// 2799/// \returns the more specialized class template partial specialization. If 2800/// neither partial specialization is more specialized, returns NULL. 2801ClassTemplatePartialSpecializationDecl * 2802Sema::getMoreSpecializedPartialSpecialization( 2803 ClassTemplatePartialSpecializationDecl *PS1, 2804 ClassTemplatePartialSpecializationDecl *PS2, 2805 SourceLocation Loc) { 2806 // C++ [temp.class.order]p1: 2807 // For two class template partial specializations, the first is at least as 2808 // specialized as the second if, given the following rewrite to two 2809 // function templates, the first function template is at least as 2810 // specialized as the second according to the ordering rules for function 2811 // templates (14.6.6.2): 2812 // - the first function template has the same template parameters as the 2813 // first partial specialization and has a single function parameter 2814 // whose type is a class template specialization with the template 2815 // arguments of the first partial specialization, and 2816 // - the second function template has the same template parameters as the 2817 // second partial specialization and has a single function parameter 2818 // whose type is a class template specialization with the template 2819 // arguments of the second partial specialization. 2820 // 2821 // Rather than synthesize function templates, we merely perform the 2822 // equivalent partial ordering by performing deduction directly on 2823 // the template arguments of the class template partial 2824 // specializations. This computation is slightly simpler than the 2825 // general problem of function template partial ordering, because 2826 // class template partial specializations are more constrained. We 2827 // know that every template parameter is deducible from the class 2828 // template partial specialization's template arguments, for 2829 // example. 2830 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced; 2831 TemplateDeductionInfo Info(Context, Loc); 2832 2833 QualType PT1 = PS1->getInjectedSpecializationType(); 2834 QualType PT2 = PS2->getInjectedSpecializationType(); 2835 2836 // Determine whether PS1 is at least as specialized as PS2 2837 Deduced.resize(PS2->getTemplateParameters()->size()); 2838 bool Better1 = !DeduceTemplateArgumentsDuringPartialOrdering(*this, 2839 PS2->getTemplateParameters(), 2840 PT2, 2841 PT1, 2842 Info, 2843 Deduced, 2844 0); 2845 if (Better1) { 2846 InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2, 2847 Deduced.data(), Deduced.size(), Info); 2848 Better1 = !::FinishTemplateArgumentDeduction(*this, PS2, 2849 PS1->getTemplateArgs(), 2850 Deduced, Info); 2851 } 2852 2853 // Determine whether PS2 is at least as specialized as PS1 2854 Deduced.clear(); 2855 Deduced.resize(PS1->getTemplateParameters()->size()); 2856 bool Better2 = !DeduceTemplateArgumentsDuringPartialOrdering(*this, 2857 PS1->getTemplateParameters(), 2858 PT1, 2859 PT2, 2860 Info, 2861 Deduced, 2862 0); 2863 if (Better2) { 2864 InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1, 2865 Deduced.data(), Deduced.size(), Info); 2866 Better2 = !::FinishTemplateArgumentDeduction(*this, PS1, 2867 PS2->getTemplateArgs(), 2868 Deduced, Info); 2869 } 2870 2871 if (Better1 == Better2) 2872 return 0; 2873 2874 return Better1? PS1 : PS2; 2875} 2876 2877static void 2878MarkUsedTemplateParameters(Sema &SemaRef, 2879 const TemplateArgument &TemplateArg, 2880 bool OnlyDeduced, 2881 unsigned Depth, 2882 llvm::SmallVectorImpl<bool> &Used); 2883 2884/// \brief Mark the template parameters that are used by the given 2885/// expression. 2886static void 2887MarkUsedTemplateParameters(Sema &SemaRef, 2888 const Expr *E, 2889 bool OnlyDeduced, 2890 unsigned Depth, 2891 llvm::SmallVectorImpl<bool> &Used) { 2892 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to 2893 // find other occurrences of template parameters. 2894 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E); 2895 if (!DRE) 2896 return; 2897 2898 const NonTypeTemplateParmDecl *NTTP 2899 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 2900 if (!NTTP) 2901 return; 2902 2903 if (NTTP->getDepth() == Depth) 2904 Used[NTTP->getIndex()] = true; 2905} 2906 2907/// \brief Mark the template parameters that are used by the given 2908/// nested name specifier. 2909static void 2910MarkUsedTemplateParameters(Sema &SemaRef, 2911 NestedNameSpecifier *NNS, 2912 bool OnlyDeduced, 2913 unsigned Depth, 2914 llvm::SmallVectorImpl<bool> &Used) { 2915 if (!NNS) 2916 return; 2917 2918 MarkUsedTemplateParameters(SemaRef, NNS->getPrefix(), OnlyDeduced, Depth, 2919 Used); 2920 MarkUsedTemplateParameters(SemaRef, QualType(NNS->getAsType(), 0), 2921 OnlyDeduced, Depth, Used); 2922} 2923 2924/// \brief Mark the template parameters that are used by the given 2925/// template name. 2926static void 2927MarkUsedTemplateParameters(Sema &SemaRef, 2928 TemplateName Name, 2929 bool OnlyDeduced, 2930 unsigned Depth, 2931 llvm::SmallVectorImpl<bool> &Used) { 2932 if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 2933 if (TemplateTemplateParmDecl *TTP 2934 = dyn_cast<TemplateTemplateParmDecl>(Template)) { 2935 if (TTP->getDepth() == Depth) 2936 Used[TTP->getIndex()] = true; 2937 } 2938 return; 2939 } 2940 2941 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) 2942 MarkUsedTemplateParameters(SemaRef, QTN->getQualifier(), OnlyDeduced, 2943 Depth, Used); 2944 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 2945 MarkUsedTemplateParameters(SemaRef, DTN->getQualifier(), OnlyDeduced, 2946 Depth, Used); 2947} 2948 2949/// \brief Mark the template parameters that are used by the given 2950/// type. 2951static void 2952MarkUsedTemplateParameters(Sema &SemaRef, QualType T, 2953 bool OnlyDeduced, 2954 unsigned Depth, 2955 llvm::SmallVectorImpl<bool> &Used) { 2956 if (T.isNull()) 2957 return; 2958 2959 // Non-dependent types have nothing deducible 2960 if (!T->isDependentType()) 2961 return; 2962 2963 T = SemaRef.Context.getCanonicalType(T); 2964 switch (T->getTypeClass()) { 2965 case Type::Pointer: 2966 MarkUsedTemplateParameters(SemaRef, 2967 cast<PointerType>(T)->getPointeeType(), 2968 OnlyDeduced, 2969 Depth, 2970 Used); 2971 break; 2972 2973 case Type::BlockPointer: 2974 MarkUsedTemplateParameters(SemaRef, 2975 cast<BlockPointerType>(T)->getPointeeType(), 2976 OnlyDeduced, 2977 Depth, 2978 Used); 2979 break; 2980 2981 case Type::LValueReference: 2982 case Type::RValueReference: 2983 MarkUsedTemplateParameters(SemaRef, 2984 cast<ReferenceType>(T)->getPointeeType(), 2985 OnlyDeduced, 2986 Depth, 2987 Used); 2988 break; 2989 2990 case Type::MemberPointer: { 2991 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 2992 MarkUsedTemplateParameters(SemaRef, MemPtr->getPointeeType(), OnlyDeduced, 2993 Depth, Used); 2994 MarkUsedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0), 2995 OnlyDeduced, Depth, Used); 2996 break; 2997 } 2998 2999 case Type::DependentSizedArray: 3000 MarkUsedTemplateParameters(SemaRef, 3001 cast<DependentSizedArrayType>(T)->getSizeExpr(), 3002 OnlyDeduced, Depth, Used); 3003 // Fall through to check the element type 3004 3005 case Type::ConstantArray: 3006 case Type::IncompleteArray: 3007 MarkUsedTemplateParameters(SemaRef, 3008 cast<ArrayType>(T)->getElementType(), 3009 OnlyDeduced, Depth, Used); 3010 break; 3011 3012 case Type::Vector: 3013 case Type::ExtVector: 3014 MarkUsedTemplateParameters(SemaRef, 3015 cast<VectorType>(T)->getElementType(), 3016 OnlyDeduced, Depth, Used); 3017 break; 3018 3019 case Type::DependentSizedExtVector: { 3020 const DependentSizedExtVectorType *VecType 3021 = cast<DependentSizedExtVectorType>(T); 3022 MarkUsedTemplateParameters(SemaRef, VecType->getElementType(), OnlyDeduced, 3023 Depth, Used); 3024 MarkUsedTemplateParameters(SemaRef, VecType->getSizeExpr(), OnlyDeduced, 3025 Depth, Used); 3026 break; 3027 } 3028 3029 case Type::FunctionProto: { 3030 const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 3031 MarkUsedTemplateParameters(SemaRef, Proto->getResultType(), OnlyDeduced, 3032 Depth, Used); 3033 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I) 3034 MarkUsedTemplateParameters(SemaRef, Proto->getArgType(I), OnlyDeduced, 3035 Depth, Used); 3036 break; 3037 } 3038 3039 case Type::TemplateTypeParm: { 3040 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T); 3041 if (TTP->getDepth() == Depth) 3042 Used[TTP->getIndex()] = true; 3043 break; 3044 } 3045 3046 case Type::InjectedClassName: 3047 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType(); 3048 // fall through 3049 3050 case Type::TemplateSpecialization: { 3051 const TemplateSpecializationType *Spec 3052 = cast<TemplateSpecializationType>(T); 3053 MarkUsedTemplateParameters(SemaRef, Spec->getTemplateName(), OnlyDeduced, 3054 Depth, Used); 3055 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 3056 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 3057 Used); 3058 break; 3059 } 3060 3061 case Type::Complex: 3062 if (!OnlyDeduced) 3063 MarkUsedTemplateParameters(SemaRef, 3064 cast<ComplexType>(T)->getElementType(), 3065 OnlyDeduced, Depth, Used); 3066 break; 3067 3068 case Type::DependentName: 3069 if (!OnlyDeduced) 3070 MarkUsedTemplateParameters(SemaRef, 3071 cast<DependentNameType>(T)->getQualifier(), 3072 OnlyDeduced, Depth, Used); 3073 break; 3074 3075 case Type::DependentTemplateSpecialization: { 3076 const DependentTemplateSpecializationType *Spec 3077 = cast<DependentTemplateSpecializationType>(T); 3078 if (!OnlyDeduced) 3079 MarkUsedTemplateParameters(SemaRef, Spec->getQualifier(), 3080 OnlyDeduced, Depth, Used); 3081 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 3082 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth, 3083 Used); 3084 break; 3085 } 3086 3087 case Type::TypeOf: 3088 if (!OnlyDeduced) 3089 MarkUsedTemplateParameters(SemaRef, 3090 cast<TypeOfType>(T)->getUnderlyingType(), 3091 OnlyDeduced, Depth, Used); 3092 break; 3093 3094 case Type::TypeOfExpr: 3095 if (!OnlyDeduced) 3096 MarkUsedTemplateParameters(SemaRef, 3097 cast<TypeOfExprType>(T)->getUnderlyingExpr(), 3098 OnlyDeduced, Depth, Used); 3099 break; 3100 3101 case Type::Decltype: 3102 if (!OnlyDeduced) 3103 MarkUsedTemplateParameters(SemaRef, 3104 cast<DecltypeType>(T)->getUnderlyingExpr(), 3105 OnlyDeduced, Depth, Used); 3106 break; 3107 3108 case Type::PackExpansion: 3109 MarkUsedTemplateParameters(SemaRef, 3110 cast<PackExpansionType>(T)->getPattern(), 3111 OnlyDeduced, Depth, Used); 3112 break; 3113 3114 // None of these types have any template parameters in them. 3115 case Type::Builtin: 3116 case Type::VariableArray: 3117 case Type::FunctionNoProto: 3118 case Type::Record: 3119 case Type::Enum: 3120 case Type::ObjCInterface: 3121 case Type::ObjCObject: 3122 case Type::ObjCObjectPointer: 3123 case Type::UnresolvedUsing: 3124#define TYPE(Class, Base) 3125#define ABSTRACT_TYPE(Class, Base) 3126#define DEPENDENT_TYPE(Class, Base) 3127#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 3128#include "clang/AST/TypeNodes.def" 3129 break; 3130 } 3131} 3132 3133/// \brief Mark the template parameters that are used by this 3134/// template argument. 3135static void 3136MarkUsedTemplateParameters(Sema &SemaRef, 3137 const TemplateArgument &TemplateArg, 3138 bool OnlyDeduced, 3139 unsigned Depth, 3140 llvm::SmallVectorImpl<bool> &Used) { 3141 switch (TemplateArg.getKind()) { 3142 case TemplateArgument::Null: 3143 case TemplateArgument::Integral: 3144 case TemplateArgument::Declaration: 3145 break; 3146 3147 case TemplateArgument::Type: 3148 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsType(), OnlyDeduced, 3149 Depth, Used); 3150 break; 3151 3152 case TemplateArgument::Template: 3153 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsTemplate(), 3154 OnlyDeduced, Depth, Used); 3155 break; 3156 3157 case TemplateArgument::Expression: 3158 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsExpr(), OnlyDeduced, 3159 Depth, Used); 3160 break; 3161 3162 case TemplateArgument::Pack: 3163 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(), 3164 PEnd = TemplateArg.pack_end(); 3165 P != PEnd; ++P) 3166 MarkUsedTemplateParameters(SemaRef, *P, OnlyDeduced, Depth, Used); 3167 break; 3168 } 3169} 3170 3171/// \brief Mark the template parameters can be deduced by the given 3172/// template argument list. 3173/// 3174/// \param TemplateArgs the template argument list from which template 3175/// parameters will be deduced. 3176/// 3177/// \param Deduced a bit vector whose elements will be set to \c true 3178/// to indicate when the corresponding template parameter will be 3179/// deduced. 3180void 3181Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 3182 bool OnlyDeduced, unsigned Depth, 3183 llvm::SmallVectorImpl<bool> &Used) { 3184 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 3185 ::MarkUsedTemplateParameters(*this, TemplateArgs[I], OnlyDeduced, 3186 Depth, Used); 3187} 3188 3189/// \brief Marks all of the template parameters that will be deduced by a 3190/// call to the given function template. 3191void 3192Sema::MarkDeducedTemplateParameters(FunctionTemplateDecl *FunctionTemplate, 3193 llvm::SmallVectorImpl<bool> &Deduced) { 3194 TemplateParameterList *TemplateParams 3195 = FunctionTemplate->getTemplateParameters(); 3196 Deduced.clear(); 3197 Deduced.resize(TemplateParams->size()); 3198 3199 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 3200 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 3201 ::MarkUsedTemplateParameters(*this, Function->getParamDecl(I)->getType(), 3202 true, TemplateParams->getDepth(), Deduced); 3203} 3204