1193576Sed//===------- SemaTemplateDeduction.cpp - Template Argument Deduction ------===/ 2193576Sed// 3193576Sed// The LLVM Compiler Infrastructure 4193576Sed// 5193576Sed// This file is distributed under the University of Illinois Open Source 6193576Sed// License. See LICENSE.TXT for details. 7193576Sed//===----------------------------------------------------------------------===/ 8193576Sed// 9193576Sed// This file implements C++ template argument deduction. 10193576Sed// 11193576Sed//===----------------------------------------------------------------------===/ 12193576Sed 13212904Sdim#include "clang/Sema/TemplateDeduction.h" 14252723Sdim#include "TreeTransform.h" 15193576Sed#include "clang/AST/ASTContext.h" 16263509Sdim#include "clang/AST/ASTLambda.h" 17212904Sdim#include "clang/AST/DeclObjC.h" 18193576Sed#include "clang/AST/DeclTemplate.h" 19193576Sed#include "clang/AST/Expr.h" 20193576Sed#include "clang/AST/ExprCXX.h" 21252723Sdim#include "clang/AST/StmtVisitor.h" 22252723Sdim#include "clang/Sema/DeclSpec.h" 23252723Sdim#include "clang/Sema/Sema.h" 24252723Sdim#include "clang/Sema/Template.h" 25235633Sdim#include "llvm/ADT/SmallBitVector.h" 26198092Srdivacky#include <algorithm> 27195099Sed 28195099Sednamespace clang { 29212904Sdim using namespace sema; 30195099Sed /// \brief Various flags that control template argument deduction. 31195099Sed /// 32195099Sed /// These flags can be bitwise-OR'd together. 33195099Sed enum TemplateDeductionFlags { 34195099Sed /// \brief No template argument deduction flags, which indicates the 35195099Sed /// strictest results for template argument deduction (as used for, e.g., 36195099Sed /// matching class template partial specializations). 37195099Sed TDF_None = 0, 38195099Sed /// \brief Within template argument deduction from a function call, we are 39195099Sed /// matching with a parameter type for which the original parameter was 40195099Sed /// a reference. 41195099Sed TDF_ParamWithReferenceType = 0x1, 42195099Sed /// \brief Within template argument deduction from a function call, we 43195099Sed /// are matching in a case where we ignore cv-qualifiers. 44195099Sed TDF_IgnoreQualifiers = 0x02, 45195099Sed /// \brief Within template argument deduction from a function call, 46195099Sed /// we are matching in a case where we can perform template argument 47195099Sed /// deduction from a template-id of a derived class of the argument type. 48198092Srdivacky TDF_DerivedClass = 0x04, 49198092Srdivacky /// \brief Allow non-dependent types to differ, e.g., when performing 50198092Srdivacky /// template argument deduction from a function call where conversions 51198092Srdivacky /// may apply. 52218893Sdim TDF_SkipNonDependent = 0x08, 53218893Sdim /// \brief Whether we are performing template argument deduction for 54218893Sdim /// parameters and arguments in a top-level template argument 55252723Sdim TDF_TopLevelParameterTypeList = 0x10, 56252723Sdim /// \brief Within template argument deduction from overload resolution per 57252723Sdim /// C++ [over.over] allow matching function types that are compatible in 58252723Sdim /// terms of noreturn and default calling convention adjustments. 59252723Sdim TDF_InOverloadResolution = 0x20 60195099Sed }; 61195099Sed} 62195099Sed 63193576Sedusing namespace clang; 64193576Sed 65206084Srdivacky/// \brief Compare two APSInts, extending and switching the sign as 66206084Srdivacky/// necessary to compare their values regardless of underlying type. 67206084Srdivackystatic bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) { 68206084Srdivacky if (Y.getBitWidth() > X.getBitWidth()) 69218893Sdim X = X.extend(Y.getBitWidth()); 70206084Srdivacky else if (Y.getBitWidth() < X.getBitWidth()) 71218893Sdim Y = Y.extend(X.getBitWidth()); 72206084Srdivacky 73206084Srdivacky // If there is a signedness mismatch, correct it. 74206084Srdivacky if (X.isSigned() != Y.isSigned()) { 75206084Srdivacky // If the signed value is negative, then the values cannot be the same. 76206084Srdivacky if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative())) 77206084Srdivacky return false; 78206084Srdivacky 79206084Srdivacky Y.setIsSigned(true); 80206084Srdivacky X.setIsSigned(true); 81206084Srdivacky } 82206084Srdivacky 83206084Srdivacky return X == Y; 84206084Srdivacky} 85206084Srdivacky 86194179Sedstatic Sema::TemplateDeductionResult 87203955SrdivackyDeduceTemplateArguments(Sema &S, 88194179Sed TemplateParameterList *TemplateParams, 89194179Sed const TemplateArgument &Param, 90218893Sdim TemplateArgument Arg, 91212904Sdim TemplateDeductionInfo &Info, 92263509Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced); 93194179Sed 94218893Sdim/// \brief Whether template argument deduction for two reference parameters 95218893Sdim/// resulted in the argument type, parameter type, or neither type being more 96218893Sdim/// qualified than the other. 97218893Sdimenum DeductionQualifierComparison { 98218893Sdim NeitherMoreQualified = 0, 99218893Sdim ParamMoreQualified, 100218893Sdim ArgMoreQualified 101218893Sdim}; 102218893Sdim 103218893Sdim/// \brief Stores the result of comparing two reference parameters while 104218893Sdim/// performing template argument deduction for partial ordering of function 105218893Sdim/// templates. 106218893Sdimstruct RefParamPartialOrderingComparison { 107218893Sdim /// \brief Whether the parameter type is an rvalue reference type. 108218893Sdim bool ParamIsRvalueRef; 109218893Sdim /// \brief Whether the argument type is an rvalue reference type. 110218893Sdim bool ArgIsRvalueRef; 111218893Sdim 112218893Sdim /// \brief Whether the parameter or argument (or neither) is more qualified. 113218893Sdim DeductionQualifierComparison Qualifiers; 114218893Sdim}; 115218893Sdim 116218893Sdim 117218893Sdim 118218893Sdimstatic Sema::TemplateDeductionResult 119235633SdimDeduceTemplateArgumentsByTypeMatch(Sema &S, 120235633Sdim TemplateParameterList *TemplateParams, 121235633Sdim QualType Param, 122235633Sdim QualType Arg, 123235633Sdim TemplateDeductionInfo &Info, 124235633Sdim SmallVectorImpl<DeducedTemplateArgument> & 125235633Sdim Deduced, 126235633Sdim unsigned TDF, 127235633Sdim bool PartialOrdering = false, 128235633Sdim SmallVectorImpl<RefParamPartialOrderingComparison> * 129218893Sdim RefParamComparisons = 0); 130218893Sdim 131218893Sdimstatic Sema::TemplateDeductionResult 132218893SdimDeduceTemplateArguments(Sema &S, 133218893Sdim TemplateParameterList *TemplateParams, 134218893Sdim const TemplateArgument *Params, unsigned NumParams, 135218893Sdim const TemplateArgument *Args, unsigned NumArgs, 136218893Sdim TemplateDeductionInfo &Info, 137252723Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced); 138218893Sdim 139193576Sed/// \brief If the given expression is of a form that permits the deduction 140193576Sed/// of a non-type template parameter, return the declaration of that 141193576Sed/// non-type template parameter. 142193576Sedstatic NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) { 143245431Sdim // If we are within an alias template, the expression may have undergone 144245431Sdim // any number of parameter substitutions already. 145245431Sdim while (1) { 146245431Sdim if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E)) 147245431Sdim E = IC->getSubExpr(); 148245431Sdim else if (SubstNonTypeTemplateParmExpr *Subst = 149245431Sdim dyn_cast<SubstNonTypeTemplateParmExpr>(E)) 150245431Sdim E = Subst->getReplacement(); 151245431Sdim else 152245431Sdim break; 153245431Sdim } 154198092Srdivacky 155193576Sed if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E)) 156193576Sed return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 157198092Srdivacky 158193576Sed return 0; 159193576Sed} 160193576Sed 161218893Sdim/// \brief Determine whether two declaration pointers refer to the same 162218893Sdim/// declaration. 163218893Sdimstatic bool isSameDeclaration(Decl *X, Decl *Y) { 164218893Sdim if (NamedDecl *NX = dyn_cast<NamedDecl>(X)) 165218893Sdim X = NX->getUnderlyingDecl(); 166218893Sdim if (NamedDecl *NY = dyn_cast<NamedDecl>(Y)) 167218893Sdim Y = NY->getUnderlyingDecl(); 168218893Sdim 169218893Sdim return X->getCanonicalDecl() == Y->getCanonicalDecl(); 170218893Sdim} 171218893Sdim 172218893Sdim/// \brief Verify that the given, deduced template arguments are compatible. 173218893Sdim/// 174218893Sdim/// \returns The deduced template argument, or a NULL template argument if 175218893Sdim/// the deduced template arguments were incompatible. 176218893Sdimstatic DeducedTemplateArgument 177218893SdimcheckDeducedTemplateArguments(ASTContext &Context, 178218893Sdim const DeducedTemplateArgument &X, 179218893Sdim const DeducedTemplateArgument &Y) { 180218893Sdim // We have no deduction for one or both of the arguments; they're compatible. 181218893Sdim if (X.isNull()) 182218893Sdim return Y; 183218893Sdim if (Y.isNull()) 184218893Sdim return X; 185218893Sdim 186218893Sdim switch (X.getKind()) { 187218893Sdim case TemplateArgument::Null: 188218893Sdim llvm_unreachable("Non-deduced template arguments handled above"); 189218893Sdim 190218893Sdim case TemplateArgument::Type: 191218893Sdim // If two template type arguments have the same type, they're compatible. 192218893Sdim if (Y.getKind() == TemplateArgument::Type && 193218893Sdim Context.hasSameType(X.getAsType(), Y.getAsType())) 194218893Sdim return X; 195218893Sdim 196218893Sdim return DeducedTemplateArgument(); 197218893Sdim 198218893Sdim case TemplateArgument::Integral: 199218893Sdim // If we deduced a constant in one case and either a dependent expression or 200218893Sdim // declaration in another case, keep the integral constant. 201218893Sdim // If both are integral constants with the same value, keep that value. 202218893Sdim if (Y.getKind() == TemplateArgument::Expression || 203218893Sdim Y.getKind() == TemplateArgument::Declaration || 204218893Sdim (Y.getKind() == TemplateArgument::Integral && 205245431Sdim hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral()))) 206218893Sdim return DeducedTemplateArgument(X, 207218893Sdim X.wasDeducedFromArrayBound() && 208218893Sdim Y.wasDeducedFromArrayBound()); 209218893Sdim 210218893Sdim // All other combinations are incompatible. 211218893Sdim return DeducedTemplateArgument(); 212218893Sdim 213218893Sdim case TemplateArgument::Template: 214218893Sdim if (Y.getKind() == TemplateArgument::Template && 215218893Sdim Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate())) 216218893Sdim return X; 217218893Sdim 218218893Sdim // All other combinations are incompatible. 219218893Sdim return DeducedTemplateArgument(); 220218893Sdim 221218893Sdim case TemplateArgument::TemplateExpansion: 222218893Sdim if (Y.getKind() == TemplateArgument::TemplateExpansion && 223218893Sdim Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(), 224218893Sdim Y.getAsTemplateOrTemplatePattern())) 225218893Sdim return X; 226218893Sdim 227218893Sdim // All other combinations are incompatible. 228218893Sdim return DeducedTemplateArgument(); 229218893Sdim 230218893Sdim case TemplateArgument::Expression: 231218893Sdim // If we deduced a dependent expression in one case and either an integral 232218893Sdim // constant or a declaration in another case, keep the integral constant 233218893Sdim // or declaration. 234218893Sdim if (Y.getKind() == TemplateArgument::Integral || 235218893Sdim Y.getKind() == TemplateArgument::Declaration) 236218893Sdim return DeducedTemplateArgument(Y, X.wasDeducedFromArrayBound() && 237218893Sdim Y.wasDeducedFromArrayBound()); 238218893Sdim 239218893Sdim if (Y.getKind() == TemplateArgument::Expression) { 240218893Sdim // Compare the expressions for equality 241218893Sdim llvm::FoldingSetNodeID ID1, ID2; 242218893Sdim X.getAsExpr()->Profile(ID1, Context, true); 243218893Sdim Y.getAsExpr()->Profile(ID2, Context, true); 244218893Sdim if (ID1 == ID2) 245218893Sdim return X; 246218893Sdim } 247218893Sdim 248218893Sdim // All other combinations are incompatible. 249218893Sdim return DeducedTemplateArgument(); 250218893Sdim 251218893Sdim case TemplateArgument::Declaration: 252218893Sdim // If we deduced a declaration and a dependent expression, keep the 253218893Sdim // declaration. 254218893Sdim if (Y.getKind() == TemplateArgument::Expression) 255218893Sdim return X; 256218893Sdim 257218893Sdim // If we deduced a declaration and an integral constant, keep the 258218893Sdim // integral constant. 259218893Sdim if (Y.getKind() == TemplateArgument::Integral) 260218893Sdim return Y; 261218893Sdim 262218893Sdim // If we deduced two declarations, make sure they they refer to the 263218893Sdim // same declaration. 264218893Sdim if (Y.getKind() == TemplateArgument::Declaration && 265245431Sdim isSameDeclaration(X.getAsDecl(), Y.getAsDecl()) && 266245431Sdim X.isDeclForReferenceParam() == Y.isDeclForReferenceParam()) 267218893Sdim return X; 268218893Sdim 269218893Sdim // All other combinations are incompatible. 270218893Sdim return DeducedTemplateArgument(); 271218893Sdim 272245431Sdim case TemplateArgument::NullPtr: 273245431Sdim // If we deduced a null pointer and a dependent expression, keep the 274245431Sdim // null pointer. 275245431Sdim if (Y.getKind() == TemplateArgument::Expression) 276245431Sdim return X; 277245431Sdim 278245431Sdim // If we deduced a null pointer and an integral constant, keep the 279245431Sdim // integral constant. 280245431Sdim if (Y.getKind() == TemplateArgument::Integral) 281245431Sdim return Y; 282245431Sdim 283245431Sdim // If we deduced two null pointers, make sure they have the same type. 284245431Sdim if (Y.getKind() == TemplateArgument::NullPtr && 285245431Sdim Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType())) 286245431Sdim return X; 287245431Sdim 288245431Sdim // All other combinations are incompatible. 289245431Sdim return DeducedTemplateArgument(); 290245431Sdim 291218893Sdim case TemplateArgument::Pack: 292218893Sdim if (Y.getKind() != TemplateArgument::Pack || 293218893Sdim X.pack_size() != Y.pack_size()) 294218893Sdim return DeducedTemplateArgument(); 295218893Sdim 296218893Sdim for (TemplateArgument::pack_iterator XA = X.pack_begin(), 297218893Sdim XAEnd = X.pack_end(), 298218893Sdim YA = Y.pack_begin(); 299218893Sdim XA != XAEnd; ++XA, ++YA) { 300218893Sdim if (checkDeducedTemplateArguments(Context, 301218893Sdim DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()), 302218893Sdim DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound())) 303218893Sdim .isNull()) 304218893Sdim return DeducedTemplateArgument(); 305218893Sdim } 306218893Sdim 307218893Sdim return X; 308218893Sdim } 309218893Sdim 310235633Sdim llvm_unreachable("Invalid TemplateArgument Kind!"); 311218893Sdim} 312218893Sdim 313198092Srdivacky/// \brief Deduce the value of the given non-type template parameter 314193576Sed/// from the given constant. 315194179Sedstatic Sema::TemplateDeductionResult 316203955SrdivackyDeduceNonTypeTemplateArgument(Sema &S, 317198092Srdivacky NonTypeTemplateParmDecl *NTTP, 318206084Srdivacky llvm::APSInt Value, QualType ValueType, 319206084Srdivacky bool DeducedFromArrayBound, 320212904Sdim TemplateDeductionInfo &Info, 321226890Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 322198092Srdivacky assert(NTTP->getDepth() == 0 && 323193576Sed "Cannot deduce non-type template argument with depth > 0"); 324198092Srdivacky 325245431Sdim DeducedTemplateArgument NewDeduced(S.Context, Value, ValueType, 326245431Sdim DeducedFromArrayBound); 327218893Sdim DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 328218893Sdim Deduced[NTTP->getIndex()], 329218893Sdim NewDeduced); 330218893Sdim if (Result.isNull()) { 331194179Sed Info.Param = NTTP; 332194179Sed Info.FirstArg = Deduced[NTTP->getIndex()]; 333218893Sdim Info.SecondArg = NewDeduced; 334194179Sed return Sema::TDK_Inconsistent; 335194179Sed } 336194179Sed 337218893Sdim Deduced[NTTP->getIndex()] = Result; 338194179Sed return Sema::TDK_Success; 339193576Sed} 340193576Sed 341198092Srdivacky/// \brief Deduce the value of the given non-type template parameter 342193576Sed/// from the given type- or value-dependent expression. 343193576Sed/// 344193576Sed/// \returns true if deduction succeeded, false otherwise. 345194179Sedstatic Sema::TemplateDeductionResult 346203955SrdivackyDeduceNonTypeTemplateArgument(Sema &S, 347194179Sed NonTypeTemplateParmDecl *NTTP, 348194179Sed Expr *Value, 349212904Sdim TemplateDeductionInfo &Info, 350226890Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 351198092Srdivacky assert(NTTP->getDepth() == 0 && 352193576Sed "Cannot deduce non-type template argument with depth > 0"); 353193576Sed assert((Value->isTypeDependent() || Value->isValueDependent()) && 354193576Sed "Expression template argument must be type- or value-dependent."); 355198092Srdivacky 356218893Sdim DeducedTemplateArgument NewDeduced(Value); 357218893Sdim DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 358218893Sdim Deduced[NTTP->getIndex()], 359218893Sdim NewDeduced); 360198092Srdivacky 361218893Sdim if (Result.isNull()) { 362218893Sdim Info.Param = NTTP; 363218893Sdim Info.FirstArg = Deduced[NTTP->getIndex()]; 364218893Sdim Info.SecondArg = NewDeduced; 365218893Sdim return Sema::TDK_Inconsistent; 366193576Sed } 367198092Srdivacky 368218893Sdim Deduced[NTTP->getIndex()] = Result; 369194179Sed return Sema::TDK_Success; 370193576Sed} 371193576Sed 372199482Srdivacky/// \brief Deduce the value of the given non-type template parameter 373199482Srdivacky/// from the given declaration. 374199482Srdivacky/// 375199482Srdivacky/// \returns true if deduction succeeded, false otherwise. 376194179Sedstatic Sema::TemplateDeductionResult 377203955SrdivackyDeduceNonTypeTemplateArgument(Sema &S, 378263509Sdim NonTypeTemplateParmDecl *NTTP, 379263509Sdim ValueDecl *D, 380263509Sdim TemplateDeductionInfo &Info, 381263509Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 382199482Srdivacky assert(NTTP->getDepth() == 0 && 383199482Srdivacky "Cannot deduce non-type template argument with depth > 0"); 384218893Sdim 385245431Sdim D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : 0; 386245431Sdim TemplateArgument New(D, NTTP->getType()->isReferenceType()); 387245431Sdim DeducedTemplateArgument NewDeduced(New); 388218893Sdim DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 389218893Sdim Deduced[NTTP->getIndex()], 390218893Sdim NewDeduced); 391218893Sdim if (Result.isNull()) { 392218893Sdim Info.Param = NTTP; 393218893Sdim Info.FirstArg = Deduced[NTTP->getIndex()]; 394218893Sdim Info.SecondArg = NewDeduced; 395218893Sdim return Sema::TDK_Inconsistent; 396199482Srdivacky } 397218893Sdim 398218893Sdim Deduced[NTTP->getIndex()] = Result; 399199482Srdivacky return Sema::TDK_Success; 400199482Srdivacky} 401199482Srdivacky 402199482Srdivackystatic Sema::TemplateDeductionResult 403203955SrdivackyDeduceTemplateArguments(Sema &S, 404199482Srdivacky TemplateParameterList *TemplateParams, 405194179Sed TemplateName Param, 406194179Sed TemplateName Arg, 407212904Sdim TemplateDeductionInfo &Info, 408263509Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 409194179Sed TemplateDecl *ParamDecl = Param.getAsTemplateDecl(); 410199482Srdivacky if (!ParamDecl) { 411199482Srdivacky // The parameter type is dependent and is not a template template parameter, 412199482Srdivacky // so there is nothing that we can deduce. 413199482Srdivacky return Sema::TDK_Success; 414194179Sed } 415218893Sdim 416199482Srdivacky if (TemplateTemplateParmDecl *TempParam 417199482Srdivacky = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) { 418218893Sdim DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg)); 419218893Sdim DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 420218893Sdim Deduced[TempParam->getIndex()], 421218893Sdim NewDeduced); 422218893Sdim if (Result.isNull()) { 423218893Sdim Info.Param = TempParam; 424218893Sdim Info.FirstArg = Deduced[TempParam->getIndex()]; 425218893Sdim Info.SecondArg = NewDeduced; 426218893Sdim return Sema::TDK_Inconsistent; 427199482Srdivacky } 428218893Sdim 429218893Sdim Deduced[TempParam->getIndex()] = Result; 430218893Sdim return Sema::TDK_Success; 431194179Sed } 432218893Sdim 433199482Srdivacky // Verify that the two template names are equivalent. 434203955Srdivacky if (S.Context.hasSameTemplateName(Param, Arg)) 435199482Srdivacky return Sema::TDK_Success; 436218893Sdim 437199482Srdivacky // Mismatch of non-dependent template parameter to argument. 438199482Srdivacky Info.FirstArg = TemplateArgument(Param); 439199482Srdivacky Info.SecondArg = TemplateArgument(Arg); 440199482Srdivacky return Sema::TDK_NonDeducedMismatch; 441194179Sed} 442194179Sed 443198092Srdivacky/// \brief Deduce the template arguments by comparing the template parameter 444198092Srdivacky/// type (which is a template-id) with the template argument type. 445198092Srdivacky/// 446203955Srdivacky/// \param S the Sema 447198092Srdivacky/// 448198092Srdivacky/// \param TemplateParams the template parameters that we are deducing 449198092Srdivacky/// 450198092Srdivacky/// \param Param the parameter type 451198092Srdivacky/// 452198092Srdivacky/// \param Arg the argument type 453198092Srdivacky/// 454198092Srdivacky/// \param Info information about the template argument deduction itself 455198092Srdivacky/// 456198092Srdivacky/// \param Deduced the deduced template arguments 457198092Srdivacky/// 458198092Srdivacky/// \returns the result of template argument deduction so far. Note that a 459198092Srdivacky/// "success" result means that template argument deduction has not yet failed, 460198092Srdivacky/// but it may still fail, later, for other reasons. 461198092Srdivackystatic Sema::TemplateDeductionResult 462203955SrdivackyDeduceTemplateArguments(Sema &S, 463198092Srdivacky TemplateParameterList *TemplateParams, 464198092Srdivacky const TemplateSpecializationType *Param, 465198092Srdivacky QualType Arg, 466212904Sdim TemplateDeductionInfo &Info, 467263509Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 468198398Srdivacky assert(Arg.isCanonical() && "Argument type must be canonical"); 469198092Srdivacky 470198092Srdivacky // Check whether the template argument is a dependent template-id. 471198092Srdivacky if (const TemplateSpecializationType *SpecArg 472198092Srdivacky = dyn_cast<TemplateSpecializationType>(Arg)) { 473198092Srdivacky // Perform template argument deduction for the template name. 474198092Srdivacky if (Sema::TemplateDeductionResult Result 475203955Srdivacky = DeduceTemplateArguments(S, TemplateParams, 476198092Srdivacky Param->getTemplateName(), 477198092Srdivacky SpecArg->getTemplateName(), 478198092Srdivacky Info, Deduced)) 479198092Srdivacky return Result; 480198092Srdivacky 481198092Srdivacky 482198092Srdivacky // Perform template argument deduction on each template 483218893Sdim // argument. Ignore any missing/extra arguments, since they could be 484218893Sdim // filled in by default arguments. 485218893Sdim return DeduceTemplateArguments(S, TemplateParams, 486218893Sdim Param->getArgs(), Param->getNumArgs(), 487218893Sdim SpecArg->getArgs(), SpecArg->getNumArgs(), 488252723Sdim Info, Deduced); 489198092Srdivacky } 490198092Srdivacky 491198092Srdivacky // If the argument type is a class template specialization, we 492198092Srdivacky // perform template argument deduction using its template 493198092Srdivacky // arguments. 494198092Srdivacky const RecordType *RecordArg = dyn_cast<RecordType>(Arg); 495252723Sdim if (!RecordArg) { 496252723Sdim Info.FirstArg = TemplateArgument(QualType(Param, 0)); 497252723Sdim Info.SecondArg = TemplateArgument(Arg); 498198092Srdivacky return Sema::TDK_NonDeducedMismatch; 499252723Sdim } 500198092Srdivacky 501198092Srdivacky ClassTemplateSpecializationDecl *SpecArg 502198092Srdivacky = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl()); 503252723Sdim if (!SpecArg) { 504252723Sdim Info.FirstArg = TemplateArgument(QualType(Param, 0)); 505252723Sdim Info.SecondArg = TemplateArgument(Arg); 506198092Srdivacky return Sema::TDK_NonDeducedMismatch; 507252723Sdim } 508198092Srdivacky 509198092Srdivacky // Perform template argument deduction for the template name. 510198092Srdivacky if (Sema::TemplateDeductionResult Result 511203955Srdivacky = DeduceTemplateArguments(S, 512199482Srdivacky TemplateParams, 513198092Srdivacky Param->getTemplateName(), 514198092Srdivacky TemplateName(SpecArg->getSpecializedTemplate()), 515198092Srdivacky Info, Deduced)) 516198092Srdivacky return Result; 517198092Srdivacky 518218893Sdim // Perform template argument deduction for the template arguments. 519218893Sdim return DeduceTemplateArguments(S, TemplateParams, 520218893Sdim Param->getArgs(), Param->getNumArgs(), 521218893Sdim SpecArg->getTemplateArgs().data(), 522218893Sdim SpecArg->getTemplateArgs().size(), 523218893Sdim Info, Deduced); 524198092Srdivacky} 525198092Srdivacky 526212904Sdim/// \brief Determines whether the given type is an opaque type that 527212904Sdim/// might be more qualified when instantiated. 528212904Sdimstatic bool IsPossiblyOpaquelyQualifiedType(QualType T) { 529212904Sdim switch (T->getTypeClass()) { 530212904Sdim case Type::TypeOfExpr: 531212904Sdim case Type::TypeOf: 532212904Sdim case Type::DependentName: 533212904Sdim case Type::Decltype: 534212904Sdim case Type::UnresolvedUsing: 535218893Sdim case Type::TemplateTypeParm: 536212904Sdim return true; 537212904Sdim 538212904Sdim case Type::ConstantArray: 539212904Sdim case Type::IncompleteArray: 540212904Sdim case Type::VariableArray: 541212904Sdim case Type::DependentSizedArray: 542212904Sdim return IsPossiblyOpaquelyQualifiedType( 543212904Sdim cast<ArrayType>(T)->getElementType()); 544212904Sdim 545212904Sdim default: 546212904Sdim return false; 547212904Sdim } 548212904Sdim} 549212904Sdim 550218893Sdim/// \brief Retrieve the depth and index of a template parameter. 551218893Sdimstatic std::pair<unsigned, unsigned> 552218893SdimgetDepthAndIndex(NamedDecl *ND) { 553218893Sdim if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND)) 554218893Sdim return std::make_pair(TTP->getDepth(), TTP->getIndex()); 555218893Sdim 556218893Sdim if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND)) 557218893Sdim return std::make_pair(NTTP->getDepth(), NTTP->getIndex()); 558218893Sdim 559218893Sdim TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND); 560218893Sdim return std::make_pair(TTP->getDepth(), TTP->getIndex()); 561218893Sdim} 562218893Sdim 563218893Sdim/// \brief Retrieve the depth and index of an unexpanded parameter pack. 564218893Sdimstatic std::pair<unsigned, unsigned> 565218893SdimgetDepthAndIndex(UnexpandedParameterPack UPP) { 566218893Sdim if (const TemplateTypeParmType *TTP 567218893Sdim = UPP.first.dyn_cast<const TemplateTypeParmType *>()) 568218893Sdim return std::make_pair(TTP->getDepth(), TTP->getIndex()); 569218893Sdim 570218893Sdim return getDepthAndIndex(UPP.first.get<NamedDecl *>()); 571218893Sdim} 572218893Sdim 573218893Sdim/// \brief Helper function to build a TemplateParameter when we don't 574218893Sdim/// know its type statically. 575218893Sdimstatic TemplateParameter makeTemplateParameter(Decl *D) { 576218893Sdim if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D)) 577218893Sdim return TemplateParameter(TTP); 578263509Sdim if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) 579218893Sdim return TemplateParameter(NTTP); 580218893Sdim 581218893Sdim return TemplateParameter(cast<TemplateTemplateParmDecl>(D)); 582218893Sdim} 583218893Sdim 584263509Sdimtypedef SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2> 585263509Sdim NewlyDeducedPacksType; 586263509Sdim 587218893Sdim/// \brief Prepare to perform template argument deduction for all of the 588218893Sdim/// arguments in a set of argument packs. 589263509Sdimstatic void 590263509SdimPrepareArgumentPackDeduction(Sema &S, 591263509Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 592263509Sdim ArrayRef<unsigned> PackIndices, 593263509Sdim SmallVectorImpl<DeducedTemplateArgument> &SavedPacks, 594263509Sdim NewlyDeducedPacksType &NewlyDeducedPacks) { 595218893Sdim // Save the deduced template arguments for each parameter pack expanded 596218893Sdim // by this pack expansion, then clear out the deduction. 597218893Sdim for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 598218893Sdim // Save the previously-deduced argument pack, then clear it out so that we 599218893Sdim // can deduce a new argument pack. 600218893Sdim SavedPacks[I] = Deduced[PackIndices[I]]; 601218893Sdim Deduced[PackIndices[I]] = TemplateArgument(); 602218893Sdim 603245431Sdim if (!S.CurrentInstantiationScope) 604245431Sdim continue; 605245431Sdim 606245431Sdim // If the template argument pack was explicitly specified, add that to 607218893Sdim // the set of deduced arguments. 608218893Sdim const TemplateArgument *ExplicitArgs; 609218893Sdim unsigned NumExplicitArgs; 610218893Sdim if (NamedDecl *PartiallySubstitutedPack 611218893Sdim = S.CurrentInstantiationScope->getPartiallySubstitutedPack( 612218893Sdim &ExplicitArgs, 613218893Sdim &NumExplicitArgs)) { 614218893Sdim if (getDepthAndIndex(PartiallySubstitutedPack).second == PackIndices[I]) 615218893Sdim NewlyDeducedPacks[I].append(ExplicitArgs, 616218893Sdim ExplicitArgs + NumExplicitArgs); 617218893Sdim } 618218893Sdim } 619218893Sdim} 620218893Sdim 621218893Sdim/// \brief Finish template argument deduction for a set of argument packs, 622218893Sdim/// producing the argument packs and checking for consistency with prior 623218893Sdim/// deductions. 624218893Sdimstatic Sema::TemplateDeductionResult 625218893SdimFinishArgumentPackDeduction(Sema &S, 626263509Sdim TemplateParameterList *TemplateParams, 627263509Sdim bool HasAnyArguments, 628263509Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 629263509Sdim ArrayRef<unsigned> PackIndices, 630263509Sdim SmallVectorImpl<DeducedTemplateArgument> &SavedPacks, 631263509Sdim NewlyDeducedPacksType &NewlyDeducedPacks, 632263509Sdim TemplateDeductionInfo &Info) { 633218893Sdim // Build argument packs for each of the parameter packs expanded by this 634218893Sdim // pack expansion. 635218893Sdim for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 636218893Sdim if (HasAnyArguments && NewlyDeducedPacks[I].empty()) { 637218893Sdim // We were not able to deduce anything for this parameter pack, 638218893Sdim // so just restore the saved argument pack. 639218893Sdim Deduced[PackIndices[I]] = SavedPacks[I]; 640218893Sdim continue; 641218893Sdim } 642218893Sdim 643218893Sdim DeducedTemplateArgument NewPack; 644218893Sdim 645218893Sdim if (NewlyDeducedPacks[I].empty()) { 646218893Sdim // If we deduced an empty argument pack, create it now. 647245431Sdim NewPack = DeducedTemplateArgument(TemplateArgument::getEmptyPack()); 648218893Sdim } else { 649218893Sdim TemplateArgument *ArgumentPack 650218893Sdim = new (S.Context) TemplateArgument [NewlyDeducedPacks[I].size()]; 651218893Sdim std::copy(NewlyDeducedPacks[I].begin(), NewlyDeducedPacks[I].end(), 652218893Sdim ArgumentPack); 653218893Sdim NewPack 654218893Sdim = DeducedTemplateArgument(TemplateArgument(ArgumentPack, 655218893Sdim NewlyDeducedPacks[I].size()), 656218893Sdim NewlyDeducedPacks[I][0].wasDeducedFromArrayBound()); 657218893Sdim } 658218893Sdim 659218893Sdim DeducedTemplateArgument Result 660218893Sdim = checkDeducedTemplateArguments(S.Context, SavedPacks[I], NewPack); 661218893Sdim if (Result.isNull()) { 662218893Sdim Info.Param 663218893Sdim = makeTemplateParameter(TemplateParams->getParam(PackIndices[I])); 664218893Sdim Info.FirstArg = SavedPacks[I]; 665218893Sdim Info.SecondArg = NewPack; 666218893Sdim return Sema::TDK_Inconsistent; 667218893Sdim } 668218893Sdim 669218893Sdim Deduced[PackIndices[I]] = Result; 670218893Sdim } 671218893Sdim 672218893Sdim return Sema::TDK_Success; 673218893Sdim} 674218893Sdim 675218893Sdim/// \brief Deduce the template arguments by comparing the list of parameter 676218893Sdim/// types to the list of argument types, as in the parameter-type-lists of 677218893Sdim/// function types (C++ [temp.deduct.type]p10). 678218893Sdim/// 679218893Sdim/// \param S The semantic analysis object within which we are deducing 680218893Sdim/// 681218893Sdim/// \param TemplateParams The template parameters that we are deducing 682218893Sdim/// 683218893Sdim/// \param Params The list of parameter types 684218893Sdim/// 685218893Sdim/// \param NumParams The number of types in \c Params 686218893Sdim/// 687218893Sdim/// \param Args The list of argument types 688218893Sdim/// 689218893Sdim/// \param NumArgs The number of types in \c Args 690218893Sdim/// 691218893Sdim/// \param Info information about the template argument deduction itself 692218893Sdim/// 693218893Sdim/// \param Deduced the deduced template arguments 694218893Sdim/// 695218893Sdim/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe 696218893Sdim/// how template argument deduction is performed. 697218893Sdim/// 698218893Sdim/// \param PartialOrdering If true, we are performing template argument 699218893Sdim/// deduction for during partial ordering for a call 700218893Sdim/// (C++0x [temp.deduct.partial]). 701218893Sdim/// 702218893Sdim/// \param RefParamComparisons If we're performing template argument deduction 703218893Sdim/// in the context of partial ordering, the set of qualifier comparisons. 704218893Sdim/// 705218893Sdim/// \returns the result of template argument deduction so far. Note that a 706218893Sdim/// "success" result means that template argument deduction has not yet failed, 707218893Sdim/// but it may still fail, later, for other reasons. 708218893Sdimstatic Sema::TemplateDeductionResult 709218893SdimDeduceTemplateArguments(Sema &S, 710218893Sdim TemplateParameterList *TemplateParams, 711218893Sdim const QualType *Params, unsigned NumParams, 712218893Sdim const QualType *Args, unsigned NumArgs, 713218893Sdim TemplateDeductionInfo &Info, 714263509Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 715218893Sdim unsigned TDF, 716218893Sdim bool PartialOrdering = false, 717226890Sdim SmallVectorImpl<RefParamPartialOrderingComparison> * 718218893Sdim RefParamComparisons = 0) { 719218893Sdim // Fast-path check to see if we have too many/too few arguments. 720218893Sdim if (NumParams != NumArgs && 721218893Sdim !(NumParams && isa<PackExpansionType>(Params[NumParams - 1])) && 722218893Sdim !(NumArgs && isa<PackExpansionType>(Args[NumArgs - 1]))) 723252723Sdim return Sema::TDK_MiscellaneousDeductionFailure; 724218893Sdim 725218893Sdim // C++0x [temp.deduct.type]p10: 726218893Sdim // Similarly, if P has a form that contains (T), then each parameter type 727218893Sdim // Pi of the respective parameter-type- list of P is compared with the 728218893Sdim // corresponding parameter type Ai of the corresponding parameter-type-list 729218893Sdim // of A. [...] 730218893Sdim unsigned ArgIdx = 0, ParamIdx = 0; 731218893Sdim for (; ParamIdx != NumParams; ++ParamIdx) { 732218893Sdim // Check argument types. 733218893Sdim const PackExpansionType *Expansion 734218893Sdim = dyn_cast<PackExpansionType>(Params[ParamIdx]); 735218893Sdim if (!Expansion) { 736218893Sdim // Simple case: compare the parameter and argument types at this point. 737218893Sdim 738218893Sdim // Make sure we have an argument. 739218893Sdim if (ArgIdx >= NumArgs) 740252723Sdim return Sema::TDK_MiscellaneousDeductionFailure; 741218893Sdim 742218893Sdim if (isa<PackExpansionType>(Args[ArgIdx])) { 743218893Sdim // C++0x [temp.deduct.type]p22: 744218893Sdim // If the original function parameter associated with A is a function 745218893Sdim // parameter pack and the function parameter associated with P is not 746218893Sdim // a function parameter pack, then template argument deduction fails. 747252723Sdim return Sema::TDK_MiscellaneousDeductionFailure; 748218893Sdim } 749218893Sdim 750218893Sdim if (Sema::TemplateDeductionResult Result 751235633Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 752235633Sdim Params[ParamIdx], Args[ArgIdx], 753235633Sdim Info, Deduced, TDF, 754235633Sdim PartialOrdering, 755235633Sdim RefParamComparisons)) 756218893Sdim return Result; 757218893Sdim 758218893Sdim ++ArgIdx; 759218893Sdim continue; 760218893Sdim } 761218893Sdim 762218893Sdim // C++0x [temp.deduct.type]p5: 763218893Sdim // The non-deduced contexts are: 764218893Sdim // - A function parameter pack that does not occur at the end of the 765218893Sdim // parameter-declaration-clause. 766218893Sdim if (ParamIdx + 1 < NumParams) 767218893Sdim return Sema::TDK_Success; 768218893Sdim 769218893Sdim // C++0x [temp.deduct.type]p10: 770218893Sdim // If the parameter-declaration corresponding to Pi is a function 771218893Sdim // parameter pack, then the type of its declarator- id is compared with 772218893Sdim // each remaining parameter type in the parameter-type-list of A. Each 773218893Sdim // comparison deduces template arguments for subsequent positions in the 774218893Sdim // template parameter packs expanded by the function parameter pack. 775218893Sdim 776218893Sdim // Compute the set of template parameter indices that correspond to 777218893Sdim // parameter packs expanded by the pack expansion. 778226890Sdim SmallVector<unsigned, 2> PackIndices; 779218893Sdim QualType Pattern = Expansion->getPattern(); 780218893Sdim { 781235633Sdim llvm::SmallBitVector SawIndices(TemplateParams->size()); 782226890Sdim SmallVector<UnexpandedParameterPack, 2> Unexpanded; 783218893Sdim S.collectUnexpandedParameterPacks(Pattern, Unexpanded); 784218893Sdim for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) { 785218893Sdim unsigned Depth, Index; 786218893Sdim llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]); 787218893Sdim if (Depth == 0 && !SawIndices[Index]) { 788218893Sdim SawIndices[Index] = true; 789218893Sdim PackIndices.push_back(Index); 790218893Sdim } 791218893Sdim } 792218893Sdim } 793218893Sdim assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?"); 794218893Sdim 795218893Sdim // Keep track of the deduced template arguments for each parameter pack 796218893Sdim // expanded by this pack expansion (the outer index) and for each 797218893Sdim // template argument (the inner SmallVectors). 798263509Sdim NewlyDeducedPacksType NewlyDeducedPacks(PackIndices.size()); 799226890Sdim SmallVector<DeducedTemplateArgument, 2> 800218893Sdim SavedPacks(PackIndices.size()); 801218893Sdim PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks, 802218893Sdim NewlyDeducedPacks); 803218893Sdim 804218893Sdim bool HasAnyArguments = false; 805218893Sdim for (; ArgIdx < NumArgs; ++ArgIdx) { 806218893Sdim HasAnyArguments = true; 807218893Sdim 808218893Sdim // Deduce template arguments from the pattern. 809218893Sdim if (Sema::TemplateDeductionResult Result 810235633Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, Pattern, 811235633Sdim Args[ArgIdx], Info, Deduced, 812235633Sdim TDF, PartialOrdering, 813235633Sdim RefParamComparisons)) 814218893Sdim return Result; 815218893Sdim 816218893Sdim // Capture the deduced template arguments for each parameter pack expanded 817218893Sdim // by this pack expansion, add them to the list of arguments we've deduced 818218893Sdim // for that pack, then clear out the deduced argument. 819218893Sdim for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 820218893Sdim DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]]; 821218893Sdim if (!DeducedArg.isNull()) { 822218893Sdim NewlyDeducedPacks[I].push_back(DeducedArg); 823218893Sdim DeducedArg = DeducedTemplateArgument(); 824218893Sdim } 825218893Sdim } 826218893Sdim } 827218893Sdim 828218893Sdim // Build argument packs for each of the parameter packs expanded by this 829218893Sdim // pack expansion. 830218893Sdim if (Sema::TemplateDeductionResult Result 831218893Sdim = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments, 832218893Sdim Deduced, PackIndices, SavedPacks, 833218893Sdim NewlyDeducedPacks, Info)) 834218893Sdim return Result; 835218893Sdim } 836218893Sdim 837218893Sdim // Make sure we don't have any extra arguments. 838218893Sdim if (ArgIdx < NumArgs) 839252723Sdim return Sema::TDK_MiscellaneousDeductionFailure; 840218893Sdim 841218893Sdim return Sema::TDK_Success; 842218893Sdim} 843218893Sdim 844221345Sdim/// \brief Determine whether the parameter has qualifiers that are either 845221345Sdim/// inconsistent with or a superset of the argument's qualifiers. 846221345Sdimstatic bool hasInconsistentOrSupersetQualifiersOf(QualType ParamType, 847221345Sdim QualType ArgType) { 848221345Sdim Qualifiers ParamQs = ParamType.getQualifiers(); 849221345Sdim Qualifiers ArgQs = ArgType.getQualifiers(); 850221345Sdim 851221345Sdim if (ParamQs == ArgQs) 852221345Sdim return false; 853221345Sdim 854221345Sdim // Mismatched (but not missing) Objective-C GC attributes. 855221345Sdim if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() && 856221345Sdim ParamQs.hasObjCGCAttr()) 857221345Sdim return true; 858221345Sdim 859221345Sdim // Mismatched (but not missing) address spaces. 860221345Sdim if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() && 861221345Sdim ParamQs.hasAddressSpace()) 862221345Sdim return true; 863221345Sdim 864224145Sdim // Mismatched (but not missing) Objective-C lifetime qualifiers. 865224145Sdim if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() && 866224145Sdim ParamQs.hasObjCLifetime()) 867224145Sdim return true; 868224145Sdim 869221345Sdim // CVR qualifier superset. 870221345Sdim return (ParamQs.getCVRQualifiers() != ArgQs.getCVRQualifiers()) && 871221345Sdim ((ParamQs.getCVRQualifiers() | ArgQs.getCVRQualifiers()) 872221345Sdim == ParamQs.getCVRQualifiers()); 873221345Sdim} 874221345Sdim 875252723Sdim/// \brief Compare types for equality with respect to possibly compatible 876252723Sdim/// function types (noreturn adjustment, implicit calling conventions). If any 877252723Sdim/// of parameter and argument is not a function, just perform type comparison. 878252723Sdim/// 879252723Sdim/// \param Param the template parameter type. 880252723Sdim/// 881252723Sdim/// \param Arg the argument type. 882252723Sdimbool Sema::isSameOrCompatibleFunctionType(CanQualType Param, 883252723Sdim CanQualType Arg) { 884252723Sdim const FunctionType *ParamFunction = Param->getAs<FunctionType>(), 885252723Sdim *ArgFunction = Arg->getAs<FunctionType>(); 886252723Sdim 887252723Sdim // Just compare if not functions. 888252723Sdim if (!ParamFunction || !ArgFunction) 889252723Sdim return Param == Arg; 890252723Sdim 891252723Sdim // Noreturn adjustment. 892252723Sdim QualType AdjustedParam; 893252723Sdim if (IsNoReturnConversion(Param, Arg, AdjustedParam)) 894252723Sdim return Arg == Context.getCanonicalType(AdjustedParam); 895252723Sdim 896252723Sdim // FIXME: Compatible calling conventions. 897252723Sdim 898252723Sdim return Param == Arg; 899252723Sdim} 900252723Sdim 901195099Sed/// \brief Deduce the template arguments by comparing the parameter type and 902195099Sed/// the argument type (C++ [temp.deduct.type]). 903195099Sed/// 904203955Srdivacky/// \param S the semantic analysis object within which we are deducing 905195099Sed/// 906195099Sed/// \param TemplateParams the template parameters that we are deducing 907195099Sed/// 908195099Sed/// \param ParamIn the parameter type 909195099Sed/// 910195099Sed/// \param ArgIn the argument type 911195099Sed/// 912195099Sed/// \param Info information about the template argument deduction itself 913195099Sed/// 914195099Sed/// \param Deduced the deduced template arguments 915195099Sed/// 916195099Sed/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe 917198092Srdivacky/// how template argument deduction is performed. 918195099Sed/// 919218893Sdim/// \param PartialOrdering Whether we're performing template argument deduction 920218893Sdim/// in the context of partial ordering (C++0x [temp.deduct.partial]). 921218893Sdim/// 922218893Sdim/// \param RefParamComparisons If we're performing template argument deduction 923218893Sdim/// in the context of partial ordering, the set of qualifier comparisons. 924218893Sdim/// 925195099Sed/// \returns the result of template argument deduction so far. Note that a 926195099Sed/// "success" result means that template argument deduction has not yet failed, 927195099Sed/// but it may still fail, later, for other reasons. 928194179Sedstatic Sema::TemplateDeductionResult 929235633SdimDeduceTemplateArgumentsByTypeMatch(Sema &S, 930235633Sdim TemplateParameterList *TemplateParams, 931235633Sdim QualType ParamIn, QualType ArgIn, 932235633Sdim TemplateDeductionInfo &Info, 933235633Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 934235633Sdim unsigned TDF, 935235633Sdim bool PartialOrdering, 936235633Sdim SmallVectorImpl<RefParamPartialOrderingComparison> * 937235633Sdim RefParamComparisons) { 938193576Sed // We only want to look at the canonical types, since typedefs and 939193576Sed // sugar are not part of template argument deduction. 940203955Srdivacky QualType Param = S.Context.getCanonicalType(ParamIn); 941203955Srdivacky QualType Arg = S.Context.getCanonicalType(ArgIn); 942193576Sed 943218893Sdim // If the argument type is a pack expansion, look at its pattern. 944218893Sdim // This isn't explicitly called out 945218893Sdim if (const PackExpansionType *ArgExpansion 946218893Sdim = dyn_cast<PackExpansionType>(Arg)) 947218893Sdim Arg = ArgExpansion->getPattern(); 948218893Sdim 949218893Sdim if (PartialOrdering) { 950218893Sdim // C++0x [temp.deduct.partial]p5: 951218893Sdim // Before the partial ordering is done, certain transformations are 952218893Sdim // performed on the types used for partial ordering: 953218893Sdim // - If P is a reference type, P is replaced by the type referred to. 954218893Sdim const ReferenceType *ParamRef = Param->getAs<ReferenceType>(); 955218893Sdim if (ParamRef) 956218893Sdim Param = ParamRef->getPointeeType(); 957218893Sdim 958218893Sdim // - If A is a reference type, A is replaced by the type referred to. 959218893Sdim const ReferenceType *ArgRef = Arg->getAs<ReferenceType>(); 960218893Sdim if (ArgRef) 961218893Sdim Arg = ArgRef->getPointeeType(); 962218893Sdim 963218893Sdim if (RefParamComparisons && ParamRef && ArgRef) { 964218893Sdim // C++0x [temp.deduct.partial]p6: 965218893Sdim // If both P and A were reference types (before being replaced with the 966218893Sdim // type referred to above), determine which of the two types (if any) is 967218893Sdim // more cv-qualified than the other; otherwise the types are considered 968218893Sdim // to be equally cv-qualified for partial ordering purposes. The result 969218893Sdim // of this determination will be used below. 970218893Sdim // 971218893Sdim // We save this information for later, using it only when deduction 972218893Sdim // succeeds in both directions. 973218893Sdim RefParamPartialOrderingComparison Comparison; 974218893Sdim Comparison.ParamIsRvalueRef = ParamRef->getAs<RValueReferenceType>(); 975218893Sdim Comparison.ArgIsRvalueRef = ArgRef->getAs<RValueReferenceType>(); 976218893Sdim Comparison.Qualifiers = NeitherMoreQualified; 977221345Sdim 978221345Sdim Qualifiers ParamQuals = Param.getQualifiers(); 979221345Sdim Qualifiers ArgQuals = Arg.getQualifiers(); 980221345Sdim if (ParamQuals.isStrictSupersetOf(ArgQuals)) 981218893Sdim Comparison.Qualifiers = ParamMoreQualified; 982221345Sdim else if (ArgQuals.isStrictSupersetOf(ParamQuals)) 983218893Sdim Comparison.Qualifiers = ArgMoreQualified; 984218893Sdim RefParamComparisons->push_back(Comparison); 985218893Sdim } 986218893Sdim 987218893Sdim // C++0x [temp.deduct.partial]p7: 988218893Sdim // Remove any top-level cv-qualifiers: 989218893Sdim // - If P is a cv-qualified type, P is replaced by the cv-unqualified 990218893Sdim // version of P. 991218893Sdim Param = Param.getUnqualifiedType(); 992218893Sdim // - If A is a cv-qualified type, A is replaced by the cv-unqualified 993218893Sdim // version of A. 994218893Sdim Arg = Arg.getUnqualifiedType(); 995218893Sdim } else { 996218893Sdim // C++0x [temp.deduct.call]p4 bullet 1: 997218893Sdim // - If the original P is a reference type, the deduced A (i.e., the type 998218893Sdim // referred to by the reference) can be more cv-qualified than the 999218893Sdim // transformed A. 1000218893Sdim if (TDF & TDF_ParamWithReferenceType) { 1001218893Sdim Qualifiers Quals; 1002218893Sdim QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals); 1003218893Sdim Quals.setCVRQualifiers(Quals.getCVRQualifiers() & 1004218893Sdim Arg.getCVRQualifiers()); 1005218893Sdim Param = S.Context.getQualifiedType(UnqualParam, Quals); 1006218893Sdim } 1007218893Sdim 1008218893Sdim if ((TDF & TDF_TopLevelParameterTypeList) && !Param->isFunctionType()) { 1009218893Sdim // C++0x [temp.deduct.type]p10: 1010218893Sdim // If P and A are function types that originated from deduction when 1011218893Sdim // taking the address of a function template (14.8.2.2) or when deducing 1012218893Sdim // template arguments from a function declaration (14.8.2.6) and Pi and 1013218893Sdim // Ai are parameters of the top-level parameter-type-list of P and A, 1014218893Sdim // respectively, Pi is adjusted if it is an rvalue reference to a 1015218893Sdim // cv-unqualified template parameter and Ai is an lvalue reference, in 1016218893Sdim // which case the type of Pi is changed to be the template parameter 1017218893Sdim // type (i.e., T&& is changed to simply T). [ Note: As a result, when 1018218893Sdim // Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be 1019218893Sdim // deduced as X&. - end note ] 1020218893Sdim TDF &= ~TDF_TopLevelParameterTypeList; 1021218893Sdim 1022218893Sdim if (const RValueReferenceType *ParamRef 1023218893Sdim = Param->getAs<RValueReferenceType>()) { 1024218893Sdim if (isa<TemplateTypeParmType>(ParamRef->getPointeeType()) && 1025218893Sdim !ParamRef->getPointeeType().getQualifiers()) 1026218893Sdim if (Arg->isLValueReferenceType()) 1027218893Sdim Param = ParamRef->getPointeeType(); 1028218893Sdim } 1029218893Sdim } 1030194179Sed } 1031198092Srdivacky 1032193576Sed // C++ [temp.deduct.type]p9: 1033198092Srdivacky // A template type argument T, a template template argument TT or a 1034198092Srdivacky // template non-type argument i can be deduced if P and A have one of 1035193576Sed // the following forms: 1036193576Sed // 1037193576Sed // T 1038193576Sed // cv-list T 1039198092Srdivacky if (const TemplateTypeParmType *TemplateTypeParm 1040198092Srdivacky = Param->getAs<TemplateTypeParmType>()) { 1041226890Sdim // Just skip any attempts to deduce from a placeholder type. 1042226890Sdim if (Arg->isPlaceholderType()) 1043226890Sdim return Sema::TDK_Success; 1044226890Sdim 1045194179Sed unsigned Index = TemplateTypeParm->getIndex(); 1046198092Srdivacky bool RecanonicalizeArg = false; 1047194179Sed 1048198092Srdivacky // If the argument type is an array type, move the qualifiers up to the 1049198092Srdivacky // top level, so they can be matched with the qualifiers on the parameter. 1050198092Srdivacky if (isa<ArrayType>(Arg)) { 1051198092Srdivacky Qualifiers Quals; 1052203955Srdivacky Arg = S.Context.getUnqualifiedArrayType(Arg, Quals); 1053198092Srdivacky if (Quals) { 1054203955Srdivacky Arg = S.Context.getQualifiedType(Arg, Quals); 1055198092Srdivacky RecanonicalizeArg = true; 1056198092Srdivacky } 1057198092Srdivacky } 1058198092Srdivacky 1059193576Sed // The argument type can not be less qualified than the parameter 1060193576Sed // type. 1061221345Sdim if (!(TDF & TDF_IgnoreQualifiers) && 1062221345Sdim hasInconsistentOrSupersetQualifiersOf(Param, Arg)) { 1063194179Sed Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 1064212904Sdim Info.FirstArg = TemplateArgument(Param); 1065198893Srdivacky Info.SecondArg = TemplateArgument(Arg); 1066212904Sdim return Sema::TDK_Underqualified; 1067194179Sed } 1068193576Sed 1069193576Sed assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0"); 1070203955Srdivacky assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function"); 1071198092Srdivacky QualType DeducedType = Arg; 1072218893Sdim 1073221345Sdim // Remove any qualifiers on the parameter from the deduced type. 1074221345Sdim // We checked the qualifiers for consistency above. 1075221345Sdim Qualifiers DeducedQs = DeducedType.getQualifiers(); 1076221345Sdim Qualifiers ParamQs = Param.getQualifiers(); 1077221345Sdim DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers()); 1078221345Sdim if (ParamQs.hasObjCGCAttr()) 1079221345Sdim DeducedQs.removeObjCGCAttr(); 1080221345Sdim if (ParamQs.hasAddressSpace()) 1081221345Sdim DeducedQs.removeAddressSpace(); 1082224145Sdim if (ParamQs.hasObjCLifetime()) 1083224145Sdim DeducedQs.removeObjCLifetime(); 1084224145Sdim 1085224145Sdim // Objective-C ARC: 1086226890Sdim // If template deduction would produce a lifetime qualifier on a type 1087226890Sdim // that is not a lifetime type, template argument deduction fails. 1088226890Sdim if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() && 1089226890Sdim !DeducedType->isDependentType()) { 1090226890Sdim Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 1091226890Sdim Info.FirstArg = TemplateArgument(Param); 1092226890Sdim Info.SecondArg = TemplateArgument(Arg); 1093226890Sdim return Sema::TDK_Underqualified; 1094226890Sdim } 1095226890Sdim 1096226890Sdim // Objective-C ARC: 1097224145Sdim // If template deduction would produce an argument type with lifetime type 1098224145Sdim // but no lifetime qualifier, the __strong lifetime qualifier is inferred. 1099235633Sdim if (S.getLangOpts().ObjCAutoRefCount && 1100224145Sdim DeducedType->isObjCLifetimeType() && 1101224145Sdim !DeducedQs.hasObjCLifetime()) 1102224145Sdim DeducedQs.setObjCLifetime(Qualifiers::OCL_Strong); 1103224145Sdim 1104221345Sdim DeducedType = S.Context.getQualifiedType(DeducedType.getUnqualifiedType(), 1105221345Sdim DeducedQs); 1106221345Sdim 1107198092Srdivacky if (RecanonicalizeArg) 1108203955Srdivacky DeducedType = S.Context.getCanonicalType(DeducedType); 1109198092Srdivacky 1110218893Sdim DeducedTemplateArgument NewDeduced(DeducedType); 1111218893Sdim DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 1112218893Sdim Deduced[Index], 1113218893Sdim NewDeduced); 1114218893Sdim if (Result.isNull()) { 1115218893Sdim Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 1116218893Sdim Info.FirstArg = Deduced[Index]; 1117218893Sdim Info.SecondArg = NewDeduced; 1118218893Sdim return Sema::TDK_Inconsistent; 1119193576Sed } 1120218893Sdim 1121218893Sdim Deduced[Index] = Result; 1122194179Sed return Sema::TDK_Success; 1123193576Sed } 1124193576Sed 1125194179Sed // Set up the template argument deduction information for a failure. 1126198893Srdivacky Info.FirstArg = TemplateArgument(ParamIn); 1127198893Srdivacky Info.SecondArg = TemplateArgument(ArgIn); 1128194179Sed 1129218893Sdim // If the parameter is an already-substituted template parameter 1130218893Sdim // pack, do nothing: we don't know which of its arguments to look 1131218893Sdim // at, so we have to wait until all of the parameter packs in this 1132218893Sdim // expansion have arguments. 1133218893Sdim if (isa<SubstTemplateTypeParmPackType>(Param)) 1134218893Sdim return Sema::TDK_Success; 1135218893Sdim 1136195099Sed // Check the cv-qualifiers on the parameter and argument types. 1137252723Sdim CanQualType CanParam = S.Context.getCanonicalType(Param); 1138252723Sdim CanQualType CanArg = S.Context.getCanonicalType(Arg); 1139195099Sed if (!(TDF & TDF_IgnoreQualifiers)) { 1140195099Sed if (TDF & TDF_ParamWithReferenceType) { 1141221345Sdim if (hasInconsistentOrSupersetQualifiersOf(Param, Arg)) 1142195099Sed return Sema::TDK_NonDeducedMismatch; 1143212904Sdim } else if (!IsPossiblyOpaquelyQualifiedType(Param)) { 1144195099Sed if (Param.getCVRQualifiers() != Arg.getCVRQualifiers()) 1145198092Srdivacky return Sema::TDK_NonDeducedMismatch; 1146195099Sed } 1147235633Sdim 1148235633Sdim // If the parameter type is not dependent, there is nothing to deduce. 1149235633Sdim if (!Param->isDependentType()) { 1150252723Sdim if (!(TDF & TDF_SkipNonDependent)) { 1151252723Sdim bool NonDeduced = (TDF & TDF_InOverloadResolution)? 1152252723Sdim !S.isSameOrCompatibleFunctionType(CanParam, CanArg) : 1153252723Sdim Param != Arg; 1154252723Sdim if (NonDeduced) { 1155252723Sdim return Sema::TDK_NonDeducedMismatch; 1156252723Sdim } 1157252723Sdim } 1158235633Sdim return Sema::TDK_Success; 1159235633Sdim } 1160252723Sdim } else if (!Param->isDependentType()) { 1161252723Sdim CanQualType ParamUnqualType = CanParam.getUnqualifiedType(), 1162252723Sdim ArgUnqualType = CanArg.getUnqualifiedType(); 1163252723Sdim bool Success = (TDF & TDF_InOverloadResolution)? 1164252723Sdim S.isSameOrCompatibleFunctionType(ParamUnqualType, 1165252723Sdim ArgUnqualType) : 1166252723Sdim ParamUnqualType == ArgUnqualType; 1167252723Sdim if (Success) 1168252723Sdim return Sema::TDK_Success; 1169195099Sed } 1170193576Sed 1171193576Sed switch (Param->getTypeClass()) { 1172224145Sdim // Non-canonical types cannot appear here. 1173224145Sdim#define NON_CANONICAL_TYPE(Class, Base) \ 1174224145Sdim case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class); 1175224145Sdim#define TYPE(Class, Base) 1176224145Sdim#include "clang/AST/TypeNodes.def" 1177224145Sdim 1178224145Sdim case Type::TemplateTypeParm: 1179224145Sdim case Type::SubstTemplateTypeParmPack: 1180224145Sdim llvm_unreachable("Type nodes handled above"); 1181235633Sdim 1182235633Sdim // These types cannot be dependent, so simply check whether the types are 1183235633Sdim // the same. 1184193576Sed case Type::Builtin: 1185224145Sdim case Type::VariableArray: 1186224145Sdim case Type::Vector: 1187224145Sdim case Type::FunctionNoProto: 1188224145Sdim case Type::Record: 1189224145Sdim case Type::Enum: 1190224145Sdim case Type::ObjCObject: 1191224145Sdim case Type::ObjCInterface: 1192235633Sdim case Type::ObjCObjectPointer: { 1193235633Sdim if (TDF & TDF_SkipNonDependent) 1194235633Sdim return Sema::TDK_Success; 1195235633Sdim 1196235633Sdim if (TDF & TDF_IgnoreQualifiers) { 1197235633Sdim Param = Param.getUnqualifiedType(); 1198235633Sdim Arg = Arg.getUnqualifiedType(); 1199235633Sdim } 1200235633Sdim 1201235633Sdim return Param == Arg? Sema::TDK_Success : Sema::TDK_NonDeducedMismatch; 1202235633Sdim } 1203235633Sdim 1204224145Sdim // _Complex T [placeholder extension] 1205224145Sdim case Type::Complex: 1206224145Sdim if (const ComplexType *ComplexArg = Arg->getAs<ComplexType>()) 1207235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1208224145Sdim cast<ComplexType>(Param)->getElementType(), 1209235633Sdim ComplexArg->getElementType(), 1210235633Sdim Info, Deduced, TDF); 1211224145Sdim 1212224145Sdim return Sema::TDK_NonDeducedMismatch; 1213226890Sdim 1214226890Sdim // _Atomic T [extension] 1215226890Sdim case Type::Atomic: 1216226890Sdim if (const AtomicType *AtomicArg = Arg->getAs<AtomicType>()) 1217235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1218226890Sdim cast<AtomicType>(Param)->getValueType(), 1219226890Sdim AtomicArg->getValueType(), 1220226890Sdim Info, Deduced, TDF); 1221226890Sdim 1222226890Sdim return Sema::TDK_NonDeducedMismatch; 1223226890Sdim 1224193576Sed // T * 1225193576Sed case Type::Pointer: { 1226208600Srdivacky QualType PointeeType; 1227208600Srdivacky if (const PointerType *PointerArg = Arg->getAs<PointerType>()) { 1228208600Srdivacky PointeeType = PointerArg->getPointeeType(); 1229208600Srdivacky } else if (const ObjCObjectPointerType *PointerArg 1230208600Srdivacky = Arg->getAs<ObjCObjectPointerType>()) { 1231208600Srdivacky PointeeType = PointerArg->getPointeeType(); 1232208600Srdivacky } else { 1233194179Sed return Sema::TDK_NonDeducedMismatch; 1234208600Srdivacky } 1235198092Srdivacky 1236195099Sed unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass); 1237235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1238235633Sdim cast<PointerType>(Param)->getPointeeType(), 1239208600Srdivacky PointeeType, 1240195099Sed Info, Deduced, SubTDF); 1241193576Sed } 1242198092Srdivacky 1243193576Sed // T & 1244193576Sed case Type::LValueReference: { 1245198092Srdivacky const LValueReferenceType *ReferenceArg = Arg->getAs<LValueReferenceType>(); 1246193576Sed if (!ReferenceArg) 1247194179Sed return Sema::TDK_NonDeducedMismatch; 1248198092Srdivacky 1249235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1250193576Sed cast<LValueReferenceType>(Param)->getPointeeType(), 1251235633Sdim ReferenceArg->getPointeeType(), Info, Deduced, 0); 1252193576Sed } 1253193576Sed 1254193576Sed // T && [C++0x] 1255193576Sed case Type::RValueReference: { 1256198092Srdivacky const RValueReferenceType *ReferenceArg = Arg->getAs<RValueReferenceType>(); 1257193576Sed if (!ReferenceArg) 1258194179Sed return Sema::TDK_NonDeducedMismatch; 1259198092Srdivacky 1260235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1261235633Sdim cast<RValueReferenceType>(Param)->getPointeeType(), 1262235633Sdim ReferenceArg->getPointeeType(), 1263235633Sdim Info, Deduced, 0); 1264193576Sed } 1265198092Srdivacky 1266193576Sed // T [] (implied, but not stated explicitly) 1267193576Sed case Type::IncompleteArray: { 1268198092Srdivacky const IncompleteArrayType *IncompleteArrayArg = 1269203955Srdivacky S.Context.getAsIncompleteArrayType(Arg); 1270193576Sed if (!IncompleteArrayArg) 1271194179Sed return Sema::TDK_NonDeducedMismatch; 1272198092Srdivacky 1273212904Sdim unsigned SubTDF = TDF & TDF_IgnoreQualifiers; 1274235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1275235633Sdim S.Context.getAsIncompleteArrayType(Param)->getElementType(), 1276235633Sdim IncompleteArrayArg->getElementType(), 1277235633Sdim Info, Deduced, SubTDF); 1278193576Sed } 1279193576Sed 1280193576Sed // T [integer-constant] 1281193576Sed case Type::ConstantArray: { 1282198092Srdivacky const ConstantArrayType *ConstantArrayArg = 1283203955Srdivacky S.Context.getAsConstantArrayType(Arg); 1284193576Sed if (!ConstantArrayArg) 1285194179Sed return Sema::TDK_NonDeducedMismatch; 1286198092Srdivacky 1287198092Srdivacky const ConstantArrayType *ConstantArrayParm = 1288203955Srdivacky S.Context.getAsConstantArrayType(Param); 1289193576Sed if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize()) 1290194179Sed return Sema::TDK_NonDeducedMismatch; 1291198092Srdivacky 1292212904Sdim unsigned SubTDF = TDF & TDF_IgnoreQualifiers; 1293235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1294235633Sdim ConstantArrayParm->getElementType(), 1295235633Sdim ConstantArrayArg->getElementType(), 1296235633Sdim Info, Deduced, SubTDF); 1297193576Sed } 1298193576Sed 1299193576Sed // type [i] 1300193576Sed case Type::DependentSizedArray: { 1301203955Srdivacky const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg); 1302193576Sed if (!ArrayArg) 1303194179Sed return Sema::TDK_NonDeducedMismatch; 1304198092Srdivacky 1305212904Sdim unsigned SubTDF = TDF & TDF_IgnoreQualifiers; 1306212904Sdim 1307193576Sed // Check the element type of the arrays 1308193576Sed const DependentSizedArrayType *DependentArrayParm 1309203955Srdivacky = S.Context.getAsDependentSizedArrayType(Param); 1310194179Sed if (Sema::TemplateDeductionResult Result 1311235633Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1312235633Sdim DependentArrayParm->getElementType(), 1313235633Sdim ArrayArg->getElementType(), 1314235633Sdim Info, Deduced, SubTDF)) 1315194179Sed return Result; 1316198092Srdivacky 1317193576Sed // Determine the array bound is something we can deduce. 1318198092Srdivacky NonTypeTemplateParmDecl *NTTP 1319193576Sed = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr()); 1320193576Sed if (!NTTP) 1321194179Sed return Sema::TDK_Success; 1322198092Srdivacky 1323198092Srdivacky // We can perform template argument deduction for the given non-type 1324193576Sed // template parameter. 1325198092Srdivacky assert(NTTP->getDepth() == 0 && 1326193576Sed "Cannot deduce non-type template argument at depth > 0"); 1327198092Srdivacky if (const ConstantArrayType *ConstantArrayArg 1328194613Sed = dyn_cast<ConstantArrayType>(ArrayArg)) { 1329194613Sed llvm::APSInt Size(ConstantArrayArg->getSize()); 1330218893Sdim return DeduceNonTypeTemplateArgument(S, NTTP, Size, 1331206084Srdivacky S.Context.getSizeType(), 1332206084Srdivacky /*ArrayBound=*/true, 1333194179Sed Info, Deduced); 1334194613Sed } 1335193576Sed if (const DependentSizedArrayType *DependentArrayArg 1336193576Sed = dyn_cast<DependentSizedArrayType>(ArrayArg)) 1337218893Sdim if (DependentArrayArg->getSizeExpr()) 1338218893Sdim return DeduceNonTypeTemplateArgument(S, NTTP, 1339218893Sdim DependentArrayArg->getSizeExpr(), 1340218893Sdim Info, Deduced); 1341198092Srdivacky 1342193576Sed // Incomplete type does not match a dependently-sized array type 1343194179Sed return Sema::TDK_NonDeducedMismatch; 1344193576Sed } 1345198092Srdivacky 1346198092Srdivacky // type(*)(T) 1347198092Srdivacky // T(*)() 1348198092Srdivacky // T(*)(T) 1349193725Sed case Type::FunctionProto: { 1350218893Sdim unsigned SubTDF = TDF & TDF_TopLevelParameterTypeList; 1351198092Srdivacky const FunctionProtoType *FunctionProtoArg = 1352193725Sed dyn_cast<FunctionProtoType>(Arg); 1353193725Sed if (!FunctionProtoArg) 1354194179Sed return Sema::TDK_NonDeducedMismatch; 1355198092Srdivacky 1356198092Srdivacky const FunctionProtoType *FunctionProtoParam = 1357193725Sed cast<FunctionProtoType>(Param); 1358194179Sed 1359218893Sdim if (FunctionProtoParam->getTypeQuals() 1360218893Sdim != FunctionProtoArg->getTypeQuals() || 1361218893Sdim FunctionProtoParam->getRefQualifier() 1362218893Sdim != FunctionProtoArg->getRefQualifier() || 1363218893Sdim FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic()) 1364194179Sed return Sema::TDK_NonDeducedMismatch; 1365198092Srdivacky 1366193725Sed // Check return types. 1367194179Sed if (Sema::TemplateDeductionResult Result 1368235633Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1369235633Sdim FunctionProtoParam->getResultType(), 1370235633Sdim FunctionProtoArg->getResultType(), 1371235633Sdim Info, Deduced, 0)) 1372194179Sed return Result; 1373198092Srdivacky 1374218893Sdim return DeduceTemplateArguments(S, TemplateParams, 1375218893Sdim FunctionProtoParam->arg_type_begin(), 1376218893Sdim FunctionProtoParam->getNumArgs(), 1377218893Sdim FunctionProtoArg->arg_type_begin(), 1378218893Sdim FunctionProtoArg->getNumArgs(), 1379218893Sdim Info, Deduced, SubTDF); 1380193725Sed } 1381198092Srdivacky 1382204962Srdivacky case Type::InjectedClassName: { 1383204962Srdivacky // Treat a template's injected-class-name as if the template 1384204962Srdivacky // specialization type had been used. 1385207619Srdivacky Param = cast<InjectedClassNameType>(Param) 1386207619Srdivacky ->getInjectedSpecializationType(); 1387204962Srdivacky assert(isa<TemplateSpecializationType>(Param) && 1388204962Srdivacky "injected class name is not a template specialization type"); 1389204962Srdivacky // fall through 1390204962Srdivacky } 1391204962Srdivacky 1392195099Sed // template-name<T> (where template-name refers to a class template) 1393194179Sed // template-name<i> 1394199482Srdivacky // TT<T> 1395199482Srdivacky // TT<i> 1396199482Srdivacky // TT<> 1397194179Sed case Type::TemplateSpecialization: { 1398194179Sed const TemplateSpecializationType *SpecParam 1399194179Sed = cast<TemplateSpecializationType>(Param); 1400194179Sed 1401198092Srdivacky // Try to deduce template arguments from the template-id. 1402198092Srdivacky Sema::TemplateDeductionResult Result 1403203955Srdivacky = DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg, 1404198092Srdivacky Info, Deduced); 1405194179Sed 1406198092Srdivacky if (Result && (TDF & TDF_DerivedClass)) { 1407198092Srdivacky // C++ [temp.deduct.call]p3b3: 1408198092Srdivacky // If P is a class, and P has the form template-id, then A can be a 1409198092Srdivacky // derived class of the deduced A. Likewise, if P is a pointer to a 1410198092Srdivacky // class of the form template-id, A can be a pointer to a derived 1411198092Srdivacky // class pointed to by the deduced A. 1412198092Srdivacky // 1413198092Srdivacky // More importantly: 1414198092Srdivacky // These alternatives are considered only if type deduction would 1415198092Srdivacky // otherwise fail. 1416203955Srdivacky if (const RecordType *RecordT = Arg->getAs<RecordType>()) { 1417203955Srdivacky // We cannot inspect base classes as part of deduction when the type 1418203955Srdivacky // is incomplete, so either instantiate any templates necessary to 1419203955Srdivacky // complete the type, or skip over it if it cannot be completed. 1420203955Srdivacky if (S.RequireCompleteType(Info.getLocation(), Arg, 0)) 1421203955Srdivacky return Result; 1422203955Srdivacky 1423198092Srdivacky // Use data recursion to crawl through the list of base classes. 1424198092Srdivacky // Visited contains the set of nodes we have already visited, while 1425198092Srdivacky // ToVisit is our stack of records that we still need to visit. 1426198092Srdivacky llvm::SmallPtrSet<const RecordType *, 8> Visited; 1427226890Sdim SmallVector<const RecordType *, 8> ToVisit; 1428198092Srdivacky ToVisit.push_back(RecordT); 1429198092Srdivacky bool Successful = false; 1430235633Sdim SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(), 1431235633Sdim Deduced.end()); 1432198092Srdivacky while (!ToVisit.empty()) { 1433198092Srdivacky // Retrieve the next class in the inheritance hierarchy. 1434263509Sdim const RecordType *NextT = ToVisit.pop_back_val(); 1435194179Sed 1436198092Srdivacky // If we have already seen this type, skip it. 1437198092Srdivacky if (!Visited.insert(NextT)) 1438198092Srdivacky continue; 1439194179Sed 1440198092Srdivacky // If this is a base class, try to perform template argument 1441198092Srdivacky // deduction from it. 1442198092Srdivacky if (NextT != RecordT) { 1443245431Sdim TemplateDeductionInfo BaseInfo(Info.getLocation()); 1444198092Srdivacky Sema::TemplateDeductionResult BaseResult 1445203955Srdivacky = DeduceTemplateArguments(S, TemplateParams, SpecParam, 1446245431Sdim QualType(NextT, 0), BaseInfo, 1447245431Sdim Deduced); 1448194179Sed 1449198092Srdivacky // If template argument deduction for this base was successful, 1450218893Sdim // note that we had some success. Otherwise, ignore any deductions 1451218893Sdim // from this base class. 1452218893Sdim if (BaseResult == Sema::TDK_Success) { 1453198092Srdivacky Successful = true; 1454235633Sdim DeducedOrig.clear(); 1455235633Sdim DeducedOrig.append(Deduced.begin(), Deduced.end()); 1456245431Sdim Info.Param = BaseInfo.Param; 1457245431Sdim Info.FirstArg = BaseInfo.FirstArg; 1458245431Sdim Info.SecondArg = BaseInfo.SecondArg; 1459218893Sdim } 1460218893Sdim else 1461218893Sdim Deduced = DeducedOrig; 1462198092Srdivacky } 1463194179Sed 1464198092Srdivacky // Visit base classes 1465198092Srdivacky CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl()); 1466198092Srdivacky for (CXXRecordDecl::base_class_iterator Base = Next->bases_begin(), 1467198092Srdivacky BaseEnd = Next->bases_end(); 1468198893Srdivacky Base != BaseEnd; ++Base) { 1469198092Srdivacky assert(Base->getType()->isRecordType() && 1470198092Srdivacky "Base class that isn't a record?"); 1471198092Srdivacky ToVisit.push_back(Base->getType()->getAs<RecordType>()); 1472198092Srdivacky } 1473198092Srdivacky } 1474195099Sed 1475198092Srdivacky if (Successful) 1476198092Srdivacky return Sema::TDK_Success; 1477198092Srdivacky } 1478194179Sed 1479198092Srdivacky } 1480194179Sed 1481198092Srdivacky return Result; 1482194179Sed } 1483194179Sed 1484194179Sed // T type::* 1485194179Sed // T T::* 1486194179Sed // T (type::*)() 1487194179Sed // type (T::*)() 1488194179Sed // type (type::*)(T) 1489194179Sed // type (T::*)(T) 1490194179Sed // T (type::*)(T) 1491194179Sed // T (T::*)() 1492194179Sed // T (T::*)(T) 1493194179Sed case Type::MemberPointer: { 1494194179Sed const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param); 1495194179Sed const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg); 1496194179Sed if (!MemPtrArg) 1497194179Sed return Sema::TDK_NonDeducedMismatch; 1498194179Sed 1499194179Sed if (Sema::TemplateDeductionResult Result 1500235633Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1501235633Sdim MemPtrParam->getPointeeType(), 1502235633Sdim MemPtrArg->getPointeeType(), 1503235633Sdim Info, Deduced, 1504235633Sdim TDF & TDF_IgnoreQualifiers)) 1505194179Sed return Result; 1506194179Sed 1507235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1508235633Sdim QualType(MemPtrParam->getClass(), 0), 1509235633Sdim QualType(MemPtrArg->getClass(), 0), 1510235633Sdim Info, Deduced, 1511235633Sdim TDF & TDF_IgnoreQualifiers); 1512194179Sed } 1513194179Sed 1514194179Sed // (clang extension) 1515194179Sed // 1516198092Srdivacky // type(^)(T) 1517198092Srdivacky // T(^)() 1518198092Srdivacky // T(^)(T) 1519194179Sed case Type::BlockPointer: { 1520194179Sed const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param); 1521194179Sed const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg); 1522198092Srdivacky 1523194179Sed if (!BlockPtrArg) 1524194179Sed return Sema::TDK_NonDeducedMismatch; 1525198092Srdivacky 1526235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1527235633Sdim BlockPtrParam->getPointeeType(), 1528235633Sdim BlockPtrArg->getPointeeType(), 1529235633Sdim Info, Deduced, 0); 1530194179Sed } 1531194179Sed 1532224145Sdim // (clang extension) 1533224145Sdim // 1534224145Sdim // T __attribute__(((ext_vector_type(<integral constant>)))) 1535224145Sdim case Type::ExtVector: { 1536224145Sdim const ExtVectorType *VectorParam = cast<ExtVectorType>(Param); 1537224145Sdim if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) { 1538224145Sdim // Make sure that the vectors have the same number of elements. 1539224145Sdim if (VectorParam->getNumElements() != VectorArg->getNumElements()) 1540224145Sdim return Sema::TDK_NonDeducedMismatch; 1541224145Sdim 1542224145Sdim // Perform deduction on the element types. 1543235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1544235633Sdim VectorParam->getElementType(), 1545235633Sdim VectorArg->getElementType(), 1546235633Sdim Info, Deduced, TDF); 1547224145Sdim } 1548224145Sdim 1549224145Sdim if (const DependentSizedExtVectorType *VectorArg 1550224145Sdim = dyn_cast<DependentSizedExtVectorType>(Arg)) { 1551224145Sdim // We can't check the number of elements, since the argument has a 1552224145Sdim // dependent number of elements. This can only occur during partial 1553224145Sdim // ordering. 1554224145Sdim 1555224145Sdim // Perform deduction on the element types. 1556235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1557235633Sdim VectorParam->getElementType(), 1558235633Sdim VectorArg->getElementType(), 1559235633Sdim Info, Deduced, TDF); 1560224145Sdim } 1561224145Sdim 1562224145Sdim return Sema::TDK_NonDeducedMismatch; 1563224145Sdim } 1564224145Sdim 1565224145Sdim // (clang extension) 1566224145Sdim // 1567224145Sdim // T __attribute__(((ext_vector_type(N)))) 1568224145Sdim case Type::DependentSizedExtVector: { 1569224145Sdim const DependentSizedExtVectorType *VectorParam 1570224145Sdim = cast<DependentSizedExtVectorType>(Param); 1571224145Sdim 1572224145Sdim if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) { 1573224145Sdim // Perform deduction on the element types. 1574224145Sdim if (Sema::TemplateDeductionResult Result 1575235633Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1576235633Sdim VectorParam->getElementType(), 1577235633Sdim VectorArg->getElementType(), 1578235633Sdim Info, Deduced, TDF)) 1579224145Sdim return Result; 1580224145Sdim 1581224145Sdim // Perform deduction on the vector size, if we can. 1582224145Sdim NonTypeTemplateParmDecl *NTTP 1583224145Sdim = getDeducedParameterFromExpr(VectorParam->getSizeExpr()); 1584224145Sdim if (!NTTP) 1585224145Sdim return Sema::TDK_Success; 1586224145Sdim 1587224145Sdim llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false); 1588224145Sdim ArgSize = VectorArg->getNumElements(); 1589224145Sdim return DeduceNonTypeTemplateArgument(S, NTTP, ArgSize, S.Context.IntTy, 1590224145Sdim false, Info, Deduced); 1591224145Sdim } 1592224145Sdim 1593224145Sdim if (const DependentSizedExtVectorType *VectorArg 1594224145Sdim = dyn_cast<DependentSizedExtVectorType>(Arg)) { 1595224145Sdim // Perform deduction on the element types. 1596224145Sdim if (Sema::TemplateDeductionResult Result 1597235633Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1598235633Sdim VectorParam->getElementType(), 1599235633Sdim VectorArg->getElementType(), 1600235633Sdim Info, Deduced, TDF)) 1601224145Sdim return Result; 1602224145Sdim 1603224145Sdim // Perform deduction on the vector size, if we can. 1604224145Sdim NonTypeTemplateParmDecl *NTTP 1605224145Sdim = getDeducedParameterFromExpr(VectorParam->getSizeExpr()); 1606224145Sdim if (!NTTP) 1607224145Sdim return Sema::TDK_Success; 1608224145Sdim 1609224145Sdim return DeduceNonTypeTemplateArgument(S, NTTP, VectorArg->getSizeExpr(), 1610224145Sdim Info, Deduced); 1611224145Sdim } 1612224145Sdim 1613224145Sdim return Sema::TDK_NonDeducedMismatch; 1614224145Sdim } 1615224145Sdim 1616194179Sed case Type::TypeOfExpr: 1617194179Sed case Type::TypeOf: 1618206084Srdivacky case Type::DependentName: 1619224145Sdim case Type::UnresolvedUsing: 1620224145Sdim case Type::Decltype: 1621224145Sdim case Type::UnaryTransform: 1622224145Sdim case Type::Auto: 1623224145Sdim case Type::DependentTemplateSpecialization: 1624224145Sdim case Type::PackExpansion: 1625194179Sed // No template argument deduction for these types 1626194179Sed return Sema::TDK_Success; 1627193576Sed } 1628193576Sed 1629235633Sdim llvm_unreachable("Invalid Type Class!"); 1630193576Sed} 1631193576Sed 1632194179Sedstatic Sema::TemplateDeductionResult 1633203955SrdivackyDeduceTemplateArguments(Sema &S, 1634194179Sed TemplateParameterList *TemplateParams, 1635194179Sed const TemplateArgument &Param, 1636218893Sdim TemplateArgument Arg, 1637212904Sdim TemplateDeductionInfo &Info, 1638263509Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 1639218893Sdim // If the template argument is a pack expansion, perform template argument 1640218893Sdim // deduction against the pattern of that expansion. This only occurs during 1641218893Sdim // partial ordering. 1642218893Sdim if (Arg.isPackExpansion()) 1643218893Sdim Arg = Arg.getPackExpansionPattern(); 1644218893Sdim 1645193576Sed switch (Param.getKind()) { 1646193576Sed case TemplateArgument::Null: 1647226890Sdim llvm_unreachable("Null template argument in parameter list"); 1648198092Srdivacky 1649198092Srdivacky case TemplateArgument::Type: 1650199482Srdivacky if (Arg.getKind() == TemplateArgument::Type) 1651235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1652235633Sdim Param.getAsType(), 1653235633Sdim Arg.getAsType(), 1654235633Sdim Info, Deduced, 0); 1655199482Srdivacky Info.FirstArg = Param; 1656199482Srdivacky Info.SecondArg = Arg; 1657199482Srdivacky return Sema::TDK_NonDeducedMismatch; 1658218893Sdim 1659199482Srdivacky case TemplateArgument::Template: 1660199482Srdivacky if (Arg.getKind() == TemplateArgument::Template) 1661218893Sdim return DeduceTemplateArguments(S, TemplateParams, 1662199482Srdivacky Param.getAsTemplate(), 1663199482Srdivacky Arg.getAsTemplate(), Info, Deduced); 1664199482Srdivacky Info.FirstArg = Param; 1665199482Srdivacky Info.SecondArg = Arg; 1666199482Srdivacky return Sema::TDK_NonDeducedMismatch; 1667218893Sdim 1668218893Sdim case TemplateArgument::TemplateExpansion: 1669218893Sdim llvm_unreachable("caller should handle pack expansions"); 1670218893Sdim 1671193576Sed case TemplateArgument::Declaration: 1672199482Srdivacky if (Arg.getKind() == TemplateArgument::Declaration && 1673245431Sdim isSameDeclaration(Param.getAsDecl(), Arg.getAsDecl()) && 1674245431Sdim Param.isDeclForReferenceParam() == Arg.isDeclForReferenceParam()) 1675199482Srdivacky return Sema::TDK_Success; 1676218893Sdim 1677194179Sed Info.FirstArg = Param; 1678194179Sed Info.SecondArg = Arg; 1679194179Sed return Sema::TDK_NonDeducedMismatch; 1680198092Srdivacky 1681245431Sdim case TemplateArgument::NullPtr: 1682245431Sdim if (Arg.getKind() == TemplateArgument::NullPtr && 1683245431Sdim S.Context.hasSameType(Param.getNullPtrType(), Arg.getNullPtrType())) 1684245431Sdim return Sema::TDK_Success; 1685245431Sdim 1686245431Sdim Info.FirstArg = Param; 1687245431Sdim Info.SecondArg = Arg; 1688245431Sdim return Sema::TDK_NonDeducedMismatch; 1689245431Sdim 1690193576Sed case TemplateArgument::Integral: 1691193576Sed if (Arg.getKind() == TemplateArgument::Integral) { 1692245431Sdim if (hasSameExtendedValue(Param.getAsIntegral(), Arg.getAsIntegral())) 1693194179Sed return Sema::TDK_Success; 1694194179Sed 1695194179Sed Info.FirstArg = Param; 1696194179Sed Info.SecondArg = Arg; 1697194179Sed return Sema::TDK_NonDeducedMismatch; 1698193576Sed } 1699193576Sed 1700194179Sed if (Arg.getKind() == TemplateArgument::Expression) { 1701194179Sed Info.FirstArg = Param; 1702194179Sed Info.SecondArg = Arg; 1703194179Sed return Sema::TDK_NonDeducedMismatch; 1704194179Sed } 1705194179Sed 1706194179Sed Info.FirstArg = Param; 1707194179Sed Info.SecondArg = Arg; 1708194179Sed return Sema::TDK_NonDeducedMismatch; 1709198092Srdivacky 1710193576Sed case TemplateArgument::Expression: { 1711198092Srdivacky if (NonTypeTemplateParmDecl *NTTP 1712193576Sed = getDeducedParameterFromExpr(Param.getAsExpr())) { 1713193576Sed if (Arg.getKind() == TemplateArgument::Integral) 1714203955Srdivacky return DeduceNonTypeTemplateArgument(S, NTTP, 1715245431Sdim Arg.getAsIntegral(), 1716206084Srdivacky Arg.getIntegralType(), 1717206084Srdivacky /*ArrayBound=*/false, 1718194179Sed Info, Deduced); 1719193576Sed if (Arg.getKind() == TemplateArgument::Expression) 1720203955Srdivacky return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(), 1721194179Sed Info, Deduced); 1722199482Srdivacky if (Arg.getKind() == TemplateArgument::Declaration) 1723203955Srdivacky return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(), 1724199482Srdivacky Info, Deduced); 1725218893Sdim 1726194179Sed Info.FirstArg = Param; 1727194179Sed Info.SecondArg = Arg; 1728194179Sed return Sema::TDK_NonDeducedMismatch; 1729193576Sed } 1730198092Srdivacky 1731193576Sed // Can't deduce anything, but that's okay. 1732194179Sed return Sema::TDK_Success; 1733193576Sed } 1734194613Sed case TemplateArgument::Pack: 1735218893Sdim llvm_unreachable("Argument packs should be expanded by the caller!"); 1736193576Sed } 1737198092Srdivacky 1738235633Sdim llvm_unreachable("Invalid TemplateArgument Kind!"); 1739193576Sed} 1740193576Sed 1741218893Sdim/// \brief Determine whether there is a template argument to be used for 1742218893Sdim/// deduction. 1743218893Sdim/// 1744218893Sdim/// This routine "expands" argument packs in-place, overriding its input 1745218893Sdim/// parameters so that \c Args[ArgIdx] will be the available template argument. 1746218893Sdim/// 1747218893Sdim/// \returns true if there is another template argument (which will be at 1748218893Sdim/// \c Args[ArgIdx]), false otherwise. 1749218893Sdimstatic bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args, 1750218893Sdim unsigned &ArgIdx, 1751218893Sdim unsigned &NumArgs) { 1752218893Sdim if (ArgIdx == NumArgs) 1753218893Sdim return false; 1754218893Sdim 1755218893Sdim const TemplateArgument &Arg = Args[ArgIdx]; 1756218893Sdim if (Arg.getKind() != TemplateArgument::Pack) 1757218893Sdim return true; 1758218893Sdim 1759218893Sdim assert(ArgIdx == NumArgs - 1 && "Pack not at the end of argument list?"); 1760218893Sdim Args = Arg.pack_begin(); 1761218893Sdim NumArgs = Arg.pack_size(); 1762218893Sdim ArgIdx = 0; 1763218893Sdim return ArgIdx < NumArgs; 1764218893Sdim} 1765218893Sdim 1766218893Sdim/// \brief Determine whether the given set of template arguments has a pack 1767218893Sdim/// expansion that is not the last template argument. 1768218893Sdimstatic bool hasPackExpansionBeforeEnd(const TemplateArgument *Args, 1769218893Sdim unsigned NumArgs) { 1770218893Sdim unsigned ArgIdx = 0; 1771218893Sdim while (ArgIdx < NumArgs) { 1772218893Sdim const TemplateArgument &Arg = Args[ArgIdx]; 1773218893Sdim 1774218893Sdim // Unwrap argument packs. 1775218893Sdim if (Args[ArgIdx].getKind() == TemplateArgument::Pack) { 1776218893Sdim Args = Arg.pack_begin(); 1777218893Sdim NumArgs = Arg.pack_size(); 1778218893Sdim ArgIdx = 0; 1779218893Sdim continue; 1780218893Sdim } 1781218893Sdim 1782218893Sdim ++ArgIdx; 1783218893Sdim if (ArgIdx == NumArgs) 1784218893Sdim return false; 1785218893Sdim 1786218893Sdim if (Arg.isPackExpansion()) 1787218893Sdim return true; 1788218893Sdim } 1789218893Sdim 1790218893Sdim return false; 1791218893Sdim} 1792218893Sdim 1793198092Srdivackystatic Sema::TemplateDeductionResult 1794203955SrdivackyDeduceTemplateArguments(Sema &S, 1795194179Sed TemplateParameterList *TemplateParams, 1796218893Sdim const TemplateArgument *Params, unsigned NumParams, 1797218893Sdim const TemplateArgument *Args, unsigned NumArgs, 1798212904Sdim TemplateDeductionInfo &Info, 1799252723Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 1800218893Sdim // C++0x [temp.deduct.type]p9: 1801218893Sdim // If the template argument list of P contains a pack expansion that is not 1802218893Sdim // the last template argument, the entire template argument list is a 1803218893Sdim // non-deduced context. 1804218893Sdim if (hasPackExpansionBeforeEnd(Params, NumParams)) 1805218893Sdim return Sema::TDK_Success; 1806218893Sdim 1807218893Sdim // C++0x [temp.deduct.type]p9: 1808218893Sdim // If P has a form that contains <T> or <i>, then each argument Pi of the 1809218893Sdim // respective template argument list P is compared with the corresponding 1810218893Sdim // argument Ai of the corresponding template argument list of A. 1811218893Sdim unsigned ArgIdx = 0, ParamIdx = 0; 1812218893Sdim for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams); 1813218893Sdim ++ParamIdx) { 1814218893Sdim if (!Params[ParamIdx].isPackExpansion()) { 1815218893Sdim // The simple case: deduce template arguments by matching Pi and Ai. 1816218893Sdim 1817218893Sdim // Check whether we have enough arguments. 1818218893Sdim if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) 1819252723Sdim return Sema::TDK_Success; 1820218893Sdim 1821218893Sdim if (Args[ArgIdx].isPackExpansion()) { 1822218893Sdim // FIXME: We follow the logic of C++0x [temp.deduct.type]p22 here, 1823218893Sdim // but applied to pack expansions that are template arguments. 1824252723Sdim return Sema::TDK_MiscellaneousDeductionFailure; 1825218893Sdim } 1826218893Sdim 1827218893Sdim // Perform deduction for this Pi/Ai pair. 1828218893Sdim if (Sema::TemplateDeductionResult Result 1829218893Sdim = DeduceTemplateArguments(S, TemplateParams, 1830218893Sdim Params[ParamIdx], Args[ArgIdx], 1831218893Sdim Info, Deduced)) 1832218893Sdim return Result; 1833218893Sdim 1834218893Sdim // Move to the next argument. 1835218893Sdim ++ArgIdx; 1836218893Sdim continue; 1837218893Sdim } 1838218893Sdim 1839218893Sdim // The parameter is a pack expansion. 1840218893Sdim 1841218893Sdim // C++0x [temp.deduct.type]p9: 1842218893Sdim // If Pi is a pack expansion, then the pattern of Pi is compared with 1843218893Sdim // each remaining argument in the template argument list of A. Each 1844218893Sdim // comparison deduces template arguments for subsequent positions in the 1845218893Sdim // template parameter packs expanded by Pi. 1846218893Sdim TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern(); 1847218893Sdim 1848218893Sdim // Compute the set of template parameter indices that correspond to 1849218893Sdim // parameter packs expanded by the pack expansion. 1850226890Sdim SmallVector<unsigned, 2> PackIndices; 1851218893Sdim { 1852235633Sdim llvm::SmallBitVector SawIndices(TemplateParams->size()); 1853226890Sdim SmallVector<UnexpandedParameterPack, 2> Unexpanded; 1854218893Sdim S.collectUnexpandedParameterPacks(Pattern, Unexpanded); 1855218893Sdim for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) { 1856218893Sdim unsigned Depth, Index; 1857218893Sdim llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]); 1858218893Sdim if (Depth == 0 && !SawIndices[Index]) { 1859218893Sdim SawIndices[Index] = true; 1860218893Sdim PackIndices.push_back(Index); 1861218893Sdim } 1862218893Sdim } 1863218893Sdim } 1864218893Sdim assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?"); 1865218893Sdim 1866218893Sdim // FIXME: If there are no remaining arguments, we can bail out early 1867218893Sdim // and set any deduced parameter packs to an empty argument pack. 1868218893Sdim // The latter part of this is a (minor) correctness issue. 1869218893Sdim 1870218893Sdim // Save the deduced template arguments for each parameter pack expanded 1871218893Sdim // by this pack expansion, then clear out the deduction. 1872226890Sdim SmallVector<DeducedTemplateArgument, 2> 1873218893Sdim SavedPacks(PackIndices.size()); 1874263509Sdim NewlyDeducedPacksType NewlyDeducedPacks(PackIndices.size()); 1875218893Sdim PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks, 1876218893Sdim NewlyDeducedPacks); 1877218893Sdim 1878218893Sdim // Keep track of the deduced template arguments for each parameter pack 1879218893Sdim // expanded by this pack expansion (the outer index) and for each 1880218893Sdim // template argument (the inner SmallVectors). 1881218893Sdim bool HasAnyArguments = false; 1882218893Sdim while (hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) { 1883218893Sdim HasAnyArguments = true; 1884218893Sdim 1885218893Sdim // Deduce template arguments from the pattern. 1886218893Sdim if (Sema::TemplateDeductionResult Result 1887218893Sdim = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx], 1888218893Sdim Info, Deduced)) 1889218893Sdim return Result; 1890218893Sdim 1891218893Sdim // Capture the deduced template arguments for each parameter pack expanded 1892218893Sdim // by this pack expansion, add them to the list of arguments we've deduced 1893218893Sdim // for that pack, then clear out the deduced argument. 1894218893Sdim for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 1895218893Sdim DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]]; 1896218893Sdim if (!DeducedArg.isNull()) { 1897218893Sdim NewlyDeducedPacks[I].push_back(DeducedArg); 1898218893Sdim DeducedArg = DeducedTemplateArgument(); 1899218893Sdim } 1900218893Sdim } 1901218893Sdim 1902218893Sdim ++ArgIdx; 1903218893Sdim } 1904218893Sdim 1905218893Sdim // Build argument packs for each of the parameter packs expanded by this 1906218893Sdim // pack expansion. 1907194179Sed if (Sema::TemplateDeductionResult Result 1908218893Sdim = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments, 1909218893Sdim Deduced, PackIndices, SavedPacks, 1910218893Sdim NewlyDeducedPacks, Info)) 1911194179Sed return Result; 1912193576Sed } 1913218893Sdim 1914194179Sed return Sema::TDK_Success; 1915193576Sed} 1916193576Sed 1917218893Sdimstatic Sema::TemplateDeductionResult 1918218893SdimDeduceTemplateArguments(Sema &S, 1919218893Sdim TemplateParameterList *TemplateParams, 1920218893Sdim const TemplateArgumentList &ParamList, 1921218893Sdim const TemplateArgumentList &ArgList, 1922218893Sdim TemplateDeductionInfo &Info, 1923263509Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 1924218893Sdim return DeduceTemplateArguments(S, TemplateParams, 1925218893Sdim ParamList.data(), ParamList.size(), 1926218893Sdim ArgList.data(), ArgList.size(), 1927218893Sdim Info, Deduced); 1928218893Sdim} 1929218893Sdim 1930195099Sed/// \brief Determine whether two template arguments are the same. 1931198092Srdivackystatic bool isSameTemplateArg(ASTContext &Context, 1932195099Sed const TemplateArgument &X, 1933195099Sed const TemplateArgument &Y) { 1934195099Sed if (X.getKind() != Y.getKind()) 1935195099Sed return false; 1936198092Srdivacky 1937195099Sed switch (X.getKind()) { 1938195099Sed case TemplateArgument::Null: 1939226890Sdim llvm_unreachable("Comparing NULL template argument"); 1940198092Srdivacky 1941195099Sed case TemplateArgument::Type: 1942195099Sed return Context.getCanonicalType(X.getAsType()) == 1943195099Sed Context.getCanonicalType(Y.getAsType()); 1944198092Srdivacky 1945195099Sed case TemplateArgument::Declaration: 1946245431Sdim return isSameDeclaration(X.getAsDecl(), Y.getAsDecl()) && 1947245431Sdim X.isDeclForReferenceParam() == Y.isDeclForReferenceParam(); 1948198092Srdivacky 1949245431Sdim case TemplateArgument::NullPtr: 1950245431Sdim return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType()); 1951245431Sdim 1952199482Srdivacky case TemplateArgument::Template: 1953218893Sdim case TemplateArgument::TemplateExpansion: 1954218893Sdim return Context.getCanonicalTemplateName( 1955218893Sdim X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() == 1956218893Sdim Context.getCanonicalTemplateName( 1957218893Sdim Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer(); 1958218893Sdim 1959195099Sed case TemplateArgument::Integral: 1960245431Sdim return X.getAsIntegral() == Y.getAsIntegral(); 1961198092Srdivacky 1962199482Srdivacky case TemplateArgument::Expression: { 1963199482Srdivacky llvm::FoldingSetNodeID XID, YID; 1964199482Srdivacky X.getAsExpr()->Profile(XID, Context, true); 1965218893Sdim Y.getAsExpr()->Profile(YID, Context, true); 1966199482Srdivacky return XID == YID; 1967199482Srdivacky } 1968198092Srdivacky 1969195099Sed case TemplateArgument::Pack: 1970195099Sed if (X.pack_size() != Y.pack_size()) 1971195099Sed return false; 1972198092Srdivacky 1973198092Srdivacky for (TemplateArgument::pack_iterator XP = X.pack_begin(), 1974198092Srdivacky XPEnd = X.pack_end(), 1975195099Sed YP = Y.pack_begin(); 1976198092Srdivacky XP != XPEnd; ++XP, ++YP) 1977195099Sed if (!isSameTemplateArg(Context, *XP, *YP)) 1978195099Sed return false; 1979195099Sed 1980195099Sed return true; 1981195099Sed } 1982195099Sed 1983235633Sdim llvm_unreachable("Invalid TemplateArgument Kind!"); 1984195099Sed} 1985195099Sed 1986218893Sdim/// \brief Allocate a TemplateArgumentLoc where all locations have 1987218893Sdim/// been initialized to the given location. 1988218893Sdim/// 1989218893Sdim/// \param S The semantic analysis object. 1990218893Sdim/// 1991245431Sdim/// \param Arg The template argument we are producing template argument 1992218893Sdim/// location information for. 1993218893Sdim/// 1994218893Sdim/// \param NTTPType For a declaration template argument, the type of 1995218893Sdim/// the non-type template parameter that corresponds to this template 1996218893Sdim/// argument. 1997218893Sdim/// 1998218893Sdim/// \param Loc The source location to use for the resulting template 1999218893Sdim/// argument. 2000218893Sdimstatic TemplateArgumentLoc 2001218893SdimgetTrivialTemplateArgumentLoc(Sema &S, 2002218893Sdim const TemplateArgument &Arg, 2003218893Sdim QualType NTTPType, 2004218893Sdim SourceLocation Loc) { 2005218893Sdim switch (Arg.getKind()) { 2006218893Sdim case TemplateArgument::Null: 2007218893Sdim llvm_unreachable("Can't get a NULL template argument here"); 2008198092Srdivacky 2009218893Sdim case TemplateArgument::Type: 2010218893Sdim return TemplateArgumentLoc(Arg, 2011218893Sdim S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc)); 2012218893Sdim 2013218893Sdim case TemplateArgument::Declaration: { 2014218893Sdim Expr *E 2015218893Sdim = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc) 2016235633Sdim .takeAs<Expr>(); 2017218893Sdim return TemplateArgumentLoc(TemplateArgument(E), E); 2018218893Sdim } 2019218893Sdim 2020245431Sdim case TemplateArgument::NullPtr: { 2021245431Sdim Expr *E 2022245431Sdim = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc) 2023245431Sdim .takeAs<Expr>(); 2024245431Sdim return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true), 2025245431Sdim E); 2026245431Sdim } 2027245431Sdim 2028218893Sdim case TemplateArgument::Integral: { 2029218893Sdim Expr *E 2030218893Sdim = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).takeAs<Expr>(); 2031218893Sdim return TemplateArgumentLoc(TemplateArgument(E), E); 2032218893Sdim } 2033218893Sdim 2034221345Sdim case TemplateArgument::Template: 2035221345Sdim case TemplateArgument::TemplateExpansion: { 2036221345Sdim NestedNameSpecifierLocBuilder Builder; 2037221345Sdim TemplateName Template = Arg.getAsTemplate(); 2038221345Sdim if (DependentTemplateName *DTN = Template.getAsDependentTemplateName()) 2039221345Sdim Builder.MakeTrivial(S.Context, DTN->getQualifier(), Loc); 2040221345Sdim else if (QualifiedTemplateName *QTN = Template.getAsQualifiedTemplateName()) 2041221345Sdim Builder.MakeTrivial(S.Context, QTN->getQualifier(), Loc); 2042221345Sdim 2043221345Sdim if (Arg.getKind() == TemplateArgument::Template) 2044221345Sdim return TemplateArgumentLoc(Arg, 2045221345Sdim Builder.getWithLocInContext(S.Context), 2046221345Sdim Loc); 2047221345Sdim 2048221345Sdim 2049221345Sdim return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(S.Context), 2050221345Sdim Loc, Loc); 2051221345Sdim } 2052218893Sdim 2053218893Sdim case TemplateArgument::Expression: 2054218893Sdim return TemplateArgumentLoc(Arg, Arg.getAsExpr()); 2055218893Sdim 2056218893Sdim case TemplateArgument::Pack: 2057218893Sdim return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo()); 2058218893Sdim } 2059218893Sdim 2060235633Sdim llvm_unreachable("Invalid TemplateArgument Kind!"); 2061195099Sed} 2062195099Sed 2063218893Sdim 2064218893Sdim/// \brief Convert the given deduced template argument and add it to the set of 2065218893Sdim/// fully-converted template arguments. 2066263509Sdimstatic bool 2067263509SdimConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param, 2068263509Sdim DeducedTemplateArgument Arg, 2069263509Sdim NamedDecl *Template, 2070263509Sdim QualType NTTPType, 2071263509Sdim unsigned ArgumentPackIndex, 2072263509Sdim TemplateDeductionInfo &Info, 2073263509Sdim bool InFunctionTemplate, 2074263509Sdim SmallVectorImpl<TemplateArgument> &Output) { 2075218893Sdim if (Arg.getKind() == TemplateArgument::Pack) { 2076218893Sdim // This is a template argument pack, so check each of its arguments against 2077218893Sdim // the template parameter. 2078226890Sdim SmallVector<TemplateArgument, 2> PackedArgsBuilder; 2079218893Sdim for (TemplateArgument::pack_iterator PA = Arg.pack_begin(), 2080218893Sdim PAEnd = Arg.pack_end(); 2081218893Sdim PA != PAEnd; ++PA) { 2082218893Sdim // When converting the deduced template argument, append it to the 2083218893Sdim // general output list. We need to do this so that the template argument 2084218893Sdim // checking logic has all of the prior template arguments available. 2085218893Sdim DeducedTemplateArgument InnerArg(*PA); 2086218893Sdim InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound()); 2087218893Sdim if (ConvertDeducedTemplateArgument(S, Param, InnerArg, Template, 2088218893Sdim NTTPType, PackedArgsBuilder.size(), 2089218893Sdim Info, InFunctionTemplate, Output)) 2090218893Sdim return true; 2091218893Sdim 2092218893Sdim // Move the converted template argument into our argument pack. 2093263509Sdim PackedArgsBuilder.push_back(Output.pop_back_val()); 2094218893Sdim } 2095218893Sdim 2096218893Sdim // Create the resulting argument pack. 2097218893Sdim Output.push_back(TemplateArgument::CreatePackCopy(S.Context, 2098218893Sdim PackedArgsBuilder.data(), 2099218893Sdim PackedArgsBuilder.size())); 2100218893Sdim return false; 2101218893Sdim } 2102218893Sdim 2103218893Sdim // Convert the deduced template argument into a template 2104218893Sdim // argument that we can check, almost as if the user had written 2105218893Sdim // the template argument explicitly. 2106218893Sdim TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType, 2107218893Sdim Info.getLocation()); 2108218893Sdim 2109218893Sdim // Check the template argument, converting it as necessary. 2110218893Sdim return S.CheckTemplateArgument(Param, ArgLoc, 2111218893Sdim Template, 2112218893Sdim Template->getLocation(), 2113218893Sdim Template->getSourceRange().getEnd(), 2114218893Sdim ArgumentPackIndex, 2115218893Sdim Output, 2116218893Sdim InFunctionTemplate 2117218893Sdim ? (Arg.wasDeducedFromArrayBound() 2118218893Sdim ? Sema::CTAK_DeducedFromArrayBound 2119218893Sdim : Sema::CTAK_Deduced) 2120218893Sdim : Sema::CTAK_Specified); 2121218893Sdim} 2122218893Sdim 2123207619Srdivacky/// Complete template argument deduction for a class template partial 2124207619Srdivacky/// specialization. 2125207619Srdivackystatic Sema::TemplateDeductionResult 2126218893SdimFinishTemplateArgumentDeduction(Sema &S, 2127207619Srdivacky ClassTemplatePartialSpecializationDecl *Partial, 2128207619Srdivacky const TemplateArgumentList &TemplateArgs, 2129226890Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2130212904Sdim TemplateDeductionInfo &Info) { 2131235633Sdim // Unevaluated SFINAE context. 2132235633Sdim EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated); 2133207619Srdivacky Sema::SFINAETrap Trap(S); 2134218893Sdim 2135207619Srdivacky Sema::ContextRAII SavedContext(S, Partial); 2136194179Sed 2137194179Sed // C++ [temp.deduct.type]p2: 2138194179Sed // [...] or if any template argument remains neither deduced nor 2139194179Sed // explicitly specified, template argument deduction fails. 2140226890Sdim SmallVector<TemplateArgument, 4> Builder; 2141218893Sdim TemplateParameterList *PartialParams = Partial->getTemplateParameters(); 2142218893Sdim for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) { 2143218893Sdim NamedDecl *Param = PartialParams->getParam(I); 2144194179Sed if (Deduced[I].isNull()) { 2145206084Srdivacky Info.Param = makeTemplateParameter(Param); 2146207619Srdivacky return Sema::TDK_Incomplete; 2147194179Sed } 2148218893Sdim 2149218893Sdim // We have deduced this argument, so it still needs to be 2150218893Sdim // checked and converted. 2151218893Sdim 2152218893Sdim // First, for a non-type template parameter type that is 2153218893Sdim // initialized by a declaration, we need the type of the 2154218893Sdim // corresponding non-type template parameter. 2155218893Sdim QualType NTTPType; 2156218893Sdim if (NonTypeTemplateParmDecl *NTTP 2157218893Sdim = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 2158218893Sdim NTTPType = NTTP->getType(); 2159218893Sdim if (NTTPType->isDependentType()) { 2160218893Sdim TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, 2161218893Sdim Builder.data(), Builder.size()); 2162218893Sdim NTTPType = S.SubstType(NTTPType, 2163218893Sdim MultiLevelTemplateArgumentList(TemplateArgs), 2164218893Sdim NTTP->getLocation(), 2165218893Sdim NTTP->getDeclName()); 2166218893Sdim if (NTTPType.isNull()) { 2167218893Sdim Info.Param = makeTemplateParameter(Param); 2168218893Sdim // FIXME: These template arguments are temporary. Free them! 2169218893Sdim Info.reset(TemplateArgumentList::CreateCopy(S.Context, 2170218893Sdim Builder.data(), 2171218893Sdim Builder.size())); 2172218893Sdim return Sema::TDK_SubstitutionFailure; 2173218893Sdim } 2174218893Sdim } 2175218893Sdim } 2176218893Sdim 2177218893Sdim if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], 2178218893Sdim Partial, NTTPType, 0, Info, false, 2179218893Sdim Builder)) { 2180218893Sdim Info.Param = makeTemplateParameter(Param); 2181218893Sdim // FIXME: These template arguments are temporary. Free them! 2182218893Sdim Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(), 2183218893Sdim Builder.size())); 2184218893Sdim return Sema::TDK_SubstitutionFailure; 2185218893Sdim } 2186194179Sed } 2187218893Sdim 2188194179Sed // Form the template argument list from the deduced template arguments. 2189198092Srdivacky TemplateArgumentList *DeducedArgumentList 2190218893Sdim = TemplateArgumentList::CreateCopy(S.Context, Builder.data(), 2191218893Sdim Builder.size()); 2192218893Sdim 2193194179Sed Info.reset(DeducedArgumentList); 2194194179Sed 2195194179Sed // Substitute the deduced template arguments into the template 2196194179Sed // arguments of the class template partial specialization, and 2197194179Sed // verify that the instantiated template arguments are both valid 2198194179Sed // and are equivalent to the template arguments originally provided 2199198092Srdivacky // to the class template. 2200212904Sdim LocalInstantiationScope InstScope(S); 2201194179Sed ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate(); 2202263509Sdim const ASTTemplateArgumentListInfo *PartialTemplArgInfo 2203263509Sdim = Partial->getTemplateArgsAsWritten(); 2204198893Srdivacky const TemplateArgumentLoc *PartialTemplateArgs 2205263509Sdim = PartialTemplArgInfo->getTemplateArgs(); 2206199990Srdivacky 2207263509Sdim TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc, 2208263509Sdim PartialTemplArgInfo->RAngleLoc); 2209199990Srdivacky 2210263509Sdim if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs, 2211218893Sdim InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) { 2212218893Sdim unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx; 2213218893Sdim if (ParamIdx >= Partial->getTemplateParameters()->size()) 2214218893Sdim ParamIdx = Partial->getTemplateParameters()->size() - 1; 2215218893Sdim 2216218893Sdim Decl *Param 2217218893Sdim = const_cast<NamedDecl *>( 2218218893Sdim Partial->getTemplateParameters()->getParam(ParamIdx)); 2219218893Sdim Info.Param = makeTemplateParameter(Param); 2220218893Sdim Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument(); 2221218893Sdim return Sema::TDK_SubstitutionFailure; 2222198893Srdivacky } 2223198092Srdivacky 2224226890Sdim SmallVector<TemplateArgument, 4> ConvertedInstArgs; 2225207619Srdivacky if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(), 2226218893Sdim InstArgs, false, ConvertedInstArgs)) 2227207619Srdivacky return Sema::TDK_SubstitutionFailure; 2228198893Srdivacky 2229218893Sdim TemplateParameterList *TemplateParams 2230218893Sdim = ClassTemplate->getTemplateParameters(); 2231218893Sdim for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) { 2232218893Sdim TemplateArgument InstArg = ConvertedInstArgs.data()[I]; 2233207619Srdivacky if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) { 2234218893Sdim Info.Param = makeTemplateParameter(TemplateParams->getParam(I)); 2235195099Sed Info.FirstArg = TemplateArgs[I]; 2236195099Sed Info.SecondArg = InstArg; 2237207619Srdivacky return Sema::TDK_NonDeducedMismatch; 2238195099Sed } 2239195099Sed } 2240194179Sed 2241195099Sed if (Trap.hasErrorOccurred()) 2242207619Srdivacky return Sema::TDK_SubstitutionFailure; 2243195099Sed 2244207619Srdivacky return Sema::TDK_Success; 2245195099Sed} 2246195099Sed 2247207619Srdivacky/// \brief Perform template argument deduction to determine whether 2248207619Srdivacky/// the given template arguments match the given class template 2249207619Srdivacky/// partial specialization per C++ [temp.class.spec.match]. 2250207619SrdivackySema::TemplateDeductionResult 2251207619SrdivackySema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial, 2252207619Srdivacky const TemplateArgumentList &TemplateArgs, 2253207619Srdivacky TemplateDeductionInfo &Info) { 2254245431Sdim if (Partial->isInvalidDecl()) 2255245431Sdim return TDK_Invalid; 2256245431Sdim 2257207619Srdivacky // C++ [temp.class.spec.match]p2: 2258207619Srdivacky // A partial specialization matches a given actual template 2259207619Srdivacky // argument list if the template arguments of the partial 2260207619Srdivacky // specialization can be deduced from the actual template argument 2261207619Srdivacky // list (14.8.2). 2262235633Sdim 2263235633Sdim // Unevaluated SFINAE context. 2264235633Sdim EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 2265207619Srdivacky SFINAETrap Trap(*this); 2266235633Sdim 2267226890Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 2268207619Srdivacky Deduced.resize(Partial->getTemplateParameters()->size()); 2269207619Srdivacky if (TemplateDeductionResult Result 2270207619Srdivacky = ::DeduceTemplateArguments(*this, 2271207619Srdivacky Partial->getTemplateParameters(), 2272207619Srdivacky Partial->getTemplateArgs(), 2273207619Srdivacky TemplateArgs, Info, Deduced)) 2274207619Srdivacky return Result; 2275207619Srdivacky 2276245431Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end()); 2277207619Srdivacky InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial, 2278245431Sdim DeducedArgs, Info); 2279263509Sdim if (Inst.isInvalid()) 2280207619Srdivacky return TDK_InstantiationDepth; 2281207619Srdivacky 2282207619Srdivacky if (Trap.hasErrorOccurred()) 2283207619Srdivacky return Sema::TDK_SubstitutionFailure; 2284218893Sdim 2285218893Sdim return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs, 2286207619Srdivacky Deduced, Info); 2287207619Srdivacky} 2288207619Srdivacky 2289263509Sdim/// Complete template argument deduction for a variable template partial 2290263509Sdim/// specialization. 2291263509Sdim/// TODO: Unify with ClassTemplatePartialSpecializationDecl version? 2292263509Sdim/// May require unifying ClassTemplate(Partial)SpecializationDecl and 2293263509Sdim/// VarTemplate(Partial)SpecializationDecl with a new data 2294263509Sdim/// structure Template(Partial)SpecializationDecl, and 2295263509Sdim/// using Template(Partial)SpecializationDecl as input type. 2296263509Sdimstatic Sema::TemplateDeductionResult FinishTemplateArgumentDeduction( 2297263509Sdim Sema &S, VarTemplatePartialSpecializationDecl *Partial, 2298263509Sdim const TemplateArgumentList &TemplateArgs, 2299263509Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2300263509Sdim TemplateDeductionInfo &Info) { 2301263509Sdim // Unevaluated SFINAE context. 2302263509Sdim EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated); 2303263509Sdim Sema::SFINAETrap Trap(S); 2304263509Sdim 2305263509Sdim // C++ [temp.deduct.type]p2: 2306263509Sdim // [...] or if any template argument remains neither deduced nor 2307263509Sdim // explicitly specified, template argument deduction fails. 2308263509Sdim SmallVector<TemplateArgument, 4> Builder; 2309263509Sdim TemplateParameterList *PartialParams = Partial->getTemplateParameters(); 2310263509Sdim for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) { 2311263509Sdim NamedDecl *Param = PartialParams->getParam(I); 2312263509Sdim if (Deduced[I].isNull()) { 2313263509Sdim Info.Param = makeTemplateParameter(Param); 2314263509Sdim return Sema::TDK_Incomplete; 2315263509Sdim } 2316263509Sdim 2317263509Sdim // We have deduced this argument, so it still needs to be 2318263509Sdim // checked and converted. 2319263509Sdim 2320263509Sdim // First, for a non-type template parameter type that is 2321263509Sdim // initialized by a declaration, we need the type of the 2322263509Sdim // corresponding non-type template parameter. 2323263509Sdim QualType NTTPType; 2324263509Sdim if (NonTypeTemplateParmDecl *NTTP = 2325263509Sdim dyn_cast<NonTypeTemplateParmDecl>(Param)) { 2326263509Sdim NTTPType = NTTP->getType(); 2327263509Sdim if (NTTPType->isDependentType()) { 2328263509Sdim TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, 2329263509Sdim Builder.data(), Builder.size()); 2330263509Sdim NTTPType = 2331263509Sdim S.SubstType(NTTPType, MultiLevelTemplateArgumentList(TemplateArgs), 2332263509Sdim NTTP->getLocation(), NTTP->getDeclName()); 2333263509Sdim if (NTTPType.isNull()) { 2334263509Sdim Info.Param = makeTemplateParameter(Param); 2335263509Sdim // FIXME: These template arguments are temporary. Free them! 2336263509Sdim Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(), 2337263509Sdim Builder.size())); 2338263509Sdim return Sema::TDK_SubstitutionFailure; 2339263509Sdim } 2340263509Sdim } 2341263509Sdim } 2342263509Sdim 2343263509Sdim if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Partial, NTTPType, 2344263509Sdim 0, Info, false, Builder)) { 2345263509Sdim Info.Param = makeTemplateParameter(Param); 2346263509Sdim // FIXME: These template arguments are temporary. Free them! 2347263509Sdim Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(), 2348263509Sdim Builder.size())); 2349263509Sdim return Sema::TDK_SubstitutionFailure; 2350263509Sdim } 2351263509Sdim } 2352263509Sdim 2353263509Sdim // Form the template argument list from the deduced template arguments. 2354263509Sdim TemplateArgumentList *DeducedArgumentList = TemplateArgumentList::CreateCopy( 2355263509Sdim S.Context, Builder.data(), Builder.size()); 2356263509Sdim 2357263509Sdim Info.reset(DeducedArgumentList); 2358263509Sdim 2359263509Sdim // Substitute the deduced template arguments into the template 2360263509Sdim // arguments of the class template partial specialization, and 2361263509Sdim // verify that the instantiated template arguments are both valid 2362263509Sdim // and are equivalent to the template arguments originally provided 2363263509Sdim // to the class template. 2364263509Sdim LocalInstantiationScope InstScope(S); 2365263509Sdim VarTemplateDecl *VarTemplate = Partial->getSpecializedTemplate(); 2366263509Sdim const ASTTemplateArgumentListInfo *PartialTemplArgInfo 2367263509Sdim = Partial->getTemplateArgsAsWritten(); 2368263509Sdim const TemplateArgumentLoc *PartialTemplateArgs 2369263509Sdim = PartialTemplArgInfo->getTemplateArgs(); 2370263509Sdim 2371263509Sdim TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc, 2372263509Sdim PartialTemplArgInfo->RAngleLoc); 2373263509Sdim 2374263509Sdim if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs, 2375263509Sdim InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) { 2376263509Sdim unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx; 2377263509Sdim if (ParamIdx >= Partial->getTemplateParameters()->size()) 2378263509Sdim ParamIdx = Partial->getTemplateParameters()->size() - 1; 2379263509Sdim 2380263509Sdim Decl *Param = const_cast<NamedDecl *>( 2381263509Sdim Partial->getTemplateParameters()->getParam(ParamIdx)); 2382263509Sdim Info.Param = makeTemplateParameter(Param); 2383263509Sdim Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument(); 2384263509Sdim return Sema::TDK_SubstitutionFailure; 2385263509Sdim } 2386263509Sdim SmallVector<TemplateArgument, 4> ConvertedInstArgs; 2387263509Sdim if (S.CheckTemplateArgumentList(VarTemplate, Partial->getLocation(), InstArgs, 2388263509Sdim false, ConvertedInstArgs)) 2389263509Sdim return Sema::TDK_SubstitutionFailure; 2390263509Sdim 2391263509Sdim TemplateParameterList *TemplateParams = VarTemplate->getTemplateParameters(); 2392263509Sdim for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) { 2393263509Sdim TemplateArgument InstArg = ConvertedInstArgs.data()[I]; 2394263509Sdim if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) { 2395263509Sdim Info.Param = makeTemplateParameter(TemplateParams->getParam(I)); 2396263509Sdim Info.FirstArg = TemplateArgs[I]; 2397263509Sdim Info.SecondArg = InstArg; 2398263509Sdim return Sema::TDK_NonDeducedMismatch; 2399263509Sdim } 2400263509Sdim } 2401263509Sdim 2402263509Sdim if (Trap.hasErrorOccurred()) 2403263509Sdim return Sema::TDK_SubstitutionFailure; 2404263509Sdim 2405263509Sdim return Sema::TDK_Success; 2406263509Sdim} 2407263509Sdim 2408263509Sdim/// \brief Perform template argument deduction to determine whether 2409263509Sdim/// the given template arguments match the given variable template 2410263509Sdim/// partial specialization per C++ [temp.class.spec.match]. 2411263509Sdim/// TODO: Unify with ClassTemplatePartialSpecializationDecl version? 2412263509Sdim/// May require unifying ClassTemplate(Partial)SpecializationDecl and 2413263509Sdim/// VarTemplate(Partial)SpecializationDecl with a new data 2414263509Sdim/// structure Template(Partial)SpecializationDecl, and 2415263509Sdim/// using Template(Partial)SpecializationDecl as input type. 2416263509SdimSema::TemplateDeductionResult 2417263509SdimSema::DeduceTemplateArguments(VarTemplatePartialSpecializationDecl *Partial, 2418263509Sdim const TemplateArgumentList &TemplateArgs, 2419263509Sdim TemplateDeductionInfo &Info) { 2420263509Sdim if (Partial->isInvalidDecl()) 2421263509Sdim return TDK_Invalid; 2422263509Sdim 2423263509Sdim // C++ [temp.class.spec.match]p2: 2424263509Sdim // A partial specialization matches a given actual template 2425263509Sdim // argument list if the template arguments of the partial 2426263509Sdim // specialization can be deduced from the actual template argument 2427263509Sdim // list (14.8.2). 2428263509Sdim 2429263509Sdim // Unevaluated SFINAE context. 2430263509Sdim EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 2431263509Sdim SFINAETrap Trap(*this); 2432263509Sdim 2433263509Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 2434263509Sdim Deduced.resize(Partial->getTemplateParameters()->size()); 2435263509Sdim if (TemplateDeductionResult Result = ::DeduceTemplateArguments( 2436263509Sdim *this, Partial->getTemplateParameters(), Partial->getTemplateArgs(), 2437263509Sdim TemplateArgs, Info, Deduced)) 2438263509Sdim return Result; 2439263509Sdim 2440263509Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end()); 2441263509Sdim InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial, 2442263509Sdim DeducedArgs, Info); 2443263509Sdim if (Inst.isInvalid()) 2444263509Sdim return TDK_InstantiationDepth; 2445263509Sdim 2446263509Sdim if (Trap.hasErrorOccurred()) 2447263509Sdim return Sema::TDK_SubstitutionFailure; 2448263509Sdim 2449263509Sdim return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs, 2450263509Sdim Deduced, Info); 2451263509Sdim} 2452263509Sdim 2453195099Sed/// \brief Determine whether the given type T is a simple-template-id type. 2454195099Sedstatic bool isSimpleTemplateIdType(QualType T) { 2455198092Srdivacky if (const TemplateSpecializationType *Spec 2456198092Srdivacky = T->getAs<TemplateSpecializationType>()) 2457195099Sed return Spec->getTemplateName().getAsTemplateDecl() != 0; 2458198092Srdivacky 2459195099Sed return false; 2460195099Sed} 2461198092Srdivacky 2462198092Srdivacky/// \brief Substitute the explicitly-provided template arguments into the 2463198092Srdivacky/// given function template according to C++ [temp.arg.explicit]. 2464198092Srdivacky/// 2465198092Srdivacky/// \param FunctionTemplate the function template into which the explicit 2466198092Srdivacky/// template arguments will be substituted. 2467198092Srdivacky/// 2468245431Sdim/// \param ExplicitTemplateArgs the explicitly-specified template 2469198092Srdivacky/// arguments. 2470198092Srdivacky/// 2471198092Srdivacky/// \param Deduced the deduced template arguments, which will be populated 2472198092Srdivacky/// with the converted and checked explicit template arguments. 2473198092Srdivacky/// 2474198092Srdivacky/// \param ParamTypes will be populated with the instantiated function 2475198092Srdivacky/// parameters. 2476198092Srdivacky/// 2477198092Srdivacky/// \param FunctionType if non-NULL, the result type of the function template 2478198092Srdivacky/// will also be instantiated and the pointed-to value will be updated with 2479198092Srdivacky/// the instantiated function type. 2480198092Srdivacky/// 2481198092Srdivacky/// \param Info if substitution fails for any reason, this object will be 2482198092Srdivacky/// populated with more information about the failure. 2483198092Srdivacky/// 2484198092Srdivacky/// \returns TDK_Success if substitution was successful, or some failure 2485198092Srdivacky/// condition. 2486198092SrdivackySema::TemplateDeductionResult 2487198092SrdivackySema::SubstituteExplicitTemplateArguments( 2488198092Srdivacky FunctionTemplateDecl *FunctionTemplate, 2489221345Sdim TemplateArgumentListInfo &ExplicitTemplateArgs, 2490226890Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2491226890Sdim SmallVectorImpl<QualType> &ParamTypes, 2492198092Srdivacky QualType *FunctionType, 2493198092Srdivacky TemplateDeductionInfo &Info) { 2494198092Srdivacky FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2495198092Srdivacky TemplateParameterList *TemplateParams 2496198092Srdivacky = FunctionTemplate->getTemplateParameters(); 2497198092Srdivacky 2498199990Srdivacky if (ExplicitTemplateArgs.size() == 0) { 2499198092Srdivacky // No arguments to substitute; just copy over the parameter types and 2500198092Srdivacky // fill in the function type. 2501198092Srdivacky for (FunctionDecl::param_iterator P = Function->param_begin(), 2502198092Srdivacky PEnd = Function->param_end(); 2503198092Srdivacky P != PEnd; 2504198092Srdivacky ++P) 2505198092Srdivacky ParamTypes.push_back((*P)->getType()); 2506198092Srdivacky 2507198092Srdivacky if (FunctionType) 2508198092Srdivacky *FunctionType = Function->getType(); 2509198092Srdivacky return TDK_Success; 2510198092Srdivacky } 2511198092Srdivacky 2512235633Sdim // Unevaluated SFINAE context. 2513235633Sdim EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 2514198092Srdivacky SFINAETrap Trap(*this); 2515198092Srdivacky 2516198092Srdivacky // C++ [temp.arg.explicit]p3: 2517198092Srdivacky // Template arguments that are present shall be specified in the 2518198092Srdivacky // declaration order of their corresponding template-parameters. The 2519198092Srdivacky // template argument list shall not specify more template-arguments than 2520198092Srdivacky // there are corresponding template-parameters. 2521226890Sdim SmallVector<TemplateArgument, 4> Builder; 2522198092Srdivacky 2523198092Srdivacky // Enter a new template instantiation context where we check the 2524198092Srdivacky // explicitly-specified template arguments against this function template, 2525198092Srdivacky // and then substitute them into the function parameter types. 2526245431Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end()); 2527198092Srdivacky InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 2528245431Sdim FunctionTemplate, DeducedArgs, 2529218893Sdim ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution, 2530218893Sdim Info); 2531263509Sdim if (Inst.isInvalid()) 2532198092Srdivacky return TDK_InstantiationDepth; 2533198092Srdivacky 2534198092Srdivacky if (CheckTemplateArgumentList(FunctionTemplate, 2535199990Srdivacky SourceLocation(), 2536198092Srdivacky ExplicitTemplateArgs, 2537198092Srdivacky true, 2538208600Srdivacky Builder) || Trap.hasErrorOccurred()) { 2539218893Sdim unsigned Index = Builder.size(); 2540208600Srdivacky if (Index >= TemplateParams->size()) 2541208600Srdivacky Index = TemplateParams->size() - 1; 2542208600Srdivacky Info.Param = makeTemplateParameter(TemplateParams->getParam(Index)); 2543198092Srdivacky return TDK_InvalidExplicitArguments; 2544208600Srdivacky } 2545198092Srdivacky 2546198092Srdivacky // Form the template argument list from the explicitly-specified 2547198092Srdivacky // template arguments. 2548198092Srdivacky TemplateArgumentList *ExplicitArgumentList 2549218893Sdim = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size()); 2550198092Srdivacky Info.reset(ExplicitArgumentList); 2551198092Srdivacky 2552218893Sdim // Template argument deduction and the final substitution should be 2553218893Sdim // done in the context of the templated declaration. Explicit 2554218893Sdim // argument substitution, on the other hand, needs to happen in the 2555218893Sdim // calling context. 2556218893Sdim ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 2557218893Sdim 2558218893Sdim // If we deduced template arguments for a template parameter pack, 2559218893Sdim // note that the template argument pack is partially substituted and record 2560218893Sdim // the explicit template arguments. They'll be used as part of deduction 2561218893Sdim // for this template parameter pack. 2562218893Sdim for (unsigned I = 0, N = Builder.size(); I != N; ++I) { 2563218893Sdim const TemplateArgument &Arg = Builder[I]; 2564218893Sdim if (Arg.getKind() == TemplateArgument::Pack) { 2565218893Sdim CurrentInstantiationScope->SetPartiallySubstitutedPack( 2566218893Sdim TemplateParams->getParam(I), 2567218893Sdim Arg.pack_begin(), 2568218893Sdim Arg.pack_size()); 2569218893Sdim break; 2570218893Sdim } 2571218893Sdim } 2572218893Sdim 2573235633Sdim const FunctionProtoType *Proto 2574235633Sdim = Function->getType()->getAs<FunctionProtoType>(); 2575235633Sdim assert(Proto && "Function template does not have a prototype?"); 2576235633Sdim 2577198092Srdivacky // Instantiate the types of each of the function parameters given the 2578235633Sdim // explicitly-specified template arguments. If the function has a trailing 2579235633Sdim // return type, substitute it after the arguments to ensure we substitute 2580235633Sdim // in lexical order. 2581235633Sdim if (Proto->hasTrailingReturn()) { 2582235633Sdim if (SubstParmTypes(Function->getLocation(), 2583235633Sdim Function->param_begin(), Function->getNumParams(), 2584235633Sdim MultiLevelTemplateArgumentList(*ExplicitArgumentList), 2585235633Sdim ParamTypes)) 2586235633Sdim return TDK_SubstitutionFailure; 2587235633Sdim } 2588235633Sdim 2589235633Sdim // Instantiate the return type. 2590235633Sdim QualType ResultType; 2591235633Sdim { 2592235633Sdim // C++11 [expr.prim.general]p3: 2593235633Sdim // If a declaration declares a member function or member function 2594235633Sdim // template of a class X, the expression this is a prvalue of type 2595235633Sdim // "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq 2596235633Sdim // and the end of the function-definition, member-declarator, or 2597235633Sdim // declarator. 2598235633Sdim unsigned ThisTypeQuals = 0; 2599235633Sdim CXXRecordDecl *ThisContext = 0; 2600235633Sdim if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) { 2601235633Sdim ThisContext = Method->getParent(); 2602235633Sdim ThisTypeQuals = Method->getTypeQualifiers(); 2603235633Sdim } 2604235633Sdim 2605235633Sdim CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals, 2606252723Sdim getLangOpts().CPlusPlus11); 2607235633Sdim 2608235633Sdim ResultType = SubstType(Proto->getResultType(), 2609235633Sdim MultiLevelTemplateArgumentList(*ExplicitArgumentList), 2610235633Sdim Function->getTypeSpecStartLoc(), 2611235633Sdim Function->getDeclName()); 2612235633Sdim if (ResultType.isNull() || Trap.hasErrorOccurred()) 2613235633Sdim return TDK_SubstitutionFailure; 2614235633Sdim } 2615235633Sdim 2616235633Sdim // Instantiate the types of each of the function parameters given the 2617235633Sdim // explicitly-specified template arguments if we didn't do so earlier. 2618235633Sdim if (!Proto->hasTrailingReturn() && 2619235633Sdim SubstParmTypes(Function->getLocation(), 2620218893Sdim Function->param_begin(), Function->getNumParams(), 2621218893Sdim MultiLevelTemplateArgumentList(*ExplicitArgumentList), 2622218893Sdim ParamTypes)) 2623218893Sdim return TDK_SubstitutionFailure; 2624198092Srdivacky 2625198092Srdivacky if (FunctionType) { 2626252723Sdim *FunctionType = BuildFunctionType(ResultType, ParamTypes, 2627198092Srdivacky Function->getLocation(), 2628212904Sdim Function->getDeclName(), 2629252723Sdim Proto->getExtProtoInfo()); 2630198092Srdivacky if (FunctionType->isNull() || Trap.hasErrorOccurred()) 2631198092Srdivacky return TDK_SubstitutionFailure; 2632198092Srdivacky } 2633198092Srdivacky 2634198092Srdivacky // C++ [temp.arg.explicit]p2: 2635198092Srdivacky // Trailing template arguments that can be deduced (14.8.2) may be 2636198092Srdivacky // omitted from the list of explicit template-arguments. If all of the 2637198092Srdivacky // template arguments can be deduced, they may all be omitted; in this 2638198092Srdivacky // case, the empty template argument list <> itself may also be omitted. 2639198092Srdivacky // 2640218893Sdim // Take all of the explicitly-specified arguments and put them into 2641218893Sdim // the set of deduced template arguments. Explicitly-specified 2642218893Sdim // parameter packs, however, will be set to NULL since the deduction 2643218893Sdim // mechanisms handle explicitly-specified argument packs directly. 2644198092Srdivacky Deduced.reserve(TemplateParams->size()); 2645218893Sdim for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) { 2646218893Sdim const TemplateArgument &Arg = ExplicitArgumentList->get(I); 2647218893Sdim if (Arg.getKind() == TemplateArgument::Pack) 2648218893Sdim Deduced.push_back(DeducedTemplateArgument()); 2649218893Sdim else 2650218893Sdim Deduced.push_back(Arg); 2651218893Sdim } 2652198092Srdivacky 2653198092Srdivacky return TDK_Success; 2654198092Srdivacky} 2655198092Srdivacky 2656224145Sdim/// \brief Check whether the deduced argument type for a call to a function 2657224145Sdim/// template matches the actual argument type per C++ [temp.deduct.call]p4. 2658224145Sdimstatic bool 2659224145SdimCheckOriginalCallArgDeduction(Sema &S, Sema::OriginalCallArg OriginalArg, 2660224145Sdim QualType DeducedA) { 2661224145Sdim ASTContext &Context = S.Context; 2662224145Sdim 2663224145Sdim QualType A = OriginalArg.OriginalArgType; 2664224145Sdim QualType OriginalParamType = OriginalArg.OriginalParamType; 2665224145Sdim 2666224145Sdim // Check for type equality (top-level cv-qualifiers are ignored). 2667224145Sdim if (Context.hasSameUnqualifiedType(A, DeducedA)) 2668224145Sdim return false; 2669224145Sdim 2670224145Sdim // Strip off references on the argument types; they aren't needed for 2671224145Sdim // the following checks. 2672224145Sdim if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>()) 2673224145Sdim DeducedA = DeducedARef->getPointeeType(); 2674224145Sdim if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 2675224145Sdim A = ARef->getPointeeType(); 2676224145Sdim 2677224145Sdim // C++ [temp.deduct.call]p4: 2678224145Sdim // [...] However, there are three cases that allow a difference: 2679224145Sdim // - If the original P is a reference type, the deduced A (i.e., the 2680224145Sdim // type referred to by the reference) can be more cv-qualified than 2681224145Sdim // the transformed A. 2682224145Sdim if (const ReferenceType *OriginalParamRef 2683224145Sdim = OriginalParamType->getAs<ReferenceType>()) { 2684224145Sdim // We don't want to keep the reference around any more. 2685224145Sdim OriginalParamType = OriginalParamRef->getPointeeType(); 2686224145Sdim 2687224145Sdim Qualifiers AQuals = A.getQualifiers(); 2688224145Sdim Qualifiers DeducedAQuals = DeducedA.getQualifiers(); 2689245431Sdim 2690263509Sdim // Under Objective-C++ ARC, the deduced type may have implicitly 2691263509Sdim // been given strong or (when dealing with a const reference) 2692263509Sdim // unsafe_unretained lifetime. If so, update the original 2693263509Sdim // qualifiers to include this lifetime. 2694245431Sdim if (S.getLangOpts().ObjCAutoRefCount && 2695263509Sdim ((DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong && 2696263509Sdim AQuals.getObjCLifetime() == Qualifiers::OCL_None) || 2697263509Sdim (DeducedAQuals.hasConst() && 2698263509Sdim DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone))) { 2699263509Sdim AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime()); 2700245431Sdim } 2701245431Sdim 2702224145Sdim if (AQuals == DeducedAQuals) { 2703224145Sdim // Qualifiers match; there's nothing to do. 2704224145Sdim } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) { 2705224145Sdim return true; 2706224145Sdim } else { 2707224145Sdim // Qualifiers are compatible, so have the argument type adopt the 2708224145Sdim // deduced argument type's qualifiers as if we had performed the 2709224145Sdim // qualification conversion. 2710224145Sdim A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals); 2711224145Sdim } 2712224145Sdim } 2713224145Sdim 2714224145Sdim // - The transformed A can be another pointer or pointer to member 2715224145Sdim // type that can be converted to the deduced A via a qualification 2716224145Sdim // conversion. 2717224145Sdim // 2718224145Sdim // Also allow conversions which merely strip [[noreturn]] from function types 2719224145Sdim // (recursively) as an extension. 2720263509Sdim // FIXME: Currently, this doesn't play nicely with qualification conversions. 2721224145Sdim bool ObjCLifetimeConversion = false; 2722224145Sdim QualType ResultTy; 2723224145Sdim if ((A->isAnyPointerType() || A->isMemberPointerType()) && 2724224145Sdim (S.IsQualificationConversion(A, DeducedA, false, 2725224145Sdim ObjCLifetimeConversion) || 2726224145Sdim S.IsNoReturnConversion(A, DeducedA, ResultTy))) 2727224145Sdim return false; 2728224145Sdim 2729224145Sdim 2730224145Sdim // - If P is a class and P has the form simple-template-id, then the 2731224145Sdim // transformed A can be a derived class of the deduced A. [...] 2732224145Sdim // [...] Likewise, if P is a pointer to a class of the form 2733224145Sdim // simple-template-id, the transformed A can be a pointer to a 2734224145Sdim // derived class pointed to by the deduced A. 2735224145Sdim if (const PointerType *OriginalParamPtr 2736224145Sdim = OriginalParamType->getAs<PointerType>()) { 2737224145Sdim if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) { 2738224145Sdim if (const PointerType *APtr = A->getAs<PointerType>()) { 2739224145Sdim if (A->getPointeeType()->isRecordType()) { 2740224145Sdim OriginalParamType = OriginalParamPtr->getPointeeType(); 2741224145Sdim DeducedA = DeducedAPtr->getPointeeType(); 2742224145Sdim A = APtr->getPointeeType(); 2743224145Sdim } 2744224145Sdim } 2745224145Sdim } 2746224145Sdim } 2747224145Sdim 2748224145Sdim if (Context.hasSameUnqualifiedType(A, DeducedA)) 2749224145Sdim return false; 2750224145Sdim 2751224145Sdim if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) && 2752224145Sdim S.IsDerivedFrom(A, DeducedA)) 2753224145Sdim return false; 2754224145Sdim 2755224145Sdim return true; 2756224145Sdim} 2757224145Sdim 2758198092Srdivacky/// \brief Finish template argument deduction for a function template, 2759198092Srdivacky/// checking the deduced template arguments for completeness and forming 2760198092Srdivacky/// the function template specialization. 2761224145Sdim/// 2762224145Sdim/// \param OriginalCallArgs If non-NULL, the original call arguments against 2763224145Sdim/// which the deduced argument types should be compared. 2764198092SrdivackySema::TemplateDeductionResult 2765198092SrdivackySema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate, 2766226890Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2767206084Srdivacky unsigned NumExplicitlySpecified, 2768198092Srdivacky FunctionDecl *&Specialization, 2769224145Sdim TemplateDeductionInfo &Info, 2770226890Sdim SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs) { 2771198092Srdivacky TemplateParameterList *TemplateParams 2772198092Srdivacky = FunctionTemplate->getTemplateParameters(); 2773198092Srdivacky 2774235633Sdim // Unevaluated SFINAE context. 2775235633Sdim EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 2776199990Srdivacky SFINAETrap Trap(*this); 2777199990Srdivacky 2778199990Srdivacky // Enter a new template instantiation context while we instantiate the 2779199990Srdivacky // actual function declaration. 2780245431Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end()); 2781199990Srdivacky InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 2782245431Sdim FunctionTemplate, DeducedArgs, 2783218893Sdim ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution, 2784218893Sdim Info); 2785263509Sdim if (Inst.isInvalid()) 2786199990Srdivacky return TDK_InstantiationDepth; 2787199990Srdivacky 2788207619Srdivacky ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 2789207619Srdivacky 2790198092Srdivacky // C++ [temp.deduct.type]p2: 2791198092Srdivacky // [...] or if any template argument remains neither deduced nor 2792198092Srdivacky // explicitly specified, template argument deduction fails. 2793226890Sdim SmallVector<TemplateArgument, 4> Builder; 2794218893Sdim for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) { 2795218893Sdim NamedDecl *Param = TemplateParams->getParam(I); 2796218893Sdim 2797199990Srdivacky if (!Deduced[I].isNull()) { 2798218893Sdim if (I < NumExplicitlySpecified) { 2799206084Srdivacky // We have already fully type-checked and converted this 2800218893Sdim // argument, because it was explicitly-specified. Just record the 2801218893Sdim // presence of this argument. 2802218893Sdim Builder.push_back(Deduced[I]); 2803206084Srdivacky continue; 2804206084Srdivacky } 2805206084Srdivacky 2806206084Srdivacky // We have deduced this argument, so it still needs to be 2807206084Srdivacky // checked and converted. 2808206084Srdivacky 2809206084Srdivacky // First, for a non-type template parameter type that is 2810206084Srdivacky // initialized by a declaration, we need the type of the 2811206084Srdivacky // corresponding non-type template parameter. 2812206084Srdivacky QualType NTTPType; 2813218893Sdim if (NonTypeTemplateParmDecl *NTTP 2814218893Sdim = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 2815218893Sdim NTTPType = NTTP->getType(); 2816218893Sdim if (NTTPType->isDependentType()) { 2817218893Sdim TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, 2818218893Sdim Builder.data(), Builder.size()); 2819218893Sdim NTTPType = SubstType(NTTPType, 2820218893Sdim MultiLevelTemplateArgumentList(TemplateArgs), 2821218893Sdim NTTP->getLocation(), 2822218893Sdim NTTP->getDeclName()); 2823218893Sdim if (NTTPType.isNull()) { 2824218893Sdim Info.Param = makeTemplateParameter(Param); 2825218893Sdim // FIXME: These template arguments are temporary. Free them! 2826218893Sdim Info.reset(TemplateArgumentList::CreateCopy(Context, 2827218893Sdim Builder.data(), 2828218893Sdim Builder.size())); 2829218893Sdim return TDK_SubstitutionFailure; 2830206084Srdivacky } 2831206084Srdivacky } 2832206084Srdivacky } 2833206084Srdivacky 2834218893Sdim if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I], 2835218893Sdim FunctionTemplate, NTTPType, 0, Info, 2836218893Sdim true, Builder)) { 2837218893Sdim Info.Param = makeTemplateParameter(Param); 2838218893Sdim // FIXME: These template arguments are temporary. Free them! 2839218893Sdim Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 2840218893Sdim Builder.size())); 2841206084Srdivacky return TDK_SubstitutionFailure; 2842206084Srdivacky } 2843206084Srdivacky 2844199990Srdivacky continue; 2845199990Srdivacky } 2846199990Srdivacky 2847218893Sdim // C++0x [temp.arg.explicit]p3: 2848218893Sdim // A trailing template parameter pack (14.5.3) not otherwise deduced will 2849218893Sdim // be deduced to an empty sequence of template arguments. 2850218893Sdim // FIXME: Where did the word "trailing" come from? 2851218893Sdim if (Param->isTemplateParameterPack()) { 2852218893Sdim // We may have had explicitly-specified template arguments for this 2853218893Sdim // template parameter pack. If so, our empty deduction extends the 2854218893Sdim // explicitly-specified set (C++0x [temp.arg.explicit]p9). 2855218893Sdim const TemplateArgument *ExplicitArgs; 2856218893Sdim unsigned NumExplicitArgs; 2857245431Sdim if (CurrentInstantiationScope && 2858245431Sdim CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs, 2859218893Sdim &NumExplicitArgs) 2860252723Sdim == Param) { 2861218893Sdim Builder.push_back(TemplateArgument(ExplicitArgs, NumExplicitArgs)); 2862252723Sdim 2863252723Sdim // Forget the partially-substituted pack; it's substitution is now 2864252723Sdim // complete. 2865252723Sdim CurrentInstantiationScope->ResetPartiallySubstitutedPack(); 2866252723Sdim } else { 2867245431Sdim Builder.push_back(TemplateArgument::getEmptyPack()); 2868252723Sdim } 2869218893Sdim continue; 2870218893Sdim } 2871218893Sdim 2872218893Sdim // Substitute into the default template argument, if available. 2873263509Sdim bool HasDefaultArg = false; 2874199990Srdivacky TemplateArgumentLoc DefArg 2875199990Srdivacky = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate, 2876199990Srdivacky FunctionTemplate->getLocation(), 2877199990Srdivacky FunctionTemplate->getSourceRange().getEnd(), 2878199990Srdivacky Param, 2879263509Sdim Builder, HasDefaultArg); 2880199990Srdivacky 2881199990Srdivacky // If there was no default argument, deduction is incomplete. 2882199990Srdivacky if (DefArg.getArgument().isNull()) { 2883198092Srdivacky Info.Param = makeTemplateParameter( 2884199990Srdivacky const_cast<NamedDecl *>(TemplateParams->getParam(I))); 2885263509Sdim Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 2886263509Sdim Builder.size())); 2887263509Sdim return HasDefaultArg ? TDK_SubstitutionFailure : TDK_Incomplete; 2888198092Srdivacky } 2889218893Sdim 2890199990Srdivacky // Check whether we can actually use the default argument. 2891199990Srdivacky if (CheckTemplateArgument(Param, DefArg, 2892199990Srdivacky FunctionTemplate, 2893199990Srdivacky FunctionTemplate->getLocation(), 2894199990Srdivacky FunctionTemplate->getSourceRange().getEnd(), 2895218893Sdim 0, Builder, 2896223017Sdim CTAK_Specified)) { 2897199990Srdivacky Info.Param = makeTemplateParameter( 2898199990Srdivacky const_cast<NamedDecl *>(TemplateParams->getParam(I))); 2899218893Sdim // FIXME: These template arguments are temporary. Free them! 2900218893Sdim Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 2901218893Sdim Builder.size())); 2902199990Srdivacky return TDK_SubstitutionFailure; 2903199990Srdivacky } 2904198092Srdivacky 2905199990Srdivacky // If we get here, we successfully used the default template argument. 2906198092Srdivacky } 2907198092Srdivacky 2908198092Srdivacky // Form the template argument list from the deduced template arguments. 2909198092Srdivacky TemplateArgumentList *DeducedArgumentList 2910218893Sdim = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size()); 2911198092Srdivacky Info.reset(DeducedArgumentList); 2912198092Srdivacky 2913198092Srdivacky // Substitute the deduced template arguments into the function template 2914198092Srdivacky // declaration to produce the function template specialization. 2915207619Srdivacky DeclContext *Owner = FunctionTemplate->getDeclContext(); 2916207619Srdivacky if (FunctionTemplate->getFriendObjectKind()) 2917207619Srdivacky Owner = FunctionTemplate->getLexicalDeclContext(); 2918198092Srdivacky Specialization = cast_or_null<FunctionDecl>( 2919207619Srdivacky SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner, 2920198092Srdivacky MultiLevelTemplateArgumentList(*DeducedArgumentList))); 2921226890Sdim if (!Specialization || Specialization->isInvalidDecl()) 2922198092Srdivacky return TDK_SubstitutionFailure; 2923198092Srdivacky 2924218893Sdim assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() == 2925198092Srdivacky FunctionTemplate->getCanonicalDecl()); 2926218893Sdim 2927198092Srdivacky // If the template argument list is owned by the function template 2928198092Srdivacky // specialization, release it. 2929208600Srdivacky if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList && 2930208600Srdivacky !Trap.hasErrorOccurred()) 2931198092Srdivacky Info.take(); 2932198092Srdivacky 2933226890Sdim // There may have been an error that did not prevent us from constructing a 2934226890Sdim // declaration. Mark the declaration invalid and return with a substitution 2935226890Sdim // failure. 2936226890Sdim if (Trap.hasErrorOccurred()) { 2937226890Sdim Specialization->setInvalidDecl(true); 2938226890Sdim return TDK_SubstitutionFailure; 2939226890Sdim } 2940226890Sdim 2941224145Sdim if (OriginalCallArgs) { 2942224145Sdim // C++ [temp.deduct.call]p4: 2943224145Sdim // In general, the deduction process attempts to find template argument 2944224145Sdim // values that will make the deduced A identical to A (after the type A 2945224145Sdim // is transformed as described above). [...] 2946224145Sdim for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) { 2947224145Sdim OriginalCallArg OriginalArg = (*OriginalCallArgs)[I]; 2948224145Sdim unsigned ParamIdx = OriginalArg.ArgIdx; 2949224145Sdim 2950224145Sdim if (ParamIdx >= Specialization->getNumParams()) 2951224145Sdim continue; 2952224145Sdim 2953224145Sdim QualType DeducedA = Specialization->getParamDecl(ParamIdx)->getType(); 2954224145Sdim if (CheckOriginalCallArgDeduction(*this, OriginalArg, DeducedA)) 2955224145Sdim return Sema::TDK_SubstitutionFailure; 2956224145Sdim } 2957224145Sdim } 2958224145Sdim 2959218893Sdim // If we suppressed any diagnostics while performing template argument 2960218893Sdim // deduction, and if we haven't already instantiated this declaration, 2961218893Sdim // keep track of these diagnostics. They'll be emitted if this specialization 2962218893Sdim // is actually used. 2963218893Sdim if (Info.diag_begin() != Info.diag_end()) { 2964263509Sdim SuppressedDiagnosticsMap::iterator 2965218893Sdim Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl()); 2966218893Sdim if (Pos == SuppressedDiagnostics.end()) 2967218893Sdim SuppressedDiagnostics[Specialization->getCanonicalDecl()] 2968218893Sdim .append(Info.diag_begin(), Info.diag_end()); 2969218893Sdim } 2970218893Sdim 2971198092Srdivacky return TDK_Success; 2972198092Srdivacky} 2973198092Srdivacky 2974212904Sdim/// Gets the type of a function for template-argument-deducton 2975212904Sdim/// purposes when it's considered as part of an overload set. 2976252723Sdimstatic QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R, 2977203955Srdivacky FunctionDecl *Fn) { 2978252723Sdim // We may need to deduce the return type of the function now. 2979252723Sdim if (S.getLangOpts().CPlusPlus1y && Fn->getResultType()->isUndeducedType() && 2980252723Sdim S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/false)) 2981252723Sdim return QualType(); 2982252723Sdim 2983203955Srdivacky if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn)) 2984212904Sdim if (Method->isInstance()) { 2985212904Sdim // An instance method that's referenced in a form that doesn't 2986212904Sdim // look like a member pointer is just invalid. 2987212904Sdim if (!R.HasFormOfMemberPointer) return QualType(); 2988212904Sdim 2989252723Sdim return S.Context.getMemberPointerType(Fn->getType(), 2990252723Sdim S.Context.getTypeDeclType(Method->getParent()).getTypePtr()); 2991212904Sdim } 2992212904Sdim 2993212904Sdim if (!R.IsAddressOfOperand) return Fn->getType(); 2994252723Sdim return S.Context.getPointerType(Fn->getType()); 2995203955Srdivacky} 2996203955Srdivacky 2997203955Srdivacky/// Apply the deduction rules for overload sets. 2998203955Srdivacky/// 2999203955Srdivacky/// \return the null type if this argument should be treated as an 3000203955Srdivacky/// undeduced context 3001203955Srdivackystatic QualType 3002203955SrdivackyResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams, 3003212904Sdim Expr *Arg, QualType ParamType, 3004212904Sdim bool ParamWasReference) { 3005218893Sdim 3006212904Sdim OverloadExpr::FindResult R = OverloadExpr::find(Arg); 3007203955Srdivacky 3008212904Sdim OverloadExpr *Ovl = R.Expression; 3009203955Srdivacky 3010212904Sdim // C++0x [temp.deduct.call]p4 3011212904Sdim unsigned TDF = 0; 3012212904Sdim if (ParamWasReference) 3013212904Sdim TDF |= TDF_ParamWithReferenceType; 3014212904Sdim if (R.IsAddressOfOperand) 3015212904Sdim TDF |= TDF_IgnoreQualifiers; 3016212904Sdim 3017203955Srdivacky // C++0x [temp.deduct.call]p6: 3018203955Srdivacky // When P is a function type, pointer to function type, or pointer 3019203955Srdivacky // to member function type: 3020203955Srdivacky 3021203955Srdivacky if (!ParamType->isFunctionType() && 3022203955Srdivacky !ParamType->isFunctionPointerType() && 3023235633Sdim !ParamType->isMemberFunctionPointerType()) { 3024235633Sdim if (Ovl->hasExplicitTemplateArgs()) { 3025235633Sdim // But we can still look for an explicit specialization. 3026235633Sdim if (FunctionDecl *ExplicitSpec 3027235633Sdim = S.ResolveSingleFunctionTemplateSpecialization(Ovl)) 3028252723Sdim return GetTypeOfFunction(S, R, ExplicitSpec); 3029235633Sdim } 3030235633Sdim 3031203955Srdivacky return QualType(); 3032235633Sdim } 3033235633Sdim 3034235633Sdim // Gather the explicit template arguments, if any. 3035235633Sdim TemplateArgumentListInfo ExplicitTemplateArgs; 3036235633Sdim if (Ovl->hasExplicitTemplateArgs()) 3037235633Sdim Ovl->getExplicitTemplateArgs().copyInto(ExplicitTemplateArgs); 3038203955Srdivacky QualType Match; 3039203955Srdivacky for (UnresolvedSetIterator I = Ovl->decls_begin(), 3040203955Srdivacky E = Ovl->decls_end(); I != E; ++I) { 3041203955Srdivacky NamedDecl *D = (*I)->getUnderlyingDecl(); 3042203955Srdivacky 3043235633Sdim if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) { 3044235633Sdim // - If the argument is an overload set containing one or more 3045235633Sdim // function templates, the parameter is treated as a 3046235633Sdim // non-deduced context. 3047235633Sdim if (!Ovl->hasExplicitTemplateArgs()) 3048235633Sdim return QualType(); 3049235633Sdim 3050235633Sdim // Otherwise, see if we can resolve a function type 3051235633Sdim FunctionDecl *Specialization = 0; 3052245431Sdim TemplateDeductionInfo Info(Ovl->getNameLoc()); 3053235633Sdim if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs, 3054235633Sdim Specialization, Info)) 3055235633Sdim continue; 3056235633Sdim 3057235633Sdim D = Specialization; 3058235633Sdim } 3059203955Srdivacky 3060203955Srdivacky FunctionDecl *Fn = cast<FunctionDecl>(D); 3061252723Sdim QualType ArgType = GetTypeOfFunction(S, R, Fn); 3062212904Sdim if (ArgType.isNull()) continue; 3063203955Srdivacky 3064212904Sdim // Function-to-pointer conversion. 3065218893Sdim if (!ParamWasReference && ParamType->isPointerType() && 3066212904Sdim ArgType->isFunctionType()) 3067212904Sdim ArgType = S.Context.getPointerType(ArgType); 3068218893Sdim 3069203955Srdivacky // - If the argument is an overload set (not containing function 3070203955Srdivacky // templates), trial argument deduction is attempted using each 3071203955Srdivacky // of the members of the set. If deduction succeeds for only one 3072203955Srdivacky // of the overload set members, that member is used as the 3073203955Srdivacky // argument value for the deduction. If deduction succeeds for 3074203955Srdivacky // more than one member of the overload set the parameter is 3075203955Srdivacky // treated as a non-deduced context. 3076203955Srdivacky 3077203955Srdivacky // We do all of this in a fresh context per C++0x [temp.deduct.type]p2: 3078203955Srdivacky // Type deduction is done independently for each P/A pair, and 3079203955Srdivacky // the deduced template argument values are then combined. 3080203955Srdivacky // So we do not reject deductions which were made elsewhere. 3081226890Sdim SmallVector<DeducedTemplateArgument, 8> 3082206084Srdivacky Deduced(TemplateParams->size()); 3083245431Sdim TemplateDeductionInfo Info(Ovl->getNameLoc()); 3084203955Srdivacky Sema::TemplateDeductionResult Result 3085235633Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType, 3086235633Sdim ArgType, Info, Deduced, TDF); 3087203955Srdivacky if (Result) continue; 3088203955Srdivacky if (!Match.isNull()) return QualType(); 3089203955Srdivacky Match = ArgType; 3090203955Srdivacky } 3091203955Srdivacky 3092203955Srdivacky return Match; 3093203955Srdivacky} 3094203955Srdivacky 3095218893Sdim/// \brief Perform the adjustments to the parameter and argument types 3096218893Sdim/// described in C++ [temp.deduct.call]. 3097218893Sdim/// 3098218893Sdim/// \returns true if the caller should not attempt to perform any template 3099252723Sdim/// argument deduction based on this P/A pair because the argument is an 3100252723Sdim/// overloaded function set that could not be resolved. 3101218893Sdimstatic bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S, 3102218893Sdim TemplateParameterList *TemplateParams, 3103218893Sdim QualType &ParamType, 3104218893Sdim QualType &ArgType, 3105218893Sdim Expr *Arg, 3106218893Sdim unsigned &TDF) { 3107218893Sdim // C++0x [temp.deduct.call]p3: 3108218893Sdim // If P is a cv-qualified type, the top level cv-qualifiers of P's type 3109218893Sdim // are ignored for type deduction. 3110221345Sdim if (ParamType.hasQualifiers()) 3111221345Sdim ParamType = ParamType.getUnqualifiedType(); 3112218893Sdim const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>(); 3113218893Sdim if (ParamRefType) { 3114218893Sdim QualType PointeeType = ParamRefType->getPointeeType(); 3115218893Sdim 3116252723Sdim // If the argument has incomplete array type, try to complete its type. 3117245431Sdim if (ArgType->isIncompleteArrayType() && !S.RequireCompleteExprType(Arg, 0)) 3118223017Sdim ArgType = Arg->getType(); 3119223017Sdim 3120218893Sdim // [C++0x] If P is an rvalue reference to a cv-unqualified 3121218893Sdim // template parameter and the argument is an lvalue, the type 3122218893Sdim // "lvalue reference to A" is used in place of A for type 3123218893Sdim // deduction. 3124218893Sdim if (isa<RValueReferenceType>(ParamType)) { 3125218893Sdim if (!PointeeType.getQualifiers() && 3126218893Sdim isa<TemplateTypeParmType>(PointeeType) && 3127223017Sdim Arg->Classify(S.Context).isLValue() && 3128223017Sdim Arg->getType() != S.Context.OverloadTy && 3129223017Sdim Arg->getType() != S.Context.BoundMemberTy) 3130218893Sdim ArgType = S.Context.getLValueReferenceType(ArgType); 3131218893Sdim } 3132218893Sdim 3133218893Sdim // [...] If P is a reference type, the type referred to by P is used 3134218893Sdim // for type deduction. 3135218893Sdim ParamType = PointeeType; 3136218893Sdim } 3137218893Sdim 3138218893Sdim // Overload sets usually make this parameter an undeduced 3139218893Sdim // context, but there are sometimes special circumstances. 3140218893Sdim if (ArgType == S.Context.OverloadTy) { 3141218893Sdim ArgType = ResolveOverloadForDeduction(S, TemplateParams, 3142218893Sdim Arg, ParamType, 3143218893Sdim ParamRefType != 0); 3144218893Sdim if (ArgType.isNull()) 3145218893Sdim return true; 3146218893Sdim } 3147218893Sdim 3148218893Sdim if (ParamRefType) { 3149218893Sdim // C++0x [temp.deduct.call]p3: 3150218893Sdim // [...] If P is of the form T&&, where T is a template parameter, and 3151218893Sdim // the argument is an lvalue, the type A& is used in place of A for 3152218893Sdim // type deduction. 3153218893Sdim if (ParamRefType->isRValueReferenceType() && 3154218893Sdim ParamRefType->getAs<TemplateTypeParmType>() && 3155218893Sdim Arg->isLValue()) 3156218893Sdim ArgType = S.Context.getLValueReferenceType(ArgType); 3157218893Sdim } else { 3158218893Sdim // C++ [temp.deduct.call]p2: 3159218893Sdim // If P is not a reference type: 3160218893Sdim // - If A is an array type, the pointer type produced by the 3161218893Sdim // array-to-pointer standard conversion (4.2) is used in place of 3162218893Sdim // A for type deduction; otherwise, 3163218893Sdim if (ArgType->isArrayType()) 3164218893Sdim ArgType = S.Context.getArrayDecayedType(ArgType); 3165218893Sdim // - If A is a function type, the pointer type produced by the 3166218893Sdim // function-to-pointer standard conversion (4.3) is used in place 3167218893Sdim // of A for type deduction; otherwise, 3168218893Sdim else if (ArgType->isFunctionType()) 3169218893Sdim ArgType = S.Context.getPointerType(ArgType); 3170218893Sdim else { 3171218893Sdim // - If A is a cv-qualified type, the top level cv-qualifiers of A's 3172218893Sdim // type are ignored for type deduction. 3173221345Sdim ArgType = ArgType.getUnqualifiedType(); 3174218893Sdim } 3175218893Sdim } 3176218893Sdim 3177218893Sdim // C++0x [temp.deduct.call]p4: 3178218893Sdim // In general, the deduction process attempts to find template argument 3179218893Sdim // values that will make the deduced A identical to A (after the type A 3180218893Sdim // is transformed as described above). [...] 3181218893Sdim TDF = TDF_SkipNonDependent; 3182218893Sdim 3183218893Sdim // - If the original P is a reference type, the deduced A (i.e., the 3184218893Sdim // type referred to by the reference) can be more cv-qualified than 3185218893Sdim // the transformed A. 3186218893Sdim if (ParamRefType) 3187218893Sdim TDF |= TDF_ParamWithReferenceType; 3188218893Sdim // - The transformed A can be another pointer or pointer to member 3189218893Sdim // type that can be converted to the deduced A via a qualification 3190218893Sdim // conversion (4.4). 3191218893Sdim if (ArgType->isPointerType() || ArgType->isMemberPointerType() || 3192218893Sdim ArgType->isObjCObjectPointerType()) 3193218893Sdim TDF |= TDF_IgnoreQualifiers; 3194218893Sdim // - If P is a class and P has the form simple-template-id, then the 3195218893Sdim // transformed A can be a derived class of the deduced A. Likewise, 3196218893Sdim // if P is a pointer to a class of the form simple-template-id, the 3197218893Sdim // transformed A can be a pointer to a derived class pointed to by 3198218893Sdim // the deduced A. 3199218893Sdim if (isSimpleTemplateIdType(ParamType) || 3200218893Sdim (isa<PointerType>(ParamType) && 3201218893Sdim isSimpleTemplateIdType( 3202218893Sdim ParamType->getAs<PointerType>()->getPointeeType()))) 3203218893Sdim TDF |= TDF_DerivedClass; 3204218893Sdim 3205218893Sdim return false; 3206218893Sdim} 3207218893Sdim 3208224145Sdimstatic bool hasDeducibleTemplateParameters(Sema &S, 3209224145Sdim FunctionTemplateDecl *FunctionTemplate, 3210224145Sdim QualType T); 3211224145Sdim 3212235633Sdim/// \brief Perform template argument deduction by matching a parameter type 3213235633Sdim/// against a single expression, where the expression is an element of 3214252723Sdim/// an initializer list that was originally matched against a parameter 3215252723Sdim/// of type \c initializer_list\<ParamType\>. 3216235633Sdimstatic Sema::TemplateDeductionResult 3217235633SdimDeduceTemplateArgumentByListElement(Sema &S, 3218235633Sdim TemplateParameterList *TemplateParams, 3219235633Sdim QualType ParamType, Expr *Arg, 3220235633Sdim TemplateDeductionInfo &Info, 3221235633Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 3222235633Sdim unsigned TDF) { 3223235633Sdim // Handle the case where an init list contains another init list as the 3224235633Sdim // element. 3225235633Sdim if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) { 3226235633Sdim QualType X; 3227235633Sdim if (!S.isStdInitializerList(ParamType.getNonReferenceType(), &X)) 3228235633Sdim return Sema::TDK_Success; // Just ignore this expression. 3229235633Sdim 3230235633Sdim // Recurse down into the init list. 3231235633Sdim for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) { 3232235633Sdim if (Sema::TemplateDeductionResult Result = 3233235633Sdim DeduceTemplateArgumentByListElement(S, TemplateParams, X, 3234235633Sdim ILE->getInit(i), 3235235633Sdim Info, Deduced, TDF)) 3236235633Sdim return Result; 3237235633Sdim } 3238235633Sdim return Sema::TDK_Success; 3239235633Sdim } 3240235633Sdim 3241235633Sdim // For all other cases, just match by type. 3242235633Sdim QualType ArgType = Arg->getType(); 3243235633Sdim if (AdjustFunctionParmAndArgTypesForDeduction(S, TemplateParams, ParamType, 3244252723Sdim ArgType, Arg, TDF)) { 3245252723Sdim Info.Expression = Arg; 3246235633Sdim return Sema::TDK_FailedOverloadResolution; 3247252723Sdim } 3248235633Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType, 3249235633Sdim ArgType, Info, Deduced, TDF); 3250235633Sdim} 3251235633Sdim 3252195099Sed/// \brief Perform template argument deduction from a function call 3253195099Sed/// (C++ [temp.deduct.call]). 3254195099Sed/// 3255195099Sed/// \param FunctionTemplate the function template for which we are performing 3256195099Sed/// template argument deduction. 3257195099Sed/// 3258245431Sdim/// \param ExplicitTemplateArgs the explicit template arguments provided 3259202379Srdivacky/// for this call. 3260195341Sed/// 3261195099Sed/// \param Args the function call arguments 3262195099Sed/// 3263195099Sed/// \param Specialization if template argument deduction was successful, 3264198092Srdivacky/// this will be set to the function template specialization produced by 3265195099Sed/// template argument deduction. 3266195099Sed/// 3267195099Sed/// \param Info the argument will be updated to provide additional information 3268195099Sed/// about template argument deduction. 3269195099Sed/// 3270195099Sed/// \returns the result of template argument deduction. 3271263509SdimSema::TemplateDeductionResult Sema::DeduceTemplateArguments( 3272263509Sdim FunctionTemplateDecl *FunctionTemplate, 3273263509Sdim TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args, 3274263509Sdim FunctionDecl *&Specialization, TemplateDeductionInfo &Info) { 3275245431Sdim if (FunctionTemplate->isInvalidDecl()) 3276245431Sdim return TDK_Invalid; 3277245431Sdim 3278195099Sed FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 3279195341Sed 3280195099Sed // C++ [temp.deduct.call]p1: 3281195099Sed // Template argument deduction is done by comparing each function template 3282195099Sed // parameter type (call it P) with the type of the corresponding argument 3283195099Sed // of the call (call it A) as described below. 3284235633Sdim unsigned CheckArgs = Args.size(); 3285235633Sdim if (Args.size() < Function->getMinRequiredArguments()) 3286195099Sed return TDK_TooFewArguments; 3287235633Sdim else if (Args.size() > Function->getNumParams()) { 3288198092Srdivacky const FunctionProtoType *Proto 3289198092Srdivacky = Function->getType()->getAs<FunctionProtoType>(); 3290218893Sdim if (Proto->isTemplateVariadic()) 3291218893Sdim /* Do nothing */; 3292218893Sdim else if (Proto->isVariadic()) 3293218893Sdim CheckArgs = Function->getNumParams(); 3294218893Sdim else 3295195099Sed return TDK_TooManyArguments; 3296195099Sed } 3297195341Sed 3298195341Sed // The types of the parameters from which we will perform template argument 3299195341Sed // deduction. 3300212904Sdim LocalInstantiationScope InstScope(*this); 3301195341Sed TemplateParameterList *TemplateParams 3302195341Sed = FunctionTemplate->getTemplateParameters(); 3303226890Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 3304226890Sdim SmallVector<QualType, 4> ParamTypes; 3305206084Srdivacky unsigned NumExplicitlySpecified = 0; 3306199990Srdivacky if (ExplicitTemplateArgs) { 3307198092Srdivacky TemplateDeductionResult Result = 3308198092Srdivacky SubstituteExplicitTemplateArguments(FunctionTemplate, 3309199990Srdivacky *ExplicitTemplateArgs, 3310198092Srdivacky Deduced, 3311198092Srdivacky ParamTypes, 3312198092Srdivacky 0, 3313198092Srdivacky Info); 3314198092Srdivacky if (Result) 3315198092Srdivacky return Result; 3316206084Srdivacky 3317206084Srdivacky NumExplicitlySpecified = Deduced.size(); 3318195341Sed } else { 3319195341Sed // Just fill in the parameter types from the function declaration. 3320218893Sdim for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 3321195341Sed ParamTypes.push_back(Function->getParamDecl(I)->getType()); 3322195341Sed } 3323198092Srdivacky 3324195099Sed // Deduce template arguments from the function parameters. 3325198092Srdivacky Deduced.resize(TemplateParams->size()); 3326218893Sdim unsigned ArgIdx = 0; 3327226890Sdim SmallVector<OriginalCallArg, 4> OriginalCallArgs; 3328218893Sdim for (unsigned ParamIdx = 0, NumParams = ParamTypes.size(); 3329218893Sdim ParamIdx != NumParams; ++ParamIdx) { 3330224145Sdim QualType OrigParamType = ParamTypes[ParamIdx]; 3331224145Sdim QualType ParamType = OrigParamType; 3332224145Sdim 3333218893Sdim const PackExpansionType *ParamExpansion 3334218893Sdim = dyn_cast<PackExpansionType>(ParamType); 3335218893Sdim if (!ParamExpansion) { 3336218893Sdim // Simple case: matching a function parameter to a function argument. 3337218893Sdim if (ArgIdx >= CheckArgs) 3338218893Sdim break; 3339218893Sdim 3340218893Sdim Expr *Arg = Args[ArgIdx++]; 3341218893Sdim QualType ArgType = Arg->getType(); 3342224145Sdim 3343218893Sdim unsigned TDF = 0; 3344218893Sdim if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams, 3345218893Sdim ParamType, ArgType, Arg, 3346218893Sdim TDF)) 3347203955Srdivacky continue; 3348218893Sdim 3349226890Sdim // If we have nothing to deduce, we're done. 3350226890Sdim if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType)) 3351226890Sdim continue; 3352226890Sdim 3353235633Sdim // If the argument is an initializer list ... 3354235633Sdim if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) { 3355235633Sdim // ... then the parameter is an undeduced context, unless the parameter 3356235633Sdim // type is (reference to cv) std::initializer_list<P'>, in which case 3357235633Sdim // deduction is done for each element of the initializer list, and the 3358235633Sdim // result is the deduced type if it's the same for all elements. 3359235633Sdim QualType X; 3360235633Sdim // Removing references was already done. 3361235633Sdim if (!isStdInitializerList(ParamType, &X)) 3362235633Sdim continue; 3363235633Sdim 3364235633Sdim for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) { 3365235633Sdim if (TemplateDeductionResult Result = 3366235633Sdim DeduceTemplateArgumentByListElement(*this, TemplateParams, X, 3367235633Sdim ILE->getInit(i), 3368235633Sdim Info, Deduced, TDF)) 3369235633Sdim return Result; 3370235633Sdim } 3371235633Sdim // Don't track the argument type, since an initializer list has none. 3372235633Sdim continue; 3373235633Sdim } 3374235633Sdim 3375224145Sdim // Keep track of the argument type and corresponding parameter index, 3376224145Sdim // so we can check for compatibility between the deduced A and A. 3377226890Sdim OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx-1, 3378226890Sdim ArgType)); 3379224145Sdim 3380218893Sdim if (TemplateDeductionResult Result 3381235633Sdim = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3382235633Sdim ParamType, ArgType, 3383235633Sdim Info, Deduced, TDF)) 3384218893Sdim return Result; 3385218893Sdim 3386218893Sdim continue; 3387203955Srdivacky } 3388203955Srdivacky 3389218893Sdim // C++0x [temp.deduct.call]p1: 3390218893Sdim // For a function parameter pack that occurs at the end of the 3391218893Sdim // parameter-declaration-list, the type A of each remaining argument of 3392218893Sdim // the call is compared with the type P of the declarator-id of the 3393218893Sdim // function parameter pack. Each comparison deduces template arguments 3394218893Sdim // for subsequent positions in the template parameter packs expanded by 3395218893Sdim // the function parameter pack. For a function parameter pack that does 3396218893Sdim // not occur at the end of the parameter-declaration-list, the type of 3397218893Sdim // the parameter pack is a non-deduced context. 3398218893Sdim if (ParamIdx + 1 < NumParams) 3399218893Sdim break; 3400218893Sdim 3401218893Sdim QualType ParamPattern = ParamExpansion->getPattern(); 3402226890Sdim SmallVector<unsigned, 2> PackIndices; 3403218893Sdim { 3404235633Sdim llvm::SmallBitVector SawIndices(TemplateParams->size()); 3405226890Sdim SmallVector<UnexpandedParameterPack, 2> Unexpanded; 3406218893Sdim collectUnexpandedParameterPacks(ParamPattern, Unexpanded); 3407218893Sdim for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) { 3408218893Sdim unsigned Depth, Index; 3409218893Sdim llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]); 3410218893Sdim if (Depth == 0 && !SawIndices[Index]) { 3411218893Sdim SawIndices[Index] = true; 3412218893Sdim PackIndices.push_back(Index); 3413218893Sdim } 3414194179Sed } 3415195099Sed } 3416218893Sdim assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?"); 3417198092Srdivacky 3418218893Sdim // Keep track of the deduced template arguments for each parameter pack 3419218893Sdim // expanded by this pack expansion (the outer index) and for each 3420218893Sdim // template argument (the inner SmallVectors). 3421263509Sdim NewlyDeducedPacksType NewlyDeducedPacks(PackIndices.size()); 3422226890Sdim SmallVector<DeducedTemplateArgument, 2> 3423218893Sdim SavedPacks(PackIndices.size()); 3424218893Sdim PrepareArgumentPackDeduction(*this, Deduced, PackIndices, SavedPacks, 3425218893Sdim NewlyDeducedPacks); 3426218893Sdim bool HasAnyArguments = false; 3427235633Sdim for (; ArgIdx < Args.size(); ++ArgIdx) { 3428218893Sdim HasAnyArguments = true; 3429198092Srdivacky 3430224145Sdim QualType OrigParamType = ParamPattern; 3431224145Sdim ParamType = OrigParamType; 3432218893Sdim Expr *Arg = Args[ArgIdx]; 3433218893Sdim QualType ArgType = Arg->getType(); 3434224145Sdim 3435218893Sdim unsigned TDF = 0; 3436218893Sdim if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams, 3437218893Sdim ParamType, ArgType, Arg, 3438218893Sdim TDF)) { 3439218893Sdim // We can't actually perform any deduction for this argument, so stop 3440218893Sdim // deduction at this point. 3441218893Sdim ++ArgIdx; 3442218893Sdim break; 3443218893Sdim } 3444198092Srdivacky 3445235633Sdim // As above, initializer lists need special handling. 3446235633Sdim if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) { 3447235633Sdim QualType X; 3448235633Sdim if (!isStdInitializerList(ParamType, &X)) { 3449235633Sdim ++ArgIdx; 3450235633Sdim break; 3451235633Sdim } 3452224145Sdim 3453235633Sdim for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) { 3454235633Sdim if (TemplateDeductionResult Result = 3455235633Sdim DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, X, 3456235633Sdim ILE->getInit(i)->getType(), 3457235633Sdim Info, Deduced, TDF)) 3458235633Sdim return Result; 3459235633Sdim } 3460235633Sdim } else { 3461218893Sdim 3462235633Sdim // Keep track of the argument type and corresponding argument index, 3463235633Sdim // so we can check for compatibility between the deduced A and A. 3464235633Sdim if (hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType)) 3465235633Sdim OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx, 3466235633Sdim ArgType)); 3467235633Sdim 3468235633Sdim if (TemplateDeductionResult Result 3469235633Sdim = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3470235633Sdim ParamType, ArgType, Info, 3471235633Sdim Deduced, TDF)) 3472235633Sdim return Result; 3473235633Sdim } 3474235633Sdim 3475218893Sdim // Capture the deduced template arguments for each parameter pack expanded 3476218893Sdim // by this pack expansion, add them to the list of arguments we've deduced 3477218893Sdim // for that pack, then clear out the deduced argument. 3478218893Sdim for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 3479218893Sdim DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]]; 3480218893Sdim if (!DeducedArg.isNull()) { 3481218893Sdim NewlyDeducedPacks[I].push_back(DeducedArg); 3482218893Sdim DeducedArg = DeducedTemplateArgument(); 3483218893Sdim } 3484218893Sdim } 3485218893Sdim } 3486218893Sdim 3487218893Sdim // Build argument packs for each of the parameter packs expanded by this 3488218893Sdim // pack expansion. 3489218893Sdim if (Sema::TemplateDeductionResult Result 3490218893Sdim = FinishArgumentPackDeduction(*this, TemplateParams, HasAnyArguments, 3491218893Sdim Deduced, PackIndices, SavedPacks, 3492218893Sdim NewlyDeducedPacks, Info)) 3493195099Sed return Result; 3494198092Srdivacky 3495218893Sdim // After we've matching against a parameter pack, we're done. 3496218893Sdim break; 3497198092Srdivacky } 3498198092Srdivacky 3499198092Srdivacky return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 3500206084Srdivacky NumExplicitlySpecified, 3501224145Sdim Specialization, Info, &OriginalCallArgs); 3502198092Srdivacky} 3503198092Srdivacky 3504263509SdimQualType Sema::adjustCCAndNoReturn(QualType ArgFunctionType, 3505263509Sdim QualType FunctionType) { 3506263509Sdim if (ArgFunctionType.isNull()) 3507263509Sdim return ArgFunctionType; 3508263509Sdim 3509263509Sdim const FunctionProtoType *FunctionTypeP = 3510263509Sdim FunctionType->castAs<FunctionProtoType>(); 3511263509Sdim CallingConv CC = FunctionTypeP->getCallConv(); 3512263509Sdim bool NoReturn = FunctionTypeP->getNoReturnAttr(); 3513263509Sdim const FunctionProtoType *ArgFunctionTypeP = 3514263509Sdim ArgFunctionType->getAs<FunctionProtoType>(); 3515263509Sdim if (ArgFunctionTypeP->getCallConv() == CC && 3516263509Sdim ArgFunctionTypeP->getNoReturnAttr() == NoReturn) 3517263509Sdim return ArgFunctionType; 3518263509Sdim 3519263509Sdim FunctionType::ExtInfo EI = ArgFunctionTypeP->getExtInfo().withCallingConv(CC); 3520263509Sdim EI = EI.withNoReturn(NoReturn); 3521263509Sdim ArgFunctionTypeP = 3522263509Sdim cast<FunctionProtoType>(Context.adjustFunctionType(ArgFunctionTypeP, EI)); 3523263509Sdim return QualType(ArgFunctionTypeP, 0); 3524263509Sdim} 3525263509Sdim 3526198092Srdivacky/// \brief Deduce template arguments when taking the address of a function 3527201361Srdivacky/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to 3528201361Srdivacky/// a template. 3529198092Srdivacky/// 3530198092Srdivacky/// \param FunctionTemplate the function template for which we are performing 3531198092Srdivacky/// template argument deduction. 3532198092Srdivacky/// 3533245431Sdim/// \param ExplicitTemplateArgs the explicitly-specified template 3534201361Srdivacky/// arguments. 3535198092Srdivacky/// 3536198092Srdivacky/// \param ArgFunctionType the function type that will be used as the 3537198092Srdivacky/// "argument" type (A) when performing template argument deduction from the 3538201361Srdivacky/// function template's function type. This type may be NULL, if there is no 3539201361Srdivacky/// argument type to compare against, in C++0x [temp.arg.explicit]p3. 3540198092Srdivacky/// 3541198092Srdivacky/// \param Specialization if template argument deduction was successful, 3542198092Srdivacky/// this will be set to the function template specialization produced by 3543198092Srdivacky/// template argument deduction. 3544198092Srdivacky/// 3545198092Srdivacky/// \param Info the argument will be updated to provide additional information 3546198092Srdivacky/// about template argument deduction. 3547198092Srdivacky/// 3548198092Srdivacky/// \returns the result of template argument deduction. 3549198092SrdivackySema::TemplateDeductionResult 3550198092SrdivackySema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 3551221345Sdim TemplateArgumentListInfo *ExplicitTemplateArgs, 3552198092Srdivacky QualType ArgFunctionType, 3553198092Srdivacky FunctionDecl *&Specialization, 3554252723Sdim TemplateDeductionInfo &Info, 3555252723Sdim bool InOverloadResolution) { 3556245431Sdim if (FunctionTemplate->isInvalidDecl()) 3557245431Sdim return TDK_Invalid; 3558245431Sdim 3559198092Srdivacky FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 3560198092Srdivacky TemplateParameterList *TemplateParams 3561198092Srdivacky = FunctionTemplate->getTemplateParameters(); 3562198092Srdivacky QualType FunctionType = Function->getType(); 3563263509Sdim if (!InOverloadResolution) 3564263509Sdim ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, FunctionType); 3565198092Srdivacky 3566198092Srdivacky // Substitute any explicit template arguments. 3567212904Sdim LocalInstantiationScope InstScope(*this); 3568226890Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 3569206084Srdivacky unsigned NumExplicitlySpecified = 0; 3570226890Sdim SmallVector<QualType, 4> ParamTypes; 3571199990Srdivacky if (ExplicitTemplateArgs) { 3572198092Srdivacky if (TemplateDeductionResult Result 3573198092Srdivacky = SubstituteExplicitTemplateArguments(FunctionTemplate, 3574199990Srdivacky *ExplicitTemplateArgs, 3575198092Srdivacky Deduced, ParamTypes, 3576198092Srdivacky &FunctionType, Info)) 3577198092Srdivacky return Result; 3578206084Srdivacky 3579206084Srdivacky NumExplicitlySpecified = Deduced.size(); 3580198092Srdivacky } 3581198092Srdivacky 3582235633Sdim // Unevaluated SFINAE context. 3583235633Sdim EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 3584198092Srdivacky SFINAETrap Trap(*this); 3585198092Srdivacky 3586203955Srdivacky Deduced.resize(TemplateParams->size()); 3587203955Srdivacky 3588252723Sdim // If the function has a deduced return type, substitute it for a dependent 3589252723Sdim // type so that we treat it as a non-deduced context in what follows. 3590263509Sdim bool HasDeducedReturnType = false; 3591252723Sdim if (getLangOpts().CPlusPlus1y && InOverloadResolution && 3592263509Sdim Function->getResultType()->getContainedAutoType()) { 3593252723Sdim FunctionType = SubstAutoType(FunctionType, Context.DependentTy); 3594263509Sdim HasDeducedReturnType = true; 3595252723Sdim } 3596252723Sdim 3597201361Srdivacky if (!ArgFunctionType.isNull()) { 3598252723Sdim unsigned TDF = TDF_TopLevelParameterTypeList; 3599252723Sdim if (InOverloadResolution) TDF |= TDF_InOverloadResolution; 3600201361Srdivacky // Deduce template arguments from the function type. 3601201361Srdivacky if (TemplateDeductionResult Result 3602235633Sdim = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3603252723Sdim FunctionType, ArgFunctionType, 3604252723Sdim Info, Deduced, TDF)) 3605201361Srdivacky return Result; 3606201361Srdivacky } 3607218893Sdim 3608218893Sdim if (TemplateDeductionResult Result 3609218893Sdim = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 3610218893Sdim NumExplicitlySpecified, 3611218893Sdim Specialization, Info)) 3612218893Sdim return Result; 3613218893Sdim 3614252723Sdim // If the function has a deduced return type, deduce it now, so we can check 3615252723Sdim // that the deduced function type matches the requested type. 3616263509Sdim if (HasDeducedReturnType && 3617252723Sdim Specialization->getResultType()->isUndeducedType() && 3618252723Sdim DeduceReturnType(Specialization, Info.getLocation(), false)) 3619252723Sdim return TDK_MiscellaneousDeductionFailure; 3620252723Sdim 3621218893Sdim // If the requested function type does not match the actual type of the 3622252723Sdim // specialization with respect to arguments of compatible pointer to function 3623252723Sdim // types, template argument deduction fails. 3624252723Sdim if (!ArgFunctionType.isNull()) { 3625252723Sdim if (InOverloadResolution && !isSameOrCompatibleFunctionType( 3626252723Sdim Context.getCanonicalType(Specialization->getType()), 3627252723Sdim Context.getCanonicalType(ArgFunctionType))) 3628252723Sdim return TDK_MiscellaneousDeductionFailure; 3629252723Sdim else if(!InOverloadResolution && 3630252723Sdim !Context.hasSameType(Specialization->getType(), ArgFunctionType)) 3631252723Sdim return TDK_MiscellaneousDeductionFailure; 3632252723Sdim } 3633218893Sdim 3634218893Sdim return TDK_Success; 3635198092Srdivacky} 3636198092Srdivacky 3637263509Sdim/// \brief Given a function declaration (e.g. a generic lambda conversion 3638263509Sdim/// function) that contains an 'auto' in its result type, substitute it 3639263509Sdim/// with TypeToReplaceAutoWith. Be careful to pass in the type you want 3640263509Sdim/// to replace 'auto' with and not the actual result type you want 3641263509Sdim/// to set the function to. 3642263509Sdimstatic inline void 3643263509SdimSubstAutoWithinFunctionReturnType(FunctionDecl *F, 3644263509Sdim QualType TypeToReplaceAutoWith, Sema &S) { 3645263509Sdim assert(!TypeToReplaceAutoWith->getContainedAutoType()); 3646263509Sdim QualType AutoResultType = F->getResultType(); 3647263509Sdim assert(AutoResultType->getContainedAutoType()); 3648263509Sdim QualType DeducedResultType = S.SubstAutoType(AutoResultType, 3649263509Sdim TypeToReplaceAutoWith); 3650263509Sdim S.Context.adjustDeducedFunctionResultType(F, DeducedResultType); 3651263509Sdim} 3652263509Sdim 3653263509Sdim/// \brief Given a specialized conversion operator of a generic lambda 3654263509Sdim/// create the corresponding specializations of the call operator and 3655263509Sdim/// the static-invoker. If the return type of the call operator is auto, 3656263509Sdim/// deduce its return type and check if that matches the 3657263509Sdim/// return type of the destination function ptr. 3658263509Sdim 3659263509Sdimstatic inline Sema::TemplateDeductionResult 3660263509SdimSpecializeCorrespondingLambdaCallOperatorAndInvoker( 3661263509Sdim CXXConversionDecl *ConversionSpecialized, 3662263509Sdim SmallVectorImpl<DeducedTemplateArgument> &DeducedArguments, 3663263509Sdim QualType ReturnTypeOfDestFunctionPtr, 3664263509Sdim TemplateDeductionInfo &TDInfo, 3665263509Sdim Sema &S) { 3666263509Sdim 3667263509Sdim CXXRecordDecl *LambdaClass = ConversionSpecialized->getParent(); 3668263509Sdim assert(LambdaClass && LambdaClass->isGenericLambda()); 3669263509Sdim 3670263509Sdim CXXMethodDecl *CallOpGeneric = LambdaClass->getLambdaCallOperator(); 3671263509Sdim QualType CallOpResultType = CallOpGeneric->getResultType(); 3672263509Sdim const bool GenericLambdaCallOperatorHasDeducedReturnType = 3673263509Sdim CallOpResultType->getContainedAutoType(); 3674263509Sdim 3675263509Sdim FunctionTemplateDecl *CallOpTemplate = 3676263509Sdim CallOpGeneric->getDescribedFunctionTemplate(); 3677263509Sdim 3678263509Sdim FunctionDecl *CallOpSpecialized = 0; 3679263509Sdim // Use the deduced arguments of the conversion function, to specialize our 3680263509Sdim // generic lambda's call operator. 3681263509Sdim if (Sema::TemplateDeductionResult Result 3682263509Sdim = S.FinishTemplateArgumentDeduction(CallOpTemplate, 3683263509Sdim DeducedArguments, 3684263509Sdim 0, CallOpSpecialized, TDInfo)) 3685263509Sdim return Result; 3686263509Sdim 3687263509Sdim // If we need to deduce the return type, do so (instantiates the callop). 3688263509Sdim if (GenericLambdaCallOperatorHasDeducedReturnType && 3689263509Sdim CallOpSpecialized->getResultType()->isUndeducedType()) 3690263509Sdim S.DeduceReturnType(CallOpSpecialized, 3691263509Sdim CallOpSpecialized->getPointOfInstantiation(), 3692263509Sdim /*Diagnose*/ true); 3693263509Sdim 3694263509Sdim // Check to see if the return type of the destination ptr-to-function 3695263509Sdim // matches the return type of the call operator. 3696263509Sdim if (!S.Context.hasSameType(CallOpSpecialized->getResultType(), 3697263509Sdim ReturnTypeOfDestFunctionPtr)) 3698263509Sdim return Sema::TDK_NonDeducedMismatch; 3699263509Sdim // Since we have succeeded in matching the source and destination 3700263509Sdim // ptr-to-functions (now including return type), and have successfully 3701263509Sdim // specialized our corresponding call operator, we are ready to 3702263509Sdim // specialize the static invoker with the deduced arguments of our 3703263509Sdim // ptr-to-function. 3704263509Sdim FunctionDecl *InvokerSpecialized = 0; 3705263509Sdim FunctionTemplateDecl *InvokerTemplate = LambdaClass-> 3706263509Sdim getLambdaStaticInvoker()->getDescribedFunctionTemplate(); 3707263509Sdim 3708263509Sdim Sema::TemplateDeductionResult LLVM_ATTRIBUTE_UNUSED Result 3709263509Sdim = S.FinishTemplateArgumentDeduction(InvokerTemplate, DeducedArguments, 0, 3710263509Sdim InvokerSpecialized, TDInfo); 3711263509Sdim assert(Result == Sema::TDK_Success && 3712263509Sdim "If the call operator succeeded so should the invoker!"); 3713263509Sdim // Set the result type to match the corresponding call operator 3714263509Sdim // specialization's result type. 3715263509Sdim if (GenericLambdaCallOperatorHasDeducedReturnType && 3716263509Sdim InvokerSpecialized->getResultType()->isUndeducedType()) { 3717263509Sdim // Be sure to get the type to replace 'auto' with and not 3718263509Sdim // the full result type of the call op specialization 3719263509Sdim // to substitute into the 'auto' of the invoker and conversion 3720263509Sdim // function. 3721263509Sdim // For e.g. 3722263509Sdim // int* (*fp)(int*) = [](auto* a) -> auto* { return a; }; 3723263509Sdim // We don't want to subst 'int*' into 'auto' to get int**. 3724263509Sdim 3725263509Sdim QualType TypeToReplaceAutoWith = 3726263509Sdim CallOpSpecialized->getResultType()-> 3727263509Sdim getContainedAutoType()->getDeducedType(); 3728263509Sdim SubstAutoWithinFunctionReturnType(InvokerSpecialized, 3729263509Sdim TypeToReplaceAutoWith, S); 3730263509Sdim SubstAutoWithinFunctionReturnType(ConversionSpecialized, 3731263509Sdim TypeToReplaceAutoWith, S); 3732263509Sdim } 3733263509Sdim 3734263509Sdim // Ensure that static invoker doesn't have a const qualifier. 3735263509Sdim // FIXME: When creating the InvokerTemplate in SemaLambda.cpp 3736263509Sdim // do not use the CallOperator's TypeSourceInfo which allows 3737263509Sdim // the const qualifier to leak through. 3738263509Sdim const FunctionProtoType *InvokerFPT = InvokerSpecialized-> 3739263509Sdim getType().getTypePtr()->castAs<FunctionProtoType>(); 3740263509Sdim FunctionProtoType::ExtProtoInfo EPI = InvokerFPT->getExtProtoInfo(); 3741263509Sdim EPI.TypeQuals = 0; 3742263509Sdim InvokerSpecialized->setType(S.Context.getFunctionType( 3743263509Sdim InvokerFPT->getResultType(), InvokerFPT->getArgTypes(),EPI)); 3744263509Sdim return Sema::TDK_Success; 3745263509Sdim} 3746198092Srdivacky/// \brief Deduce template arguments for a templated conversion 3747198092Srdivacky/// function (C++ [temp.deduct.conv]) and, if successful, produce a 3748198092Srdivacky/// conversion function template specialization. 3749198092SrdivackySema::TemplateDeductionResult 3750263509SdimSema::DeduceTemplateArguments(FunctionTemplateDecl *ConversionTemplate, 3751198092Srdivacky QualType ToType, 3752198092Srdivacky CXXConversionDecl *&Specialization, 3753198092Srdivacky TemplateDeductionInfo &Info) { 3754263509Sdim if (ConversionTemplate->isInvalidDecl()) 3755245431Sdim return TDK_Invalid; 3756245431Sdim 3757263509Sdim CXXConversionDecl *ConversionGeneric 3758263509Sdim = cast<CXXConversionDecl>(ConversionTemplate->getTemplatedDecl()); 3759198092Srdivacky 3760263509Sdim QualType FromType = ConversionGeneric->getConversionType(); 3761263509Sdim 3762198092Srdivacky // Canonicalize the types for deduction. 3763198092Srdivacky QualType P = Context.getCanonicalType(FromType); 3764198092Srdivacky QualType A = Context.getCanonicalType(ToType); 3765198092Srdivacky 3766221345Sdim // C++0x [temp.deduct.conv]p2: 3767198092Srdivacky // If P is a reference type, the type referred to by P is used for 3768198092Srdivacky // type deduction. 3769198092Srdivacky if (const ReferenceType *PRef = P->getAs<ReferenceType>()) 3770198092Srdivacky P = PRef->getPointeeType(); 3771198092Srdivacky 3772221345Sdim // C++0x [temp.deduct.conv]p4: 3773221345Sdim // [...] If A is a reference type, the type referred to by A is used 3774198092Srdivacky // for type deduction. 3775198092Srdivacky if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 3776221345Sdim A = ARef->getPointeeType().getUnqualifiedType(); 3777221345Sdim // C++ [temp.deduct.conv]p3: 3778198092Srdivacky // 3779198092Srdivacky // If A is not a reference type: 3780198092Srdivacky else { 3781198092Srdivacky assert(!A->isReferenceType() && "Reference types were handled above"); 3782198092Srdivacky 3783198092Srdivacky // - If P is an array type, the pointer type produced by the 3784198092Srdivacky // array-to-pointer standard conversion (4.2) is used in place 3785198092Srdivacky // of P for type deduction; otherwise, 3786198092Srdivacky if (P->isArrayType()) 3787198092Srdivacky P = Context.getArrayDecayedType(P); 3788198092Srdivacky // - If P is a function type, the pointer type produced by the 3789198092Srdivacky // function-to-pointer standard conversion (4.3) is used in 3790198092Srdivacky // place of P for type deduction; otherwise, 3791198092Srdivacky else if (P->isFunctionType()) 3792198092Srdivacky P = Context.getPointerType(P); 3793198092Srdivacky // - If P is a cv-qualified type, the top level cv-qualifiers of 3794218893Sdim // P's type are ignored for type deduction. 3795198092Srdivacky else 3796198092Srdivacky P = P.getUnqualifiedType(); 3797198092Srdivacky 3798221345Sdim // C++0x [temp.deduct.conv]p4: 3799218893Sdim // If A is a cv-qualified type, the top level cv-qualifiers of A's 3800221345Sdim // type are ignored for type deduction. If A is a reference type, the type 3801221345Sdim // referred to by A is used for type deduction. 3802198092Srdivacky A = A.getUnqualifiedType(); 3803198092Srdivacky } 3804198092Srdivacky 3805235633Sdim // Unevaluated SFINAE context. 3806235633Sdim EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 3807198092Srdivacky SFINAETrap Trap(*this); 3808198092Srdivacky 3809198092Srdivacky // C++ [temp.deduct.conv]p1: 3810198092Srdivacky // Template argument deduction is done by comparing the return 3811198092Srdivacky // type of the template conversion function (call it P) with the 3812198092Srdivacky // type that is required as the result of the conversion (call it 3813198092Srdivacky // A) as described in 14.8.2.4. 3814198092Srdivacky TemplateParameterList *TemplateParams 3815263509Sdim = ConversionTemplate->getTemplateParameters(); 3816226890Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 3817198092Srdivacky Deduced.resize(TemplateParams->size()); 3818198092Srdivacky 3819198092Srdivacky // C++0x [temp.deduct.conv]p4: 3820198092Srdivacky // In general, the deduction process attempts to find template 3821198092Srdivacky // argument values that will make the deduced A identical to 3822198092Srdivacky // A. However, there are two cases that allow a difference: 3823198092Srdivacky unsigned TDF = 0; 3824198092Srdivacky // - If the original A is a reference type, A can be more 3825198092Srdivacky // cv-qualified than the deduced A (i.e., the type referred to 3826198092Srdivacky // by the reference) 3827198092Srdivacky if (ToType->isReferenceType()) 3828198092Srdivacky TDF |= TDF_ParamWithReferenceType; 3829198092Srdivacky // - The deduced A can be another pointer or pointer to member 3830218893Sdim // type that can be converted to A via a qualification 3831198092Srdivacky // conversion. 3832198092Srdivacky // 3833198092Srdivacky // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 3834198092Srdivacky // both P and A are pointers or member pointers. In this case, we 3835198092Srdivacky // just ignore cv-qualifiers completely). 3836198092Srdivacky if ((P->isPointerType() && A->isPointerType()) || 3837226890Sdim (P->isMemberPointerType() && A->isMemberPointerType())) 3838198092Srdivacky TDF |= TDF_IgnoreQualifiers; 3839198092Srdivacky if (TemplateDeductionResult Result 3840235633Sdim = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3841235633Sdim P, A, Info, Deduced, TDF)) 3842198092Srdivacky return Result; 3843198092Srdivacky 3844263509Sdim // Create an Instantiation Scope for finalizing the operator. 3845263509Sdim LocalInstantiationScope InstScope(*this); 3846198092Srdivacky // Finish template argument deduction. 3847263509Sdim FunctionDecl *ConversionSpecialized = 0; 3848198092Srdivacky TemplateDeductionResult Result 3849263509Sdim = FinishTemplateArgumentDeduction(ConversionTemplate, Deduced, 0, 3850263509Sdim ConversionSpecialized, Info); 3851263509Sdim Specialization = cast_or_null<CXXConversionDecl>(ConversionSpecialized); 3852263509Sdim 3853263509Sdim // If the conversion operator is being invoked on a lambda closure to convert 3854263509Sdim // to a ptr-to-function, use the deduced arguments from the conversion function 3855263509Sdim // to specialize the corresponding call operator. 3856263509Sdim // e.g., int (*fp)(int) = [](auto a) { return a; }; 3857263509Sdim if (Result == TDK_Success && isLambdaConversionOperator(ConversionGeneric)) { 3858263509Sdim 3859263509Sdim // Get the return type of the destination ptr-to-function we are converting 3860263509Sdim // to. This is necessary for matching the lambda call operator's return 3861263509Sdim // type to that of the destination ptr-to-function's return type. 3862263509Sdim assert(A->isPointerType() && 3863263509Sdim "Can only convert from lambda to ptr-to-function"); 3864263509Sdim const FunctionType *ToFunType = 3865263509Sdim A->getPointeeType().getTypePtr()->getAs<FunctionType>(); 3866263509Sdim const QualType DestFunctionPtrReturnType = ToFunType->getResultType(); 3867263509Sdim 3868263509Sdim // Create the corresponding specializations of the call operator and 3869263509Sdim // the static-invoker; and if the return type is auto, 3870263509Sdim // deduce the return type and check if it matches the 3871263509Sdim // DestFunctionPtrReturnType. 3872263509Sdim // For instance: 3873263509Sdim // auto L = [](auto a) { return f(a); }; 3874263509Sdim // int (*fp)(int) = L; 3875263509Sdim // char (*fp2)(int) = L; <-- Not OK. 3876263509Sdim 3877263509Sdim Result = SpecializeCorrespondingLambdaCallOperatorAndInvoker( 3878263509Sdim Specialization, Deduced, DestFunctionPtrReturnType, 3879263509Sdim Info, *this); 3880263509Sdim } 3881198092Srdivacky return Result; 3882198092Srdivacky} 3883198092Srdivacky 3884201361Srdivacky/// \brief Deduce template arguments for a function template when there is 3885201361Srdivacky/// nothing to deduce against (C++0x [temp.arg.explicit]p3). 3886201361Srdivacky/// 3887201361Srdivacky/// \param FunctionTemplate the function template for which we are performing 3888201361Srdivacky/// template argument deduction. 3889201361Srdivacky/// 3890245431Sdim/// \param ExplicitTemplateArgs the explicitly-specified template 3891201361Srdivacky/// arguments. 3892201361Srdivacky/// 3893201361Srdivacky/// \param Specialization if template argument deduction was successful, 3894201361Srdivacky/// this will be set to the function template specialization produced by 3895201361Srdivacky/// template argument deduction. 3896201361Srdivacky/// 3897201361Srdivacky/// \param Info the argument will be updated to provide additional information 3898201361Srdivacky/// about template argument deduction. 3899201361Srdivacky/// 3900201361Srdivacky/// \returns the result of template argument deduction. 3901201361SrdivackySema::TemplateDeductionResult 3902201361SrdivackySema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 3903221345Sdim TemplateArgumentListInfo *ExplicitTemplateArgs, 3904201361Srdivacky FunctionDecl *&Specialization, 3905252723Sdim TemplateDeductionInfo &Info, 3906252723Sdim bool InOverloadResolution) { 3907201361Srdivacky return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs, 3908252723Sdim QualType(), Specialization, Info, 3909252723Sdim InOverloadResolution); 3910201361Srdivacky} 3911201361Srdivacky 3912218893Sdimnamespace { 3913218893Sdim /// Substitute the 'auto' type specifier within a type for a given replacement 3914218893Sdim /// type. 3915218893Sdim class SubstituteAutoTransform : 3916218893Sdim public TreeTransform<SubstituteAutoTransform> { 3917218893Sdim QualType Replacement; 3918218893Sdim public: 3919218893Sdim SubstituteAutoTransform(Sema &SemaRef, QualType Replacement) : 3920218893Sdim TreeTransform<SubstituteAutoTransform>(SemaRef), Replacement(Replacement) { 3921218893Sdim } 3922218893Sdim QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) { 3923218893Sdim // If we're building the type pattern to deduce against, don't wrap the 3924218893Sdim // substituted type in an AutoType. Certain template deduction rules 3925218893Sdim // apply only when a template type parameter appears directly (and not if 3926218893Sdim // the parameter is found through desugaring). For instance: 3927218893Sdim // auto &&lref = lvalue; 3928218893Sdim // must transform into "rvalue reference to T" not "rvalue reference to 3929218893Sdim // auto type deduced as T" in order for [temp.deduct.call]p3 to apply. 3930252723Sdim if (!Replacement.isNull() && isa<TemplateTypeParmType>(Replacement)) { 3931218893Sdim QualType Result = Replacement; 3932252723Sdim TemplateTypeParmTypeLoc NewTL = 3933252723Sdim TLB.push<TemplateTypeParmTypeLoc>(Result); 3934218893Sdim NewTL.setNameLoc(TL.getNameLoc()); 3935218893Sdim return Result; 3936218893Sdim } else { 3937252723Sdim bool Dependent = 3938252723Sdim !Replacement.isNull() && Replacement->isDependentType(); 3939252723Sdim QualType Result = 3940252723Sdim SemaRef.Context.getAutoType(Dependent ? QualType() : Replacement, 3941252723Sdim TL.getTypePtr()->isDecltypeAuto(), 3942252723Sdim Dependent); 3943218893Sdim AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result); 3944218893Sdim NewTL.setNameLoc(TL.getNameLoc()); 3945218893Sdim return Result; 3946218893Sdim } 3947218893Sdim } 3948235633Sdim 3949235633Sdim ExprResult TransformLambdaExpr(LambdaExpr *E) { 3950235633Sdim // Lambdas never need to be transformed. 3951235633Sdim return E; 3952235633Sdim } 3953245431Sdim 3954252723Sdim QualType Apply(TypeLoc TL) { 3955252723Sdim // Create some scratch storage for the transformed type locations. 3956252723Sdim // FIXME: We're just going to throw this information away. Don't build it. 3957252723Sdim TypeLocBuilder TLB; 3958252723Sdim TLB.reserve(TL.getFullDataSize()); 3959252723Sdim return TransformType(TLB, TL); 3960245431Sdim } 3961252723Sdim }; 3962218893Sdim} 3963198092Srdivacky 3964252723SdimSema::DeduceAutoResult 3965252723SdimSema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result) { 3966252723Sdim return DeduceAutoType(Type->getTypeLoc(), Init, Result); 3967252723Sdim} 3968252723Sdim 3969252723Sdim/// \brief Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6) 3970198092Srdivacky/// 3971218893Sdim/// \param Type the type pattern using the auto type-specifier. 3972218893Sdim/// \param Init the initializer for the variable whose type is to be deduced. 3973218893Sdim/// \param Result if type deduction was successful, this will be set to the 3974252723Sdim/// deduced type. 3975235633SdimSema::DeduceAutoResult 3976252723SdimSema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) { 3977235633Sdim if (Init->getType()->isNonOverloadPlaceholderType()) { 3978252723Sdim ExprResult NonPlaceholder = CheckPlaceholderExpr(Init); 3979252723Sdim if (NonPlaceholder.isInvalid()) 3980252723Sdim return DAR_FailedAlreadyDiagnosed; 3981252723Sdim Init = NonPlaceholder.take(); 3982235633Sdim } 3983235633Sdim 3984252723Sdim if (Init->isTypeDependent() || Type.getType()->isDependentType()) { 3985252723Sdim Result = SubstituteAutoTransform(*this, Context.DependentTy).Apply(Type); 3986252723Sdim assert(!Result.isNull() && "substituting DependentTy can't fail"); 3987235633Sdim return DAR_Succeeded; 3988218893Sdim } 3989198092Srdivacky 3990252723Sdim // If this is a 'decltype(auto)' specifier, do the decltype dance. 3991252723Sdim // Since 'decltype(auto)' can only occur at the top of the type, we 3992252723Sdim // don't need to go digging for it. 3993252723Sdim if (const AutoType *AT = Type.getType()->getAs<AutoType>()) { 3994252723Sdim if (AT->isDecltypeAuto()) { 3995252723Sdim if (isa<InitListExpr>(Init)) { 3996252723Sdim Diag(Init->getLocStart(), diag::err_decltype_auto_initializer_list); 3997252723Sdim return DAR_FailedAlreadyDiagnosed; 3998252723Sdim } 3999252723Sdim 4000252723Sdim QualType Deduced = BuildDecltypeType(Init, Init->getLocStart()); 4001252723Sdim // FIXME: Support a non-canonical deduced type for 'auto'. 4002252723Sdim Deduced = Context.getCanonicalType(Deduced); 4003252723Sdim Result = SubstituteAutoTransform(*this, Deduced).Apply(Type); 4004252723Sdim if (Result.isNull()) 4005252723Sdim return DAR_FailedAlreadyDiagnosed; 4006252723Sdim return DAR_Succeeded; 4007252723Sdim } 4008252723Sdim } 4009252723Sdim 4010218893Sdim SourceLocation Loc = Init->getExprLoc(); 4011218893Sdim 4012218893Sdim LocalInstantiationScope InstScope(*this); 4013218893Sdim 4014218893Sdim // Build template<class TemplParam> void Func(FuncParam); 4015221345Sdim TemplateTypeParmDecl *TemplParam = 4016221345Sdim TemplateTypeParmDecl::Create(Context, 0, SourceLocation(), Loc, 0, 0, 0, 4017221345Sdim false, false); 4018221345Sdim QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0); 4019221345Sdim NamedDecl *TemplParamPtr = TemplParam; 4020219077Sdim FixedSizeTemplateParameterList<1> TemplateParams(Loc, Loc, &TemplParamPtr, 4021219077Sdim Loc); 4022218893Sdim 4023252723Sdim QualType FuncParam = SubstituteAutoTransform(*this, TemplArg).Apply(Type); 4024252723Sdim assert(!FuncParam.isNull() && 4025252723Sdim "substituting template parameter for 'auto' failed"); 4026218893Sdim 4027218893Sdim // Deduce type of TemplParam in Func(Init) 4028226890Sdim SmallVector<DeducedTemplateArgument, 1> Deduced; 4029218893Sdim Deduced.resize(1); 4030218893Sdim QualType InitType = Init->getType(); 4031218893Sdim unsigned TDF = 0; 4032218893Sdim 4033245431Sdim TemplateDeductionInfo Info(Loc); 4034218893Sdim 4035245431Sdim InitListExpr *InitList = dyn_cast<InitListExpr>(Init); 4036235633Sdim if (InitList) { 4037235633Sdim for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) { 4038245431Sdim if (DeduceTemplateArgumentByListElement(*this, &TemplateParams, 4039235633Sdim TemplArg, 4040235633Sdim InitList->getInit(i), 4041235633Sdim Info, Deduced, TDF)) 4042235633Sdim return DAR_Failed; 4043235633Sdim } 4044235633Sdim } else { 4045235633Sdim if (AdjustFunctionParmAndArgTypesForDeduction(*this, &TemplateParams, 4046235633Sdim FuncParam, InitType, Init, 4047235633Sdim TDF)) 4048235633Sdim return DAR_Failed; 4049245431Sdim 4050235633Sdim if (DeduceTemplateArgumentsByTypeMatch(*this, &TemplateParams, FuncParam, 4051235633Sdim InitType, Info, Deduced, TDF)) 4052235633Sdim return DAR_Failed; 4053235633Sdim } 4054235633Sdim 4055245431Sdim if (Deduced[0].getKind() != TemplateArgument::Type) 4056235633Sdim return DAR_Failed; 4057235633Sdim 4058245431Sdim QualType DeducedType = Deduced[0].getAsType(); 4059245431Sdim 4060235633Sdim if (InitList) { 4061235633Sdim DeducedType = BuildStdInitializerList(DeducedType, Loc); 4062235633Sdim if (DeducedType.isNull()) 4063235633Sdim return DAR_FailedAlreadyDiagnosed; 4064235633Sdim } 4065235633Sdim 4066252723Sdim Result = SubstituteAutoTransform(*this, DeducedType).Apply(Type); 4067252723Sdim if (Result.isNull()) 4068252723Sdim return DAR_FailedAlreadyDiagnosed; 4069235633Sdim 4070224145Sdim // Check that the deduced argument type is compatible with the original 4071224145Sdim // argument type per C++ [temp.deduct.call]p4. 4072252723Sdim if (!InitList && !Result.isNull() && 4073252723Sdim CheckOriginalCallArgDeduction(*this, 4074224145Sdim Sema::OriginalCallArg(FuncParam,0,InitType), 4075252723Sdim Result)) { 4076252723Sdim Result = QualType(); 4077235633Sdim return DAR_Failed; 4078224145Sdim } 4079218893Sdim 4080235633Sdim return DAR_Succeeded; 4081198092Srdivacky} 4082198092Srdivacky 4083263509SdimQualType Sema::SubstAutoType(QualType TypeWithAuto, 4084263509Sdim QualType TypeToReplaceAuto) { 4085263509Sdim return SubstituteAutoTransform(*this, TypeToReplaceAuto). 4086263509Sdim TransformType(TypeWithAuto); 4087252723Sdim} 4088252723Sdim 4089263509SdimTypeSourceInfo* Sema::SubstAutoTypeSourceInfo(TypeSourceInfo *TypeWithAuto, 4090263509Sdim QualType TypeToReplaceAuto) { 4091263509Sdim return SubstituteAutoTransform(*this, TypeToReplaceAuto). 4092263509Sdim TransformType(TypeWithAuto); 4093263509Sdim} 4094263509Sdim 4095235633Sdimvoid Sema::DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init) { 4096235633Sdim if (isa<InitListExpr>(Init)) 4097235633Sdim Diag(VDecl->getLocation(), 4098263509Sdim VDecl->isInitCapture() 4099263509Sdim ? diag::err_init_capture_deduction_failure_from_init_list 4100263509Sdim : diag::err_auto_var_deduction_failure_from_init_list) 4101235633Sdim << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange(); 4102235633Sdim else 4103263509Sdim Diag(VDecl->getLocation(), 4104263509Sdim VDecl->isInitCapture() ? diag::err_init_capture_deduction_failure 4105263509Sdim : diag::err_auto_var_deduction_failure) 4106235633Sdim << VDecl->getDeclName() << VDecl->getType() << Init->getType() 4107235633Sdim << Init->getSourceRange(); 4108235633Sdim} 4109235633Sdim 4110252723Sdimbool Sema::DeduceReturnType(FunctionDecl *FD, SourceLocation Loc, 4111252723Sdim bool Diagnose) { 4112252723Sdim assert(FD->getResultType()->isUndeducedType()); 4113252723Sdim 4114252723Sdim if (FD->getTemplateInstantiationPattern()) 4115252723Sdim InstantiateFunctionDefinition(Loc, FD); 4116252723Sdim 4117252723Sdim bool StillUndeduced = FD->getResultType()->isUndeducedType(); 4118252723Sdim if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) { 4119252723Sdim Diag(Loc, diag::err_auto_fn_used_before_defined) << FD; 4120252723Sdim Diag(FD->getLocation(), diag::note_callee_decl) << FD; 4121252723Sdim } 4122252723Sdim 4123252723Sdim return StillUndeduced; 4124252723Sdim} 4125252723Sdim 4126198092Srdivackystatic void 4127235633SdimMarkUsedTemplateParameters(ASTContext &Ctx, QualType T, 4128198092Srdivacky bool OnlyDeduced, 4129198893Srdivacky unsigned Level, 4130235633Sdim llvm::SmallBitVector &Deduced); 4131218893Sdim 4132218893Sdim/// \brief If this is a non-static member function, 4133263509Sdimstatic void 4134263509SdimAddImplicitObjectParameterType(ASTContext &Context, 4135263509Sdim CXXMethodDecl *Method, 4136263509Sdim SmallVectorImpl<QualType> &ArgTypes) { 4137245431Sdim // C++11 [temp.func.order]p3: 4138245431Sdim // [...] The new parameter is of type "reference to cv A," where cv are 4139245431Sdim // the cv-qualifiers of the function template (if any) and A is 4140245431Sdim // the class of which the function template is a member. 4141218893Sdim // 4142245431Sdim // The standard doesn't say explicitly, but we pick the appropriate kind of 4143245431Sdim // reference type based on [over.match.funcs]p4. 4144218893Sdim QualType ArgTy = Context.getTypeDeclType(Method->getParent()); 4145218893Sdim ArgTy = Context.getQualifiedType(ArgTy, 4146218893Sdim Qualifiers::fromCVRMask(Method->getTypeQualifiers())); 4147245431Sdim if (Method->getRefQualifier() == RQ_RValue) 4148245431Sdim ArgTy = Context.getRValueReferenceType(ArgTy); 4149245431Sdim else 4150245431Sdim ArgTy = Context.getLValueReferenceType(ArgTy); 4151218893Sdim ArgTypes.push_back(ArgTy); 4152218893Sdim} 4153218893Sdim 4154198092Srdivacky/// \brief Determine whether the function template \p FT1 is at least as 4155198092Srdivacky/// specialized as \p FT2. 4156198092Srdivackystatic bool isAtLeastAsSpecializedAs(Sema &S, 4157203955Srdivacky SourceLocation Loc, 4158198092Srdivacky FunctionTemplateDecl *FT1, 4159198092Srdivacky FunctionTemplateDecl *FT2, 4160198092Srdivacky TemplatePartialOrderingContext TPOC, 4161263509Sdim unsigned NumCallArguments1, 4162226890Sdim SmallVectorImpl<RefParamPartialOrderingComparison> *RefParamComparisons) { 4163198092Srdivacky FunctionDecl *FD1 = FT1->getTemplatedDecl(); 4164218893Sdim FunctionDecl *FD2 = FT2->getTemplatedDecl(); 4165198092Srdivacky const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 4166198092Srdivacky const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 4167218893Sdim 4168198092Srdivacky assert(Proto1 && Proto2 && "Function templates must have prototypes"); 4169198092Srdivacky TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 4170226890Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 4171198092Srdivacky Deduced.resize(TemplateParams->size()); 4172198092Srdivacky 4173198092Srdivacky // C++0x [temp.deduct.partial]p3: 4174198092Srdivacky // The types used to determine the ordering depend on the context in which 4175198092Srdivacky // the partial ordering is done: 4176245431Sdim TemplateDeductionInfo Info(Loc); 4177263509Sdim SmallVector<QualType, 4> Args2; 4178198092Srdivacky switch (TPOC) { 4179198092Srdivacky case TPOC_Call: { 4180198092Srdivacky // - In the context of a function call, the function parameter types are 4181198092Srdivacky // used. 4182263509Sdim CXXMethodDecl *Method1 = dyn_cast<CXXMethodDecl>(FD1); 4183263509Sdim CXXMethodDecl *Method2 = dyn_cast<CXXMethodDecl>(FD2); 4184218893Sdim 4185245431Sdim // C++11 [temp.func.order]p3: 4186218893Sdim // [...] If only one of the function templates is a non-static 4187218893Sdim // member, that function template is considered to have a new 4188218893Sdim // first parameter inserted in its function parameter list. The 4189218893Sdim // new parameter is of type "reference to cv A," where cv are 4190218893Sdim // the cv-qualifiers of the function template (if any) and A is 4191218893Sdim // the class of which the function template is a member. 4192218893Sdim // 4193245431Sdim // Note that we interpret this to mean "if one of the function 4194245431Sdim // templates is a non-static member and the other is a non-member"; 4195245431Sdim // otherwise, the ordering rules for static functions against non-static 4196245431Sdim // functions don't make any sense. 4197245431Sdim // 4198218893Sdim // C++98/03 doesn't have this provision, so instead we drop the 4199245431Sdim // first argument of the free function, which seems to match 4200245431Sdim // existing practice. 4201226890Sdim SmallVector<QualType, 4> Args1; 4202263509Sdim 4203263509Sdim unsigned Skip1 = 0, Skip2 = 0; 4204263509Sdim unsigned NumComparedArguments = NumCallArguments1; 4205263509Sdim 4206263509Sdim if (!Method2 && Method1 && !Method1->isStatic()) { 4207263509Sdim if (S.getLangOpts().CPlusPlus11) { 4208263509Sdim // Compare 'this' from Method1 against first parameter from Method2. 4209263509Sdim AddImplicitObjectParameterType(S.Context, Method1, Args1); 4210263509Sdim ++NumComparedArguments; 4211263509Sdim } else 4212263509Sdim // Ignore first parameter from Method2. 4213263509Sdim ++Skip2; 4214263509Sdim } else if (!Method1 && Method2 && !Method2->isStatic()) { 4215263509Sdim if (S.getLangOpts().CPlusPlus11) 4216263509Sdim // Compare 'this' from Method2 against first parameter from Method1. 4217263509Sdim AddImplicitObjectParameterType(S.Context, Method2, Args2); 4218263509Sdim else 4219263509Sdim // Ignore first parameter from Method1. 4220263509Sdim ++Skip1; 4221263509Sdim } 4222263509Sdim 4223218893Sdim Args1.insert(Args1.end(), 4224218893Sdim Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end()); 4225218893Sdim Args2.insert(Args2.end(), 4226218893Sdim Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end()); 4227218893Sdim 4228218893Sdim // C++ [temp.func.order]p5: 4229218893Sdim // The presence of unused ellipsis and default arguments has no effect on 4230218893Sdim // the partial ordering of function templates. 4231263509Sdim if (Args1.size() > NumComparedArguments) 4232263509Sdim Args1.resize(NumComparedArguments); 4233263509Sdim if (Args2.size() > NumComparedArguments) 4234263509Sdim Args2.resize(NumComparedArguments); 4235218893Sdim if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(), 4236218893Sdim Args1.data(), Args1.size(), Info, Deduced, 4237218893Sdim TDF_None, /*PartialOrdering=*/true, 4238218893Sdim RefParamComparisons)) 4239198092Srdivacky return false; 4240218893Sdim 4241198092Srdivacky break; 4242195099Sed } 4243218893Sdim 4244198092Srdivacky case TPOC_Conversion: 4245198092Srdivacky // - In the context of a call to a conversion operator, the return types 4246198092Srdivacky // of the conversion function templates are used. 4247235633Sdim if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 4248235633Sdim Proto2->getResultType(), 4249235633Sdim Proto1->getResultType(), 4250235633Sdim Info, Deduced, TDF_None, 4251235633Sdim /*PartialOrdering=*/true, 4252235633Sdim RefParamComparisons)) 4253198092Srdivacky return false; 4254198092Srdivacky break; 4255218893Sdim 4256198092Srdivacky case TPOC_Other: 4257218893Sdim // - In other contexts (14.6.6.2) the function template's function type 4258198092Srdivacky // is used. 4259235633Sdim if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 4260235633Sdim FD2->getType(), FD1->getType(), 4261235633Sdim Info, Deduced, TDF_None, 4262235633Sdim /*PartialOrdering=*/true, 4263235633Sdim RefParamComparisons)) 4264198092Srdivacky return false; 4265198092Srdivacky break; 4266198092Srdivacky } 4267218893Sdim 4268198092Srdivacky // C++0x [temp.deduct.partial]p11: 4269218893Sdim // In most cases, all template parameters must have values in order for 4270218893Sdim // deduction to succeed, but for partial ordering purposes a template 4271218893Sdim // parameter may remain without a value provided it is not used in the 4272198092Srdivacky // types being used for partial ordering. [ Note: a template parameter used 4273198092Srdivacky // in a non-deduced context is considered used. -end note] 4274198092Srdivacky unsigned ArgIdx = 0, NumArgs = Deduced.size(); 4275198092Srdivacky for (; ArgIdx != NumArgs; ++ArgIdx) 4276198092Srdivacky if (Deduced[ArgIdx].isNull()) 4277198092Srdivacky break; 4278198092Srdivacky 4279198092Srdivacky if (ArgIdx == NumArgs) { 4280218893Sdim // All template arguments were deduced. FT1 is at least as specialized 4281198092Srdivacky // as FT2. 4282198092Srdivacky return true; 4283198092Srdivacky } 4284198092Srdivacky 4285198092Srdivacky // Figure out which template parameters were used. 4286235633Sdim llvm::SmallBitVector UsedParameters(TemplateParams->size()); 4287198092Srdivacky switch (TPOC) { 4288263509Sdim case TPOC_Call: 4289263509Sdim for (unsigned I = 0, N = Args2.size(); I != N; ++I) 4290263509Sdim ::MarkUsedTemplateParameters(S.Context, Args2[I], false, 4291198893Srdivacky TemplateParams->getDepth(), 4292198092Srdivacky UsedParameters); 4293198092Srdivacky break; 4294218893Sdim 4295198092Srdivacky case TPOC_Conversion: 4296235633Sdim ::MarkUsedTemplateParameters(S.Context, Proto2->getResultType(), false, 4297198893Srdivacky TemplateParams->getDepth(), 4298198092Srdivacky UsedParameters); 4299198092Srdivacky break; 4300218893Sdim 4301198092Srdivacky case TPOC_Other: 4302235633Sdim ::MarkUsedTemplateParameters(S.Context, FD2->getType(), false, 4303198893Srdivacky TemplateParams->getDepth(), 4304198893Srdivacky UsedParameters); 4305198092Srdivacky break; 4306194179Sed } 4307218893Sdim 4308198092Srdivacky for (; ArgIdx != NumArgs; ++ArgIdx) 4309198092Srdivacky // If this argument had no value deduced but was used in one of the types 4310198092Srdivacky // used for partial ordering, then deduction fails. 4311198092Srdivacky if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 4312198092Srdivacky return false; 4313218893Sdim 4314198092Srdivacky return true; 4315198092Srdivacky} 4316218893Sdim 4317218893Sdim/// \brief Determine whether this a function template whose parameter-type-list 4318218893Sdim/// ends with a function parameter pack. 4319218893Sdimstatic bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) { 4320218893Sdim FunctionDecl *Function = FunTmpl->getTemplatedDecl(); 4321218893Sdim unsigned NumParams = Function->getNumParams(); 4322218893Sdim if (NumParams == 0) 4323218893Sdim return false; 4324218893Sdim 4325218893Sdim ParmVarDecl *Last = Function->getParamDecl(NumParams - 1); 4326218893Sdim if (!Last->isParameterPack()) 4327218893Sdim return false; 4328218893Sdim 4329218893Sdim // Make sure that no previous parameter is a parameter pack. 4330218893Sdim while (--NumParams > 0) { 4331218893Sdim if (Function->getParamDecl(NumParams - 1)->isParameterPack()) 4332218893Sdim return false; 4333218893Sdim } 4334218893Sdim 4335218893Sdim return true; 4336218893Sdim} 4337218893Sdim 4338198092Srdivacky/// \brief Returns the more specialized function template according 4339198092Srdivacky/// to the rules of function template partial ordering (C++ [temp.func.order]). 4340198092Srdivacky/// 4341198092Srdivacky/// \param FT1 the first function template 4342198092Srdivacky/// 4343198092Srdivacky/// \param FT2 the second function template 4344198092Srdivacky/// 4345198092Srdivacky/// \param TPOC the context in which we are performing partial ordering of 4346198092Srdivacky/// function templates. 4347198092Srdivacky/// 4348263509Sdim/// \param NumCallArguments1 The number of arguments in the call to FT1, used 4349263509Sdim/// only when \c TPOC is \c TPOC_Call. 4350218893Sdim/// 4351263509Sdim/// \param NumCallArguments2 The number of arguments in the call to FT2, used 4352263509Sdim/// only when \c TPOC is \c TPOC_Call. 4353263509Sdim/// 4354198092Srdivacky/// \returns the more specialized function template. If neither 4355198092Srdivacky/// template is more specialized, returns NULL. 4356198092SrdivackyFunctionTemplateDecl * 4357198092SrdivackySema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, 4358198092Srdivacky FunctionTemplateDecl *FT2, 4359203955Srdivacky SourceLocation Loc, 4360218893Sdim TemplatePartialOrderingContext TPOC, 4361263509Sdim unsigned NumCallArguments1, 4362263509Sdim unsigned NumCallArguments2) { 4363226890Sdim SmallVector<RefParamPartialOrderingComparison, 4> RefParamComparisons; 4364218893Sdim bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC, 4365263509Sdim NumCallArguments1, 0); 4366218893Sdim bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC, 4367263509Sdim NumCallArguments2, 4368218893Sdim &RefParamComparisons); 4369218893Sdim 4370198092Srdivacky if (Better1 != Better2) // We have a clear winner 4371198092Srdivacky return Better1? FT1 : FT2; 4372218893Sdim 4373198092Srdivacky if (!Better1 && !Better2) // Neither is better than the other 4374198092Srdivacky return 0; 4375195341Sed 4376198092Srdivacky // C++0x [temp.deduct.partial]p10: 4377218893Sdim // If for each type being considered a given template is at least as 4378198092Srdivacky // specialized for all types and more specialized for some set of types and 4379218893Sdim // the other template is not more specialized for any types or is not at 4380198092Srdivacky // least as specialized for any types, then the given template is more 4381198092Srdivacky // specialized than the other template. Otherwise, neither template is more 4382198092Srdivacky // specialized than the other. 4383198092Srdivacky Better1 = false; 4384198092Srdivacky Better2 = false; 4385218893Sdim for (unsigned I = 0, N = RefParamComparisons.size(); I != N; ++I) { 4386198092Srdivacky // C++0x [temp.deduct.partial]p9: 4387198092Srdivacky // If, for a given type, deduction succeeds in both directions (i.e., the 4388218893Sdim // types are identical after the transformations above) and both P and A 4389218893Sdim // were reference types (before being replaced with the type referred to 4390218893Sdim // above): 4391218893Sdim 4392218893Sdim // -- if the type from the argument template was an lvalue reference 4393218893Sdim // and the type from the parameter template was not, the argument 4394218893Sdim // type is considered to be more specialized than the other; 4395218893Sdim // otherwise, 4396218893Sdim if (!RefParamComparisons[I].ArgIsRvalueRef && 4397218893Sdim RefParamComparisons[I].ParamIsRvalueRef) { 4398218893Sdim Better2 = true; 4399218893Sdim if (Better1) 4400218893Sdim return 0; 4401218893Sdim continue; 4402218893Sdim } else if (!RefParamComparisons[I].ParamIsRvalueRef && 4403218893Sdim RefParamComparisons[I].ArgIsRvalueRef) { 4404218893Sdim Better1 = true; 4405218893Sdim if (Better2) 4406218893Sdim return 0; 4407218893Sdim continue; 4408198092Srdivacky } 4409218893Sdim 4410218893Sdim // -- if the type from the argument template is more cv-qualified than 4411218893Sdim // the type from the parameter template (as described above), the 4412218893Sdim // argument type is considered to be more specialized than the 4413218893Sdim // other; otherwise, 4414218893Sdim switch (RefParamComparisons[I].Qualifiers) { 4415218893Sdim case NeitherMoreQualified: 4416218893Sdim break; 4417218893Sdim 4418218893Sdim case ParamMoreQualified: 4419218893Sdim Better1 = true; 4420218893Sdim if (Better2) 4421218893Sdim return 0; 4422218893Sdim continue; 4423218893Sdim 4424218893Sdim case ArgMoreQualified: 4425218893Sdim Better2 = true; 4426218893Sdim if (Better1) 4427218893Sdim return 0; 4428218893Sdim continue; 4429218893Sdim } 4430218893Sdim 4431218893Sdim // -- neither type is more specialized than the other. 4432195341Sed } 4433218893Sdim 4434198092Srdivacky assert(!(Better1 && Better2) && "Should have broken out in the loop above"); 4435198092Srdivacky if (Better1) 4436198092Srdivacky return FT1; 4437198092Srdivacky else if (Better2) 4438198092Srdivacky return FT2; 4439218893Sdim 4440218893Sdim // FIXME: This mimics what GCC implements, but doesn't match up with the 4441218893Sdim // proposed resolution for core issue 692. This area needs to be sorted out, 4442218893Sdim // but for now we attempt to maintain compatibility. 4443218893Sdim bool Variadic1 = isVariadicFunctionTemplate(FT1); 4444218893Sdim bool Variadic2 = isVariadicFunctionTemplate(FT2); 4445218893Sdim if (Variadic1 != Variadic2) 4446218893Sdim return Variadic1? FT2 : FT1; 4447218893Sdim 4448218893Sdim return 0; 4449198092Srdivacky} 4450198092Srdivacky 4451198092Srdivacky/// \brief Determine if the two templates are equivalent. 4452198092Srdivackystatic bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) { 4453198092Srdivacky if (T1 == T2) 4454198092Srdivacky return true; 4455218893Sdim 4456198092Srdivacky if (!T1 || !T2) 4457198092Srdivacky return false; 4458218893Sdim 4459198092Srdivacky return T1->getCanonicalDecl() == T2->getCanonicalDecl(); 4460193576Sed} 4461194179Sed 4462198092Srdivacky/// \brief Retrieve the most specialized of the given function template 4463198092Srdivacky/// specializations. 4464198092Srdivacky/// 4465203955Srdivacky/// \param SpecBegin the start iterator of the function template 4466203955Srdivacky/// specializations that we will be comparing. 4467198092Srdivacky/// 4468203955Srdivacky/// \param SpecEnd the end iterator of the function template 4469203955Srdivacky/// specializations, paired with \p SpecBegin. 4470198092Srdivacky/// 4471218893Sdim/// \param Loc the location where the ambiguity or no-specializations 4472198092Srdivacky/// diagnostic should occur. 4473198092Srdivacky/// 4474198092Srdivacky/// \param NoneDiag partial diagnostic used to diagnose cases where there are 4475198092Srdivacky/// no matching candidates. 4476198092Srdivacky/// 4477198092Srdivacky/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one 4478198092Srdivacky/// occurs. 4479198092Srdivacky/// 4480198092Srdivacky/// \param CandidateDiag partial diagnostic used for each function template 4481198092Srdivacky/// specialization that is a candidate in the ambiguous ordering. One parameter 4482198092Srdivacky/// in this diagnostic should be unbound, which will correspond to the string 4483198092Srdivacky/// describing the template arguments for the function template specialization. 4484198092Srdivacky/// 4485218893Sdim/// \returns the most specialized function template specialization, if 4486203955Srdivacky/// found. Otherwise, returns SpecEnd. 4487263509SdimUnresolvedSetIterator Sema::getMostSpecialized( 4488263509Sdim UnresolvedSetIterator SpecBegin, UnresolvedSetIterator SpecEnd, 4489263509Sdim TemplateSpecCandidateSet &FailedCandidates, 4490263509Sdim SourceLocation Loc, const PartialDiagnostic &NoneDiag, 4491263509Sdim const PartialDiagnostic &AmbigDiag, const PartialDiagnostic &CandidateDiag, 4492263509Sdim bool Complain, QualType TargetType) { 4493203955Srdivacky if (SpecBegin == SpecEnd) { 4494263509Sdim if (Complain) { 4495218893Sdim Diag(Loc, NoneDiag); 4496263509Sdim FailedCandidates.NoteCandidates(*this, Loc); 4497263509Sdim } 4498203955Srdivacky return SpecEnd; 4499198092Srdivacky } 4500218893Sdim 4501218893Sdim if (SpecBegin + 1 == SpecEnd) 4502203955Srdivacky return SpecBegin; 4503218893Sdim 4504198092Srdivacky // Find the function template that is better than all of the templates it 4505198092Srdivacky // has been compared to. 4506203955Srdivacky UnresolvedSetIterator Best = SpecBegin; 4507218893Sdim FunctionTemplateDecl *BestTemplate 4508203955Srdivacky = cast<FunctionDecl>(*Best)->getPrimaryTemplate(); 4509198092Srdivacky assert(BestTemplate && "Not a function template specialization?"); 4510203955Srdivacky for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) { 4511203955Srdivacky FunctionTemplateDecl *Challenger 4512203955Srdivacky = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 4513198092Srdivacky assert(Challenger && "Not a function template specialization?"); 4514203955Srdivacky if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 4515263509Sdim Loc, TPOC_Other, 0, 0), 4516198092Srdivacky Challenger)) { 4517198092Srdivacky Best = I; 4518198092Srdivacky BestTemplate = Challenger; 4519198092Srdivacky } 4520198092Srdivacky } 4521218893Sdim 4522198092Srdivacky // Make sure that the "best" function template is more specialized than all 4523198092Srdivacky // of the others. 4524198092Srdivacky bool Ambiguous = false; 4525203955Srdivacky for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 4526203955Srdivacky FunctionTemplateDecl *Challenger 4527203955Srdivacky = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 4528198092Srdivacky if (I != Best && 4529218893Sdim !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 4530263509Sdim Loc, TPOC_Other, 0, 0), 4531198092Srdivacky BestTemplate)) { 4532198092Srdivacky Ambiguous = true; 4533198092Srdivacky break; 4534198092Srdivacky } 4535198092Srdivacky } 4536218893Sdim 4537198092Srdivacky if (!Ambiguous) { 4538198092Srdivacky // We found an answer. Return it. 4539203955Srdivacky return Best; 4540198092Srdivacky } 4541218893Sdim 4542198092Srdivacky // Diagnose the ambiguity. 4543252723Sdim if (Complain) { 4544218893Sdim Diag(Loc, AmbigDiag); 4545218893Sdim 4546252723Sdim // FIXME: Can we order the candidates in some sane way? 4547235633Sdim for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 4548235633Sdim PartialDiagnostic PD = CandidateDiag; 4549235633Sdim PD << getTemplateArgumentBindingsText( 4550218893Sdim cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(), 4551203955Srdivacky *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs()); 4552235633Sdim if (!TargetType.isNull()) 4553235633Sdim HandleFunctionTypeMismatch(PD, cast<FunctionDecl>(*I)->getType(), 4554235633Sdim TargetType); 4555235633Sdim Diag((*I)->getLocation(), PD); 4556235633Sdim } 4557252723Sdim } 4558218893Sdim 4559203955Srdivacky return SpecEnd; 4560198092Srdivacky} 4561194179Sed 4562198092Srdivacky/// \brief Returns the more specialized class template partial specialization 4563198092Srdivacky/// according to the rules of partial ordering of class template partial 4564198092Srdivacky/// specializations (C++ [temp.class.order]). 4565198092Srdivacky/// 4566198092Srdivacky/// \param PS1 the first class template partial specialization 4567198092Srdivacky/// 4568198092Srdivacky/// \param PS2 the second class template partial specialization 4569198092Srdivacky/// 4570198092Srdivacky/// \returns the more specialized class template partial specialization. If 4571198092Srdivacky/// neither partial specialization is more specialized, returns NULL. 4572198092SrdivackyClassTemplatePartialSpecializationDecl * 4573198092SrdivackySema::getMoreSpecializedPartialSpecialization( 4574198092Srdivacky ClassTemplatePartialSpecializationDecl *PS1, 4575203955Srdivacky ClassTemplatePartialSpecializationDecl *PS2, 4576203955Srdivacky SourceLocation Loc) { 4577198092Srdivacky // C++ [temp.class.order]p1: 4578198092Srdivacky // For two class template partial specializations, the first is at least as 4579218893Sdim // specialized as the second if, given the following rewrite to two 4580218893Sdim // function templates, the first function template is at least as 4581218893Sdim // specialized as the second according to the ordering rules for function 4582198092Srdivacky // templates (14.6.6.2): 4583198092Srdivacky // - the first function template has the same template parameters as the 4584218893Sdim // first partial specialization and has a single function parameter 4585218893Sdim // whose type is a class template specialization with the template 4586198092Srdivacky // arguments of the first partial specialization, and 4587198092Srdivacky // - the second function template has the same template parameters as the 4588218893Sdim // second partial specialization and has a single function parameter 4589218893Sdim // whose type is a class template specialization with the template 4590198092Srdivacky // arguments of the second partial specialization. 4591198092Srdivacky // 4592207619Srdivacky // Rather than synthesize function templates, we merely perform the 4593207619Srdivacky // equivalent partial ordering by performing deduction directly on 4594207619Srdivacky // the template arguments of the class template partial 4595207619Srdivacky // specializations. This computation is slightly simpler than the 4596207619Srdivacky // general problem of function template partial ordering, because 4597207619Srdivacky // class template partial specializations are more constrained. We 4598207619Srdivacky // know that every template parameter is deducible from the class 4599207619Srdivacky // template partial specialization's template arguments, for 4600207619Srdivacky // example. 4601226890Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 4602245431Sdim TemplateDeductionInfo Info(Loc); 4603207619Srdivacky 4604207619Srdivacky QualType PT1 = PS1->getInjectedSpecializationType(); 4605207619Srdivacky QualType PT2 = PS2->getInjectedSpecializationType(); 4606218893Sdim 4607198092Srdivacky // Determine whether PS1 is at least as specialized as PS2 4608198092Srdivacky Deduced.resize(PS2->getTemplateParameters()->size()); 4609235633Sdim bool Better1 = !DeduceTemplateArgumentsByTypeMatch(*this, 4610235633Sdim PS2->getTemplateParameters(), 4611218893Sdim PT2, PT1, Info, Deduced, TDF_None, 4612218893Sdim /*PartialOrdering=*/true, 4613218893Sdim /*RefParamComparisons=*/0); 4614218893Sdim if (Better1) { 4615245431Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end()); 4616263509Sdim InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2, DeducedArgs, 4617263509Sdim Info); 4618263509Sdim Better1 = !::FinishTemplateArgumentDeduction( 4619263509Sdim *this, PS2, PS1->getTemplateArgs(), Deduced, Info); 4620263509Sdim } 4621263509Sdim 4622263509Sdim // Determine whether PS2 is at least as specialized as PS1 4623263509Sdim Deduced.clear(); 4624263509Sdim Deduced.resize(PS1->getTemplateParameters()->size()); 4625263509Sdim bool Better2 = !DeduceTemplateArgumentsByTypeMatch( 4626263509Sdim *this, PS1->getTemplateParameters(), PT1, PT2, Info, Deduced, TDF_None, 4627263509Sdim /*PartialOrdering=*/true, 4628263509Sdim /*RefParamComparisons=*/0); 4629263509Sdim if (Better2) { 4630263509Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), 4631263509Sdim Deduced.end()); 4632263509Sdim InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1, DeducedArgs, 4633263509Sdim Info); 4634263509Sdim Better2 = !::FinishTemplateArgumentDeduction( 4635263509Sdim *this, PS1, PS2->getTemplateArgs(), Deduced, Info); 4636263509Sdim } 4637263509Sdim 4638263509Sdim if (Better1 == Better2) 4639263509Sdim return 0; 4640263509Sdim 4641263509Sdim return Better1 ? PS1 : PS2; 4642263509Sdim} 4643263509Sdim 4644263509Sdim/// TODO: Unify with ClassTemplatePartialSpecializationDecl version? 4645263509Sdim/// May require unifying ClassTemplate(Partial)SpecializationDecl and 4646263509Sdim/// VarTemplate(Partial)SpecializationDecl with a new data 4647263509Sdim/// structure Template(Partial)SpecializationDecl, and 4648263509Sdim/// using Template(Partial)SpecializationDecl as input type. 4649263509SdimVarTemplatePartialSpecializationDecl * 4650263509SdimSema::getMoreSpecializedPartialSpecialization( 4651263509Sdim VarTemplatePartialSpecializationDecl *PS1, 4652263509Sdim VarTemplatePartialSpecializationDecl *PS2, SourceLocation Loc) { 4653263509Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 4654263509Sdim TemplateDeductionInfo Info(Loc); 4655263509Sdim 4656263509Sdim assert(PS1->getSpecializedTemplate() == PS1->getSpecializedTemplate() && 4657263509Sdim "the partial specializations being compared should specialize" 4658263509Sdim " the same template."); 4659263509Sdim TemplateName Name(PS1->getSpecializedTemplate()); 4660263509Sdim TemplateName CanonTemplate = Context.getCanonicalTemplateName(Name); 4661263509Sdim QualType PT1 = Context.getTemplateSpecializationType( 4662263509Sdim CanonTemplate, PS1->getTemplateArgs().data(), 4663263509Sdim PS1->getTemplateArgs().size()); 4664263509Sdim QualType PT2 = Context.getTemplateSpecializationType( 4665263509Sdim CanonTemplate, PS2->getTemplateArgs().data(), 4666263509Sdim PS2->getTemplateArgs().size()); 4667263509Sdim 4668263509Sdim // Determine whether PS1 is at least as specialized as PS2 4669263509Sdim Deduced.resize(PS2->getTemplateParameters()->size()); 4670263509Sdim bool Better1 = !DeduceTemplateArgumentsByTypeMatch( 4671263509Sdim *this, PS2->getTemplateParameters(), PT2, PT1, Info, Deduced, TDF_None, 4672263509Sdim /*PartialOrdering=*/true, 4673263509Sdim /*RefParamComparisons=*/0); 4674263509Sdim if (Better1) { 4675263509Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), 4676263509Sdim Deduced.end()); 4677218893Sdim InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2, 4678245431Sdim DeducedArgs, Info); 4679218893Sdim Better1 = !::FinishTemplateArgumentDeduction(*this, PS2, 4680218893Sdim PS1->getTemplateArgs(), 4681207619Srdivacky Deduced, Info); 4682218893Sdim } 4683218893Sdim 4684198092Srdivacky // Determine whether PS2 is at least as specialized as PS1 4685199482Srdivacky Deduced.clear(); 4686198092Srdivacky Deduced.resize(PS1->getTemplateParameters()->size()); 4687235633Sdim bool Better2 = !DeduceTemplateArgumentsByTypeMatch(*this, 4688235633Sdim PS1->getTemplateParameters(), 4689218893Sdim PT1, PT2, Info, Deduced, TDF_None, 4690218893Sdim /*PartialOrdering=*/true, 4691218893Sdim /*RefParamComparisons=*/0); 4692218893Sdim if (Better2) { 4693245431Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end()); 4694218893Sdim InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1, 4695245431Sdim DeducedArgs, Info); 4696218893Sdim Better2 = !::FinishTemplateArgumentDeduction(*this, PS1, 4697218893Sdim PS2->getTemplateArgs(), 4698207619Srdivacky Deduced, Info); 4699218893Sdim } 4700218893Sdim 4701198092Srdivacky if (Better1 == Better2) 4702198092Srdivacky return 0; 4703218893Sdim 4704198092Srdivacky return Better1? PS1 : PS2; 4705198092Srdivacky} 4706198092Srdivacky 4707198092Srdivackystatic void 4708235633SdimMarkUsedTemplateParameters(ASTContext &Ctx, 4709198092Srdivacky const TemplateArgument &TemplateArg, 4710198092Srdivacky bool OnlyDeduced, 4711198893Srdivacky unsigned Depth, 4712235633Sdim llvm::SmallBitVector &Used); 4713198092Srdivacky 4714198092Srdivacky/// \brief Mark the template parameters that are used by the given 4715194179Sed/// expression. 4716198092Srdivackystatic void 4717235633SdimMarkUsedTemplateParameters(ASTContext &Ctx, 4718198092Srdivacky const Expr *E, 4719198092Srdivacky bool OnlyDeduced, 4720198893Srdivacky unsigned Depth, 4721235633Sdim llvm::SmallBitVector &Used) { 4722218893Sdim // We can deduce from a pack expansion. 4723218893Sdim if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E)) 4724218893Sdim E = Expansion->getPattern(); 4725218893Sdim 4726245431Sdim // Skip through any implicit casts we added while type-checking, and any 4727245431Sdim // substitutions performed by template alias expansion. 4728245431Sdim while (1) { 4729245431Sdim if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E)) 4730245431Sdim E = ICE->getSubExpr(); 4731245431Sdim else if (const SubstNonTypeTemplateParmExpr *Subst = 4732245431Sdim dyn_cast<SubstNonTypeTemplateParmExpr>(E)) 4733245431Sdim E = Subst->getReplacement(); 4734245431Sdim else 4735245431Sdim break; 4736245431Sdim } 4737218893Sdim 4738218893Sdim // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to 4739198092Srdivacky // find other occurrences of template parameters. 4740194613Sed const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E); 4741202379Srdivacky if (!DRE) 4742194179Sed return; 4743194179Sed 4744198092Srdivacky const NonTypeTemplateParmDecl *NTTP 4745194179Sed = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 4746194179Sed if (!NTTP) 4747194179Sed return; 4748194179Sed 4749198893Srdivacky if (NTTP->getDepth() == Depth) 4750198893Srdivacky Used[NTTP->getIndex()] = true; 4751194179Sed} 4752194179Sed 4753198092Srdivacky/// \brief Mark the template parameters that are used by the given 4754198092Srdivacky/// nested name specifier. 4755198092Srdivackystatic void 4756235633SdimMarkUsedTemplateParameters(ASTContext &Ctx, 4757198092Srdivacky NestedNameSpecifier *NNS, 4758198092Srdivacky bool OnlyDeduced, 4759198893Srdivacky unsigned Depth, 4760235633Sdim llvm::SmallBitVector &Used) { 4761198092Srdivacky if (!NNS) 4762198092Srdivacky return; 4763218893Sdim 4764235633Sdim MarkUsedTemplateParameters(Ctx, NNS->getPrefix(), OnlyDeduced, Depth, 4765198893Srdivacky Used); 4766235633Sdim MarkUsedTemplateParameters(Ctx, QualType(NNS->getAsType(), 0), 4767198893Srdivacky OnlyDeduced, Depth, Used); 4768198092Srdivacky} 4769218893Sdim 4770198092Srdivacky/// \brief Mark the template parameters that are used by the given 4771198092Srdivacky/// template name. 4772198092Srdivackystatic void 4773235633SdimMarkUsedTemplateParameters(ASTContext &Ctx, 4774198092Srdivacky TemplateName Name, 4775198092Srdivacky bool OnlyDeduced, 4776198893Srdivacky unsigned Depth, 4777235633Sdim llvm::SmallBitVector &Used) { 4778198092Srdivacky if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 4779198092Srdivacky if (TemplateTemplateParmDecl *TTP 4780198893Srdivacky = dyn_cast<TemplateTemplateParmDecl>(Template)) { 4781198893Srdivacky if (TTP->getDepth() == Depth) 4782198893Srdivacky Used[TTP->getIndex()] = true; 4783198893Srdivacky } 4784198092Srdivacky return; 4785198092Srdivacky } 4786218893Sdim 4787199482Srdivacky if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) 4788235633Sdim MarkUsedTemplateParameters(Ctx, QTN->getQualifier(), OnlyDeduced, 4789199482Srdivacky Depth, Used); 4790198092Srdivacky if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 4791235633Sdim MarkUsedTemplateParameters(Ctx, DTN->getQualifier(), OnlyDeduced, 4792198893Srdivacky Depth, Used); 4793198092Srdivacky} 4794198092Srdivacky 4795198092Srdivacky/// \brief Mark the template parameters that are used by the given 4796194179Sed/// type. 4797198092Srdivackystatic void 4798235633SdimMarkUsedTemplateParameters(ASTContext &Ctx, QualType T, 4799198092Srdivacky bool OnlyDeduced, 4800198893Srdivacky unsigned Depth, 4801235633Sdim llvm::SmallBitVector &Used) { 4802198092Srdivacky if (T.isNull()) 4803198092Srdivacky return; 4804218893Sdim 4805194179Sed // Non-dependent types have nothing deducible 4806194179Sed if (!T->isDependentType()) 4807194179Sed return; 4808194179Sed 4809235633Sdim T = Ctx.getCanonicalType(T); 4810194179Sed switch (T->getTypeClass()) { 4811194179Sed case Type::Pointer: 4812235633Sdim MarkUsedTemplateParameters(Ctx, 4813198092Srdivacky cast<PointerType>(T)->getPointeeType(), 4814198092Srdivacky OnlyDeduced, 4815198893Srdivacky Depth, 4816198092Srdivacky Used); 4817194179Sed break; 4818194179Sed 4819194179Sed case Type::BlockPointer: 4820235633Sdim MarkUsedTemplateParameters(Ctx, 4821198092Srdivacky cast<BlockPointerType>(T)->getPointeeType(), 4822198092Srdivacky OnlyDeduced, 4823198893Srdivacky Depth, 4824198092Srdivacky Used); 4825194179Sed break; 4826194179Sed 4827194179Sed case Type::LValueReference: 4828194179Sed case Type::RValueReference: 4829235633Sdim MarkUsedTemplateParameters(Ctx, 4830198092Srdivacky cast<ReferenceType>(T)->getPointeeType(), 4831198092Srdivacky OnlyDeduced, 4832198893Srdivacky Depth, 4833198092Srdivacky Used); 4834194179Sed break; 4835194179Sed 4836194179Sed case Type::MemberPointer: { 4837194179Sed const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 4838235633Sdim MarkUsedTemplateParameters(Ctx, MemPtr->getPointeeType(), OnlyDeduced, 4839198893Srdivacky Depth, Used); 4840235633Sdim MarkUsedTemplateParameters(Ctx, QualType(MemPtr->getClass(), 0), 4841198893Srdivacky OnlyDeduced, Depth, Used); 4842194179Sed break; 4843194179Sed } 4844194179Sed 4845194179Sed case Type::DependentSizedArray: 4846235633Sdim MarkUsedTemplateParameters(Ctx, 4847198092Srdivacky cast<DependentSizedArrayType>(T)->getSizeExpr(), 4848198893Srdivacky OnlyDeduced, Depth, Used); 4849194179Sed // Fall through to check the element type 4850194179Sed 4851194179Sed case Type::ConstantArray: 4852194179Sed case Type::IncompleteArray: 4853235633Sdim MarkUsedTemplateParameters(Ctx, 4854198092Srdivacky cast<ArrayType>(T)->getElementType(), 4855198893Srdivacky OnlyDeduced, Depth, Used); 4856194179Sed break; 4857194179Sed 4858194179Sed case Type::Vector: 4859194179Sed case Type::ExtVector: 4860235633Sdim MarkUsedTemplateParameters(Ctx, 4861198092Srdivacky cast<VectorType>(T)->getElementType(), 4862198893Srdivacky OnlyDeduced, Depth, Used); 4863194179Sed break; 4864194179Sed 4865194613Sed case Type::DependentSizedExtVector: { 4866194613Sed const DependentSizedExtVectorType *VecType 4867194613Sed = cast<DependentSizedExtVectorType>(T); 4868235633Sdim MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced, 4869198893Srdivacky Depth, Used); 4870235633Sdim MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced, 4871198893Srdivacky Depth, Used); 4872194613Sed break; 4873194613Sed } 4874194613Sed 4875194179Sed case Type::FunctionProto: { 4876194613Sed const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 4877235633Sdim MarkUsedTemplateParameters(Ctx, Proto->getResultType(), OnlyDeduced, 4878198893Srdivacky Depth, Used); 4879194179Sed for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I) 4880235633Sdim MarkUsedTemplateParameters(Ctx, Proto->getArgType(I), OnlyDeduced, 4881198893Srdivacky Depth, Used); 4882194179Sed break; 4883194179Sed } 4884194179Sed 4885198893Srdivacky case Type::TemplateTypeParm: { 4886198893Srdivacky const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T); 4887198893Srdivacky if (TTP->getDepth() == Depth) 4888198893Srdivacky Used[TTP->getIndex()] = true; 4889194179Sed break; 4890198893Srdivacky } 4891194179Sed 4892218893Sdim case Type::SubstTemplateTypeParmPack: { 4893218893Sdim const SubstTemplateTypeParmPackType *Subst 4894218893Sdim = cast<SubstTemplateTypeParmPackType>(T); 4895235633Sdim MarkUsedTemplateParameters(Ctx, 4896218893Sdim QualType(Subst->getReplacedParameter(), 0), 4897218893Sdim OnlyDeduced, Depth, Used); 4898235633Sdim MarkUsedTemplateParameters(Ctx, Subst->getArgumentPack(), 4899218893Sdim OnlyDeduced, Depth, Used); 4900218893Sdim break; 4901218893Sdim } 4902218893Sdim 4903207619Srdivacky case Type::InjectedClassName: 4904207619Srdivacky T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType(); 4905207619Srdivacky // fall through 4906207619Srdivacky 4907194179Sed case Type::TemplateSpecialization: { 4908198092Srdivacky const TemplateSpecializationType *Spec 4909194613Sed = cast<TemplateSpecializationType>(T); 4910235633Sdim MarkUsedTemplateParameters(Ctx, Spec->getTemplateName(), OnlyDeduced, 4911198893Srdivacky Depth, Used); 4912218893Sdim 4913218893Sdim // C++0x [temp.deduct.type]p9: 4914218893Sdim // If the template argument list of P contains a pack expansion that is not 4915218893Sdim // the last template argument, the entire template argument list is a 4916218893Sdim // non-deduced context. 4917218893Sdim if (OnlyDeduced && 4918218893Sdim hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 4919218893Sdim break; 4920218893Sdim 4921198092Srdivacky for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 4922235633Sdim MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth, 4923198893Srdivacky Used); 4924194179Sed break; 4925194179Sed } 4926194179Sed 4927198092Srdivacky case Type::Complex: 4928198092Srdivacky if (!OnlyDeduced) 4929235633Sdim MarkUsedTemplateParameters(Ctx, 4930198092Srdivacky cast<ComplexType>(T)->getElementType(), 4931198893Srdivacky OnlyDeduced, Depth, Used); 4932198092Srdivacky break; 4933198092Srdivacky 4934226890Sdim case Type::Atomic: 4935226890Sdim if (!OnlyDeduced) 4936235633Sdim MarkUsedTemplateParameters(Ctx, 4937226890Sdim cast<AtomicType>(T)->getValueType(), 4938226890Sdim OnlyDeduced, Depth, Used); 4939226890Sdim break; 4940226890Sdim 4941206084Srdivacky case Type::DependentName: 4942198092Srdivacky if (!OnlyDeduced) 4943235633Sdim MarkUsedTemplateParameters(Ctx, 4944206084Srdivacky cast<DependentNameType>(T)->getQualifier(), 4945198893Srdivacky OnlyDeduced, Depth, Used); 4946198092Srdivacky break; 4947198092Srdivacky 4948210299Sed case Type::DependentTemplateSpecialization: { 4949210299Sed const DependentTemplateSpecializationType *Spec 4950210299Sed = cast<DependentTemplateSpecializationType>(T); 4951210299Sed if (!OnlyDeduced) 4952235633Sdim MarkUsedTemplateParameters(Ctx, Spec->getQualifier(), 4953210299Sed OnlyDeduced, Depth, Used); 4954218893Sdim 4955218893Sdim // C++0x [temp.deduct.type]p9: 4956218893Sdim // If the template argument list of P contains a pack expansion that is not 4957218893Sdim // the last template argument, the entire template argument list is a 4958218893Sdim // non-deduced context. 4959218893Sdim if (OnlyDeduced && 4960218893Sdim hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 4961218893Sdim break; 4962218893Sdim 4963210299Sed for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 4964235633Sdim MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth, 4965210299Sed Used); 4966210299Sed break; 4967210299Sed } 4968210299Sed 4969204643Srdivacky case Type::TypeOf: 4970204643Srdivacky if (!OnlyDeduced) 4971235633Sdim MarkUsedTemplateParameters(Ctx, 4972204643Srdivacky cast<TypeOfType>(T)->getUnderlyingType(), 4973204643Srdivacky OnlyDeduced, Depth, Used); 4974204643Srdivacky break; 4975204643Srdivacky 4976204643Srdivacky case Type::TypeOfExpr: 4977204643Srdivacky if (!OnlyDeduced) 4978235633Sdim MarkUsedTemplateParameters(Ctx, 4979204643Srdivacky cast<TypeOfExprType>(T)->getUnderlyingExpr(), 4980204643Srdivacky OnlyDeduced, Depth, Used); 4981204643Srdivacky break; 4982204643Srdivacky 4983204643Srdivacky case Type::Decltype: 4984204643Srdivacky if (!OnlyDeduced) 4985235633Sdim MarkUsedTemplateParameters(Ctx, 4986204643Srdivacky cast<DecltypeType>(T)->getUnderlyingExpr(), 4987204643Srdivacky OnlyDeduced, Depth, Used); 4988204643Srdivacky break; 4989204643Srdivacky 4990223017Sdim case Type::UnaryTransform: 4991223017Sdim if (!OnlyDeduced) 4992235633Sdim MarkUsedTemplateParameters(Ctx, 4993223017Sdim cast<UnaryTransformType>(T)->getUnderlyingType(), 4994223017Sdim OnlyDeduced, Depth, Used); 4995223017Sdim break; 4996223017Sdim 4997218893Sdim case Type::PackExpansion: 4998235633Sdim MarkUsedTemplateParameters(Ctx, 4999218893Sdim cast<PackExpansionType>(T)->getPattern(), 5000218893Sdim OnlyDeduced, Depth, Used); 5001218893Sdim break; 5002218893Sdim 5003218893Sdim case Type::Auto: 5004235633Sdim MarkUsedTemplateParameters(Ctx, 5005218893Sdim cast<AutoType>(T)->getDeducedType(), 5006218893Sdim OnlyDeduced, Depth, Used); 5007218893Sdim 5008198092Srdivacky // None of these types have any template parameters in them. 5009194179Sed case Type::Builtin: 5010194179Sed case Type::VariableArray: 5011194179Sed case Type::FunctionNoProto: 5012194179Sed case Type::Record: 5013194179Sed case Type::Enum: 5014194179Sed case Type::ObjCInterface: 5015208600Srdivacky case Type::ObjCObject: 5016194613Sed case Type::ObjCObjectPointer: 5017200583Srdivacky case Type::UnresolvedUsing: 5018194179Sed#define TYPE(Class, Base) 5019194179Sed#define ABSTRACT_TYPE(Class, Base) 5020194179Sed#define DEPENDENT_TYPE(Class, Base) 5021194179Sed#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 5022194179Sed#include "clang/AST/TypeNodes.def" 5023194179Sed break; 5024194179Sed } 5025194179Sed} 5026194179Sed 5027198092Srdivacky/// \brief Mark the template parameters that are used by this 5028194179Sed/// template argument. 5029198092Srdivackystatic void 5030235633SdimMarkUsedTemplateParameters(ASTContext &Ctx, 5031198092Srdivacky const TemplateArgument &TemplateArg, 5032198092Srdivacky bool OnlyDeduced, 5033198893Srdivacky unsigned Depth, 5034235633Sdim llvm::SmallBitVector &Used) { 5035194179Sed switch (TemplateArg.getKind()) { 5036194179Sed case TemplateArgument::Null: 5037194179Sed case TemplateArgument::Integral: 5038235633Sdim case TemplateArgument::Declaration: 5039194179Sed break; 5040198092Srdivacky 5041245431Sdim case TemplateArgument::NullPtr: 5042245431Sdim MarkUsedTemplateParameters(Ctx, TemplateArg.getNullPtrType(), OnlyDeduced, 5043245431Sdim Depth, Used); 5044245431Sdim break; 5045245431Sdim 5046194179Sed case TemplateArgument::Type: 5047235633Sdim MarkUsedTemplateParameters(Ctx, TemplateArg.getAsType(), OnlyDeduced, 5048198893Srdivacky Depth, Used); 5049194179Sed break; 5050194179Sed 5051199482Srdivacky case TemplateArgument::Template: 5052218893Sdim case TemplateArgument::TemplateExpansion: 5053235633Sdim MarkUsedTemplateParameters(Ctx, 5054218893Sdim TemplateArg.getAsTemplateOrTemplatePattern(), 5055199482Srdivacky OnlyDeduced, Depth, Used); 5056194179Sed break; 5057194179Sed 5058194179Sed case TemplateArgument::Expression: 5059235633Sdim MarkUsedTemplateParameters(Ctx, TemplateArg.getAsExpr(), OnlyDeduced, 5060198893Srdivacky Depth, Used); 5061194179Sed break; 5062218893Sdim 5063194613Sed case TemplateArgument::Pack: 5064198092Srdivacky for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(), 5065198092Srdivacky PEnd = TemplateArg.pack_end(); 5066198092Srdivacky P != PEnd; ++P) 5067235633Sdim MarkUsedTemplateParameters(Ctx, *P, OnlyDeduced, Depth, Used); 5068194613Sed break; 5069194179Sed } 5070194179Sed} 5071194179Sed 5072245431Sdim/// \brief Mark which template parameters can be deduced from a given 5073194179Sed/// template argument list. 5074194179Sed/// 5075194179Sed/// \param TemplateArgs the template argument list from which template 5076194179Sed/// parameters will be deduced. 5077194179Sed/// 5078245431Sdim/// \param Used a bit vector whose elements will be set to \c true 5079194179Sed/// to indicate when the corresponding template parameter will be 5080194179Sed/// deduced. 5081198092Srdivackyvoid 5082198092SrdivackySema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 5083198893Srdivacky bool OnlyDeduced, unsigned Depth, 5084235633Sdim llvm::SmallBitVector &Used) { 5085218893Sdim // C++0x [temp.deduct.type]p9: 5086218893Sdim // If the template argument list of P contains a pack expansion that is not 5087218893Sdim // the last template argument, the entire template argument list is a 5088218893Sdim // non-deduced context. 5089218893Sdim if (OnlyDeduced && 5090218893Sdim hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size())) 5091218893Sdim return; 5092218893Sdim 5093194179Sed for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 5094235633Sdim ::MarkUsedTemplateParameters(Context, TemplateArgs[I], OnlyDeduced, 5095198893Srdivacky Depth, Used); 5096194179Sed} 5097198092Srdivacky 5098198092Srdivacky/// \brief Marks all of the template parameters that will be deduced by a 5099198092Srdivacky/// call to the given function template. 5100218893Sdimvoid 5101235633SdimSema::MarkDeducedTemplateParameters(ASTContext &Ctx, 5102252723Sdim const FunctionTemplateDecl *FunctionTemplate, 5103235633Sdim llvm::SmallBitVector &Deduced) { 5104218893Sdim TemplateParameterList *TemplateParams 5105198092Srdivacky = FunctionTemplate->getTemplateParameters(); 5106198092Srdivacky Deduced.clear(); 5107198092Srdivacky Deduced.resize(TemplateParams->size()); 5108218893Sdim 5109198092Srdivacky FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 5110198092Srdivacky for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 5111235633Sdim ::MarkUsedTemplateParameters(Ctx, Function->getParamDecl(I)->getType(), 5112198893Srdivacky true, TemplateParams->getDepth(), Deduced); 5113198092Srdivacky} 5114224145Sdim 5115224145Sdimbool hasDeducibleTemplateParameters(Sema &S, 5116224145Sdim FunctionTemplateDecl *FunctionTemplate, 5117224145Sdim QualType T) { 5118224145Sdim if (!T->isDependentType()) 5119224145Sdim return false; 5120224145Sdim 5121224145Sdim TemplateParameterList *TemplateParams 5122224145Sdim = FunctionTemplate->getTemplateParameters(); 5123235633Sdim llvm::SmallBitVector Deduced(TemplateParams->size()); 5124235633Sdim ::MarkUsedTemplateParameters(S.Context, T, true, TemplateParams->getDepth(), 5125224145Sdim Deduced); 5126224145Sdim 5127235633Sdim return Deduced.any(); 5128224145Sdim} 5129