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