1 //===- SemaTemplateDeduction.cpp - Template Argument Deduction ------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements C++ template argument deduction. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "TreeTransform.h" 14 #include "TypeLocBuilder.h" 15 #include "clang/AST/ASTContext.h" 16 #include "clang/AST/ASTLambda.h" 17 #include "clang/AST/Decl.h" 18 #include "clang/AST/DeclAccessPair.h" 19 #include "clang/AST/DeclBase.h" 20 #include "clang/AST/DeclCXX.h" 21 #include "clang/AST/DeclTemplate.h" 22 #include "clang/AST/DeclarationName.h" 23 #include "clang/AST/Expr.h" 24 #include "clang/AST/ExprCXX.h" 25 #include "clang/AST/NestedNameSpecifier.h" 26 #include "clang/AST/RecursiveASTVisitor.h" 27 #include "clang/AST/TemplateBase.h" 28 #include "clang/AST/TemplateName.h" 29 #include "clang/AST/Type.h" 30 #include "clang/AST/TypeLoc.h" 31 #include "clang/AST/UnresolvedSet.h" 32 #include "clang/Basic/AddressSpaces.h" 33 #include "clang/Basic/ExceptionSpecificationType.h" 34 #include "clang/Basic/LLVM.h" 35 #include "clang/Basic/LangOptions.h" 36 #include "clang/Basic/PartialDiagnostic.h" 37 #include "clang/Basic/SourceLocation.h" 38 #include "clang/Basic/Specifiers.h" 39 #include "clang/Sema/EnterExpressionEvaluationContext.h" 40 #include "clang/Sema/Ownership.h" 41 #include "clang/Sema/Sema.h" 42 #include "clang/Sema/Template.h" 43 #include "clang/Sema/TemplateDeduction.h" 44 #include "llvm/ADT/APInt.h" 45 #include "llvm/ADT/APSInt.h" 46 #include "llvm/ADT/ArrayRef.h" 47 #include "llvm/ADT/DenseMap.h" 48 #include "llvm/ADT/FoldingSet.h" 49 #include "llvm/ADT/SmallBitVector.h" 50 #include "llvm/ADT/SmallPtrSet.h" 51 #include "llvm/ADT/SmallVector.h" 52 #include "llvm/Support/Casting.h" 53 #include "llvm/Support/Compiler.h" 54 #include "llvm/Support/ErrorHandling.h" 55 #include <algorithm> 56 #include <cassert> 57 #include <optional> 58 #include <tuple> 59 #include <type_traits> 60 #include <utility> 61 62 namespace clang { 63 64 /// Various flags that control template argument deduction. 65 /// 66 /// These flags can be bitwise-OR'd together. 67 enum TemplateDeductionFlags { 68 /// No template argument deduction flags, which indicates the 69 /// strictest results for template argument deduction (as used for, e.g., 70 /// matching class template partial specializations). 71 TDF_None = 0, 72 73 /// Within template argument deduction from a function call, we are 74 /// matching with a parameter type for which the original parameter was 75 /// a reference. 76 TDF_ParamWithReferenceType = 0x1, 77 78 /// Within template argument deduction from a function call, we 79 /// are matching in a case where we ignore cv-qualifiers. 80 TDF_IgnoreQualifiers = 0x02, 81 82 /// Within template argument deduction from a function call, 83 /// we are matching in a case where we can perform template argument 84 /// deduction from a template-id of a derived class of the argument type. 85 TDF_DerivedClass = 0x04, 86 87 /// Allow non-dependent types to differ, e.g., when performing 88 /// template argument deduction from a function call where conversions 89 /// may apply. 90 TDF_SkipNonDependent = 0x08, 91 92 /// Whether we are performing template argument deduction for 93 /// parameters and arguments in a top-level template argument 94 TDF_TopLevelParameterTypeList = 0x10, 95 96 /// Within template argument deduction from overload resolution per 97 /// C++ [over.over] allow matching function types that are compatible in 98 /// terms of noreturn and default calling convention adjustments, or 99 /// similarly matching a declared template specialization against a 100 /// possible template, per C++ [temp.deduct.decl]. In either case, permit 101 /// deduction where the parameter is a function type that can be converted 102 /// to the argument type. 103 TDF_AllowCompatibleFunctionType = 0x20, 104 105 /// Within template argument deduction for a conversion function, we are 106 /// matching with an argument type for which the original argument was 107 /// a reference. 108 TDF_ArgWithReferenceType = 0x40, 109 }; 110 } 111 112 using namespace clang; 113 using namespace sema; 114 115 /// Compare two APSInts, extending and switching the sign as 116 /// necessary to compare their values regardless of underlying type. 117 static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) { 118 if (Y.getBitWidth() > X.getBitWidth()) 119 X = X.extend(Y.getBitWidth()); 120 else if (Y.getBitWidth() < X.getBitWidth()) 121 Y = Y.extend(X.getBitWidth()); 122 123 // If there is a signedness mismatch, correct it. 124 if (X.isSigned() != Y.isSigned()) { 125 // If the signed value is negative, then the values cannot be the same. 126 if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative())) 127 return false; 128 129 Y.setIsSigned(true); 130 X.setIsSigned(true); 131 } 132 133 return X == Y; 134 } 135 136 static Sema::TemplateDeductionResult DeduceTemplateArgumentsByTypeMatch( 137 Sema &S, TemplateParameterList *TemplateParams, QualType Param, 138 QualType Arg, TemplateDeductionInfo &Info, 139 SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF, 140 bool PartialOrdering = false, bool DeducedFromArrayBound = false); 141 142 static Sema::TemplateDeductionResult 143 DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams, 144 ArrayRef<TemplateArgument> Ps, 145 ArrayRef<TemplateArgument> As, 146 TemplateDeductionInfo &Info, 147 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 148 bool NumberOfArgumentsMustMatch); 149 150 static void MarkUsedTemplateParameters(ASTContext &Ctx, 151 const TemplateArgument &TemplateArg, 152 bool OnlyDeduced, unsigned Depth, 153 llvm::SmallBitVector &Used); 154 155 static void MarkUsedTemplateParameters(ASTContext &Ctx, QualType T, 156 bool OnlyDeduced, unsigned Level, 157 llvm::SmallBitVector &Deduced); 158 159 /// If the given expression is of a form that permits the deduction 160 /// of a non-type template parameter, return the declaration of that 161 /// non-type template parameter. 162 static const NonTypeTemplateParmDecl * 163 getDeducedParameterFromExpr(const Expr *E, unsigned Depth) { 164 // If we are within an alias template, the expression may have undergone 165 // any number of parameter substitutions already. 166 while (true) { 167 if (const auto *IC = dyn_cast<ImplicitCastExpr>(E)) 168 E = IC->getSubExpr(); 169 else if (const auto *CE = dyn_cast<ConstantExpr>(E)) 170 E = CE->getSubExpr(); 171 else if (const auto *Subst = dyn_cast<SubstNonTypeTemplateParmExpr>(E)) 172 E = Subst->getReplacement(); 173 else if (const auto *CCE = dyn_cast<CXXConstructExpr>(E)) { 174 // Look through implicit copy construction from an lvalue of the same type. 175 if (CCE->getParenOrBraceRange().isValid()) 176 break; 177 // Note, there could be default arguments. 178 assert(CCE->getNumArgs() >= 1 && "implicit construct expr should have 1 arg"); 179 E = CCE->getArg(0); 180 } else 181 break; 182 } 183 184 if (const auto *DRE = dyn_cast<DeclRefExpr>(E)) 185 if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl())) 186 if (NTTP->getDepth() == Depth) 187 return NTTP; 188 189 return nullptr; 190 } 191 192 static const NonTypeTemplateParmDecl * 193 getDeducedParameterFromExpr(TemplateDeductionInfo &Info, Expr *E) { 194 return getDeducedParameterFromExpr(E, Info.getDeducedDepth()); 195 } 196 197 /// Determine whether two declaration pointers refer to the same 198 /// declaration. 199 static bool isSameDeclaration(Decl *X, Decl *Y) { 200 if (NamedDecl *NX = dyn_cast<NamedDecl>(X)) 201 X = NX->getUnderlyingDecl(); 202 if (NamedDecl *NY = dyn_cast<NamedDecl>(Y)) 203 Y = NY->getUnderlyingDecl(); 204 205 return X->getCanonicalDecl() == Y->getCanonicalDecl(); 206 } 207 208 /// Verify that the given, deduced template arguments are compatible. 209 /// 210 /// \returns The deduced template argument, or a NULL template argument if 211 /// the deduced template arguments were incompatible. 212 static DeducedTemplateArgument 213 checkDeducedTemplateArguments(ASTContext &Context, 214 const DeducedTemplateArgument &X, 215 const DeducedTemplateArgument &Y, 216 bool AggregateCandidateDeduction = false) { 217 // We have no deduction for one or both of the arguments; they're compatible. 218 if (X.isNull()) 219 return Y; 220 if (Y.isNull()) 221 return X; 222 223 // If we have two non-type template argument values deduced for the same 224 // parameter, they must both match the type of the parameter, and thus must 225 // match each other's type. As we're only keeping one of them, we must check 226 // for that now. The exception is that if either was deduced from an array 227 // bound, the type is permitted to differ. 228 if (!X.wasDeducedFromArrayBound() && !Y.wasDeducedFromArrayBound()) { 229 QualType XType = X.getNonTypeTemplateArgumentType(); 230 if (!XType.isNull()) { 231 QualType YType = Y.getNonTypeTemplateArgumentType(); 232 if (YType.isNull() || !Context.hasSameType(XType, YType)) 233 return DeducedTemplateArgument(); 234 } 235 } 236 237 switch (X.getKind()) { 238 case TemplateArgument::Null: 239 llvm_unreachable("Non-deduced template arguments handled above"); 240 241 case TemplateArgument::Type: { 242 // If two template type arguments have the same type, they're compatible. 243 QualType TX = X.getAsType(), TY = Y.getAsType(); 244 if (Y.getKind() == TemplateArgument::Type && Context.hasSameType(TX, TY)) 245 return DeducedTemplateArgument(Context.getCommonSugaredType(TX, TY), 246 X.wasDeducedFromArrayBound() || 247 Y.wasDeducedFromArrayBound()); 248 249 // If one of the two arguments was deduced from an array bound, the other 250 // supersedes it. 251 if (X.wasDeducedFromArrayBound() != Y.wasDeducedFromArrayBound()) 252 return X.wasDeducedFromArrayBound() ? Y : X; 253 254 // The arguments are not compatible. 255 return DeducedTemplateArgument(); 256 } 257 258 case TemplateArgument::Integral: 259 // If we deduced a constant in one case and either a dependent expression or 260 // declaration in another case, keep the integral constant. 261 // If both are integral constants with the same value, keep that value. 262 if (Y.getKind() == TemplateArgument::Expression || 263 Y.getKind() == TemplateArgument::Declaration || 264 (Y.getKind() == TemplateArgument::Integral && 265 hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral()))) 266 return X.wasDeducedFromArrayBound() ? Y : X; 267 268 // All other combinations are incompatible. 269 return DeducedTemplateArgument(); 270 271 case TemplateArgument::Template: 272 if (Y.getKind() == TemplateArgument::Template && 273 Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate())) 274 return X; 275 276 // All other combinations are incompatible. 277 return DeducedTemplateArgument(); 278 279 case TemplateArgument::TemplateExpansion: 280 if (Y.getKind() == TemplateArgument::TemplateExpansion && 281 Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(), 282 Y.getAsTemplateOrTemplatePattern())) 283 return X; 284 285 // All other combinations are incompatible. 286 return DeducedTemplateArgument(); 287 288 case TemplateArgument::Expression: { 289 if (Y.getKind() != TemplateArgument::Expression) 290 return checkDeducedTemplateArguments(Context, Y, X); 291 292 // Compare the expressions for equality 293 llvm::FoldingSetNodeID ID1, ID2; 294 X.getAsExpr()->Profile(ID1, Context, true); 295 Y.getAsExpr()->Profile(ID2, Context, true); 296 if (ID1 == ID2) 297 return X.wasDeducedFromArrayBound() ? Y : X; 298 299 // Differing dependent expressions are incompatible. 300 return DeducedTemplateArgument(); 301 } 302 303 case TemplateArgument::Declaration: 304 assert(!X.wasDeducedFromArrayBound()); 305 306 // If we deduced a declaration and a dependent expression, keep the 307 // declaration. 308 if (Y.getKind() == TemplateArgument::Expression) 309 return X; 310 311 // If we deduced a declaration and an integral constant, keep the 312 // integral constant and whichever type did not come from an array 313 // bound. 314 if (Y.getKind() == TemplateArgument::Integral) { 315 if (Y.wasDeducedFromArrayBound()) 316 return TemplateArgument(Context, Y.getAsIntegral(), 317 X.getParamTypeForDecl()); 318 return Y; 319 } 320 321 // If we deduced two declarations, make sure that they refer to the 322 // same declaration. 323 if (Y.getKind() == TemplateArgument::Declaration && 324 isSameDeclaration(X.getAsDecl(), Y.getAsDecl())) 325 return X; 326 327 // All other combinations are incompatible. 328 return DeducedTemplateArgument(); 329 330 case TemplateArgument::NullPtr: 331 // If we deduced a null pointer and a dependent expression, keep the 332 // null pointer. 333 if (Y.getKind() == TemplateArgument::Expression) 334 return TemplateArgument(Context.getCommonSugaredType( 335 X.getNullPtrType(), Y.getAsExpr()->getType()), 336 true); 337 338 // If we deduced a null pointer and an integral constant, keep the 339 // integral constant. 340 if (Y.getKind() == TemplateArgument::Integral) 341 return Y; 342 343 // If we deduced two null pointers, they are the same. 344 if (Y.getKind() == TemplateArgument::NullPtr) 345 return TemplateArgument( 346 Context.getCommonSugaredType(X.getNullPtrType(), Y.getNullPtrType()), 347 true); 348 349 // All other combinations are incompatible. 350 return DeducedTemplateArgument(); 351 352 case TemplateArgument::Pack: { 353 if (Y.getKind() != TemplateArgument::Pack || 354 (!AggregateCandidateDeduction && X.pack_size() != Y.pack_size())) 355 return DeducedTemplateArgument(); 356 357 llvm::SmallVector<TemplateArgument, 8> NewPack; 358 for (TemplateArgument::pack_iterator 359 XA = X.pack_begin(), 360 XAEnd = X.pack_end(), YA = Y.pack_begin(), YAEnd = Y.pack_end(); 361 XA != XAEnd; ++XA, ++YA) { 362 if (YA != YAEnd) { 363 TemplateArgument Merged = checkDeducedTemplateArguments( 364 Context, DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()), 365 DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound())); 366 if (Merged.isNull() && !(XA->isNull() && YA->isNull())) 367 return DeducedTemplateArgument(); 368 NewPack.push_back(Merged); 369 } else { 370 NewPack.push_back(*XA); 371 } 372 } 373 374 return DeducedTemplateArgument( 375 TemplateArgument::CreatePackCopy(Context, NewPack), 376 X.wasDeducedFromArrayBound() && Y.wasDeducedFromArrayBound()); 377 } 378 } 379 380 llvm_unreachable("Invalid TemplateArgument Kind!"); 381 } 382 383 /// Deduce the value of the given non-type template parameter 384 /// as the given deduced template argument. All non-type template parameter 385 /// deduction is funneled through here. 386 static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument( 387 Sema &S, TemplateParameterList *TemplateParams, 388 const NonTypeTemplateParmDecl *NTTP, const DeducedTemplateArgument &NewDeduced, 389 QualType ValueType, TemplateDeductionInfo &Info, 390 SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 391 assert(NTTP->getDepth() == Info.getDeducedDepth() && 392 "deducing non-type template argument with wrong depth"); 393 394 DeducedTemplateArgument Result = checkDeducedTemplateArguments( 395 S.Context, Deduced[NTTP->getIndex()], NewDeduced); 396 if (Result.isNull()) { 397 Info.Param = const_cast<NonTypeTemplateParmDecl*>(NTTP); 398 Info.FirstArg = Deduced[NTTP->getIndex()]; 399 Info.SecondArg = NewDeduced; 400 return Sema::TDK_Inconsistent; 401 } 402 403 Deduced[NTTP->getIndex()] = Result; 404 if (!S.getLangOpts().CPlusPlus17) 405 return Sema::TDK_Success; 406 407 if (NTTP->isExpandedParameterPack()) 408 // FIXME: We may still need to deduce parts of the type here! But we 409 // don't have any way to find which slice of the type to use, and the 410 // type stored on the NTTP itself is nonsense. Perhaps the type of an 411 // expanded NTTP should be a pack expansion type? 412 return Sema::TDK_Success; 413 414 // Get the type of the parameter for deduction. If it's a (dependent) array 415 // or function type, we will not have decayed it yet, so do that now. 416 QualType ParamType = S.Context.getAdjustedParameterType(NTTP->getType()); 417 if (auto *Expansion = dyn_cast<PackExpansionType>(ParamType)) 418 ParamType = Expansion->getPattern(); 419 420 // FIXME: It's not clear how deduction of a parameter of reference 421 // type from an argument (of non-reference type) should be performed. 422 // For now, we just remove reference types from both sides and let 423 // the final check for matching types sort out the mess. 424 ValueType = ValueType.getNonReferenceType(); 425 if (ParamType->isReferenceType()) 426 ParamType = ParamType.getNonReferenceType(); 427 else 428 // Top-level cv-qualifiers are irrelevant for a non-reference type. 429 ValueType = ValueType.getUnqualifiedType(); 430 431 return DeduceTemplateArgumentsByTypeMatch( 432 S, TemplateParams, ParamType, ValueType, Info, Deduced, 433 TDF_SkipNonDependent, /*PartialOrdering=*/false, 434 /*ArrayBound=*/NewDeduced.wasDeducedFromArrayBound()); 435 } 436 437 /// Deduce the value of the given non-type template parameter 438 /// from the given integral constant. 439 static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument( 440 Sema &S, TemplateParameterList *TemplateParams, 441 const NonTypeTemplateParmDecl *NTTP, const llvm::APSInt &Value, 442 QualType ValueType, bool DeducedFromArrayBound, TemplateDeductionInfo &Info, 443 SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 444 return DeduceNonTypeTemplateArgument( 445 S, TemplateParams, NTTP, 446 DeducedTemplateArgument(S.Context, Value, ValueType, 447 DeducedFromArrayBound), 448 ValueType, Info, Deduced); 449 } 450 451 /// Deduce the value of the given non-type template parameter 452 /// from the given null pointer template argument type. 453 static Sema::TemplateDeductionResult DeduceNullPtrTemplateArgument( 454 Sema &S, TemplateParameterList *TemplateParams, 455 const NonTypeTemplateParmDecl *NTTP, QualType NullPtrType, 456 TemplateDeductionInfo &Info, 457 SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 458 Expr *Value = S.ImpCastExprToType( 459 new (S.Context) CXXNullPtrLiteralExpr(S.Context.NullPtrTy, 460 NTTP->getLocation()), 461 NullPtrType, 462 NullPtrType->isMemberPointerType() ? CK_NullToMemberPointer 463 : CK_NullToPointer) 464 .get(); 465 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, 466 DeducedTemplateArgument(Value), 467 Value->getType(), Info, Deduced); 468 } 469 470 /// Deduce the value of the given non-type template parameter 471 /// from the given type- or value-dependent expression. 472 /// 473 /// \returns true if deduction succeeded, false otherwise. 474 static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument( 475 Sema &S, TemplateParameterList *TemplateParams, 476 const NonTypeTemplateParmDecl *NTTP, Expr *Value, TemplateDeductionInfo &Info, 477 SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 478 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, 479 DeducedTemplateArgument(Value), 480 Value->getType(), Info, Deduced); 481 } 482 483 /// Deduce the value of the given non-type template parameter 484 /// from the given declaration. 485 /// 486 /// \returns true if deduction succeeded, false otherwise. 487 static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument( 488 Sema &S, TemplateParameterList *TemplateParams, 489 const NonTypeTemplateParmDecl *NTTP, ValueDecl *D, QualType T, 490 TemplateDeductionInfo &Info, 491 SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 492 D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : nullptr; 493 TemplateArgument New(D, T); 494 return DeduceNonTypeTemplateArgument( 495 S, TemplateParams, NTTP, DeducedTemplateArgument(New), T, Info, Deduced); 496 } 497 498 static Sema::TemplateDeductionResult 499 DeduceTemplateArguments(Sema &S, 500 TemplateParameterList *TemplateParams, 501 TemplateName Param, 502 TemplateName Arg, 503 TemplateDeductionInfo &Info, 504 SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 505 TemplateDecl *ParamDecl = Param.getAsTemplateDecl(); 506 if (!ParamDecl) { 507 // The parameter type is dependent and is not a template template parameter, 508 // so there is nothing that we can deduce. 509 return Sema::TDK_Success; 510 } 511 512 if (TemplateTemplateParmDecl *TempParam 513 = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) { 514 // If we're not deducing at this depth, there's nothing to deduce. 515 if (TempParam->getDepth() != Info.getDeducedDepth()) 516 return Sema::TDK_Success; 517 518 DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg)); 519 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context, 520 Deduced[TempParam->getIndex()], 521 NewDeduced); 522 if (Result.isNull()) { 523 Info.Param = TempParam; 524 Info.FirstArg = Deduced[TempParam->getIndex()]; 525 Info.SecondArg = NewDeduced; 526 return Sema::TDK_Inconsistent; 527 } 528 529 Deduced[TempParam->getIndex()] = Result; 530 return Sema::TDK_Success; 531 } 532 533 // Verify that the two template names are equivalent. 534 if (S.Context.hasSameTemplateName(Param, Arg)) 535 return Sema::TDK_Success; 536 537 // Mismatch of non-dependent template parameter to argument. 538 Info.FirstArg = TemplateArgument(Param); 539 Info.SecondArg = TemplateArgument(Arg); 540 return Sema::TDK_NonDeducedMismatch; 541 } 542 543 /// Deduce the template arguments by comparing the template parameter 544 /// type (which is a template-id) with the template argument type. 545 /// 546 /// \param S the Sema 547 /// 548 /// \param TemplateParams the template parameters that we are deducing 549 /// 550 /// \param P the parameter type 551 /// 552 /// \param A the argument type 553 /// 554 /// \param Info information about the template argument deduction itself 555 /// 556 /// \param Deduced the deduced template arguments 557 /// 558 /// \returns the result of template argument deduction so far. Note that a 559 /// "success" result means that template argument deduction has not yet failed, 560 /// but it may still fail, later, for other reasons. 561 static Sema::TemplateDeductionResult 562 DeduceTemplateSpecArguments(Sema &S, TemplateParameterList *TemplateParams, 563 const QualType P, QualType A, 564 TemplateDeductionInfo &Info, 565 SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 566 QualType UP = P; 567 if (const auto *IP = P->getAs<InjectedClassNameType>()) 568 UP = IP->getInjectedSpecializationType(); 569 // FIXME: Try to preserve type sugar here, which is hard 570 // because of the unresolved template arguments. 571 const auto *TP = UP.getCanonicalType()->castAs<TemplateSpecializationType>(); 572 TemplateName TNP = TP->getTemplateName(); 573 574 // If the parameter is an alias template, there is nothing to deduce. 575 if (const auto *TD = TNP.getAsTemplateDecl(); TD && TD->isTypeAlias()) 576 return Sema::TDK_Success; 577 578 ArrayRef<TemplateArgument> PResolved = TP->template_arguments(); 579 580 QualType UA = A; 581 // Treat an injected-class-name as its underlying template-id. 582 if (const auto *Injected = A->getAs<InjectedClassNameType>()) 583 UA = Injected->getInjectedSpecializationType(); 584 585 // Check whether the template argument is a dependent template-id. 586 // FIXME: Should not lose sugar here. 587 if (const auto *SA = 588 dyn_cast<TemplateSpecializationType>(UA.getCanonicalType())) { 589 TemplateName TNA = SA->getTemplateName(); 590 591 // If the argument is an alias template, there is nothing to deduce. 592 if (const auto *TD = TNA.getAsTemplateDecl(); TD && TD->isTypeAlias()) 593 return Sema::TDK_Success; 594 595 // Perform template argument deduction for the template name. 596 if (auto Result = 597 DeduceTemplateArguments(S, TemplateParams, TNP, TNA, Info, Deduced)) 598 return Result; 599 // Perform template argument deduction on each template 600 // argument. Ignore any missing/extra arguments, since they could be 601 // filled in by default arguments. 602 return DeduceTemplateArguments(S, TemplateParams, PResolved, 603 SA->template_arguments(), Info, Deduced, 604 /*NumberOfArgumentsMustMatch=*/false); 605 } 606 607 // If the argument type is a class template specialization, we 608 // perform template argument deduction using its template 609 // arguments. 610 const auto *RA = UA->getAs<RecordType>(); 611 const auto *SA = 612 RA ? dyn_cast<ClassTemplateSpecializationDecl>(RA->getDecl()) : nullptr; 613 if (!SA) { 614 Info.FirstArg = TemplateArgument(P); 615 Info.SecondArg = TemplateArgument(A); 616 return Sema::TDK_NonDeducedMismatch; 617 } 618 619 // Perform template argument deduction for the template name. 620 if (auto Result = DeduceTemplateArguments( 621 S, TemplateParams, TP->getTemplateName(), 622 TemplateName(SA->getSpecializedTemplate()), Info, Deduced)) 623 return Result; 624 625 // Perform template argument deduction for the template arguments. 626 return DeduceTemplateArguments(S, TemplateParams, PResolved, 627 SA->getTemplateArgs().asArray(), Info, Deduced, 628 /*NumberOfArgumentsMustMatch=*/true); 629 } 630 631 static bool IsPossiblyOpaquelyQualifiedTypeInternal(const Type *T) { 632 assert(T->isCanonicalUnqualified()); 633 634 switch (T->getTypeClass()) { 635 case Type::TypeOfExpr: 636 case Type::TypeOf: 637 case Type::DependentName: 638 case Type::Decltype: 639 case Type::UnresolvedUsing: 640 case Type::TemplateTypeParm: 641 return true; 642 643 case Type::ConstantArray: 644 case Type::IncompleteArray: 645 case Type::VariableArray: 646 case Type::DependentSizedArray: 647 return IsPossiblyOpaquelyQualifiedTypeInternal( 648 cast<ArrayType>(T)->getElementType().getTypePtr()); 649 650 default: 651 return false; 652 } 653 } 654 655 /// Determines whether the given type is an opaque type that 656 /// might be more qualified when instantiated. 657 static bool IsPossiblyOpaquelyQualifiedType(QualType T) { 658 return IsPossiblyOpaquelyQualifiedTypeInternal( 659 T->getCanonicalTypeInternal().getTypePtr()); 660 } 661 662 /// Helper function to build a TemplateParameter when we don't 663 /// know its type statically. 664 static TemplateParameter makeTemplateParameter(Decl *D) { 665 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D)) 666 return TemplateParameter(TTP); 667 if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) 668 return TemplateParameter(NTTP); 669 670 return TemplateParameter(cast<TemplateTemplateParmDecl>(D)); 671 } 672 673 /// A pack that we're currently deducing. 674 struct clang::DeducedPack { 675 // The index of the pack. 676 unsigned Index; 677 678 // The old value of the pack before we started deducing it. 679 DeducedTemplateArgument Saved; 680 681 // A deferred value of this pack from an inner deduction, that couldn't be 682 // deduced because this deduction hadn't happened yet. 683 DeducedTemplateArgument DeferredDeduction; 684 685 // The new value of the pack. 686 SmallVector<DeducedTemplateArgument, 4> New; 687 688 // The outer deduction for this pack, if any. 689 DeducedPack *Outer = nullptr; 690 691 DeducedPack(unsigned Index) : Index(Index) {} 692 }; 693 694 namespace { 695 696 /// A scope in which we're performing pack deduction. 697 class PackDeductionScope { 698 public: 699 /// Prepare to deduce the packs named within Pattern. 700 PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams, 701 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 702 TemplateDeductionInfo &Info, TemplateArgument Pattern, 703 bool DeducePackIfNotAlreadyDeduced = false) 704 : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info), 705 DeducePackIfNotAlreadyDeduced(DeducePackIfNotAlreadyDeduced){ 706 unsigned NumNamedPacks = addPacks(Pattern); 707 finishConstruction(NumNamedPacks); 708 } 709 710 /// Prepare to directly deduce arguments of the parameter with index \p Index. 711 PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams, 712 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 713 TemplateDeductionInfo &Info, unsigned Index) 714 : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) { 715 addPack(Index); 716 finishConstruction(1); 717 } 718 719 private: 720 void addPack(unsigned Index) { 721 // Save the deduced template argument for the parameter pack expanded 722 // by this pack expansion, then clear out the deduction. 723 DeducedPack Pack(Index); 724 Pack.Saved = Deduced[Index]; 725 Deduced[Index] = TemplateArgument(); 726 727 // FIXME: What if we encounter multiple packs with different numbers of 728 // pre-expanded expansions? (This should already have been diagnosed 729 // during substitution.) 730 if (std::optional<unsigned> ExpandedPackExpansions = 731 getExpandedPackSize(TemplateParams->getParam(Index))) 732 FixedNumExpansions = ExpandedPackExpansions; 733 734 Packs.push_back(Pack); 735 } 736 737 unsigned addPacks(TemplateArgument Pattern) { 738 // Compute the set of template parameter indices that correspond to 739 // parameter packs expanded by the pack expansion. 740 llvm::SmallBitVector SawIndices(TemplateParams->size()); 741 llvm::SmallVector<TemplateArgument, 4> ExtraDeductions; 742 743 auto AddPack = [&](unsigned Index) { 744 if (SawIndices[Index]) 745 return; 746 SawIndices[Index] = true; 747 addPack(Index); 748 749 // Deducing a parameter pack that is a pack expansion also constrains the 750 // packs appearing in that parameter to have the same deduced arity. Also, 751 // in C++17 onwards, deducing a non-type template parameter deduces its 752 // type, so we need to collect the pending deduced values for those packs. 753 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>( 754 TemplateParams->getParam(Index))) { 755 if (!NTTP->isExpandedParameterPack()) 756 if (auto *Expansion = dyn_cast<PackExpansionType>(NTTP->getType())) 757 ExtraDeductions.push_back(Expansion->getPattern()); 758 } 759 // FIXME: Also collect the unexpanded packs in any type and template 760 // parameter packs that are pack expansions. 761 }; 762 763 auto Collect = [&](TemplateArgument Pattern) { 764 SmallVector<UnexpandedParameterPack, 2> Unexpanded; 765 S.collectUnexpandedParameterPacks(Pattern, Unexpanded); 766 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) { 767 unsigned Depth, Index; 768 std::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]); 769 if (Depth == Info.getDeducedDepth()) 770 AddPack(Index); 771 } 772 }; 773 774 // Look for unexpanded packs in the pattern. 775 Collect(Pattern); 776 assert(!Packs.empty() && "Pack expansion without unexpanded packs?"); 777 778 unsigned NumNamedPacks = Packs.size(); 779 780 // Also look for unexpanded packs that are indirectly deduced by deducing 781 // the sizes of the packs in this pattern. 782 while (!ExtraDeductions.empty()) 783 Collect(ExtraDeductions.pop_back_val()); 784 785 return NumNamedPacks; 786 } 787 788 void finishConstruction(unsigned NumNamedPacks) { 789 // Dig out the partially-substituted pack, if there is one. 790 const TemplateArgument *PartialPackArgs = nullptr; 791 unsigned NumPartialPackArgs = 0; 792 std::pair<unsigned, unsigned> PartialPackDepthIndex(-1u, -1u); 793 if (auto *Scope = S.CurrentInstantiationScope) 794 if (auto *Partial = Scope->getPartiallySubstitutedPack( 795 &PartialPackArgs, &NumPartialPackArgs)) 796 PartialPackDepthIndex = getDepthAndIndex(Partial); 797 798 // This pack expansion will have been partially or fully expanded if 799 // it only names explicitly-specified parameter packs (including the 800 // partially-substituted one, if any). 801 bool IsExpanded = true; 802 for (unsigned I = 0; I != NumNamedPacks; ++I) { 803 if (Packs[I].Index >= Info.getNumExplicitArgs()) { 804 IsExpanded = false; 805 IsPartiallyExpanded = false; 806 break; 807 } 808 if (PartialPackDepthIndex == 809 std::make_pair(Info.getDeducedDepth(), Packs[I].Index)) { 810 IsPartiallyExpanded = true; 811 } 812 } 813 814 // Skip over the pack elements that were expanded into separate arguments. 815 // If we partially expanded, this is the number of partial arguments. 816 if (IsPartiallyExpanded) 817 PackElements += NumPartialPackArgs; 818 else if (IsExpanded) 819 PackElements += *FixedNumExpansions; 820 821 for (auto &Pack : Packs) { 822 if (Info.PendingDeducedPacks.size() > Pack.Index) 823 Pack.Outer = Info.PendingDeducedPacks[Pack.Index]; 824 else 825 Info.PendingDeducedPacks.resize(Pack.Index + 1); 826 Info.PendingDeducedPacks[Pack.Index] = &Pack; 827 828 if (PartialPackDepthIndex == 829 std::make_pair(Info.getDeducedDepth(), Pack.Index)) { 830 Pack.New.append(PartialPackArgs, PartialPackArgs + NumPartialPackArgs); 831 // We pre-populate the deduced value of the partially-substituted 832 // pack with the specified value. This is not entirely correct: the 833 // value is supposed to have been substituted, not deduced, but the 834 // cases where this is observable require an exact type match anyway. 835 // 836 // FIXME: If we could represent a "depth i, index j, pack elem k" 837 // parameter, we could substitute the partially-substituted pack 838 // everywhere and avoid this. 839 if (!IsPartiallyExpanded) 840 Deduced[Pack.Index] = Pack.New[PackElements]; 841 } 842 } 843 } 844 845 public: 846 ~PackDeductionScope() { 847 for (auto &Pack : Packs) 848 Info.PendingDeducedPacks[Pack.Index] = Pack.Outer; 849 } 850 851 /// Determine whether this pack has already been partially expanded into a 852 /// sequence of (prior) function parameters / template arguments. 853 bool isPartiallyExpanded() { return IsPartiallyExpanded; } 854 855 /// Determine whether this pack expansion scope has a known, fixed arity. 856 /// This happens if it involves a pack from an outer template that has 857 /// (notionally) already been expanded. 858 bool hasFixedArity() { return FixedNumExpansions.has_value(); } 859 860 /// Determine whether the next element of the argument is still part of this 861 /// pack. This is the case unless the pack is already expanded to a fixed 862 /// length. 863 bool hasNextElement() { 864 return !FixedNumExpansions || *FixedNumExpansions > PackElements; 865 } 866 867 /// Move to deducing the next element in each pack that is being deduced. 868 void nextPackElement() { 869 // Capture the deduced template arguments for each parameter pack expanded 870 // by this pack expansion, add them to the list of arguments we've deduced 871 // for that pack, then clear out the deduced argument. 872 for (auto &Pack : Packs) { 873 DeducedTemplateArgument &DeducedArg = Deduced[Pack.Index]; 874 if (!Pack.New.empty() || !DeducedArg.isNull()) { 875 while (Pack.New.size() < PackElements) 876 Pack.New.push_back(DeducedTemplateArgument()); 877 if (Pack.New.size() == PackElements) 878 Pack.New.push_back(DeducedArg); 879 else 880 Pack.New[PackElements] = DeducedArg; 881 DeducedArg = Pack.New.size() > PackElements + 1 882 ? Pack.New[PackElements + 1] 883 : DeducedTemplateArgument(); 884 } 885 } 886 ++PackElements; 887 } 888 889 /// Finish template argument deduction for a set of argument packs, 890 /// producing the argument packs and checking for consistency with prior 891 /// deductions. 892 Sema::TemplateDeductionResult finish() { 893 // Build argument packs for each of the parameter packs expanded by this 894 // pack expansion. 895 for (auto &Pack : Packs) { 896 // Put back the old value for this pack. 897 Deduced[Pack.Index] = Pack.Saved; 898 899 // Always make sure the size of this pack is correct, even if we didn't 900 // deduce any values for it. 901 // 902 // FIXME: This isn't required by the normative wording, but substitution 903 // and post-substitution checking will always fail if the arity of any 904 // pack is not equal to the number of elements we processed. (Either that 905 // or something else has gone *very* wrong.) We're permitted to skip any 906 // hard errors from those follow-on steps by the intent (but not the 907 // wording) of C++ [temp.inst]p8: 908 // 909 // If the function selected by overload resolution can be determined 910 // without instantiating a class template definition, it is unspecified 911 // whether that instantiation actually takes place 912 Pack.New.resize(PackElements); 913 914 // Build or find a new value for this pack. 915 DeducedTemplateArgument NewPack; 916 if (Pack.New.empty()) { 917 // If we deduced an empty argument pack, create it now. 918 NewPack = DeducedTemplateArgument(TemplateArgument::getEmptyPack()); 919 } else { 920 TemplateArgument *ArgumentPack = 921 new (S.Context) TemplateArgument[Pack.New.size()]; 922 std::copy(Pack.New.begin(), Pack.New.end(), ArgumentPack); 923 NewPack = DeducedTemplateArgument( 924 TemplateArgument(llvm::ArrayRef(ArgumentPack, Pack.New.size())), 925 // FIXME: This is wrong, it's possible that some pack elements are 926 // deduced from an array bound and others are not: 927 // template<typename ...T, T ...V> void g(const T (&...p)[V]); 928 // g({1, 2, 3}, {{}, {}}); 929 // ... should deduce T = {int, size_t (from array bound)}. 930 Pack.New[0].wasDeducedFromArrayBound()); 931 } 932 933 // Pick where we're going to put the merged pack. 934 DeducedTemplateArgument *Loc; 935 if (Pack.Outer) { 936 if (Pack.Outer->DeferredDeduction.isNull()) { 937 // Defer checking this pack until we have a complete pack to compare 938 // it against. 939 Pack.Outer->DeferredDeduction = NewPack; 940 continue; 941 } 942 Loc = &Pack.Outer->DeferredDeduction; 943 } else { 944 Loc = &Deduced[Pack.Index]; 945 } 946 947 // Check the new pack matches any previous value. 948 DeducedTemplateArgument OldPack = *Loc; 949 DeducedTemplateArgument Result = checkDeducedTemplateArguments( 950 S.Context, OldPack, NewPack, DeducePackIfNotAlreadyDeduced); 951 952 Info.AggregateDeductionCandidateHasMismatchedArity = 953 OldPack.getKind() == TemplateArgument::Pack && 954 NewPack.getKind() == TemplateArgument::Pack && 955 OldPack.pack_size() != NewPack.pack_size() && !Result.isNull(); 956 957 // If we deferred a deduction of this pack, check that one now too. 958 if (!Result.isNull() && !Pack.DeferredDeduction.isNull()) { 959 OldPack = Result; 960 NewPack = Pack.DeferredDeduction; 961 Result = checkDeducedTemplateArguments(S.Context, OldPack, NewPack); 962 } 963 964 NamedDecl *Param = TemplateParams->getParam(Pack.Index); 965 if (Result.isNull()) { 966 Info.Param = makeTemplateParameter(Param); 967 Info.FirstArg = OldPack; 968 Info.SecondArg = NewPack; 969 return Sema::TDK_Inconsistent; 970 } 971 972 // If we have a pre-expanded pack and we didn't deduce enough elements 973 // for it, fail deduction. 974 if (std::optional<unsigned> Expansions = getExpandedPackSize(Param)) { 975 if (*Expansions != PackElements) { 976 Info.Param = makeTemplateParameter(Param); 977 Info.FirstArg = Result; 978 return Sema::TDK_IncompletePack; 979 } 980 } 981 982 *Loc = Result; 983 } 984 985 return Sema::TDK_Success; 986 } 987 988 private: 989 Sema &S; 990 TemplateParameterList *TemplateParams; 991 SmallVectorImpl<DeducedTemplateArgument> &Deduced; 992 TemplateDeductionInfo &Info; 993 unsigned PackElements = 0; 994 bool IsPartiallyExpanded = false; 995 bool DeducePackIfNotAlreadyDeduced = false; 996 /// The number of expansions, if we have a fully-expanded pack in this scope. 997 std::optional<unsigned> FixedNumExpansions; 998 999 SmallVector<DeducedPack, 2> Packs; 1000 }; 1001 1002 } // namespace 1003 1004 /// Deduce the template arguments by comparing the list of parameter 1005 /// types to the list of argument types, as in the parameter-type-lists of 1006 /// function types (C++ [temp.deduct.type]p10). 1007 /// 1008 /// \param S The semantic analysis object within which we are deducing 1009 /// 1010 /// \param TemplateParams The template parameters that we are deducing 1011 /// 1012 /// \param Params The list of parameter types 1013 /// 1014 /// \param NumParams The number of types in \c Params 1015 /// 1016 /// \param Args The list of argument types 1017 /// 1018 /// \param NumArgs The number of types in \c Args 1019 /// 1020 /// \param Info information about the template argument deduction itself 1021 /// 1022 /// \param Deduced the deduced template arguments 1023 /// 1024 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe 1025 /// how template argument deduction is performed. 1026 /// 1027 /// \param PartialOrdering If true, we are performing template argument 1028 /// deduction for during partial ordering for a call 1029 /// (C++0x [temp.deduct.partial]). 1030 /// 1031 /// \returns the result of template argument deduction so far. Note that a 1032 /// "success" result means that template argument deduction has not yet failed, 1033 /// but it may still fail, later, for other reasons. 1034 static Sema::TemplateDeductionResult 1035 DeduceTemplateArguments(Sema &S, 1036 TemplateParameterList *TemplateParams, 1037 const QualType *Params, unsigned NumParams, 1038 const QualType *Args, unsigned NumArgs, 1039 TemplateDeductionInfo &Info, 1040 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 1041 unsigned TDF, 1042 bool PartialOrdering = false) { 1043 // C++0x [temp.deduct.type]p10: 1044 // Similarly, if P has a form that contains (T), then each parameter type 1045 // Pi of the respective parameter-type- list of P is compared with the 1046 // corresponding parameter type Ai of the corresponding parameter-type-list 1047 // of A. [...] 1048 unsigned ArgIdx = 0, ParamIdx = 0; 1049 for (; ParamIdx != NumParams; ++ParamIdx) { 1050 // Check argument types. 1051 const PackExpansionType *Expansion 1052 = dyn_cast<PackExpansionType>(Params[ParamIdx]); 1053 if (!Expansion) { 1054 // Simple case: compare the parameter and argument types at this point. 1055 1056 // Make sure we have an argument. 1057 if (ArgIdx >= NumArgs) 1058 return Sema::TDK_MiscellaneousDeductionFailure; 1059 1060 if (isa<PackExpansionType>(Args[ArgIdx])) { 1061 // C++0x [temp.deduct.type]p22: 1062 // If the original function parameter associated with A is a function 1063 // parameter pack and the function parameter associated with P is not 1064 // a function parameter pack, then template argument deduction fails. 1065 return Sema::TDK_MiscellaneousDeductionFailure; 1066 } 1067 1068 if (Sema::TemplateDeductionResult Result = 1069 DeduceTemplateArgumentsByTypeMatch( 1070 S, TemplateParams, Params[ParamIdx].getUnqualifiedType(), 1071 Args[ArgIdx].getUnqualifiedType(), Info, Deduced, TDF, 1072 PartialOrdering, 1073 /*DeducedFromArrayBound=*/false)) 1074 return Result; 1075 1076 ++ArgIdx; 1077 continue; 1078 } 1079 1080 // C++0x [temp.deduct.type]p10: 1081 // If the parameter-declaration corresponding to Pi is a function 1082 // parameter pack, then the type of its declarator- id is compared with 1083 // each remaining parameter type in the parameter-type-list of A. Each 1084 // comparison deduces template arguments for subsequent positions in the 1085 // template parameter packs expanded by the function parameter pack. 1086 1087 QualType Pattern = Expansion->getPattern(); 1088 PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern); 1089 1090 // A pack scope with fixed arity is not really a pack any more, so is not 1091 // a non-deduced context. 1092 if (ParamIdx + 1 == NumParams || PackScope.hasFixedArity()) { 1093 for (; ArgIdx < NumArgs && PackScope.hasNextElement(); ++ArgIdx) { 1094 // Deduce template arguments from the pattern. 1095 if (Sema::TemplateDeductionResult Result = 1096 DeduceTemplateArgumentsByTypeMatch( 1097 S, TemplateParams, Pattern.getUnqualifiedType(), 1098 Args[ArgIdx].getUnqualifiedType(), Info, Deduced, TDF, 1099 PartialOrdering, /*DeducedFromArrayBound=*/false)) 1100 return Result; 1101 1102 PackScope.nextPackElement(); 1103 } 1104 } else { 1105 // C++0x [temp.deduct.type]p5: 1106 // The non-deduced contexts are: 1107 // - A function parameter pack that does not occur at the end of the 1108 // parameter-declaration-clause. 1109 // 1110 // FIXME: There is no wording to say what we should do in this case. We 1111 // choose to resolve this by applying the same rule that is applied for a 1112 // function call: that is, deduce all contained packs to their 1113 // explicitly-specified values (or to <> if there is no such value). 1114 // 1115 // This is seemingly-arbitrarily different from the case of a template-id 1116 // with a non-trailing pack-expansion in its arguments, which renders the 1117 // entire template-argument-list a non-deduced context. 1118 1119 // If the parameter type contains an explicitly-specified pack that we 1120 // could not expand, skip the number of parameters notionally created 1121 // by the expansion. 1122 std::optional<unsigned> NumExpansions = Expansion->getNumExpansions(); 1123 if (NumExpansions && !PackScope.isPartiallyExpanded()) { 1124 for (unsigned I = 0; I != *NumExpansions && ArgIdx < NumArgs; 1125 ++I, ++ArgIdx) 1126 PackScope.nextPackElement(); 1127 } 1128 } 1129 1130 // Build argument packs for each of the parameter packs expanded by this 1131 // pack expansion. 1132 if (auto Result = PackScope.finish()) 1133 return Result; 1134 } 1135 1136 // DR692, DR1395 1137 // C++0x [temp.deduct.type]p10: 1138 // If the parameter-declaration corresponding to P_i ... 1139 // During partial ordering, if Ai was originally a function parameter pack: 1140 // - if P does not contain a function parameter type corresponding to Ai then 1141 // Ai is ignored; 1142 if (PartialOrdering && ArgIdx + 1 == NumArgs && 1143 isa<PackExpansionType>(Args[ArgIdx])) 1144 return Sema::TDK_Success; 1145 1146 // Make sure we don't have any extra arguments. 1147 if (ArgIdx < NumArgs) 1148 return Sema::TDK_MiscellaneousDeductionFailure; 1149 1150 return Sema::TDK_Success; 1151 } 1152 1153 /// Determine whether the parameter has qualifiers that the argument 1154 /// lacks. Put another way, determine whether there is no way to add 1155 /// a deduced set of qualifiers to the ParamType that would result in 1156 /// its qualifiers matching those of the ArgType. 1157 static bool hasInconsistentOrSupersetQualifiersOf(QualType ParamType, 1158 QualType ArgType) { 1159 Qualifiers ParamQs = ParamType.getQualifiers(); 1160 Qualifiers ArgQs = ArgType.getQualifiers(); 1161 1162 if (ParamQs == ArgQs) 1163 return false; 1164 1165 // Mismatched (but not missing) Objective-C GC attributes. 1166 if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() && 1167 ParamQs.hasObjCGCAttr()) 1168 return true; 1169 1170 // Mismatched (but not missing) address spaces. 1171 if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() && 1172 ParamQs.hasAddressSpace()) 1173 return true; 1174 1175 // Mismatched (but not missing) Objective-C lifetime qualifiers. 1176 if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() && 1177 ParamQs.hasObjCLifetime()) 1178 return true; 1179 1180 // CVR qualifiers inconsistent or a superset. 1181 return (ParamQs.getCVRQualifiers() & ~ArgQs.getCVRQualifiers()) != 0; 1182 } 1183 1184 /// Compare types for equality with respect to possibly compatible 1185 /// function types (noreturn adjustment, implicit calling conventions). If any 1186 /// of parameter and argument is not a function, just perform type comparison. 1187 /// 1188 /// \param P the template parameter type. 1189 /// 1190 /// \param A the argument type. 1191 bool Sema::isSameOrCompatibleFunctionType(QualType P, QualType A) { 1192 const FunctionType *PF = P->getAs<FunctionType>(), 1193 *AF = A->getAs<FunctionType>(); 1194 1195 // Just compare if not functions. 1196 if (!PF || !AF) 1197 return Context.hasSameType(P, A); 1198 1199 // Noreturn and noexcept adjustment. 1200 QualType AdjustedParam; 1201 if (IsFunctionConversion(P, A, AdjustedParam)) 1202 return Context.hasSameType(AdjustedParam, A); 1203 1204 // FIXME: Compatible calling conventions. 1205 1206 return Context.hasSameType(P, A); 1207 } 1208 1209 /// Get the index of the first template parameter that was originally from the 1210 /// innermost template-parameter-list. This is 0 except when we concatenate 1211 /// the template parameter lists of a class template and a constructor template 1212 /// when forming an implicit deduction guide. 1213 static unsigned getFirstInnerIndex(FunctionTemplateDecl *FTD) { 1214 auto *Guide = dyn_cast<CXXDeductionGuideDecl>(FTD->getTemplatedDecl()); 1215 if (!Guide || !Guide->isImplicit()) 1216 return 0; 1217 return Guide->getDeducedTemplate()->getTemplateParameters()->size(); 1218 } 1219 1220 /// Determine whether a type denotes a forwarding reference. 1221 static bool isForwardingReference(QualType Param, unsigned FirstInnerIndex) { 1222 // C++1z [temp.deduct.call]p3: 1223 // A forwarding reference is an rvalue reference to a cv-unqualified 1224 // template parameter that does not represent a template parameter of a 1225 // class template. 1226 if (auto *ParamRef = Param->getAs<RValueReferenceType>()) { 1227 if (ParamRef->getPointeeType().getQualifiers()) 1228 return false; 1229 auto *TypeParm = ParamRef->getPointeeType()->getAs<TemplateTypeParmType>(); 1230 return TypeParm && TypeParm->getIndex() >= FirstInnerIndex; 1231 } 1232 return false; 1233 } 1234 1235 static CXXRecordDecl *getCanonicalRD(QualType T) { 1236 return cast<CXXRecordDecl>( 1237 T->castAs<RecordType>()->getDecl()->getCanonicalDecl()); 1238 } 1239 1240 /// Attempt to deduce the template arguments by checking the base types 1241 /// according to (C++20 [temp.deduct.call] p4b3. 1242 /// 1243 /// \param S the semantic analysis object within which we are deducing. 1244 /// 1245 /// \param RD the top level record object we are deducing against. 1246 /// 1247 /// \param TemplateParams the template parameters that we are deducing. 1248 /// 1249 /// \param P the template specialization parameter type. 1250 /// 1251 /// \param Info information about the template argument deduction itself. 1252 /// 1253 /// \param Deduced the deduced template arguments. 1254 /// 1255 /// \returns the result of template argument deduction with the bases. "invalid" 1256 /// means no matches, "success" found a single item, and the 1257 /// "MiscellaneousDeductionFailure" result happens when the match is ambiguous. 1258 static Sema::TemplateDeductionResult 1259 DeduceTemplateBases(Sema &S, const CXXRecordDecl *RD, 1260 TemplateParameterList *TemplateParams, QualType P, 1261 TemplateDeductionInfo &Info, 1262 SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 1263 // C++14 [temp.deduct.call] p4b3: 1264 // If P is a class and P has the form simple-template-id, then the 1265 // transformed A can be a derived class of the deduced A. Likewise if 1266 // P is a pointer to a class of the form simple-template-id, the 1267 // transformed A can be a pointer to a derived class pointed to by the 1268 // deduced A. However, if there is a class C that is a (direct or 1269 // indirect) base class of D and derived (directly or indirectly) from a 1270 // class B and that would be a valid deduced A, the deduced A cannot be 1271 // B or pointer to B, respectively. 1272 // 1273 // These alternatives are considered only if type deduction would 1274 // otherwise fail. If they yield more than one possible deduced A, the 1275 // type deduction fails. 1276 1277 // Use a breadth-first search through the bases to collect the set of 1278 // successful matches. Visited contains the set of nodes we have already 1279 // visited, while ToVisit is our stack of records that we still need to 1280 // visit. Matches contains a list of matches that have yet to be 1281 // disqualified. 1282 llvm::SmallPtrSet<const CXXRecordDecl *, 8> Visited; 1283 SmallVector<QualType, 8> ToVisit; 1284 // We iterate over this later, so we have to use MapVector to ensure 1285 // determinism. 1286 llvm::MapVector<const CXXRecordDecl *, 1287 SmallVector<DeducedTemplateArgument, 8>> 1288 Matches; 1289 1290 auto AddBases = [&Visited, &ToVisit](const CXXRecordDecl *RD) { 1291 for (const auto &Base : RD->bases()) { 1292 QualType T = Base.getType(); 1293 assert(T->isRecordType() && "Base class that isn't a record?"); 1294 if (Visited.insert(::getCanonicalRD(T)).second) 1295 ToVisit.push_back(T); 1296 } 1297 }; 1298 1299 // Set up the loop by adding all the bases. 1300 AddBases(RD); 1301 1302 // Search each path of bases until we either run into a successful match 1303 // (where all bases of it are invalid), or we run out of bases. 1304 while (!ToVisit.empty()) { 1305 QualType NextT = ToVisit.pop_back_val(); 1306 1307 SmallVector<DeducedTemplateArgument, 8> DeducedCopy(Deduced.begin(), 1308 Deduced.end()); 1309 TemplateDeductionInfo BaseInfo(TemplateDeductionInfo::ForBase, Info); 1310 Sema::TemplateDeductionResult BaseResult = DeduceTemplateSpecArguments( 1311 S, TemplateParams, P, NextT, BaseInfo, DeducedCopy); 1312 1313 // If this was a successful deduction, add it to the list of matches, 1314 // otherwise we need to continue searching its bases. 1315 const CXXRecordDecl *RD = ::getCanonicalRD(NextT); 1316 if (BaseResult == Sema::TDK_Success) 1317 Matches.insert({RD, DeducedCopy}); 1318 else 1319 AddBases(RD); 1320 } 1321 1322 // At this point, 'Matches' contains a list of seemingly valid bases, however 1323 // in the event that we have more than 1 match, it is possible that the base 1324 // of one of the matches might be disqualified for being a base of another 1325 // valid match. We can count on cyclical instantiations being invalid to 1326 // simplify the disqualifications. That is, if A & B are both matches, and B 1327 // inherits from A (disqualifying A), we know that A cannot inherit from B. 1328 if (Matches.size() > 1) { 1329 Visited.clear(); 1330 for (const auto &Match : Matches) 1331 AddBases(Match.first); 1332 1333 // We can give up once we have a single item (or have run out of things to 1334 // search) since cyclical inheritance isn't valid. 1335 while (Matches.size() > 1 && !ToVisit.empty()) { 1336 const CXXRecordDecl *RD = ::getCanonicalRD(ToVisit.pop_back_val()); 1337 Matches.erase(RD); 1338 1339 // Always add all bases, since the inheritance tree can contain 1340 // disqualifications for multiple matches. 1341 AddBases(RD); 1342 } 1343 } 1344 1345 if (Matches.empty()) 1346 return Sema::TDK_Invalid; 1347 if (Matches.size() > 1) 1348 return Sema::TDK_MiscellaneousDeductionFailure; 1349 1350 std::swap(Matches.front().second, Deduced); 1351 return Sema::TDK_Success; 1352 } 1353 1354 /// Deduce the template arguments by comparing the parameter type and 1355 /// the argument type (C++ [temp.deduct.type]). 1356 /// 1357 /// \param S the semantic analysis object within which we are deducing 1358 /// 1359 /// \param TemplateParams the template parameters that we are deducing 1360 /// 1361 /// \param P the parameter type 1362 /// 1363 /// \param A the argument type 1364 /// 1365 /// \param Info information about the template argument deduction itself 1366 /// 1367 /// \param Deduced the deduced template arguments 1368 /// 1369 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe 1370 /// how template argument deduction is performed. 1371 /// 1372 /// \param PartialOrdering Whether we're performing template argument deduction 1373 /// in the context of partial ordering (C++0x [temp.deduct.partial]). 1374 /// 1375 /// \returns the result of template argument deduction so far. Note that a 1376 /// "success" result means that template argument deduction has not yet failed, 1377 /// but it may still fail, later, for other reasons. 1378 static Sema::TemplateDeductionResult DeduceTemplateArgumentsByTypeMatch( 1379 Sema &S, TemplateParameterList *TemplateParams, QualType P, QualType A, 1380 TemplateDeductionInfo &Info, 1381 SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF, 1382 bool PartialOrdering, bool DeducedFromArrayBound) { 1383 1384 // If the argument type is a pack expansion, look at its pattern. 1385 // This isn't explicitly called out 1386 if (const auto *AExp = dyn_cast<PackExpansionType>(A)) 1387 A = AExp->getPattern(); 1388 assert(!isa<PackExpansionType>(A.getCanonicalType())); 1389 1390 if (PartialOrdering) { 1391 // C++11 [temp.deduct.partial]p5: 1392 // Before the partial ordering is done, certain transformations are 1393 // performed on the types used for partial ordering: 1394 // - If P is a reference type, P is replaced by the type referred to. 1395 const ReferenceType *PRef = P->getAs<ReferenceType>(); 1396 if (PRef) 1397 P = PRef->getPointeeType(); 1398 1399 // - If A is a reference type, A is replaced by the type referred to. 1400 const ReferenceType *ARef = A->getAs<ReferenceType>(); 1401 if (ARef) 1402 A = A->getPointeeType(); 1403 1404 if (PRef && ARef && S.Context.hasSameUnqualifiedType(P, A)) { 1405 // C++11 [temp.deduct.partial]p9: 1406 // If, for a given type, deduction succeeds in both directions (i.e., 1407 // the types are identical after the transformations above) and both 1408 // P and A were reference types [...]: 1409 // - if [one type] was an lvalue reference and [the other type] was 1410 // not, [the other type] is not considered to be at least as 1411 // specialized as [the first type] 1412 // - if [one type] is more cv-qualified than [the other type], 1413 // [the other type] is not considered to be at least as specialized 1414 // as [the first type] 1415 // Objective-C ARC adds: 1416 // - [one type] has non-trivial lifetime, [the other type] has 1417 // __unsafe_unretained lifetime, and the types are otherwise 1418 // identical 1419 // 1420 // A is "considered to be at least as specialized" as P iff deduction 1421 // succeeds, so we model this as a deduction failure. Note that 1422 // [the first type] is P and [the other type] is A here; the standard 1423 // gets this backwards. 1424 Qualifiers PQuals = P.getQualifiers(), AQuals = A.getQualifiers(); 1425 if ((PRef->isLValueReferenceType() && !ARef->isLValueReferenceType()) || 1426 PQuals.isStrictSupersetOf(AQuals) || 1427 (PQuals.hasNonTrivialObjCLifetime() && 1428 AQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone && 1429 PQuals.withoutObjCLifetime() == AQuals.withoutObjCLifetime())) { 1430 Info.FirstArg = TemplateArgument(P); 1431 Info.SecondArg = TemplateArgument(A); 1432 return Sema::TDK_NonDeducedMismatch; 1433 } 1434 } 1435 Qualifiers DiscardedQuals; 1436 // C++11 [temp.deduct.partial]p7: 1437 // Remove any top-level cv-qualifiers: 1438 // - If P is a cv-qualified type, P is replaced by the cv-unqualified 1439 // version of P. 1440 P = S.Context.getUnqualifiedArrayType(P, DiscardedQuals); 1441 // - If A is a cv-qualified type, A is replaced by the cv-unqualified 1442 // version of A. 1443 A = S.Context.getUnqualifiedArrayType(A, DiscardedQuals); 1444 } else { 1445 // C++0x [temp.deduct.call]p4 bullet 1: 1446 // - If the original P is a reference type, the deduced A (i.e., the type 1447 // referred to by the reference) can be more cv-qualified than the 1448 // transformed A. 1449 if (TDF & TDF_ParamWithReferenceType) { 1450 Qualifiers Quals; 1451 QualType UnqualP = S.Context.getUnqualifiedArrayType(P, Quals); 1452 Quals.setCVRQualifiers(Quals.getCVRQualifiers() & A.getCVRQualifiers()); 1453 P = S.Context.getQualifiedType(UnqualP, Quals); 1454 } 1455 1456 if ((TDF & TDF_TopLevelParameterTypeList) && !P->isFunctionType()) { 1457 // C++0x [temp.deduct.type]p10: 1458 // If P and A are function types that originated from deduction when 1459 // taking the address of a function template (14.8.2.2) or when deducing 1460 // template arguments from a function declaration (14.8.2.6) and Pi and 1461 // Ai are parameters of the top-level parameter-type-list of P and A, 1462 // respectively, Pi is adjusted if it is a forwarding reference and Ai 1463 // is an lvalue reference, in 1464 // which case the type of Pi is changed to be the template parameter 1465 // type (i.e., T&& is changed to simply T). [ Note: As a result, when 1466 // Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be 1467 // deduced as X&. - end note ] 1468 TDF &= ~TDF_TopLevelParameterTypeList; 1469 if (isForwardingReference(P, /*FirstInnerIndex=*/0) && 1470 A->isLValueReferenceType()) 1471 P = P->getPointeeType(); 1472 } 1473 } 1474 1475 // C++ [temp.deduct.type]p9: 1476 // A template type argument T, a template template argument TT or a 1477 // template non-type argument i can be deduced if P and A have one of 1478 // the following forms: 1479 // 1480 // T 1481 // cv-list T 1482 if (const auto *TTP = P->getAs<TemplateTypeParmType>()) { 1483 // Just skip any attempts to deduce from a placeholder type or a parameter 1484 // at a different depth. 1485 if (A->isPlaceholderType() || Info.getDeducedDepth() != TTP->getDepth()) 1486 return Sema::TDK_Success; 1487 1488 unsigned Index = TTP->getIndex(); 1489 1490 // If the argument type is an array type, move the qualifiers up to the 1491 // top level, so they can be matched with the qualifiers on the parameter. 1492 if (A->isArrayType()) { 1493 Qualifiers Quals; 1494 A = S.Context.getUnqualifiedArrayType(A, Quals); 1495 if (Quals) 1496 A = S.Context.getQualifiedType(A, Quals); 1497 } 1498 1499 // The argument type can not be less qualified than the parameter 1500 // type. 1501 if (!(TDF & TDF_IgnoreQualifiers) && 1502 hasInconsistentOrSupersetQualifiersOf(P, A)) { 1503 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 1504 Info.FirstArg = TemplateArgument(P); 1505 Info.SecondArg = TemplateArgument(A); 1506 return Sema::TDK_Underqualified; 1507 } 1508 1509 // Do not match a function type with a cv-qualified type. 1510 // http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1584 1511 if (A->isFunctionType() && P.hasQualifiers()) 1512 return Sema::TDK_NonDeducedMismatch; 1513 1514 assert(TTP->getDepth() == Info.getDeducedDepth() && 1515 "saw template type parameter with wrong depth"); 1516 assert(A->getCanonicalTypeInternal() != S.Context.OverloadTy && 1517 "Unresolved overloaded function"); 1518 QualType DeducedType = A; 1519 1520 // Remove any qualifiers on the parameter from the deduced type. 1521 // We checked the qualifiers for consistency above. 1522 Qualifiers DeducedQs = DeducedType.getQualifiers(); 1523 Qualifiers ParamQs = P.getQualifiers(); 1524 DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers()); 1525 if (ParamQs.hasObjCGCAttr()) 1526 DeducedQs.removeObjCGCAttr(); 1527 if (ParamQs.hasAddressSpace()) 1528 DeducedQs.removeAddressSpace(); 1529 if (ParamQs.hasObjCLifetime()) 1530 DeducedQs.removeObjCLifetime(); 1531 1532 // Objective-C ARC: 1533 // If template deduction would produce a lifetime qualifier on a type 1534 // that is not a lifetime type, template argument deduction fails. 1535 if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() && 1536 !DeducedType->isDependentType()) { 1537 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 1538 Info.FirstArg = TemplateArgument(P); 1539 Info.SecondArg = TemplateArgument(A); 1540 return Sema::TDK_Underqualified; 1541 } 1542 1543 // Objective-C ARC: 1544 // If template deduction would produce an argument type with lifetime type 1545 // but no lifetime qualifier, the __strong lifetime qualifier is inferred. 1546 if (S.getLangOpts().ObjCAutoRefCount && DeducedType->isObjCLifetimeType() && 1547 !DeducedQs.hasObjCLifetime()) 1548 DeducedQs.setObjCLifetime(Qualifiers::OCL_Strong); 1549 1550 DeducedType = 1551 S.Context.getQualifiedType(DeducedType.getUnqualifiedType(), DeducedQs); 1552 1553 DeducedTemplateArgument NewDeduced(DeducedType, DeducedFromArrayBound); 1554 DeducedTemplateArgument Result = 1555 checkDeducedTemplateArguments(S.Context, Deduced[Index], NewDeduced); 1556 if (Result.isNull()) { 1557 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 1558 Info.FirstArg = Deduced[Index]; 1559 Info.SecondArg = NewDeduced; 1560 return Sema::TDK_Inconsistent; 1561 } 1562 1563 Deduced[Index] = Result; 1564 return Sema::TDK_Success; 1565 } 1566 1567 // Set up the template argument deduction information for a failure. 1568 Info.FirstArg = TemplateArgument(P); 1569 Info.SecondArg = TemplateArgument(A); 1570 1571 // If the parameter is an already-substituted template parameter 1572 // pack, do nothing: we don't know which of its arguments to look 1573 // at, so we have to wait until all of the parameter packs in this 1574 // expansion have arguments. 1575 if (P->getAs<SubstTemplateTypeParmPackType>()) 1576 return Sema::TDK_Success; 1577 1578 // Check the cv-qualifiers on the parameter and argument types. 1579 if (!(TDF & TDF_IgnoreQualifiers)) { 1580 if (TDF & TDF_ParamWithReferenceType) { 1581 if (hasInconsistentOrSupersetQualifiersOf(P, A)) 1582 return Sema::TDK_NonDeducedMismatch; 1583 } else if (TDF & TDF_ArgWithReferenceType) { 1584 // C++ [temp.deduct.conv]p4: 1585 // If the original A is a reference type, A can be more cv-qualified 1586 // than the deduced A 1587 if (!A.getQualifiers().compatiblyIncludes(P.getQualifiers())) 1588 return Sema::TDK_NonDeducedMismatch; 1589 1590 // Strip out all extra qualifiers from the argument to figure out the 1591 // type we're converting to, prior to the qualification conversion. 1592 Qualifiers Quals; 1593 A = S.Context.getUnqualifiedArrayType(A, Quals); 1594 A = S.Context.getQualifiedType(A, P.getQualifiers()); 1595 } else if (!IsPossiblyOpaquelyQualifiedType(P)) { 1596 if (P.getCVRQualifiers() != A.getCVRQualifiers()) 1597 return Sema::TDK_NonDeducedMismatch; 1598 } 1599 } 1600 1601 // If the parameter type is not dependent, there is nothing to deduce. 1602 if (!P->isDependentType()) { 1603 if (TDF & TDF_SkipNonDependent) 1604 return Sema::TDK_Success; 1605 if ((TDF & TDF_IgnoreQualifiers) ? S.Context.hasSameUnqualifiedType(P, A) 1606 : S.Context.hasSameType(P, A)) 1607 return Sema::TDK_Success; 1608 if (TDF & TDF_AllowCompatibleFunctionType && 1609 S.isSameOrCompatibleFunctionType(P, A)) 1610 return Sema::TDK_Success; 1611 if (!(TDF & TDF_IgnoreQualifiers)) 1612 return Sema::TDK_NonDeducedMismatch; 1613 // Otherwise, when ignoring qualifiers, the types not having the same 1614 // unqualified type does not mean they do not match, so in this case we 1615 // must keep going and analyze with a non-dependent parameter type. 1616 } 1617 1618 switch (P.getCanonicalType()->getTypeClass()) { 1619 // Non-canonical types cannot appear here. 1620 #define NON_CANONICAL_TYPE(Class, Base) \ 1621 case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class); 1622 #define TYPE(Class, Base) 1623 #include "clang/AST/TypeNodes.inc" 1624 1625 case Type::TemplateTypeParm: 1626 case Type::SubstTemplateTypeParmPack: 1627 llvm_unreachable("Type nodes handled above"); 1628 1629 case Type::Auto: 1630 // C++23 [temp.deduct.funcaddr]/3: 1631 // A placeholder type in the return type of a function template is a 1632 // non-deduced context. 1633 // There's no corresponding wording for [temp.deduct.decl], but we treat 1634 // it the same to match other compilers. 1635 if (P->isDependentType()) 1636 return Sema::TDK_Success; 1637 [[fallthrough]]; 1638 case Type::Builtin: 1639 case Type::VariableArray: 1640 case Type::Vector: 1641 case Type::FunctionNoProto: 1642 case Type::Record: 1643 case Type::Enum: 1644 case Type::ObjCObject: 1645 case Type::ObjCInterface: 1646 case Type::ObjCObjectPointer: 1647 case Type::BitInt: 1648 return (TDF & TDF_SkipNonDependent) || 1649 ((TDF & TDF_IgnoreQualifiers) 1650 ? S.Context.hasSameUnqualifiedType(P, A) 1651 : S.Context.hasSameType(P, A)) 1652 ? Sema::TDK_Success 1653 : Sema::TDK_NonDeducedMismatch; 1654 1655 // _Complex T [placeholder extension] 1656 case Type::Complex: { 1657 const auto *CP = P->castAs<ComplexType>(), *CA = A->getAs<ComplexType>(); 1658 if (!CA) 1659 return Sema::TDK_NonDeducedMismatch; 1660 return DeduceTemplateArgumentsByTypeMatch( 1661 S, TemplateParams, CP->getElementType(), CA->getElementType(), Info, 1662 Deduced, TDF); 1663 } 1664 1665 // _Atomic T [extension] 1666 case Type::Atomic: { 1667 const auto *PA = P->castAs<AtomicType>(), *AA = A->getAs<AtomicType>(); 1668 if (!AA) 1669 return Sema::TDK_NonDeducedMismatch; 1670 return DeduceTemplateArgumentsByTypeMatch( 1671 S, TemplateParams, PA->getValueType(), AA->getValueType(), Info, 1672 Deduced, TDF); 1673 } 1674 1675 // T * 1676 case Type::Pointer: { 1677 QualType PointeeType; 1678 if (const auto *PA = A->getAs<PointerType>()) { 1679 PointeeType = PA->getPointeeType(); 1680 } else if (const auto *PA = A->getAs<ObjCObjectPointerType>()) { 1681 PointeeType = PA->getPointeeType(); 1682 } else { 1683 return Sema::TDK_NonDeducedMismatch; 1684 } 1685 return DeduceTemplateArgumentsByTypeMatch( 1686 S, TemplateParams, P->castAs<PointerType>()->getPointeeType(), 1687 PointeeType, Info, Deduced, 1688 TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass)); 1689 } 1690 1691 // T & 1692 case Type::LValueReference: { 1693 const auto *RP = P->castAs<LValueReferenceType>(), 1694 *RA = A->getAs<LValueReferenceType>(); 1695 if (!RA) 1696 return Sema::TDK_NonDeducedMismatch; 1697 1698 return DeduceTemplateArgumentsByTypeMatch( 1699 S, TemplateParams, RP->getPointeeType(), RA->getPointeeType(), Info, 1700 Deduced, 0); 1701 } 1702 1703 // T && [C++0x] 1704 case Type::RValueReference: { 1705 const auto *RP = P->castAs<RValueReferenceType>(), 1706 *RA = A->getAs<RValueReferenceType>(); 1707 if (!RA) 1708 return Sema::TDK_NonDeducedMismatch; 1709 1710 return DeduceTemplateArgumentsByTypeMatch( 1711 S, TemplateParams, RP->getPointeeType(), RA->getPointeeType(), Info, 1712 Deduced, 0); 1713 } 1714 1715 // T [] (implied, but not stated explicitly) 1716 case Type::IncompleteArray: { 1717 const auto *IAA = S.Context.getAsIncompleteArrayType(A); 1718 if (!IAA) 1719 return Sema::TDK_NonDeducedMismatch; 1720 1721 const auto *IAP = S.Context.getAsIncompleteArrayType(P); 1722 assert(IAP && "Template parameter not of incomplete array type"); 1723 1724 return DeduceTemplateArgumentsByTypeMatch( 1725 S, TemplateParams, IAP->getElementType(), IAA->getElementType(), Info, 1726 Deduced, TDF & TDF_IgnoreQualifiers); 1727 } 1728 1729 // T [integer-constant] 1730 case Type::ConstantArray: { 1731 const auto *CAA = S.Context.getAsConstantArrayType(A), 1732 *CAP = S.Context.getAsConstantArrayType(P); 1733 assert(CAP); 1734 if (!CAA || CAA->getSize() != CAP->getSize()) 1735 return Sema::TDK_NonDeducedMismatch; 1736 1737 return DeduceTemplateArgumentsByTypeMatch( 1738 S, TemplateParams, CAP->getElementType(), CAA->getElementType(), Info, 1739 Deduced, TDF & TDF_IgnoreQualifiers); 1740 } 1741 1742 // type [i] 1743 case Type::DependentSizedArray: { 1744 const auto *AA = S.Context.getAsArrayType(A); 1745 if (!AA) 1746 return Sema::TDK_NonDeducedMismatch; 1747 1748 // Check the element type of the arrays 1749 const auto *DAP = S.Context.getAsDependentSizedArrayType(P); 1750 assert(DAP); 1751 if (auto Result = DeduceTemplateArgumentsByTypeMatch( 1752 S, TemplateParams, DAP->getElementType(), AA->getElementType(), 1753 Info, Deduced, TDF & TDF_IgnoreQualifiers)) 1754 return Result; 1755 1756 // Determine the array bound is something we can deduce. 1757 const NonTypeTemplateParmDecl *NTTP = 1758 getDeducedParameterFromExpr(Info, DAP->getSizeExpr()); 1759 if (!NTTP) 1760 return Sema::TDK_Success; 1761 1762 // We can perform template argument deduction for the given non-type 1763 // template parameter. 1764 assert(NTTP->getDepth() == Info.getDeducedDepth() && 1765 "saw non-type template parameter with wrong depth"); 1766 if (const auto *CAA = dyn_cast<ConstantArrayType>(AA)) { 1767 llvm::APSInt Size(CAA->getSize()); 1768 return DeduceNonTypeTemplateArgument( 1769 S, TemplateParams, NTTP, Size, S.Context.getSizeType(), 1770 /*ArrayBound=*/true, Info, Deduced); 1771 } 1772 if (const auto *DAA = dyn_cast<DependentSizedArrayType>(AA)) 1773 if (DAA->getSizeExpr()) 1774 return DeduceNonTypeTemplateArgument( 1775 S, TemplateParams, NTTP, DAA->getSizeExpr(), Info, Deduced); 1776 1777 // Incomplete type does not match a dependently-sized array type 1778 return Sema::TDK_NonDeducedMismatch; 1779 } 1780 1781 // type(*)(T) 1782 // T(*)() 1783 // T(*)(T) 1784 case Type::FunctionProto: { 1785 const auto *FPP = P->castAs<FunctionProtoType>(), 1786 *FPA = A->getAs<FunctionProtoType>(); 1787 if (!FPA) 1788 return Sema::TDK_NonDeducedMismatch; 1789 1790 if (FPP->getMethodQuals() != FPA->getMethodQuals() || 1791 FPP->getRefQualifier() != FPA->getRefQualifier() || 1792 FPP->isVariadic() != FPA->isVariadic()) 1793 return Sema::TDK_NonDeducedMismatch; 1794 1795 // Check return types. 1796 if (auto Result = DeduceTemplateArgumentsByTypeMatch( 1797 S, TemplateParams, FPP->getReturnType(), FPA->getReturnType(), 1798 Info, Deduced, 0, 1799 /*PartialOrdering=*/false, 1800 /*DeducedFromArrayBound=*/false)) 1801 return Result; 1802 1803 // Check parameter types. 1804 if (auto Result = DeduceTemplateArguments( 1805 S, TemplateParams, FPP->param_type_begin(), FPP->getNumParams(), 1806 FPA->param_type_begin(), FPA->getNumParams(), Info, Deduced, 1807 TDF & TDF_TopLevelParameterTypeList, PartialOrdering)) 1808 return Result; 1809 1810 if (TDF & TDF_AllowCompatibleFunctionType) 1811 return Sema::TDK_Success; 1812 1813 // FIXME: Per core-2016/10/1019 (no corresponding core issue yet), permit 1814 // deducing through the noexcept-specifier if it's part of the canonical 1815 // type. libstdc++ relies on this. 1816 Expr *NoexceptExpr = FPP->getNoexceptExpr(); 1817 if (const NonTypeTemplateParmDecl *NTTP = 1818 NoexceptExpr ? getDeducedParameterFromExpr(Info, NoexceptExpr) 1819 : nullptr) { 1820 assert(NTTP->getDepth() == Info.getDeducedDepth() && 1821 "saw non-type template parameter with wrong depth"); 1822 1823 llvm::APSInt Noexcept(1); 1824 switch (FPA->canThrow()) { 1825 case CT_Cannot: 1826 Noexcept = 1; 1827 [[fallthrough]]; 1828 1829 case CT_Can: 1830 // We give E in noexcept(E) the "deduced from array bound" treatment. 1831 // FIXME: Should we? 1832 return DeduceNonTypeTemplateArgument( 1833 S, TemplateParams, NTTP, Noexcept, S.Context.BoolTy, 1834 /*DeducedFromArrayBound=*/true, Info, Deduced); 1835 1836 case CT_Dependent: 1837 if (Expr *ArgNoexceptExpr = FPA->getNoexceptExpr()) 1838 return DeduceNonTypeTemplateArgument( 1839 S, TemplateParams, NTTP, ArgNoexceptExpr, Info, Deduced); 1840 // Can't deduce anything from throw(T...). 1841 break; 1842 } 1843 } 1844 // FIXME: Detect non-deduced exception specification mismatches? 1845 // 1846 // Careful about [temp.deduct.call] and [temp.deduct.conv], which allow 1847 // top-level differences in noexcept-specifications. 1848 1849 return Sema::TDK_Success; 1850 } 1851 1852 case Type::InjectedClassName: 1853 // Treat a template's injected-class-name as if the template 1854 // specialization type had been used. 1855 1856 // template-name<T> (where template-name refers to a class template) 1857 // template-name<i> 1858 // TT<T> 1859 // TT<i> 1860 // TT<> 1861 case Type::TemplateSpecialization: { 1862 // When Arg cannot be a derived class, we can just try to deduce template 1863 // arguments from the template-id. 1864 if (!(TDF & TDF_DerivedClass) || !A->isRecordType()) 1865 return DeduceTemplateSpecArguments(S, TemplateParams, P, A, Info, 1866 Deduced); 1867 1868 SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(), 1869 Deduced.end()); 1870 1871 auto Result = 1872 DeduceTemplateSpecArguments(S, TemplateParams, P, A, Info, Deduced); 1873 if (Result == Sema::TDK_Success) 1874 return Result; 1875 1876 // We cannot inspect base classes as part of deduction when the type 1877 // is incomplete, so either instantiate any templates necessary to 1878 // complete the type, or skip over it if it cannot be completed. 1879 if (!S.isCompleteType(Info.getLocation(), A)) 1880 return Result; 1881 1882 // Reset the incorrectly deduced argument from above. 1883 Deduced = DeducedOrig; 1884 1885 // Check bases according to C++14 [temp.deduct.call] p4b3: 1886 auto BaseResult = DeduceTemplateBases(S, getCanonicalRD(A), 1887 TemplateParams, P, Info, Deduced); 1888 return BaseResult != Sema::TDK_Invalid ? BaseResult : Result; 1889 } 1890 1891 // T type::* 1892 // T T::* 1893 // T (type::*)() 1894 // type (T::*)() 1895 // type (type::*)(T) 1896 // type (T::*)(T) 1897 // T (type::*)(T) 1898 // T (T::*)() 1899 // T (T::*)(T) 1900 case Type::MemberPointer: { 1901 const auto *MPP = P->castAs<MemberPointerType>(), 1902 *MPA = A->getAs<MemberPointerType>(); 1903 if (!MPA) 1904 return Sema::TDK_NonDeducedMismatch; 1905 1906 QualType PPT = MPP->getPointeeType(); 1907 if (PPT->isFunctionType()) 1908 S.adjustMemberFunctionCC(PPT, /*IsStatic=*/true, 1909 /*IsCtorOrDtor=*/false, Info.getLocation()); 1910 QualType APT = MPA->getPointeeType(); 1911 if (APT->isFunctionType()) 1912 S.adjustMemberFunctionCC(APT, /*IsStatic=*/true, 1913 /*IsCtorOrDtor=*/false, Info.getLocation()); 1914 1915 unsigned SubTDF = TDF & TDF_IgnoreQualifiers; 1916 if (auto Result = DeduceTemplateArgumentsByTypeMatch( 1917 S, TemplateParams, PPT, APT, Info, Deduced, SubTDF)) 1918 return Result; 1919 return DeduceTemplateArgumentsByTypeMatch( 1920 S, TemplateParams, QualType(MPP->getClass(), 0), 1921 QualType(MPA->getClass(), 0), Info, Deduced, SubTDF); 1922 } 1923 1924 // (clang extension) 1925 // 1926 // type(^)(T) 1927 // T(^)() 1928 // T(^)(T) 1929 case Type::BlockPointer: { 1930 const auto *BPP = P->castAs<BlockPointerType>(), 1931 *BPA = A->getAs<BlockPointerType>(); 1932 if (!BPA) 1933 return Sema::TDK_NonDeducedMismatch; 1934 return DeduceTemplateArgumentsByTypeMatch( 1935 S, TemplateParams, BPP->getPointeeType(), BPA->getPointeeType(), Info, 1936 Deduced, 0); 1937 } 1938 1939 // (clang extension) 1940 // 1941 // T __attribute__(((ext_vector_type(<integral constant>)))) 1942 case Type::ExtVector: { 1943 const auto *VP = P->castAs<ExtVectorType>(); 1944 QualType ElementType; 1945 if (const auto *VA = A->getAs<ExtVectorType>()) { 1946 // Make sure that the vectors have the same number of elements. 1947 if (VP->getNumElements() != VA->getNumElements()) 1948 return Sema::TDK_NonDeducedMismatch; 1949 ElementType = VA->getElementType(); 1950 } else if (const auto *VA = A->getAs<DependentSizedExtVectorType>()) { 1951 // We can't check the number of elements, since the argument has a 1952 // dependent number of elements. This can only occur during partial 1953 // ordering. 1954 ElementType = VA->getElementType(); 1955 } else { 1956 return Sema::TDK_NonDeducedMismatch; 1957 } 1958 // Perform deduction on the element types. 1959 return DeduceTemplateArgumentsByTypeMatch( 1960 S, TemplateParams, VP->getElementType(), ElementType, Info, Deduced, 1961 TDF); 1962 } 1963 1964 case Type::DependentVector: { 1965 const auto *VP = P->castAs<DependentVectorType>(); 1966 1967 if (const auto *VA = A->getAs<VectorType>()) { 1968 // Perform deduction on the element types. 1969 if (auto Result = DeduceTemplateArgumentsByTypeMatch( 1970 S, TemplateParams, VP->getElementType(), VA->getElementType(), 1971 Info, Deduced, TDF)) 1972 return Result; 1973 1974 // Perform deduction on the vector size, if we can. 1975 const NonTypeTemplateParmDecl *NTTP = 1976 getDeducedParameterFromExpr(Info, VP->getSizeExpr()); 1977 if (!NTTP) 1978 return Sema::TDK_Success; 1979 1980 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false); 1981 ArgSize = VA->getNumElements(); 1982 // Note that we use the "array bound" rules here; just like in that 1983 // case, we don't have any particular type for the vector size, but 1984 // we can provide one if necessary. 1985 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize, 1986 S.Context.UnsignedIntTy, true, 1987 Info, Deduced); 1988 } 1989 1990 if (const auto *VA = A->getAs<DependentVectorType>()) { 1991 // Perform deduction on the element types. 1992 if (auto Result = DeduceTemplateArgumentsByTypeMatch( 1993 S, TemplateParams, VP->getElementType(), VA->getElementType(), 1994 Info, Deduced, TDF)) 1995 return Result; 1996 1997 // Perform deduction on the vector size, if we can. 1998 const NonTypeTemplateParmDecl *NTTP = 1999 getDeducedParameterFromExpr(Info, VP->getSizeExpr()); 2000 if (!NTTP) 2001 return Sema::TDK_Success; 2002 2003 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, 2004 VA->getSizeExpr(), Info, Deduced); 2005 } 2006 2007 return Sema::TDK_NonDeducedMismatch; 2008 } 2009 2010 // (clang extension) 2011 // 2012 // T __attribute__(((ext_vector_type(N)))) 2013 case Type::DependentSizedExtVector: { 2014 const auto *VP = P->castAs<DependentSizedExtVectorType>(); 2015 2016 if (const auto *VA = A->getAs<ExtVectorType>()) { 2017 // Perform deduction on the element types. 2018 if (auto Result = DeduceTemplateArgumentsByTypeMatch( 2019 S, TemplateParams, VP->getElementType(), VA->getElementType(), 2020 Info, Deduced, TDF)) 2021 return Result; 2022 2023 // Perform deduction on the vector size, if we can. 2024 const NonTypeTemplateParmDecl *NTTP = 2025 getDeducedParameterFromExpr(Info, VP->getSizeExpr()); 2026 if (!NTTP) 2027 return Sema::TDK_Success; 2028 2029 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false); 2030 ArgSize = VA->getNumElements(); 2031 // Note that we use the "array bound" rules here; just like in that 2032 // case, we don't have any particular type for the vector size, but 2033 // we can provide one if necessary. 2034 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize, 2035 S.Context.IntTy, true, Info, 2036 Deduced); 2037 } 2038 2039 if (const auto *VA = A->getAs<DependentSizedExtVectorType>()) { 2040 // Perform deduction on the element types. 2041 if (auto Result = DeduceTemplateArgumentsByTypeMatch( 2042 S, TemplateParams, VP->getElementType(), VA->getElementType(), 2043 Info, Deduced, TDF)) 2044 return Result; 2045 2046 // Perform deduction on the vector size, if we can. 2047 const NonTypeTemplateParmDecl *NTTP = 2048 getDeducedParameterFromExpr(Info, VP->getSizeExpr()); 2049 if (!NTTP) 2050 return Sema::TDK_Success; 2051 2052 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, 2053 VA->getSizeExpr(), Info, Deduced); 2054 } 2055 2056 return Sema::TDK_NonDeducedMismatch; 2057 } 2058 2059 // (clang extension) 2060 // 2061 // T __attribute__((matrix_type(<integral constant>, 2062 // <integral constant>))) 2063 case Type::ConstantMatrix: { 2064 const auto *MP = P->castAs<ConstantMatrixType>(), 2065 *MA = A->getAs<ConstantMatrixType>(); 2066 if (!MA) 2067 return Sema::TDK_NonDeducedMismatch; 2068 2069 // Check that the dimensions are the same 2070 if (MP->getNumRows() != MA->getNumRows() || 2071 MP->getNumColumns() != MA->getNumColumns()) { 2072 return Sema::TDK_NonDeducedMismatch; 2073 } 2074 // Perform deduction on element types. 2075 return DeduceTemplateArgumentsByTypeMatch( 2076 S, TemplateParams, MP->getElementType(), MA->getElementType(), Info, 2077 Deduced, TDF); 2078 } 2079 2080 case Type::DependentSizedMatrix: { 2081 const auto *MP = P->castAs<DependentSizedMatrixType>(); 2082 const auto *MA = A->getAs<MatrixType>(); 2083 if (!MA) 2084 return Sema::TDK_NonDeducedMismatch; 2085 2086 // Check the element type of the matrixes. 2087 if (auto Result = DeduceTemplateArgumentsByTypeMatch( 2088 S, TemplateParams, MP->getElementType(), MA->getElementType(), 2089 Info, Deduced, TDF)) 2090 return Result; 2091 2092 // Try to deduce a matrix dimension. 2093 auto DeduceMatrixArg = 2094 [&S, &Info, &Deduced, &TemplateParams]( 2095 Expr *ParamExpr, const MatrixType *A, 2096 unsigned (ConstantMatrixType::*GetArgDimension)() const, 2097 Expr *(DependentSizedMatrixType::*GetArgDimensionExpr)() const) { 2098 const auto *ACM = dyn_cast<ConstantMatrixType>(A); 2099 const auto *ADM = dyn_cast<DependentSizedMatrixType>(A); 2100 if (!ParamExpr->isValueDependent()) { 2101 std::optional<llvm::APSInt> ParamConst = 2102 ParamExpr->getIntegerConstantExpr(S.Context); 2103 if (!ParamConst) 2104 return Sema::TDK_NonDeducedMismatch; 2105 2106 if (ACM) { 2107 if ((ACM->*GetArgDimension)() == *ParamConst) 2108 return Sema::TDK_Success; 2109 return Sema::TDK_NonDeducedMismatch; 2110 } 2111 2112 Expr *ArgExpr = (ADM->*GetArgDimensionExpr)(); 2113 if (std::optional<llvm::APSInt> ArgConst = 2114 ArgExpr->getIntegerConstantExpr(S.Context)) 2115 if (*ArgConst == *ParamConst) 2116 return Sema::TDK_Success; 2117 return Sema::TDK_NonDeducedMismatch; 2118 } 2119 2120 const NonTypeTemplateParmDecl *NTTP = 2121 getDeducedParameterFromExpr(Info, ParamExpr); 2122 if (!NTTP) 2123 return Sema::TDK_Success; 2124 2125 if (ACM) { 2126 llvm::APSInt ArgConst( 2127 S.Context.getTypeSize(S.Context.getSizeType())); 2128 ArgConst = (ACM->*GetArgDimension)(); 2129 return DeduceNonTypeTemplateArgument( 2130 S, TemplateParams, NTTP, ArgConst, S.Context.getSizeType(), 2131 /*ArrayBound=*/true, Info, Deduced); 2132 } 2133 2134 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, 2135 (ADM->*GetArgDimensionExpr)(), 2136 Info, Deduced); 2137 }; 2138 2139 if (auto Result = DeduceMatrixArg(MP->getRowExpr(), MA, 2140 &ConstantMatrixType::getNumRows, 2141 &DependentSizedMatrixType::getRowExpr)) 2142 return Result; 2143 2144 return DeduceMatrixArg(MP->getColumnExpr(), MA, 2145 &ConstantMatrixType::getNumColumns, 2146 &DependentSizedMatrixType::getColumnExpr); 2147 } 2148 2149 // (clang extension) 2150 // 2151 // T __attribute__(((address_space(N)))) 2152 case Type::DependentAddressSpace: { 2153 const auto *ASP = P->castAs<DependentAddressSpaceType>(); 2154 2155 if (const auto *ASA = A->getAs<DependentAddressSpaceType>()) { 2156 // Perform deduction on the pointer type. 2157 if (auto Result = DeduceTemplateArgumentsByTypeMatch( 2158 S, TemplateParams, ASP->getPointeeType(), ASA->getPointeeType(), 2159 Info, Deduced, TDF)) 2160 return Result; 2161 2162 // Perform deduction on the address space, if we can. 2163 const NonTypeTemplateParmDecl *NTTP = 2164 getDeducedParameterFromExpr(Info, ASP->getAddrSpaceExpr()); 2165 if (!NTTP) 2166 return Sema::TDK_Success; 2167 2168 return DeduceNonTypeTemplateArgument( 2169 S, TemplateParams, NTTP, ASA->getAddrSpaceExpr(), Info, Deduced); 2170 } 2171 2172 if (isTargetAddressSpace(A.getAddressSpace())) { 2173 llvm::APSInt ArgAddressSpace(S.Context.getTypeSize(S.Context.IntTy), 2174 false); 2175 ArgAddressSpace = toTargetAddressSpace(A.getAddressSpace()); 2176 2177 // Perform deduction on the pointer types. 2178 if (auto Result = DeduceTemplateArgumentsByTypeMatch( 2179 S, TemplateParams, ASP->getPointeeType(), 2180 S.Context.removeAddrSpaceQualType(A), Info, Deduced, TDF)) 2181 return Result; 2182 2183 // Perform deduction on the address space, if we can. 2184 const NonTypeTemplateParmDecl *NTTP = 2185 getDeducedParameterFromExpr(Info, ASP->getAddrSpaceExpr()); 2186 if (!NTTP) 2187 return Sema::TDK_Success; 2188 2189 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, 2190 ArgAddressSpace, S.Context.IntTy, 2191 true, Info, Deduced); 2192 } 2193 2194 return Sema::TDK_NonDeducedMismatch; 2195 } 2196 case Type::DependentBitInt: { 2197 const auto *IP = P->castAs<DependentBitIntType>(); 2198 2199 if (const auto *IA = A->getAs<BitIntType>()) { 2200 if (IP->isUnsigned() != IA->isUnsigned()) 2201 return Sema::TDK_NonDeducedMismatch; 2202 2203 const NonTypeTemplateParmDecl *NTTP = 2204 getDeducedParameterFromExpr(Info, IP->getNumBitsExpr()); 2205 if (!NTTP) 2206 return Sema::TDK_Success; 2207 2208 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false); 2209 ArgSize = IA->getNumBits(); 2210 2211 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize, 2212 S.Context.IntTy, true, Info, 2213 Deduced); 2214 } 2215 2216 if (const auto *IA = A->getAs<DependentBitIntType>()) { 2217 if (IP->isUnsigned() != IA->isUnsigned()) 2218 return Sema::TDK_NonDeducedMismatch; 2219 return Sema::TDK_Success; 2220 } 2221 2222 return Sema::TDK_NonDeducedMismatch; 2223 } 2224 2225 case Type::TypeOfExpr: 2226 case Type::TypeOf: 2227 case Type::DependentName: 2228 case Type::UnresolvedUsing: 2229 case Type::Decltype: 2230 case Type::UnaryTransform: 2231 case Type::DeducedTemplateSpecialization: 2232 case Type::DependentTemplateSpecialization: 2233 case Type::PackExpansion: 2234 case Type::Pipe: 2235 // No template argument deduction for these types 2236 return Sema::TDK_Success; 2237 } 2238 2239 llvm_unreachable("Invalid Type Class!"); 2240 } 2241 2242 static Sema::TemplateDeductionResult 2243 DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams, 2244 const TemplateArgument &P, TemplateArgument A, 2245 TemplateDeductionInfo &Info, 2246 SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 2247 // If the template argument is a pack expansion, perform template argument 2248 // deduction against the pattern of that expansion. This only occurs during 2249 // partial ordering. 2250 if (A.isPackExpansion()) 2251 A = A.getPackExpansionPattern(); 2252 2253 switch (P.getKind()) { 2254 case TemplateArgument::Null: 2255 llvm_unreachable("Null template argument in parameter list"); 2256 2257 case TemplateArgument::Type: 2258 if (A.getKind() == TemplateArgument::Type) 2259 return DeduceTemplateArgumentsByTypeMatch( 2260 S, TemplateParams, P.getAsType(), A.getAsType(), Info, Deduced, 0); 2261 Info.FirstArg = P; 2262 Info.SecondArg = A; 2263 return Sema::TDK_NonDeducedMismatch; 2264 2265 case TemplateArgument::Template: 2266 if (A.getKind() == TemplateArgument::Template) 2267 return DeduceTemplateArguments(S, TemplateParams, P.getAsTemplate(), 2268 A.getAsTemplate(), Info, Deduced); 2269 Info.FirstArg = P; 2270 Info.SecondArg = A; 2271 return Sema::TDK_NonDeducedMismatch; 2272 2273 case TemplateArgument::TemplateExpansion: 2274 llvm_unreachable("caller should handle pack expansions"); 2275 2276 case TemplateArgument::Declaration: 2277 if (A.getKind() == TemplateArgument::Declaration && 2278 isSameDeclaration(P.getAsDecl(), A.getAsDecl())) 2279 return Sema::TDK_Success; 2280 2281 Info.FirstArg = P; 2282 Info.SecondArg = A; 2283 return Sema::TDK_NonDeducedMismatch; 2284 2285 case TemplateArgument::NullPtr: 2286 if (A.getKind() == TemplateArgument::NullPtr && 2287 S.Context.hasSameType(P.getNullPtrType(), A.getNullPtrType())) 2288 return Sema::TDK_Success; 2289 2290 Info.FirstArg = P; 2291 Info.SecondArg = A; 2292 return Sema::TDK_NonDeducedMismatch; 2293 2294 case TemplateArgument::Integral: 2295 if (A.getKind() == TemplateArgument::Integral) { 2296 if (hasSameExtendedValue(P.getAsIntegral(), A.getAsIntegral())) 2297 return Sema::TDK_Success; 2298 } 2299 Info.FirstArg = P; 2300 Info.SecondArg = A; 2301 return Sema::TDK_NonDeducedMismatch; 2302 2303 case TemplateArgument::Expression: 2304 if (const NonTypeTemplateParmDecl *NTTP = 2305 getDeducedParameterFromExpr(Info, P.getAsExpr())) { 2306 if (A.getKind() == TemplateArgument::Integral) 2307 return DeduceNonTypeTemplateArgument( 2308 S, TemplateParams, NTTP, A.getAsIntegral(), A.getIntegralType(), 2309 /*ArrayBound=*/false, Info, Deduced); 2310 if (A.getKind() == TemplateArgument::NullPtr) 2311 return DeduceNullPtrTemplateArgument(S, TemplateParams, NTTP, 2312 A.getNullPtrType(), Info, Deduced); 2313 if (A.getKind() == TemplateArgument::Expression) 2314 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, 2315 A.getAsExpr(), Info, Deduced); 2316 if (A.getKind() == TemplateArgument::Declaration) 2317 return DeduceNonTypeTemplateArgument( 2318 S, TemplateParams, NTTP, A.getAsDecl(), A.getParamTypeForDecl(), 2319 Info, Deduced); 2320 2321 Info.FirstArg = P; 2322 Info.SecondArg = A; 2323 return Sema::TDK_NonDeducedMismatch; 2324 } 2325 2326 // Can't deduce anything, but that's okay. 2327 return Sema::TDK_Success; 2328 case TemplateArgument::Pack: 2329 llvm_unreachable("Argument packs should be expanded by the caller!"); 2330 } 2331 2332 llvm_unreachable("Invalid TemplateArgument Kind!"); 2333 } 2334 2335 /// Determine whether there is a template argument to be used for 2336 /// deduction. 2337 /// 2338 /// This routine "expands" argument packs in-place, overriding its input 2339 /// parameters so that \c Args[ArgIdx] will be the available template argument. 2340 /// 2341 /// \returns true if there is another template argument (which will be at 2342 /// \c Args[ArgIdx]), false otherwise. 2343 static bool hasTemplateArgumentForDeduction(ArrayRef<TemplateArgument> &Args, 2344 unsigned &ArgIdx) { 2345 if (ArgIdx == Args.size()) 2346 return false; 2347 2348 const TemplateArgument &Arg = Args[ArgIdx]; 2349 if (Arg.getKind() != TemplateArgument::Pack) 2350 return true; 2351 2352 assert(ArgIdx == Args.size() - 1 && "Pack not at the end of argument list?"); 2353 Args = Arg.pack_elements(); 2354 ArgIdx = 0; 2355 return ArgIdx < Args.size(); 2356 } 2357 2358 /// Determine whether the given set of template arguments has a pack 2359 /// expansion that is not the last template argument. 2360 static bool hasPackExpansionBeforeEnd(ArrayRef<TemplateArgument> Args) { 2361 bool FoundPackExpansion = false; 2362 for (const auto &A : Args) { 2363 if (FoundPackExpansion) 2364 return true; 2365 2366 if (A.getKind() == TemplateArgument::Pack) 2367 return hasPackExpansionBeforeEnd(A.pack_elements()); 2368 2369 // FIXME: If this is a fixed-arity pack expansion from an outer level of 2370 // templates, it should not be treated as a pack expansion. 2371 if (A.isPackExpansion()) 2372 FoundPackExpansion = true; 2373 } 2374 2375 return false; 2376 } 2377 2378 static Sema::TemplateDeductionResult 2379 DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams, 2380 ArrayRef<TemplateArgument> Ps, 2381 ArrayRef<TemplateArgument> As, 2382 TemplateDeductionInfo &Info, 2383 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2384 bool NumberOfArgumentsMustMatch) { 2385 // C++0x [temp.deduct.type]p9: 2386 // If the template argument list of P contains a pack expansion that is not 2387 // the last template argument, the entire template argument list is a 2388 // non-deduced context. 2389 if (hasPackExpansionBeforeEnd(Ps)) 2390 return Sema::TDK_Success; 2391 2392 // C++0x [temp.deduct.type]p9: 2393 // If P has a form that contains <T> or <i>, then each argument Pi of the 2394 // respective template argument list P is compared with the corresponding 2395 // argument Ai of the corresponding template argument list of A. 2396 unsigned ArgIdx = 0, ParamIdx = 0; 2397 for (; hasTemplateArgumentForDeduction(Ps, ParamIdx); ++ParamIdx) { 2398 const TemplateArgument &P = Ps[ParamIdx]; 2399 if (!P.isPackExpansion()) { 2400 // The simple case: deduce template arguments by matching Pi and Ai. 2401 2402 // Check whether we have enough arguments. 2403 if (!hasTemplateArgumentForDeduction(As, ArgIdx)) 2404 return NumberOfArgumentsMustMatch 2405 ? Sema::TDK_MiscellaneousDeductionFailure 2406 : Sema::TDK_Success; 2407 2408 // C++1z [temp.deduct.type]p9: 2409 // During partial ordering, if Ai was originally a pack expansion [and] 2410 // Pi is not a pack expansion, template argument deduction fails. 2411 if (As[ArgIdx].isPackExpansion()) 2412 return Sema::TDK_MiscellaneousDeductionFailure; 2413 2414 // Perform deduction for this Pi/Ai pair. 2415 if (auto Result = DeduceTemplateArguments(S, TemplateParams, P, 2416 As[ArgIdx], Info, Deduced)) 2417 return Result; 2418 2419 // Move to the next argument. 2420 ++ArgIdx; 2421 continue; 2422 } 2423 2424 // The parameter is a pack expansion. 2425 2426 // C++0x [temp.deduct.type]p9: 2427 // If Pi is a pack expansion, then the pattern of Pi is compared with 2428 // each remaining argument in the template argument list of A. Each 2429 // comparison deduces template arguments for subsequent positions in the 2430 // template parameter packs expanded by Pi. 2431 TemplateArgument Pattern = P.getPackExpansionPattern(); 2432 2433 // Prepare to deduce the packs within the pattern. 2434 PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern); 2435 2436 // Keep track of the deduced template arguments for each parameter pack 2437 // expanded by this pack expansion (the outer index) and for each 2438 // template argument (the inner SmallVectors). 2439 for (; hasTemplateArgumentForDeduction(As, ArgIdx) && 2440 PackScope.hasNextElement(); 2441 ++ArgIdx) { 2442 // Deduce template arguments from the pattern. 2443 if (auto Result = DeduceTemplateArguments(S, TemplateParams, Pattern, 2444 As[ArgIdx], Info, Deduced)) 2445 return Result; 2446 2447 PackScope.nextPackElement(); 2448 } 2449 2450 // Build argument packs for each of the parameter packs expanded by this 2451 // pack expansion. 2452 if (auto Result = PackScope.finish()) 2453 return Result; 2454 } 2455 2456 return Sema::TDK_Success; 2457 } 2458 2459 static Sema::TemplateDeductionResult 2460 DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams, 2461 const TemplateArgumentList &ParamList, 2462 const TemplateArgumentList &ArgList, 2463 TemplateDeductionInfo &Info, 2464 SmallVectorImpl<DeducedTemplateArgument> &Deduced) { 2465 return DeduceTemplateArguments(S, TemplateParams, ParamList.asArray(), 2466 ArgList.asArray(), Info, Deduced, 2467 /*NumberOfArgumentsMustMatch=*/false); 2468 } 2469 2470 /// Determine whether two template arguments are the same. 2471 static bool isSameTemplateArg(ASTContext &Context, 2472 TemplateArgument X, 2473 const TemplateArgument &Y, 2474 bool PartialOrdering, 2475 bool PackExpansionMatchesPack = false) { 2476 // If we're checking deduced arguments (X) against original arguments (Y), 2477 // we will have flattened packs to non-expansions in X. 2478 if (PackExpansionMatchesPack && X.isPackExpansion() && !Y.isPackExpansion()) 2479 X = X.getPackExpansionPattern(); 2480 2481 if (X.getKind() != Y.getKind()) 2482 return false; 2483 2484 switch (X.getKind()) { 2485 case TemplateArgument::Null: 2486 llvm_unreachable("Comparing NULL template argument"); 2487 2488 case TemplateArgument::Type: 2489 return Context.getCanonicalType(X.getAsType()) == 2490 Context.getCanonicalType(Y.getAsType()); 2491 2492 case TemplateArgument::Declaration: 2493 return isSameDeclaration(X.getAsDecl(), Y.getAsDecl()); 2494 2495 case TemplateArgument::NullPtr: 2496 return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType()); 2497 2498 case TemplateArgument::Template: 2499 case TemplateArgument::TemplateExpansion: 2500 return Context.getCanonicalTemplateName( 2501 X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() == 2502 Context.getCanonicalTemplateName( 2503 Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer(); 2504 2505 case TemplateArgument::Integral: 2506 return hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral()); 2507 2508 case TemplateArgument::Expression: { 2509 llvm::FoldingSetNodeID XID, YID; 2510 X.getAsExpr()->Profile(XID, Context, true); 2511 Y.getAsExpr()->Profile(YID, Context, true); 2512 return XID == YID; 2513 } 2514 2515 case TemplateArgument::Pack: { 2516 unsigned PackIterationSize = X.pack_size(); 2517 if (X.pack_size() != Y.pack_size()) { 2518 if (!PartialOrdering) 2519 return false; 2520 2521 // C++0x [temp.deduct.type]p9: 2522 // During partial ordering, if Ai was originally a pack expansion: 2523 // - if P does not contain a template argument corresponding to Ai 2524 // then Ai is ignored; 2525 bool XHasMoreArg = X.pack_size() > Y.pack_size(); 2526 if (!(XHasMoreArg && X.pack_elements().back().isPackExpansion()) && 2527 !(!XHasMoreArg && Y.pack_elements().back().isPackExpansion())) 2528 return false; 2529 2530 if (XHasMoreArg) 2531 PackIterationSize = Y.pack_size(); 2532 } 2533 2534 ArrayRef<TemplateArgument> XP = X.pack_elements(); 2535 ArrayRef<TemplateArgument> YP = Y.pack_elements(); 2536 for (unsigned i = 0; i < PackIterationSize; ++i) 2537 if (!isSameTemplateArg(Context, XP[i], YP[i], PartialOrdering, 2538 PackExpansionMatchesPack)) 2539 return false; 2540 return true; 2541 } 2542 } 2543 2544 llvm_unreachable("Invalid TemplateArgument Kind!"); 2545 } 2546 2547 /// Allocate a TemplateArgumentLoc where all locations have 2548 /// been initialized to the given location. 2549 /// 2550 /// \param Arg The template argument we are producing template argument 2551 /// location information for. 2552 /// 2553 /// \param NTTPType For a declaration template argument, the type of 2554 /// the non-type template parameter that corresponds to this template 2555 /// argument. Can be null if no type sugar is available to add to the 2556 /// type from the template argument. 2557 /// 2558 /// \param Loc The source location to use for the resulting template 2559 /// argument. 2560 TemplateArgumentLoc 2561 Sema::getTrivialTemplateArgumentLoc(const TemplateArgument &Arg, 2562 QualType NTTPType, SourceLocation Loc) { 2563 switch (Arg.getKind()) { 2564 case TemplateArgument::Null: 2565 llvm_unreachable("Can't get a NULL template argument here"); 2566 2567 case TemplateArgument::Type: 2568 return TemplateArgumentLoc( 2569 Arg, Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc)); 2570 2571 case TemplateArgument::Declaration: { 2572 if (NTTPType.isNull()) 2573 NTTPType = Arg.getParamTypeForDecl(); 2574 Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc) 2575 .getAs<Expr>(); 2576 return TemplateArgumentLoc(TemplateArgument(E), E); 2577 } 2578 2579 case TemplateArgument::NullPtr: { 2580 if (NTTPType.isNull()) 2581 NTTPType = Arg.getNullPtrType(); 2582 Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc) 2583 .getAs<Expr>(); 2584 return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true), 2585 E); 2586 } 2587 2588 case TemplateArgument::Integral: { 2589 Expr *E = 2590 BuildExpressionFromIntegralTemplateArgument(Arg, Loc).getAs<Expr>(); 2591 return TemplateArgumentLoc(TemplateArgument(E), E); 2592 } 2593 2594 case TemplateArgument::Template: 2595 case TemplateArgument::TemplateExpansion: { 2596 NestedNameSpecifierLocBuilder Builder; 2597 TemplateName Template = Arg.getAsTemplateOrTemplatePattern(); 2598 if (DependentTemplateName *DTN = Template.getAsDependentTemplateName()) 2599 Builder.MakeTrivial(Context, DTN->getQualifier(), Loc); 2600 else if (QualifiedTemplateName *QTN = 2601 Template.getAsQualifiedTemplateName()) 2602 Builder.MakeTrivial(Context, QTN->getQualifier(), Loc); 2603 2604 if (Arg.getKind() == TemplateArgument::Template) 2605 return TemplateArgumentLoc(Context, Arg, 2606 Builder.getWithLocInContext(Context), Loc); 2607 2608 return TemplateArgumentLoc( 2609 Context, Arg, Builder.getWithLocInContext(Context), Loc, Loc); 2610 } 2611 2612 case TemplateArgument::Expression: 2613 return TemplateArgumentLoc(Arg, Arg.getAsExpr()); 2614 2615 case TemplateArgument::Pack: 2616 return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo()); 2617 } 2618 2619 llvm_unreachable("Invalid TemplateArgument Kind!"); 2620 } 2621 2622 TemplateArgumentLoc 2623 Sema::getIdentityTemplateArgumentLoc(NamedDecl *TemplateParm, 2624 SourceLocation Location) { 2625 return getTrivialTemplateArgumentLoc( 2626 Context.getInjectedTemplateArg(TemplateParm), QualType(), Location); 2627 } 2628 2629 /// Convert the given deduced template argument and add it to the set of 2630 /// fully-converted template arguments. 2631 static bool ConvertDeducedTemplateArgument( 2632 Sema &S, NamedDecl *Param, DeducedTemplateArgument Arg, NamedDecl *Template, 2633 TemplateDeductionInfo &Info, bool IsDeduced, 2634 SmallVectorImpl<TemplateArgument> &SugaredOutput, 2635 SmallVectorImpl<TemplateArgument> &CanonicalOutput) { 2636 auto ConvertArg = [&](DeducedTemplateArgument Arg, 2637 unsigned ArgumentPackIndex) { 2638 // Convert the deduced template argument into a template 2639 // argument that we can check, almost as if the user had written 2640 // the template argument explicitly. 2641 TemplateArgumentLoc ArgLoc = 2642 S.getTrivialTemplateArgumentLoc(Arg, QualType(), Info.getLocation()); 2643 2644 // Check the template argument, converting it as necessary. 2645 return S.CheckTemplateArgument( 2646 Param, ArgLoc, Template, Template->getLocation(), 2647 Template->getSourceRange().getEnd(), ArgumentPackIndex, SugaredOutput, 2648 CanonicalOutput, 2649 IsDeduced 2650 ? (Arg.wasDeducedFromArrayBound() ? Sema::CTAK_DeducedFromArrayBound 2651 : Sema::CTAK_Deduced) 2652 : Sema::CTAK_Specified); 2653 }; 2654 2655 if (Arg.getKind() == TemplateArgument::Pack) { 2656 // This is a template argument pack, so check each of its arguments against 2657 // the template parameter. 2658 SmallVector<TemplateArgument, 2> SugaredPackedArgsBuilder, 2659 CanonicalPackedArgsBuilder; 2660 for (const auto &P : Arg.pack_elements()) { 2661 // When converting the deduced template argument, append it to the 2662 // general output list. We need to do this so that the template argument 2663 // checking logic has all of the prior template arguments available. 2664 DeducedTemplateArgument InnerArg(P); 2665 InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound()); 2666 assert(InnerArg.getKind() != TemplateArgument::Pack && 2667 "deduced nested pack"); 2668 if (P.isNull()) { 2669 // We deduced arguments for some elements of this pack, but not for 2670 // all of them. This happens if we get a conditionally-non-deduced 2671 // context in a pack expansion (such as an overload set in one of the 2672 // arguments). 2673 S.Diag(Param->getLocation(), 2674 diag::err_template_arg_deduced_incomplete_pack) 2675 << Arg << Param; 2676 return true; 2677 } 2678 if (ConvertArg(InnerArg, SugaredPackedArgsBuilder.size())) 2679 return true; 2680 2681 // Move the converted template argument into our argument pack. 2682 SugaredPackedArgsBuilder.push_back(SugaredOutput.pop_back_val()); 2683 CanonicalPackedArgsBuilder.push_back(CanonicalOutput.pop_back_val()); 2684 } 2685 2686 // If the pack is empty, we still need to substitute into the parameter 2687 // itself, in case that substitution fails. 2688 if (SugaredPackedArgsBuilder.empty()) { 2689 LocalInstantiationScope Scope(S); 2690 MultiLevelTemplateArgumentList Args(Template, SugaredOutput, 2691 /*Final=*/true); 2692 2693 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 2694 Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template, 2695 NTTP, SugaredOutput, 2696 Template->getSourceRange()); 2697 if (Inst.isInvalid() || 2698 S.SubstType(NTTP->getType(), Args, NTTP->getLocation(), 2699 NTTP->getDeclName()).isNull()) 2700 return true; 2701 } else if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(Param)) { 2702 Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template, 2703 TTP, SugaredOutput, 2704 Template->getSourceRange()); 2705 if (Inst.isInvalid() || !S.SubstDecl(TTP, S.CurContext, Args)) 2706 return true; 2707 } 2708 // For type parameters, no substitution is ever required. 2709 } 2710 2711 // Create the resulting argument pack. 2712 SugaredOutput.push_back( 2713 TemplateArgument::CreatePackCopy(S.Context, SugaredPackedArgsBuilder)); 2714 CanonicalOutput.push_back(TemplateArgument::CreatePackCopy( 2715 S.Context, CanonicalPackedArgsBuilder)); 2716 return false; 2717 } 2718 2719 return ConvertArg(Arg, 0); 2720 } 2721 2722 // FIXME: This should not be a template, but 2723 // ClassTemplatePartialSpecializationDecl sadly does not derive from 2724 // TemplateDecl. 2725 template <typename TemplateDeclT> 2726 static Sema::TemplateDeductionResult ConvertDeducedTemplateArguments( 2727 Sema &S, TemplateDeclT *Template, bool IsDeduced, 2728 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2729 TemplateDeductionInfo &Info, 2730 SmallVectorImpl<TemplateArgument> &SugaredBuilder, 2731 SmallVectorImpl<TemplateArgument> &CanonicalBuilder, 2732 LocalInstantiationScope *CurrentInstantiationScope = nullptr, 2733 unsigned NumAlreadyConverted = 0, bool PartialOverloading = false) { 2734 TemplateParameterList *TemplateParams = Template->getTemplateParameters(); 2735 2736 for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) { 2737 NamedDecl *Param = TemplateParams->getParam(I); 2738 2739 // C++0x [temp.arg.explicit]p3: 2740 // A trailing template parameter pack (14.5.3) not otherwise deduced will 2741 // be deduced to an empty sequence of template arguments. 2742 // FIXME: Where did the word "trailing" come from? 2743 if (Deduced[I].isNull() && Param->isTemplateParameterPack()) { 2744 if (auto Result = 2745 PackDeductionScope(S, TemplateParams, Deduced, Info, I).finish()) 2746 return Result; 2747 } 2748 2749 if (!Deduced[I].isNull()) { 2750 if (I < NumAlreadyConverted) { 2751 // We may have had explicitly-specified template arguments for a 2752 // template parameter pack (that may or may not have been extended 2753 // via additional deduced arguments). 2754 if (Param->isParameterPack() && CurrentInstantiationScope && 2755 CurrentInstantiationScope->getPartiallySubstitutedPack() == Param) { 2756 // Forget the partially-substituted pack; its substitution is now 2757 // complete. 2758 CurrentInstantiationScope->ResetPartiallySubstitutedPack(); 2759 // We still need to check the argument in case it was extended by 2760 // deduction. 2761 } else { 2762 // We have already fully type-checked and converted this 2763 // argument, because it was explicitly-specified. Just record the 2764 // presence of this argument. 2765 SugaredBuilder.push_back(Deduced[I]); 2766 CanonicalBuilder.push_back( 2767 S.Context.getCanonicalTemplateArgument(Deduced[I])); 2768 continue; 2769 } 2770 } 2771 2772 // We may have deduced this argument, so it still needs to be 2773 // checked and converted. 2774 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info, 2775 IsDeduced, SugaredBuilder, 2776 CanonicalBuilder)) { 2777 Info.Param = makeTemplateParameter(Param); 2778 // FIXME: These template arguments are temporary. Free them! 2779 Info.reset( 2780 TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder), 2781 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder)); 2782 return Sema::TDK_SubstitutionFailure; 2783 } 2784 2785 continue; 2786 } 2787 2788 // Substitute into the default template argument, if available. 2789 bool HasDefaultArg = false; 2790 TemplateDecl *TD = dyn_cast<TemplateDecl>(Template); 2791 if (!TD) { 2792 assert(isa<ClassTemplatePartialSpecializationDecl>(Template) || 2793 isa<VarTemplatePartialSpecializationDecl>(Template)); 2794 return Sema::TDK_Incomplete; 2795 } 2796 2797 TemplateArgumentLoc DefArg; 2798 { 2799 Qualifiers ThisTypeQuals; 2800 CXXRecordDecl *ThisContext = nullptr; 2801 if (auto *Rec = dyn_cast<CXXRecordDecl>(TD->getDeclContext())) 2802 if (Rec->isLambda()) 2803 if (auto *Method = dyn_cast<CXXMethodDecl>(Rec->getDeclContext())) { 2804 ThisContext = Method->getParent(); 2805 ThisTypeQuals = Method->getMethodQualifiers(); 2806 } 2807 2808 Sema::CXXThisScopeRAII ThisScope(S, ThisContext, ThisTypeQuals, 2809 S.getLangOpts().CPlusPlus17); 2810 2811 DefArg = S.SubstDefaultTemplateArgumentIfAvailable( 2812 TD, TD->getLocation(), TD->getSourceRange().getEnd(), Param, 2813 SugaredBuilder, CanonicalBuilder, HasDefaultArg); 2814 } 2815 2816 // If there was no default argument, deduction is incomplete. 2817 if (DefArg.getArgument().isNull()) { 2818 Info.Param = makeTemplateParameter( 2819 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 2820 Info.reset(TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder), 2821 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder)); 2822 if (PartialOverloading) break; 2823 2824 return HasDefaultArg ? Sema::TDK_SubstitutionFailure 2825 : Sema::TDK_Incomplete; 2826 } 2827 2828 // Check whether we can actually use the default argument. 2829 if (S.CheckTemplateArgument( 2830 Param, DefArg, TD, TD->getLocation(), TD->getSourceRange().getEnd(), 2831 0, SugaredBuilder, CanonicalBuilder, Sema::CTAK_Specified)) { 2832 Info.Param = makeTemplateParameter( 2833 const_cast<NamedDecl *>(TemplateParams->getParam(I))); 2834 // FIXME: These template arguments are temporary. Free them! 2835 Info.reset(TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder), 2836 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder)); 2837 return Sema::TDK_SubstitutionFailure; 2838 } 2839 2840 // If we get here, we successfully used the default template argument. 2841 } 2842 2843 return Sema::TDK_Success; 2844 } 2845 2846 static DeclContext *getAsDeclContextOrEnclosing(Decl *D) { 2847 if (auto *DC = dyn_cast<DeclContext>(D)) 2848 return DC; 2849 return D->getDeclContext(); 2850 } 2851 2852 template<typename T> struct IsPartialSpecialization { 2853 static constexpr bool value = false; 2854 }; 2855 template<> 2856 struct IsPartialSpecialization<ClassTemplatePartialSpecializationDecl> { 2857 static constexpr bool value = true; 2858 }; 2859 template<> 2860 struct IsPartialSpecialization<VarTemplatePartialSpecializationDecl> { 2861 static constexpr bool value = true; 2862 }; 2863 template <typename TemplateDeclT> 2864 static bool DeducedArgsNeedReplacement(TemplateDeclT *Template) { 2865 return false; 2866 } 2867 template <> 2868 bool DeducedArgsNeedReplacement<VarTemplatePartialSpecializationDecl>( 2869 VarTemplatePartialSpecializationDecl *Spec) { 2870 return !Spec->isClassScopeExplicitSpecialization(); 2871 } 2872 template <> 2873 bool DeducedArgsNeedReplacement<ClassTemplatePartialSpecializationDecl>( 2874 ClassTemplatePartialSpecializationDecl *Spec) { 2875 return !Spec->isClassScopeExplicitSpecialization(); 2876 } 2877 2878 template <typename TemplateDeclT> 2879 static Sema::TemplateDeductionResult 2880 CheckDeducedArgumentConstraints(Sema &S, TemplateDeclT *Template, 2881 ArrayRef<TemplateArgument> SugaredDeducedArgs, 2882 ArrayRef<TemplateArgument> CanonicalDeducedArgs, 2883 TemplateDeductionInfo &Info) { 2884 llvm::SmallVector<const Expr *, 3> AssociatedConstraints; 2885 Template->getAssociatedConstraints(AssociatedConstraints); 2886 2887 bool NeedsReplacement = DeducedArgsNeedReplacement(Template); 2888 TemplateArgumentList DeducedTAL{TemplateArgumentList::OnStack, 2889 CanonicalDeducedArgs}; 2890 2891 MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs( 2892 Template, /*Final=*/false, 2893 /*InnerMost=*/NeedsReplacement ? nullptr : &DeducedTAL, 2894 /*RelativeToPrimary=*/true, /*Pattern=*/ 2895 nullptr, /*ForConstraintInstantiation=*/true); 2896 2897 // getTemplateInstantiationArgs picks up the non-deduced version of the 2898 // template args when this is a variable template partial specialization and 2899 // not class-scope explicit specialization, so replace with Deduced Args 2900 // instead of adding to inner-most. 2901 if (NeedsReplacement) 2902 MLTAL.replaceInnermostTemplateArguments(Template, CanonicalDeducedArgs); 2903 2904 if (S.CheckConstraintSatisfaction(Template, AssociatedConstraints, MLTAL, 2905 Info.getLocation(), 2906 Info.AssociatedConstraintsSatisfaction) || 2907 !Info.AssociatedConstraintsSatisfaction.IsSatisfied) { 2908 Info.reset( 2909 TemplateArgumentList::CreateCopy(S.Context, SugaredDeducedArgs), 2910 TemplateArgumentList::CreateCopy(S.Context, CanonicalDeducedArgs)); 2911 return Sema::TDK_ConstraintsNotSatisfied; 2912 } 2913 return Sema::TDK_Success; 2914 } 2915 2916 /// Complete template argument deduction for a partial specialization. 2917 template <typename T> 2918 static std::enable_if_t<IsPartialSpecialization<T>::value, 2919 Sema::TemplateDeductionResult> 2920 FinishTemplateArgumentDeduction( 2921 Sema &S, T *Partial, bool IsPartialOrdering, 2922 const TemplateArgumentList &TemplateArgs, 2923 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 2924 TemplateDeductionInfo &Info) { 2925 // Unevaluated SFINAE context. 2926 EnterExpressionEvaluationContext Unevaluated( 2927 S, Sema::ExpressionEvaluationContext::Unevaluated); 2928 Sema::SFINAETrap Trap(S); 2929 2930 Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Partial)); 2931 2932 // C++ [temp.deduct.type]p2: 2933 // [...] or if any template argument remains neither deduced nor 2934 // explicitly specified, template argument deduction fails. 2935 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder; 2936 if (auto Result = ConvertDeducedTemplateArguments( 2937 S, Partial, IsPartialOrdering, Deduced, Info, SugaredBuilder, 2938 CanonicalBuilder)) 2939 return Result; 2940 2941 // Form the template argument list from the deduced template arguments. 2942 TemplateArgumentList *SugaredDeducedArgumentList = 2943 TemplateArgumentList::CreateCopy(S.Context, SugaredBuilder); 2944 TemplateArgumentList *CanonicalDeducedArgumentList = 2945 TemplateArgumentList::CreateCopy(S.Context, CanonicalBuilder); 2946 2947 Info.reset(SugaredDeducedArgumentList, CanonicalDeducedArgumentList); 2948 2949 // Substitute the deduced template arguments into the template 2950 // arguments of the class template partial specialization, and 2951 // verify that the instantiated template arguments are both valid 2952 // and are equivalent to the template arguments originally provided 2953 // to the class template. 2954 LocalInstantiationScope InstScope(S); 2955 auto *Template = Partial->getSpecializedTemplate(); 2956 const ASTTemplateArgumentListInfo *PartialTemplArgInfo = 2957 Partial->getTemplateArgsAsWritten(); 2958 2959 TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc, 2960 PartialTemplArgInfo->RAngleLoc); 2961 2962 if (S.SubstTemplateArguments(PartialTemplArgInfo->arguments(), 2963 MultiLevelTemplateArgumentList(Partial, 2964 SugaredBuilder, 2965 /*Final=*/true), 2966 InstArgs)) { 2967 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx; 2968 if (ParamIdx >= Partial->getTemplateParameters()->size()) 2969 ParamIdx = Partial->getTemplateParameters()->size() - 1; 2970 2971 Decl *Param = const_cast<NamedDecl *>( 2972 Partial->getTemplateParameters()->getParam(ParamIdx)); 2973 Info.Param = makeTemplateParameter(Param); 2974 Info.FirstArg = (*PartialTemplArgInfo)[ArgIdx].getArgument(); 2975 return Sema::TDK_SubstitutionFailure; 2976 } 2977 2978 bool ConstraintsNotSatisfied; 2979 SmallVector<TemplateArgument, 4> SugaredConvertedInstArgs, 2980 CanonicalConvertedInstArgs; 2981 if (S.CheckTemplateArgumentList( 2982 Template, Partial->getLocation(), InstArgs, false, 2983 SugaredConvertedInstArgs, CanonicalConvertedInstArgs, 2984 /*UpdateArgsWithConversions=*/true, &ConstraintsNotSatisfied)) 2985 return ConstraintsNotSatisfied ? Sema::TDK_ConstraintsNotSatisfied 2986 : Sema::TDK_SubstitutionFailure; 2987 2988 TemplateParameterList *TemplateParams = Template->getTemplateParameters(); 2989 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) { 2990 TemplateArgument InstArg = SugaredConvertedInstArgs.data()[I]; 2991 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg, 2992 IsPartialOrdering)) { 2993 Info.Param = makeTemplateParameter(TemplateParams->getParam(I)); 2994 Info.FirstArg = TemplateArgs[I]; 2995 Info.SecondArg = InstArg; 2996 return Sema::TDK_NonDeducedMismatch; 2997 } 2998 } 2999 3000 if (Trap.hasErrorOccurred()) 3001 return Sema::TDK_SubstitutionFailure; 3002 3003 if (auto Result = CheckDeducedArgumentConstraints(S, Partial, SugaredBuilder, 3004 CanonicalBuilder, Info)) 3005 return Result; 3006 3007 return Sema::TDK_Success; 3008 } 3009 3010 /// Complete template argument deduction for a class or variable template, 3011 /// when partial ordering against a partial specialization. 3012 // FIXME: Factor out duplication with partial specialization version above. 3013 static Sema::TemplateDeductionResult FinishTemplateArgumentDeduction( 3014 Sema &S, TemplateDecl *Template, bool PartialOrdering, 3015 const TemplateArgumentList &TemplateArgs, 3016 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 3017 TemplateDeductionInfo &Info) { 3018 // Unevaluated SFINAE context. 3019 EnterExpressionEvaluationContext Unevaluated( 3020 S, Sema::ExpressionEvaluationContext::Unevaluated); 3021 Sema::SFINAETrap Trap(S); 3022 3023 Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Template)); 3024 3025 // C++ [temp.deduct.type]p2: 3026 // [...] or if any template argument remains neither deduced nor 3027 // explicitly specified, template argument deduction fails. 3028 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder; 3029 if (auto Result = ConvertDeducedTemplateArguments( 3030 S, Template, /*IsDeduced*/ PartialOrdering, Deduced, Info, 3031 SugaredBuilder, CanonicalBuilder, 3032 /*CurrentInstantiationScope=*/nullptr, 3033 /*NumAlreadyConverted=*/0U, /*PartialOverloading=*/false)) 3034 return Result; 3035 3036 // Check that we produced the correct argument list. 3037 TemplateParameterList *TemplateParams = Template->getTemplateParameters(); 3038 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) { 3039 TemplateArgument InstArg = CanonicalBuilder[I]; 3040 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg, PartialOrdering, 3041 /*PackExpansionMatchesPack=*/true)) { 3042 Info.Param = makeTemplateParameter(TemplateParams->getParam(I)); 3043 Info.FirstArg = TemplateArgs[I]; 3044 Info.SecondArg = InstArg; 3045 return Sema::TDK_NonDeducedMismatch; 3046 } 3047 } 3048 3049 if (Trap.hasErrorOccurred()) 3050 return Sema::TDK_SubstitutionFailure; 3051 3052 if (auto Result = CheckDeducedArgumentConstraints(S, Template, SugaredBuilder, 3053 CanonicalBuilder, Info)) 3054 return Result; 3055 3056 return Sema::TDK_Success; 3057 } 3058 3059 /// Perform template argument deduction to determine whether 3060 /// the given template arguments match the given class template 3061 /// partial specialization per C++ [temp.class.spec.match]. 3062 Sema::TemplateDeductionResult 3063 Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial, 3064 const TemplateArgumentList &TemplateArgs, 3065 TemplateDeductionInfo &Info) { 3066 if (Partial->isInvalidDecl()) 3067 return TDK_Invalid; 3068 3069 // C++ [temp.class.spec.match]p2: 3070 // A partial specialization matches a given actual template 3071 // argument list if the template arguments of the partial 3072 // specialization can be deduced from the actual template argument 3073 // list (14.8.2). 3074 3075 // Unevaluated SFINAE context. 3076 EnterExpressionEvaluationContext Unevaluated( 3077 *this, Sema::ExpressionEvaluationContext::Unevaluated); 3078 SFINAETrap Trap(*this); 3079 3080 // This deduction has no relation to any outer instantiation we might be 3081 // performing. 3082 LocalInstantiationScope InstantiationScope(*this); 3083 3084 SmallVector<DeducedTemplateArgument, 4> Deduced; 3085 Deduced.resize(Partial->getTemplateParameters()->size()); 3086 if (TemplateDeductionResult Result 3087 = ::DeduceTemplateArguments(*this, 3088 Partial->getTemplateParameters(), 3089 Partial->getTemplateArgs(), 3090 TemplateArgs, Info, Deduced)) 3091 return Result; 3092 3093 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end()); 3094 InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs, 3095 Info); 3096 if (Inst.isInvalid()) 3097 return TDK_InstantiationDepth; 3098 3099 if (Trap.hasErrorOccurred()) 3100 return Sema::TDK_SubstitutionFailure; 3101 3102 TemplateDeductionResult Result; 3103 runWithSufficientStackSpace(Info.getLocation(), [&] { 3104 Result = ::FinishTemplateArgumentDeduction(*this, Partial, 3105 /*IsPartialOrdering=*/false, 3106 TemplateArgs, Deduced, Info); 3107 }); 3108 return Result; 3109 } 3110 3111 /// Perform template argument deduction to determine whether 3112 /// the given template arguments match the given variable template 3113 /// partial specialization per C++ [temp.class.spec.match]. 3114 Sema::TemplateDeductionResult 3115 Sema::DeduceTemplateArguments(VarTemplatePartialSpecializationDecl *Partial, 3116 const TemplateArgumentList &TemplateArgs, 3117 TemplateDeductionInfo &Info) { 3118 if (Partial->isInvalidDecl()) 3119 return TDK_Invalid; 3120 3121 // C++ [temp.class.spec.match]p2: 3122 // A partial specialization matches a given actual template 3123 // argument list if the template arguments of the partial 3124 // specialization can be deduced from the actual template argument 3125 // list (14.8.2). 3126 3127 // Unevaluated SFINAE context. 3128 EnterExpressionEvaluationContext Unevaluated( 3129 *this, Sema::ExpressionEvaluationContext::Unevaluated); 3130 SFINAETrap Trap(*this); 3131 3132 // This deduction has no relation to any outer instantiation we might be 3133 // performing. 3134 LocalInstantiationScope InstantiationScope(*this); 3135 3136 SmallVector<DeducedTemplateArgument, 4> Deduced; 3137 Deduced.resize(Partial->getTemplateParameters()->size()); 3138 if (TemplateDeductionResult Result = ::DeduceTemplateArguments( 3139 *this, Partial->getTemplateParameters(), Partial->getTemplateArgs(), 3140 TemplateArgs, Info, Deduced)) 3141 return Result; 3142 3143 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end()); 3144 InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs, 3145 Info); 3146 if (Inst.isInvalid()) 3147 return TDK_InstantiationDepth; 3148 3149 if (Trap.hasErrorOccurred()) 3150 return Sema::TDK_SubstitutionFailure; 3151 3152 TemplateDeductionResult Result; 3153 runWithSufficientStackSpace(Info.getLocation(), [&] { 3154 Result = ::FinishTemplateArgumentDeduction(*this, Partial, 3155 /*IsPartialOrdering=*/false, 3156 TemplateArgs, Deduced, Info); 3157 }); 3158 return Result; 3159 } 3160 3161 /// Determine whether the given type T is a simple-template-id type. 3162 static bool isSimpleTemplateIdType(QualType T) { 3163 if (const TemplateSpecializationType *Spec 3164 = T->getAs<TemplateSpecializationType>()) 3165 return Spec->getTemplateName().getAsTemplateDecl() != nullptr; 3166 3167 // C++17 [temp.local]p2: 3168 // the injected-class-name [...] is equivalent to the template-name followed 3169 // by the template-arguments of the class template specialization or partial 3170 // specialization enclosed in <> 3171 // ... which means it's equivalent to a simple-template-id. 3172 // 3173 // This only arises during class template argument deduction for a copy 3174 // deduction candidate, where it permits slicing. 3175 if (T->getAs<InjectedClassNameType>()) 3176 return true; 3177 3178 return false; 3179 } 3180 3181 /// Substitute the explicitly-provided template arguments into the 3182 /// given function template according to C++ [temp.arg.explicit]. 3183 /// 3184 /// \param FunctionTemplate the function template into which the explicit 3185 /// template arguments will be substituted. 3186 /// 3187 /// \param ExplicitTemplateArgs the explicitly-specified template 3188 /// arguments. 3189 /// 3190 /// \param Deduced the deduced template arguments, which will be populated 3191 /// with the converted and checked explicit template arguments. 3192 /// 3193 /// \param ParamTypes will be populated with the instantiated function 3194 /// parameters. 3195 /// 3196 /// \param FunctionType if non-NULL, the result type of the function template 3197 /// will also be instantiated and the pointed-to value will be updated with 3198 /// the instantiated function type. 3199 /// 3200 /// \param Info if substitution fails for any reason, this object will be 3201 /// populated with more information about the failure. 3202 /// 3203 /// \returns TDK_Success if substitution was successful, or some failure 3204 /// condition. 3205 Sema::TemplateDeductionResult Sema::SubstituteExplicitTemplateArguments( 3206 FunctionTemplateDecl *FunctionTemplate, 3207 TemplateArgumentListInfo &ExplicitTemplateArgs, 3208 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 3209 SmallVectorImpl<QualType> &ParamTypes, QualType *FunctionType, 3210 TemplateDeductionInfo &Info) { 3211 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 3212 TemplateParameterList *TemplateParams 3213 = FunctionTemplate->getTemplateParameters(); 3214 3215 if (ExplicitTemplateArgs.size() == 0) { 3216 // No arguments to substitute; just copy over the parameter types and 3217 // fill in the function type. 3218 for (auto *P : Function->parameters()) 3219 ParamTypes.push_back(P->getType()); 3220 3221 if (FunctionType) 3222 *FunctionType = Function->getType(); 3223 return TDK_Success; 3224 } 3225 3226 // Unevaluated SFINAE context. 3227 EnterExpressionEvaluationContext Unevaluated( 3228 *this, Sema::ExpressionEvaluationContext::Unevaluated); 3229 SFINAETrap Trap(*this); 3230 3231 // C++ [temp.arg.explicit]p3: 3232 // Template arguments that are present shall be specified in the 3233 // declaration order of their corresponding template-parameters. The 3234 // template argument list shall not specify more template-arguments than 3235 // there are corresponding template-parameters. 3236 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder; 3237 3238 // Enter a new template instantiation context where we check the 3239 // explicitly-specified template arguments against this function template, 3240 // and then substitute them into the function parameter types. 3241 SmallVector<TemplateArgument, 4> DeducedArgs; 3242 InstantiatingTemplate Inst( 3243 *this, Info.getLocation(), FunctionTemplate, DeducedArgs, 3244 CodeSynthesisContext::ExplicitTemplateArgumentSubstitution, Info); 3245 if (Inst.isInvalid()) 3246 return TDK_InstantiationDepth; 3247 3248 if (CheckTemplateArgumentList(FunctionTemplate, SourceLocation(), 3249 ExplicitTemplateArgs, true, SugaredBuilder, 3250 CanonicalBuilder, 3251 /*UpdateArgsWithConversions=*/false) || 3252 Trap.hasErrorOccurred()) { 3253 unsigned Index = SugaredBuilder.size(); 3254 if (Index >= TemplateParams->size()) 3255 return TDK_SubstitutionFailure; 3256 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index)); 3257 return TDK_InvalidExplicitArguments; 3258 } 3259 3260 // Form the template argument list from the explicitly-specified 3261 // template arguments. 3262 TemplateArgumentList *SugaredExplicitArgumentList = 3263 TemplateArgumentList::CreateCopy(Context, SugaredBuilder); 3264 TemplateArgumentList *CanonicalExplicitArgumentList = 3265 TemplateArgumentList::CreateCopy(Context, CanonicalBuilder); 3266 Info.setExplicitArgs(SugaredExplicitArgumentList, 3267 CanonicalExplicitArgumentList); 3268 3269 // Template argument deduction and the final substitution should be 3270 // done in the context of the templated declaration. Explicit 3271 // argument substitution, on the other hand, needs to happen in the 3272 // calling context. 3273 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 3274 3275 // If we deduced template arguments for a template parameter pack, 3276 // note that the template argument pack is partially substituted and record 3277 // the explicit template arguments. They'll be used as part of deduction 3278 // for this template parameter pack. 3279 unsigned PartiallySubstitutedPackIndex = -1u; 3280 if (!CanonicalBuilder.empty()) { 3281 const TemplateArgument &Arg = CanonicalBuilder.back(); 3282 if (Arg.getKind() == TemplateArgument::Pack) { 3283 auto *Param = TemplateParams->getParam(CanonicalBuilder.size() - 1); 3284 // If this is a fully-saturated fixed-size pack, it should be 3285 // fully-substituted, not partially-substituted. 3286 std::optional<unsigned> Expansions = getExpandedPackSize(Param); 3287 if (!Expansions || Arg.pack_size() < *Expansions) { 3288 PartiallySubstitutedPackIndex = CanonicalBuilder.size() - 1; 3289 CurrentInstantiationScope->SetPartiallySubstitutedPack( 3290 Param, Arg.pack_begin(), Arg.pack_size()); 3291 } 3292 } 3293 } 3294 3295 const FunctionProtoType *Proto 3296 = Function->getType()->getAs<FunctionProtoType>(); 3297 assert(Proto && "Function template does not have a prototype?"); 3298 3299 // Isolate our substituted parameters from our caller. 3300 LocalInstantiationScope InstScope(*this, /*MergeWithOuterScope*/true); 3301 3302 ExtParameterInfoBuilder ExtParamInfos; 3303 3304 MultiLevelTemplateArgumentList MLTAL(FunctionTemplate, 3305 SugaredExplicitArgumentList->asArray(), 3306 /*Final=*/true); 3307 3308 // Instantiate the types of each of the function parameters given the 3309 // explicitly-specified template arguments. If the function has a trailing 3310 // return type, substitute it after the arguments to ensure we substitute 3311 // in lexical order. 3312 if (Proto->hasTrailingReturn()) { 3313 if (SubstParmTypes(Function->getLocation(), Function->parameters(), 3314 Proto->getExtParameterInfosOrNull(), MLTAL, ParamTypes, 3315 /*params=*/nullptr, ExtParamInfos)) 3316 return TDK_SubstitutionFailure; 3317 } 3318 3319 // Instantiate the return type. 3320 QualType ResultType; 3321 { 3322 // C++11 [expr.prim.general]p3: 3323 // If a declaration declares a member function or member function 3324 // template of a class X, the expression this is a prvalue of type 3325 // "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq 3326 // and the end of the function-definition, member-declarator, or 3327 // declarator. 3328 Qualifiers ThisTypeQuals; 3329 CXXRecordDecl *ThisContext = nullptr; 3330 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) { 3331 ThisContext = Method->getParent(); 3332 ThisTypeQuals = Method->getMethodQualifiers(); 3333 } 3334 3335 CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals, 3336 getLangOpts().CPlusPlus11); 3337 3338 ResultType = 3339 SubstType(Proto->getReturnType(), MLTAL, 3340 Function->getTypeSpecStartLoc(), Function->getDeclName()); 3341 if (ResultType.isNull() || Trap.hasErrorOccurred()) 3342 return TDK_SubstitutionFailure; 3343 // CUDA: Kernel function must have 'void' return type. 3344 if (getLangOpts().CUDA) 3345 if (Function->hasAttr<CUDAGlobalAttr>() && !ResultType->isVoidType()) { 3346 Diag(Function->getLocation(), diag::err_kern_type_not_void_return) 3347 << Function->getType() << Function->getSourceRange(); 3348 return TDK_SubstitutionFailure; 3349 } 3350 } 3351 3352 // Instantiate the types of each of the function parameters given the 3353 // explicitly-specified template arguments if we didn't do so earlier. 3354 if (!Proto->hasTrailingReturn() && 3355 SubstParmTypes(Function->getLocation(), Function->parameters(), 3356 Proto->getExtParameterInfosOrNull(), MLTAL, ParamTypes, 3357 /*params*/ nullptr, ExtParamInfos)) 3358 return TDK_SubstitutionFailure; 3359 3360 if (FunctionType) { 3361 auto EPI = Proto->getExtProtoInfo(); 3362 EPI.ExtParameterInfos = ExtParamInfos.getPointerOrNull(ParamTypes.size()); 3363 3364 // In C++1z onwards, exception specifications are part of the function type, 3365 // so substitution into the type must also substitute into the exception 3366 // specification. 3367 SmallVector<QualType, 4> ExceptionStorage; 3368 if (getLangOpts().CPlusPlus17 && 3369 SubstExceptionSpec(Function->getLocation(), EPI.ExceptionSpec, 3370 ExceptionStorage, MLTAL)) 3371 return TDK_SubstitutionFailure; 3372 3373 *FunctionType = BuildFunctionType(ResultType, ParamTypes, 3374 Function->getLocation(), 3375 Function->getDeclName(), 3376 EPI); 3377 if (FunctionType->isNull() || Trap.hasErrorOccurred()) 3378 return TDK_SubstitutionFailure; 3379 } 3380 3381 // C++ [temp.arg.explicit]p2: 3382 // Trailing template arguments that can be deduced (14.8.2) may be 3383 // omitted from the list of explicit template-arguments. If all of the 3384 // template arguments can be deduced, they may all be omitted; in this 3385 // case, the empty template argument list <> itself may also be omitted. 3386 // 3387 // Take all of the explicitly-specified arguments and put them into 3388 // the set of deduced template arguments. The partially-substituted 3389 // parameter pack, however, will be set to NULL since the deduction 3390 // mechanism handles the partially-substituted argument pack directly. 3391 Deduced.reserve(TemplateParams->size()); 3392 for (unsigned I = 0, N = SugaredExplicitArgumentList->size(); I != N; ++I) { 3393 const TemplateArgument &Arg = SugaredExplicitArgumentList->get(I); 3394 if (I == PartiallySubstitutedPackIndex) 3395 Deduced.push_back(DeducedTemplateArgument()); 3396 else 3397 Deduced.push_back(Arg); 3398 } 3399 3400 return TDK_Success; 3401 } 3402 3403 /// Check whether the deduced argument type for a call to a function 3404 /// template matches the actual argument type per C++ [temp.deduct.call]p4. 3405 static Sema::TemplateDeductionResult 3406 CheckOriginalCallArgDeduction(Sema &S, TemplateDeductionInfo &Info, 3407 Sema::OriginalCallArg OriginalArg, 3408 QualType DeducedA) { 3409 ASTContext &Context = S.Context; 3410 3411 auto Failed = [&]() -> Sema::TemplateDeductionResult { 3412 Info.FirstArg = TemplateArgument(DeducedA); 3413 Info.SecondArg = TemplateArgument(OriginalArg.OriginalArgType); 3414 Info.CallArgIndex = OriginalArg.ArgIdx; 3415 return OriginalArg.DecomposedParam ? Sema::TDK_DeducedMismatchNested 3416 : Sema::TDK_DeducedMismatch; 3417 }; 3418 3419 QualType A = OriginalArg.OriginalArgType; 3420 QualType OriginalParamType = OriginalArg.OriginalParamType; 3421 3422 // Check for type equality (top-level cv-qualifiers are ignored). 3423 if (Context.hasSameUnqualifiedType(A, DeducedA)) 3424 return Sema::TDK_Success; 3425 3426 // Strip off references on the argument types; they aren't needed for 3427 // the following checks. 3428 if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>()) 3429 DeducedA = DeducedARef->getPointeeType(); 3430 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) 3431 A = ARef->getPointeeType(); 3432 3433 // C++ [temp.deduct.call]p4: 3434 // [...] However, there are three cases that allow a difference: 3435 // - If the original P is a reference type, the deduced A (i.e., the 3436 // type referred to by the reference) can be more cv-qualified than 3437 // the transformed A. 3438 if (const ReferenceType *OriginalParamRef 3439 = OriginalParamType->getAs<ReferenceType>()) { 3440 // We don't want to keep the reference around any more. 3441 OriginalParamType = OriginalParamRef->getPointeeType(); 3442 3443 // FIXME: Resolve core issue (no number yet): if the original P is a 3444 // reference type and the transformed A is function type "noexcept F", 3445 // the deduced A can be F. 3446 QualType Tmp; 3447 if (A->isFunctionType() && S.IsFunctionConversion(A, DeducedA, Tmp)) 3448 return Sema::TDK_Success; 3449 3450 Qualifiers AQuals = A.getQualifiers(); 3451 Qualifiers DeducedAQuals = DeducedA.getQualifiers(); 3452 3453 // Under Objective-C++ ARC, the deduced type may have implicitly 3454 // been given strong or (when dealing with a const reference) 3455 // unsafe_unretained lifetime. If so, update the original 3456 // qualifiers to include this lifetime. 3457 if (S.getLangOpts().ObjCAutoRefCount && 3458 ((DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong && 3459 AQuals.getObjCLifetime() == Qualifiers::OCL_None) || 3460 (DeducedAQuals.hasConst() && 3461 DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone))) { 3462 AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime()); 3463 } 3464 3465 if (AQuals == DeducedAQuals) { 3466 // Qualifiers match; there's nothing to do. 3467 } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) { 3468 return Failed(); 3469 } else { 3470 // Qualifiers are compatible, so have the argument type adopt the 3471 // deduced argument type's qualifiers as if we had performed the 3472 // qualification conversion. 3473 A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals); 3474 } 3475 } 3476 3477 // - The transformed A can be another pointer or pointer to member 3478 // type that can be converted to the deduced A via a function pointer 3479 // conversion and/or a qualification conversion. 3480 // 3481 // Also allow conversions which merely strip __attribute__((noreturn)) from 3482 // function types (recursively). 3483 bool ObjCLifetimeConversion = false; 3484 QualType ResultTy; 3485 if ((A->isAnyPointerType() || A->isMemberPointerType()) && 3486 (S.IsQualificationConversion(A, DeducedA, false, 3487 ObjCLifetimeConversion) || 3488 S.IsFunctionConversion(A, DeducedA, ResultTy))) 3489 return Sema::TDK_Success; 3490 3491 // - If P is a class and P has the form simple-template-id, then the 3492 // transformed A can be a derived class of the deduced A. [...] 3493 // [...] Likewise, if P is a pointer to a class of the form 3494 // simple-template-id, the transformed A can be a pointer to a 3495 // derived class pointed to by the deduced A. 3496 if (const PointerType *OriginalParamPtr 3497 = OriginalParamType->getAs<PointerType>()) { 3498 if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) { 3499 if (const PointerType *APtr = A->getAs<PointerType>()) { 3500 if (A->getPointeeType()->isRecordType()) { 3501 OriginalParamType = OriginalParamPtr->getPointeeType(); 3502 DeducedA = DeducedAPtr->getPointeeType(); 3503 A = APtr->getPointeeType(); 3504 } 3505 } 3506 } 3507 } 3508 3509 if (Context.hasSameUnqualifiedType(A, DeducedA)) 3510 return Sema::TDK_Success; 3511 3512 if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) && 3513 S.IsDerivedFrom(Info.getLocation(), A, DeducedA)) 3514 return Sema::TDK_Success; 3515 3516 return Failed(); 3517 } 3518 3519 /// Find the pack index for a particular parameter index in an instantiation of 3520 /// a function template with specific arguments. 3521 /// 3522 /// \return The pack index for whichever pack produced this parameter, or -1 3523 /// if this was not produced by a parameter. Intended to be used as the 3524 /// ArgumentPackSubstitutionIndex for further substitutions. 3525 // FIXME: We should track this in OriginalCallArgs so we don't need to 3526 // reconstruct it here. 3527 static unsigned getPackIndexForParam(Sema &S, 3528 FunctionTemplateDecl *FunctionTemplate, 3529 const MultiLevelTemplateArgumentList &Args, 3530 unsigned ParamIdx) { 3531 unsigned Idx = 0; 3532 for (auto *PD : FunctionTemplate->getTemplatedDecl()->parameters()) { 3533 if (PD->isParameterPack()) { 3534 unsigned NumExpansions = 3535 S.getNumArgumentsInExpansion(PD->getType(), Args).value_or(1); 3536 if (Idx + NumExpansions > ParamIdx) 3537 return ParamIdx - Idx; 3538 Idx += NumExpansions; 3539 } else { 3540 if (Idx == ParamIdx) 3541 return -1; // Not a pack expansion 3542 ++Idx; 3543 } 3544 } 3545 3546 llvm_unreachable("parameter index would not be produced from template"); 3547 } 3548 3549 /// Finish template argument deduction for a function template, 3550 /// checking the deduced template arguments for completeness and forming 3551 /// the function template specialization. 3552 /// 3553 /// \param OriginalCallArgs If non-NULL, the original call arguments against 3554 /// which the deduced argument types should be compared. 3555 Sema::TemplateDeductionResult Sema::FinishTemplateArgumentDeduction( 3556 FunctionTemplateDecl *FunctionTemplate, 3557 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 3558 unsigned NumExplicitlySpecified, FunctionDecl *&Specialization, 3559 TemplateDeductionInfo &Info, 3560 SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs, 3561 bool PartialOverloading, llvm::function_ref<bool()> CheckNonDependent) { 3562 // Unevaluated SFINAE context. 3563 EnterExpressionEvaluationContext Unevaluated( 3564 *this, Sema::ExpressionEvaluationContext::Unevaluated); 3565 SFINAETrap Trap(*this); 3566 3567 // Enter a new template instantiation context while we instantiate the 3568 // actual function declaration. 3569 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end()); 3570 InstantiatingTemplate Inst( 3571 *this, Info.getLocation(), FunctionTemplate, DeducedArgs, 3572 CodeSynthesisContext::DeducedTemplateArgumentSubstitution, Info); 3573 if (Inst.isInvalid()) 3574 return TDK_InstantiationDepth; 3575 3576 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl()); 3577 3578 // C++ [temp.deduct.type]p2: 3579 // [...] or if any template argument remains neither deduced nor 3580 // explicitly specified, template argument deduction fails. 3581 SmallVector<TemplateArgument, 4> SugaredBuilder, CanonicalBuilder; 3582 if (auto Result = ConvertDeducedTemplateArguments( 3583 *this, FunctionTemplate, /*IsDeduced*/ true, Deduced, Info, 3584 SugaredBuilder, CanonicalBuilder, CurrentInstantiationScope, 3585 NumExplicitlySpecified, PartialOverloading)) 3586 return Result; 3587 3588 // C++ [temp.deduct.call]p10: [DR1391] 3589 // If deduction succeeds for all parameters that contain 3590 // template-parameters that participate in template argument deduction, 3591 // and all template arguments are explicitly specified, deduced, or 3592 // obtained from default template arguments, remaining parameters are then 3593 // compared with the corresponding arguments. For each remaining parameter 3594 // P with a type that was non-dependent before substitution of any 3595 // explicitly-specified template arguments, if the corresponding argument 3596 // A cannot be implicitly converted to P, deduction fails. 3597 if (CheckNonDependent()) 3598 return TDK_NonDependentConversionFailure; 3599 3600 // Form the template argument list from the deduced template arguments. 3601 TemplateArgumentList *SugaredDeducedArgumentList = 3602 TemplateArgumentList::CreateCopy(Context, SugaredBuilder); 3603 TemplateArgumentList *CanonicalDeducedArgumentList = 3604 TemplateArgumentList::CreateCopy(Context, CanonicalBuilder); 3605 Info.reset(SugaredDeducedArgumentList, CanonicalDeducedArgumentList); 3606 3607 // Substitute the deduced template arguments into the function template 3608 // declaration to produce the function template specialization. 3609 DeclContext *Owner = FunctionTemplate->getDeclContext(); 3610 if (FunctionTemplate->getFriendObjectKind()) 3611 Owner = FunctionTemplate->getLexicalDeclContext(); 3612 FunctionDecl *FD = FunctionTemplate->getTemplatedDecl(); 3613 // additional check for inline friend, 3614 // ``` 3615 // template <class F1> int foo(F1 X); 3616 // template <int A1> struct A { 3617 // template <class F1> friend int foo(F1 X) { return A1; } 3618 // }; 3619 // template struct A<1>; 3620 // int a = foo(1.0); 3621 // ``` 3622 const FunctionDecl *FDFriend; 3623 if (FD->getFriendObjectKind() == Decl::FriendObjectKind::FOK_None && 3624 FD->isDefined(FDFriend, /*CheckForPendingFriendDefinition*/ true) && 3625 FDFriend->getFriendObjectKind() != Decl::FriendObjectKind::FOK_None) { 3626 FD = const_cast<FunctionDecl *>(FDFriend); 3627 Owner = FD->getLexicalDeclContext(); 3628 } 3629 MultiLevelTemplateArgumentList SubstArgs( 3630 FunctionTemplate, CanonicalDeducedArgumentList->asArray(), 3631 /*Final=*/false); 3632 Specialization = cast_or_null<FunctionDecl>( 3633 SubstDecl(FD, Owner, SubstArgs)); 3634 if (!Specialization || Specialization->isInvalidDecl()) 3635 return TDK_SubstitutionFailure; 3636 3637 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() == 3638 FunctionTemplate->getCanonicalDecl()); 3639 3640 // If the template argument list is owned by the function template 3641 // specialization, release it. 3642 if (Specialization->getTemplateSpecializationArgs() == 3643 CanonicalDeducedArgumentList && 3644 !Trap.hasErrorOccurred()) 3645 Info.takeCanonical(); 3646 3647 // There may have been an error that did not prevent us from constructing a 3648 // declaration. Mark the declaration invalid and return with a substitution 3649 // failure. 3650 if (Trap.hasErrorOccurred()) { 3651 Specialization->setInvalidDecl(true); 3652 return TDK_SubstitutionFailure; 3653 } 3654 3655 // C++2a [temp.deduct]p5 3656 // [...] When all template arguments have been deduced [...] all uses of 3657 // template parameters [...] are replaced with the corresponding deduced 3658 // or default argument values. 3659 // [...] If the function template has associated constraints 3660 // ([temp.constr.decl]), those constraints are checked for satisfaction 3661 // ([temp.constr.constr]). If the constraints are not satisfied, type 3662 // deduction fails. 3663 if (!PartialOverloading || 3664 (CanonicalBuilder.size() == 3665 FunctionTemplate->getTemplateParameters()->size())) { 3666 if (CheckInstantiatedFunctionTemplateConstraints( 3667 Info.getLocation(), Specialization, CanonicalBuilder, 3668 Info.AssociatedConstraintsSatisfaction)) 3669 return TDK_MiscellaneousDeductionFailure; 3670 3671 if (!Info.AssociatedConstraintsSatisfaction.IsSatisfied) { 3672 Info.reset(Info.takeSugared(), 3673 TemplateArgumentList::CreateCopy(Context, CanonicalBuilder)); 3674 return TDK_ConstraintsNotSatisfied; 3675 } 3676 } 3677 3678 if (OriginalCallArgs) { 3679 // C++ [temp.deduct.call]p4: 3680 // In general, the deduction process attempts to find template argument 3681 // values that will make the deduced A identical to A (after the type A 3682 // is transformed as described above). [...] 3683 llvm::SmallDenseMap<std::pair<unsigned, QualType>, QualType> DeducedATypes; 3684 for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) { 3685 OriginalCallArg OriginalArg = (*OriginalCallArgs)[I]; 3686 3687 auto ParamIdx = OriginalArg.ArgIdx; 3688 if (ParamIdx >= Specialization->getNumParams()) 3689 // FIXME: This presumably means a pack ended up smaller than we 3690 // expected while deducing. Should this not result in deduction 3691 // failure? Can it even happen? 3692 continue; 3693 3694 QualType DeducedA; 3695 if (!OriginalArg.DecomposedParam) { 3696 // P is one of the function parameters, just look up its substituted 3697 // type. 3698 DeducedA = Specialization->getParamDecl(ParamIdx)->getType(); 3699 } else { 3700 // P is a decomposed element of a parameter corresponding to a 3701 // braced-init-list argument. Substitute back into P to find the 3702 // deduced A. 3703 QualType &CacheEntry = 3704 DeducedATypes[{ParamIdx, OriginalArg.OriginalParamType}]; 3705 if (CacheEntry.isNull()) { 3706 ArgumentPackSubstitutionIndexRAII PackIndex( 3707 *this, getPackIndexForParam(*this, FunctionTemplate, SubstArgs, 3708 ParamIdx)); 3709 CacheEntry = 3710 SubstType(OriginalArg.OriginalParamType, SubstArgs, 3711 Specialization->getTypeSpecStartLoc(), 3712 Specialization->getDeclName()); 3713 } 3714 DeducedA = CacheEntry; 3715 } 3716 3717 if (auto TDK = 3718 CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA)) 3719 return TDK; 3720 } 3721 } 3722 3723 // If we suppressed any diagnostics while performing template argument 3724 // deduction, and if we haven't already instantiated this declaration, 3725 // keep track of these diagnostics. They'll be emitted if this specialization 3726 // is actually used. 3727 if (Info.diag_begin() != Info.diag_end()) { 3728 SuppressedDiagnosticsMap::iterator 3729 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl()); 3730 if (Pos == SuppressedDiagnostics.end()) 3731 SuppressedDiagnostics[Specialization->getCanonicalDecl()] 3732 .append(Info.diag_begin(), Info.diag_end()); 3733 } 3734 3735 return TDK_Success; 3736 } 3737 3738 /// Gets the type of a function for template-argument-deducton 3739 /// purposes when it's considered as part of an overload set. 3740 static QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R, 3741 FunctionDecl *Fn) { 3742 // We may need to deduce the return type of the function now. 3743 if (S.getLangOpts().CPlusPlus14 && Fn->getReturnType()->isUndeducedType() && 3744 S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/ false)) 3745 return {}; 3746 3747 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn)) 3748 if (Method->isInstance()) { 3749 // An instance method that's referenced in a form that doesn't 3750 // look like a member pointer is just invalid. 3751 if (!R.HasFormOfMemberPointer) 3752 return {}; 3753 3754 return S.Context.getMemberPointerType(Fn->getType(), 3755 S.Context.getTypeDeclType(Method->getParent()).getTypePtr()); 3756 } 3757 3758 if (!R.IsAddressOfOperand) return Fn->getType(); 3759 return S.Context.getPointerType(Fn->getType()); 3760 } 3761 3762 /// Apply the deduction rules for overload sets. 3763 /// 3764 /// \return the null type if this argument should be treated as an 3765 /// undeduced context 3766 static QualType 3767 ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams, 3768 Expr *Arg, QualType ParamType, 3769 bool ParamWasReference, 3770 TemplateSpecCandidateSet *FailedTSC = nullptr) { 3771 3772 OverloadExpr::FindResult R = OverloadExpr::find(Arg); 3773 3774 OverloadExpr *Ovl = R.Expression; 3775 3776 // C++0x [temp.deduct.call]p4 3777 unsigned TDF = 0; 3778 if (ParamWasReference) 3779 TDF |= TDF_ParamWithReferenceType; 3780 if (R.IsAddressOfOperand) 3781 TDF |= TDF_IgnoreQualifiers; 3782 3783 // C++0x [temp.deduct.call]p6: 3784 // When P is a function type, pointer to function type, or pointer 3785 // to member function type: 3786 3787 if (!ParamType->isFunctionType() && 3788 !ParamType->isFunctionPointerType() && 3789 !ParamType->isMemberFunctionPointerType()) { 3790 if (Ovl->hasExplicitTemplateArgs()) { 3791 // But we can still look for an explicit specialization. 3792 if (FunctionDecl *ExplicitSpec = 3793 S.ResolveSingleFunctionTemplateSpecialization( 3794 Ovl, /*Complain=*/false, 3795 /*FoundDeclAccessPair=*/nullptr, FailedTSC)) 3796 return GetTypeOfFunction(S, R, ExplicitSpec); 3797 } 3798 3799 DeclAccessPair DAP; 3800 if (FunctionDecl *Viable = 3801 S.resolveAddressOfSingleOverloadCandidate(Arg, DAP)) 3802 return GetTypeOfFunction(S, R, Viable); 3803 3804 return {}; 3805 } 3806 3807 // Gather the explicit template arguments, if any. 3808 TemplateArgumentListInfo ExplicitTemplateArgs; 3809 if (Ovl->hasExplicitTemplateArgs()) 3810 Ovl->copyTemplateArgumentsInto(ExplicitTemplateArgs); 3811 QualType Match; 3812 for (UnresolvedSetIterator I = Ovl->decls_begin(), 3813 E = Ovl->decls_end(); I != E; ++I) { 3814 NamedDecl *D = (*I)->getUnderlyingDecl(); 3815 3816 if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) { 3817 // - If the argument is an overload set containing one or more 3818 // function templates, the parameter is treated as a 3819 // non-deduced context. 3820 if (!Ovl->hasExplicitTemplateArgs()) 3821 return {}; 3822 3823 // Otherwise, see if we can resolve a function type 3824 FunctionDecl *Specialization = nullptr; 3825 TemplateDeductionInfo Info(Ovl->getNameLoc()); 3826 if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs, 3827 Specialization, Info)) 3828 continue; 3829 3830 D = Specialization; 3831 } 3832 3833 FunctionDecl *Fn = cast<FunctionDecl>(D); 3834 QualType ArgType = GetTypeOfFunction(S, R, Fn); 3835 if (ArgType.isNull()) continue; 3836 3837 // Function-to-pointer conversion. 3838 if (!ParamWasReference && ParamType->isPointerType() && 3839 ArgType->isFunctionType()) 3840 ArgType = S.Context.getPointerType(ArgType); 3841 3842 // - If the argument is an overload set (not containing function 3843 // templates), trial argument deduction is attempted using each 3844 // of the members of the set. If deduction succeeds for only one 3845 // of the overload set members, that member is used as the 3846 // argument value for the deduction. If deduction succeeds for 3847 // more than one member of the overload set the parameter is 3848 // treated as a non-deduced context. 3849 3850 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2: 3851 // Type deduction is done independently for each P/A pair, and 3852 // the deduced template argument values are then combined. 3853 // So we do not reject deductions which were made elsewhere. 3854 SmallVector<DeducedTemplateArgument, 8> 3855 Deduced(TemplateParams->size()); 3856 TemplateDeductionInfo Info(Ovl->getNameLoc()); 3857 Sema::TemplateDeductionResult Result 3858 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType, 3859 ArgType, Info, Deduced, TDF); 3860 if (Result) continue; 3861 if (!Match.isNull()) 3862 return {}; 3863 Match = ArgType; 3864 } 3865 3866 return Match; 3867 } 3868 3869 /// Perform the adjustments to the parameter and argument types 3870 /// described in C++ [temp.deduct.call]. 3871 /// 3872 /// \returns true if the caller should not attempt to perform any template 3873 /// argument deduction based on this P/A pair because the argument is an 3874 /// overloaded function set that could not be resolved. 3875 static bool AdjustFunctionParmAndArgTypesForDeduction( 3876 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex, 3877 QualType &ParamType, QualType &ArgType, Expr *Arg, unsigned &TDF, 3878 TemplateSpecCandidateSet *FailedTSC = nullptr) { 3879 // C++0x [temp.deduct.call]p3: 3880 // If P is a cv-qualified type, the top level cv-qualifiers of P's type 3881 // are ignored for type deduction. 3882 if (ParamType.hasQualifiers()) 3883 ParamType = ParamType.getUnqualifiedType(); 3884 3885 // [...] If P is a reference type, the type referred to by P is 3886 // used for type deduction. 3887 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>(); 3888 if (ParamRefType) 3889 ParamType = ParamRefType->getPointeeType(); 3890 3891 // Overload sets usually make this parameter an undeduced context, 3892 // but there are sometimes special circumstances. Typically 3893 // involving a template-id-expr. 3894 if (ArgType == S.Context.OverloadTy) { 3895 ArgType = ResolveOverloadForDeduction(S, TemplateParams, Arg, ParamType, 3896 ParamRefType != nullptr, FailedTSC); 3897 if (ArgType.isNull()) 3898 return true; 3899 } 3900 3901 if (ParamRefType) { 3902 // If the argument has incomplete array type, try to complete its type. 3903 if (ArgType->isIncompleteArrayType()) 3904 ArgType = S.getCompletedType(Arg); 3905 3906 // C++1z [temp.deduct.call]p3: 3907 // If P is a forwarding reference and the argument is an lvalue, the type 3908 // "lvalue reference to A" is used in place of A for type deduction. 3909 if (isForwardingReference(QualType(ParamRefType, 0), FirstInnerIndex) && 3910 Arg->isLValue()) { 3911 if (S.getLangOpts().OpenCL && !ArgType.hasAddressSpace()) 3912 ArgType = S.Context.getAddrSpaceQualType( 3913 ArgType, S.Context.getDefaultOpenCLPointeeAddrSpace()); 3914 ArgType = S.Context.getLValueReferenceType(ArgType); 3915 } 3916 } else { 3917 // C++ [temp.deduct.call]p2: 3918 // If P is not a reference type: 3919 // - If A is an array type, the pointer type produced by the 3920 // array-to-pointer standard conversion (4.2) is used in place of 3921 // A for type deduction; otherwise, 3922 // - If A is a function type, the pointer type produced by the 3923 // function-to-pointer standard conversion (4.3) is used in place 3924 // of A for type deduction; otherwise, 3925 if (ArgType->canDecayToPointerType()) 3926 ArgType = S.Context.getDecayedType(ArgType); 3927 else { 3928 // - If A is a cv-qualified type, the top level cv-qualifiers of A's 3929 // type are ignored for type deduction. 3930 ArgType = ArgType.getUnqualifiedType(); 3931 } 3932 } 3933 3934 // C++0x [temp.deduct.call]p4: 3935 // In general, the deduction process attempts to find template argument 3936 // values that will make the deduced A identical to A (after the type A 3937 // is transformed as described above). [...] 3938 TDF = TDF_SkipNonDependent; 3939 3940 // - If the original P is a reference type, the deduced A (i.e., the 3941 // type referred to by the reference) can be more cv-qualified than 3942 // the transformed A. 3943 if (ParamRefType) 3944 TDF |= TDF_ParamWithReferenceType; 3945 // - The transformed A can be another pointer or pointer to member 3946 // type that can be converted to the deduced A via a qualification 3947 // conversion (4.4). 3948 if (ArgType->isPointerType() || ArgType->isMemberPointerType() || 3949 ArgType->isObjCObjectPointerType()) 3950 TDF |= TDF_IgnoreQualifiers; 3951 // - If P is a class and P has the form simple-template-id, then the 3952 // transformed A can be a derived class of the deduced A. Likewise, 3953 // if P is a pointer to a class of the form simple-template-id, the 3954 // transformed A can be a pointer to a derived class pointed to by 3955 // the deduced A. 3956 if (isSimpleTemplateIdType(ParamType) || 3957 (isa<PointerType>(ParamType) && 3958 isSimpleTemplateIdType( 3959 ParamType->castAs<PointerType>()->getPointeeType()))) 3960 TDF |= TDF_DerivedClass; 3961 3962 return false; 3963 } 3964 3965 static bool 3966 hasDeducibleTemplateParameters(Sema &S, FunctionTemplateDecl *FunctionTemplate, 3967 QualType T); 3968 3969 static Sema::TemplateDeductionResult DeduceTemplateArgumentsFromCallArgument( 3970 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex, 3971 QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info, 3972 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 3973 SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs, 3974 bool DecomposedParam, unsigned ArgIdx, unsigned TDF, 3975 TemplateSpecCandidateSet *FailedTSC = nullptr); 3976 3977 /// Attempt template argument deduction from an initializer list 3978 /// deemed to be an argument in a function call. 3979 static Sema::TemplateDeductionResult DeduceFromInitializerList( 3980 Sema &S, TemplateParameterList *TemplateParams, QualType AdjustedParamType, 3981 InitListExpr *ILE, TemplateDeductionInfo &Info, 3982 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 3983 SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs, unsigned ArgIdx, 3984 unsigned TDF) { 3985 // C++ [temp.deduct.call]p1: (CWG 1591) 3986 // If removing references and cv-qualifiers from P gives 3987 // std::initializer_list<P0> or P0[N] for some P0 and N and the argument is 3988 // a non-empty initializer list, then deduction is performed instead for 3989 // each element of the initializer list, taking P0 as a function template 3990 // parameter type and the initializer element as its argument 3991 // 3992 // We've already removed references and cv-qualifiers here. 3993 if (!ILE->getNumInits()) 3994 return Sema::TDK_Success; 3995 3996 QualType ElTy; 3997 auto *ArrTy = S.Context.getAsArrayType(AdjustedParamType); 3998 if (ArrTy) 3999 ElTy = ArrTy->getElementType(); 4000 else if (!S.isStdInitializerList(AdjustedParamType, &ElTy)) { 4001 // Otherwise, an initializer list argument causes the parameter to be 4002 // considered a non-deduced context 4003 return Sema::TDK_Success; 4004 } 4005 4006 // Resolving a core issue: a braced-init-list containing any designators is 4007 // a non-deduced context. 4008 for (Expr *E : ILE->inits()) 4009 if (isa<DesignatedInitExpr>(E)) 4010 return Sema::TDK_Success; 4011 4012 // Deduction only needs to be done for dependent types. 4013 if (ElTy->isDependentType()) { 4014 for (Expr *E : ILE->inits()) { 4015 if (auto Result = DeduceTemplateArgumentsFromCallArgument( 4016 S, TemplateParams, 0, ElTy, E, Info, Deduced, OriginalCallArgs, true, 4017 ArgIdx, TDF)) 4018 return Result; 4019 } 4020 } 4021 4022 // in the P0[N] case, if N is a non-type template parameter, N is deduced 4023 // from the length of the initializer list. 4024 if (auto *DependentArrTy = dyn_cast_or_null<DependentSizedArrayType>(ArrTy)) { 4025 // Determine the array bound is something we can deduce. 4026 if (const NonTypeTemplateParmDecl *NTTP = 4027 getDeducedParameterFromExpr(Info, DependentArrTy->getSizeExpr())) { 4028 // We can perform template argument deduction for the given non-type 4029 // template parameter. 4030 // C++ [temp.deduct.type]p13: 4031 // The type of N in the type T[N] is std::size_t. 4032 QualType T = S.Context.getSizeType(); 4033 llvm::APInt Size(S.Context.getIntWidth(T), ILE->getNumInits()); 4034 if (auto Result = DeduceNonTypeTemplateArgument( 4035 S, TemplateParams, NTTP, llvm::APSInt(Size), T, 4036 /*ArrayBound=*/true, Info, Deduced)) 4037 return Result; 4038 } 4039 } 4040 4041 return Sema::TDK_Success; 4042 } 4043 4044 /// Perform template argument deduction per [temp.deduct.call] for a 4045 /// single parameter / argument pair. 4046 static Sema::TemplateDeductionResult DeduceTemplateArgumentsFromCallArgument( 4047 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex, 4048 QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info, 4049 SmallVectorImpl<DeducedTemplateArgument> &Deduced, 4050 SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs, 4051 bool DecomposedParam, unsigned ArgIdx, unsigned TDF, 4052 TemplateSpecCandidateSet *FailedTSC) { 4053 QualType ArgType = Arg->getType(); 4054 QualType OrigParamType = ParamType; 4055 4056 // If P is a reference type [...] 4057 // If P is a cv-qualified type [...] 4058 if (AdjustFunctionParmAndArgTypesForDeduction(S, TemplateParams, 4059 FirstInnerIndex, ParamType, 4060 ArgType, Arg, TDF, FailedTSC)) 4061 return Sema::TDK_Success; 4062 4063 // If [...] the argument is a non-empty initializer list [...] 4064 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) 4065 return DeduceFromInitializerList(S, TemplateParams, ParamType, ILE, Info, 4066 Deduced, OriginalCallArgs, ArgIdx, TDF); 4067 4068 // [...] the deduction process attempts to find template argument values 4069 // that will make the deduced A identical to A 4070 // 4071 // Keep track of the argument type and corresponding parameter index, 4072 // so we can check for compatibility between the deduced A and A. 4073 OriginalCallArgs.push_back( 4074 Sema::OriginalCallArg(OrigParamType, DecomposedParam, ArgIdx, ArgType)); 4075 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType, 4076 ArgType, Info, Deduced, TDF); 4077 } 4078 4079 /// Perform template argument deduction from a function call 4080 /// (C++ [temp.deduct.call]). 4081 /// 4082 /// \param FunctionTemplate the function template for which we are performing 4083 /// template argument deduction. 4084 /// 4085 /// \param ExplicitTemplateArgs the explicit template arguments provided 4086 /// for this call. 4087 /// 4088 /// \param Args the function call arguments 4089 /// 4090 /// \param Specialization if template argument deduction was successful, 4091 /// this will be set to the function template specialization produced by 4092 /// template argument deduction. 4093 /// 4094 /// \param Info the argument will be updated to provide additional information 4095 /// about template argument deduction. 4096 /// 4097 /// \param CheckNonDependent A callback to invoke to check conversions for 4098 /// non-dependent parameters, between deduction and substitution, per DR1391. 4099 /// If this returns true, substitution will be skipped and we return 4100 /// TDK_NonDependentConversionFailure. The callback is passed the parameter 4101 /// types (after substituting explicit template arguments). 4102 /// 4103 /// \returns the result of template argument deduction. 4104 Sema::TemplateDeductionResult Sema::DeduceTemplateArguments( 4105 FunctionTemplateDecl *FunctionTemplate, 4106 TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args, 4107 FunctionDecl *&Specialization, TemplateDeductionInfo &Info, 4108 bool PartialOverloading, bool AggregateDeductionCandidate, 4109 llvm::function_ref<bool(ArrayRef<QualType>)> CheckNonDependent) { 4110 if (FunctionTemplate->isInvalidDecl()) 4111 return TDK_Invalid; 4112 4113 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 4114 unsigned NumParams = Function->getNumParams(); 4115 4116 unsigned FirstInnerIndex = getFirstInnerIndex(FunctionTemplate); 4117 4118 // C++ [temp.deduct.call]p1: 4119 // Template argument deduction is done by comparing each function template 4120 // parameter type (call it P) with the type of the corresponding argument 4121 // of the call (call it A) as described below. 4122 if (Args.size() < Function->getMinRequiredArguments() && !PartialOverloading) 4123 return TDK_TooFewArguments; 4124 else if (TooManyArguments(NumParams, Args.size(), PartialOverloading)) { 4125 const auto *Proto = Function->getType()->castAs<FunctionProtoType>(); 4126 if (Proto->isTemplateVariadic()) 4127 /* Do nothing */; 4128 else if (!Proto->isVariadic()) 4129 return TDK_TooManyArguments; 4130 } 4131 4132 // The types of the parameters from which we will perform template argument 4133 // deduction. 4134 LocalInstantiationScope InstScope(*this); 4135 TemplateParameterList *TemplateParams 4136 = FunctionTemplate->getTemplateParameters(); 4137 SmallVector<DeducedTemplateArgument, 4> Deduced; 4138 SmallVector<QualType, 8> ParamTypes; 4139 unsigned NumExplicitlySpecified = 0; 4140 if (ExplicitTemplateArgs) { 4141 TemplateDeductionResult Result; 4142 runWithSufficientStackSpace(Info.getLocation(), [&] { 4143 Result = SubstituteExplicitTemplateArguments( 4144 FunctionTemplate, *ExplicitTemplateArgs, Deduced, ParamTypes, nullptr, 4145 Info); 4146 }); 4147 if (Result) 4148 return Result; 4149 4150 NumExplicitlySpecified = Deduced.size(); 4151 } else { 4152 // Just fill in the parameter types from the function declaration. 4153 for (unsigned I = 0; I != NumParams; ++I) 4154 ParamTypes.push_back(Function->getParamDecl(I)->getType()); 4155 } 4156 4157 SmallVector<OriginalCallArg, 8> OriginalCallArgs; 4158 4159 // Deduce an argument of type ParamType from an expression with index ArgIdx. 4160 auto DeduceCallArgument = [&](QualType ParamType, unsigned ArgIdx) { 4161 // C++ [demp.deduct.call]p1: (DR1391) 4162 // Template argument deduction is done by comparing each function template 4163 // parameter that contains template-parameters that participate in 4164 // template argument deduction ... 4165 if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType)) 4166 return Sema::TDK_Success; 4167 4168 // ... with the type of the corresponding argument 4169 return DeduceTemplateArgumentsFromCallArgument( 4170 *this, TemplateParams, FirstInnerIndex, ParamType, Args[ArgIdx], Info, Deduced, 4171 OriginalCallArgs, /*Decomposed*/false, ArgIdx, /*TDF*/ 0); 4172 }; 4173 4174 // Deduce template arguments from the function parameters. 4175 Deduced.resize(TemplateParams->size()); 4176 SmallVector<QualType, 8> ParamTypesForArgChecking; 4177 for (unsigned ParamIdx = 0, NumParamTypes = ParamTypes.size(), ArgIdx = 0; 4178 ParamIdx != NumParamTypes; ++ParamIdx) { 4179 QualType ParamType = ParamTypes[ParamIdx]; 4180 4181 const PackExpansionType *ParamExpansion = 4182 dyn_cast<PackExpansionType>(ParamType); 4183 if (!ParamExpansion) { 4184 // Simple case: matching a function parameter to a function argument. 4185 if (ArgIdx >= Args.size()) 4186 break; 4187 4188 ParamTypesForArgChecking.push_back(ParamType); 4189 if (auto Result = DeduceCallArgument(ParamType, ArgIdx++)) 4190 return Result; 4191 4192 continue; 4193 } 4194 4195 bool IsTrailingPack = ParamIdx + 1 == NumParamTypes; 4196 4197 QualType ParamPattern = ParamExpansion->getPattern(); 4198 PackDeductionScope PackScope(*this, TemplateParams, Deduced, Info, 4199 ParamPattern, 4200 AggregateDeductionCandidate && IsTrailingPack); 4201 4202 // C++0x [temp.deduct.call]p1: 4203 // For a function parameter pack that occurs at the end of the 4204 // parameter-declaration-list, the type A of each remaining argument of 4205 // the call is compared with the type P of the declarator-id of the 4206 // function parameter pack. Each comparison deduces template arguments 4207 // for subsequent positions in the template parameter packs expanded by 4208 // the function parameter pack. When a function parameter pack appears 4209 // in a non-deduced context [not at the end of the list], the type of 4210 // that parameter pack is never deduced. 4211 // 4212 // FIXME: The above rule allows the size of the parameter pack to change 4213 // after we skip it (in the non-deduced case). That makes no sense, so 4214 // we instead notionally deduce the pack against N arguments, where N is 4215 // the length of the explicitly-specified pack if it's expanded by the 4216 // parameter pack and 0 otherwise, and we treat each deduction as a 4217 // non-deduced context. 4218 if (IsTrailingPack || PackScope.hasFixedArity()) { 4219 for (; ArgIdx < Args.size() && PackScope.hasNextElement(); 4220 PackScope.nextPackElement(), ++ArgIdx) { 4221 ParamTypesForArgChecking.push_back(ParamPattern); 4222 if (auto Result = DeduceCallArgument(ParamPattern, ArgIdx)) 4223 return Result; 4224 } 4225 } else { 4226 // If the parameter type contains an explicitly-specified pack that we 4227 // could not expand, skip the number of parameters notionally created 4228 // by the expansion. 4229 std::optional<unsigned> NumExpansions = 4230 ParamExpansion->getNumExpansions(); 4231 if (NumExpansions && !PackScope.isPartiallyExpanded()) { 4232 for (unsigned I = 0; I != *NumExpansions && ArgIdx < Args.size(); 4233 ++I, ++ArgIdx) { 4234 ParamTypesForArgChecking.push_back(ParamPattern); 4235 // FIXME: Should we add OriginalCallArgs for these? What if the 4236 // corresponding argument is a list? 4237 PackScope.nextPackElement(); 4238 } 4239 } 4240 } 4241 4242 // Build argument packs for each of the parameter packs expanded by this 4243 // pack expansion. 4244 if (auto Result = PackScope.finish()) 4245 return Result; 4246 } 4247 4248 // Capture the context in which the function call is made. This is the context 4249 // that is needed when the accessibility of template arguments is checked. 4250 DeclContext *CallingCtx = CurContext; 4251 4252 TemplateDeductionResult Result; 4253 runWithSufficientStackSpace(Info.getLocation(), [&] { 4254 Result = FinishTemplateArgumentDeduction( 4255 FunctionTemplate, Deduced, NumExplicitlySpecified, Specialization, Info, 4256 &OriginalCallArgs, PartialOverloading, [&, CallingCtx]() { 4257 ContextRAII SavedContext(*this, CallingCtx); 4258 return CheckNonDependent(ParamTypesForArgChecking); 4259 }); 4260 }); 4261 return Result; 4262 } 4263 4264 QualType Sema::adjustCCAndNoReturn(QualType ArgFunctionType, 4265 QualType FunctionType, 4266 bool AdjustExceptionSpec) { 4267 if (ArgFunctionType.isNull()) 4268 return ArgFunctionType; 4269 4270 const auto *FunctionTypeP = FunctionType->castAs<FunctionProtoType>(); 4271 const auto *ArgFunctionTypeP = ArgFunctionType->castAs<FunctionProtoType>(); 4272 FunctionProtoType::ExtProtoInfo EPI = ArgFunctionTypeP->getExtProtoInfo(); 4273 bool Rebuild = false; 4274 4275 CallingConv CC = FunctionTypeP->getCallConv(); 4276 if (EPI.ExtInfo.getCC() != CC) { 4277 EPI.ExtInfo = EPI.ExtInfo.withCallingConv(CC); 4278 Rebuild = true; 4279 } 4280 4281 bool NoReturn = FunctionTypeP->getNoReturnAttr(); 4282 if (EPI.ExtInfo.getNoReturn() != NoReturn) { 4283 EPI.ExtInfo = EPI.ExtInfo.withNoReturn(NoReturn); 4284 Rebuild = true; 4285 } 4286 4287 if (AdjustExceptionSpec && (FunctionTypeP->hasExceptionSpec() || 4288 ArgFunctionTypeP->hasExceptionSpec())) { 4289 EPI.ExceptionSpec = FunctionTypeP->getExtProtoInfo().ExceptionSpec; 4290 Rebuild = true; 4291 } 4292 4293 if (!Rebuild) 4294 return ArgFunctionType; 4295 4296 return Context.getFunctionType(ArgFunctionTypeP->getReturnType(), 4297 ArgFunctionTypeP->getParamTypes(), EPI); 4298 } 4299 4300 /// Deduce template arguments when taking the address of a function 4301 /// template (C++ [temp.deduct.funcaddr]) or matching a specialization to 4302 /// a template. 4303 /// 4304 /// \param FunctionTemplate the function template for which we are performing 4305 /// template argument deduction. 4306 /// 4307 /// \param ExplicitTemplateArgs the explicitly-specified template 4308 /// arguments. 4309 /// 4310 /// \param ArgFunctionType the function type that will be used as the 4311 /// "argument" type (A) when performing template argument deduction from the 4312 /// function template's function type. This type may be NULL, if there is no 4313 /// argument type to compare against, in C++0x [temp.arg.explicit]p3. 4314 /// 4315 /// \param Specialization if template argument deduction was successful, 4316 /// this will be set to the function template specialization produced by 4317 /// template argument deduction. 4318 /// 4319 /// \param Info the argument will be updated to provide additional information 4320 /// about template argument deduction. 4321 /// 4322 /// \param IsAddressOfFunction If \c true, we are deducing as part of taking 4323 /// the address of a function template per [temp.deduct.funcaddr] and 4324 /// [over.over]. If \c false, we are looking up a function template 4325 /// specialization based on its signature, per [temp.deduct.decl]. 4326 /// 4327 /// \returns the result of template argument deduction. 4328 Sema::TemplateDeductionResult Sema::DeduceTemplateArguments( 4329 FunctionTemplateDecl *FunctionTemplate, 4330 TemplateArgumentListInfo *ExplicitTemplateArgs, QualType ArgFunctionType, 4331 FunctionDecl *&Specialization, TemplateDeductionInfo &Info, 4332 bool IsAddressOfFunction) { 4333 if (FunctionTemplate->isInvalidDecl()) 4334 return TDK_Invalid; 4335 4336 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 4337 TemplateParameterList *TemplateParams 4338 = FunctionTemplate->getTemplateParameters(); 4339 QualType FunctionType = Function->getType(); 4340 4341 // Substitute any explicit template arguments. 4342 LocalInstantiationScope InstScope(*this); 4343 SmallVector<DeducedTemplateArgument, 4> Deduced; 4344 unsigned NumExplicitlySpecified = 0; 4345 SmallVector<QualType, 4> ParamTypes; 4346 if (ExplicitTemplateArgs) { 4347 TemplateDeductionResult Result; 4348 runWithSufficientStackSpace(Info.getLocation(), [&] { 4349 Result = SubstituteExplicitTemplateArguments( 4350 FunctionTemplate, *ExplicitTemplateArgs, Deduced, ParamTypes, 4351 &FunctionType, Info); 4352 }); 4353 if (Result) 4354 return Result; 4355 4356 NumExplicitlySpecified = Deduced.size(); 4357 } 4358 4359 // When taking the address of a function, we require convertibility of 4360 // the resulting function type. Otherwise, we allow arbitrary mismatches 4361 // of calling convention and noreturn. 4362 if (!IsAddressOfFunction) 4363 ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, FunctionType, 4364 /*AdjustExceptionSpec*/false); 4365 4366 // Unevaluated SFINAE context. 4367 EnterExpressionEvaluationContext Unevaluated( 4368 *this, Sema::ExpressionEvaluationContext::Unevaluated); 4369 SFINAETrap Trap(*this); 4370 4371 Deduced.resize(TemplateParams->size()); 4372 4373 // If the function has a deduced return type, substitute it for a dependent 4374 // type so that we treat it as a non-deduced context in what follows. 4375 bool HasDeducedReturnType = false; 4376 if (getLangOpts().CPlusPlus14 && 4377 Function->getReturnType()->getContainedAutoType()) { 4378 FunctionType = SubstAutoTypeDependent(FunctionType); 4379 HasDeducedReturnType = true; 4380 } 4381 4382 if (!ArgFunctionType.isNull() && !FunctionType.isNull()) { 4383 unsigned TDF = 4384 TDF_TopLevelParameterTypeList | TDF_AllowCompatibleFunctionType; 4385 // Deduce template arguments from the function type. 4386 if (TemplateDeductionResult Result 4387 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 4388 FunctionType, ArgFunctionType, 4389 Info, Deduced, TDF)) 4390 return Result; 4391 } 4392 4393 TemplateDeductionResult Result; 4394 runWithSufficientStackSpace(Info.getLocation(), [&] { 4395 Result = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 4396 NumExplicitlySpecified, 4397 Specialization, Info); 4398 }); 4399 if (Result) 4400 return Result; 4401 4402 // If the function has a deduced return type, deduce it now, so we can check 4403 // that the deduced function type matches the requested type. 4404 if (HasDeducedReturnType && IsAddressOfFunction && 4405 Specialization->getReturnType()->isUndeducedType() && 4406 DeduceReturnType(Specialization, Info.getLocation(), false)) 4407 return TDK_MiscellaneousDeductionFailure; 4408 4409 if (IsAddressOfFunction && getLangOpts().CPlusPlus20 && 4410 Specialization->isImmediateEscalating() && 4411 CheckIfFunctionSpecializationIsImmediate(Specialization, 4412 Info.getLocation())) 4413 return TDK_MiscellaneousDeductionFailure; 4414 4415 // If the function has a dependent exception specification, resolve it now, 4416 // so we can check that the exception specification matches. 4417 auto *SpecializationFPT = 4418 Specialization->getType()->castAs<FunctionProtoType>(); 4419 if (getLangOpts().CPlusPlus17 && 4420 isUnresolvedExceptionSpec(SpecializationFPT->getExceptionSpecType()) && 4421 !ResolveExceptionSpec(Info.getLocation(), SpecializationFPT)) 4422 return TDK_MiscellaneousDeductionFailure; 4423 4424 // Adjust the exception specification of the argument to match the 4425 // substituted and resolved type we just formed. (Calling convention and 4426 // noreturn can't be dependent, so we don't actually need this for them 4427 // right now.) 4428 QualType SpecializationType = Specialization->getType(); 4429 if (!IsAddressOfFunction) { 4430 ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, SpecializationType, 4431 /*AdjustExceptionSpec*/true); 4432 4433 // Revert placeholder types in the return type back to undeduced types so 4434 // that the comparison below compares the declared return types. 4435 if (HasDeducedReturnType) { 4436 SpecializationType = SubstAutoType(SpecializationType, QualType()); 4437 ArgFunctionType = SubstAutoType(ArgFunctionType, QualType()); 4438 } 4439 } 4440 4441 // If the requested function type does not match the actual type of the 4442 // specialization with respect to arguments of compatible pointer to function 4443 // types, template argument deduction fails. 4444 if (!ArgFunctionType.isNull()) { 4445 if (IsAddressOfFunction 4446 ? !isSameOrCompatibleFunctionType( 4447 Context.getCanonicalType(SpecializationType), 4448 Context.getCanonicalType(ArgFunctionType)) 4449 : !Context.hasSameType(SpecializationType, ArgFunctionType)) { 4450 Info.FirstArg = TemplateArgument(SpecializationType); 4451 Info.SecondArg = TemplateArgument(ArgFunctionType); 4452 return TDK_NonDeducedMismatch; 4453 } 4454 } 4455 4456 return TDK_Success; 4457 } 4458 4459 /// Deduce template arguments for a templated conversion 4460 /// function (C++ [temp.deduct.conv]) and, if successful, produce a 4461 /// conversion function template specialization. 4462 Sema::TemplateDeductionResult 4463 Sema::DeduceTemplateArguments(FunctionTemplateDecl *ConversionTemplate, 4464 QualType ToType, 4465 CXXConversionDecl *&Specialization, 4466 TemplateDeductionInfo &Info) { 4467 if (ConversionTemplate->isInvalidDecl()) 4468 return TDK_Invalid; 4469 4470 CXXConversionDecl *ConversionGeneric 4471 = cast<CXXConversionDecl>(ConversionTemplate->getTemplatedDecl()); 4472 4473 QualType FromType = ConversionGeneric->getConversionType(); 4474 4475 // Canonicalize the types for deduction. 4476 QualType P = Context.getCanonicalType(FromType); 4477 QualType A = Context.getCanonicalType(ToType); 4478 4479 // C++0x [temp.deduct.conv]p2: 4480 // If P is a reference type, the type referred to by P is used for 4481 // type deduction. 4482 if (const ReferenceType *PRef = P->getAs<ReferenceType>()) 4483 P = PRef->getPointeeType(); 4484 4485 // C++0x [temp.deduct.conv]p4: 4486 // [...] If A is a reference type, the type referred to by A is used 4487 // for type deduction. 4488 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) { 4489 A = ARef->getPointeeType(); 4490 // We work around a defect in the standard here: cv-qualifiers are also 4491 // removed from P and A in this case, unless P was a reference type. This 4492 // seems to mostly match what other compilers are doing. 4493 if (!FromType->getAs<ReferenceType>()) { 4494 A = A.getUnqualifiedType(); 4495 P = P.getUnqualifiedType(); 4496 } 4497 4498 // C++ [temp.deduct.conv]p3: 4499 // 4500 // If A is not a reference type: 4501 } else { 4502 assert(!A->isReferenceType() && "Reference types were handled above"); 4503 4504 // - If P is an array type, the pointer type produced by the 4505 // array-to-pointer standard conversion (4.2) is used in place 4506 // of P for type deduction; otherwise, 4507 if (P->isArrayType()) 4508 P = Context.getArrayDecayedType(P); 4509 // - If P is a function type, the pointer type produced by the 4510 // function-to-pointer standard conversion (4.3) is used in 4511 // place of P for type deduction; otherwise, 4512 else if (P->isFunctionType()) 4513 P = Context.getPointerType(P); 4514 // - If P is a cv-qualified type, the top level cv-qualifiers of 4515 // P's type are ignored for type deduction. 4516 else 4517 P = P.getUnqualifiedType(); 4518 4519 // C++0x [temp.deduct.conv]p4: 4520 // If A is a cv-qualified type, the top level cv-qualifiers of A's 4521 // type are ignored for type deduction. If A is a reference type, the type 4522 // referred to by A is used for type deduction. 4523 A = A.getUnqualifiedType(); 4524 } 4525 4526 // Unevaluated SFINAE context. 4527 EnterExpressionEvaluationContext Unevaluated( 4528 *this, Sema::ExpressionEvaluationContext::Unevaluated); 4529 SFINAETrap Trap(*this); 4530 4531 // C++ [temp.deduct.conv]p1: 4532 // Template argument deduction is done by comparing the return 4533 // type of the template conversion function (call it P) with the 4534 // type that is required as the result of the conversion (call it 4535 // A) as described in 14.8.2.4. 4536 TemplateParameterList *TemplateParams 4537 = ConversionTemplate->getTemplateParameters(); 4538 SmallVector<DeducedTemplateArgument, 4> Deduced; 4539 Deduced.resize(TemplateParams->size()); 4540 4541 // C++0x [temp.deduct.conv]p4: 4542 // In general, the deduction process attempts to find template 4543 // argument values that will make the deduced A identical to 4544 // A. However, there are two cases that allow a difference: 4545 unsigned TDF = 0; 4546 // - If the original A is a reference type, A can be more 4547 // cv-qualified than the deduced A (i.e., the type referred to 4548 // by the reference) 4549 if (ToType->isReferenceType()) 4550 TDF |= TDF_ArgWithReferenceType; 4551 // - The deduced A can be another pointer or pointer to member 4552 // type that can be converted to A via a qualification 4553 // conversion. 4554 // 4555 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when 4556 // both P and A are pointers or member pointers. In this case, we 4557 // just ignore cv-qualifiers completely). 4558 if ((P->isPointerType() && A->isPointerType()) || 4559 (P->isMemberPointerType() && A->isMemberPointerType())) 4560 TDF |= TDF_IgnoreQualifiers; 4561 if (TemplateDeductionResult Result 4562 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, 4563 P, A, Info, Deduced, TDF)) 4564 return Result; 4565 4566 // Create an Instantiation Scope for finalizing the operator. 4567 LocalInstantiationScope InstScope(*this); 4568 // Finish template argument deduction. 4569 FunctionDecl *ConversionSpecialized = nullptr; 4570 TemplateDeductionResult Result; 4571 runWithSufficientStackSpace(Info.getLocation(), [&] { 4572 Result = FinishTemplateArgumentDeduction(ConversionTemplate, Deduced, 0, 4573 ConversionSpecialized, Info); 4574 }); 4575 Specialization = cast_or_null<CXXConversionDecl>(ConversionSpecialized); 4576 return Result; 4577 } 4578 4579 /// Deduce template arguments for a function template when there is 4580 /// nothing to deduce against (C++0x [temp.arg.explicit]p3). 4581 /// 4582 /// \param FunctionTemplate the function template for which we are performing 4583 /// template argument deduction. 4584 /// 4585 /// \param ExplicitTemplateArgs the explicitly-specified template 4586 /// arguments. 4587 /// 4588 /// \param Specialization if template argument deduction was successful, 4589 /// this will be set to the function template specialization produced by 4590 /// template argument deduction. 4591 /// 4592 /// \param Info the argument will be updated to provide additional information 4593 /// about template argument deduction. 4594 /// 4595 /// \param IsAddressOfFunction If \c true, we are deducing as part of taking 4596 /// the address of a function template in a context where we do not have a 4597 /// target type, per [over.over]. If \c false, we are looking up a function 4598 /// template specialization based on its signature, which only happens when 4599 /// deducing a function parameter type from an argument that is a template-id 4600 /// naming a function template specialization. 4601 /// 4602 /// \returns the result of template argument deduction. 4603 Sema::TemplateDeductionResult Sema::DeduceTemplateArguments( 4604 FunctionTemplateDecl *FunctionTemplate, 4605 TemplateArgumentListInfo *ExplicitTemplateArgs, 4606 FunctionDecl *&Specialization, TemplateDeductionInfo &Info, 4607 bool IsAddressOfFunction) { 4608 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs, 4609 QualType(), Specialization, Info, 4610 IsAddressOfFunction); 4611 } 4612 4613 namespace { 4614 struct DependentAuto { bool IsPack; }; 4615 4616 /// Substitute the 'auto' specifier or deduced template specialization type 4617 /// specifier within a type for a given replacement type. 4618 class SubstituteDeducedTypeTransform : 4619 public TreeTransform<SubstituteDeducedTypeTransform> { 4620 QualType Replacement; 4621 bool ReplacementIsPack; 4622 bool UseTypeSugar; 4623 4624 public: 4625 SubstituteDeducedTypeTransform(Sema &SemaRef, DependentAuto DA) 4626 : TreeTransform<SubstituteDeducedTypeTransform>(SemaRef), 4627 ReplacementIsPack(DA.IsPack), UseTypeSugar(true) {} 4628 4629 SubstituteDeducedTypeTransform(Sema &SemaRef, QualType Replacement, 4630 bool UseTypeSugar = true) 4631 : TreeTransform<SubstituteDeducedTypeTransform>(SemaRef), 4632 Replacement(Replacement), ReplacementIsPack(false), 4633 UseTypeSugar(UseTypeSugar) {} 4634 4635 QualType TransformDesugared(TypeLocBuilder &TLB, DeducedTypeLoc TL) { 4636 assert(isa<TemplateTypeParmType>(Replacement) && 4637 "unexpected unsugared replacement kind"); 4638 QualType Result = Replacement; 4639 TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result); 4640 NewTL.setNameLoc(TL.getNameLoc()); 4641 return Result; 4642 } 4643 4644 QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) { 4645 // If we're building the type pattern to deduce against, don't wrap the 4646 // substituted type in an AutoType. Certain template deduction rules 4647 // apply only when a template type parameter appears directly (and not if 4648 // the parameter is found through desugaring). For instance: 4649 // auto &&lref = lvalue; 4650 // must transform into "rvalue reference to T" not "rvalue reference to 4651 // auto type deduced as T" in order for [temp.deduct.call]p3 to apply. 4652 // 4653 // FIXME: Is this still necessary? 4654 if (!UseTypeSugar) 4655 return TransformDesugared(TLB, TL); 4656 4657 QualType Result = SemaRef.Context.getAutoType( 4658 Replacement, TL.getTypePtr()->getKeyword(), Replacement.isNull(), 4659 ReplacementIsPack, TL.getTypePtr()->getTypeConstraintConcept(), 4660 TL.getTypePtr()->getTypeConstraintArguments()); 4661 auto NewTL = TLB.push<AutoTypeLoc>(Result); 4662 NewTL.copy(TL); 4663 return Result; 4664 } 4665 4666 QualType TransformDeducedTemplateSpecializationType( 4667 TypeLocBuilder &TLB, DeducedTemplateSpecializationTypeLoc TL) { 4668 if (!UseTypeSugar) 4669 return TransformDesugared(TLB, TL); 4670 4671 QualType Result = SemaRef.Context.getDeducedTemplateSpecializationType( 4672 TL.getTypePtr()->getTemplateName(), 4673 Replacement, Replacement.isNull()); 4674 auto NewTL = TLB.push<DeducedTemplateSpecializationTypeLoc>(Result); 4675 NewTL.setNameLoc(TL.getNameLoc()); 4676 return Result; 4677 } 4678 4679 ExprResult TransformLambdaExpr(LambdaExpr *E) { 4680 // Lambdas never need to be transformed. 4681 return E; 4682 } 4683 4684 QualType Apply(TypeLoc TL) { 4685 // Create some scratch storage for the transformed type locations. 4686 // FIXME: We're just going to throw this information away. Don't build it. 4687 TypeLocBuilder TLB; 4688 TLB.reserve(TL.getFullDataSize()); 4689 return TransformType(TLB, TL); 4690 } 4691 }; 4692 4693 } // namespace 4694 4695 static bool CheckDeducedPlaceholderConstraints(Sema &S, const AutoType &Type, 4696 AutoTypeLoc TypeLoc, 4697 QualType Deduced) { 4698 ConstraintSatisfaction Satisfaction; 4699 ConceptDecl *Concept = Type.getTypeConstraintConcept(); 4700 TemplateArgumentListInfo TemplateArgs(TypeLoc.getLAngleLoc(), 4701 TypeLoc.getRAngleLoc()); 4702 TemplateArgs.addArgument( 4703 TemplateArgumentLoc(TemplateArgument(Deduced), 4704 S.Context.getTrivialTypeSourceInfo( 4705 Deduced, TypeLoc.getNameLoc()))); 4706 for (unsigned I = 0, C = TypeLoc.getNumArgs(); I != C; ++I) 4707 TemplateArgs.addArgument(TypeLoc.getArgLoc(I)); 4708 4709 llvm::SmallVector<TemplateArgument, 4> SugaredConverted, CanonicalConverted; 4710 if (S.CheckTemplateArgumentList(Concept, SourceLocation(), TemplateArgs, 4711 /*PartialTemplateArgs=*/false, 4712 SugaredConverted, CanonicalConverted)) 4713 return true; 4714 MultiLevelTemplateArgumentList MLTAL(Concept, CanonicalConverted, 4715 /*Final=*/false); 4716 if (S.CheckConstraintSatisfaction(Concept, {Concept->getConstraintExpr()}, 4717 MLTAL, TypeLoc.getLocalSourceRange(), 4718 Satisfaction)) 4719 return true; 4720 if (!Satisfaction.IsSatisfied) { 4721 std::string Buf; 4722 llvm::raw_string_ostream OS(Buf); 4723 OS << "'" << Concept->getName(); 4724 if (TypeLoc.hasExplicitTemplateArgs()) { 4725 printTemplateArgumentList( 4726 OS, Type.getTypeConstraintArguments(), S.getPrintingPolicy(), 4727 Type.getTypeConstraintConcept()->getTemplateParameters()); 4728 } 4729 OS << "'"; 4730 OS.flush(); 4731 S.Diag(TypeLoc.getConceptNameLoc(), 4732 diag::err_placeholder_constraints_not_satisfied) 4733 << Deduced << Buf << TypeLoc.getLocalSourceRange(); 4734 S.DiagnoseUnsatisfiedConstraint(Satisfaction); 4735 return true; 4736 } 4737 return false; 4738 } 4739 4740 /// Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6) 4741 /// 4742 /// Note that this is done even if the initializer is dependent. (This is 4743 /// necessary to support partial ordering of templates using 'auto'.) 4744 /// A dependent type will be produced when deducing from a dependent type. 4745 /// 4746 /// \param Type the type pattern using the auto type-specifier. 4747 /// \param Init the initializer for the variable whose type is to be deduced. 4748 /// \param Result if type deduction was successful, this will be set to the 4749 /// deduced type. 4750 /// \param Info the argument will be updated to provide additional information 4751 /// about template argument deduction. 4752 /// \param DependentDeduction Set if we should permit deduction in 4753 /// dependent cases. This is necessary for template partial ordering with 4754 /// 'auto' template parameters. The template parameter depth to be used 4755 /// should be specified in the 'Info' parameter. 4756 /// \param IgnoreConstraints Set if we should not fail if the deduced type does 4757 /// not satisfy the type-constraint in the auto type. 4758 Sema::TemplateDeductionResult 4759 Sema::DeduceAutoType(TypeLoc Type, Expr *Init, QualType &Result, 4760 TemplateDeductionInfo &Info, bool DependentDeduction, 4761 bool IgnoreConstraints, 4762 TemplateSpecCandidateSet *FailedTSC) { 4763 assert(DependentDeduction || Info.getDeducedDepth() == 0); 4764 if (Init->containsErrors()) 4765 return TDK_AlreadyDiagnosed; 4766 4767 const AutoType *AT = Type.getType()->getContainedAutoType(); 4768 assert(AT); 4769 4770 if (Init->getType()->isNonOverloadPlaceholderType() || AT->isDecltypeAuto()) { 4771 ExprResult NonPlaceholder = CheckPlaceholderExpr(Init); 4772 if (NonPlaceholder.isInvalid()) 4773 return TDK_AlreadyDiagnosed; 4774 Init = NonPlaceholder.get(); 4775 } 4776 4777 DependentAuto DependentResult = { 4778 /*.IsPack = */ (bool)Type.getAs<PackExpansionTypeLoc>()}; 4779 4780 if (!DependentDeduction && 4781 (Type.getType()->isDependentType() || Init->isTypeDependent() || 4782 Init->containsUnexpandedParameterPack())) { 4783 Result = SubstituteDeducedTypeTransform(*this, DependentResult).Apply(Type); 4784 assert(!Result.isNull() && "substituting DependentTy can't fail"); 4785 return TDK_Success; 4786 } 4787 4788 auto *InitList = dyn_cast<InitListExpr>(Init); 4789 if (!getLangOpts().CPlusPlus && InitList) { 4790 Diag(Init->getBeginLoc(), diag::err_auto_init_list_from_c); 4791 return TDK_AlreadyDiagnosed; 4792 } 4793 4794 // Deduce type of TemplParam in Func(Init) 4795 SmallVector<DeducedTemplateArgument, 1> Deduced; 4796 Deduced.resize(1); 4797 4798 // If deduction failed, don't diagnose if the initializer is dependent; it 4799 // might acquire a matching type in the instantiation. 4800 auto DeductionFailed = [&](TemplateDeductionResult TDK) { 4801 if (Init->isTypeDependent()) { 4802 Result = 4803 SubstituteDeducedTypeTransform(*this, DependentResult).Apply(Type); 4804 assert(!Result.isNull() && "substituting DependentTy can't fail"); 4805 return TDK_Success; 4806 } 4807 return TDK; 4808 }; 4809 4810 SmallVector<OriginalCallArg, 4> OriginalCallArgs; 4811 4812 QualType DeducedType; 4813 // If this is a 'decltype(auto)' specifier, do the decltype dance. 4814 if (AT->isDecltypeAuto()) { 4815 if (InitList) { 4816 Diag(Init->getBeginLoc(), diag::err_decltype_auto_initializer_list); 4817 return TDK_AlreadyDiagnosed; 4818 } 4819 4820 DeducedType = getDecltypeForExpr(Init); 4821 assert(!DeducedType.isNull()); 4822 } else { 4823 LocalInstantiationScope InstScope(*this); 4824 4825 // Build template<class TemplParam> void Func(FuncParam); 4826 SourceLocation Loc = Init->getExprLoc(); 4827 TemplateTypeParmDecl *TemplParam = TemplateTypeParmDecl::Create( 4828 Context, nullptr, SourceLocation(), Loc, Info.getDeducedDepth(), 0, 4829 nullptr, false, false, false); 4830 QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0); 4831 NamedDecl *TemplParamPtr = TemplParam; 4832 FixedSizeTemplateParameterListStorage<1, false> TemplateParamsSt( 4833 Context, Loc, Loc, TemplParamPtr, Loc, nullptr); 4834 4835 if (InitList) { 4836 // Notionally, we substitute std::initializer_list<T> for 'auto' and 4837 // deduce against that. Such deduction only succeeds if removing 4838 // cv-qualifiers and references results in std::initializer_list<T>. 4839 if (!Type.getType().getNonReferenceType()->getAs<AutoType>()) 4840 return TDK_Invalid; 4841 4842 SourceRange DeducedFromInitRange; 4843 for (Expr *Init : InitList->inits()) { 4844 // Resolving a core issue: a braced-init-list containing any designators 4845 // is a non-deduced context. 4846 if (isa<DesignatedInitExpr>(Init)) 4847 return TDK_Invalid; 4848 if (auto TDK = DeduceTemplateArgumentsFromCallArgument( 4849 *this, TemplateParamsSt.get(), 0, TemplArg, Init, Info, Deduced, 4850 OriginalCallArgs, /*Decomposed=*/true, 4851 /*ArgIdx=*/0, /*TDF=*/0)) { 4852 if (TDK == TDK_Inconsistent) { 4853 Diag(Info.getLocation(), diag::err_auto_inconsistent_deduction) 4854 << Info.FirstArg << Info.SecondArg << DeducedFromInitRange 4855 << Init->getSourceRange(); 4856 return DeductionFailed(TDK_AlreadyDiagnosed); 4857 } 4858 return DeductionFailed(TDK); 4859 } 4860 4861 if (DeducedFromInitRange.isInvalid() && 4862 Deduced[0].getKind() != TemplateArgument::Null) 4863 DeducedFromInitRange = Init->getSourceRange(); 4864 } 4865 } else { 4866 if (!getLangOpts().CPlusPlus && Init->refersToBitField()) { 4867 Diag(Loc, diag::err_auto_bitfield); 4868 return TDK_AlreadyDiagnosed; 4869 } 4870 QualType FuncParam = 4871 SubstituteDeducedTypeTransform(*this, TemplArg).Apply(Type); 4872 assert(!FuncParam.isNull() && 4873 "substituting template parameter for 'auto' failed"); 4874 if (auto TDK = DeduceTemplateArgumentsFromCallArgument( 4875 *this, TemplateParamsSt.get(), 0, FuncParam, Init, Info, Deduced, 4876 OriginalCallArgs, /*Decomposed=*/false, /*ArgIdx=*/0, /*TDF=*/0, 4877 FailedTSC)) 4878 return DeductionFailed(TDK); 4879 } 4880 4881 // Could be null if somehow 'auto' appears in a non-deduced context. 4882 if (Deduced[0].getKind() != TemplateArgument::Type) 4883 return DeductionFailed(TDK_Incomplete); 4884 DeducedType = Deduced[0].getAsType(); 4885 4886 if (InitList) { 4887 DeducedType = BuildStdInitializerList(DeducedType, Loc); 4888 if (DeducedType.isNull()) 4889 return TDK_AlreadyDiagnosed; 4890 } 4891 } 4892 4893 if (!Result.isNull()) { 4894 if (!Context.hasSameType(DeducedType, Result)) { 4895 Info.FirstArg = Result; 4896 Info.SecondArg = DeducedType; 4897 return DeductionFailed(TDK_Inconsistent); 4898 } 4899 DeducedType = Context.getCommonSugaredType(Result, DeducedType); 4900 } 4901 4902 if (AT->isConstrained() && !IgnoreConstraints && 4903 CheckDeducedPlaceholderConstraints( 4904 *this, *AT, Type.getContainedAutoTypeLoc(), DeducedType)) 4905 return TDK_AlreadyDiagnosed; 4906 4907 Result = SubstituteDeducedTypeTransform(*this, DeducedType).Apply(Type); 4908 if (Result.isNull()) 4909 return TDK_AlreadyDiagnosed; 4910 4911 // Check that the deduced argument type is compatible with the original 4912 // argument type per C++ [temp.deduct.call]p4. 4913 QualType DeducedA = InitList ? Deduced[0].getAsType() : Result; 4914 for (const OriginalCallArg &OriginalArg : OriginalCallArgs) { 4915 assert((bool)InitList == OriginalArg.DecomposedParam && 4916 "decomposed non-init-list in auto deduction?"); 4917 if (auto TDK = 4918 CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA)) { 4919 Result = QualType(); 4920 return DeductionFailed(TDK); 4921 } 4922 } 4923 4924 return TDK_Success; 4925 } 4926 4927 QualType Sema::SubstAutoType(QualType TypeWithAuto, 4928 QualType TypeToReplaceAuto) { 4929 assert(TypeToReplaceAuto != Context.DependentTy); 4930 return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto) 4931 .TransformType(TypeWithAuto); 4932 } 4933 4934 TypeSourceInfo *Sema::SubstAutoTypeSourceInfo(TypeSourceInfo *TypeWithAuto, 4935 QualType TypeToReplaceAuto) { 4936 assert(TypeToReplaceAuto != Context.DependentTy); 4937 return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto) 4938 .TransformType(TypeWithAuto); 4939 } 4940 4941 QualType Sema::SubstAutoTypeDependent(QualType TypeWithAuto) { 4942 return SubstituteDeducedTypeTransform(*this, DependentAuto{false}) 4943 .TransformType(TypeWithAuto); 4944 } 4945 4946 TypeSourceInfo * 4947 Sema::SubstAutoTypeSourceInfoDependent(TypeSourceInfo *TypeWithAuto) { 4948 return SubstituteDeducedTypeTransform(*this, DependentAuto{false}) 4949 .TransformType(TypeWithAuto); 4950 } 4951 4952 QualType Sema::ReplaceAutoType(QualType TypeWithAuto, 4953 QualType TypeToReplaceAuto) { 4954 return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto, 4955 /*UseTypeSugar*/ false) 4956 .TransformType(TypeWithAuto); 4957 } 4958 4959 TypeSourceInfo *Sema::ReplaceAutoTypeSourceInfo(TypeSourceInfo *TypeWithAuto, 4960 QualType TypeToReplaceAuto) { 4961 return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto, 4962 /*UseTypeSugar*/ false) 4963 .TransformType(TypeWithAuto); 4964 } 4965 4966 void Sema::DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init) { 4967 if (isa<InitListExpr>(Init)) 4968 Diag(VDecl->getLocation(), 4969 VDecl->isInitCapture() 4970 ? diag::err_init_capture_deduction_failure_from_init_list 4971 : diag::err_auto_var_deduction_failure_from_init_list) 4972 << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange(); 4973 else 4974 Diag(VDecl->getLocation(), 4975 VDecl->isInitCapture() ? diag::err_init_capture_deduction_failure 4976 : diag::err_auto_var_deduction_failure) 4977 << VDecl->getDeclName() << VDecl->getType() << Init->getType() 4978 << Init->getSourceRange(); 4979 } 4980 4981 bool Sema::DeduceReturnType(FunctionDecl *FD, SourceLocation Loc, 4982 bool Diagnose) { 4983 assert(FD->getReturnType()->isUndeducedType()); 4984 4985 // For a lambda's conversion operator, deduce any 'auto' or 'decltype(auto)' 4986 // within the return type from the call operator's type. 4987 if (isLambdaConversionOperator(FD)) { 4988 CXXRecordDecl *Lambda = cast<CXXMethodDecl>(FD)->getParent(); 4989 FunctionDecl *CallOp = Lambda->getLambdaCallOperator(); 4990 4991 // For a generic lambda, instantiate the call operator if needed. 4992 if (auto *Args = FD->getTemplateSpecializationArgs()) { 4993 CallOp = InstantiateFunctionDeclaration( 4994 CallOp->getDescribedFunctionTemplate(), Args, Loc); 4995 if (!CallOp || CallOp->isInvalidDecl()) 4996 return true; 4997 4998 // We might need to deduce the return type by instantiating the definition 4999 // of the operator() function. 5000 if (CallOp->getReturnType()->isUndeducedType()) { 5001 runWithSufficientStackSpace(Loc, [&] { 5002 InstantiateFunctionDefinition(Loc, CallOp); 5003 }); 5004 } 5005 } 5006 5007 if (CallOp->isInvalidDecl()) 5008 return true; 5009 assert(!CallOp->getReturnType()->isUndeducedType() && 5010 "failed to deduce lambda return type"); 5011 5012 // Build the new return type from scratch. 5013 CallingConv RetTyCC = FD->getReturnType() 5014 ->getPointeeType() 5015 ->castAs<FunctionType>() 5016 ->getCallConv(); 5017 QualType RetType = getLambdaConversionFunctionResultType( 5018 CallOp->getType()->castAs<FunctionProtoType>(), RetTyCC); 5019 if (FD->getReturnType()->getAs<PointerType>()) 5020 RetType = Context.getPointerType(RetType); 5021 else { 5022 assert(FD->getReturnType()->getAs<BlockPointerType>()); 5023 RetType = Context.getBlockPointerType(RetType); 5024 } 5025 Context.adjustDeducedFunctionResultType(FD, RetType); 5026 return false; 5027 } 5028 5029 if (FD->getTemplateInstantiationPattern()) { 5030 runWithSufficientStackSpace(Loc, [&] { 5031 InstantiateFunctionDefinition(Loc, FD); 5032 }); 5033 } 5034 5035 bool StillUndeduced = FD->getReturnType()->isUndeducedType(); 5036 if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) { 5037 Diag(Loc, diag::err_auto_fn_used_before_defined) << FD; 5038 Diag(FD->getLocation(), diag::note_callee_decl) << FD; 5039 } 5040 5041 return StillUndeduced; 5042 } 5043 5044 bool Sema::CheckIfFunctionSpecializationIsImmediate(FunctionDecl *FD, 5045 SourceLocation Loc) { 5046 assert(FD->isImmediateEscalating()); 5047 5048 if (isLambdaConversionOperator(FD)) { 5049 CXXRecordDecl *Lambda = cast<CXXMethodDecl>(FD)->getParent(); 5050 FunctionDecl *CallOp = Lambda->getLambdaCallOperator(); 5051 5052 // For a generic lambda, instantiate the call operator if needed. 5053 if (auto *Args = FD->getTemplateSpecializationArgs()) { 5054 CallOp = InstantiateFunctionDeclaration( 5055 CallOp->getDescribedFunctionTemplate(), Args, Loc); 5056 if (!CallOp || CallOp->isInvalidDecl()) 5057 return true; 5058 runWithSufficientStackSpace( 5059 Loc, [&] { InstantiateFunctionDefinition(Loc, CallOp); }); 5060 } 5061 return CallOp->isInvalidDecl(); 5062 } 5063 5064 if (FD->getTemplateInstantiationPattern()) { 5065 runWithSufficientStackSpace( 5066 Loc, [&] { InstantiateFunctionDefinition(Loc, FD); }); 5067 } 5068 return false; 5069 } 5070 5071 /// If this is a non-static member function, 5072 static void 5073 AddImplicitObjectParameterType(ASTContext &Context, 5074 CXXMethodDecl *Method, 5075 SmallVectorImpl<QualType> &ArgTypes) { 5076 // C++11 [temp.func.order]p3: 5077 // [...] The new parameter is of type "reference to cv A," where cv are 5078 // the cv-qualifiers of the function template (if any) and A is 5079 // the class of which the function template is a member. 5080 // 5081 // The standard doesn't say explicitly, but we pick the appropriate kind of 5082 // reference type based on [over.match.funcs]p4. 5083 QualType ArgTy = Context.getTypeDeclType(Method->getParent()); 5084 ArgTy = Context.getQualifiedType(ArgTy, Method->getMethodQualifiers()); 5085 if (Method->getRefQualifier() == RQ_RValue) 5086 ArgTy = Context.getRValueReferenceType(ArgTy); 5087 else 5088 ArgTy = Context.getLValueReferenceType(ArgTy); 5089 ArgTypes.push_back(ArgTy); 5090 } 5091 5092 /// Determine whether the function template \p FT1 is at least as 5093 /// specialized as \p FT2. 5094 static bool isAtLeastAsSpecializedAs(Sema &S, 5095 SourceLocation Loc, 5096 FunctionTemplateDecl *FT1, 5097 FunctionTemplateDecl *FT2, 5098 TemplatePartialOrderingContext TPOC, 5099 unsigned NumCallArguments1, 5100 bool Reversed) { 5101 assert(!Reversed || TPOC == TPOC_Call); 5102 5103 FunctionDecl *FD1 = FT1->getTemplatedDecl(); 5104 FunctionDecl *FD2 = FT2->getTemplatedDecl(); 5105 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>(); 5106 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>(); 5107 5108 assert(Proto1 && Proto2 && "Function templates must have prototypes"); 5109 TemplateParameterList *TemplateParams = FT2->getTemplateParameters(); 5110 SmallVector<DeducedTemplateArgument, 4> Deduced; 5111 Deduced.resize(TemplateParams->size()); 5112 5113 // C++0x [temp.deduct.partial]p3: 5114 // The types used to determine the ordering depend on the context in which 5115 // the partial ordering is done: 5116 TemplateDeductionInfo Info(Loc); 5117 SmallVector<QualType, 4> Args2; 5118 switch (TPOC) { 5119 case TPOC_Call: { 5120 // - In the context of a function call, the function parameter types are 5121 // used. 5122 CXXMethodDecl *Method1 = dyn_cast<CXXMethodDecl>(FD1); 5123 CXXMethodDecl *Method2 = dyn_cast<CXXMethodDecl>(FD2); 5124 5125 // C++11 [temp.func.order]p3: 5126 // [...] If only one of the function templates is a non-static 5127 // member, that function template is considered to have a new 5128 // first parameter inserted in its function parameter list. The 5129 // new parameter is of type "reference to cv A," where cv are 5130 // the cv-qualifiers of the function template (if any) and A is 5131 // the class of which the function template is a member. 5132 // 5133 // Note that we interpret this to mean "if one of the function 5134 // templates is a non-static member and the other is a non-member"; 5135 // otherwise, the ordering rules for static functions against non-static 5136 // functions don't make any sense. 5137 // 5138 // C++98/03 doesn't have this provision but we've extended DR532 to cover 5139 // it as wording was broken prior to it. 5140 SmallVector<QualType, 4> Args1; 5141 5142 unsigned NumComparedArguments = NumCallArguments1; 5143 5144 if (!Method2 && Method1 && !Method1->isStatic()) { 5145 // Compare 'this' from Method1 against first parameter from Method2. 5146 AddImplicitObjectParameterType(S.Context, Method1, Args1); 5147 ++NumComparedArguments; 5148 } else if (!Method1 && Method2 && !Method2->isStatic()) { 5149 // Compare 'this' from Method2 against first parameter from Method1. 5150 AddImplicitObjectParameterType(S.Context, Method2, Args2); 5151 } else if (Method1 && Method2 && Reversed) { 5152 // Compare 'this' from Method1 against second parameter from Method2 5153 // and 'this' from Method2 against second parameter from Method1. 5154 AddImplicitObjectParameterType(S.Context, Method1, Args1); 5155 AddImplicitObjectParameterType(S.Context, Method2, Args2); 5156 ++NumComparedArguments; 5157 } 5158 5159 Args1.insert(Args1.end(), Proto1->param_type_begin(), 5160 Proto1->param_type_end()); 5161 Args2.insert(Args2.end(), Proto2->param_type_begin(), 5162 Proto2->param_type_end()); 5163 5164 // C++ [temp.func.order]p5: 5165 // The presence of unused ellipsis and default arguments has no effect on 5166 // the partial ordering of function templates. 5167 if (Args1.size() > NumComparedArguments) 5168 Args1.resize(NumComparedArguments); 5169 if (Args2.size() > NumComparedArguments) 5170 Args2.resize(NumComparedArguments); 5171 if (Reversed) 5172 std::reverse(Args2.begin(), Args2.end()); 5173 5174 if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(), 5175 Args1.data(), Args1.size(), Info, Deduced, 5176 TDF_None, /*PartialOrdering=*/true)) 5177 return false; 5178 5179 break; 5180 } 5181 5182 case TPOC_Conversion: 5183 // - In the context of a call to a conversion operator, the return types 5184 // of the conversion function templates are used. 5185 if (DeduceTemplateArgumentsByTypeMatch( 5186 S, TemplateParams, Proto2->getReturnType(), Proto1->getReturnType(), 5187 Info, Deduced, TDF_None, 5188 /*PartialOrdering=*/true)) 5189 return false; 5190 break; 5191 5192 case TPOC_Other: 5193 // - In other contexts (14.6.6.2) the function template's function type 5194 // is used. 5195 if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 5196 FD2->getType(), FD1->getType(), 5197 Info, Deduced, TDF_None, 5198 /*PartialOrdering=*/true)) 5199 return false; 5200 break; 5201 } 5202 5203 // C++0x [temp.deduct.partial]p11: 5204 // In most cases, all template parameters must have values in order for 5205 // deduction to succeed, but for partial ordering purposes a template 5206 // parameter may remain without a value provided it is not used in the 5207 // types being used for partial ordering. [ Note: a template parameter used 5208 // in a non-deduced context is considered used. -end note] 5209 unsigned ArgIdx = 0, NumArgs = Deduced.size(); 5210 for (; ArgIdx != NumArgs; ++ArgIdx) 5211 if (Deduced[ArgIdx].isNull()) 5212 break; 5213 5214 // FIXME: We fail to implement [temp.deduct.type]p1 along this path. We need 5215 // to substitute the deduced arguments back into the template and check that 5216 // we get the right type. 5217 5218 if (ArgIdx == NumArgs) { 5219 // All template arguments were deduced. FT1 is at least as specialized 5220 // as FT2. 5221 return true; 5222 } 5223 5224 // Figure out which template parameters were used. 5225 llvm::SmallBitVector UsedParameters(TemplateParams->size()); 5226 switch (TPOC) { 5227 case TPOC_Call: 5228 for (unsigned I = 0, N = Args2.size(); I != N; ++I) 5229 ::MarkUsedTemplateParameters(S.Context, Args2[I], false, 5230 TemplateParams->getDepth(), 5231 UsedParameters); 5232 break; 5233 5234 case TPOC_Conversion: 5235 ::MarkUsedTemplateParameters(S.Context, Proto2->getReturnType(), false, 5236 TemplateParams->getDepth(), UsedParameters); 5237 break; 5238 5239 case TPOC_Other: 5240 ::MarkUsedTemplateParameters(S.Context, FD2->getType(), false, 5241 TemplateParams->getDepth(), 5242 UsedParameters); 5243 break; 5244 } 5245 5246 for (; ArgIdx != NumArgs; ++ArgIdx) 5247 // If this argument had no value deduced but was used in one of the types 5248 // used for partial ordering, then deduction fails. 5249 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx]) 5250 return false; 5251 5252 return true; 5253 } 5254 5255 /// Returns the more specialized function template according 5256 /// to the rules of function template partial ordering (C++ [temp.func.order]). 5257 /// 5258 /// \param FT1 the first function template 5259 /// 5260 /// \param FT2 the second function template 5261 /// 5262 /// \param TPOC the context in which we are performing partial ordering of 5263 /// function templates. 5264 /// 5265 /// \param NumCallArguments1 The number of arguments in the call to FT1, used 5266 /// only when \c TPOC is \c TPOC_Call. 5267 /// 5268 /// \param NumCallArguments2 The number of arguments in the call to FT2, used 5269 /// only when \c TPOC is \c TPOC_Call. 5270 /// 5271 /// \param Reversed If \c true, exactly one of FT1 and FT2 is an overload 5272 /// candidate with a reversed parameter order. In this case, the corresponding 5273 /// P/A pairs between FT1 and FT2 are reversed. 5274 /// 5275 /// \returns the more specialized function template. If neither 5276 /// template is more specialized, returns NULL. 5277 FunctionTemplateDecl *Sema::getMoreSpecializedTemplate( 5278 FunctionTemplateDecl *FT1, FunctionTemplateDecl *FT2, SourceLocation Loc, 5279 TemplatePartialOrderingContext TPOC, unsigned NumCallArguments1, 5280 unsigned NumCallArguments2, bool Reversed) { 5281 5282 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC, 5283 NumCallArguments1, Reversed); 5284 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC, 5285 NumCallArguments2, Reversed); 5286 5287 // C++ [temp.deduct.partial]p10: 5288 // F is more specialized than G if F is at least as specialized as G and G 5289 // is not at least as specialized as F. 5290 if (Better1 != Better2) // We have a clear winner 5291 return Better1 ? FT1 : FT2; 5292 5293 if (!Better1 && !Better2) // Neither is better than the other 5294 return nullptr; 5295 5296 // C++ [temp.deduct.partial]p11: 5297 // ... and if G has a trailing function parameter pack for which F does not 5298 // have a corresponding parameter, and if F does not have a trailing 5299 // function parameter pack, then F is more specialized than G. 5300 FunctionDecl *FD1 = FT1->getTemplatedDecl(); 5301 FunctionDecl *FD2 = FT2->getTemplatedDecl(); 5302 unsigned NumParams1 = FD1->getNumParams(); 5303 unsigned NumParams2 = FD2->getNumParams(); 5304 bool Variadic1 = NumParams1 && FD1->parameters().back()->isParameterPack(); 5305 bool Variadic2 = NumParams2 && FD2->parameters().back()->isParameterPack(); 5306 if (Variadic1 != Variadic2) { 5307 if (Variadic1 && NumParams1 > NumParams2) 5308 return FT2; 5309 if (Variadic2 && NumParams2 > NumParams1) 5310 return FT1; 5311 } 5312 5313 // This a speculative fix for CWG1432 (Similar to the fix for CWG1395) that 5314 // there is no wording or even resolution for this issue. 5315 for (int i = 0, e = std::min(NumParams1, NumParams2); i < e; ++i) { 5316 QualType T1 = FD1->getParamDecl(i)->getType().getCanonicalType(); 5317 QualType T2 = FD2->getParamDecl(i)->getType().getCanonicalType(); 5318 auto *TST1 = dyn_cast<TemplateSpecializationType>(T1); 5319 auto *TST2 = dyn_cast<TemplateSpecializationType>(T2); 5320 if (!TST1 || !TST2) 5321 continue; 5322 const TemplateArgument &TA1 = TST1->template_arguments().back(); 5323 if (TA1.getKind() == TemplateArgument::Pack) { 5324 assert(TST1->template_arguments().size() == 5325 TST2->template_arguments().size()); 5326 const TemplateArgument &TA2 = TST2->template_arguments().back(); 5327 assert(TA2.getKind() == TemplateArgument::Pack); 5328 unsigned PackSize1 = TA1.pack_size(); 5329 unsigned PackSize2 = TA2.pack_size(); 5330 bool IsPackExpansion1 = 5331 PackSize1 && TA1.pack_elements().back().isPackExpansion(); 5332 bool IsPackExpansion2 = 5333 PackSize2 && TA2.pack_elements().back().isPackExpansion(); 5334 if (PackSize1 != PackSize2 && IsPackExpansion1 != IsPackExpansion2) { 5335 if (PackSize1 > PackSize2 && IsPackExpansion1) 5336 return FT2; 5337 if (PackSize1 < PackSize2 && IsPackExpansion2) 5338 return FT1; 5339 } 5340 } 5341 } 5342 5343 if (!Context.getLangOpts().CPlusPlus20) 5344 return nullptr; 5345 5346 // Match GCC on not implementing [temp.func.order]p6.2.1. 5347 5348 // C++20 [temp.func.order]p6: 5349 // If deduction against the other template succeeds for both transformed 5350 // templates, constraints can be considered as follows: 5351 5352 // C++20 [temp.func.order]p6.1: 5353 // If their template-parameter-lists (possibly including template-parameters 5354 // invented for an abbreviated function template ([dcl.fct])) or function 5355 // parameter lists differ in length, neither template is more specialized 5356 // than the other. 5357 TemplateParameterList *TPL1 = FT1->getTemplateParameters(); 5358 TemplateParameterList *TPL2 = FT2->getTemplateParameters(); 5359 if (TPL1->size() != TPL2->size() || NumParams1 != NumParams2) 5360 return nullptr; 5361 5362 // C++20 [temp.func.order]p6.2.2: 5363 // Otherwise, if the corresponding template-parameters of the 5364 // template-parameter-lists are not equivalent ([temp.over.link]) or if the 5365 // function parameters that positionally correspond between the two 5366 // templates are not of the same type, neither template is more specialized 5367 // than the other. 5368 if (!TemplateParameterListsAreEqual(TPL1, TPL2, false, 5369 Sema::TPL_TemplateParamsEquivalent)) 5370 return nullptr; 5371 5372 for (unsigned i = 0; i < NumParams1; ++i) 5373 if (!Context.hasSameType(FD1->getParamDecl(i)->getType(), 5374 FD2->getParamDecl(i)->getType())) 5375 return nullptr; 5376 5377 // C++20 [temp.func.order]p6.3: 5378 // Otherwise, if the context in which the partial ordering is done is 5379 // that of a call to a conversion function and the return types of the 5380 // templates are not the same, then neither template is more specialized 5381 // than the other. 5382 if (TPOC == TPOC_Conversion && 5383 !Context.hasSameType(FD1->getReturnType(), FD2->getReturnType())) 5384 return nullptr; 5385 5386 llvm::SmallVector<const Expr *, 3> AC1, AC2; 5387 FT1->getAssociatedConstraints(AC1); 5388 FT2->getAssociatedConstraints(AC2); 5389 bool AtLeastAsConstrained1, AtLeastAsConstrained2; 5390 if (IsAtLeastAsConstrained(FT1, AC1, FT2, AC2, AtLeastAsConstrained1)) 5391 return nullptr; 5392 if (IsAtLeastAsConstrained(FT2, AC2, FT1, AC1, AtLeastAsConstrained2)) 5393 return nullptr; 5394 if (AtLeastAsConstrained1 == AtLeastAsConstrained2) 5395 return nullptr; 5396 return AtLeastAsConstrained1 ? FT1 : FT2; 5397 } 5398 5399 /// Determine if the two templates are equivalent. 5400 static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) { 5401 if (T1 == T2) 5402 return true; 5403 5404 if (!T1 || !T2) 5405 return false; 5406 5407 return T1->getCanonicalDecl() == T2->getCanonicalDecl(); 5408 } 5409 5410 /// Retrieve the most specialized of the given function template 5411 /// specializations. 5412 /// 5413 /// \param SpecBegin the start iterator of the function template 5414 /// specializations that we will be comparing. 5415 /// 5416 /// \param SpecEnd the end iterator of the function template 5417 /// specializations, paired with \p SpecBegin. 5418 /// 5419 /// \param Loc the location where the ambiguity or no-specializations 5420 /// diagnostic should occur. 5421 /// 5422 /// \param NoneDiag partial diagnostic used to diagnose cases where there are 5423 /// no matching candidates. 5424 /// 5425 /// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one 5426 /// occurs. 5427 /// 5428 /// \param CandidateDiag partial diagnostic used for each function template 5429 /// specialization that is a candidate in the ambiguous ordering. One parameter 5430 /// in this diagnostic should be unbound, which will correspond to the string 5431 /// describing the template arguments for the function template specialization. 5432 /// 5433 /// \returns the most specialized function template specialization, if 5434 /// found. Otherwise, returns SpecEnd. 5435 UnresolvedSetIterator Sema::getMostSpecialized( 5436 UnresolvedSetIterator SpecBegin, UnresolvedSetIterator SpecEnd, 5437 TemplateSpecCandidateSet &FailedCandidates, 5438 SourceLocation Loc, const PartialDiagnostic &NoneDiag, 5439 const PartialDiagnostic &AmbigDiag, const PartialDiagnostic &CandidateDiag, 5440 bool Complain, QualType TargetType) { 5441 if (SpecBegin == SpecEnd) { 5442 if (Complain) { 5443 Diag(Loc, NoneDiag); 5444 FailedCandidates.NoteCandidates(*this, Loc); 5445 } 5446 return SpecEnd; 5447 } 5448 5449 if (SpecBegin + 1 == SpecEnd) 5450 return SpecBegin; 5451 5452 // Find the function template that is better than all of the templates it 5453 // has been compared to. 5454 UnresolvedSetIterator Best = SpecBegin; 5455 FunctionTemplateDecl *BestTemplate 5456 = cast<FunctionDecl>(*Best)->getPrimaryTemplate(); 5457 assert(BestTemplate && "Not a function template specialization?"); 5458 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) { 5459 FunctionTemplateDecl *Challenger 5460 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 5461 assert(Challenger && "Not a function template specialization?"); 5462 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 5463 Loc, TPOC_Other, 0, 0), 5464 Challenger)) { 5465 Best = I; 5466 BestTemplate = Challenger; 5467 } 5468 } 5469 5470 // Make sure that the "best" function template is more specialized than all 5471 // of the others. 5472 bool Ambiguous = false; 5473 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 5474 FunctionTemplateDecl *Challenger 5475 = cast<FunctionDecl>(*I)->getPrimaryTemplate(); 5476 if (I != Best && 5477 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger, 5478 Loc, TPOC_Other, 0, 0), 5479 BestTemplate)) { 5480 Ambiguous = true; 5481 break; 5482 } 5483 } 5484 5485 if (!Ambiguous) { 5486 // We found an answer. Return it. 5487 return Best; 5488 } 5489 5490 // Diagnose the ambiguity. 5491 if (Complain) { 5492 Diag(Loc, AmbigDiag); 5493 5494 // FIXME: Can we order the candidates in some sane way? 5495 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) { 5496 PartialDiagnostic PD = CandidateDiag; 5497 const auto *FD = cast<FunctionDecl>(*I); 5498 PD << FD << getTemplateArgumentBindingsText( 5499 FD->getPrimaryTemplate()->getTemplateParameters(), 5500 *FD->getTemplateSpecializationArgs()); 5501 if (!TargetType.isNull()) 5502 HandleFunctionTypeMismatch(PD, FD->getType(), TargetType); 5503 Diag((*I)->getLocation(), PD); 5504 } 5505 } 5506 5507 return SpecEnd; 5508 } 5509 5510 /// Determine whether one partial specialization, P1, is at least as 5511 /// specialized than another, P2. 5512 /// 5513 /// \tparam TemplateLikeDecl The kind of P2, which must be a 5514 /// TemplateDecl or {Class,Var}TemplatePartialSpecializationDecl. 5515 /// \param T1 The injected-class-name of P1 (faked for a variable template). 5516 /// \param T2 The injected-class-name of P2 (faked for a variable template). 5517 template<typename TemplateLikeDecl> 5518 static bool isAtLeastAsSpecializedAs(Sema &S, QualType T1, QualType T2, 5519 TemplateLikeDecl *P2, 5520 TemplateDeductionInfo &Info) { 5521 // C++ [temp.class.order]p1: 5522 // For two class template partial specializations, the first is at least as 5523 // specialized as the second if, given the following rewrite to two 5524 // function templates, the first function template is at least as 5525 // specialized as the second according to the ordering rules for function 5526 // templates (14.6.6.2): 5527 // - the first function template has the same template parameters as the 5528 // first partial specialization and has a single function parameter 5529 // whose type is a class template specialization with the template 5530 // arguments of the first partial specialization, and 5531 // - the second function template has the same template parameters as the 5532 // second partial specialization and has a single function parameter 5533 // whose type is a class template specialization with the template 5534 // arguments of the second partial specialization. 5535 // 5536 // Rather than synthesize function templates, we merely perform the 5537 // equivalent partial ordering by performing deduction directly on 5538 // the template arguments of the class template partial 5539 // specializations. This computation is slightly simpler than the 5540 // general problem of function template partial ordering, because 5541 // class template partial specializations are more constrained. We 5542 // know that every template parameter is deducible from the class 5543 // template partial specialization's template arguments, for 5544 // example. 5545 SmallVector<DeducedTemplateArgument, 4> Deduced; 5546 5547 // Determine whether P1 is at least as specialized as P2. 5548 Deduced.resize(P2->getTemplateParameters()->size()); 5549 if (DeduceTemplateArgumentsByTypeMatch(S, P2->getTemplateParameters(), 5550 T2, T1, Info, Deduced, TDF_None, 5551 /*PartialOrdering=*/true)) 5552 return false; 5553 5554 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), 5555 Deduced.end()); 5556 Sema::InstantiatingTemplate Inst(S, Info.getLocation(), P2, DeducedArgs, 5557 Info); 5558 if (Inst.isInvalid()) 5559 return false; 5560 5561 const auto *TST1 = cast<TemplateSpecializationType>(T1); 5562 bool AtLeastAsSpecialized; 5563 S.runWithSufficientStackSpace(Info.getLocation(), [&] { 5564 AtLeastAsSpecialized = !FinishTemplateArgumentDeduction( 5565 S, P2, /*IsPartialOrdering=*/true, 5566 TemplateArgumentList(TemplateArgumentList::OnStack, 5567 TST1->template_arguments()), 5568 Deduced, Info); 5569 }); 5570 return AtLeastAsSpecialized; 5571 } 5572 5573 namespace { 5574 // A dummy class to return nullptr instead of P2 when performing "more 5575 // specialized than primary" check. 5576 struct GetP2 { 5577 template <typename T1, typename T2, 5578 std::enable_if_t<std::is_same_v<T1, T2>, bool> = true> 5579 T2 *operator()(T1 *, T2 *P2) { 5580 return P2; 5581 } 5582 template <typename T1, typename T2, 5583 std::enable_if_t<!std::is_same_v<T1, T2>, bool> = true> 5584 T1 *operator()(T1 *, T2 *) { 5585 return nullptr; 5586 } 5587 }; 5588 5589 // The assumption is that two template argument lists have the same size. 5590 struct TemplateArgumentListAreEqual { 5591 ASTContext &Ctx; 5592 TemplateArgumentListAreEqual(ASTContext &Ctx) : Ctx(Ctx) {} 5593 5594 template <typename T1, typename T2, 5595 std::enable_if_t<std::is_same_v<T1, T2>, bool> = true> 5596 bool operator()(T1 *PS1, T2 *PS2) { 5597 ArrayRef<TemplateArgument> Args1 = PS1->getTemplateArgs().asArray(), 5598 Args2 = PS2->getTemplateArgs().asArray(); 5599 5600 for (unsigned I = 0, E = Args1.size(); I < E; ++I) { 5601 // We use profile, instead of structural comparison of the arguments, 5602 // because canonicalization can't do the right thing for dependent 5603 // expressions. 5604 llvm::FoldingSetNodeID IDA, IDB; 5605 Args1[I].Profile(IDA, Ctx); 5606 Args2[I].Profile(IDB, Ctx); 5607 if (IDA != IDB) 5608 return false; 5609 } 5610 return true; 5611 } 5612 5613 template <typename T1, typename T2, 5614 std::enable_if_t<!std::is_same_v<T1, T2>, bool> = true> 5615 bool operator()(T1 *Spec, T2 *Primary) { 5616 ArrayRef<TemplateArgument> Args1 = Spec->getTemplateArgs().asArray(), 5617 Args2 = Primary->getInjectedTemplateArgs(); 5618 5619 for (unsigned I = 0, E = Args1.size(); I < E; ++I) { 5620 // We use profile, instead of structural comparison of the arguments, 5621 // because canonicalization can't do the right thing for dependent 5622 // expressions. 5623 llvm::FoldingSetNodeID IDA, IDB; 5624 Args1[I].Profile(IDA, Ctx); 5625 // Unlike the specialization arguments, the injected arguments are not 5626 // always canonical. 5627 Ctx.getCanonicalTemplateArgument(Args2[I]).Profile(IDB, Ctx); 5628 if (IDA != IDB) 5629 return false; 5630 } 5631 return true; 5632 } 5633 }; 5634 } // namespace 5635 5636 /// Returns the more specialized template specialization between T1/P1 and 5637 /// T2/P2. 5638 /// - If IsMoreSpecialThanPrimaryCheck is true, T1/P1 is the partial 5639 /// specialization and T2/P2 is the primary template. 5640 /// - otherwise, both T1/P1 and T2/P2 are the partial specialization. 5641 /// 5642 /// \param T1 the type of the first template partial specialization 5643 /// 5644 /// \param T2 if IsMoreSpecialThanPrimaryCheck is true, the type of the second 5645 /// template partial specialization; otherwise, the type of the 5646 /// primary template. 5647 /// 5648 /// \param P1 the first template partial specialization 5649 /// 5650 /// \param P2 if IsMoreSpecialThanPrimaryCheck is true, the second template 5651 /// partial specialization; otherwise, the primary template. 5652 /// 5653 /// \returns - If IsMoreSpecialThanPrimaryCheck is true, returns P1 if P1 is 5654 /// more specialized, returns nullptr if P1 is not more specialized. 5655 /// - otherwise, returns the more specialized template partial 5656 /// specialization. If neither partial specialization is more 5657 /// specialized, returns NULL. 5658 template <typename TemplateLikeDecl, typename PrimaryDel> 5659 static TemplateLikeDecl * 5660 getMoreSpecialized(Sema &S, QualType T1, QualType T2, TemplateLikeDecl *P1, 5661 PrimaryDel *P2, TemplateDeductionInfo &Info) { 5662 constexpr bool IsMoreSpecialThanPrimaryCheck = 5663 !std::is_same_v<TemplateLikeDecl, PrimaryDel>; 5664 5665 bool Better1 = isAtLeastAsSpecializedAs(S, T1, T2, P2, Info); 5666 if (IsMoreSpecialThanPrimaryCheck && !Better1) 5667 return nullptr; 5668 5669 bool Better2 = isAtLeastAsSpecializedAs(S, T2, T1, P1, Info); 5670 if (IsMoreSpecialThanPrimaryCheck && !Better2) 5671 return P1; 5672 5673 // C++ [temp.deduct.partial]p10: 5674 // F is more specialized than G if F is at least as specialized as G and G 5675 // is not at least as specialized as F. 5676 if (Better1 != Better2) // We have a clear winner 5677 return Better1 ? P1 : GetP2()(P1, P2); 5678 5679 if (!Better1 && !Better2) 5680 return nullptr; 5681 5682 // This a speculative fix for CWG1432 (Similar to the fix for CWG1395) that 5683 // there is no wording or even resolution for this issue. 5684 auto *TST1 = cast<TemplateSpecializationType>(T1); 5685 auto *TST2 = cast<TemplateSpecializationType>(T2); 5686 const TemplateArgument &TA1 = TST1->template_arguments().back(); 5687 if (TA1.getKind() == TemplateArgument::Pack) { 5688 assert(TST1->template_arguments().size() == 5689 TST2->template_arguments().size()); 5690 const TemplateArgument &TA2 = TST2->template_arguments().back(); 5691 assert(TA2.getKind() == TemplateArgument::Pack); 5692 unsigned PackSize1 = TA1.pack_size(); 5693 unsigned PackSize2 = TA2.pack_size(); 5694 bool IsPackExpansion1 = 5695 PackSize1 && TA1.pack_elements().back().isPackExpansion(); 5696 bool IsPackExpansion2 = 5697 PackSize2 && TA2.pack_elements().back().isPackExpansion(); 5698 if (PackSize1 != PackSize2 && IsPackExpansion1 != IsPackExpansion2) { 5699 if (PackSize1 > PackSize2 && IsPackExpansion1) 5700 return GetP2()(P1, P2); 5701 if (PackSize1 < PackSize2 && IsPackExpansion2) 5702 return P1; 5703 } 5704 } 5705 5706 if (!S.Context.getLangOpts().CPlusPlus20) 5707 return nullptr; 5708 5709 // Match GCC on not implementing [temp.func.order]p6.2.1. 5710 5711 // C++20 [temp.func.order]p6: 5712 // If deduction against the other template succeeds for both transformed 5713 // templates, constraints can be considered as follows: 5714 5715 TemplateParameterList *TPL1 = P1->getTemplateParameters(); 5716 TemplateParameterList *TPL2 = P2->getTemplateParameters(); 5717 if (TPL1->size() != TPL2->size()) 5718 return nullptr; 5719 5720 // C++20 [temp.func.order]p6.2.2: 5721 // Otherwise, if the corresponding template-parameters of the 5722 // template-parameter-lists are not equivalent ([temp.over.link]) or if the 5723 // function parameters that positionally correspond between the two 5724 // templates are not of the same type, neither template is more specialized 5725 // than the other. 5726 if (!S.TemplateParameterListsAreEqual(TPL1, TPL2, false, 5727 Sema::TPL_TemplateParamsEquivalent)) 5728 return nullptr; 5729 5730 if (!TemplateArgumentListAreEqual(S.getASTContext())(P1, P2)) 5731 return nullptr; 5732 5733 llvm::SmallVector<const Expr *, 3> AC1, AC2; 5734 P1->getAssociatedConstraints(AC1); 5735 P2->getAssociatedConstraints(AC2); 5736 bool AtLeastAsConstrained1, AtLeastAsConstrained2; 5737 if (S.IsAtLeastAsConstrained(P1, AC1, P2, AC2, AtLeastAsConstrained1) || 5738 (IsMoreSpecialThanPrimaryCheck && !AtLeastAsConstrained1)) 5739 return nullptr; 5740 if (S.IsAtLeastAsConstrained(P2, AC2, P1, AC1, AtLeastAsConstrained2)) 5741 return nullptr; 5742 if (AtLeastAsConstrained1 == AtLeastAsConstrained2) 5743 return nullptr; 5744 return AtLeastAsConstrained1 ? P1 : GetP2()(P1, P2); 5745 } 5746 5747 /// Returns the more specialized class template partial specialization 5748 /// according to the rules of partial ordering of class template partial 5749 /// specializations (C++ [temp.class.order]). 5750 /// 5751 /// \param PS1 the first class template partial specialization 5752 /// 5753 /// \param PS2 the second class template partial specialization 5754 /// 5755 /// \returns the more specialized class template partial specialization. If 5756 /// neither partial specialization is more specialized, returns NULL. 5757 ClassTemplatePartialSpecializationDecl * 5758 Sema::getMoreSpecializedPartialSpecialization( 5759 ClassTemplatePartialSpecializationDecl *PS1, 5760 ClassTemplatePartialSpecializationDecl *PS2, 5761 SourceLocation Loc) { 5762 QualType PT1 = PS1->getInjectedSpecializationType(); 5763 QualType PT2 = PS2->getInjectedSpecializationType(); 5764 5765 TemplateDeductionInfo Info(Loc); 5766 return getMoreSpecialized(*this, PT1, PT2, PS1, PS2, Info); 5767 } 5768 5769 bool Sema::isMoreSpecializedThanPrimary( 5770 ClassTemplatePartialSpecializationDecl *Spec, TemplateDeductionInfo &Info) { 5771 ClassTemplateDecl *Primary = Spec->getSpecializedTemplate(); 5772 QualType PrimaryT = Primary->getInjectedClassNameSpecialization(); 5773 QualType PartialT = Spec->getInjectedSpecializationType(); 5774 5775 ClassTemplatePartialSpecializationDecl *MaybeSpec = 5776 getMoreSpecialized(*this, PartialT, PrimaryT, Spec, Primary, Info); 5777 if (MaybeSpec) 5778 Info.clearSFINAEDiagnostic(); 5779 return MaybeSpec; 5780 } 5781 5782 VarTemplatePartialSpecializationDecl * 5783 Sema::getMoreSpecializedPartialSpecialization( 5784 VarTemplatePartialSpecializationDecl *PS1, 5785 VarTemplatePartialSpecializationDecl *PS2, SourceLocation Loc) { 5786 // Pretend the variable template specializations are class template 5787 // specializations and form a fake injected class name type for comparison. 5788 assert(PS1->getSpecializedTemplate() == PS2->getSpecializedTemplate() && 5789 "the partial specializations being compared should specialize" 5790 " the same template."); 5791 TemplateName Name(PS1->getSpecializedTemplate()); 5792 TemplateName CanonTemplate = Context.getCanonicalTemplateName(Name); 5793 QualType PT1 = Context.getTemplateSpecializationType( 5794 CanonTemplate, PS1->getTemplateArgs().asArray()); 5795 QualType PT2 = Context.getTemplateSpecializationType( 5796 CanonTemplate, PS2->getTemplateArgs().asArray()); 5797 5798 TemplateDeductionInfo Info(Loc); 5799 return getMoreSpecialized(*this, PT1, PT2, PS1, PS2, Info); 5800 } 5801 5802 bool Sema::isMoreSpecializedThanPrimary( 5803 VarTemplatePartialSpecializationDecl *Spec, TemplateDeductionInfo &Info) { 5804 VarTemplateDecl *Primary = Spec->getSpecializedTemplate(); 5805 TemplateName CanonTemplate = 5806 Context.getCanonicalTemplateName(TemplateName(Primary)); 5807 QualType PrimaryT = Context.getTemplateSpecializationType( 5808 CanonTemplate, Primary->getInjectedTemplateArgs()); 5809 QualType PartialT = Context.getTemplateSpecializationType( 5810 CanonTemplate, Spec->getTemplateArgs().asArray()); 5811 5812 VarTemplatePartialSpecializationDecl *MaybeSpec = 5813 getMoreSpecialized(*this, PartialT, PrimaryT, Spec, Primary, Info); 5814 if (MaybeSpec) 5815 Info.clearSFINAEDiagnostic(); 5816 return MaybeSpec; 5817 } 5818 5819 bool Sema::isTemplateTemplateParameterAtLeastAsSpecializedAs( 5820 TemplateParameterList *P, TemplateDecl *AArg, SourceLocation Loc) { 5821 // C++1z [temp.arg.template]p4: (DR 150) 5822 // A template template-parameter P is at least as specialized as a 5823 // template template-argument A if, given the following rewrite to two 5824 // function templates... 5825 5826 // Rather than synthesize function templates, we merely perform the 5827 // equivalent partial ordering by performing deduction directly on 5828 // the template parameter lists of the template template parameters. 5829 // 5830 // Given an invented class template X with the template parameter list of 5831 // A (including default arguments): 5832 TemplateName X = Context.getCanonicalTemplateName(TemplateName(AArg)); 5833 TemplateParameterList *A = AArg->getTemplateParameters(); 5834 5835 // - Each function template has a single function parameter whose type is 5836 // a specialization of X with template arguments corresponding to the 5837 // template parameters from the respective function template 5838 SmallVector<TemplateArgument, 8> AArgs; 5839 Context.getInjectedTemplateArgs(A, AArgs); 5840 5841 // Check P's arguments against A's parameter list. This will fill in default 5842 // template arguments as needed. AArgs are already correct by construction. 5843 // We can't just use CheckTemplateIdType because that will expand alias 5844 // templates. 5845 SmallVector<TemplateArgument, 4> PArgs; 5846 { 5847 SFINAETrap Trap(*this); 5848 5849 Context.getInjectedTemplateArgs(P, PArgs); 5850 TemplateArgumentListInfo PArgList(P->getLAngleLoc(), 5851 P->getRAngleLoc()); 5852 for (unsigned I = 0, N = P->size(); I != N; ++I) { 5853 // Unwrap packs that getInjectedTemplateArgs wrapped around pack 5854 // expansions, to form an "as written" argument list. 5855 TemplateArgument Arg = PArgs[I]; 5856 if (Arg.getKind() == TemplateArgument::Pack) { 5857 assert(Arg.pack_size() == 1 && Arg.pack_begin()->isPackExpansion()); 5858 Arg = *Arg.pack_begin(); 5859 } 5860 PArgList.addArgument(getTrivialTemplateArgumentLoc( 5861 Arg, QualType(), P->getParam(I)->getLocation())); 5862 } 5863 PArgs.clear(); 5864 5865 // C++1z [temp.arg.template]p3: 5866 // If the rewrite produces an invalid type, then P is not at least as 5867 // specialized as A. 5868 SmallVector<TemplateArgument, 4> SugaredPArgs; 5869 if (CheckTemplateArgumentList(AArg, Loc, PArgList, false, SugaredPArgs, 5870 PArgs) || 5871 Trap.hasErrorOccurred()) 5872 return false; 5873 } 5874 5875 QualType AType = Context.getCanonicalTemplateSpecializationType(X, AArgs); 5876 QualType PType = Context.getCanonicalTemplateSpecializationType(X, PArgs); 5877 5878 // ... the function template corresponding to P is at least as specialized 5879 // as the function template corresponding to A according to the partial 5880 // ordering rules for function templates. 5881 TemplateDeductionInfo Info(Loc, A->getDepth()); 5882 return isAtLeastAsSpecializedAs(*this, PType, AType, AArg, Info); 5883 } 5884 5885 namespace { 5886 struct MarkUsedTemplateParameterVisitor : 5887 RecursiveASTVisitor<MarkUsedTemplateParameterVisitor> { 5888 llvm::SmallBitVector &Used; 5889 unsigned Depth; 5890 5891 MarkUsedTemplateParameterVisitor(llvm::SmallBitVector &Used, 5892 unsigned Depth) 5893 : Used(Used), Depth(Depth) { } 5894 5895 bool VisitTemplateTypeParmType(TemplateTypeParmType *T) { 5896 if (T->getDepth() == Depth) 5897 Used[T->getIndex()] = true; 5898 return true; 5899 } 5900 5901 bool TraverseTemplateName(TemplateName Template) { 5902 if (auto *TTP = llvm::dyn_cast_or_null<TemplateTemplateParmDecl>( 5903 Template.getAsTemplateDecl())) 5904 if (TTP->getDepth() == Depth) 5905 Used[TTP->getIndex()] = true; 5906 RecursiveASTVisitor<MarkUsedTemplateParameterVisitor>:: 5907 TraverseTemplateName(Template); 5908 return true; 5909 } 5910 5911 bool VisitDeclRefExpr(DeclRefExpr *E) { 5912 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(E->getDecl())) 5913 if (NTTP->getDepth() == Depth) 5914 Used[NTTP->getIndex()] = true; 5915 return true; 5916 } 5917 }; 5918 } 5919 5920 /// Mark the template parameters that are used by the given 5921 /// expression. 5922 static void 5923 MarkUsedTemplateParameters(ASTContext &Ctx, 5924 const Expr *E, 5925 bool OnlyDeduced, 5926 unsigned Depth, 5927 llvm::SmallBitVector &Used) { 5928 if (!OnlyDeduced) { 5929 MarkUsedTemplateParameterVisitor(Used, Depth) 5930 .TraverseStmt(const_cast<Expr *>(E)); 5931 return; 5932 } 5933 5934 // We can deduce from a pack expansion. 5935 if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E)) 5936 E = Expansion->getPattern(); 5937 5938 const NonTypeTemplateParmDecl *NTTP = getDeducedParameterFromExpr(E, Depth); 5939 if (!NTTP) 5940 return; 5941 5942 if (NTTP->getDepth() == Depth) 5943 Used[NTTP->getIndex()] = true; 5944 5945 // In C++17 mode, additional arguments may be deduced from the type of a 5946 // non-type argument. 5947 if (Ctx.getLangOpts().CPlusPlus17) 5948 MarkUsedTemplateParameters(Ctx, NTTP->getType(), OnlyDeduced, Depth, Used); 5949 } 5950 5951 /// Mark the template parameters that are used by the given 5952 /// nested name specifier. 5953 static void 5954 MarkUsedTemplateParameters(ASTContext &Ctx, 5955 NestedNameSpecifier *NNS, 5956 bool OnlyDeduced, 5957 unsigned Depth, 5958 llvm::SmallBitVector &Used) { 5959 if (!NNS) 5960 return; 5961 5962 MarkUsedTemplateParameters(Ctx, NNS->getPrefix(), OnlyDeduced, Depth, 5963 Used); 5964 MarkUsedTemplateParameters(Ctx, QualType(NNS->getAsType(), 0), 5965 OnlyDeduced, Depth, Used); 5966 } 5967 5968 /// Mark the template parameters that are used by the given 5969 /// template name. 5970 static void 5971 MarkUsedTemplateParameters(ASTContext &Ctx, 5972 TemplateName Name, 5973 bool OnlyDeduced, 5974 unsigned Depth, 5975 llvm::SmallBitVector &Used) { 5976 if (TemplateDecl *Template = Name.getAsTemplateDecl()) { 5977 if (TemplateTemplateParmDecl *TTP 5978 = dyn_cast<TemplateTemplateParmDecl>(Template)) { 5979 if (TTP->getDepth() == Depth) 5980 Used[TTP->getIndex()] = true; 5981 } 5982 return; 5983 } 5984 5985 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) 5986 MarkUsedTemplateParameters(Ctx, QTN->getQualifier(), OnlyDeduced, 5987 Depth, Used); 5988 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) 5989 MarkUsedTemplateParameters(Ctx, DTN->getQualifier(), OnlyDeduced, 5990 Depth, Used); 5991 } 5992 5993 /// Mark the template parameters that are used by the given 5994 /// type. 5995 static void 5996 MarkUsedTemplateParameters(ASTContext &Ctx, QualType T, 5997 bool OnlyDeduced, 5998 unsigned Depth, 5999 llvm::SmallBitVector &Used) { 6000 if (T.isNull()) 6001 return; 6002 6003 // Non-dependent types have nothing deducible 6004 if (!T->isDependentType()) 6005 return; 6006 6007 T = Ctx.getCanonicalType(T); 6008 switch (T->getTypeClass()) { 6009 case Type::Pointer: 6010 MarkUsedTemplateParameters(Ctx, 6011 cast<PointerType>(T)->getPointeeType(), 6012 OnlyDeduced, 6013 Depth, 6014 Used); 6015 break; 6016 6017 case Type::BlockPointer: 6018 MarkUsedTemplateParameters(Ctx, 6019 cast<BlockPointerType>(T)->getPointeeType(), 6020 OnlyDeduced, 6021 Depth, 6022 Used); 6023 break; 6024 6025 case Type::LValueReference: 6026 case Type::RValueReference: 6027 MarkUsedTemplateParameters(Ctx, 6028 cast<ReferenceType>(T)->getPointeeType(), 6029 OnlyDeduced, 6030 Depth, 6031 Used); 6032 break; 6033 6034 case Type::MemberPointer: { 6035 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr()); 6036 MarkUsedTemplateParameters(Ctx, MemPtr->getPointeeType(), OnlyDeduced, 6037 Depth, Used); 6038 MarkUsedTemplateParameters(Ctx, QualType(MemPtr->getClass(), 0), 6039 OnlyDeduced, Depth, Used); 6040 break; 6041 } 6042 6043 case Type::DependentSizedArray: 6044 MarkUsedTemplateParameters(Ctx, 6045 cast<DependentSizedArrayType>(T)->getSizeExpr(), 6046 OnlyDeduced, Depth, Used); 6047 // Fall through to check the element type 6048 [[fallthrough]]; 6049 6050 case Type::ConstantArray: 6051 case Type::IncompleteArray: 6052 MarkUsedTemplateParameters(Ctx, 6053 cast<ArrayType>(T)->getElementType(), 6054 OnlyDeduced, Depth, Used); 6055 break; 6056 6057 case Type::Vector: 6058 case Type::ExtVector: 6059 MarkUsedTemplateParameters(Ctx, 6060 cast<VectorType>(T)->getElementType(), 6061 OnlyDeduced, Depth, Used); 6062 break; 6063 6064 case Type::DependentVector: { 6065 const auto *VecType = cast<DependentVectorType>(T); 6066 MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced, 6067 Depth, Used); 6068 MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced, Depth, 6069 Used); 6070 break; 6071 } 6072 case Type::DependentSizedExtVector: { 6073 const DependentSizedExtVectorType *VecType 6074 = cast<DependentSizedExtVectorType>(T); 6075 MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced, 6076 Depth, Used); 6077 MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced, 6078 Depth, Used); 6079 break; 6080 } 6081 6082 case Type::DependentAddressSpace: { 6083 const DependentAddressSpaceType *DependentASType = 6084 cast<DependentAddressSpaceType>(T); 6085 MarkUsedTemplateParameters(Ctx, DependentASType->getPointeeType(), 6086 OnlyDeduced, Depth, Used); 6087 MarkUsedTemplateParameters(Ctx, 6088 DependentASType->getAddrSpaceExpr(), 6089 OnlyDeduced, Depth, Used); 6090 break; 6091 } 6092 6093 case Type::ConstantMatrix: { 6094 const ConstantMatrixType *MatType = cast<ConstantMatrixType>(T); 6095 MarkUsedTemplateParameters(Ctx, MatType->getElementType(), OnlyDeduced, 6096 Depth, Used); 6097 break; 6098 } 6099 6100 case Type::DependentSizedMatrix: { 6101 const DependentSizedMatrixType *MatType = cast<DependentSizedMatrixType>(T); 6102 MarkUsedTemplateParameters(Ctx, MatType->getElementType(), OnlyDeduced, 6103 Depth, Used); 6104 MarkUsedTemplateParameters(Ctx, MatType->getRowExpr(), OnlyDeduced, Depth, 6105 Used); 6106 MarkUsedTemplateParameters(Ctx, MatType->getColumnExpr(), OnlyDeduced, 6107 Depth, Used); 6108 break; 6109 } 6110 6111 case Type::FunctionProto: { 6112 const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 6113 MarkUsedTemplateParameters(Ctx, Proto->getReturnType(), OnlyDeduced, Depth, 6114 Used); 6115 for (unsigned I = 0, N = Proto->getNumParams(); I != N; ++I) { 6116 // C++17 [temp.deduct.type]p5: 6117 // The non-deduced contexts are: [...] 6118 // -- A function parameter pack that does not occur at the end of the 6119 // parameter-declaration-list. 6120 if (!OnlyDeduced || I + 1 == N || 6121 !Proto->getParamType(I)->getAs<PackExpansionType>()) { 6122 MarkUsedTemplateParameters(Ctx, Proto->getParamType(I), OnlyDeduced, 6123 Depth, Used); 6124 } else { 6125 // FIXME: C++17 [temp.deduct.call]p1: 6126 // When a function parameter pack appears in a non-deduced context, 6127 // the type of that pack is never deduced. 6128 // 6129 // We should also track a set of "never deduced" parameters, and 6130 // subtract that from the list of deduced parameters after marking. 6131 } 6132 } 6133 if (auto *E = Proto->getNoexceptExpr()) 6134 MarkUsedTemplateParameters(Ctx, E, OnlyDeduced, Depth, Used); 6135 break; 6136 } 6137 6138 case Type::TemplateTypeParm: { 6139 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T); 6140 if (TTP->getDepth() == Depth) 6141 Used[TTP->getIndex()] = true; 6142 break; 6143 } 6144 6145 case Type::SubstTemplateTypeParmPack: { 6146 const SubstTemplateTypeParmPackType *Subst 6147 = cast<SubstTemplateTypeParmPackType>(T); 6148 if (Subst->getReplacedParameter()->getDepth() == Depth) 6149 Used[Subst->getIndex()] = true; 6150 MarkUsedTemplateParameters(Ctx, Subst->getArgumentPack(), 6151 OnlyDeduced, Depth, Used); 6152 break; 6153 } 6154 6155 case Type::InjectedClassName: 6156 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType(); 6157 [[fallthrough]]; 6158 6159 case Type::TemplateSpecialization: { 6160 const TemplateSpecializationType *Spec 6161 = cast<TemplateSpecializationType>(T); 6162 MarkUsedTemplateParameters(Ctx, Spec->getTemplateName(), OnlyDeduced, 6163 Depth, Used); 6164 6165 // C++0x [temp.deduct.type]p9: 6166 // If the template argument list of P contains a pack expansion that is 6167 // not the last template argument, the entire template argument list is a 6168 // non-deduced context. 6169 if (OnlyDeduced && 6170 hasPackExpansionBeforeEnd(Spec->template_arguments())) 6171 break; 6172 6173 for (const auto &Arg : Spec->template_arguments()) 6174 MarkUsedTemplateParameters(Ctx, Arg, OnlyDeduced, Depth, Used); 6175 break; 6176 } 6177 6178 case Type::Complex: 6179 if (!OnlyDeduced) 6180 MarkUsedTemplateParameters(Ctx, 6181 cast<ComplexType>(T)->getElementType(), 6182 OnlyDeduced, Depth, Used); 6183 break; 6184 6185 case Type::Atomic: 6186 if (!OnlyDeduced) 6187 MarkUsedTemplateParameters(Ctx, 6188 cast<AtomicType>(T)->getValueType(), 6189 OnlyDeduced, Depth, Used); 6190 break; 6191 6192 case Type::DependentName: 6193 if (!OnlyDeduced) 6194 MarkUsedTemplateParameters(Ctx, 6195 cast<DependentNameType>(T)->getQualifier(), 6196 OnlyDeduced, Depth, Used); 6197 break; 6198 6199 case Type::DependentTemplateSpecialization: { 6200 // C++14 [temp.deduct.type]p5: 6201 // The non-deduced contexts are: 6202 // -- The nested-name-specifier of a type that was specified using a 6203 // qualified-id 6204 // 6205 // C++14 [temp.deduct.type]p6: 6206 // When a type name is specified in a way that includes a non-deduced 6207 // context, all of the types that comprise that type name are also 6208 // non-deduced. 6209 if (OnlyDeduced) 6210 break; 6211 6212 const DependentTemplateSpecializationType *Spec 6213 = cast<DependentTemplateSpecializationType>(T); 6214 6215 MarkUsedTemplateParameters(Ctx, Spec->getQualifier(), 6216 OnlyDeduced, Depth, Used); 6217 6218 for (const auto &Arg : Spec->template_arguments()) 6219 MarkUsedTemplateParameters(Ctx, Arg, OnlyDeduced, Depth, Used); 6220 break; 6221 } 6222 6223 case Type::TypeOf: 6224 if (!OnlyDeduced) 6225 MarkUsedTemplateParameters(Ctx, cast<TypeOfType>(T)->getUnmodifiedType(), 6226 OnlyDeduced, Depth, Used); 6227 break; 6228 6229 case Type::TypeOfExpr: 6230 if (!OnlyDeduced) 6231 MarkUsedTemplateParameters(Ctx, 6232 cast<TypeOfExprType>(T)->getUnderlyingExpr(), 6233 OnlyDeduced, Depth, Used); 6234 break; 6235 6236 case Type::Decltype: 6237 if (!OnlyDeduced) 6238 MarkUsedTemplateParameters(Ctx, 6239 cast<DecltypeType>(T)->getUnderlyingExpr(), 6240 OnlyDeduced, Depth, Used); 6241 break; 6242 6243 case Type::UnaryTransform: 6244 if (!OnlyDeduced) 6245 MarkUsedTemplateParameters(Ctx, 6246 cast<UnaryTransformType>(T)->getUnderlyingType(), 6247 OnlyDeduced, Depth, Used); 6248 break; 6249 6250 case Type::PackExpansion: 6251 MarkUsedTemplateParameters(Ctx, 6252 cast<PackExpansionType>(T)->getPattern(), 6253 OnlyDeduced, Depth, Used); 6254 break; 6255 6256 case Type::Auto: 6257 case Type::DeducedTemplateSpecialization: 6258 MarkUsedTemplateParameters(Ctx, 6259 cast<DeducedType>(T)->getDeducedType(), 6260 OnlyDeduced, Depth, Used); 6261 break; 6262 case Type::DependentBitInt: 6263 MarkUsedTemplateParameters(Ctx, 6264 cast<DependentBitIntType>(T)->getNumBitsExpr(), 6265 OnlyDeduced, Depth, Used); 6266 break; 6267 6268 // None of these types have any template parameters in them. 6269 case Type::Builtin: 6270 case Type::VariableArray: 6271 case Type::FunctionNoProto: 6272 case Type::Record: 6273 case Type::Enum: 6274 case Type::ObjCInterface: 6275 case Type::ObjCObject: 6276 case Type::ObjCObjectPointer: 6277 case Type::UnresolvedUsing: 6278 case Type::Pipe: 6279 case Type::BitInt: 6280 #define TYPE(Class, Base) 6281 #define ABSTRACT_TYPE(Class, Base) 6282 #define DEPENDENT_TYPE(Class, Base) 6283 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 6284 #include "clang/AST/TypeNodes.inc" 6285 break; 6286 } 6287 } 6288 6289 /// Mark the template parameters that are used by this 6290 /// template argument. 6291 static void 6292 MarkUsedTemplateParameters(ASTContext &Ctx, 6293 const TemplateArgument &TemplateArg, 6294 bool OnlyDeduced, 6295 unsigned Depth, 6296 llvm::SmallBitVector &Used) { 6297 switch (TemplateArg.getKind()) { 6298 case TemplateArgument::Null: 6299 case TemplateArgument::Integral: 6300 case TemplateArgument::Declaration: 6301 break; 6302 6303 case TemplateArgument::NullPtr: 6304 MarkUsedTemplateParameters(Ctx, TemplateArg.getNullPtrType(), OnlyDeduced, 6305 Depth, Used); 6306 break; 6307 6308 case TemplateArgument::Type: 6309 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsType(), OnlyDeduced, 6310 Depth, Used); 6311 break; 6312 6313 case TemplateArgument::Template: 6314 case TemplateArgument::TemplateExpansion: 6315 MarkUsedTemplateParameters(Ctx, 6316 TemplateArg.getAsTemplateOrTemplatePattern(), 6317 OnlyDeduced, Depth, Used); 6318 break; 6319 6320 case TemplateArgument::Expression: 6321 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsExpr(), OnlyDeduced, 6322 Depth, Used); 6323 break; 6324 6325 case TemplateArgument::Pack: 6326 for (const auto &P : TemplateArg.pack_elements()) 6327 MarkUsedTemplateParameters(Ctx, P, OnlyDeduced, Depth, Used); 6328 break; 6329 } 6330 } 6331 6332 /// Mark which template parameters are used in a given expression. 6333 /// 6334 /// \param E the expression from which template parameters will be deduced. 6335 /// 6336 /// \param Used a bit vector whose elements will be set to \c true 6337 /// to indicate when the corresponding template parameter will be 6338 /// deduced. 6339 void 6340 Sema::MarkUsedTemplateParameters(const Expr *E, bool OnlyDeduced, 6341 unsigned Depth, 6342 llvm::SmallBitVector &Used) { 6343 ::MarkUsedTemplateParameters(Context, E, OnlyDeduced, Depth, Used); 6344 } 6345 6346 /// Mark which template parameters can be deduced from a given 6347 /// template argument list. 6348 /// 6349 /// \param TemplateArgs the template argument list from which template 6350 /// parameters will be deduced. 6351 /// 6352 /// \param Used a bit vector whose elements will be set to \c true 6353 /// to indicate when the corresponding template parameter will be 6354 /// deduced. 6355 void 6356 Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, 6357 bool OnlyDeduced, unsigned Depth, 6358 llvm::SmallBitVector &Used) { 6359 // C++0x [temp.deduct.type]p9: 6360 // If the template argument list of P contains a pack expansion that is not 6361 // the last template argument, the entire template argument list is a 6362 // non-deduced context. 6363 if (OnlyDeduced && 6364 hasPackExpansionBeforeEnd(TemplateArgs.asArray())) 6365 return; 6366 6367 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 6368 ::MarkUsedTemplateParameters(Context, TemplateArgs[I], OnlyDeduced, 6369 Depth, Used); 6370 } 6371 6372 /// Marks all of the template parameters that will be deduced by a 6373 /// call to the given function template. 6374 void Sema::MarkDeducedTemplateParameters( 6375 ASTContext &Ctx, const FunctionTemplateDecl *FunctionTemplate, 6376 llvm::SmallBitVector &Deduced) { 6377 TemplateParameterList *TemplateParams 6378 = FunctionTemplate->getTemplateParameters(); 6379 Deduced.clear(); 6380 Deduced.resize(TemplateParams->size()); 6381 6382 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl(); 6383 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) 6384 ::MarkUsedTemplateParameters(Ctx, Function->getParamDecl(I)->getType(), 6385 true, TemplateParams->getDepth(), Deduced); 6386 } 6387 6388 bool hasDeducibleTemplateParameters(Sema &S, 6389 FunctionTemplateDecl *FunctionTemplate, 6390 QualType T) { 6391 if (!T->isDependentType()) 6392 return false; 6393 6394 TemplateParameterList *TemplateParams 6395 = FunctionTemplate->getTemplateParameters(); 6396 llvm::SmallBitVector Deduced(TemplateParams->size()); 6397 ::MarkUsedTemplateParameters(S.Context, T, true, TemplateParams->getDepth(), 6398 Deduced); 6399 6400 return Deduced.any(); 6401 } 6402