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" 14249423Sdim#include "TreeTransform.h" 15193576Sed#include "clang/AST/ASTContext.h" 16212904Sdim#include "clang/AST/DeclObjC.h" 17193576Sed#include "clang/AST/DeclTemplate.h" 18193576Sed#include "clang/AST/Expr.h" 19193576Sed#include "clang/AST/ExprCXX.h" 20249423Sdim#include "clang/AST/StmtVisitor.h" 21249423Sdim#include "clang/Sema/DeclSpec.h" 22249423Sdim#include "clang/Sema/Sema.h" 23249423Sdim#include "clang/Sema/Template.h" 24234353Sdim#include "llvm/ADT/SmallBitVector.h" 25198092Srdivacky#include <algorithm> 26195099Sed 27195099Sednamespace clang { 28212904Sdim using namespace sema; 29212904Sdim 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 55251662Sdim TDF_TopLevelParameterTypeList = 0x10, 56251662Sdim /// \brief Within template argument deduction from overload resolution per 57251662Sdim /// C++ [over.over] allow matching function types that are compatible in 58251662Sdim /// terms of noreturn and default calling convention adjustments. 59251662Sdim 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, 92226633Sdim 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 119234353SdimDeduceTemplateArgumentsByTypeMatch(Sema &S, 120234353Sdim TemplateParameterList *TemplateParams, 121234353Sdim QualType Param, 122234353Sdim QualType Arg, 123234353Sdim TemplateDeductionInfo &Info, 124234353Sdim SmallVectorImpl<DeducedTemplateArgument> & 125234353Sdim Deduced, 126234353Sdim unsigned TDF, 127234353Sdim bool PartialOrdering = false, 128234353Sdim 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, 137249423Sdim 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) { 143239462Sdim // If we are within an alias template, the expression may have undergone 144239462Sdim // any number of parameter substitutions already. 145239462Sdim while (1) { 146239462Sdim if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E)) 147239462Sdim E = IC->getSubExpr(); 148239462Sdim else if (SubstNonTypeTemplateParmExpr *Subst = 149239462Sdim dyn_cast<SubstNonTypeTemplateParmExpr>(E)) 150239462Sdim E = Subst->getReplacement(); 151239462Sdim else 152239462Sdim break; 153239462Sdim } 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 && 205239462Sdim 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 && 265243830Sdim isSameDeclaration(X.getAsDecl(), Y.getAsDecl()) && 266243830Sdim X.isDeclForReferenceParam() == Y.isDeclForReferenceParam()) 267218893Sdim return X; 268218893Sdim 269218893Sdim // All other combinations are incompatible. 270218893Sdim return DeducedTemplateArgument(); 271218893Sdim 272243830Sdim case TemplateArgument::NullPtr: 273243830Sdim // If we deduced a null pointer and a dependent expression, keep the 274243830Sdim // null pointer. 275243830Sdim if (Y.getKind() == TemplateArgument::Expression) 276243830Sdim return X; 277243830Sdim 278243830Sdim // If we deduced a null pointer and an integral constant, keep the 279243830Sdim // integral constant. 280243830Sdim if (Y.getKind() == TemplateArgument::Integral) 281243830Sdim return Y; 282243830Sdim 283243830Sdim // If we deduced two null pointers, make sure they have the same type. 284243830Sdim if (Y.getKind() == TemplateArgument::NullPtr && 285243830Sdim Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType())) 286243830Sdim return X; 287243830Sdim 288243830Sdim // All other combinations are incompatible. 289243830Sdim return DeducedTemplateArgument(); 290243830Sdim 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 310234353Sdim 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, 321226633Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 322198092Srdivacky assert(NTTP->getDepth() == 0 && 323193576Sed "Cannot deduce non-type template argument with depth > 0"); 324198092Srdivacky 325239462Sdim DeducedTemplateArgument NewDeduced(S.Context, Value, ValueType, 326239462Sdim 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, 350226633Sdim 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, 378199482Srdivacky NonTypeTemplateParmDecl *NTTP, 379243830Sdim ValueDecl *D, 380212904Sdim TemplateDeductionInfo &Info, 381226633Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 382199482Srdivacky assert(NTTP->getDepth() == 0 && 383199482Srdivacky "Cannot deduce non-type template argument with depth > 0"); 384218893Sdim 385243830Sdim D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : 0; 386243830Sdim TemplateArgument New(D, NTTP->getType()->isReferenceType()); 387243830Sdim 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, 408226633Sdim 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, 467226633Sdim 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(), 488249423Sdim 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); 495249423Sdim if (!RecordArg) { 496249423Sdim Info.FirstArg = TemplateArgument(QualType(Param, 0)); 497249423Sdim Info.SecondArg = TemplateArgument(Arg); 498198092Srdivacky return Sema::TDK_NonDeducedMismatch; 499249423Sdim } 500198092Srdivacky 501198092Srdivacky ClassTemplateSpecializationDecl *SpecArg 502198092Srdivacky = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl()); 503249423Sdim if (!SpecArg) { 504249423Sdim Info.FirstArg = TemplateArgument(QualType(Param, 0)); 505249423Sdim Info.SecondArg = TemplateArgument(Arg); 506198092Srdivacky return Sema::TDK_NonDeducedMismatch; 507249423Sdim } 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); 578218893Sdim else if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) 579218893Sdim return TemplateParameter(NTTP); 580218893Sdim 581218893Sdim return TemplateParameter(cast<TemplateTemplateParmDecl>(D)); 582218893Sdim} 583218893Sdim 584218893Sdim/// \brief Prepare to perform template argument deduction for all of the 585218893Sdim/// arguments in a set of argument packs. 586218893Sdimstatic void PrepareArgumentPackDeduction(Sema &S, 587226633Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 588234353Sdim ArrayRef<unsigned> PackIndices, 589226633Sdim SmallVectorImpl<DeducedTemplateArgument> &SavedPacks, 590226633Sdim SmallVectorImpl< 591226633Sdim SmallVector<DeducedTemplateArgument, 4> > &NewlyDeducedPacks) { 592218893Sdim // Save the deduced template arguments for each parameter pack expanded 593218893Sdim // by this pack expansion, then clear out the deduction. 594218893Sdim for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 595218893Sdim // Save the previously-deduced argument pack, then clear it out so that we 596218893Sdim // can deduce a new argument pack. 597218893Sdim SavedPacks[I] = Deduced[PackIndices[I]]; 598218893Sdim Deduced[PackIndices[I]] = TemplateArgument(); 599218893Sdim 600243830Sdim if (!S.CurrentInstantiationScope) 601243830Sdim continue; 602243830Sdim 603243830Sdim // If the template argument pack was explicitly specified, add that to 604218893Sdim // the set of deduced arguments. 605218893Sdim const TemplateArgument *ExplicitArgs; 606218893Sdim unsigned NumExplicitArgs; 607218893Sdim if (NamedDecl *PartiallySubstitutedPack 608218893Sdim = S.CurrentInstantiationScope->getPartiallySubstitutedPack( 609218893Sdim &ExplicitArgs, 610218893Sdim &NumExplicitArgs)) { 611218893Sdim if (getDepthAndIndex(PartiallySubstitutedPack).second == PackIndices[I]) 612218893Sdim NewlyDeducedPacks[I].append(ExplicitArgs, 613218893Sdim ExplicitArgs + NumExplicitArgs); 614218893Sdim } 615218893Sdim } 616218893Sdim} 617218893Sdim 618218893Sdim/// \brief Finish template argument deduction for a set of argument packs, 619218893Sdim/// producing the argument packs and checking for consistency with prior 620218893Sdim/// deductions. 621218893Sdimstatic Sema::TemplateDeductionResult 622218893SdimFinishArgumentPackDeduction(Sema &S, 623218893Sdim TemplateParameterList *TemplateParams, 624218893Sdim bool HasAnyArguments, 625226633Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 626234353Sdim ArrayRef<unsigned> PackIndices, 627226633Sdim SmallVectorImpl<DeducedTemplateArgument> &SavedPacks, 628226633Sdim SmallVectorImpl< 629226633Sdim SmallVector<DeducedTemplateArgument, 4> > &NewlyDeducedPacks, 630218893Sdim TemplateDeductionInfo &Info) { 631218893Sdim // Build argument packs for each of the parameter packs expanded by this 632218893Sdim // pack expansion. 633218893Sdim for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 634218893Sdim if (HasAnyArguments && NewlyDeducedPacks[I].empty()) { 635218893Sdim // We were not able to deduce anything for this parameter pack, 636218893Sdim // so just restore the saved argument pack. 637218893Sdim Deduced[PackIndices[I]] = SavedPacks[I]; 638218893Sdim continue; 639218893Sdim } 640218893Sdim 641218893Sdim DeducedTemplateArgument NewPack; 642218893Sdim 643218893Sdim if (NewlyDeducedPacks[I].empty()) { 644218893Sdim // If we deduced an empty argument pack, create it now. 645243830Sdim NewPack = DeducedTemplateArgument(TemplateArgument::getEmptyPack()); 646218893Sdim } else { 647218893Sdim TemplateArgument *ArgumentPack 648218893Sdim = new (S.Context) TemplateArgument [NewlyDeducedPacks[I].size()]; 649218893Sdim std::copy(NewlyDeducedPacks[I].begin(), NewlyDeducedPacks[I].end(), 650218893Sdim ArgumentPack); 651218893Sdim NewPack 652218893Sdim = DeducedTemplateArgument(TemplateArgument(ArgumentPack, 653218893Sdim NewlyDeducedPacks[I].size()), 654218893Sdim NewlyDeducedPacks[I][0].wasDeducedFromArrayBound()); 655218893Sdim } 656218893Sdim 657218893Sdim DeducedTemplateArgument Result 658218893Sdim = checkDeducedTemplateArguments(S.Context, SavedPacks[I], NewPack); 659218893Sdim if (Result.isNull()) { 660218893Sdim Info.Param 661218893Sdim = makeTemplateParameter(TemplateParams->getParam(PackIndices[I])); 662218893Sdim Info.FirstArg = SavedPacks[I]; 663218893Sdim Info.SecondArg = NewPack; 664218893Sdim return Sema::TDK_Inconsistent; 665218893Sdim } 666218893Sdim 667218893Sdim Deduced[PackIndices[I]] = Result; 668218893Sdim } 669218893Sdim 670218893Sdim return Sema::TDK_Success; 671218893Sdim} 672218893Sdim 673218893Sdim/// \brief Deduce the template arguments by comparing the list of parameter 674218893Sdim/// types to the list of argument types, as in the parameter-type-lists of 675218893Sdim/// function types (C++ [temp.deduct.type]p10). 676218893Sdim/// 677218893Sdim/// \param S The semantic analysis object within which we are deducing 678218893Sdim/// 679218893Sdim/// \param TemplateParams The template parameters that we are deducing 680218893Sdim/// 681218893Sdim/// \param Params The list of parameter types 682218893Sdim/// 683218893Sdim/// \param NumParams The number of types in \c Params 684218893Sdim/// 685218893Sdim/// \param Args The list of argument types 686218893Sdim/// 687218893Sdim/// \param NumArgs The number of types in \c Args 688218893Sdim/// 689218893Sdim/// \param Info information about the template argument deduction itself 690218893Sdim/// 691218893Sdim/// \param Deduced the deduced template arguments 692218893Sdim/// 693218893Sdim/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe 694218893Sdim/// how template argument deduction is performed. 695218893Sdim/// 696218893Sdim/// \param PartialOrdering If true, we are performing template argument 697218893Sdim/// deduction for during partial ordering for a call 698218893Sdim/// (C++0x [temp.deduct.partial]). 699218893Sdim/// 700218893Sdim/// \param RefParamComparisons If we're performing template argument deduction 701218893Sdim/// in the context of partial ordering, the set of qualifier comparisons. 702218893Sdim/// 703218893Sdim/// \returns the result of template argument deduction so far. Note that a 704218893Sdim/// "success" result means that template argument deduction has not yet failed, 705218893Sdim/// but it may still fail, later, for other reasons. 706218893Sdimstatic Sema::TemplateDeductionResult 707218893SdimDeduceTemplateArguments(Sema &S, 708218893Sdim TemplateParameterList *TemplateParams, 709218893Sdim const QualType *Params, unsigned NumParams, 710218893Sdim const QualType *Args, unsigned NumArgs, 711218893Sdim TemplateDeductionInfo &Info, 712226633Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 713218893Sdim unsigned TDF, 714218893Sdim bool PartialOrdering = false, 715226633Sdim SmallVectorImpl<RefParamPartialOrderingComparison> * 716218893Sdim RefParamComparisons = 0) { 717218893Sdim // Fast-path check to see if we have too many/too few arguments. 718218893Sdim if (NumParams != NumArgs && 719218893Sdim !(NumParams && isa<PackExpansionType>(Params[NumParams - 1])) && 720218893Sdim !(NumArgs && isa<PackExpansionType>(Args[NumArgs - 1]))) 721249423Sdim return Sema::TDK_MiscellaneousDeductionFailure; 722218893Sdim 723218893Sdim // C++0x [temp.deduct.type]p10: 724218893Sdim // Similarly, if P has a form that contains (T), then each parameter type 725218893Sdim // Pi of the respective parameter-type- list of P is compared with the 726218893Sdim // corresponding parameter type Ai of the corresponding parameter-type-list 727218893Sdim // of A. [...] 728218893Sdim unsigned ArgIdx = 0, ParamIdx = 0; 729218893Sdim for (; ParamIdx != NumParams; ++ParamIdx) { 730218893Sdim // Check argument types. 731218893Sdim const PackExpansionType *Expansion 732218893Sdim = dyn_cast<PackExpansionType>(Params[ParamIdx]); 733218893Sdim if (!Expansion) { 734218893Sdim // Simple case: compare the parameter and argument types at this point. 735218893Sdim 736218893Sdim // Make sure we have an argument. 737218893Sdim if (ArgIdx >= NumArgs) 738249423Sdim return Sema::TDK_MiscellaneousDeductionFailure; 739218893Sdim 740218893Sdim if (isa<PackExpansionType>(Args[ArgIdx])) { 741218893Sdim // C++0x [temp.deduct.type]p22: 742218893Sdim // If the original function parameter associated with A is a function 743218893Sdim // parameter pack and the function parameter associated with P is not 744218893Sdim // a function parameter pack, then template argument deduction fails. 745249423Sdim return Sema::TDK_MiscellaneousDeductionFailure; 746218893Sdim } 747218893Sdim 748218893Sdim if (Sema::TemplateDeductionResult Result 749234353Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 750234353Sdim Params[ParamIdx], Args[ArgIdx], 751234353Sdim Info, Deduced, TDF, 752234353Sdim PartialOrdering, 753234353Sdim RefParamComparisons)) 754218893Sdim return Result; 755218893Sdim 756218893Sdim ++ArgIdx; 757218893Sdim continue; 758218893Sdim } 759218893Sdim 760218893Sdim // C++0x [temp.deduct.type]p5: 761218893Sdim // The non-deduced contexts are: 762218893Sdim // - A function parameter pack that does not occur at the end of the 763218893Sdim // parameter-declaration-clause. 764218893Sdim if (ParamIdx + 1 < NumParams) 765218893Sdim return Sema::TDK_Success; 766218893Sdim 767218893Sdim // C++0x [temp.deduct.type]p10: 768218893Sdim // If the parameter-declaration corresponding to Pi is a function 769218893Sdim // parameter pack, then the type of its declarator- id is compared with 770218893Sdim // each remaining parameter type in the parameter-type-list of A. Each 771218893Sdim // comparison deduces template arguments for subsequent positions in the 772218893Sdim // template parameter packs expanded by the function parameter pack. 773218893Sdim 774218893Sdim // Compute the set of template parameter indices that correspond to 775218893Sdim // parameter packs expanded by the pack expansion. 776226633Sdim SmallVector<unsigned, 2> PackIndices; 777218893Sdim QualType Pattern = Expansion->getPattern(); 778218893Sdim { 779234353Sdim llvm::SmallBitVector SawIndices(TemplateParams->size()); 780226633Sdim SmallVector<UnexpandedParameterPack, 2> Unexpanded; 781218893Sdim S.collectUnexpandedParameterPacks(Pattern, Unexpanded); 782218893Sdim for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) { 783218893Sdim unsigned Depth, Index; 784218893Sdim llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]); 785218893Sdim if (Depth == 0 && !SawIndices[Index]) { 786218893Sdim SawIndices[Index] = true; 787218893Sdim PackIndices.push_back(Index); 788218893Sdim } 789218893Sdim } 790218893Sdim } 791218893Sdim assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?"); 792218893Sdim 793218893Sdim // Keep track of the deduced template arguments for each parameter pack 794218893Sdim // expanded by this pack expansion (the outer index) and for each 795218893Sdim // template argument (the inner SmallVectors). 796226633Sdim SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2> 797218893Sdim NewlyDeducedPacks(PackIndices.size()); 798226633Sdim SmallVector<DeducedTemplateArgument, 2> 799218893Sdim SavedPacks(PackIndices.size()); 800218893Sdim PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks, 801218893Sdim NewlyDeducedPacks); 802218893Sdim 803218893Sdim bool HasAnyArguments = false; 804218893Sdim for (; ArgIdx < NumArgs; ++ArgIdx) { 805218893Sdim HasAnyArguments = true; 806218893Sdim 807218893Sdim // Deduce template arguments from the pattern. 808218893Sdim if (Sema::TemplateDeductionResult Result 809234353Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, Pattern, 810234353Sdim Args[ArgIdx], Info, Deduced, 811234353Sdim TDF, PartialOrdering, 812234353Sdim RefParamComparisons)) 813218893Sdim return Result; 814218893Sdim 815218893Sdim // Capture the deduced template arguments for each parameter pack expanded 816218893Sdim // by this pack expansion, add them to the list of arguments we've deduced 817218893Sdim // for that pack, then clear out the deduced argument. 818218893Sdim for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 819218893Sdim DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]]; 820218893Sdim if (!DeducedArg.isNull()) { 821218893Sdim NewlyDeducedPacks[I].push_back(DeducedArg); 822218893Sdim DeducedArg = DeducedTemplateArgument(); 823218893Sdim } 824218893Sdim } 825218893Sdim } 826218893Sdim 827218893Sdim // Build argument packs for each of the parameter packs expanded by this 828218893Sdim // pack expansion. 829218893Sdim if (Sema::TemplateDeductionResult Result 830218893Sdim = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments, 831218893Sdim Deduced, PackIndices, SavedPacks, 832218893Sdim NewlyDeducedPacks, Info)) 833218893Sdim return Result; 834218893Sdim } 835218893Sdim 836218893Sdim // Make sure we don't have any extra arguments. 837218893Sdim if (ArgIdx < NumArgs) 838249423Sdim return Sema::TDK_MiscellaneousDeductionFailure; 839218893Sdim 840218893Sdim return Sema::TDK_Success; 841218893Sdim} 842218893Sdim 843221345Sdim/// \brief Determine whether the parameter has qualifiers that are either 844221345Sdim/// inconsistent with or a superset of the argument's qualifiers. 845221345Sdimstatic bool hasInconsistentOrSupersetQualifiersOf(QualType ParamType, 846221345Sdim QualType ArgType) { 847221345Sdim Qualifiers ParamQs = ParamType.getQualifiers(); 848221345Sdim Qualifiers ArgQs = ArgType.getQualifiers(); 849221345Sdim 850221345Sdim if (ParamQs == ArgQs) 851221345Sdim return false; 852221345Sdim 853221345Sdim // Mismatched (but not missing) Objective-C GC attributes. 854221345Sdim if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() && 855221345Sdim ParamQs.hasObjCGCAttr()) 856221345Sdim return true; 857221345Sdim 858221345Sdim // Mismatched (but not missing) address spaces. 859221345Sdim if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() && 860221345Sdim ParamQs.hasAddressSpace()) 861221345Sdim return true; 862221345Sdim 863224145Sdim // Mismatched (but not missing) Objective-C lifetime qualifiers. 864224145Sdim if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() && 865224145Sdim ParamQs.hasObjCLifetime()) 866224145Sdim return true; 867224145Sdim 868221345Sdim // CVR qualifier superset. 869221345Sdim return (ParamQs.getCVRQualifiers() != ArgQs.getCVRQualifiers()) && 870221345Sdim ((ParamQs.getCVRQualifiers() | ArgQs.getCVRQualifiers()) 871221345Sdim == ParamQs.getCVRQualifiers()); 872221345Sdim} 873221345Sdim 874251662Sdim/// \brief Compare types for equality with respect to possibly compatible 875251662Sdim/// function types (noreturn adjustment, implicit calling conventions). If any 876251662Sdim/// of parameter and argument is not a function, just perform type comparison. 877251662Sdim/// 878251662Sdim/// \param Param the template parameter type. 879251662Sdim/// 880251662Sdim/// \param Arg the argument type. 881251662Sdimbool Sema::isSameOrCompatibleFunctionType(CanQualType Param, 882251662Sdim CanQualType Arg) { 883251662Sdim const FunctionType *ParamFunction = Param->getAs<FunctionType>(), 884251662Sdim *ArgFunction = Arg->getAs<FunctionType>(); 885251662Sdim 886251662Sdim // Just compare if not functions. 887251662Sdim if (!ParamFunction || !ArgFunction) 888251662Sdim return Param == Arg; 889251662Sdim 890251662Sdim // Noreturn adjustment. 891251662Sdim QualType AdjustedParam; 892251662Sdim if (IsNoReturnConversion(Param, Arg, AdjustedParam)) 893251662Sdim return Arg == Context.getCanonicalType(AdjustedParam); 894251662Sdim 895251662Sdim // FIXME: Compatible calling conventions. 896251662Sdim 897251662Sdim return Param == Arg; 898251662Sdim} 899251662Sdim 900195099Sed/// \brief Deduce the template arguments by comparing the parameter type and 901195099Sed/// the argument type (C++ [temp.deduct.type]). 902195099Sed/// 903203955Srdivacky/// \param S the semantic analysis object within which we are deducing 904195099Sed/// 905195099Sed/// \param TemplateParams the template parameters that we are deducing 906195099Sed/// 907195099Sed/// \param ParamIn the parameter type 908195099Sed/// 909195099Sed/// \param ArgIn the argument type 910195099Sed/// 911195099Sed/// \param Info information about the template argument deduction itself 912195099Sed/// 913195099Sed/// \param Deduced the deduced template arguments 914195099Sed/// 915195099Sed/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe 916198092Srdivacky/// how template argument deduction is performed. 917195099Sed/// 918218893Sdim/// \param PartialOrdering Whether we're performing template argument deduction 919218893Sdim/// in the context of partial ordering (C++0x [temp.deduct.partial]). 920218893Sdim/// 921218893Sdim/// \param RefParamComparisons If we're performing template argument deduction 922218893Sdim/// in the context of partial ordering, the set of qualifier comparisons. 923218893Sdim/// 924195099Sed/// \returns the result of template argument deduction so far. Note that a 925195099Sed/// "success" result means that template argument deduction has not yet failed, 926195099Sed/// but it may still fail, later, for other reasons. 927194179Sedstatic Sema::TemplateDeductionResult 928234353SdimDeduceTemplateArgumentsByTypeMatch(Sema &S, 929234353Sdim TemplateParameterList *TemplateParams, 930234353Sdim QualType ParamIn, QualType ArgIn, 931234353Sdim TemplateDeductionInfo &Info, 932234353Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 933234353Sdim unsigned TDF, 934234353Sdim bool PartialOrdering, 935234353Sdim SmallVectorImpl<RefParamPartialOrderingComparison> * 936234353Sdim RefParamComparisons) { 937193576Sed // We only want to look at the canonical types, since typedefs and 938193576Sed // sugar are not part of template argument deduction. 939203955Srdivacky QualType Param = S.Context.getCanonicalType(ParamIn); 940203955Srdivacky QualType Arg = S.Context.getCanonicalType(ArgIn); 941193576Sed 942218893Sdim // If the argument type is a pack expansion, look at its pattern. 943218893Sdim // This isn't explicitly called out 944218893Sdim if (const PackExpansionType *ArgExpansion 945218893Sdim = dyn_cast<PackExpansionType>(Arg)) 946218893Sdim Arg = ArgExpansion->getPattern(); 947218893Sdim 948218893Sdim if (PartialOrdering) { 949218893Sdim // C++0x [temp.deduct.partial]p5: 950218893Sdim // Before the partial ordering is done, certain transformations are 951218893Sdim // performed on the types used for partial ordering: 952218893Sdim // - If P is a reference type, P is replaced by the type referred to. 953218893Sdim const ReferenceType *ParamRef = Param->getAs<ReferenceType>(); 954218893Sdim if (ParamRef) 955218893Sdim Param = ParamRef->getPointeeType(); 956218893Sdim 957218893Sdim // - If A is a reference type, A is replaced by the type referred to. 958218893Sdim const ReferenceType *ArgRef = Arg->getAs<ReferenceType>(); 959218893Sdim if (ArgRef) 960218893Sdim Arg = ArgRef->getPointeeType(); 961218893Sdim 962218893Sdim if (RefParamComparisons && ParamRef && ArgRef) { 963218893Sdim // C++0x [temp.deduct.partial]p6: 964218893Sdim // If both P and A were reference types (before being replaced with the 965218893Sdim // type referred to above), determine which of the two types (if any) is 966218893Sdim // more cv-qualified than the other; otherwise the types are considered 967218893Sdim // to be equally cv-qualified for partial ordering purposes. The result 968218893Sdim // of this determination will be used below. 969218893Sdim // 970218893Sdim // We save this information for later, using it only when deduction 971218893Sdim // succeeds in both directions. 972218893Sdim RefParamPartialOrderingComparison Comparison; 973218893Sdim Comparison.ParamIsRvalueRef = ParamRef->getAs<RValueReferenceType>(); 974218893Sdim Comparison.ArgIsRvalueRef = ArgRef->getAs<RValueReferenceType>(); 975218893Sdim Comparison.Qualifiers = NeitherMoreQualified; 976221345Sdim 977221345Sdim Qualifiers ParamQuals = Param.getQualifiers(); 978221345Sdim Qualifiers ArgQuals = Arg.getQualifiers(); 979221345Sdim if (ParamQuals.isStrictSupersetOf(ArgQuals)) 980218893Sdim Comparison.Qualifiers = ParamMoreQualified; 981221345Sdim else if (ArgQuals.isStrictSupersetOf(ParamQuals)) 982218893Sdim Comparison.Qualifiers = ArgMoreQualified; 983218893Sdim RefParamComparisons->push_back(Comparison); 984218893Sdim } 985218893Sdim 986218893Sdim // C++0x [temp.deduct.partial]p7: 987218893Sdim // Remove any top-level cv-qualifiers: 988218893Sdim // - If P is a cv-qualified type, P is replaced by the cv-unqualified 989218893Sdim // version of P. 990218893Sdim Param = Param.getUnqualifiedType(); 991218893Sdim // - If A is a cv-qualified type, A is replaced by the cv-unqualified 992218893Sdim // version of A. 993218893Sdim Arg = Arg.getUnqualifiedType(); 994218893Sdim } else { 995218893Sdim // C++0x [temp.deduct.call]p4 bullet 1: 996218893Sdim // - If the original P is a reference type, the deduced A (i.e., the type 997218893Sdim // referred to by the reference) can be more cv-qualified than the 998218893Sdim // transformed A. 999218893Sdim if (TDF & TDF_ParamWithReferenceType) { 1000218893Sdim Qualifiers Quals; 1001218893Sdim QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals); 1002218893Sdim Quals.setCVRQualifiers(Quals.getCVRQualifiers() & 1003218893Sdim Arg.getCVRQualifiers()); 1004218893Sdim Param = S.Context.getQualifiedType(UnqualParam, Quals); 1005218893Sdim } 1006218893Sdim 1007218893Sdim if ((TDF & TDF_TopLevelParameterTypeList) && !Param->isFunctionType()) { 1008218893Sdim // C++0x [temp.deduct.type]p10: 1009218893Sdim // If P and A are function types that originated from deduction when 1010218893Sdim // taking the address of a function template (14.8.2.2) or when deducing 1011218893Sdim // template arguments from a function declaration (14.8.2.6) and Pi and 1012218893Sdim // Ai are parameters of the top-level parameter-type-list of P and A, 1013218893Sdim // respectively, Pi is adjusted if it is an rvalue reference to a 1014218893Sdim // cv-unqualified template parameter and Ai is an lvalue reference, in 1015218893Sdim // which case the type of Pi is changed to be the template parameter 1016218893Sdim // type (i.e., T&& is changed to simply T). [ Note: As a result, when 1017218893Sdim // Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be 1018218893Sdim // deduced as X&. - end note ] 1019218893Sdim TDF &= ~TDF_TopLevelParameterTypeList; 1020218893Sdim 1021218893Sdim if (const RValueReferenceType *ParamRef 1022218893Sdim = Param->getAs<RValueReferenceType>()) { 1023218893Sdim if (isa<TemplateTypeParmType>(ParamRef->getPointeeType()) && 1024218893Sdim !ParamRef->getPointeeType().getQualifiers()) 1025218893Sdim if (Arg->isLValueReferenceType()) 1026218893Sdim Param = ParamRef->getPointeeType(); 1027218893Sdim } 1028218893Sdim } 1029194179Sed } 1030198092Srdivacky 1031193576Sed // C++ [temp.deduct.type]p9: 1032198092Srdivacky // A template type argument T, a template template argument TT or a 1033198092Srdivacky // template non-type argument i can be deduced if P and A have one of 1034193576Sed // the following forms: 1035193576Sed // 1036193576Sed // T 1037193576Sed // cv-list T 1038198092Srdivacky if (const TemplateTypeParmType *TemplateTypeParm 1039198092Srdivacky = Param->getAs<TemplateTypeParmType>()) { 1040226633Sdim // Just skip any attempts to deduce from a placeholder type. 1041226633Sdim if (Arg->isPlaceholderType()) 1042226633Sdim return Sema::TDK_Success; 1043226633Sdim 1044194179Sed unsigned Index = TemplateTypeParm->getIndex(); 1045198092Srdivacky bool RecanonicalizeArg = false; 1046194179Sed 1047198092Srdivacky // If the argument type is an array type, move the qualifiers up to the 1048198092Srdivacky // top level, so they can be matched with the qualifiers on the parameter. 1049198092Srdivacky if (isa<ArrayType>(Arg)) { 1050198092Srdivacky Qualifiers Quals; 1051203955Srdivacky Arg = S.Context.getUnqualifiedArrayType(Arg, Quals); 1052198092Srdivacky if (Quals) { 1053203955Srdivacky Arg = S.Context.getQualifiedType(Arg, Quals); 1054198092Srdivacky RecanonicalizeArg = true; 1055198092Srdivacky } 1056198092Srdivacky } 1057198092Srdivacky 1058193576Sed // The argument type can not be less qualified than the parameter 1059193576Sed // type. 1060221345Sdim if (!(TDF & TDF_IgnoreQualifiers) && 1061221345Sdim hasInconsistentOrSupersetQualifiersOf(Param, Arg)) { 1062194179Sed Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 1063212904Sdim Info.FirstArg = TemplateArgument(Param); 1064198893Srdivacky Info.SecondArg = TemplateArgument(Arg); 1065212904Sdim return Sema::TDK_Underqualified; 1066194179Sed } 1067193576Sed 1068193576Sed assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0"); 1069203955Srdivacky assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function"); 1070198092Srdivacky QualType DeducedType = Arg; 1071218893Sdim 1072221345Sdim // Remove any qualifiers on the parameter from the deduced type. 1073221345Sdim // We checked the qualifiers for consistency above. 1074221345Sdim Qualifiers DeducedQs = DeducedType.getQualifiers(); 1075221345Sdim Qualifiers ParamQs = Param.getQualifiers(); 1076221345Sdim DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers()); 1077221345Sdim if (ParamQs.hasObjCGCAttr()) 1078221345Sdim DeducedQs.removeObjCGCAttr(); 1079221345Sdim if (ParamQs.hasAddressSpace()) 1080221345Sdim DeducedQs.removeAddressSpace(); 1081224145Sdim if (ParamQs.hasObjCLifetime()) 1082224145Sdim DeducedQs.removeObjCLifetime(); 1083224145Sdim 1084224145Sdim // Objective-C ARC: 1085226633Sdim // If template deduction would produce a lifetime qualifier on a type 1086226633Sdim // that is not a lifetime type, template argument deduction fails. 1087226633Sdim if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() && 1088226633Sdim !DeducedType->isDependentType()) { 1089226633Sdim Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 1090226633Sdim Info.FirstArg = TemplateArgument(Param); 1091226633Sdim Info.SecondArg = TemplateArgument(Arg); 1092226633Sdim return Sema::TDK_Underqualified; 1093226633Sdim } 1094226633Sdim 1095226633Sdim // Objective-C ARC: 1096224145Sdim // If template deduction would produce an argument type with lifetime type 1097224145Sdim // but no lifetime qualifier, the __strong lifetime qualifier is inferred. 1098234353Sdim if (S.getLangOpts().ObjCAutoRefCount && 1099224145Sdim DeducedType->isObjCLifetimeType() && 1100224145Sdim !DeducedQs.hasObjCLifetime()) 1101224145Sdim DeducedQs.setObjCLifetime(Qualifiers::OCL_Strong); 1102224145Sdim 1103221345Sdim DeducedType = S.Context.getQualifiedType(DeducedType.getUnqualifiedType(), 1104221345Sdim DeducedQs); 1105221345Sdim 1106198092Srdivacky if (RecanonicalizeArg) 1107203955Srdivacky DeducedType = S.Context.getCanonicalType(DeducedType); 1108198092Srdivacky 1109218893Sdim DeducedTemplateArgument NewDeduced(DeducedType); 1110218893Sdim DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 1111218893Sdim Deduced[Index], 1112218893Sdim NewDeduced); 1113218893Sdim if (Result.isNull()) { 1114218893Sdim Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 1115218893Sdim Info.FirstArg = Deduced[Index]; 1116218893Sdim Info.SecondArg = NewDeduced; 1117218893Sdim return Sema::TDK_Inconsistent; 1118193576Sed } 1119218893Sdim 1120218893Sdim Deduced[Index] = Result; 1121194179Sed return Sema::TDK_Success; 1122193576Sed } 1123193576Sed 1124194179Sed // Set up the template argument deduction information for a failure. 1125198893Srdivacky Info.FirstArg = TemplateArgument(ParamIn); 1126198893Srdivacky Info.SecondArg = TemplateArgument(ArgIn); 1127194179Sed 1128218893Sdim // If the parameter is an already-substituted template parameter 1129218893Sdim // pack, do nothing: we don't know which of its arguments to look 1130218893Sdim // at, so we have to wait until all of the parameter packs in this 1131218893Sdim // expansion have arguments. 1132218893Sdim if (isa<SubstTemplateTypeParmPackType>(Param)) 1133218893Sdim return Sema::TDK_Success; 1134218893Sdim 1135195099Sed // Check the cv-qualifiers on the parameter and argument types. 1136251662Sdim CanQualType CanParam = S.Context.getCanonicalType(Param); 1137251662Sdim CanQualType CanArg = S.Context.getCanonicalType(Arg); 1138195099Sed if (!(TDF & TDF_IgnoreQualifiers)) { 1139195099Sed if (TDF & TDF_ParamWithReferenceType) { 1140221345Sdim if (hasInconsistentOrSupersetQualifiersOf(Param, Arg)) 1141195099Sed return Sema::TDK_NonDeducedMismatch; 1142212904Sdim } else if (!IsPossiblyOpaquelyQualifiedType(Param)) { 1143195099Sed if (Param.getCVRQualifiers() != Arg.getCVRQualifiers()) 1144198092Srdivacky return Sema::TDK_NonDeducedMismatch; 1145195099Sed } 1146234353Sdim 1147234353Sdim // If the parameter type is not dependent, there is nothing to deduce. 1148234353Sdim if (!Param->isDependentType()) { 1149251662Sdim if (!(TDF & TDF_SkipNonDependent)) { 1150251662Sdim bool NonDeduced = (TDF & TDF_InOverloadResolution)? 1151251662Sdim !S.isSameOrCompatibleFunctionType(CanParam, CanArg) : 1152251662Sdim Param != Arg; 1153251662Sdim if (NonDeduced) { 1154251662Sdim return Sema::TDK_NonDeducedMismatch; 1155251662Sdim } 1156251662Sdim } 1157234353Sdim return Sema::TDK_Success; 1158234353Sdim } 1159251662Sdim } else if (!Param->isDependentType()) { 1160251662Sdim CanQualType ParamUnqualType = CanParam.getUnqualifiedType(), 1161251662Sdim ArgUnqualType = CanArg.getUnqualifiedType(); 1162251662Sdim bool Success = (TDF & TDF_InOverloadResolution)? 1163251662Sdim S.isSameOrCompatibleFunctionType(ParamUnqualType, 1164251662Sdim ArgUnqualType) : 1165251662Sdim ParamUnqualType == ArgUnqualType; 1166251662Sdim if (Success) 1167251662Sdim return Sema::TDK_Success; 1168195099Sed } 1169193576Sed 1170193576Sed switch (Param->getTypeClass()) { 1171224145Sdim // Non-canonical types cannot appear here. 1172224145Sdim#define NON_CANONICAL_TYPE(Class, Base) \ 1173224145Sdim case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class); 1174224145Sdim#define TYPE(Class, Base) 1175224145Sdim#include "clang/AST/TypeNodes.def" 1176224145Sdim 1177224145Sdim case Type::TemplateTypeParm: 1178224145Sdim case Type::SubstTemplateTypeParmPack: 1179224145Sdim llvm_unreachable("Type nodes handled above"); 1180234353Sdim 1181234353Sdim // These types cannot be dependent, so simply check whether the types are 1182234353Sdim // the same. 1183193576Sed case Type::Builtin: 1184224145Sdim case Type::VariableArray: 1185224145Sdim case Type::Vector: 1186224145Sdim case Type::FunctionNoProto: 1187224145Sdim case Type::Record: 1188224145Sdim case Type::Enum: 1189224145Sdim case Type::ObjCObject: 1190224145Sdim case Type::ObjCInterface: 1191234353Sdim case Type::ObjCObjectPointer: { 1192234353Sdim if (TDF & TDF_SkipNonDependent) 1193234353Sdim return Sema::TDK_Success; 1194234353Sdim 1195234353Sdim if (TDF & TDF_IgnoreQualifiers) { 1196234353Sdim Param = Param.getUnqualifiedType(); 1197234353Sdim Arg = Arg.getUnqualifiedType(); 1198234353Sdim } 1199234353Sdim 1200234353Sdim return Param == Arg? Sema::TDK_Success : Sema::TDK_NonDeducedMismatch; 1201234353Sdim } 1202234353Sdim 1203224145Sdim // _Complex T [placeholder extension] 1204224145Sdim case Type::Complex: 1205224145Sdim if (const ComplexType *ComplexArg = Arg->getAs<ComplexType>()) 1206234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1207224145Sdim cast<ComplexType>(Param)->getElementType(), 1208234353Sdim ComplexArg->getElementType(), 1209234353Sdim Info, Deduced, TDF); 1210224145Sdim 1211224145Sdim return Sema::TDK_NonDeducedMismatch; 1212226633Sdim 1213226633Sdim // _Atomic T [extension] 1214226633Sdim case Type::Atomic: 1215226633Sdim if (const AtomicType *AtomicArg = Arg->getAs<AtomicType>()) 1216234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1217226633Sdim cast<AtomicType>(Param)->getValueType(), 1218226633Sdim AtomicArg->getValueType(), 1219226633Sdim Info, Deduced, TDF); 1220226633Sdim 1221226633Sdim return Sema::TDK_NonDeducedMismatch; 1222226633Sdim 1223193576Sed // T * 1224193576Sed case Type::Pointer: { 1225208600Srdivacky QualType PointeeType; 1226208600Srdivacky if (const PointerType *PointerArg = Arg->getAs<PointerType>()) { 1227208600Srdivacky PointeeType = PointerArg->getPointeeType(); 1228208600Srdivacky } else if (const ObjCObjectPointerType *PointerArg 1229208600Srdivacky = Arg->getAs<ObjCObjectPointerType>()) { 1230208600Srdivacky PointeeType = PointerArg->getPointeeType(); 1231208600Srdivacky } else { 1232194179Sed return Sema::TDK_NonDeducedMismatch; 1233208600Srdivacky } 1234198092Srdivacky 1235195099Sed unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass); 1236234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1237234353Sdim cast<PointerType>(Param)->getPointeeType(), 1238208600Srdivacky PointeeType, 1239195099Sed Info, Deduced, SubTDF); 1240193576Sed } 1241198092Srdivacky 1242193576Sed // T & 1243193576Sed case Type::LValueReference: { 1244198092Srdivacky const LValueReferenceType *ReferenceArg = Arg->getAs<LValueReferenceType>(); 1245193576Sed if (!ReferenceArg) 1246194179Sed return Sema::TDK_NonDeducedMismatch; 1247198092Srdivacky 1248234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1249193576Sed cast<LValueReferenceType>(Param)->getPointeeType(), 1250234353Sdim ReferenceArg->getPointeeType(), Info, Deduced, 0); 1251193576Sed } 1252193576Sed 1253193576Sed // T && [C++0x] 1254193576Sed case Type::RValueReference: { 1255198092Srdivacky const RValueReferenceType *ReferenceArg = Arg->getAs<RValueReferenceType>(); 1256193576Sed if (!ReferenceArg) 1257194179Sed return Sema::TDK_NonDeducedMismatch; 1258198092Srdivacky 1259234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1260234353Sdim cast<RValueReferenceType>(Param)->getPointeeType(), 1261234353Sdim ReferenceArg->getPointeeType(), 1262234353Sdim Info, Deduced, 0); 1263193576Sed } 1264198092Srdivacky 1265193576Sed // T [] (implied, but not stated explicitly) 1266193576Sed case Type::IncompleteArray: { 1267198092Srdivacky const IncompleteArrayType *IncompleteArrayArg = 1268203955Srdivacky S.Context.getAsIncompleteArrayType(Arg); 1269193576Sed if (!IncompleteArrayArg) 1270194179Sed return Sema::TDK_NonDeducedMismatch; 1271198092Srdivacky 1272212904Sdim unsigned SubTDF = TDF & TDF_IgnoreQualifiers; 1273234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1274234353Sdim S.Context.getAsIncompleteArrayType(Param)->getElementType(), 1275234353Sdim IncompleteArrayArg->getElementType(), 1276234353Sdim Info, Deduced, SubTDF); 1277193576Sed } 1278193576Sed 1279193576Sed // T [integer-constant] 1280193576Sed case Type::ConstantArray: { 1281198092Srdivacky const ConstantArrayType *ConstantArrayArg = 1282203955Srdivacky S.Context.getAsConstantArrayType(Arg); 1283193576Sed if (!ConstantArrayArg) 1284194179Sed return Sema::TDK_NonDeducedMismatch; 1285198092Srdivacky 1286198092Srdivacky const ConstantArrayType *ConstantArrayParm = 1287203955Srdivacky S.Context.getAsConstantArrayType(Param); 1288193576Sed if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize()) 1289194179Sed return Sema::TDK_NonDeducedMismatch; 1290198092Srdivacky 1291212904Sdim unsigned SubTDF = TDF & TDF_IgnoreQualifiers; 1292234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1293234353Sdim ConstantArrayParm->getElementType(), 1294234353Sdim ConstantArrayArg->getElementType(), 1295234353Sdim Info, Deduced, SubTDF); 1296193576Sed } 1297193576Sed 1298193576Sed // type [i] 1299193576Sed case Type::DependentSizedArray: { 1300203955Srdivacky const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg); 1301193576Sed if (!ArrayArg) 1302194179Sed return Sema::TDK_NonDeducedMismatch; 1303198092Srdivacky 1304212904Sdim unsigned SubTDF = TDF & TDF_IgnoreQualifiers; 1305212904Sdim 1306193576Sed // Check the element type of the arrays 1307193576Sed const DependentSizedArrayType *DependentArrayParm 1308203955Srdivacky = S.Context.getAsDependentSizedArrayType(Param); 1309194179Sed if (Sema::TemplateDeductionResult Result 1310234353Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1311234353Sdim DependentArrayParm->getElementType(), 1312234353Sdim ArrayArg->getElementType(), 1313234353Sdim Info, Deduced, SubTDF)) 1314194179Sed return Result; 1315198092Srdivacky 1316193576Sed // Determine the array bound is something we can deduce. 1317198092Srdivacky NonTypeTemplateParmDecl *NTTP 1318193576Sed = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr()); 1319193576Sed if (!NTTP) 1320194179Sed return Sema::TDK_Success; 1321198092Srdivacky 1322198092Srdivacky // We can perform template argument deduction for the given non-type 1323193576Sed // template parameter. 1324198092Srdivacky assert(NTTP->getDepth() == 0 && 1325193576Sed "Cannot deduce non-type template argument at depth > 0"); 1326198092Srdivacky if (const ConstantArrayType *ConstantArrayArg 1327194613Sed = dyn_cast<ConstantArrayType>(ArrayArg)) { 1328194613Sed llvm::APSInt Size(ConstantArrayArg->getSize()); 1329218893Sdim return DeduceNonTypeTemplateArgument(S, NTTP, Size, 1330206084Srdivacky S.Context.getSizeType(), 1331206084Srdivacky /*ArrayBound=*/true, 1332194179Sed Info, Deduced); 1333194613Sed } 1334193576Sed if (const DependentSizedArrayType *DependentArrayArg 1335193576Sed = dyn_cast<DependentSizedArrayType>(ArrayArg)) 1336218893Sdim if (DependentArrayArg->getSizeExpr()) 1337218893Sdim return DeduceNonTypeTemplateArgument(S, NTTP, 1338218893Sdim DependentArrayArg->getSizeExpr(), 1339218893Sdim Info, Deduced); 1340198092Srdivacky 1341193576Sed // Incomplete type does not match a dependently-sized array type 1342194179Sed return Sema::TDK_NonDeducedMismatch; 1343193576Sed } 1344198092Srdivacky 1345198092Srdivacky // type(*)(T) 1346198092Srdivacky // T(*)() 1347198092Srdivacky // T(*)(T) 1348193725Sed case Type::FunctionProto: { 1349218893Sdim unsigned SubTDF = TDF & TDF_TopLevelParameterTypeList; 1350198092Srdivacky const FunctionProtoType *FunctionProtoArg = 1351193725Sed dyn_cast<FunctionProtoType>(Arg); 1352193725Sed if (!FunctionProtoArg) 1353194179Sed return Sema::TDK_NonDeducedMismatch; 1354198092Srdivacky 1355198092Srdivacky const FunctionProtoType *FunctionProtoParam = 1356193725Sed cast<FunctionProtoType>(Param); 1357194179Sed 1358218893Sdim if (FunctionProtoParam->getTypeQuals() 1359218893Sdim != FunctionProtoArg->getTypeQuals() || 1360218893Sdim FunctionProtoParam->getRefQualifier() 1361218893Sdim != FunctionProtoArg->getRefQualifier() || 1362218893Sdim FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic()) 1363194179Sed return Sema::TDK_NonDeducedMismatch; 1364198092Srdivacky 1365193725Sed // Check return types. 1366194179Sed if (Sema::TemplateDeductionResult Result 1367234353Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1368234353Sdim FunctionProtoParam->getResultType(), 1369234353Sdim FunctionProtoArg->getResultType(), 1370234353Sdim Info, Deduced, 0)) 1371194179Sed return Result; 1372198092Srdivacky 1373218893Sdim return DeduceTemplateArguments(S, TemplateParams, 1374218893Sdim FunctionProtoParam->arg_type_begin(), 1375218893Sdim FunctionProtoParam->getNumArgs(), 1376218893Sdim FunctionProtoArg->arg_type_begin(), 1377218893Sdim FunctionProtoArg->getNumArgs(), 1378218893Sdim Info, Deduced, SubTDF); 1379193725Sed } 1380198092Srdivacky 1381204962Srdivacky case Type::InjectedClassName: { 1382204962Srdivacky // Treat a template's injected-class-name as if the template 1383204962Srdivacky // specialization type had been used. 1384207619Srdivacky Param = cast<InjectedClassNameType>(Param) 1385207619Srdivacky ->getInjectedSpecializationType(); 1386204962Srdivacky assert(isa<TemplateSpecializationType>(Param) && 1387204962Srdivacky "injected class name is not a template specialization type"); 1388204962Srdivacky // fall through 1389204962Srdivacky } 1390204962Srdivacky 1391195099Sed // template-name<T> (where template-name refers to a class template) 1392194179Sed // template-name<i> 1393199482Srdivacky // TT<T> 1394199482Srdivacky // TT<i> 1395199482Srdivacky // TT<> 1396194179Sed case Type::TemplateSpecialization: { 1397194179Sed const TemplateSpecializationType *SpecParam 1398194179Sed = cast<TemplateSpecializationType>(Param); 1399194179Sed 1400198092Srdivacky // Try to deduce template arguments from the template-id. 1401198092Srdivacky Sema::TemplateDeductionResult Result 1402203955Srdivacky = DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg, 1403198092Srdivacky Info, Deduced); 1404194179Sed 1405198092Srdivacky if (Result && (TDF & TDF_DerivedClass)) { 1406198092Srdivacky // C++ [temp.deduct.call]p3b3: 1407198092Srdivacky // If P is a class, and P has the form template-id, then A can be a 1408198092Srdivacky // derived class of the deduced A. Likewise, if P is a pointer to a 1409198092Srdivacky // class of the form template-id, A can be a pointer to a derived 1410198092Srdivacky // class pointed to by the deduced A. 1411198092Srdivacky // 1412198092Srdivacky // More importantly: 1413198092Srdivacky // These alternatives are considered only if type deduction would 1414198092Srdivacky // otherwise fail. 1415203955Srdivacky if (const RecordType *RecordT = Arg->getAs<RecordType>()) { 1416203955Srdivacky // We cannot inspect base classes as part of deduction when the type 1417203955Srdivacky // is incomplete, so either instantiate any templates necessary to 1418203955Srdivacky // complete the type, or skip over it if it cannot be completed. 1419203955Srdivacky if (S.RequireCompleteType(Info.getLocation(), Arg, 0)) 1420203955Srdivacky return Result; 1421203955Srdivacky 1422198092Srdivacky // Use data recursion to crawl through the list of base classes. 1423198092Srdivacky // Visited contains the set of nodes we have already visited, while 1424198092Srdivacky // ToVisit is our stack of records that we still need to visit. 1425198092Srdivacky llvm::SmallPtrSet<const RecordType *, 8> Visited; 1426226633Sdim SmallVector<const RecordType *, 8> ToVisit; 1427198092Srdivacky ToVisit.push_back(RecordT); 1428198092Srdivacky bool Successful = false; 1429234353Sdim SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(), 1430234353Sdim Deduced.end()); 1431198092Srdivacky while (!ToVisit.empty()) { 1432198092Srdivacky // Retrieve the next class in the inheritance hierarchy. 1433198092Srdivacky const RecordType *NextT = ToVisit.back(); 1434198092Srdivacky ToVisit.pop_back(); 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) { 1443243830Sdim TemplateDeductionInfo BaseInfo(Info.getLocation()); 1444198092Srdivacky Sema::TemplateDeductionResult BaseResult 1445203955Srdivacky = DeduceTemplateArguments(S, TemplateParams, SpecParam, 1446243830Sdim QualType(NextT, 0), BaseInfo, 1447243830Sdim 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; 1454234353Sdim DeducedOrig.clear(); 1455234353Sdim DeducedOrig.append(Deduced.begin(), Deduced.end()); 1456243830Sdim Info.Param = BaseInfo.Param; 1457243830Sdim Info.FirstArg = BaseInfo.FirstArg; 1458243830Sdim 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 1500234353Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1501234353Sdim MemPtrParam->getPointeeType(), 1502234353Sdim MemPtrArg->getPointeeType(), 1503234353Sdim Info, Deduced, 1504234353Sdim TDF & TDF_IgnoreQualifiers)) 1505194179Sed return Result; 1506194179Sed 1507234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1508234353Sdim QualType(MemPtrParam->getClass(), 0), 1509234353Sdim QualType(MemPtrArg->getClass(), 0), 1510234353Sdim Info, Deduced, 1511234353Sdim 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 1526234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1527234353Sdim BlockPtrParam->getPointeeType(), 1528234353Sdim BlockPtrArg->getPointeeType(), 1529234353Sdim 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. 1543234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1544234353Sdim VectorParam->getElementType(), 1545234353Sdim VectorArg->getElementType(), 1546234353Sdim 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. 1556234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1557234353Sdim VectorParam->getElementType(), 1558234353Sdim VectorArg->getElementType(), 1559234353Sdim 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 1575234353Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1576234353Sdim VectorParam->getElementType(), 1577234353Sdim VectorArg->getElementType(), 1578234353Sdim 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 1597234353Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1598234353Sdim VectorParam->getElementType(), 1599234353Sdim VectorArg->getElementType(), 1600234353Sdim 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 1629234353Sdim 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, 1638226633Sdim 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: 1647226633Sdim llvm_unreachable("Null template argument in parameter list"); 1648198092Srdivacky 1649198092Srdivacky case TemplateArgument::Type: 1650199482Srdivacky if (Arg.getKind() == TemplateArgument::Type) 1651234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 1652234353Sdim Param.getAsType(), 1653234353Sdim Arg.getAsType(), 1654234353Sdim 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 && 1673243830Sdim isSameDeclaration(Param.getAsDecl(), Arg.getAsDecl()) && 1674243830Sdim Param.isDeclForReferenceParam() == Arg.isDeclForReferenceParam()) 1675199482Srdivacky return Sema::TDK_Success; 1676218893Sdim 1677194179Sed Info.FirstArg = Param; 1678194179Sed Info.SecondArg = Arg; 1679194179Sed return Sema::TDK_NonDeducedMismatch; 1680198092Srdivacky 1681243830Sdim case TemplateArgument::NullPtr: 1682243830Sdim if (Arg.getKind() == TemplateArgument::NullPtr && 1683243830Sdim S.Context.hasSameType(Param.getNullPtrType(), Arg.getNullPtrType())) 1684243830Sdim return Sema::TDK_Success; 1685243830Sdim 1686243830Sdim Info.FirstArg = Param; 1687243830Sdim Info.SecondArg = Arg; 1688243830Sdim return Sema::TDK_NonDeducedMismatch; 1689243830Sdim 1690193576Sed case TemplateArgument::Integral: 1691193576Sed if (Arg.getKind() == TemplateArgument::Integral) { 1692239462Sdim 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, 1715239462Sdim 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 1738234353Sdim 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, 1799249423Sdim 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)) 1819249423Sdim 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. 1824249423Sdim 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. 1850226633Sdim SmallVector<unsigned, 2> PackIndices; 1851218893Sdim { 1852234353Sdim llvm::SmallBitVector SawIndices(TemplateParams->size()); 1853226633Sdim 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. 1872226633Sdim SmallVector<DeducedTemplateArgument, 2> 1873218893Sdim SavedPacks(PackIndices.size()); 1874226633Sdim SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2> 1875218893Sdim NewlyDeducedPacks(PackIndices.size()); 1876218893Sdim PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks, 1877218893Sdim NewlyDeducedPacks); 1878218893Sdim 1879218893Sdim // Keep track of the deduced template arguments for each parameter pack 1880218893Sdim // expanded by this pack expansion (the outer index) and for each 1881218893Sdim // template argument (the inner SmallVectors). 1882218893Sdim bool HasAnyArguments = false; 1883218893Sdim while (hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) { 1884218893Sdim HasAnyArguments = true; 1885218893Sdim 1886218893Sdim // Deduce template arguments from the pattern. 1887218893Sdim if (Sema::TemplateDeductionResult Result 1888218893Sdim = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx], 1889218893Sdim Info, Deduced)) 1890218893Sdim return Result; 1891218893Sdim 1892218893Sdim // Capture the deduced template arguments for each parameter pack expanded 1893218893Sdim // by this pack expansion, add them to the list of arguments we've deduced 1894218893Sdim // for that pack, then clear out the deduced argument. 1895218893Sdim for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 1896218893Sdim DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]]; 1897218893Sdim if (!DeducedArg.isNull()) { 1898218893Sdim NewlyDeducedPacks[I].push_back(DeducedArg); 1899218893Sdim DeducedArg = DeducedTemplateArgument(); 1900218893Sdim } 1901218893Sdim } 1902218893Sdim 1903218893Sdim ++ArgIdx; 1904218893Sdim } 1905218893Sdim 1906218893Sdim // Build argument packs for each of the parameter packs expanded by this 1907218893Sdim // pack expansion. 1908194179Sed if (Sema::TemplateDeductionResult Result 1909218893Sdim = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments, 1910218893Sdim Deduced, PackIndices, SavedPacks, 1911218893Sdim NewlyDeducedPacks, Info)) 1912194179Sed return Result; 1913193576Sed } 1914218893Sdim 1915194179Sed return Sema::TDK_Success; 1916193576Sed} 1917193576Sed 1918218893Sdimstatic Sema::TemplateDeductionResult 1919218893SdimDeduceTemplateArguments(Sema &S, 1920218893Sdim TemplateParameterList *TemplateParams, 1921218893Sdim const TemplateArgumentList &ParamList, 1922218893Sdim const TemplateArgumentList &ArgList, 1923218893Sdim TemplateDeductionInfo &Info, 1924226633Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 1925218893Sdim return DeduceTemplateArguments(S, TemplateParams, 1926218893Sdim ParamList.data(), ParamList.size(), 1927218893Sdim ArgList.data(), ArgList.size(), 1928218893Sdim Info, Deduced); 1929218893Sdim} 1930218893Sdim 1931195099Sed/// \brief Determine whether two template arguments are the same. 1932198092Srdivackystatic bool isSameTemplateArg(ASTContext &Context, 1933195099Sed const TemplateArgument &X, 1934195099Sed const TemplateArgument &Y) { 1935195099Sed if (X.getKind() != Y.getKind()) 1936195099Sed return false; 1937198092Srdivacky 1938195099Sed switch (X.getKind()) { 1939195099Sed case TemplateArgument::Null: 1940226633Sdim llvm_unreachable("Comparing NULL template argument"); 1941198092Srdivacky 1942195099Sed case TemplateArgument::Type: 1943195099Sed return Context.getCanonicalType(X.getAsType()) == 1944195099Sed Context.getCanonicalType(Y.getAsType()); 1945198092Srdivacky 1946195099Sed case TemplateArgument::Declaration: 1947243830Sdim return isSameDeclaration(X.getAsDecl(), Y.getAsDecl()) && 1948243830Sdim X.isDeclForReferenceParam() == Y.isDeclForReferenceParam(); 1949198092Srdivacky 1950243830Sdim case TemplateArgument::NullPtr: 1951243830Sdim return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType()); 1952243830Sdim 1953199482Srdivacky case TemplateArgument::Template: 1954218893Sdim case TemplateArgument::TemplateExpansion: 1955218893Sdim return Context.getCanonicalTemplateName( 1956218893Sdim X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() == 1957218893Sdim Context.getCanonicalTemplateName( 1958218893Sdim Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer(); 1959218893Sdim 1960195099Sed case TemplateArgument::Integral: 1961239462Sdim return X.getAsIntegral() == Y.getAsIntegral(); 1962198092Srdivacky 1963199482Srdivacky case TemplateArgument::Expression: { 1964199482Srdivacky llvm::FoldingSetNodeID XID, YID; 1965199482Srdivacky X.getAsExpr()->Profile(XID, Context, true); 1966218893Sdim Y.getAsExpr()->Profile(YID, Context, true); 1967199482Srdivacky return XID == YID; 1968199482Srdivacky } 1969198092Srdivacky 1970195099Sed case TemplateArgument::Pack: 1971195099Sed if (X.pack_size() != Y.pack_size()) 1972195099Sed return false; 1973198092Srdivacky 1974198092Srdivacky for (TemplateArgument::pack_iterator XP = X.pack_begin(), 1975198092Srdivacky XPEnd = X.pack_end(), 1976195099Sed YP = Y.pack_begin(); 1977198092Srdivacky XP != XPEnd; ++XP, ++YP) 1978195099Sed if (!isSameTemplateArg(Context, *XP, *YP)) 1979195099Sed return false; 1980195099Sed 1981195099Sed return true; 1982195099Sed } 1983195099Sed 1984234353Sdim llvm_unreachable("Invalid TemplateArgument Kind!"); 1985195099Sed} 1986195099Sed 1987218893Sdim/// \brief Allocate a TemplateArgumentLoc where all locations have 1988218893Sdim/// been initialized to the given location. 1989218893Sdim/// 1990218893Sdim/// \param S The semantic analysis object. 1991218893Sdim/// 1992239462Sdim/// \param Arg The template argument we are producing template argument 1993218893Sdim/// location information for. 1994218893Sdim/// 1995218893Sdim/// \param NTTPType For a declaration template argument, the type of 1996218893Sdim/// the non-type template parameter that corresponds to this template 1997218893Sdim/// argument. 1998218893Sdim/// 1999218893Sdim/// \param Loc The source location to use for the resulting template 2000218893Sdim/// argument. 2001218893Sdimstatic TemplateArgumentLoc 2002218893SdimgetTrivialTemplateArgumentLoc(Sema &S, 2003218893Sdim const TemplateArgument &Arg, 2004218893Sdim QualType NTTPType, 2005218893Sdim SourceLocation Loc) { 2006218893Sdim switch (Arg.getKind()) { 2007218893Sdim case TemplateArgument::Null: 2008218893Sdim llvm_unreachable("Can't get a NULL template argument here"); 2009198092Srdivacky 2010218893Sdim case TemplateArgument::Type: 2011218893Sdim return TemplateArgumentLoc(Arg, 2012218893Sdim S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc)); 2013218893Sdim 2014218893Sdim case TemplateArgument::Declaration: { 2015218893Sdim Expr *E 2016218893Sdim = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc) 2017234353Sdim .takeAs<Expr>(); 2018218893Sdim return TemplateArgumentLoc(TemplateArgument(E), E); 2019218893Sdim } 2020218893Sdim 2021243830Sdim case TemplateArgument::NullPtr: { 2022243830Sdim Expr *E 2023243830Sdim = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc) 2024243830Sdim .takeAs<Expr>(); 2025243830Sdim return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true), 2026243830Sdim E); 2027243830Sdim } 2028243830Sdim 2029218893Sdim case TemplateArgument::Integral: { 2030218893Sdim Expr *E 2031218893Sdim = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).takeAs<Expr>(); 2032218893Sdim return TemplateArgumentLoc(TemplateArgument(E), E); 2033218893Sdim } 2034218893Sdim 2035221345Sdim case TemplateArgument::Template: 2036221345Sdim case TemplateArgument::TemplateExpansion: { 2037221345Sdim NestedNameSpecifierLocBuilder Builder; 2038221345Sdim TemplateName Template = Arg.getAsTemplate(); 2039221345Sdim if (DependentTemplateName *DTN = Template.getAsDependentTemplateName()) 2040221345Sdim Builder.MakeTrivial(S.Context, DTN->getQualifier(), Loc); 2041221345Sdim else if (QualifiedTemplateName *QTN = Template.getAsQualifiedTemplateName()) 2042221345Sdim Builder.MakeTrivial(S.Context, QTN->getQualifier(), Loc); 2043221345Sdim 2044221345Sdim if (Arg.getKind() == TemplateArgument::Template) 2045221345Sdim return TemplateArgumentLoc(Arg, 2046221345Sdim Builder.getWithLocInContext(S.Context), 2047221345Sdim Loc); 2048221345Sdim 2049221345Sdim 2050221345Sdim return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(S.Context), 2051221345Sdim Loc, Loc); 2052221345Sdim } 2053218893Sdim 2054218893Sdim case TemplateArgument::Expression: 2055218893Sdim return TemplateArgumentLoc(Arg, Arg.getAsExpr()); 2056218893Sdim 2057218893Sdim case TemplateArgument::Pack: 2058218893Sdim return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo()); 2059218893Sdim } 2060218893Sdim 2061234353Sdim llvm_unreachable("Invalid TemplateArgument Kind!"); 2062195099Sed} 2063195099Sed 2064218893Sdim 2065218893Sdim/// \brief Convert the given deduced template argument and add it to the set of 2066218893Sdim/// fully-converted template arguments. 2067218893Sdimstatic bool ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param, 2068218893Sdim DeducedTemplateArgument Arg, 2069218893Sdim NamedDecl *Template, 2070218893Sdim QualType NTTPType, 2071218893Sdim unsigned ArgumentPackIndex, 2072218893Sdim TemplateDeductionInfo &Info, 2073218893Sdim bool InFunctionTemplate, 2074226633Sdim 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. 2078226633Sdim 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. 2093218893Sdim PackedArgsBuilder.push_back(Output.back()); 2094218893Sdim Output.pop_back(); 2095218893Sdim } 2096218893Sdim 2097218893Sdim // Create the resulting argument pack. 2098218893Sdim Output.push_back(TemplateArgument::CreatePackCopy(S.Context, 2099218893Sdim PackedArgsBuilder.data(), 2100218893Sdim PackedArgsBuilder.size())); 2101218893Sdim return false; 2102218893Sdim } 2103218893Sdim 2104218893Sdim // Convert the deduced template argument into a template 2105218893Sdim // argument that we can check, almost as if the user had written 2106218893Sdim // the template argument explicitly. 2107218893Sdim TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType, 2108218893Sdim Info.getLocation()); 2109218893Sdim 2110218893Sdim // Check the template argument, converting it as necessary. 2111218893Sdim return S.CheckTemplateArgument(Param, ArgLoc, 2112218893Sdim Template, 2113218893Sdim Template->getLocation(), 2114218893Sdim Template->getSourceRange().getEnd(), 2115218893Sdim ArgumentPackIndex, 2116218893Sdim Output, 2117218893Sdim InFunctionTemplate 2118218893Sdim ? (Arg.wasDeducedFromArrayBound() 2119218893Sdim ? Sema::CTAK_DeducedFromArrayBound 2120218893Sdim : Sema::CTAK_Deduced) 2121218893Sdim : Sema::CTAK_Specified); 2122218893Sdim} 2123218893Sdim 2124207619Srdivacky/// Complete template argument deduction for a class template partial 2125207619Srdivacky/// specialization. 2126207619Srdivackystatic Sema::TemplateDeductionResult 2127218893SdimFinishTemplateArgumentDeduction(Sema &S, 2128207619Srdivacky ClassTemplatePartialSpecializationDecl *Partial, 2129207619Srdivacky const TemplateArgumentList &TemplateArgs, 2130226633Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2131212904Sdim TemplateDeductionInfo &Info) { 2132234353Sdim // Unevaluated SFINAE context. 2133234353Sdim EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated); 2134207619Srdivacky Sema::SFINAETrap Trap(S); 2135218893Sdim 2136207619Srdivacky Sema::ContextRAII SavedContext(S, Partial); 2137194179Sed 2138194179Sed // C++ [temp.deduct.type]p2: 2139194179Sed // [...] or if any template argument remains neither deduced nor 2140194179Sed // explicitly specified, template argument deduction fails. 2141226633Sdim SmallVector<TemplateArgument, 4> Builder; 2142218893Sdim TemplateParameterList *PartialParams = Partial->getTemplateParameters(); 2143218893Sdim for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) { 2144218893Sdim NamedDecl *Param = PartialParams->getParam(I); 2145194179Sed if (Deduced[I].isNull()) { 2146206084Srdivacky Info.Param = makeTemplateParameter(Param); 2147207619Srdivacky return Sema::TDK_Incomplete; 2148194179Sed } 2149218893Sdim 2150218893Sdim // We have deduced this argument, so it still needs to be 2151218893Sdim // checked and converted. 2152218893Sdim 2153218893Sdim // First, for a non-type template parameter type that is 2154218893Sdim // initialized by a declaration, we need the type of the 2155218893Sdim // corresponding non-type template parameter. 2156218893Sdim QualType NTTPType; 2157218893Sdim if (NonTypeTemplateParmDecl *NTTP 2158218893Sdim = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 2159218893Sdim NTTPType = NTTP->getType(); 2160218893Sdim if (NTTPType->isDependentType()) { 2161218893Sdim TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, 2162218893Sdim Builder.data(), Builder.size()); 2163218893Sdim NTTPType = S.SubstType(NTTPType, 2164218893Sdim MultiLevelTemplateArgumentList(TemplateArgs), 2165218893Sdim NTTP->getLocation(), 2166218893Sdim NTTP->getDeclName()); 2167218893Sdim if (NTTPType.isNull()) { 2168218893Sdim Info.Param = makeTemplateParameter(Param); 2169218893Sdim // FIXME: These template arguments are temporary. Free them! 2170218893Sdim Info.reset(TemplateArgumentList::CreateCopy(S.Context, 2171218893Sdim Builder.data(), 2172218893Sdim Builder.size())); 2173218893Sdim return Sema::TDK_SubstitutionFailure; 2174218893Sdim } 2175218893Sdim } 2176218893Sdim } 2177218893Sdim 2178218893Sdim if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], 2179218893Sdim Partial, NTTPType, 0, Info, false, 2180218893Sdim Builder)) { 2181218893Sdim Info.Param = makeTemplateParameter(Param); 2182218893Sdim // FIXME: These template arguments are temporary. Free them! 2183218893Sdim Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(), 2184218893Sdim Builder.size())); 2185218893Sdim return Sema::TDK_SubstitutionFailure; 2186218893Sdim } 2187194179Sed } 2188218893Sdim 2189194179Sed // Form the template argument list from the deduced template arguments. 2190198092Srdivacky TemplateArgumentList *DeducedArgumentList 2191218893Sdim = TemplateArgumentList::CreateCopy(S.Context, Builder.data(), 2192218893Sdim Builder.size()); 2193218893Sdim 2194194179Sed Info.reset(DeducedArgumentList); 2195194179Sed 2196194179Sed // Substitute the deduced template arguments into the template 2197194179Sed // arguments of the class template partial specialization, and 2198194179Sed // verify that the instantiated template arguments are both valid 2199194179Sed // and are equivalent to the template arguments originally provided 2200198092Srdivacky // to the class template. 2201212904Sdim LocalInstantiationScope InstScope(S); 2202194179Sed ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate(); 2203198893Srdivacky const TemplateArgumentLoc *PartialTemplateArgs 2204198893Srdivacky = Partial->getTemplateArgsAsWritten(); 2205199990Srdivacky 2206199990Srdivacky // Note that we don't provide the langle and rangle locations. 2207199990Srdivacky TemplateArgumentListInfo InstArgs; 2208199990Srdivacky 2209218893Sdim if (S.Subst(PartialTemplateArgs, 2210218893Sdim Partial->getNumTemplateArgsAsWritten(), 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 2224226633Sdim 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) { 2254243830Sdim if (Partial->isInvalidDecl()) 2255243830Sdim return TDK_Invalid; 2256243830Sdim 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). 2262234353Sdim 2263234353Sdim // Unevaluated SFINAE context. 2264234353Sdim EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 2265207619Srdivacky SFINAETrap Trap(*this); 2266234353Sdim 2267226633Sdim 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 2276239462Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end()); 2277207619Srdivacky InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial, 2278239462Sdim DeducedArgs, Info); 2279207619Srdivacky if (Inst) 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 2289195099Sed/// \brief Determine whether the given type T is a simple-template-id type. 2290195099Sedstatic bool isSimpleTemplateIdType(QualType T) { 2291198092Srdivacky if (const TemplateSpecializationType *Spec 2292198092Srdivacky = T->getAs<TemplateSpecializationType>()) 2293195099Sed return Spec->getTemplateName().getAsTemplateDecl() != 0; 2294198092Srdivacky 2295195099Sed return false; 2296195099Sed} 2297198092Srdivacky 2298198092Srdivacky/// \brief Substitute the explicitly-provided template arguments into the 2299198092Srdivacky/// given function template according to C++ [temp.arg.explicit]. 2300198092Srdivacky/// 2301198092Srdivacky/// \param FunctionTemplate the function template into which the explicit 2302198092Srdivacky/// template arguments will be substituted. 2303198092Srdivacky/// 2304239462Sdim/// \param ExplicitTemplateArgs the explicitly-specified template 2305198092Srdivacky/// arguments. 2306198092Srdivacky/// 2307198092Srdivacky/// \param Deduced the deduced template arguments, which will be populated 2308198092Srdivacky/// with the converted and checked explicit template arguments. 2309198092Srdivacky/// 2310198092Srdivacky/// \param ParamTypes will be populated with the instantiated function 2311198092Srdivacky/// parameters. 2312198092Srdivacky/// 2313198092Srdivacky/// \param FunctionType if non-NULL, the result type of the function template 2314198092Srdivacky/// will also be instantiated and the pointed-to value will be updated with 2315198092Srdivacky/// the instantiated function type. 2316198092Srdivacky/// 2317198092Srdivacky/// \param Info if substitution fails for any reason, this object will be 2318198092Srdivacky/// populated with more information about the failure. 2319198092Srdivacky/// 2320198092Srdivacky/// \returns TDK_Success if substitution was successful, or some failure 2321198092Srdivacky/// condition. 2322198092SrdivackySema::TemplateDeductionResult 2323198092SrdivackySema::SubstituteExplicitTemplateArguments( 2324198092Srdivacky FunctionTemplateDecl *FunctionTemplate, 2325221345Sdim TemplateArgumentListInfo &ExplicitTemplateArgs, 2326226633Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2327226633Sdim SmallVectorImpl<QualType> &ParamTypes, 2328198092Srdivacky QualType *FunctionType, 2329198092Srdivacky TemplateDeductionInfo &Info) { 2330198092Srdivacky FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 2331198092Srdivacky TemplateParameterList *TemplateParams 2332198092Srdivacky = FunctionTemplate->getTemplateParameters(); 2333198092Srdivacky 2334199990Srdivacky if (ExplicitTemplateArgs.size() == 0) { 2335198092Srdivacky // No arguments to substitute; just copy over the parameter types and 2336198092Srdivacky // fill in the function type. 2337198092Srdivacky for (FunctionDecl::param_iterator P = Function->param_begin(), 2338198092Srdivacky PEnd = Function->param_end(); 2339198092Srdivacky P != PEnd; 2340198092Srdivacky ++P) 2341198092Srdivacky ParamTypes.push_back((*P)->getType()); 2342198092Srdivacky 2343198092Srdivacky if (FunctionType) 2344198092Srdivacky *FunctionType = Function->getType(); 2345198092Srdivacky return TDK_Success; 2346198092Srdivacky } 2347198092Srdivacky 2348234353Sdim // Unevaluated SFINAE context. 2349234353Sdim EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 2350198092Srdivacky SFINAETrap Trap(*this); 2351198092Srdivacky 2352198092Srdivacky // C++ [temp.arg.explicit]p3: 2353198092Srdivacky // Template arguments that are present shall be specified in the 2354198092Srdivacky // declaration order of their corresponding template-parameters. The 2355198092Srdivacky // template argument list shall not specify more template-arguments than 2356198092Srdivacky // there are corresponding template-parameters. 2357226633Sdim SmallVector<TemplateArgument, 4> Builder; 2358198092Srdivacky 2359198092Srdivacky // Enter a new template instantiation context where we check the 2360198092Srdivacky // explicitly-specified template arguments against this function template, 2361198092Srdivacky // and then substitute them into the function parameter types. 2362239462Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end()); 2363198092Srdivacky InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 2364239462Sdim FunctionTemplate, DeducedArgs, 2365218893Sdim ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution, 2366218893Sdim Info); 2367198092Srdivacky if (Inst) 2368198092Srdivacky return TDK_InstantiationDepth; 2369198092Srdivacky 2370198092Srdivacky if (CheckTemplateArgumentList(FunctionTemplate, 2371199990Srdivacky SourceLocation(), 2372198092Srdivacky ExplicitTemplateArgs, 2373198092Srdivacky true, 2374208600Srdivacky Builder) || Trap.hasErrorOccurred()) { 2375218893Sdim unsigned Index = Builder.size(); 2376208600Srdivacky if (Index >= TemplateParams->size()) 2377208600Srdivacky Index = TemplateParams->size() - 1; 2378208600Srdivacky Info.Param = makeTemplateParameter(TemplateParams->getParam(Index)); 2379198092Srdivacky return TDK_InvalidExplicitArguments; 2380208600Srdivacky } 2381198092Srdivacky 2382198092Srdivacky // Form the template argument list from the explicitly-specified 2383198092Srdivacky // template arguments. 2384198092Srdivacky TemplateArgumentList *ExplicitArgumentList 2385218893Sdim = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size()); 2386198092Srdivacky Info.reset(ExplicitArgumentList); 2387198092Srdivacky 2388218893Sdim // Template argument deduction and the final substitution should be 2389218893Sdim // done in the context of the templated declaration. Explicit 2390218893Sdim // argument substitution, on the other hand, needs to happen in the 2391218893Sdim // calling context. 2392218893Sdim ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 2393218893Sdim 2394218893Sdim // If we deduced template arguments for a template parameter pack, 2395218893Sdim // note that the template argument pack is partially substituted and record 2396218893Sdim // the explicit template arguments. They'll be used as part of deduction 2397218893Sdim // for this template parameter pack. 2398218893Sdim for (unsigned I = 0, N = Builder.size(); I != N; ++I) { 2399218893Sdim const TemplateArgument &Arg = Builder[I]; 2400218893Sdim if (Arg.getKind() == TemplateArgument::Pack) { 2401218893Sdim CurrentInstantiationScope->SetPartiallySubstitutedPack( 2402218893Sdim TemplateParams->getParam(I), 2403218893Sdim Arg.pack_begin(), 2404218893Sdim Arg.pack_size()); 2405218893Sdim break; 2406218893Sdim } 2407218893Sdim } 2408218893Sdim 2409234353Sdim const FunctionProtoType *Proto 2410234353Sdim = Function->getType()->getAs<FunctionProtoType>(); 2411234353Sdim assert(Proto && "Function template does not have a prototype?"); 2412234353Sdim 2413198092Srdivacky // Instantiate the types of each of the function parameters given the 2414234353Sdim // explicitly-specified template arguments. If the function has a trailing 2415234353Sdim // return type, substitute it after the arguments to ensure we substitute 2416234353Sdim // in lexical order. 2417234982Sdim if (Proto->hasTrailingReturn()) { 2418234982Sdim if (SubstParmTypes(Function->getLocation(), 2419234982Sdim Function->param_begin(), Function->getNumParams(), 2420234982Sdim MultiLevelTemplateArgumentList(*ExplicitArgumentList), 2421234982Sdim ParamTypes)) 2422234982Sdim return TDK_SubstitutionFailure; 2423234982Sdim } 2424234982Sdim 2425234353Sdim // Instantiate the return type. 2426234353Sdim // FIXME: exception-specifications? 2427234982Sdim QualType ResultType; 2428234982Sdim { 2429234982Sdim // C++11 [expr.prim.general]p3: 2430234982Sdim // If a declaration declares a member function or member function 2431234982Sdim // template of a class X, the expression this is a prvalue of type 2432234982Sdim // "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq 2433234982Sdim // and the end of the function-definition, member-declarator, or 2434234982Sdim // declarator. 2435234982Sdim unsigned ThisTypeQuals = 0; 2436234982Sdim CXXRecordDecl *ThisContext = 0; 2437234982Sdim if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) { 2438234982Sdim ThisContext = Method->getParent(); 2439234982Sdim ThisTypeQuals = Method->getTypeQualifiers(); 2440234982Sdim } 2441234982Sdim 2442234982Sdim CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals, 2443249423Sdim getLangOpts().CPlusPlus11); 2444234982Sdim 2445234982Sdim ResultType = SubstType(Proto->getResultType(), 2446234982Sdim MultiLevelTemplateArgumentList(*ExplicitArgumentList), 2447234982Sdim Function->getTypeSpecStartLoc(), 2448234982Sdim Function->getDeclName()); 2449234982Sdim if (ResultType.isNull() || Trap.hasErrorOccurred()) 2450234982Sdim return TDK_SubstitutionFailure; 2451234982Sdim } 2452234982Sdim 2453234353Sdim // Instantiate the types of each of the function parameters given the 2454234353Sdim // explicitly-specified template arguments if we didn't do so earlier. 2455234353Sdim if (!Proto->hasTrailingReturn() && 2456234353Sdim SubstParmTypes(Function->getLocation(), 2457234353Sdim Function->param_begin(), Function->getNumParams(), 2458234353Sdim MultiLevelTemplateArgumentList(*ExplicitArgumentList), 2459234353Sdim ParamTypes)) 2460234353Sdim return TDK_SubstitutionFailure; 2461198092Srdivacky 2462234353Sdim if (FunctionType) { 2463249423Sdim *FunctionType = BuildFunctionType(ResultType, ParamTypes, 2464198092Srdivacky Function->getLocation(), 2465212904Sdim Function->getDeclName(), 2466249423Sdim Proto->getExtProtoInfo()); 2467198092Srdivacky if (FunctionType->isNull() || Trap.hasErrorOccurred()) 2468198092Srdivacky return TDK_SubstitutionFailure; 2469198092Srdivacky } 2470198092Srdivacky 2471198092Srdivacky // C++ [temp.arg.explicit]p2: 2472198092Srdivacky // Trailing template arguments that can be deduced (14.8.2) may be 2473198092Srdivacky // omitted from the list of explicit template-arguments. If all of the 2474198092Srdivacky // template arguments can be deduced, they may all be omitted; in this 2475198092Srdivacky // case, the empty template argument list <> itself may also be omitted. 2476198092Srdivacky // 2477218893Sdim // Take all of the explicitly-specified arguments and put them into 2478218893Sdim // the set of deduced template arguments. Explicitly-specified 2479218893Sdim // parameter packs, however, will be set to NULL since the deduction 2480218893Sdim // mechanisms handle explicitly-specified argument packs directly. 2481198092Srdivacky Deduced.reserve(TemplateParams->size()); 2482218893Sdim for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) { 2483218893Sdim const TemplateArgument &Arg = ExplicitArgumentList->get(I); 2484218893Sdim if (Arg.getKind() == TemplateArgument::Pack) 2485218893Sdim Deduced.push_back(DeducedTemplateArgument()); 2486218893Sdim else 2487218893Sdim Deduced.push_back(Arg); 2488218893Sdim } 2489198092Srdivacky 2490198092Srdivacky return TDK_Success; 2491198092Srdivacky} 2492198092Srdivacky 2493224145Sdim/// \brief Check whether the deduced argument type for a call to a function 2494224145Sdim/// template matches the actual argument type per C++ [temp.deduct.call]p4. 2495224145Sdimstatic bool 2496224145SdimCheckOriginalCallArgDeduction(Sema &S, Sema::OriginalCallArg OriginalArg, 2497224145Sdim QualType DeducedA) { 2498224145Sdim ASTContext &Context = S.Context; 2499224145Sdim 2500224145Sdim QualType A = OriginalArg.OriginalArgType; 2501224145Sdim QualType OriginalParamType = OriginalArg.OriginalParamType; 2502224145Sdim 2503224145Sdim // Check for type equality (top-level cv-qualifiers are ignored). 2504224145Sdim if (Context.hasSameUnqualifiedType(A, DeducedA)) 2505224145Sdim return false; 2506224145Sdim 2507224145Sdim // Strip off references on the argument types; they aren't needed for 2508224145Sdim // the following checks. 2509224145Sdim if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>()) 2510224145Sdim DeducedA = DeducedARef->getPointeeType(); 2511224145Sdim if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 2512224145Sdim A = ARef->getPointeeType(); 2513224145Sdim 2514224145Sdim // C++ [temp.deduct.call]p4: 2515224145Sdim // [...] However, there are three cases that allow a difference: 2516224145Sdim // - If the original P is a reference type, the deduced A (i.e., the 2517224145Sdim // type referred to by the reference) can be more cv-qualified than 2518224145Sdim // the transformed A. 2519224145Sdim if (const ReferenceType *OriginalParamRef 2520224145Sdim = OriginalParamType->getAs<ReferenceType>()) { 2521224145Sdim // We don't want to keep the reference around any more. 2522224145Sdim OriginalParamType = OriginalParamRef->getPointeeType(); 2523224145Sdim 2524224145Sdim Qualifiers AQuals = A.getQualifiers(); 2525224145Sdim Qualifiers DeducedAQuals = DeducedA.getQualifiers(); 2526239462Sdim 2527239462Sdim // Under Objective-C++ ARC, the deduced type may have implicitly been 2528239462Sdim // given strong lifetime. If so, update the original qualifiers to 2529239462Sdim // include this strong lifetime. 2530239462Sdim if (S.getLangOpts().ObjCAutoRefCount && 2531239462Sdim DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong && 2532239462Sdim AQuals.getObjCLifetime() == Qualifiers::OCL_None) { 2533239462Sdim AQuals.setObjCLifetime(Qualifiers::OCL_Strong); 2534239462Sdim } 2535239462Sdim 2536224145Sdim if (AQuals == DeducedAQuals) { 2537224145Sdim // Qualifiers match; there's nothing to do. 2538224145Sdim } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) { 2539224145Sdim return true; 2540224145Sdim } else { 2541224145Sdim // Qualifiers are compatible, so have the argument type adopt the 2542224145Sdim // deduced argument type's qualifiers as if we had performed the 2543224145Sdim // qualification conversion. 2544224145Sdim A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals); 2545224145Sdim } 2546224145Sdim } 2547224145Sdim 2548224145Sdim // - The transformed A can be another pointer or pointer to member 2549224145Sdim // type that can be converted to the deduced A via a qualification 2550224145Sdim // conversion. 2551224145Sdim // 2552224145Sdim // Also allow conversions which merely strip [[noreturn]] from function types 2553224145Sdim // (recursively) as an extension. 2554224145Sdim // FIXME: Currently, this doesn't place nicely with qualfication conversions. 2555224145Sdim bool ObjCLifetimeConversion = false; 2556224145Sdim QualType ResultTy; 2557224145Sdim if ((A->isAnyPointerType() || A->isMemberPointerType()) && 2558224145Sdim (S.IsQualificationConversion(A, DeducedA, false, 2559224145Sdim ObjCLifetimeConversion) || 2560224145Sdim S.IsNoReturnConversion(A, DeducedA, ResultTy))) 2561224145Sdim return false; 2562224145Sdim 2563224145Sdim 2564224145Sdim // - If P is a class and P has the form simple-template-id, then the 2565224145Sdim // transformed A can be a derived class of the deduced A. [...] 2566224145Sdim // [...] Likewise, if P is a pointer to a class of the form 2567224145Sdim // simple-template-id, the transformed A can be a pointer to a 2568224145Sdim // derived class pointed to by the deduced A. 2569224145Sdim if (const PointerType *OriginalParamPtr 2570224145Sdim = OriginalParamType->getAs<PointerType>()) { 2571224145Sdim if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) { 2572224145Sdim if (const PointerType *APtr = A->getAs<PointerType>()) { 2573224145Sdim if (A->getPointeeType()->isRecordType()) { 2574224145Sdim OriginalParamType = OriginalParamPtr->getPointeeType(); 2575224145Sdim DeducedA = DeducedAPtr->getPointeeType(); 2576224145Sdim A = APtr->getPointeeType(); 2577224145Sdim } 2578224145Sdim } 2579224145Sdim } 2580224145Sdim } 2581224145Sdim 2582224145Sdim if (Context.hasSameUnqualifiedType(A, DeducedA)) 2583224145Sdim return false; 2584224145Sdim 2585224145Sdim if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) && 2586224145Sdim S.IsDerivedFrom(A, DeducedA)) 2587224145Sdim return false; 2588224145Sdim 2589224145Sdim return true; 2590224145Sdim} 2591224145Sdim 2592198092Srdivacky/// \brief Finish template argument deduction for a function template, 2593198092Srdivacky/// checking the deduced template arguments for completeness and forming 2594198092Srdivacky/// the function template specialization. 2595224145Sdim/// 2596224145Sdim/// \param OriginalCallArgs If non-NULL, the original call arguments against 2597224145Sdim/// which the deduced argument types should be compared. 2598198092SrdivackySema::TemplateDeductionResult 2599198092SrdivackySema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate, 2600226633Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2601206084Srdivacky unsigned NumExplicitlySpecified, 2602198092Srdivacky FunctionDecl *&Specialization, 2603224145Sdim TemplateDeductionInfo &Info, 2604226633Sdim SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs) { 2605198092Srdivacky TemplateParameterList *TemplateParams 2606198092Srdivacky = FunctionTemplate->getTemplateParameters(); 2607198092Srdivacky 2608234353Sdim // Unevaluated SFINAE context. 2609234353Sdim EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 2610199990Srdivacky SFINAETrap Trap(*this); 2611199990Srdivacky 2612199990Srdivacky // Enter a new template instantiation context while we instantiate the 2613199990Srdivacky // actual function declaration. 2614239462Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end()); 2615199990Srdivacky InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 2616239462Sdim FunctionTemplate, DeducedArgs, 2617218893Sdim ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution, 2618218893Sdim Info); 2619199990Srdivacky if (Inst) 2620199990Srdivacky return TDK_InstantiationDepth; 2621199990Srdivacky 2622207619Srdivacky ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 2623207619Srdivacky 2624198092Srdivacky // C++ [temp.deduct.type]p2: 2625198092Srdivacky // [...] or if any template argument remains neither deduced nor 2626198092Srdivacky // explicitly specified, template argument deduction fails. 2627226633Sdim SmallVector<TemplateArgument, 4> Builder; 2628218893Sdim for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) { 2629218893Sdim NamedDecl *Param = TemplateParams->getParam(I); 2630218893Sdim 2631199990Srdivacky if (!Deduced[I].isNull()) { 2632218893Sdim if (I < NumExplicitlySpecified) { 2633206084Srdivacky // We have already fully type-checked and converted this 2634218893Sdim // argument, because it was explicitly-specified. Just record the 2635218893Sdim // presence of this argument. 2636218893Sdim Builder.push_back(Deduced[I]); 2637206084Srdivacky continue; 2638206084Srdivacky } 2639206084Srdivacky 2640206084Srdivacky // We have deduced this argument, so it still needs to be 2641206084Srdivacky // checked and converted. 2642206084Srdivacky 2643206084Srdivacky // First, for a non-type template parameter type that is 2644206084Srdivacky // initialized by a declaration, we need the type of the 2645206084Srdivacky // corresponding non-type template parameter. 2646206084Srdivacky QualType NTTPType; 2647218893Sdim if (NonTypeTemplateParmDecl *NTTP 2648218893Sdim = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 2649218893Sdim NTTPType = NTTP->getType(); 2650218893Sdim if (NTTPType->isDependentType()) { 2651218893Sdim TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, 2652218893Sdim Builder.data(), Builder.size()); 2653218893Sdim NTTPType = SubstType(NTTPType, 2654218893Sdim MultiLevelTemplateArgumentList(TemplateArgs), 2655218893Sdim NTTP->getLocation(), 2656218893Sdim NTTP->getDeclName()); 2657218893Sdim if (NTTPType.isNull()) { 2658218893Sdim Info.Param = makeTemplateParameter(Param); 2659218893Sdim // FIXME: These template arguments are temporary. Free them! 2660218893Sdim Info.reset(TemplateArgumentList::CreateCopy(Context, 2661218893Sdim Builder.data(), 2662218893Sdim Builder.size())); 2663218893Sdim return TDK_SubstitutionFailure; 2664206084Srdivacky } 2665206084Srdivacky } 2666206084Srdivacky } 2667206084Srdivacky 2668218893Sdim if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I], 2669218893Sdim FunctionTemplate, NTTPType, 0, Info, 2670218893Sdim true, Builder)) { 2671218893Sdim Info.Param = makeTemplateParameter(Param); 2672218893Sdim // FIXME: These template arguments are temporary. Free them! 2673218893Sdim Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 2674218893Sdim Builder.size())); 2675206084Srdivacky return TDK_SubstitutionFailure; 2676206084Srdivacky } 2677206084Srdivacky 2678199990Srdivacky continue; 2679199990Srdivacky } 2680199990Srdivacky 2681218893Sdim // C++0x [temp.arg.explicit]p3: 2682218893Sdim // A trailing template parameter pack (14.5.3) not otherwise deduced will 2683218893Sdim // be deduced to an empty sequence of template arguments. 2684218893Sdim // FIXME: Where did the word "trailing" come from? 2685218893Sdim if (Param->isTemplateParameterPack()) { 2686218893Sdim // We may have had explicitly-specified template arguments for this 2687218893Sdim // template parameter pack. If so, our empty deduction extends the 2688218893Sdim // explicitly-specified set (C++0x [temp.arg.explicit]p9). 2689218893Sdim const TemplateArgument *ExplicitArgs; 2690218893Sdim unsigned NumExplicitArgs; 2691243830Sdim if (CurrentInstantiationScope && 2692243830Sdim CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs, 2693218893Sdim &NumExplicitArgs) 2694249423Sdim == Param) { 2695218893Sdim Builder.push_back(TemplateArgument(ExplicitArgs, NumExplicitArgs)); 2696249423Sdim 2697249423Sdim // Forget the partially-substituted pack; it's substitution is now 2698249423Sdim // complete. 2699249423Sdim CurrentInstantiationScope->ResetPartiallySubstitutedPack(); 2700249423Sdim } else { 2701243830Sdim Builder.push_back(TemplateArgument::getEmptyPack()); 2702249423Sdim } 2703218893Sdim continue; 2704218893Sdim } 2705218893Sdim 2706218893Sdim // Substitute into the default template argument, if available. 2707199990Srdivacky TemplateArgumentLoc DefArg 2708199990Srdivacky = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate, 2709199990Srdivacky FunctionTemplate->getLocation(), 2710199990Srdivacky FunctionTemplate->getSourceRange().getEnd(), 2711199990Srdivacky Param, 2712199990Srdivacky Builder); 2713199990Srdivacky 2714199990Srdivacky // If there was no default argument, deduction is incomplete. 2715199990Srdivacky if (DefArg.getArgument().isNull()) { 2716198092Srdivacky Info.Param = makeTemplateParameter( 2717199990Srdivacky const_cast<NamedDecl *>(TemplateParams->getParam(I))); 2718198092Srdivacky return TDK_Incomplete; 2719198092Srdivacky } 2720218893Sdim 2721199990Srdivacky // Check whether we can actually use the default argument. 2722199990Srdivacky if (CheckTemplateArgument(Param, DefArg, 2723199990Srdivacky FunctionTemplate, 2724199990Srdivacky FunctionTemplate->getLocation(), 2725199990Srdivacky FunctionTemplate->getSourceRange().getEnd(), 2726218893Sdim 0, Builder, 2727223017Sdim CTAK_Specified)) { 2728199990Srdivacky Info.Param = makeTemplateParameter( 2729199990Srdivacky const_cast<NamedDecl *>(TemplateParams->getParam(I))); 2730218893Sdim // FIXME: These template arguments are temporary. Free them! 2731218893Sdim Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(), 2732218893Sdim Builder.size())); 2733199990Srdivacky return TDK_SubstitutionFailure; 2734199990Srdivacky } 2735198092Srdivacky 2736199990Srdivacky // If we get here, we successfully used the default template argument. 2737198092Srdivacky } 2738198092Srdivacky 2739198092Srdivacky // Form the template argument list from the deduced template arguments. 2740198092Srdivacky TemplateArgumentList *DeducedArgumentList 2741218893Sdim = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size()); 2742198092Srdivacky Info.reset(DeducedArgumentList); 2743198092Srdivacky 2744198092Srdivacky // Substitute the deduced template arguments into the function template 2745198092Srdivacky // declaration to produce the function template specialization. 2746207619Srdivacky DeclContext *Owner = FunctionTemplate->getDeclContext(); 2747207619Srdivacky if (FunctionTemplate->getFriendObjectKind()) 2748207619Srdivacky Owner = FunctionTemplate->getLexicalDeclContext(); 2749198092Srdivacky Specialization = cast_or_null<FunctionDecl>( 2750207619Srdivacky SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner, 2751198092Srdivacky MultiLevelTemplateArgumentList(*DeducedArgumentList))); 2752226633Sdim if (!Specialization || Specialization->isInvalidDecl()) 2753198092Srdivacky return TDK_SubstitutionFailure; 2754198092Srdivacky 2755218893Sdim assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() == 2756198092Srdivacky FunctionTemplate->getCanonicalDecl()); 2757218893Sdim 2758198092Srdivacky // If the template argument list is owned by the function template 2759198092Srdivacky // specialization, release it. 2760208600Srdivacky if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList && 2761208600Srdivacky !Trap.hasErrorOccurred()) 2762198092Srdivacky Info.take(); 2763198092Srdivacky 2764226633Sdim // There may have been an error that did not prevent us from constructing a 2765226633Sdim // declaration. Mark the declaration invalid and return with a substitution 2766226633Sdim // failure. 2767226633Sdim if (Trap.hasErrorOccurred()) { 2768226633Sdim Specialization->setInvalidDecl(true); 2769226633Sdim return TDK_SubstitutionFailure; 2770226633Sdim } 2771226633Sdim 2772224145Sdim if (OriginalCallArgs) { 2773224145Sdim // C++ [temp.deduct.call]p4: 2774224145Sdim // In general, the deduction process attempts to find template argument 2775224145Sdim // values that will make the deduced A identical to A (after the type A 2776224145Sdim // is transformed as described above). [...] 2777224145Sdim for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) { 2778224145Sdim OriginalCallArg OriginalArg = (*OriginalCallArgs)[I]; 2779224145Sdim unsigned ParamIdx = OriginalArg.ArgIdx; 2780224145Sdim 2781224145Sdim if (ParamIdx >= Specialization->getNumParams()) 2782224145Sdim continue; 2783224145Sdim 2784224145Sdim QualType DeducedA = Specialization->getParamDecl(ParamIdx)->getType(); 2785224145Sdim if (CheckOriginalCallArgDeduction(*this, OriginalArg, DeducedA)) 2786224145Sdim return Sema::TDK_SubstitutionFailure; 2787224145Sdim } 2788224145Sdim } 2789224145Sdim 2790218893Sdim // If we suppressed any diagnostics while performing template argument 2791218893Sdim // deduction, and if we haven't already instantiated this declaration, 2792218893Sdim // keep track of these diagnostics. They'll be emitted if this specialization 2793218893Sdim // is actually used. 2794218893Sdim if (Info.diag_begin() != Info.diag_end()) { 2795226633Sdim llvm::DenseMap<Decl *, SmallVector<PartialDiagnosticAt, 1> >::iterator 2796218893Sdim Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl()); 2797218893Sdim if (Pos == SuppressedDiagnostics.end()) 2798218893Sdim SuppressedDiagnostics[Specialization->getCanonicalDecl()] 2799218893Sdim .append(Info.diag_begin(), Info.diag_end()); 2800218893Sdim } 2801218893Sdim 2802198092Srdivacky return TDK_Success; 2803198092Srdivacky} 2804198092Srdivacky 2805212904Sdim/// Gets the type of a function for template-argument-deducton 2806212904Sdim/// purposes when it's considered as part of an overload set. 2807251662Sdimstatic QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R, 2808203955Srdivacky FunctionDecl *Fn) { 2809251662Sdim // We may need to deduce the return type of the function now. 2810251662Sdim if (S.getLangOpts().CPlusPlus1y && Fn->getResultType()->isUndeducedType() && 2811251662Sdim S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/false)) 2812251662Sdim return QualType(); 2813251662Sdim 2814203955Srdivacky if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn)) 2815212904Sdim if (Method->isInstance()) { 2816212904Sdim // An instance method that's referenced in a form that doesn't 2817212904Sdim // look like a member pointer is just invalid. 2818212904Sdim if (!R.HasFormOfMemberPointer) return QualType(); 2819212904Sdim 2820251662Sdim return S.Context.getMemberPointerType(Fn->getType(), 2821251662Sdim S.Context.getTypeDeclType(Method->getParent()).getTypePtr()); 2822212904Sdim } 2823212904Sdim 2824212904Sdim if (!R.IsAddressOfOperand) return Fn->getType(); 2825251662Sdim return S.Context.getPointerType(Fn->getType()); 2826203955Srdivacky} 2827203955Srdivacky 2828203955Srdivacky/// Apply the deduction rules for overload sets. 2829203955Srdivacky/// 2830203955Srdivacky/// \return the null type if this argument should be treated as an 2831203955Srdivacky/// undeduced context 2832203955Srdivackystatic QualType 2833203955SrdivackyResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams, 2834212904Sdim Expr *Arg, QualType ParamType, 2835212904Sdim bool ParamWasReference) { 2836218893Sdim 2837212904Sdim OverloadExpr::FindResult R = OverloadExpr::find(Arg); 2838203955Srdivacky 2839212904Sdim OverloadExpr *Ovl = R.Expression; 2840203955Srdivacky 2841212904Sdim // C++0x [temp.deduct.call]p4 2842212904Sdim unsigned TDF = 0; 2843212904Sdim if (ParamWasReference) 2844212904Sdim TDF |= TDF_ParamWithReferenceType; 2845212904Sdim if (R.IsAddressOfOperand) 2846212904Sdim TDF |= TDF_IgnoreQualifiers; 2847212904Sdim 2848203955Srdivacky // C++0x [temp.deduct.call]p6: 2849203955Srdivacky // When P is a function type, pointer to function type, or pointer 2850203955Srdivacky // to member function type: 2851203955Srdivacky 2852203955Srdivacky if (!ParamType->isFunctionType() && 2853203955Srdivacky !ParamType->isFunctionPointerType() && 2854234353Sdim !ParamType->isMemberFunctionPointerType()) { 2855234353Sdim if (Ovl->hasExplicitTemplateArgs()) { 2856234353Sdim // But we can still look for an explicit specialization. 2857234353Sdim if (FunctionDecl *ExplicitSpec 2858234353Sdim = S.ResolveSingleFunctionTemplateSpecialization(Ovl)) 2859251662Sdim return GetTypeOfFunction(S, R, ExplicitSpec); 2860234353Sdim } 2861234353Sdim 2862203955Srdivacky return QualType(); 2863234353Sdim } 2864234353Sdim 2865234353Sdim // Gather the explicit template arguments, if any. 2866234353Sdim TemplateArgumentListInfo ExplicitTemplateArgs; 2867234353Sdim if (Ovl->hasExplicitTemplateArgs()) 2868234353Sdim Ovl->getExplicitTemplateArgs().copyInto(ExplicitTemplateArgs); 2869203955Srdivacky QualType Match; 2870203955Srdivacky for (UnresolvedSetIterator I = Ovl->decls_begin(), 2871203955Srdivacky E = Ovl->decls_end(); I != E; ++I) { 2872203955Srdivacky NamedDecl *D = (*I)->getUnderlyingDecl(); 2873203955Srdivacky 2874234353Sdim if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) { 2875234353Sdim // - If the argument is an overload set containing one or more 2876234353Sdim // function templates, the parameter is treated as a 2877234353Sdim // non-deduced context. 2878234353Sdim if (!Ovl->hasExplicitTemplateArgs()) 2879234353Sdim return QualType(); 2880234353Sdim 2881234353Sdim // Otherwise, see if we can resolve a function type 2882234353Sdim FunctionDecl *Specialization = 0; 2883243830Sdim TemplateDeductionInfo Info(Ovl->getNameLoc()); 2884234353Sdim if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs, 2885234353Sdim Specialization, Info)) 2886234353Sdim continue; 2887234353Sdim 2888234353Sdim D = Specialization; 2889234353Sdim } 2890203955Srdivacky 2891203955Srdivacky FunctionDecl *Fn = cast<FunctionDecl>(D); 2892251662Sdim QualType ArgType = GetTypeOfFunction(S, R, Fn); 2893212904Sdim if (ArgType.isNull()) continue; 2894203955Srdivacky 2895212904Sdim // Function-to-pointer conversion. 2896218893Sdim if (!ParamWasReference && ParamType->isPointerType() && 2897212904Sdim ArgType->isFunctionType()) 2898212904Sdim ArgType = S.Context.getPointerType(ArgType); 2899218893Sdim 2900203955Srdivacky // - If the argument is an overload set (not containing function 2901203955Srdivacky // templates), trial argument deduction is attempted using each 2902203955Srdivacky // of the members of the set. If deduction succeeds for only one 2903203955Srdivacky // of the overload set members, that member is used as the 2904203955Srdivacky // argument value for the deduction. If deduction succeeds for 2905203955Srdivacky // more than one member of the overload set the parameter is 2906203955Srdivacky // treated as a non-deduced context. 2907203955Srdivacky 2908203955Srdivacky // We do all of this in a fresh context per C++0x [temp.deduct.type]p2: 2909203955Srdivacky // Type deduction is done independently for each P/A pair, and 2910203955Srdivacky // the deduced template argument values are then combined. 2911203955Srdivacky // So we do not reject deductions which were made elsewhere. 2912226633Sdim SmallVector<DeducedTemplateArgument, 8> 2913206084Srdivacky Deduced(TemplateParams->size()); 2914243830Sdim TemplateDeductionInfo Info(Ovl->getNameLoc()); 2915203955Srdivacky Sema::TemplateDeductionResult Result 2916234353Sdim = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType, 2917234353Sdim ArgType, Info, Deduced, TDF); 2918203955Srdivacky if (Result) continue; 2919203955Srdivacky if (!Match.isNull()) return QualType(); 2920203955Srdivacky Match = ArgType; 2921203955Srdivacky } 2922203955Srdivacky 2923203955Srdivacky return Match; 2924203955Srdivacky} 2925203955Srdivacky 2926218893Sdim/// \brief Perform the adjustments to the parameter and argument types 2927218893Sdim/// described in C++ [temp.deduct.call]. 2928218893Sdim/// 2929218893Sdim/// \returns true if the caller should not attempt to perform any template 2930249423Sdim/// argument deduction based on this P/A pair because the argument is an 2931249423Sdim/// overloaded function set that could not be resolved. 2932218893Sdimstatic bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S, 2933218893Sdim TemplateParameterList *TemplateParams, 2934218893Sdim QualType &ParamType, 2935218893Sdim QualType &ArgType, 2936218893Sdim Expr *Arg, 2937218893Sdim unsigned &TDF) { 2938218893Sdim // C++0x [temp.deduct.call]p3: 2939218893Sdim // If P is a cv-qualified type, the top level cv-qualifiers of P's type 2940218893Sdim // are ignored for type deduction. 2941221345Sdim if (ParamType.hasQualifiers()) 2942221345Sdim ParamType = ParamType.getUnqualifiedType(); 2943218893Sdim const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>(); 2944218893Sdim if (ParamRefType) { 2945218893Sdim QualType PointeeType = ParamRefType->getPointeeType(); 2946218893Sdim 2947249423Sdim // If the argument has incomplete array type, try to complete its type. 2948239462Sdim if (ArgType->isIncompleteArrayType() && !S.RequireCompleteExprType(Arg, 0)) 2949223017Sdim ArgType = Arg->getType(); 2950223017Sdim 2951218893Sdim // [C++0x] If P is an rvalue reference to a cv-unqualified 2952218893Sdim // template parameter and the argument is an lvalue, the type 2953218893Sdim // "lvalue reference to A" is used in place of A for type 2954218893Sdim // deduction. 2955218893Sdim if (isa<RValueReferenceType>(ParamType)) { 2956218893Sdim if (!PointeeType.getQualifiers() && 2957218893Sdim isa<TemplateTypeParmType>(PointeeType) && 2958223017Sdim Arg->Classify(S.Context).isLValue() && 2959223017Sdim Arg->getType() != S.Context.OverloadTy && 2960223017Sdim Arg->getType() != S.Context.BoundMemberTy) 2961218893Sdim ArgType = S.Context.getLValueReferenceType(ArgType); 2962218893Sdim } 2963218893Sdim 2964218893Sdim // [...] If P is a reference type, the type referred to by P is used 2965218893Sdim // for type deduction. 2966218893Sdim ParamType = PointeeType; 2967218893Sdim } 2968218893Sdim 2969218893Sdim // Overload sets usually make this parameter an undeduced 2970218893Sdim // context, but there are sometimes special circumstances. 2971218893Sdim if (ArgType == S.Context.OverloadTy) { 2972218893Sdim ArgType = ResolveOverloadForDeduction(S, TemplateParams, 2973218893Sdim Arg, ParamType, 2974218893Sdim ParamRefType != 0); 2975218893Sdim if (ArgType.isNull()) 2976218893Sdim return true; 2977218893Sdim } 2978218893Sdim 2979218893Sdim if (ParamRefType) { 2980218893Sdim // C++0x [temp.deduct.call]p3: 2981218893Sdim // [...] If P is of the form T&&, where T is a template parameter, and 2982218893Sdim // the argument is an lvalue, the type A& is used in place of A for 2983218893Sdim // type deduction. 2984218893Sdim if (ParamRefType->isRValueReferenceType() && 2985218893Sdim ParamRefType->getAs<TemplateTypeParmType>() && 2986218893Sdim Arg->isLValue()) 2987218893Sdim ArgType = S.Context.getLValueReferenceType(ArgType); 2988218893Sdim } else { 2989218893Sdim // C++ [temp.deduct.call]p2: 2990218893Sdim // If P is not a reference type: 2991218893Sdim // - If A is an array type, the pointer type produced by the 2992218893Sdim // array-to-pointer standard conversion (4.2) is used in place of 2993218893Sdim // A for type deduction; otherwise, 2994218893Sdim if (ArgType->isArrayType()) 2995218893Sdim ArgType = S.Context.getArrayDecayedType(ArgType); 2996218893Sdim // - If A is a function type, the pointer type produced by the 2997218893Sdim // function-to-pointer standard conversion (4.3) is used in place 2998218893Sdim // of A for type deduction; otherwise, 2999218893Sdim else if (ArgType->isFunctionType()) 3000218893Sdim ArgType = S.Context.getPointerType(ArgType); 3001218893Sdim else { 3002218893Sdim // - If A is a cv-qualified type, the top level cv-qualifiers of A's 3003218893Sdim // type are ignored for type deduction. 3004221345Sdim ArgType = ArgType.getUnqualifiedType(); 3005218893Sdim } 3006218893Sdim } 3007218893Sdim 3008218893Sdim // C++0x [temp.deduct.call]p4: 3009218893Sdim // In general, the deduction process attempts to find template argument 3010218893Sdim // values that will make the deduced A identical to A (after the type A 3011218893Sdim // is transformed as described above). [...] 3012218893Sdim TDF = TDF_SkipNonDependent; 3013218893Sdim 3014218893Sdim // - If the original P is a reference type, the deduced A (i.e., the 3015218893Sdim // type referred to by the reference) can be more cv-qualified than 3016218893Sdim // the transformed A. 3017218893Sdim if (ParamRefType) 3018218893Sdim TDF |= TDF_ParamWithReferenceType; 3019218893Sdim // - The transformed A can be another pointer or pointer to member 3020218893Sdim // type that can be converted to the deduced A via a qualification 3021218893Sdim // conversion (4.4). 3022218893Sdim if (ArgType->isPointerType() || ArgType->isMemberPointerType() || 3023218893Sdim ArgType->isObjCObjectPointerType()) 3024218893Sdim TDF |= TDF_IgnoreQualifiers; 3025218893Sdim // - If P is a class and P has the form simple-template-id, then the 3026218893Sdim // transformed A can be a derived class of the deduced A. Likewise, 3027218893Sdim // if P is a pointer to a class of the form simple-template-id, the 3028218893Sdim // transformed A can be a pointer to a derived class pointed to by 3029218893Sdim // the deduced A. 3030218893Sdim if (isSimpleTemplateIdType(ParamType) || 3031218893Sdim (isa<PointerType>(ParamType) && 3032218893Sdim isSimpleTemplateIdType( 3033218893Sdim ParamType->getAs<PointerType>()->getPointeeType()))) 3034218893Sdim TDF |= TDF_DerivedClass; 3035218893Sdim 3036218893Sdim return false; 3037218893Sdim} 3038218893Sdim 3039224145Sdimstatic bool hasDeducibleTemplateParameters(Sema &S, 3040224145Sdim FunctionTemplateDecl *FunctionTemplate, 3041224145Sdim QualType T); 3042224145Sdim 3043234353Sdim/// \brief Perform template argument deduction by matching a parameter type 3044234353Sdim/// against a single expression, where the expression is an element of 3045249423Sdim/// an initializer list that was originally matched against a parameter 3046249423Sdim/// of type \c initializer_list\<ParamType\>. 3047234353Sdimstatic Sema::TemplateDeductionResult 3048234353SdimDeduceTemplateArgumentByListElement(Sema &S, 3049234353Sdim TemplateParameterList *TemplateParams, 3050234353Sdim QualType ParamType, Expr *Arg, 3051234353Sdim TemplateDeductionInfo &Info, 3052234353Sdim SmallVectorImpl<DeducedTemplateArgument> &Deduced, 3053234353Sdim unsigned TDF) { 3054234353Sdim // Handle the case where an init list contains another init list as the 3055234353Sdim // element. 3056234353Sdim if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) { 3057234353Sdim QualType X; 3058234353Sdim if (!S.isStdInitializerList(ParamType.getNonReferenceType(), &X)) 3059234353Sdim return Sema::TDK_Success; // Just ignore this expression. 3060234353Sdim 3061234353Sdim // Recurse down into the init list. 3062234353Sdim for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) { 3063234353Sdim if (Sema::TemplateDeductionResult Result = 3064234353Sdim DeduceTemplateArgumentByListElement(S, TemplateParams, X, 3065234353Sdim ILE->getInit(i), 3066234353Sdim Info, Deduced, TDF)) 3067234353Sdim return Result; 3068234353Sdim } 3069234353Sdim return Sema::TDK_Success; 3070234353Sdim } 3071234353Sdim 3072234353Sdim // For all other cases, just match by type. 3073234353Sdim QualType ArgType = Arg->getType(); 3074234353Sdim if (AdjustFunctionParmAndArgTypesForDeduction(S, TemplateParams, ParamType, 3075249423Sdim ArgType, Arg, TDF)) { 3076249423Sdim Info.Expression = Arg; 3077234353Sdim return Sema::TDK_FailedOverloadResolution; 3078249423Sdim } 3079234353Sdim return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType, 3080234353Sdim ArgType, Info, Deduced, TDF); 3081234353Sdim} 3082234353Sdim 3083195099Sed/// \brief Perform template argument deduction from a function call 3084195099Sed/// (C++ [temp.deduct.call]). 3085195099Sed/// 3086195099Sed/// \param FunctionTemplate the function template for which we are performing 3087195099Sed/// template argument deduction. 3088195099Sed/// 3089239462Sdim/// \param ExplicitTemplateArgs the explicit template arguments provided 3090202379Srdivacky/// for this call. 3091195341Sed/// 3092195099Sed/// \param Args the function call arguments 3093195099Sed/// 3094195099Sed/// \param Specialization if template argument deduction was successful, 3095198092Srdivacky/// this will be set to the function template specialization produced by 3096195099Sed/// template argument deduction. 3097195099Sed/// 3098195099Sed/// \param Info the argument will be updated to provide additional information 3099195099Sed/// about template argument deduction. 3100195099Sed/// 3101195099Sed/// \returns the result of template argument deduction. 3102195099SedSema::TemplateDeductionResult 3103195099SedSema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 3104221345Sdim TemplateArgumentListInfo *ExplicitTemplateArgs, 3105234353Sdim llvm::ArrayRef<Expr *> Args, 3106195099Sed FunctionDecl *&Specialization, 3107195099Sed TemplateDeductionInfo &Info) { 3108243830Sdim if (FunctionTemplate->isInvalidDecl()) 3109243830Sdim return TDK_Invalid; 3110243830Sdim 3111195099Sed FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 3112195341Sed 3113195099Sed // C++ [temp.deduct.call]p1: 3114195099Sed // Template argument deduction is done by comparing each function template 3115195099Sed // parameter type (call it P) with the type of the corresponding argument 3116195099Sed // of the call (call it A) as described below. 3117234353Sdim unsigned CheckArgs = Args.size(); 3118234353Sdim if (Args.size() < Function->getMinRequiredArguments()) 3119195099Sed return TDK_TooFewArguments; 3120234353Sdim else if (Args.size() > Function->getNumParams()) { 3121198092Srdivacky const FunctionProtoType *Proto 3122198092Srdivacky = Function->getType()->getAs<FunctionProtoType>(); 3123218893Sdim if (Proto->isTemplateVariadic()) 3124218893Sdim /* Do nothing */; 3125218893Sdim else if (Proto->isVariadic()) 3126218893Sdim CheckArgs = Function->getNumParams(); 3127218893Sdim else 3128195099Sed return TDK_TooManyArguments; 3129195099Sed } 3130195341Sed 3131195341Sed // The types of the parameters from which we will perform template argument 3132195341Sed // deduction. 3133212904Sdim LocalInstantiationScope InstScope(*this); 3134195341Sed TemplateParameterList *TemplateParams 3135195341Sed = FunctionTemplate->getTemplateParameters(); 3136226633Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 3137226633Sdim SmallVector<QualType, 4> ParamTypes; 3138206084Srdivacky unsigned NumExplicitlySpecified = 0; 3139199990Srdivacky if (ExplicitTemplateArgs) { 3140198092Srdivacky TemplateDeductionResult Result = 3141198092Srdivacky SubstituteExplicitTemplateArguments(FunctionTemplate, 3142199990Srdivacky *ExplicitTemplateArgs, 3143198092Srdivacky Deduced, 3144198092Srdivacky ParamTypes, 3145198092Srdivacky 0, 3146198092Srdivacky Info); 3147198092Srdivacky if (Result) 3148198092Srdivacky return Result; 3149206084Srdivacky 3150206084Srdivacky NumExplicitlySpecified = Deduced.size(); 3151195341Sed } else { 3152195341Sed // Just fill in the parameter types from the function declaration. 3153218893Sdim for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 3154195341Sed ParamTypes.push_back(Function->getParamDecl(I)->getType()); 3155195341Sed } 3156198092Srdivacky 3157195099Sed // Deduce template arguments from the function parameters. 3158198092Srdivacky Deduced.resize(TemplateParams->size()); 3159218893Sdim unsigned ArgIdx = 0; 3160226633Sdim SmallVector<OriginalCallArg, 4> OriginalCallArgs; 3161218893Sdim for (unsigned ParamIdx = 0, NumParams = ParamTypes.size(); 3162218893Sdim ParamIdx != NumParams; ++ParamIdx) { 3163224145Sdim QualType OrigParamType = ParamTypes[ParamIdx]; 3164224145Sdim QualType ParamType = OrigParamType; 3165224145Sdim 3166218893Sdim const PackExpansionType *ParamExpansion 3167218893Sdim = dyn_cast<PackExpansionType>(ParamType); 3168218893Sdim if (!ParamExpansion) { 3169218893Sdim // Simple case: matching a function parameter to a function argument. 3170218893Sdim if (ArgIdx >= CheckArgs) 3171218893Sdim break; 3172218893Sdim 3173218893Sdim Expr *Arg = Args[ArgIdx++]; 3174218893Sdim QualType ArgType = Arg->getType(); 3175224145Sdim 3176218893Sdim unsigned TDF = 0; 3177218893Sdim if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams, 3178218893Sdim ParamType, ArgType, Arg, 3179218893Sdim TDF)) 3180203955Srdivacky continue; 3181218893Sdim 3182226633Sdim // If we have nothing to deduce, we're done. 3183226633Sdim if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType)) 3184226633Sdim continue; 3185226633Sdim 3186234353Sdim // If the argument is an initializer list ... 3187234353Sdim if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) { 3188234353Sdim // ... then the parameter is an undeduced context, unless the parameter 3189234353Sdim // type is (reference to cv) std::initializer_list<P'>, in which case 3190234353Sdim // deduction is done for each element of the initializer list, and the 3191234353Sdim // result is the deduced type if it's the same for all elements. 3192234353Sdim QualType X; 3193234353Sdim // Removing references was already done. 3194234353Sdim if (!isStdInitializerList(ParamType, &X)) 3195234353Sdim continue; 3196234353Sdim 3197234353Sdim for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) { 3198234353Sdim if (TemplateDeductionResult Result = 3199234353Sdim DeduceTemplateArgumentByListElement(*this, TemplateParams, X, 3200234353Sdim ILE->getInit(i), 3201234353Sdim Info, Deduced, TDF)) 3202234353Sdim return Result; 3203234353Sdim } 3204234353Sdim // Don't track the argument type, since an initializer list has none. 3205234353Sdim continue; 3206234353Sdim } 3207234353Sdim 3208224145Sdim // Keep track of the argument type and corresponding parameter index, 3209224145Sdim // so we can check for compatibility between the deduced A and A. 3210226633Sdim OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx-1, 3211226633Sdim ArgType)); 3212224145Sdim 3213218893Sdim if (TemplateDeductionResult Result 3214234353Sdim = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3215234353Sdim ParamType, ArgType, 3216234353Sdim Info, Deduced, TDF)) 3217218893Sdim return Result; 3218218893Sdim 3219218893Sdim continue; 3220203955Srdivacky } 3221203955Srdivacky 3222218893Sdim // C++0x [temp.deduct.call]p1: 3223218893Sdim // For a function parameter pack that occurs at the end of the 3224218893Sdim // parameter-declaration-list, the type A of each remaining argument of 3225218893Sdim // the call is compared with the type P of the declarator-id of the 3226218893Sdim // function parameter pack. Each comparison deduces template arguments 3227218893Sdim // for subsequent positions in the template parameter packs expanded by 3228218893Sdim // the function parameter pack. For a function parameter pack that does 3229218893Sdim // not occur at the end of the parameter-declaration-list, the type of 3230218893Sdim // the parameter pack is a non-deduced context. 3231218893Sdim if (ParamIdx + 1 < NumParams) 3232218893Sdim break; 3233218893Sdim 3234218893Sdim QualType ParamPattern = ParamExpansion->getPattern(); 3235226633Sdim SmallVector<unsigned, 2> PackIndices; 3236218893Sdim { 3237234353Sdim llvm::SmallBitVector SawIndices(TemplateParams->size()); 3238226633Sdim SmallVector<UnexpandedParameterPack, 2> Unexpanded; 3239218893Sdim collectUnexpandedParameterPacks(ParamPattern, Unexpanded); 3240218893Sdim for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) { 3241218893Sdim unsigned Depth, Index; 3242218893Sdim llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]); 3243218893Sdim if (Depth == 0 && !SawIndices[Index]) { 3244218893Sdim SawIndices[Index] = true; 3245218893Sdim PackIndices.push_back(Index); 3246218893Sdim } 3247194179Sed } 3248195099Sed } 3249218893Sdim assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?"); 3250198092Srdivacky 3251218893Sdim // Keep track of the deduced template arguments for each parameter pack 3252218893Sdim // expanded by this pack expansion (the outer index) and for each 3253218893Sdim // template argument (the inner SmallVectors). 3254226633Sdim SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2> 3255218893Sdim NewlyDeducedPacks(PackIndices.size()); 3256226633Sdim SmallVector<DeducedTemplateArgument, 2> 3257218893Sdim SavedPacks(PackIndices.size()); 3258218893Sdim PrepareArgumentPackDeduction(*this, Deduced, PackIndices, SavedPacks, 3259218893Sdim NewlyDeducedPacks); 3260218893Sdim bool HasAnyArguments = false; 3261234353Sdim for (; ArgIdx < Args.size(); ++ArgIdx) { 3262218893Sdim HasAnyArguments = true; 3263198092Srdivacky 3264224145Sdim QualType OrigParamType = ParamPattern; 3265224145Sdim ParamType = OrigParamType; 3266218893Sdim Expr *Arg = Args[ArgIdx]; 3267218893Sdim QualType ArgType = Arg->getType(); 3268224145Sdim 3269218893Sdim unsigned TDF = 0; 3270218893Sdim if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams, 3271218893Sdim ParamType, ArgType, Arg, 3272218893Sdim TDF)) { 3273218893Sdim // We can't actually perform any deduction for this argument, so stop 3274218893Sdim // deduction at this point. 3275218893Sdim ++ArgIdx; 3276218893Sdim break; 3277218893Sdim } 3278198092Srdivacky 3279234353Sdim // As above, initializer lists need special handling. 3280234353Sdim if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) { 3281234353Sdim QualType X; 3282234353Sdim if (!isStdInitializerList(ParamType, &X)) { 3283234353Sdim ++ArgIdx; 3284234353Sdim break; 3285234353Sdim } 3286224145Sdim 3287234353Sdim for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) { 3288234353Sdim if (TemplateDeductionResult Result = 3289234353Sdim DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, X, 3290234353Sdim ILE->getInit(i)->getType(), 3291234353Sdim Info, Deduced, TDF)) 3292234353Sdim return Result; 3293234353Sdim } 3294234353Sdim } else { 3295218893Sdim 3296234353Sdim // Keep track of the argument type and corresponding argument index, 3297234353Sdim // so we can check for compatibility between the deduced A and A. 3298234353Sdim if (hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType)) 3299234353Sdim OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx, 3300234353Sdim ArgType)); 3301234353Sdim 3302234353Sdim if (TemplateDeductionResult Result 3303234353Sdim = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3304234353Sdim ParamType, ArgType, Info, 3305234353Sdim Deduced, TDF)) 3306234353Sdim return Result; 3307234353Sdim } 3308234353Sdim 3309218893Sdim // Capture the deduced template arguments for each parameter pack expanded 3310218893Sdim // by this pack expansion, add them to the list of arguments we've deduced 3311218893Sdim // for that pack, then clear out the deduced argument. 3312218893Sdim for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) { 3313218893Sdim DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]]; 3314218893Sdim if (!DeducedArg.isNull()) { 3315218893Sdim NewlyDeducedPacks[I].push_back(DeducedArg); 3316218893Sdim DeducedArg = DeducedTemplateArgument(); 3317218893Sdim } 3318218893Sdim } 3319218893Sdim } 3320218893Sdim 3321218893Sdim // Build argument packs for each of the parameter packs expanded by this 3322218893Sdim // pack expansion. 3323218893Sdim if (Sema::TemplateDeductionResult Result 3324218893Sdim = FinishArgumentPackDeduction(*this, TemplateParams, HasAnyArguments, 3325218893Sdim Deduced, PackIndices, SavedPacks, 3326218893Sdim NewlyDeducedPacks, Info)) 3327195099Sed return Result; 3328198092Srdivacky 3329218893Sdim // After we've matching against a parameter pack, we're done. 3330218893Sdim break; 3331198092Srdivacky } 3332198092Srdivacky 3333198092Srdivacky return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 3334206084Srdivacky NumExplicitlySpecified, 3335224145Sdim Specialization, Info, &OriginalCallArgs); 3336198092Srdivacky} 3337198092Srdivacky 3338198092Srdivacky/// \brief Deduce template arguments when taking the address of a function 3339201361Srdivacky/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to 3340201361Srdivacky/// a template. 3341198092Srdivacky/// 3342198092Srdivacky/// \param FunctionTemplate the function template for which we are performing 3343198092Srdivacky/// template argument deduction. 3344198092Srdivacky/// 3345239462Sdim/// \param ExplicitTemplateArgs the explicitly-specified template 3346201361Srdivacky/// arguments. 3347198092Srdivacky/// 3348198092Srdivacky/// \param ArgFunctionType the function type that will be used as the 3349198092Srdivacky/// "argument" type (A) when performing template argument deduction from the 3350201361Srdivacky/// function template's function type. This type may be NULL, if there is no 3351201361Srdivacky/// argument type to compare against, in C++0x [temp.arg.explicit]p3. 3352198092Srdivacky/// 3353198092Srdivacky/// \param Specialization if template argument deduction was successful, 3354198092Srdivacky/// this will be set to the function template specialization produced by 3355198092Srdivacky/// template argument deduction. 3356198092Srdivacky/// 3357198092Srdivacky/// \param Info the argument will be updated to provide additional information 3358198092Srdivacky/// about template argument deduction. 3359198092Srdivacky/// 3360198092Srdivacky/// \returns the result of template argument deduction. 3361198092SrdivackySema::TemplateDeductionResult 3362198092SrdivackySema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 3363221345Sdim TemplateArgumentListInfo *ExplicitTemplateArgs, 3364198092Srdivacky QualType ArgFunctionType, 3365198092Srdivacky FunctionDecl *&Specialization, 3366251662Sdim TemplateDeductionInfo &Info, 3367251662Sdim bool InOverloadResolution) { 3368243830Sdim if (FunctionTemplate->isInvalidDecl()) 3369243830Sdim return TDK_Invalid; 3370243830Sdim 3371198092Srdivacky FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 3372198092Srdivacky TemplateParameterList *TemplateParams 3373198092Srdivacky = FunctionTemplate->getTemplateParameters(); 3374198092Srdivacky QualType FunctionType = Function->getType(); 3375198092Srdivacky 3376198092Srdivacky // Substitute any explicit template arguments. 3377212904Sdim LocalInstantiationScope InstScope(*this); 3378226633Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 3379206084Srdivacky unsigned NumExplicitlySpecified = 0; 3380226633Sdim SmallVector<QualType, 4> ParamTypes; 3381199990Srdivacky if (ExplicitTemplateArgs) { 3382198092Srdivacky if (TemplateDeductionResult Result 3383198092Srdivacky = SubstituteExplicitTemplateArguments(FunctionTemplate, 3384199990Srdivacky *ExplicitTemplateArgs, 3385198092Srdivacky Deduced, ParamTypes, 3386198092Srdivacky &FunctionType, Info)) 3387198092Srdivacky return Result; 3388206084Srdivacky 3389206084Srdivacky NumExplicitlySpecified = Deduced.size(); 3390198092Srdivacky } 3391198092Srdivacky 3392234353Sdim // Unevaluated SFINAE context. 3393234353Sdim EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 3394198092Srdivacky SFINAETrap Trap(*this); 3395198092Srdivacky 3396203955Srdivacky Deduced.resize(TemplateParams->size()); 3397203955Srdivacky 3398251662Sdim // If the function has a deduced return type, substitute it for a dependent 3399251662Sdim // type so that we treat it as a non-deduced context in what follows. 3400251662Sdim bool HasUndeducedReturnType = false; 3401251662Sdim if (getLangOpts().CPlusPlus1y && InOverloadResolution && 3402251662Sdim Function->getResultType()->isUndeducedType()) { 3403251662Sdim FunctionType = SubstAutoType(FunctionType, Context.DependentTy); 3404251662Sdim HasUndeducedReturnType = true; 3405251662Sdim } 3406251662Sdim 3407201361Srdivacky if (!ArgFunctionType.isNull()) { 3408251662Sdim unsigned TDF = TDF_TopLevelParameterTypeList; 3409251662Sdim if (InOverloadResolution) TDF |= TDF_InOverloadResolution; 3410201361Srdivacky // Deduce template arguments from the function type. 3411201361Srdivacky if (TemplateDeductionResult Result 3412234353Sdim = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3413251662Sdim FunctionType, ArgFunctionType, 3414251662Sdim Info, Deduced, TDF)) 3415201361Srdivacky return Result; 3416201361Srdivacky } 3417218893Sdim 3418218893Sdim if (TemplateDeductionResult Result 3419218893Sdim = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 3420218893Sdim NumExplicitlySpecified, 3421218893Sdim Specialization, Info)) 3422218893Sdim return Result; 3423218893Sdim 3424251662Sdim // If the function has a deduced return type, deduce it now, so we can check 3425251662Sdim // that the deduced function type matches the requested type. 3426251662Sdim if (HasUndeducedReturnType && 3427251662Sdim Specialization->getResultType()->isUndeducedType() && 3428251662Sdim DeduceReturnType(Specialization, Info.getLocation(), false)) 3429249423Sdim return TDK_MiscellaneousDeductionFailure; 3430218893Sdim 3431251662Sdim // If the requested function type does not match the actual type of the 3432251662Sdim // specialization with respect to arguments of compatible pointer to function 3433251662Sdim // types, template argument deduction fails. 3434251662Sdim if (!ArgFunctionType.isNull()) { 3435251662Sdim if (InOverloadResolution && !isSameOrCompatibleFunctionType( 3436251662Sdim Context.getCanonicalType(Specialization->getType()), 3437251662Sdim Context.getCanonicalType(ArgFunctionType))) 3438251662Sdim return TDK_MiscellaneousDeductionFailure; 3439251662Sdim else if(!InOverloadResolution && 3440251662Sdim !Context.hasSameType(Specialization->getType(), ArgFunctionType)) 3441251662Sdim return TDK_MiscellaneousDeductionFailure; 3442251662Sdim } 3443251662Sdim 3444218893Sdim return TDK_Success; 3445198092Srdivacky} 3446198092Srdivacky 3447198092Srdivacky/// \brief Deduce template arguments for a templated conversion 3448198092Srdivacky/// function (C++ [temp.deduct.conv]) and, if successful, produce a 3449198092Srdivacky/// conversion function template specialization. 3450198092SrdivackySema::TemplateDeductionResult 3451198092SrdivackySema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 3452198092Srdivacky QualType ToType, 3453198092Srdivacky CXXConversionDecl *&Specialization, 3454198092Srdivacky TemplateDeductionInfo &Info) { 3455243830Sdim if (FunctionTemplate->isInvalidDecl()) 3456243830Sdim return TDK_Invalid; 3457243830Sdim 3458198092Srdivacky CXXConversionDecl *Conv 3459198092Srdivacky = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl()); 3460198092Srdivacky QualType FromType = Conv->getConversionType(); 3461198092Srdivacky 3462198092Srdivacky // Canonicalize the types for deduction. 3463198092Srdivacky QualType P = Context.getCanonicalType(FromType); 3464198092Srdivacky QualType A = Context.getCanonicalType(ToType); 3465198092Srdivacky 3466221345Sdim // C++0x [temp.deduct.conv]p2: 3467198092Srdivacky // If P is a reference type, the type referred to by P is used for 3468198092Srdivacky // type deduction. 3469198092Srdivacky if (const ReferenceType *PRef = P->getAs<ReferenceType>()) 3470198092Srdivacky P = PRef->getPointeeType(); 3471198092Srdivacky 3472221345Sdim // C++0x [temp.deduct.conv]p4: 3473221345Sdim // [...] If A is a reference type, the type referred to by A is used 3474198092Srdivacky // for type deduction. 3475198092Srdivacky if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 3476221345Sdim A = ARef->getPointeeType().getUnqualifiedType(); 3477221345Sdim // C++ [temp.deduct.conv]p3: 3478198092Srdivacky // 3479198092Srdivacky // If A is not a reference type: 3480198092Srdivacky else { 3481198092Srdivacky assert(!A->isReferenceType() && "Reference types were handled above"); 3482198092Srdivacky 3483198092Srdivacky // - If P is an array type, the pointer type produced by the 3484198092Srdivacky // array-to-pointer standard conversion (4.2) is used in place 3485198092Srdivacky // of P for type deduction; otherwise, 3486198092Srdivacky if (P->isArrayType()) 3487198092Srdivacky P = Context.getArrayDecayedType(P); 3488198092Srdivacky // - If P is a function type, the pointer type produced by the 3489198092Srdivacky // function-to-pointer standard conversion (4.3) is used in 3490198092Srdivacky // place of P for type deduction; otherwise, 3491198092Srdivacky else if (P->isFunctionType()) 3492198092Srdivacky P = Context.getPointerType(P); 3493198092Srdivacky // - If P is a cv-qualified type, the top level cv-qualifiers of 3494218893Sdim // P's type are ignored for type deduction. 3495198092Srdivacky else 3496198092Srdivacky P = P.getUnqualifiedType(); 3497198092Srdivacky 3498221345Sdim // C++0x [temp.deduct.conv]p4: 3499218893Sdim // If A is a cv-qualified type, the top level cv-qualifiers of A's 3500221345Sdim // type are ignored for type deduction. If A is a reference type, the type 3501221345Sdim // referred to by A is used for type deduction. 3502198092Srdivacky A = A.getUnqualifiedType(); 3503198092Srdivacky } 3504198092Srdivacky 3505234353Sdim // Unevaluated SFINAE context. 3506234353Sdim EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated); 3507198092Srdivacky SFINAETrap Trap(*this); 3508198092Srdivacky 3509198092Srdivacky // C++ [temp.deduct.conv]p1: 3510198092Srdivacky // Template argument deduction is done by comparing the return 3511198092Srdivacky // type of the template conversion function (call it P) with the 3512198092Srdivacky // type that is required as the result of the conversion (call it 3513198092Srdivacky // A) as described in 14.8.2.4. 3514198092Srdivacky TemplateParameterList *TemplateParams 3515198092Srdivacky = FunctionTemplate->getTemplateParameters(); 3516226633Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 3517198092Srdivacky Deduced.resize(TemplateParams->size()); 3518198092Srdivacky 3519198092Srdivacky // C++0x [temp.deduct.conv]p4: 3520198092Srdivacky // In general, the deduction process attempts to find template 3521198092Srdivacky // argument values that will make the deduced A identical to 3522198092Srdivacky // A. However, there are two cases that allow a difference: 3523198092Srdivacky unsigned TDF = 0; 3524198092Srdivacky // - If the original A is a reference type, A can be more 3525198092Srdivacky // cv-qualified than the deduced A (i.e., the type referred to 3526198092Srdivacky // by the reference) 3527198092Srdivacky if (ToType->isReferenceType()) 3528198092Srdivacky TDF |= TDF_ParamWithReferenceType; 3529198092Srdivacky // - The deduced A can be another pointer or pointer to member 3530218893Sdim // type that can be converted to A via a qualification 3531198092Srdivacky // conversion. 3532198092Srdivacky // 3533198092Srdivacky // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 3534198092Srdivacky // both P and A are pointers or member pointers. In this case, we 3535198092Srdivacky // just ignore cv-qualifiers completely). 3536198092Srdivacky if ((P->isPointerType() && A->isPointerType()) || 3537226633Sdim (P->isMemberPointerType() && A->isMemberPointerType())) 3538198092Srdivacky TDF |= TDF_IgnoreQualifiers; 3539198092Srdivacky if (TemplateDeductionResult Result 3540234353Sdim = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 3541234353Sdim P, A, Info, Deduced, TDF)) 3542198092Srdivacky return Result; 3543198092Srdivacky 3544198092Srdivacky // Finish template argument deduction. 3545212904Sdim LocalInstantiationScope InstScope(*this); 3546198092Srdivacky FunctionDecl *Spec = 0; 3547198092Srdivacky TemplateDeductionResult Result 3548218893Sdim = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec, 3549206084Srdivacky Info); 3550198092Srdivacky Specialization = cast_or_null<CXXConversionDecl>(Spec); 3551198092Srdivacky return Result; 3552198092Srdivacky} 3553198092Srdivacky 3554201361Srdivacky/// \brief Deduce template arguments for a function template when there is 3555201361Srdivacky/// nothing to deduce against (C++0x [temp.arg.explicit]p3). 3556201361Srdivacky/// 3557201361Srdivacky/// \param FunctionTemplate the function template for which we are performing 3558201361Srdivacky/// template argument deduction. 3559201361Srdivacky/// 3560239462Sdim/// \param ExplicitTemplateArgs the explicitly-specified template 3561201361Srdivacky/// arguments. 3562201361Srdivacky/// 3563201361Srdivacky/// \param Specialization if template argument deduction was successful, 3564201361Srdivacky/// this will be set to the function template specialization produced by 3565201361Srdivacky/// template argument deduction. 3566201361Srdivacky/// 3567201361Srdivacky/// \param Info the argument will be updated to provide additional information 3568201361Srdivacky/// about template argument deduction. 3569201361Srdivacky/// 3570201361Srdivacky/// \returns the result of template argument deduction. 3571201361SrdivackySema::TemplateDeductionResult 3572201361SrdivackySema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate, 3573221345Sdim TemplateArgumentListInfo *ExplicitTemplateArgs, 3574201361Srdivacky FunctionDecl *&Specialization, 3575251662Sdim TemplateDeductionInfo &Info, 3576251662Sdim bool InOverloadResolution) { 3577201361Srdivacky return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs, 3578251662Sdim QualType(), Specialization, Info, 3579251662Sdim InOverloadResolution); 3580201361Srdivacky} 3581201361Srdivacky 3582218893Sdimnamespace { 3583218893Sdim /// Substitute the 'auto' type specifier within a type for a given replacement 3584218893Sdim /// type. 3585218893Sdim class SubstituteAutoTransform : 3586218893Sdim public TreeTransform<SubstituteAutoTransform> { 3587218893Sdim QualType Replacement; 3588218893Sdim public: 3589218893Sdim SubstituteAutoTransform(Sema &SemaRef, QualType Replacement) : 3590218893Sdim TreeTransform<SubstituteAutoTransform>(SemaRef), Replacement(Replacement) { 3591218893Sdim } 3592218893Sdim QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) { 3593218893Sdim // If we're building the type pattern to deduce against, don't wrap the 3594218893Sdim // substituted type in an AutoType. Certain template deduction rules 3595218893Sdim // apply only when a template type parameter appears directly (and not if 3596218893Sdim // the parameter is found through desugaring). For instance: 3597218893Sdim // auto &&lref = lvalue; 3598218893Sdim // must transform into "rvalue reference to T" not "rvalue reference to 3599218893Sdim // auto type deduced as T" in order for [temp.deduct.call]p3 to apply. 3600251662Sdim if (!Replacement.isNull() && isa<TemplateTypeParmType>(Replacement)) { 3601218893Sdim QualType Result = Replacement; 3602251662Sdim TemplateTypeParmTypeLoc NewTL = 3603251662Sdim TLB.push<TemplateTypeParmTypeLoc>(Result); 3604218893Sdim NewTL.setNameLoc(TL.getNameLoc()); 3605218893Sdim return Result; 3606218893Sdim } else { 3607251662Sdim bool Dependent = 3608251662Sdim !Replacement.isNull() && Replacement->isDependentType(); 3609251662Sdim QualType Result = 3610251662Sdim SemaRef.Context.getAutoType(Dependent ? QualType() : Replacement, 3611251662Sdim TL.getTypePtr()->isDecltypeAuto(), 3612251662Sdim Dependent); 3613218893Sdim AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result); 3614218893Sdim NewTL.setNameLoc(TL.getNameLoc()); 3615218893Sdim return Result; 3616218893Sdim } 3617218893Sdim } 3618234353Sdim 3619234353Sdim ExprResult TransformLambdaExpr(LambdaExpr *E) { 3620234353Sdim // Lambdas never need to be transformed. 3621234353Sdim return E; 3622234353Sdim } 3623239462Sdim 3624251662Sdim QualType Apply(TypeLoc TL) { 3625251662Sdim // Create some scratch storage for the transformed type locations. 3626251662Sdim // FIXME: We're just going to throw this information away. Don't build it. 3627251662Sdim TypeLocBuilder TLB; 3628251662Sdim TLB.reserve(TL.getFullDataSize()); 3629251662Sdim return TransformType(TLB, TL); 3630239462Sdim } 3631251662Sdim }; 3632218893Sdim} 3633198092Srdivacky 3634251662SdimSema::DeduceAutoResult 3635251662SdimSema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result) { 3636251662Sdim return DeduceAutoType(Type->getTypeLoc(), Init, Result); 3637251662Sdim} 3638251662Sdim 3639251662Sdim/// \brief Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6) 3640198092Srdivacky/// 3641218893Sdim/// \param Type the type pattern using the auto type-specifier. 3642218893Sdim/// \param Init the initializer for the variable whose type is to be deduced. 3643218893Sdim/// \param Result if type deduction was successful, this will be set to the 3644251662Sdim/// deduced type. 3645234353SdimSema::DeduceAutoResult 3646251662SdimSema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) { 3647234353Sdim if (Init->getType()->isNonOverloadPlaceholderType()) { 3648251662Sdim ExprResult NonPlaceholder = CheckPlaceholderExpr(Init); 3649251662Sdim if (NonPlaceholder.isInvalid()) 3650251662Sdim return DAR_FailedAlreadyDiagnosed; 3651251662Sdim Init = NonPlaceholder.take(); 3652234353Sdim } 3653234353Sdim 3654251662Sdim if (Init->isTypeDependent() || Type.getType()->isDependentType()) { 3655251662Sdim Result = SubstituteAutoTransform(*this, Context.DependentTy).Apply(Type); 3656251662Sdim assert(!Result.isNull() && "substituting DependentTy can't fail"); 3657234353Sdim return DAR_Succeeded; 3658218893Sdim } 3659198092Srdivacky 3660251662Sdim // If this is a 'decltype(auto)' specifier, do the decltype dance. 3661251662Sdim // Since 'decltype(auto)' can only occur at the top of the type, we 3662251662Sdim // don't need to go digging for it. 3663251662Sdim if (const AutoType *AT = Type.getType()->getAs<AutoType>()) { 3664251662Sdim if (AT->isDecltypeAuto()) { 3665251662Sdim if (isa<InitListExpr>(Init)) { 3666251662Sdim Diag(Init->getLocStart(), diag::err_decltype_auto_initializer_list); 3667251662Sdim return DAR_FailedAlreadyDiagnosed; 3668251662Sdim } 3669251662Sdim 3670251662Sdim QualType Deduced = BuildDecltypeType(Init, Init->getLocStart()); 3671251662Sdim // FIXME: Support a non-canonical deduced type for 'auto'. 3672251662Sdim Deduced = Context.getCanonicalType(Deduced); 3673251662Sdim Result = SubstituteAutoTransform(*this, Deduced).Apply(Type); 3674251662Sdim if (Result.isNull()) 3675251662Sdim return DAR_FailedAlreadyDiagnosed; 3676251662Sdim return DAR_Succeeded; 3677251662Sdim } 3678251662Sdim } 3679251662Sdim 3680218893Sdim SourceLocation Loc = Init->getExprLoc(); 3681218893Sdim 3682218893Sdim LocalInstantiationScope InstScope(*this); 3683218893Sdim 3684218893Sdim // Build template<class TemplParam> void Func(FuncParam); 3685221345Sdim TemplateTypeParmDecl *TemplParam = 3686221345Sdim TemplateTypeParmDecl::Create(Context, 0, SourceLocation(), Loc, 0, 0, 0, 3687221345Sdim false, false); 3688221345Sdim QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0); 3689221345Sdim NamedDecl *TemplParamPtr = TemplParam; 3690219077Sdim FixedSizeTemplateParameterList<1> TemplateParams(Loc, Loc, &TemplParamPtr, 3691219077Sdim Loc); 3692218893Sdim 3693251662Sdim QualType FuncParam = SubstituteAutoTransform(*this, TemplArg).Apply(Type); 3694251662Sdim assert(!FuncParam.isNull() && 3695251662Sdim "substituting template parameter for 'auto' failed"); 3696218893Sdim 3697218893Sdim // Deduce type of TemplParam in Func(Init) 3698226633Sdim SmallVector<DeducedTemplateArgument, 1> Deduced; 3699218893Sdim Deduced.resize(1); 3700218893Sdim QualType InitType = Init->getType(); 3701218893Sdim unsigned TDF = 0; 3702218893Sdim 3703243830Sdim TemplateDeductionInfo Info(Loc); 3704218893Sdim 3705239462Sdim InitListExpr *InitList = dyn_cast<InitListExpr>(Init); 3706234353Sdim if (InitList) { 3707234353Sdim for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) { 3708239462Sdim if (DeduceTemplateArgumentByListElement(*this, &TemplateParams, 3709234353Sdim TemplArg, 3710234353Sdim InitList->getInit(i), 3711234353Sdim Info, Deduced, TDF)) 3712234353Sdim return DAR_Failed; 3713234353Sdim } 3714234353Sdim } else { 3715234353Sdim if (AdjustFunctionParmAndArgTypesForDeduction(*this, &TemplateParams, 3716234353Sdim FuncParam, InitType, Init, 3717234353Sdim TDF)) 3718234353Sdim return DAR_Failed; 3719239462Sdim 3720234353Sdim if (DeduceTemplateArgumentsByTypeMatch(*this, &TemplateParams, FuncParam, 3721234353Sdim InitType, Info, Deduced, TDF)) 3722234353Sdim return DAR_Failed; 3723234353Sdim } 3724234353Sdim 3725243830Sdim if (Deduced[0].getKind() != TemplateArgument::Type) 3726234353Sdim return DAR_Failed; 3727234353Sdim 3728243830Sdim QualType DeducedType = Deduced[0].getAsType(); 3729243830Sdim 3730234353Sdim if (InitList) { 3731234353Sdim DeducedType = BuildStdInitializerList(DeducedType, Loc); 3732234353Sdim if (DeducedType.isNull()) 3733234353Sdim return DAR_FailedAlreadyDiagnosed; 3734234353Sdim } 3735234353Sdim 3736251662Sdim Result = SubstituteAutoTransform(*this, DeducedType).Apply(Type); 3737251662Sdim if (Result.isNull()) 3738251662Sdim return DAR_FailedAlreadyDiagnosed; 3739234353Sdim 3740224145Sdim // Check that the deduced argument type is compatible with the original 3741224145Sdim // argument type per C++ [temp.deduct.call]p4. 3742251662Sdim if (!InitList && !Result.isNull() && 3743251662Sdim CheckOriginalCallArgDeduction(*this, 3744224145Sdim Sema::OriginalCallArg(FuncParam,0,InitType), 3745251662Sdim Result)) { 3746251662Sdim Result = QualType(); 3747234353Sdim return DAR_Failed; 3748224145Sdim } 3749218893Sdim 3750234353Sdim return DAR_Succeeded; 3751198092Srdivacky} 3752198092Srdivacky 3753251662SdimQualType Sema::SubstAutoType(QualType Type, QualType Deduced) { 3754251662Sdim return SubstituteAutoTransform(*this, Deduced).TransformType(Type); 3755251662Sdim} 3756251662Sdim 3757234353Sdimvoid Sema::DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init) { 3758234353Sdim if (isa<InitListExpr>(Init)) 3759234353Sdim Diag(VDecl->getLocation(), 3760234353Sdim diag::err_auto_var_deduction_failure_from_init_list) 3761234353Sdim << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange(); 3762234353Sdim else 3763234353Sdim Diag(VDecl->getLocation(), diag::err_auto_var_deduction_failure) 3764234353Sdim << VDecl->getDeclName() << VDecl->getType() << Init->getType() 3765234353Sdim << Init->getSourceRange(); 3766234353Sdim} 3767234353Sdim 3768251662Sdimbool Sema::DeduceReturnType(FunctionDecl *FD, SourceLocation Loc, 3769251662Sdim bool Diagnose) { 3770251662Sdim assert(FD->getResultType()->isUndeducedType()); 3771251662Sdim 3772251662Sdim if (FD->getTemplateInstantiationPattern()) 3773251662Sdim InstantiateFunctionDefinition(Loc, FD); 3774251662Sdim 3775251662Sdim bool StillUndeduced = FD->getResultType()->isUndeducedType(); 3776251662Sdim if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) { 3777251662Sdim Diag(Loc, diag::err_auto_fn_used_before_defined) << FD; 3778251662Sdim Diag(FD->getLocation(), diag::note_callee_decl) << FD; 3779251662Sdim } 3780251662Sdim 3781251662Sdim return StillUndeduced; 3782251662Sdim} 3783251662Sdim 3784198092Srdivackystatic void 3785234353SdimMarkUsedTemplateParameters(ASTContext &Ctx, QualType T, 3786198092Srdivacky bool OnlyDeduced, 3787198893Srdivacky unsigned Level, 3788234353Sdim llvm::SmallBitVector &Deduced); 3789218893Sdim 3790218893Sdim/// \brief If this is a non-static member function, 3791243830Sdimstatic void AddImplicitObjectParameterType(ASTContext &Context, 3792218893Sdim CXXMethodDecl *Method, 3793226633Sdim SmallVectorImpl<QualType> &ArgTypes) { 3794243830Sdim // C++11 [temp.func.order]p3: 3795243830Sdim // [...] The new parameter is of type "reference to cv A," where cv are 3796243830Sdim // the cv-qualifiers of the function template (if any) and A is 3797243830Sdim // the class of which the function template is a member. 3798218893Sdim // 3799243830Sdim // The standard doesn't say explicitly, but we pick the appropriate kind of 3800243830Sdim // reference type based on [over.match.funcs]p4. 3801218893Sdim QualType ArgTy = Context.getTypeDeclType(Method->getParent()); 3802218893Sdim ArgTy = Context.getQualifiedType(ArgTy, 3803218893Sdim Qualifiers::fromCVRMask(Method->getTypeQualifiers())); 3804243830Sdim if (Method->getRefQualifier() == RQ_RValue) 3805243830Sdim ArgTy = Context.getRValueReferenceType(ArgTy); 3806243830Sdim else 3807243830Sdim ArgTy = Context.getLValueReferenceType(ArgTy); 3808218893Sdim ArgTypes.push_back(ArgTy); 3809218893Sdim} 3810218893Sdim 3811198092Srdivacky/// \brief Determine whether the function template \p FT1 is at least as 3812198092Srdivacky/// specialized as \p FT2. 3813198092Srdivackystatic bool isAtLeastAsSpecializedAs(Sema &S, 3814203955Srdivacky SourceLocation Loc, 3815198092Srdivacky FunctionTemplateDecl *FT1, 3816198092Srdivacky FunctionTemplateDecl *FT2, 3817198092Srdivacky TemplatePartialOrderingContext TPOC, 3818218893Sdim unsigned NumCallArguments, 3819226633Sdim SmallVectorImpl<RefParamPartialOrderingComparison> *RefParamComparisons) { 3820198092Srdivacky FunctionDecl *FD1 = FT1->getTemplatedDecl(); 3821218893Sdim FunctionDecl *FD2 = FT2->getTemplatedDecl(); 3822198092Srdivacky const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 3823198092Srdivacky const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 3824218893Sdim 3825198092Srdivacky assert(Proto1 && Proto2 && "Function templates must have prototypes"); 3826198092Srdivacky TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 3827226633Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 3828198092Srdivacky Deduced.resize(TemplateParams->size()); 3829198092Srdivacky 3830198092Srdivacky // C++0x [temp.deduct.partial]p3: 3831198092Srdivacky // The types used to determine the ordering depend on the context in which 3832198092Srdivacky // the partial ordering is done: 3833243830Sdim TemplateDeductionInfo Info(Loc); 3834218893Sdim CXXMethodDecl *Method1 = 0; 3835218893Sdim CXXMethodDecl *Method2 = 0; 3836218893Sdim bool IsNonStatic2 = false; 3837218893Sdim bool IsNonStatic1 = false; 3838218893Sdim unsigned Skip2 = 0; 3839198092Srdivacky switch (TPOC) { 3840198092Srdivacky case TPOC_Call: { 3841198092Srdivacky // - In the context of a function call, the function parameter types are 3842198092Srdivacky // used. 3843218893Sdim Method1 = dyn_cast<CXXMethodDecl>(FD1); 3844218893Sdim Method2 = dyn_cast<CXXMethodDecl>(FD2); 3845218893Sdim IsNonStatic1 = Method1 && !Method1->isStatic(); 3846218893Sdim IsNonStatic2 = Method2 && !Method2->isStatic(); 3847218893Sdim 3848243830Sdim // C++11 [temp.func.order]p3: 3849218893Sdim // [...] If only one of the function templates is a non-static 3850218893Sdim // member, that function template is considered to have a new 3851218893Sdim // first parameter inserted in its function parameter list. The 3852218893Sdim // new parameter is of type "reference to cv A," where cv are 3853218893Sdim // the cv-qualifiers of the function template (if any) and A is 3854218893Sdim // the class of which the function template is a member. 3855218893Sdim // 3856243830Sdim // Note that we interpret this to mean "if one of the function 3857243830Sdim // templates is a non-static member and the other is a non-member"; 3858243830Sdim // otherwise, the ordering rules for static functions against non-static 3859243830Sdim // functions don't make any sense. 3860243830Sdim // 3861218893Sdim // C++98/03 doesn't have this provision, so instead we drop the 3862243830Sdim // first argument of the free function, which seems to match 3863243830Sdim // existing practice. 3864226633Sdim SmallVector<QualType, 4> Args1; 3865249423Sdim unsigned Skip1 = !S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !Method1; 3866249423Sdim if (S.getLangOpts().CPlusPlus11 && IsNonStatic1 && !Method2) 3867243830Sdim AddImplicitObjectParameterType(S.Context, Method1, Args1); 3868218893Sdim Args1.insert(Args1.end(), 3869218893Sdim Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end()); 3870218893Sdim 3871226633Sdim SmallVector<QualType, 4> Args2; 3872249423Sdim Skip2 = !S.getLangOpts().CPlusPlus11 && IsNonStatic1 && !Method2; 3873249423Sdim if (S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !Method1) 3874243830Sdim AddImplicitObjectParameterType(S.Context, Method2, Args2); 3875218893Sdim Args2.insert(Args2.end(), 3876218893Sdim Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end()); 3877218893Sdim 3878218893Sdim // C++ [temp.func.order]p5: 3879218893Sdim // The presence of unused ellipsis and default arguments has no effect on 3880218893Sdim // the partial ordering of function templates. 3881218893Sdim if (Args1.size() > NumCallArguments) 3882218893Sdim Args1.resize(NumCallArguments); 3883218893Sdim if (Args2.size() > NumCallArguments) 3884218893Sdim Args2.resize(NumCallArguments); 3885218893Sdim if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(), 3886218893Sdim Args1.data(), Args1.size(), Info, Deduced, 3887218893Sdim TDF_None, /*PartialOrdering=*/true, 3888218893Sdim RefParamComparisons)) 3889198092Srdivacky return false; 3890218893Sdim 3891198092Srdivacky break; 3892195099Sed } 3893218893Sdim 3894198092Srdivacky case TPOC_Conversion: 3895198092Srdivacky // - In the context of a call to a conversion operator, the return types 3896198092Srdivacky // of the conversion function templates are used. 3897234353Sdim if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 3898234353Sdim Proto2->getResultType(), 3899234353Sdim Proto1->getResultType(), 3900234353Sdim Info, Deduced, TDF_None, 3901234353Sdim /*PartialOrdering=*/true, 3902234353Sdim RefParamComparisons)) 3903198092Srdivacky return false; 3904198092Srdivacky break; 3905218893Sdim 3906198092Srdivacky case TPOC_Other: 3907218893Sdim // - In other contexts (14.6.6.2) the function template's function type 3908198092Srdivacky // is used. 3909234353Sdim if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 3910234353Sdim FD2->getType(), FD1->getType(), 3911234353Sdim Info, Deduced, TDF_None, 3912234353Sdim /*PartialOrdering=*/true, 3913234353Sdim RefParamComparisons)) 3914198092Srdivacky return false; 3915198092Srdivacky break; 3916198092Srdivacky } 3917218893Sdim 3918198092Srdivacky // C++0x [temp.deduct.partial]p11: 3919218893Sdim // In most cases, all template parameters must have values in order for 3920218893Sdim // deduction to succeed, but for partial ordering purposes a template 3921218893Sdim // parameter may remain without a value provided it is not used in the 3922198092Srdivacky // types being used for partial ordering. [ Note: a template parameter used 3923198092Srdivacky // in a non-deduced context is considered used. -end note] 3924198092Srdivacky unsigned ArgIdx = 0, NumArgs = Deduced.size(); 3925198092Srdivacky for (; ArgIdx != NumArgs; ++ArgIdx) 3926198092Srdivacky if (Deduced[ArgIdx].isNull()) 3927198092Srdivacky break; 3928198092Srdivacky 3929198092Srdivacky if (ArgIdx == NumArgs) { 3930218893Sdim // All template arguments were deduced. FT1 is at least as specialized 3931198092Srdivacky // as FT2. 3932198092Srdivacky return true; 3933198092Srdivacky } 3934198092Srdivacky 3935198092Srdivacky // Figure out which template parameters were used. 3936234353Sdim llvm::SmallBitVector UsedParameters(TemplateParams->size()); 3937198092Srdivacky switch (TPOC) { 3938198092Srdivacky case TPOC_Call: { 3939218893Sdim unsigned NumParams = std::min(NumCallArguments, 3940218893Sdim std::min(Proto1->getNumArgs(), 3941218893Sdim Proto2->getNumArgs())); 3942249423Sdim if (S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !IsNonStatic1) 3943234353Sdim ::MarkUsedTemplateParameters(S.Context, Method2->getThisType(S.Context), 3944234353Sdim false, 3945218893Sdim TemplateParams->getDepth(), UsedParameters); 3946218893Sdim for (unsigned I = Skip2; I < NumParams; ++I) 3947234353Sdim ::MarkUsedTemplateParameters(S.Context, Proto2->getArgType(I), false, 3948198893Srdivacky TemplateParams->getDepth(), 3949198092Srdivacky UsedParameters); 3950198092Srdivacky break; 3951198092Srdivacky } 3952218893Sdim 3953198092Srdivacky case TPOC_Conversion: 3954234353Sdim ::MarkUsedTemplateParameters(S.Context, Proto2->getResultType(), false, 3955198893Srdivacky TemplateParams->getDepth(), 3956198092Srdivacky UsedParameters); 3957198092Srdivacky break; 3958218893Sdim 3959198092Srdivacky case TPOC_Other: 3960234353Sdim ::MarkUsedTemplateParameters(S.Context, FD2->getType(), false, 3961198893Srdivacky TemplateParams->getDepth(), 3962198893Srdivacky UsedParameters); 3963198092Srdivacky break; 3964194179Sed } 3965218893Sdim 3966198092Srdivacky for (; ArgIdx != NumArgs; ++ArgIdx) 3967198092Srdivacky // If this argument had no value deduced but was used in one of the types 3968198092Srdivacky // used for partial ordering, then deduction fails. 3969198092Srdivacky if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 3970198092Srdivacky return false; 3971218893Sdim 3972198092Srdivacky return true; 3973198092Srdivacky} 3974218893Sdim 3975218893Sdim/// \brief Determine whether this a function template whose parameter-type-list 3976218893Sdim/// ends with a function parameter pack. 3977218893Sdimstatic bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) { 3978218893Sdim FunctionDecl *Function = FunTmpl->getTemplatedDecl(); 3979218893Sdim unsigned NumParams = Function->getNumParams(); 3980218893Sdim if (NumParams == 0) 3981218893Sdim return false; 3982218893Sdim 3983218893Sdim ParmVarDecl *Last = Function->getParamDecl(NumParams - 1); 3984218893Sdim if (!Last->isParameterPack()) 3985218893Sdim return false; 3986218893Sdim 3987218893Sdim // Make sure that no previous parameter is a parameter pack. 3988218893Sdim while (--NumParams > 0) { 3989218893Sdim if (Function->getParamDecl(NumParams - 1)->isParameterPack()) 3990218893Sdim return false; 3991218893Sdim } 3992218893Sdim 3993218893Sdim return true; 3994218893Sdim} 3995218893Sdim 3996198092Srdivacky/// \brief Returns the more specialized function template according 3997198092Srdivacky/// to the rules of function template partial ordering (C++ [temp.func.order]). 3998198092Srdivacky/// 3999198092Srdivacky/// \param FT1 the first function template 4000198092Srdivacky/// 4001198092Srdivacky/// \param FT2 the second function template 4002198092Srdivacky/// 4003198092Srdivacky/// \param TPOC the context in which we are performing partial ordering of 4004198092Srdivacky/// function templates. 4005198092Srdivacky/// 4006218893Sdim/// \param NumCallArguments The number of arguments in a call, used only 4007218893Sdim/// when \c TPOC is \c TPOC_Call. 4008218893Sdim/// 4009198092Srdivacky/// \returns the more specialized function template. If neither 4010198092Srdivacky/// template is more specialized, returns NULL. 4011198092SrdivackyFunctionTemplateDecl * 4012198092SrdivackySema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, 4013198092Srdivacky FunctionTemplateDecl *FT2, 4014203955Srdivacky SourceLocation Loc, 4015218893Sdim TemplatePartialOrderingContext TPOC, 4016218893Sdim unsigned NumCallArguments) { 4017226633Sdim SmallVector<RefParamPartialOrderingComparison, 4> RefParamComparisons; 4018218893Sdim bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC, 4019218893Sdim NumCallArguments, 0); 4020218893Sdim bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC, 4021218893Sdim NumCallArguments, 4022218893Sdim &RefParamComparisons); 4023218893Sdim 4024198092Srdivacky if (Better1 != Better2) // We have a clear winner 4025198092Srdivacky return Better1? FT1 : FT2; 4026218893Sdim 4027198092Srdivacky if (!Better1 && !Better2) // Neither is better than the other 4028198092Srdivacky return 0; 4029195341Sed 4030198092Srdivacky // C++0x [temp.deduct.partial]p10: 4031218893Sdim // If for each type being considered a given template is at least as 4032198092Srdivacky // specialized for all types and more specialized for some set of types and 4033218893Sdim // the other template is not more specialized for any types or is not at 4034198092Srdivacky // least as specialized for any types, then the given template is more 4035198092Srdivacky // specialized than the other template. Otherwise, neither template is more 4036198092Srdivacky // specialized than the other. 4037198092Srdivacky Better1 = false; 4038198092Srdivacky Better2 = false; 4039218893Sdim for (unsigned I = 0, N = RefParamComparisons.size(); I != N; ++I) { 4040198092Srdivacky // C++0x [temp.deduct.partial]p9: 4041198092Srdivacky // If, for a given type, deduction succeeds in both directions (i.e., the 4042218893Sdim // types are identical after the transformations above) and both P and A 4043218893Sdim // were reference types (before being replaced with the type referred to 4044218893Sdim // above): 4045218893Sdim 4046218893Sdim // -- if the type from the argument template was an lvalue reference 4047218893Sdim // and the type from the parameter template was not, the argument 4048218893Sdim // type is considered to be more specialized than the other; 4049218893Sdim // otherwise, 4050218893Sdim if (!RefParamComparisons[I].ArgIsRvalueRef && 4051218893Sdim RefParamComparisons[I].ParamIsRvalueRef) { 4052218893Sdim Better2 = true; 4053218893Sdim if (Better1) 4054218893Sdim return 0; 4055218893Sdim continue; 4056218893Sdim } else if (!RefParamComparisons[I].ParamIsRvalueRef && 4057218893Sdim RefParamComparisons[I].ArgIsRvalueRef) { 4058218893Sdim Better1 = true; 4059218893Sdim if (Better2) 4060218893Sdim return 0; 4061218893Sdim continue; 4062198092Srdivacky } 4063218893Sdim 4064218893Sdim // -- if the type from the argument template is more cv-qualified than 4065218893Sdim // the type from the parameter template (as described above), the 4066218893Sdim // argument type is considered to be more specialized than the 4067218893Sdim // other; otherwise, 4068218893Sdim switch (RefParamComparisons[I].Qualifiers) { 4069218893Sdim case NeitherMoreQualified: 4070218893Sdim break; 4071218893Sdim 4072218893Sdim case ParamMoreQualified: 4073218893Sdim Better1 = true; 4074218893Sdim if (Better2) 4075218893Sdim return 0; 4076218893Sdim continue; 4077218893Sdim 4078218893Sdim case ArgMoreQualified: 4079218893Sdim Better2 = true; 4080218893Sdim if (Better1) 4081218893Sdim return 0; 4082218893Sdim continue; 4083218893Sdim } 4084218893Sdim 4085218893Sdim // -- neither type is more specialized than the other. 4086195341Sed } 4087218893Sdim 4088198092Srdivacky assert(!(Better1 && Better2) && "Should have broken out in the loop above"); 4089198092Srdivacky if (Better1) 4090198092Srdivacky return FT1; 4091198092Srdivacky else if (Better2) 4092198092Srdivacky return FT2; 4093218893Sdim 4094218893Sdim // FIXME: This mimics what GCC implements, but doesn't match up with the 4095218893Sdim // proposed resolution for core issue 692. This area needs to be sorted out, 4096218893Sdim // but for now we attempt to maintain compatibility. 4097218893Sdim bool Variadic1 = isVariadicFunctionTemplate(FT1); 4098218893Sdim bool Variadic2 = isVariadicFunctionTemplate(FT2); 4099218893Sdim if (Variadic1 != Variadic2) 4100218893Sdim return Variadic1? FT2 : FT1; 4101218893Sdim 4102218893Sdim return 0; 4103198092Srdivacky} 4104198092Srdivacky 4105198092Srdivacky/// \brief Determine if the two templates are equivalent. 4106198092Srdivackystatic bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) { 4107198092Srdivacky if (T1 == T2) 4108198092Srdivacky return true; 4109218893Sdim 4110198092Srdivacky if (!T1 || !T2) 4111198092Srdivacky return false; 4112218893Sdim 4113198092Srdivacky return T1->getCanonicalDecl() == T2->getCanonicalDecl(); 4114193576Sed} 4115194179Sed 4116198092Srdivacky/// \brief Retrieve the most specialized of the given function template 4117198092Srdivacky/// specializations. 4118198092Srdivacky/// 4119203955Srdivacky/// \param SpecBegin the start iterator of the function template 4120203955Srdivacky/// specializations that we will be comparing. 4121198092Srdivacky/// 4122203955Srdivacky/// \param SpecEnd the end iterator of the function template 4123203955Srdivacky/// specializations, paired with \p SpecBegin. 4124198092Srdivacky/// 4125198092Srdivacky/// \param TPOC the partial ordering context to use to compare the function 4126198092Srdivacky/// template specializations. 4127198092Srdivacky/// 4128218893Sdim/// \param NumCallArguments The number of arguments in a call, used only 4129218893Sdim/// when \c TPOC is \c TPOC_Call. 4130218893Sdim/// 4131218893Sdim/// \param Loc the location where the ambiguity or no-specializations 4132198092Srdivacky/// diagnostic should occur. 4133198092Srdivacky/// 4134198092Srdivacky/// \param NoneDiag partial diagnostic used to diagnose cases where there are 4135198092Srdivacky/// no matching candidates. 4136198092Srdivacky/// 4137198092Srdivacky/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one 4138198092Srdivacky/// occurs. 4139198092Srdivacky/// 4140198092Srdivacky/// \param CandidateDiag partial diagnostic used for each function template 4141198092Srdivacky/// specialization that is a candidate in the ambiguous ordering. One parameter 4142198092Srdivacky/// in this diagnostic should be unbound, which will correspond to the string 4143198092Srdivacky/// describing the template arguments for the function template specialization. 4144198092Srdivacky/// 4145218893Sdim/// \returns the most specialized function template specialization, if 4146203955Srdivacky/// found. Otherwise, returns SpecEnd. 4147198092Srdivacky/// 4148218893Sdim/// \todo FIXME: Consider passing in the "also-ran" candidates that failed 4149198092Srdivacky/// template argument deduction. 4150203955SrdivackyUnresolvedSetIterator 4151203955SrdivackySema::getMostSpecialized(UnresolvedSetIterator SpecBegin, 4152251662Sdim UnresolvedSetIterator SpecEnd, 4153203955Srdivacky TemplatePartialOrderingContext TPOC, 4154218893Sdim unsigned NumCallArguments, 4155203955Srdivacky SourceLocation Loc, 4156203955Srdivacky const PartialDiagnostic &NoneDiag, 4157203955Srdivacky const PartialDiagnostic &AmbigDiag, 4158218893Sdim const PartialDiagnostic &CandidateDiag, 4159234353Sdim bool Complain, 4160234353Sdim QualType TargetType) { 4161203955Srdivacky if (SpecBegin == SpecEnd) { 4162218893Sdim if (Complain) 4163218893Sdim Diag(Loc, NoneDiag); 4164203955Srdivacky return SpecEnd; 4165198092Srdivacky } 4166218893Sdim 4167218893Sdim if (SpecBegin + 1 == SpecEnd) 4168203955Srdivacky return SpecBegin; 4169218893Sdim 4170198092Srdivacky // Find the function template that is better than all of the templates it 4171198092Srdivacky // has been compared to. 4172203955Srdivacky UnresolvedSetIterator Best = SpecBegin; 4173218893Sdim FunctionTemplateDecl *BestTemplate 4174203955Srdivacky = cast<FunctionDecl>(*Best)->getPrimaryTemplate(); 4175198092Srdivacky assert(BestTemplate && "Not a function template specialization?"); 4176203955Srdivacky for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) { 4177203955Srdivacky FunctionTemplateDecl *Challenger 4178203955Srdivacky = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 4179198092Srdivacky assert(Challenger && "Not a function template specialization?"); 4180203955Srdivacky if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 4181218893Sdim Loc, TPOC, NumCallArguments), 4182198092Srdivacky Challenger)) { 4183198092Srdivacky Best = I; 4184198092Srdivacky BestTemplate = Challenger; 4185198092Srdivacky } 4186198092Srdivacky } 4187218893Sdim 4188198092Srdivacky // Make sure that the "best" function template is more specialized than all 4189198092Srdivacky // of the others. 4190198092Srdivacky bool Ambiguous = false; 4191203955Srdivacky for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 4192203955Srdivacky FunctionTemplateDecl *Challenger 4193203955Srdivacky = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 4194198092Srdivacky if (I != Best && 4195218893Sdim !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 4196218893Sdim Loc, TPOC, NumCallArguments), 4197198092Srdivacky BestTemplate)) { 4198198092Srdivacky Ambiguous = true; 4199198092Srdivacky break; 4200198092Srdivacky } 4201198092Srdivacky } 4202218893Sdim 4203198092Srdivacky if (!Ambiguous) { 4204198092Srdivacky // We found an answer. Return it. 4205203955Srdivacky return Best; 4206198092Srdivacky } 4207218893Sdim 4208198092Srdivacky // Diagnose the ambiguity. 4209251662Sdim if (Complain) { 4210218893Sdim Diag(Loc, AmbigDiag); 4211218893Sdim 4212251662Sdim // FIXME: Can we order the candidates in some sane way? 4213234353Sdim for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 4214234353Sdim PartialDiagnostic PD = CandidateDiag; 4215234353Sdim PD << getTemplateArgumentBindingsText( 4216218893Sdim cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(), 4217203955Srdivacky *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs()); 4218234353Sdim if (!TargetType.isNull()) 4219234353Sdim HandleFunctionTypeMismatch(PD, cast<FunctionDecl>(*I)->getType(), 4220234353Sdim TargetType); 4221234353Sdim Diag((*I)->getLocation(), PD); 4222234353Sdim } 4223251662Sdim } 4224218893Sdim 4225203955Srdivacky return SpecEnd; 4226198092Srdivacky} 4227194179Sed 4228198092Srdivacky/// \brief Returns the more specialized class template partial specialization 4229198092Srdivacky/// according to the rules of partial ordering of class template partial 4230198092Srdivacky/// specializations (C++ [temp.class.order]). 4231198092Srdivacky/// 4232198092Srdivacky/// \param PS1 the first class template partial specialization 4233198092Srdivacky/// 4234198092Srdivacky/// \param PS2 the second class template partial specialization 4235198092Srdivacky/// 4236198092Srdivacky/// \returns the more specialized class template partial specialization. If 4237198092Srdivacky/// neither partial specialization is more specialized, returns NULL. 4238198092SrdivackyClassTemplatePartialSpecializationDecl * 4239198092SrdivackySema::getMoreSpecializedPartialSpecialization( 4240198092Srdivacky ClassTemplatePartialSpecializationDecl *PS1, 4241203955Srdivacky ClassTemplatePartialSpecializationDecl *PS2, 4242203955Srdivacky SourceLocation Loc) { 4243198092Srdivacky // C++ [temp.class.order]p1: 4244198092Srdivacky // For two class template partial specializations, the first is at least as 4245218893Sdim // specialized as the second if, given the following rewrite to two 4246218893Sdim // function templates, the first function template is at least as 4247218893Sdim // specialized as the second according to the ordering rules for function 4248198092Srdivacky // templates (14.6.6.2): 4249198092Srdivacky // - the first function template has the same template parameters as the 4250218893Sdim // first partial specialization and has a single function parameter 4251218893Sdim // whose type is a class template specialization with the template 4252198092Srdivacky // arguments of the first partial specialization, and 4253198092Srdivacky // - the second function template has the same template parameters as the 4254218893Sdim // second partial specialization and has a single function parameter 4255218893Sdim // whose type is a class template specialization with the template 4256198092Srdivacky // arguments of the second partial specialization. 4257198092Srdivacky // 4258207619Srdivacky // Rather than synthesize function templates, we merely perform the 4259207619Srdivacky // equivalent partial ordering by performing deduction directly on 4260207619Srdivacky // the template arguments of the class template partial 4261207619Srdivacky // specializations. This computation is slightly simpler than the 4262207619Srdivacky // general problem of function template partial ordering, because 4263207619Srdivacky // class template partial specializations are more constrained. We 4264207619Srdivacky // know that every template parameter is deducible from the class 4265207619Srdivacky // template partial specialization's template arguments, for 4266207619Srdivacky // example. 4267226633Sdim SmallVector<DeducedTemplateArgument, 4> Deduced; 4268243830Sdim TemplateDeductionInfo Info(Loc); 4269207619Srdivacky 4270207619Srdivacky QualType PT1 = PS1->getInjectedSpecializationType(); 4271207619Srdivacky QualType PT2 = PS2->getInjectedSpecializationType(); 4272218893Sdim 4273198092Srdivacky // Determine whether PS1 is at least as specialized as PS2 4274198092Srdivacky Deduced.resize(PS2->getTemplateParameters()->size()); 4275234353Sdim bool Better1 = !DeduceTemplateArgumentsByTypeMatch(*this, 4276234353Sdim PS2->getTemplateParameters(), 4277218893Sdim PT2, PT1, Info, Deduced, TDF_None, 4278218893Sdim /*PartialOrdering=*/true, 4279218893Sdim /*RefParamComparisons=*/0); 4280218893Sdim if (Better1) { 4281239462Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end()); 4282218893Sdim InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2, 4283239462Sdim DeducedArgs, Info); 4284218893Sdim Better1 = !::FinishTemplateArgumentDeduction(*this, PS2, 4285218893Sdim PS1->getTemplateArgs(), 4286207619Srdivacky Deduced, Info); 4287218893Sdim } 4288218893Sdim 4289198092Srdivacky // Determine whether PS2 is at least as specialized as PS1 4290199482Srdivacky Deduced.clear(); 4291198092Srdivacky Deduced.resize(PS1->getTemplateParameters()->size()); 4292234353Sdim bool Better2 = !DeduceTemplateArgumentsByTypeMatch(*this, 4293234353Sdim PS1->getTemplateParameters(), 4294218893Sdim PT1, PT2, Info, Deduced, TDF_None, 4295218893Sdim /*PartialOrdering=*/true, 4296218893Sdim /*RefParamComparisons=*/0); 4297218893Sdim if (Better2) { 4298239462Sdim SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end()); 4299218893Sdim InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1, 4300239462Sdim DeducedArgs, Info); 4301218893Sdim Better2 = !::FinishTemplateArgumentDeduction(*this, PS1, 4302218893Sdim PS2->getTemplateArgs(), 4303207619Srdivacky Deduced, Info); 4304218893Sdim } 4305218893Sdim 4306198092Srdivacky if (Better1 == Better2) 4307198092Srdivacky return 0; 4308218893Sdim 4309198092Srdivacky return Better1? PS1 : PS2; 4310198092Srdivacky} 4311198092Srdivacky 4312198092Srdivackystatic void 4313234353SdimMarkUsedTemplateParameters(ASTContext &Ctx, 4314198092Srdivacky const TemplateArgument &TemplateArg, 4315198092Srdivacky bool OnlyDeduced, 4316198893Srdivacky unsigned Depth, 4317234353Sdim llvm::SmallBitVector &Used); 4318198092Srdivacky 4319198092Srdivacky/// \brief Mark the template parameters that are used by the given 4320194179Sed/// expression. 4321198092Srdivackystatic void 4322234353SdimMarkUsedTemplateParameters(ASTContext &Ctx, 4323198092Srdivacky const Expr *E, 4324198092Srdivacky bool OnlyDeduced, 4325198893Srdivacky unsigned Depth, 4326234353Sdim llvm::SmallBitVector &Used) { 4327218893Sdim // We can deduce from a pack expansion. 4328218893Sdim if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E)) 4329218893Sdim E = Expansion->getPattern(); 4330218893Sdim 4331239462Sdim // Skip through any implicit casts we added while type-checking, and any 4332239462Sdim // substitutions performed by template alias expansion. 4333239462Sdim while (1) { 4334239462Sdim if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E)) 4335239462Sdim E = ICE->getSubExpr(); 4336239462Sdim else if (const SubstNonTypeTemplateParmExpr *Subst = 4337239462Sdim dyn_cast<SubstNonTypeTemplateParmExpr>(E)) 4338239462Sdim E = Subst->getReplacement(); 4339239462Sdim else 4340239462Sdim break; 4341239462Sdim } 4342218893Sdim 4343218893Sdim // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to 4344198092Srdivacky // find other occurrences of template parameters. 4345194613Sed const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E); 4346202379Srdivacky if (!DRE) 4347194179Sed return; 4348194179Sed 4349198092Srdivacky const NonTypeTemplateParmDecl *NTTP 4350194179Sed = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 4351194179Sed if (!NTTP) 4352194179Sed return; 4353194179Sed 4354198893Srdivacky if (NTTP->getDepth() == Depth) 4355198893Srdivacky Used[NTTP->getIndex()] = true; 4356194179Sed} 4357194179Sed 4358198092Srdivacky/// \brief Mark the template parameters that are used by the given 4359198092Srdivacky/// nested name specifier. 4360198092Srdivackystatic void 4361234353SdimMarkUsedTemplateParameters(ASTContext &Ctx, 4362198092Srdivacky NestedNameSpecifier *NNS, 4363198092Srdivacky bool OnlyDeduced, 4364198893Srdivacky unsigned Depth, 4365234353Sdim llvm::SmallBitVector &Used) { 4366198092Srdivacky if (!NNS) 4367198092Srdivacky return; 4368218893Sdim 4369234353Sdim MarkUsedTemplateParameters(Ctx, NNS->getPrefix(), OnlyDeduced, Depth, 4370198893Srdivacky Used); 4371234353Sdim MarkUsedTemplateParameters(Ctx, QualType(NNS->getAsType(), 0), 4372198893Srdivacky OnlyDeduced, Depth, Used); 4373198092Srdivacky} 4374218893Sdim 4375198092Srdivacky/// \brief Mark the template parameters that are used by the given 4376198092Srdivacky/// template name. 4377198092Srdivackystatic void 4378234353SdimMarkUsedTemplateParameters(ASTContext &Ctx, 4379198092Srdivacky TemplateName Name, 4380198092Srdivacky bool OnlyDeduced, 4381198893Srdivacky unsigned Depth, 4382234353Sdim llvm::SmallBitVector &Used) { 4383198092Srdivacky if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 4384198092Srdivacky if (TemplateTemplateParmDecl *TTP 4385198893Srdivacky = dyn_cast<TemplateTemplateParmDecl>(Template)) { 4386198893Srdivacky if (TTP->getDepth() == Depth) 4387198893Srdivacky Used[TTP->getIndex()] = true; 4388198893Srdivacky } 4389198092Srdivacky return; 4390198092Srdivacky } 4391218893Sdim 4392199482Srdivacky if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) 4393234353Sdim MarkUsedTemplateParameters(Ctx, QTN->getQualifier(), OnlyDeduced, 4394199482Srdivacky Depth, Used); 4395198092Srdivacky if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 4396234353Sdim MarkUsedTemplateParameters(Ctx, DTN->getQualifier(), OnlyDeduced, 4397198893Srdivacky Depth, Used); 4398198092Srdivacky} 4399198092Srdivacky 4400198092Srdivacky/// \brief Mark the template parameters that are used by the given 4401194179Sed/// type. 4402198092Srdivackystatic void 4403234353SdimMarkUsedTemplateParameters(ASTContext &Ctx, QualType T, 4404198092Srdivacky bool OnlyDeduced, 4405198893Srdivacky unsigned Depth, 4406234353Sdim llvm::SmallBitVector &Used) { 4407198092Srdivacky if (T.isNull()) 4408198092Srdivacky return; 4409218893Sdim 4410194179Sed // Non-dependent types have nothing deducible 4411194179Sed if (!T->isDependentType()) 4412194179Sed return; 4413194179Sed 4414234353Sdim T = Ctx.getCanonicalType(T); 4415194179Sed switch (T->getTypeClass()) { 4416194179Sed case Type::Pointer: 4417234353Sdim MarkUsedTemplateParameters(Ctx, 4418198092Srdivacky cast<PointerType>(T)->getPointeeType(), 4419198092Srdivacky OnlyDeduced, 4420198893Srdivacky Depth, 4421198092Srdivacky Used); 4422194179Sed break; 4423194179Sed 4424194179Sed case Type::BlockPointer: 4425234353Sdim MarkUsedTemplateParameters(Ctx, 4426198092Srdivacky cast<BlockPointerType>(T)->getPointeeType(), 4427198092Srdivacky OnlyDeduced, 4428198893Srdivacky Depth, 4429198092Srdivacky Used); 4430194179Sed break; 4431194179Sed 4432194179Sed case Type::LValueReference: 4433194179Sed case Type::RValueReference: 4434234353Sdim MarkUsedTemplateParameters(Ctx, 4435198092Srdivacky cast<ReferenceType>(T)->getPointeeType(), 4436198092Srdivacky OnlyDeduced, 4437198893Srdivacky Depth, 4438198092Srdivacky Used); 4439194179Sed break; 4440194179Sed 4441194179Sed case Type::MemberPointer: { 4442194179Sed const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 4443234353Sdim MarkUsedTemplateParameters(Ctx, MemPtr->getPointeeType(), OnlyDeduced, 4444198893Srdivacky Depth, Used); 4445234353Sdim MarkUsedTemplateParameters(Ctx, QualType(MemPtr->getClass(), 0), 4446198893Srdivacky OnlyDeduced, Depth, Used); 4447194179Sed break; 4448194179Sed } 4449194179Sed 4450194179Sed case Type::DependentSizedArray: 4451234353Sdim MarkUsedTemplateParameters(Ctx, 4452198092Srdivacky cast<DependentSizedArrayType>(T)->getSizeExpr(), 4453198893Srdivacky OnlyDeduced, Depth, Used); 4454194179Sed // Fall through to check the element type 4455194179Sed 4456194179Sed case Type::ConstantArray: 4457194179Sed case Type::IncompleteArray: 4458234353Sdim MarkUsedTemplateParameters(Ctx, 4459198092Srdivacky cast<ArrayType>(T)->getElementType(), 4460198893Srdivacky OnlyDeduced, Depth, Used); 4461194179Sed break; 4462194179Sed 4463194179Sed case Type::Vector: 4464194179Sed case Type::ExtVector: 4465234353Sdim MarkUsedTemplateParameters(Ctx, 4466198092Srdivacky cast<VectorType>(T)->getElementType(), 4467198893Srdivacky OnlyDeduced, Depth, Used); 4468194179Sed break; 4469194179Sed 4470194613Sed case Type::DependentSizedExtVector: { 4471194613Sed const DependentSizedExtVectorType *VecType 4472194613Sed = cast<DependentSizedExtVectorType>(T); 4473234353Sdim MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced, 4474198893Srdivacky Depth, Used); 4475234353Sdim MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced, 4476198893Srdivacky Depth, Used); 4477194613Sed break; 4478194613Sed } 4479194613Sed 4480194179Sed case Type::FunctionProto: { 4481194613Sed const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 4482234353Sdim MarkUsedTemplateParameters(Ctx, Proto->getResultType(), OnlyDeduced, 4483198893Srdivacky Depth, Used); 4484194179Sed for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I) 4485234353Sdim MarkUsedTemplateParameters(Ctx, Proto->getArgType(I), OnlyDeduced, 4486198893Srdivacky Depth, Used); 4487194179Sed break; 4488194179Sed } 4489194179Sed 4490198893Srdivacky case Type::TemplateTypeParm: { 4491198893Srdivacky const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T); 4492198893Srdivacky if (TTP->getDepth() == Depth) 4493198893Srdivacky Used[TTP->getIndex()] = true; 4494194179Sed break; 4495198893Srdivacky } 4496194179Sed 4497218893Sdim case Type::SubstTemplateTypeParmPack: { 4498218893Sdim const SubstTemplateTypeParmPackType *Subst 4499218893Sdim = cast<SubstTemplateTypeParmPackType>(T); 4500234353Sdim MarkUsedTemplateParameters(Ctx, 4501218893Sdim QualType(Subst->getReplacedParameter(), 0), 4502218893Sdim OnlyDeduced, Depth, Used); 4503234353Sdim MarkUsedTemplateParameters(Ctx, Subst->getArgumentPack(), 4504218893Sdim OnlyDeduced, Depth, Used); 4505218893Sdim break; 4506218893Sdim } 4507218893Sdim 4508207619Srdivacky case Type::InjectedClassName: 4509207619Srdivacky T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType(); 4510207619Srdivacky // fall through 4511207619Srdivacky 4512194179Sed case Type::TemplateSpecialization: { 4513198092Srdivacky const TemplateSpecializationType *Spec 4514194613Sed = cast<TemplateSpecializationType>(T); 4515234353Sdim MarkUsedTemplateParameters(Ctx, Spec->getTemplateName(), OnlyDeduced, 4516198893Srdivacky Depth, Used); 4517218893Sdim 4518218893Sdim // C++0x [temp.deduct.type]p9: 4519218893Sdim // If the template argument list of P contains a pack expansion that is not 4520218893Sdim // the last template argument, the entire template argument list is a 4521218893Sdim // non-deduced context. 4522218893Sdim if (OnlyDeduced && 4523218893Sdim hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 4524218893Sdim break; 4525218893Sdim 4526198092Srdivacky for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 4527234353Sdim MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth, 4528198893Srdivacky Used); 4529194179Sed break; 4530194179Sed } 4531194179Sed 4532198092Srdivacky case Type::Complex: 4533198092Srdivacky if (!OnlyDeduced) 4534234353Sdim MarkUsedTemplateParameters(Ctx, 4535198092Srdivacky cast<ComplexType>(T)->getElementType(), 4536198893Srdivacky OnlyDeduced, Depth, Used); 4537198092Srdivacky break; 4538198092Srdivacky 4539226633Sdim case Type::Atomic: 4540226633Sdim if (!OnlyDeduced) 4541234353Sdim MarkUsedTemplateParameters(Ctx, 4542226633Sdim cast<AtomicType>(T)->getValueType(), 4543226633Sdim OnlyDeduced, Depth, Used); 4544226633Sdim break; 4545226633Sdim 4546206084Srdivacky case Type::DependentName: 4547198092Srdivacky if (!OnlyDeduced) 4548234353Sdim MarkUsedTemplateParameters(Ctx, 4549206084Srdivacky cast<DependentNameType>(T)->getQualifier(), 4550198893Srdivacky OnlyDeduced, Depth, Used); 4551198092Srdivacky break; 4552198092Srdivacky 4553210299Sed case Type::DependentTemplateSpecialization: { 4554210299Sed const DependentTemplateSpecializationType *Spec 4555210299Sed = cast<DependentTemplateSpecializationType>(T); 4556210299Sed if (!OnlyDeduced) 4557234353Sdim MarkUsedTemplateParameters(Ctx, Spec->getQualifier(), 4558210299Sed OnlyDeduced, Depth, Used); 4559218893Sdim 4560218893Sdim // C++0x [temp.deduct.type]p9: 4561218893Sdim // If the template argument list of P contains a pack expansion that is not 4562218893Sdim // the last template argument, the entire template argument list is a 4563218893Sdim // non-deduced context. 4564218893Sdim if (OnlyDeduced && 4565218893Sdim hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs())) 4566218893Sdim break; 4567218893Sdim 4568210299Sed for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) 4569234353Sdim MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth, 4570210299Sed Used); 4571210299Sed break; 4572210299Sed } 4573210299Sed 4574204643Srdivacky case Type::TypeOf: 4575204643Srdivacky if (!OnlyDeduced) 4576234353Sdim MarkUsedTemplateParameters(Ctx, 4577204643Srdivacky cast<TypeOfType>(T)->getUnderlyingType(), 4578204643Srdivacky OnlyDeduced, Depth, Used); 4579204643Srdivacky break; 4580204643Srdivacky 4581204643Srdivacky case Type::TypeOfExpr: 4582204643Srdivacky if (!OnlyDeduced) 4583234353Sdim MarkUsedTemplateParameters(Ctx, 4584204643Srdivacky cast<TypeOfExprType>(T)->getUnderlyingExpr(), 4585204643Srdivacky OnlyDeduced, Depth, Used); 4586204643Srdivacky break; 4587204643Srdivacky 4588204643Srdivacky case Type::Decltype: 4589204643Srdivacky if (!OnlyDeduced) 4590234353Sdim MarkUsedTemplateParameters(Ctx, 4591204643Srdivacky cast<DecltypeType>(T)->getUnderlyingExpr(), 4592204643Srdivacky OnlyDeduced, Depth, Used); 4593204643Srdivacky break; 4594204643Srdivacky 4595223017Sdim case Type::UnaryTransform: 4596223017Sdim if (!OnlyDeduced) 4597234353Sdim MarkUsedTemplateParameters(Ctx, 4598223017Sdim cast<UnaryTransformType>(T)->getUnderlyingType(), 4599223017Sdim OnlyDeduced, Depth, Used); 4600223017Sdim break; 4601223017Sdim 4602218893Sdim case Type::PackExpansion: 4603234353Sdim MarkUsedTemplateParameters(Ctx, 4604218893Sdim cast<PackExpansionType>(T)->getPattern(), 4605218893Sdim OnlyDeduced, Depth, Used); 4606218893Sdim break; 4607218893Sdim 4608218893Sdim case Type::Auto: 4609234353Sdim MarkUsedTemplateParameters(Ctx, 4610218893Sdim cast<AutoType>(T)->getDeducedType(), 4611218893Sdim OnlyDeduced, Depth, Used); 4612218893Sdim 4613198092Srdivacky // None of these types have any template parameters in them. 4614194179Sed case Type::Builtin: 4615194179Sed case Type::VariableArray: 4616194179Sed case Type::FunctionNoProto: 4617194179Sed case Type::Record: 4618194179Sed case Type::Enum: 4619194179Sed case Type::ObjCInterface: 4620208600Srdivacky case Type::ObjCObject: 4621194613Sed case Type::ObjCObjectPointer: 4622200583Srdivacky case Type::UnresolvedUsing: 4623194179Sed#define TYPE(Class, Base) 4624194179Sed#define ABSTRACT_TYPE(Class, Base) 4625194179Sed#define DEPENDENT_TYPE(Class, Base) 4626194179Sed#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 4627194179Sed#include "clang/AST/TypeNodes.def" 4628194179Sed break; 4629194179Sed } 4630194179Sed} 4631194179Sed 4632198092Srdivacky/// \brief Mark the template parameters that are used by this 4633194179Sed/// template argument. 4634198092Srdivackystatic void 4635234353SdimMarkUsedTemplateParameters(ASTContext &Ctx, 4636198092Srdivacky const TemplateArgument &TemplateArg, 4637198092Srdivacky bool OnlyDeduced, 4638198893Srdivacky unsigned Depth, 4639234353Sdim llvm::SmallBitVector &Used) { 4640194179Sed switch (TemplateArg.getKind()) { 4641194179Sed case TemplateArgument::Null: 4642194179Sed case TemplateArgument::Integral: 4643234353Sdim case TemplateArgument::Declaration: 4644194179Sed break; 4645198092Srdivacky 4646243830Sdim case TemplateArgument::NullPtr: 4647243830Sdim MarkUsedTemplateParameters(Ctx, TemplateArg.getNullPtrType(), OnlyDeduced, 4648243830Sdim Depth, Used); 4649243830Sdim break; 4650243830Sdim 4651194179Sed case TemplateArgument::Type: 4652234353Sdim MarkUsedTemplateParameters(Ctx, TemplateArg.getAsType(), OnlyDeduced, 4653198893Srdivacky Depth, Used); 4654194179Sed break; 4655194179Sed 4656199482Srdivacky case TemplateArgument::Template: 4657218893Sdim case TemplateArgument::TemplateExpansion: 4658234353Sdim MarkUsedTemplateParameters(Ctx, 4659218893Sdim TemplateArg.getAsTemplateOrTemplatePattern(), 4660199482Srdivacky OnlyDeduced, Depth, Used); 4661194179Sed break; 4662194179Sed 4663194179Sed case TemplateArgument::Expression: 4664234353Sdim MarkUsedTemplateParameters(Ctx, TemplateArg.getAsExpr(), OnlyDeduced, 4665198893Srdivacky Depth, Used); 4666194179Sed break; 4667218893Sdim 4668194613Sed case TemplateArgument::Pack: 4669198092Srdivacky for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(), 4670198092Srdivacky PEnd = TemplateArg.pack_end(); 4671198092Srdivacky P != PEnd; ++P) 4672234353Sdim MarkUsedTemplateParameters(Ctx, *P, OnlyDeduced, Depth, Used); 4673194613Sed break; 4674194179Sed } 4675194179Sed} 4676194179Sed 4677239462Sdim/// \brief Mark which template parameters can be deduced from a given 4678194179Sed/// template argument list. 4679194179Sed/// 4680194179Sed/// \param TemplateArgs the template argument list from which template 4681194179Sed/// parameters will be deduced. 4682194179Sed/// 4683239462Sdim/// \param Used a bit vector whose elements will be set to \c true 4684194179Sed/// to indicate when the corresponding template parameter will be 4685194179Sed/// deduced. 4686198092Srdivackyvoid 4687198092SrdivackySema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 4688198893Srdivacky bool OnlyDeduced, unsigned Depth, 4689234353Sdim llvm::SmallBitVector &Used) { 4690218893Sdim // C++0x [temp.deduct.type]p9: 4691218893Sdim // If the template argument list of P contains a pack expansion that is not 4692218893Sdim // the last template argument, the entire template argument list is a 4693218893Sdim // non-deduced context. 4694218893Sdim if (OnlyDeduced && 4695218893Sdim hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size())) 4696218893Sdim return; 4697218893Sdim 4698194179Sed for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 4699234353Sdim ::MarkUsedTemplateParameters(Context, TemplateArgs[I], OnlyDeduced, 4700198893Srdivacky Depth, Used); 4701194179Sed} 4702198092Srdivacky 4703198092Srdivacky/// \brief Marks all of the template parameters that will be deduced by a 4704198092Srdivacky/// call to the given function template. 4705218893Sdimvoid 4706234353SdimSema::MarkDeducedTemplateParameters(ASTContext &Ctx, 4707249423Sdim const FunctionTemplateDecl *FunctionTemplate, 4708234353Sdim llvm::SmallBitVector &Deduced) { 4709218893Sdim TemplateParameterList *TemplateParams 4710198092Srdivacky = FunctionTemplate->getTemplateParameters(); 4711198092Srdivacky Deduced.clear(); 4712198092Srdivacky Deduced.resize(TemplateParams->size()); 4713218893Sdim 4714198092Srdivacky FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 4715198092Srdivacky for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 4716234353Sdim ::MarkUsedTemplateParameters(Ctx, Function->getParamDecl(I)->getType(), 4717198893Srdivacky true, TemplateParams->getDepth(), Deduced); 4718198092Srdivacky} 4719224145Sdim 4720224145Sdimbool hasDeducibleTemplateParameters(Sema &S, 4721224145Sdim FunctionTemplateDecl *FunctionTemplate, 4722224145Sdim QualType T) { 4723224145Sdim if (!T->isDependentType()) 4724224145Sdim return false; 4725224145Sdim 4726224145Sdim TemplateParameterList *TemplateParams 4727224145Sdim = FunctionTemplate->getTemplateParameters(); 4728234353Sdim llvm::SmallBitVector Deduced(TemplateParams->size()); 4729234353Sdim ::MarkUsedTemplateParameters(S.Context, T, true, TemplateParams->getDepth(), 4730224145Sdim Deduced); 4731224145Sdim 4732234353Sdim return Deduced.any(); 4733224145Sdim} 4734