1545 lines · cpp
1//===- SemaTemplateDeductionGude.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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements deduction guides for C++ class template argument10// deduction.11//12//===----------------------------------------------------------------------===//13 14#include "TreeTransform.h"15#include "TypeLocBuilder.h"16#include "clang/AST/ASTConsumer.h"17#include "clang/AST/ASTContext.h"18#include "clang/AST/Decl.h"19#include "clang/AST/DeclBase.h"20#include "clang/AST/DeclCXX.h"21#include "clang/AST/DeclFriend.h"22#include "clang/AST/DeclTemplate.h"23#include "clang/AST/DeclarationName.h"24#include "clang/AST/Expr.h"25#include "clang/AST/ExprCXX.h"26#include "clang/AST/OperationKinds.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/Basic/LLVM.h"32#include "clang/Basic/SourceLocation.h"33#include "clang/Basic/Specifiers.h"34#include "clang/Basic/TypeTraits.h"35#include "clang/Sema/DeclSpec.h"36#include "clang/Sema/Initialization.h"37#include "clang/Sema/Lookup.h"38#include "clang/Sema/Overload.h"39#include "clang/Sema/Ownership.h"40#include "clang/Sema/Scope.h"41#include "clang/Sema/SemaInternal.h"42#include "clang/Sema/Template.h"43#include "clang/Sema/TemplateDeduction.h"44#include "llvm/ADT/ArrayRef.h"45#include "llvm/ADT/STLExtras.h"46#include "llvm/ADT/SmallVector.h"47#include "llvm/Support/Casting.h"48#include "llvm/Support/ErrorHandling.h"49#include <cassert>50#include <optional>51#include <utility>52 53using namespace clang;54using namespace sema;55 56namespace {57/// Tree transform to "extract" a transformed type from a class template's58/// constructor to a deduction guide.59class ExtractTypeForDeductionGuide60 : public TreeTransform<ExtractTypeForDeductionGuide> {61 llvm::SmallVectorImpl<TypedefNameDecl *> &MaterializedTypedefs;62 ClassTemplateDecl *NestedPattern;63 const MultiLevelTemplateArgumentList *OuterInstantiationArgs;64 std::optional<TemplateDeclInstantiator> TypedefNameInstantiator;65 66public:67 typedef TreeTransform<ExtractTypeForDeductionGuide> Base;68 ExtractTypeForDeductionGuide(69 Sema &SemaRef,70 llvm::SmallVectorImpl<TypedefNameDecl *> &MaterializedTypedefs,71 ClassTemplateDecl *NestedPattern = nullptr,72 const MultiLevelTemplateArgumentList *OuterInstantiationArgs = nullptr)73 : Base(SemaRef), MaterializedTypedefs(MaterializedTypedefs),74 NestedPattern(NestedPattern),75 OuterInstantiationArgs(OuterInstantiationArgs) {76 if (OuterInstantiationArgs)77 TypedefNameInstantiator.emplace(78 SemaRef, SemaRef.getASTContext().getTranslationUnitDecl(),79 *OuterInstantiationArgs);80 }81 82 TypeSourceInfo *transform(TypeSourceInfo *TSI) { return TransformType(TSI); }83 84 /// Returns true if it's safe to substitute \p Typedef with85 /// \p OuterInstantiationArgs.86 bool mightReferToOuterTemplateParameters(TypedefNameDecl *Typedef) {87 if (!NestedPattern)88 return false;89 90 static auto WalkUp = [](DeclContext *DC, DeclContext *TargetDC) {91 if (DC->Equals(TargetDC))92 return true;93 while (DC->isRecord()) {94 if (DC->Equals(TargetDC))95 return true;96 DC = DC->getParent();97 }98 return false;99 };100 101 if (WalkUp(Typedef->getDeclContext(), NestedPattern->getTemplatedDecl()))102 return true;103 if (WalkUp(NestedPattern->getTemplatedDecl(), Typedef->getDeclContext()))104 return true;105 return false;106 }107 108 QualType RebuildTemplateSpecializationType(109 ElaboratedTypeKeyword Keyword, TemplateName Template,110 SourceLocation TemplateNameLoc, TemplateArgumentListInfo &TemplateArgs) {111 if (!OuterInstantiationArgs ||112 !isa_and_present<TypeAliasTemplateDecl>(Template.getAsTemplateDecl()))113 return Base::RebuildTemplateSpecializationType(114 Keyword, Template, TemplateNameLoc, TemplateArgs);115 116 auto *TATD = cast<TypeAliasTemplateDecl>(Template.getAsTemplateDecl());117 auto *Pattern = TATD;118 while (Pattern->getInstantiatedFromMemberTemplate())119 Pattern = Pattern->getInstantiatedFromMemberTemplate();120 if (!mightReferToOuterTemplateParameters(Pattern->getTemplatedDecl()))121 return Base::RebuildTemplateSpecializationType(122 Keyword, Template, TemplateNameLoc, TemplateArgs);123 124 Decl *NewD =125 TypedefNameInstantiator->InstantiateTypeAliasTemplateDecl(TATD);126 if (!NewD)127 return QualType();128 129 auto *NewTATD = cast<TypeAliasTemplateDecl>(NewD);130 MaterializedTypedefs.push_back(NewTATD->getTemplatedDecl());131 132 return Base::RebuildTemplateSpecializationType(133 Keyword, TemplateName(NewTATD), TemplateNameLoc, TemplateArgs);134 }135 136 QualType TransformTypedefType(TypeLocBuilder &TLB, TypedefTypeLoc TL) {137 ASTContext &Context = SemaRef.getASTContext();138 TypedefNameDecl *OrigDecl = TL.getDecl();139 TypedefNameDecl *Decl = OrigDecl;140 const TypedefType *T = TL.getTypePtr();141 // Transform the underlying type of the typedef and clone the Decl only if142 // the typedef has a dependent context.143 bool InDependentContext = OrigDecl->getDeclContext()->isDependentContext();144 145 // A typedef/alias Decl within the NestedPattern may reference the outer146 // template parameters. They're substituted with corresponding instantiation147 // arguments here and in RebuildTemplateSpecializationType() above.148 // Otherwise, we would have a CTAD guide with "dangling" template149 // parameters.150 // For example,151 // template <class T> struct Outer {152 // using Alias = S<T>;153 // template <class U> struct Inner {154 // Inner(Alias);155 // };156 // };157 if (OuterInstantiationArgs && InDependentContext &&158 T->isInstantiationDependentType()) {159 Decl = cast_if_present<TypedefNameDecl>(160 TypedefNameInstantiator->InstantiateTypedefNameDecl(161 OrigDecl, /*IsTypeAlias=*/isa<TypeAliasDecl>(OrigDecl)));162 if (!Decl)163 return QualType();164 MaterializedTypedefs.push_back(Decl);165 } else if (InDependentContext) {166 TypeLocBuilder InnerTLB;167 QualType Transformed =168 TransformType(InnerTLB, OrigDecl->getTypeSourceInfo()->getTypeLoc());169 TypeSourceInfo *TSI = InnerTLB.getTypeSourceInfo(Context, Transformed);170 if (isa<TypeAliasDecl>(OrigDecl))171 Decl = TypeAliasDecl::Create(172 Context, Context.getTranslationUnitDecl(), OrigDecl->getBeginLoc(),173 OrigDecl->getLocation(), OrigDecl->getIdentifier(), TSI);174 else {175 assert(isa<TypedefDecl>(OrigDecl) && "Not a Type alias or typedef");176 Decl = TypedefDecl::Create(177 Context, Context.getTranslationUnitDecl(), OrigDecl->getBeginLoc(),178 OrigDecl->getLocation(), OrigDecl->getIdentifier(), TSI);179 }180 MaterializedTypedefs.push_back(Decl);181 }182 183 NestedNameSpecifierLoc QualifierLoc = TL.getQualifierLoc();184 if (QualifierLoc) {185 QualifierLoc = getDerived().TransformNestedNameSpecifierLoc(QualifierLoc);186 if (!QualifierLoc)187 return QualType();188 }189 190 QualType TDTy = Context.getTypedefType(191 T->getKeyword(), QualifierLoc.getNestedNameSpecifier(), Decl);192 TLB.push<TypedefTypeLoc>(TDTy).set(TL.getElaboratedKeywordLoc(),193 QualifierLoc, TL.getNameLoc());194 return TDTy;195 }196};197 198// Build a deduction guide using the provided information.199//200// A deduction guide can be either a template or a non-template function201// declaration. If \p TemplateParams is null, a non-template function202// declaration will be created.203NamedDecl *204buildDeductionGuide(Sema &SemaRef, TemplateDecl *OriginalTemplate,205 TemplateParameterList *TemplateParams,206 CXXConstructorDecl *Ctor, ExplicitSpecifier ES,207 TypeSourceInfo *TInfo, SourceLocation LocStart,208 SourceLocation Loc, SourceLocation LocEnd, bool IsImplicit,209 llvm::ArrayRef<TypedefNameDecl *> MaterializedTypedefs = {},210 const AssociatedConstraint &FunctionTrailingRC = {}) {211 DeclContext *DC = OriginalTemplate->getDeclContext();212 auto DeductionGuideName =213 SemaRef.Context.DeclarationNames.getCXXDeductionGuideName(214 OriginalTemplate);215 216 DeclarationNameInfo Name(DeductionGuideName, Loc);217 ArrayRef<ParmVarDecl *> Params =218 TInfo->getTypeLoc().castAs<FunctionProtoTypeLoc>().getParams();219 220 // Build the implicit deduction guide template.221 auto *Guide = CXXDeductionGuideDecl::Create(222 SemaRef.Context, DC, LocStart, ES, Name, TInfo->getType(), TInfo, LocEnd,223 Ctor, DeductionCandidate::Normal, FunctionTrailingRC);224 Guide->setImplicit(IsImplicit);225 Guide->setParams(Params);226 227 for (auto *Param : Params)228 Param->setDeclContext(Guide);229 for (auto *TD : MaterializedTypedefs)230 TD->setDeclContext(Guide);231 if (isa<CXXRecordDecl>(DC))232 Guide->setAccess(AS_public);233 234 if (!TemplateParams) {235 DC->addDecl(Guide);236 return Guide;237 }238 239 auto *GuideTemplate = FunctionTemplateDecl::Create(240 SemaRef.Context, DC, Loc, DeductionGuideName, TemplateParams, Guide);241 GuideTemplate->setImplicit(IsImplicit);242 Guide->setDescribedFunctionTemplate(GuideTemplate);243 244 if (isa<CXXRecordDecl>(DC))245 GuideTemplate->setAccess(AS_public);246 247 DC->addDecl(GuideTemplate);248 return GuideTemplate;249}250 251// Transform a given template type parameter `TTP`.252TemplateTypeParmDecl *transformTemplateTypeParam(253 Sema &SemaRef, DeclContext *DC, TemplateTypeParmDecl *TTP,254 MultiLevelTemplateArgumentList &Args, unsigned NewDepth, unsigned NewIndex,255 bool EvaluateConstraint) {256 // TemplateTypeParmDecl's index cannot be changed after creation, so257 // substitute it directly.258 auto *NewTTP = TemplateTypeParmDecl::Create(259 SemaRef.Context, DC, TTP->getBeginLoc(), TTP->getLocation(), NewDepth,260 NewIndex, TTP->getIdentifier(), TTP->wasDeclaredWithTypename(),261 TTP->isParameterPack(), TTP->hasTypeConstraint(),262 TTP->getNumExpansionParameters());263 if (const auto *TC = TTP->getTypeConstraint())264 SemaRef.SubstTypeConstraint(NewTTP, TC, Args,265 /*EvaluateConstraint=*/EvaluateConstraint);266 if (TTP->hasDefaultArgument()) {267 TemplateArgumentLoc InstantiatedDefaultArg;268 if (!SemaRef.SubstTemplateArgument(269 TTP->getDefaultArgument(), Args, InstantiatedDefaultArg,270 TTP->getDefaultArgumentLoc(), TTP->getDeclName()))271 NewTTP->setDefaultArgument(SemaRef.Context, InstantiatedDefaultArg);272 }273 SemaRef.CurrentInstantiationScope->InstantiatedLocal(TTP, NewTTP);274 return NewTTP;275}276// Similar to above, but for non-type template or template template parameters.277template <typename NonTypeTemplateOrTemplateTemplateParmDecl>278NonTypeTemplateOrTemplateTemplateParmDecl *279transformTemplateParam(Sema &SemaRef, DeclContext *DC,280 NonTypeTemplateOrTemplateTemplateParmDecl *OldParam,281 MultiLevelTemplateArgumentList &Args, unsigned NewIndex,282 unsigned NewDepth) {283 // Ask the template instantiator to do the heavy lifting for us, then adjust284 // the index of the parameter once it's done.285 auto *NewParam = cast<NonTypeTemplateOrTemplateTemplateParmDecl>(286 SemaRef.SubstDecl(OldParam, DC, Args));287 NewParam->setPosition(NewIndex);288 NewParam->setDepth(NewDepth);289 return NewParam;290}291 292NamedDecl *transformTemplateParameter(Sema &SemaRef, DeclContext *DC,293 NamedDecl *TemplateParam,294 MultiLevelTemplateArgumentList &Args,295 unsigned NewIndex, unsigned NewDepth,296 bool EvaluateConstraint = true) {297 if (auto *TTP = dyn_cast<TemplateTypeParmDecl>(TemplateParam))298 return transformTemplateTypeParam(299 SemaRef, DC, TTP, Args, NewDepth, NewIndex,300 /*EvaluateConstraint=*/EvaluateConstraint);301 if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(TemplateParam))302 return transformTemplateParam(SemaRef, DC, TTP, Args, NewIndex, NewDepth);303 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(TemplateParam))304 return transformTemplateParam(SemaRef, DC, NTTP, Args, NewIndex, NewDepth);305 llvm_unreachable("Unhandled template parameter types");306}307 308/// Transform to convert portions of a constructor declaration into the309/// corresponding deduction guide, per C++1z [over.match.class.deduct]p1.310struct ConvertConstructorToDeductionGuideTransform {311 ConvertConstructorToDeductionGuideTransform(Sema &S,312 ClassTemplateDecl *Template)313 : SemaRef(S), Template(Template) {314 // If the template is nested, then we need to use the original315 // pattern to iterate over the constructors.316 ClassTemplateDecl *Pattern = Template;317 while (Pattern->getInstantiatedFromMemberTemplate()) {318 if (Pattern->isMemberSpecialization())319 break;320 Pattern = Pattern->getInstantiatedFromMemberTemplate();321 NestedPattern = Pattern;322 }323 324 if (NestedPattern)325 OuterInstantiationArgs = SemaRef.getTemplateInstantiationArgs(Template);326 }327 328 Sema &SemaRef;329 ClassTemplateDecl *Template;330 ClassTemplateDecl *NestedPattern = nullptr;331 332 DeclContext *DC = Template->getDeclContext();333 CXXRecordDecl *Primary = Template->getTemplatedDecl();334 DeclarationName DeductionGuideName =335 SemaRef.Context.DeclarationNames.getCXXDeductionGuideName(Template);336 337 QualType DeducedType = SemaRef.Context.getCanonicalTagType(Primary);338 339 // Index adjustment to apply to convert depth-1 template parameters into340 // depth-0 template parameters.341 unsigned Depth1IndexAdjustment = Template->getTemplateParameters()->size();342 343 // Instantiation arguments for the outermost depth-1 templates344 // when the template is nested345 MultiLevelTemplateArgumentList OuterInstantiationArgs;346 347 /// Transform a constructor declaration into a deduction guide.348 NamedDecl *transformConstructor(FunctionTemplateDecl *FTD,349 CXXConstructorDecl *CD) {350 SmallVector<TemplateArgument, 16> SubstArgs;351 352 LocalInstantiationScope Scope(SemaRef);353 354 // C++ [over.match.class.deduct]p1:355 // -- For each constructor of the class template designated by the356 // template-name, a function template with the following properties:357 358 // -- The template parameters are the template parameters of the class359 // template followed by the template parameters (including default360 // template arguments) of the constructor, if any.361 TemplateParameterList *TemplateParams =362 SemaRef.GetTemplateParameterList(Template);363 SmallVector<TemplateArgument, 16> Depth1Args;364 AssociatedConstraint OuterRC(TemplateParams->getRequiresClause());365 if (FTD) {366 TemplateParameterList *InnerParams = FTD->getTemplateParameters();367 SmallVector<NamedDecl *, 16> AllParams;368 AllParams.reserve(TemplateParams->size() + InnerParams->size());369 AllParams.insert(AllParams.begin(), TemplateParams->begin(),370 TemplateParams->end());371 SubstArgs.reserve(InnerParams->size());372 Depth1Args.reserve(InnerParams->size());373 374 // Later template parameters could refer to earlier ones, so build up375 // a list of substituted template arguments as we go.376 for (NamedDecl *Param : *InnerParams) {377 MultiLevelTemplateArgumentList Args;378 Args.setKind(TemplateSubstitutionKind::Rewrite);379 Args.addOuterTemplateArguments(Depth1Args);380 Args.addOuterRetainedLevel();381 if (NestedPattern)382 Args.addOuterRetainedLevels(NestedPattern->getTemplateDepth());383 auto [Depth, Index] = getDepthAndIndex(Param);384 // Depth can be 0 if FTD belongs to a non-template class/a class385 // template specialization with an empty template parameter list. In386 // that case, we don't want the NewDepth to overflow, and it should387 // remain 0.388 NamedDecl *NewParam = transformTemplateParameter(389 SemaRef, DC, Param, Args, Index + Depth1IndexAdjustment,390 Depth ? Depth - 1 : 0);391 if (!NewParam)392 return nullptr;393 // Constraints require that we substitute depth-1 arguments394 // to match depths when substituted for evaluation later395 Depth1Args.push_back(SemaRef.Context.getInjectedTemplateArg(NewParam));396 397 if (NestedPattern) {398 auto [Depth, Index] = getDepthAndIndex(NewParam);399 NewParam = transformTemplateParameter(400 SemaRef, DC, NewParam, OuterInstantiationArgs, Index,401 Depth - OuterInstantiationArgs.getNumSubstitutedLevels(),402 /*EvaluateConstraint=*/false);403 }404 405 assert(getDepthAndIndex(NewParam).first == 0 &&406 "Unexpected template parameter depth");407 408 AllParams.push_back(NewParam);409 SubstArgs.push_back(SemaRef.Context.getInjectedTemplateArg(NewParam));410 }411 412 // Substitute new template parameters into requires-clause if present.413 Expr *RequiresClause = nullptr;414 if (Expr *InnerRC = InnerParams->getRequiresClause()) {415 MultiLevelTemplateArgumentList Args;416 Args.setKind(TemplateSubstitutionKind::Rewrite);417 Args.addOuterTemplateArguments(Depth1Args);418 Args.addOuterRetainedLevel();419 if (NestedPattern)420 Args.addOuterRetainedLevels(NestedPattern->getTemplateDepth());421 ExprResult E =422 SemaRef.SubstConstraintExprWithoutSatisfaction(InnerRC, Args);423 if (!E.isUsable())424 return nullptr;425 RequiresClause = E.get();426 }427 428 TemplateParams = TemplateParameterList::Create(429 SemaRef.Context, InnerParams->getTemplateLoc(),430 InnerParams->getLAngleLoc(), AllParams, InnerParams->getRAngleLoc(),431 RequiresClause);432 }433 434 // If we built a new template-parameter-list, track that we need to435 // substitute references to the old parameters into references to the436 // new ones.437 MultiLevelTemplateArgumentList Args;438 Args.setKind(TemplateSubstitutionKind::Rewrite);439 if (FTD) {440 Args.addOuterTemplateArguments(SubstArgs);441 Args.addOuterRetainedLevel();442 }443 444 FunctionProtoTypeLoc FPTL = CD->getTypeSourceInfo()445 ->getTypeLoc()446 .getAsAdjusted<FunctionProtoTypeLoc>();447 assert(FPTL && "no prototype for constructor declaration");448 449 // Transform the type of the function, adjusting the return type and450 // replacing references to the old parameters with references to the451 // new ones.452 TypeLocBuilder TLB;453 SmallVector<ParmVarDecl *, 8> Params;454 SmallVector<TypedefNameDecl *, 4> MaterializedTypedefs;455 QualType NewType = transformFunctionProtoType(TLB, FPTL, Params, Args,456 MaterializedTypedefs);457 if (NewType.isNull())458 return nullptr;459 TypeSourceInfo *NewTInfo = TLB.getTypeSourceInfo(SemaRef.Context, NewType);460 461 // At this point, the function parameters are already 'instantiated' in the462 // current scope. Substitute into the constructor's trailing463 // requires-clause, if any.464 AssociatedConstraint FunctionTrailingRC;465 if (const AssociatedConstraint &RC = CD->getTrailingRequiresClause()) {466 MultiLevelTemplateArgumentList Args;467 Args.setKind(TemplateSubstitutionKind::Rewrite);468 Args.addOuterTemplateArguments(Depth1Args);469 Args.addOuterRetainedLevel();470 if (NestedPattern)471 Args.addOuterRetainedLevels(NestedPattern->getTemplateDepth());472 ExprResult E = SemaRef.SubstConstraintExprWithoutSatisfaction(473 const_cast<Expr *>(RC.ConstraintExpr), Args);474 if (!E.isUsable())475 return nullptr;476 FunctionTrailingRC = AssociatedConstraint(E.get(), RC.ArgPackSubstIndex);477 }478 479 // C++ [over.match.class.deduct]p1:480 // If C is defined, for each constructor of C, a function template with481 // the following properties:482 // [...]483 // - The associated constraints are the conjunction of the associated484 // constraints of C and the associated constraints of the constructor, if485 // any.486 if (OuterRC) {487 // The outer template parameters are not transformed, so their488 // associated constraints don't need substitution.489 // FIXME: Should simply add another field for the OuterRC, instead of490 // combining them like this.491 if (!FunctionTrailingRC)492 FunctionTrailingRC = OuterRC;493 else494 FunctionTrailingRC = AssociatedConstraint(495 BinaryOperator::Create(496 SemaRef.Context,497 /*lhs=*/const_cast<Expr *>(OuterRC.ConstraintExpr),498 /*rhs=*/const_cast<Expr *>(FunctionTrailingRC.ConstraintExpr),499 BO_LAnd, SemaRef.Context.BoolTy, VK_PRValue, OK_Ordinary,500 TemplateParams->getTemplateLoc(), FPOptionsOverride()),501 FunctionTrailingRC.ArgPackSubstIndex);502 }503 504 return buildDeductionGuide(505 SemaRef, Template, TemplateParams, CD, CD->getExplicitSpecifier(),506 NewTInfo, CD->getBeginLoc(), CD->getLocation(), CD->getEndLoc(),507 /*IsImplicit=*/true, MaterializedTypedefs, FunctionTrailingRC);508 }509 510 /// Build a deduction guide with the specified parameter types.511 NamedDecl *buildSimpleDeductionGuide(MutableArrayRef<QualType> ParamTypes) {512 SourceLocation Loc = Template->getLocation();513 514 // Build the requested type.515 FunctionProtoType::ExtProtoInfo EPI;516 EPI.HasTrailingReturn = true;517 QualType Result = SemaRef.BuildFunctionType(DeducedType, ParamTypes, Loc,518 DeductionGuideName, EPI);519 TypeSourceInfo *TSI = SemaRef.Context.getTrivialTypeSourceInfo(Result, Loc);520 if (NestedPattern)521 TSI = SemaRef.SubstType(TSI, OuterInstantiationArgs, Loc,522 DeductionGuideName);523 524 if (!TSI)525 return nullptr;526 527 FunctionProtoTypeLoc FPTL =528 TSI->getTypeLoc().castAs<FunctionProtoTypeLoc>();529 530 // Build the parameters, needed during deduction / substitution.531 SmallVector<ParmVarDecl *, 4> Params;532 for (auto T : ParamTypes) {533 auto *TSI = SemaRef.Context.getTrivialTypeSourceInfo(T, Loc);534 if (NestedPattern)535 TSI = SemaRef.SubstType(TSI, OuterInstantiationArgs, Loc,536 DeclarationName());537 if (!TSI)538 return nullptr;539 540 ParmVarDecl *NewParam =541 ParmVarDecl::Create(SemaRef.Context, DC, Loc, Loc, nullptr,542 TSI->getType(), TSI, SC_None, nullptr);543 NewParam->setScopeInfo(0, Params.size());544 FPTL.setParam(Params.size(), NewParam);545 Params.push_back(NewParam);546 }547 548 return buildDeductionGuide(549 SemaRef, Template, SemaRef.GetTemplateParameterList(Template), nullptr,550 ExplicitSpecifier(), TSI, Loc, Loc, Loc, /*IsImplicit=*/true);551 }552 553private:554 QualType transformFunctionProtoType(555 TypeLocBuilder &TLB, FunctionProtoTypeLoc TL,556 SmallVectorImpl<ParmVarDecl *> &Params,557 MultiLevelTemplateArgumentList &Args,558 SmallVectorImpl<TypedefNameDecl *> &MaterializedTypedefs) {559 SmallVector<QualType, 4> ParamTypes;560 const FunctionProtoType *T = TL.getTypePtr();561 562 // -- The types of the function parameters are those of the constructor.563 for (auto *OldParam : TL.getParams()) {564 ParmVarDecl *NewParam = OldParam;565 // Given566 // template <class T> struct C {567 // template <class U> struct D {568 // template <class V> D(U, V);569 // };570 // };571 // First, transform all the references to template parameters that are572 // defined outside of the surrounding class template. That is T in the573 // above example.574 if (NestedPattern) {575 NewParam = transformFunctionTypeParam(576 NewParam, OuterInstantiationArgs, MaterializedTypedefs,577 /*TransformingOuterPatterns=*/true);578 if (!NewParam)579 return QualType();580 }581 // Then, transform all the references to template parameters that are582 // defined at the class template and the constructor. In this example,583 // they're U and V, respectively.584 NewParam =585 transformFunctionTypeParam(NewParam, Args, MaterializedTypedefs,586 /*TransformingOuterPatterns=*/false);587 if (!NewParam)588 return QualType();589 ParamTypes.push_back(NewParam->getType());590 Params.push_back(NewParam);591 }592 593 // -- The return type is the class template specialization designated by594 // the template-name and template arguments corresponding to the595 // template parameters obtained from the class template.596 //597 // We use the injected-class-name type of the primary template instead.598 // This has the convenient property that it is different from any type that599 // the user can write in a deduction-guide (because they cannot enter the600 // context of the template), so implicit deduction guides can never collide601 // with explicit ones.602 QualType ReturnType = DeducedType;603 auto TTL = TLB.push<TagTypeLoc>(ReturnType);604 TTL.setElaboratedKeywordLoc(SourceLocation());605 TTL.setQualifierLoc(NestedNameSpecifierLoc());606 TTL.setNameLoc(Primary->getLocation());607 608 // Resolving a wording defect, we also inherit the variadicness of the609 // constructor.610 FunctionProtoType::ExtProtoInfo EPI;611 EPI.Variadic = T->isVariadic();612 EPI.HasTrailingReturn = true;613 614 QualType Result = SemaRef.BuildFunctionType(615 ReturnType, ParamTypes, TL.getBeginLoc(), DeductionGuideName, EPI);616 if (Result.isNull())617 return QualType();618 619 FunctionProtoTypeLoc NewTL = TLB.push<FunctionProtoTypeLoc>(Result);620 NewTL.setLocalRangeBegin(TL.getLocalRangeBegin());621 NewTL.setLParenLoc(TL.getLParenLoc());622 NewTL.setRParenLoc(TL.getRParenLoc());623 NewTL.setExceptionSpecRange(SourceRange());624 NewTL.setLocalRangeEnd(TL.getLocalRangeEnd());625 for (unsigned I = 0, E = NewTL.getNumParams(); I != E; ++I)626 NewTL.setParam(I, Params[I]);627 628 return Result;629 }630 631 ParmVarDecl *transformFunctionTypeParam(632 ParmVarDecl *OldParam, MultiLevelTemplateArgumentList &Args,633 llvm::SmallVectorImpl<TypedefNameDecl *> &MaterializedTypedefs,634 bool TransformingOuterPatterns) {635 TypeSourceInfo *OldTSI = OldParam->getTypeSourceInfo();636 TypeSourceInfo *NewTSI;637 if (auto PackTL = OldTSI->getTypeLoc().getAs<PackExpansionTypeLoc>()) {638 // Expand out the one and only element in each inner pack.639 Sema::ArgPackSubstIndexRAII SubstIndex(SemaRef, 0u);640 NewTSI =641 SemaRef.SubstType(PackTL.getPatternLoc(), Args,642 OldParam->getLocation(), OldParam->getDeclName());643 if (!NewTSI)644 return nullptr;645 NewTSI =646 SemaRef.CheckPackExpansion(NewTSI, PackTL.getEllipsisLoc(),647 PackTL.getTypePtr()->getNumExpansions());648 } else649 NewTSI = SemaRef.SubstType(OldTSI, Args, OldParam->getLocation(),650 OldParam->getDeclName());651 if (!NewTSI)652 return nullptr;653 654 // Extract the type. This (for instance) replaces references to typedef655 // members of the current instantiations with the definitions of those656 // typedefs, avoiding triggering instantiation of the deduced type during657 // deduction.658 NewTSI = ExtractTypeForDeductionGuide(659 SemaRef, MaterializedTypedefs, NestedPattern,660 TransformingOuterPatterns ? &Args : nullptr)661 .transform(NewTSI);662 if (!NewTSI)663 return nullptr;664 // Resolving a wording defect, we also inherit default arguments from the665 // constructor.666 ExprResult NewDefArg;667 if (OldParam->hasDefaultArg()) {668 // We don't care what the value is (we won't use it); just create a669 // placeholder to indicate there is a default argument.670 QualType ParamTy = NewTSI->getType();671 NewDefArg = new (SemaRef.Context)672 OpaqueValueExpr(OldParam->getDefaultArgRange().getBegin(),673 ParamTy.getNonLValueExprType(SemaRef.Context),674 ParamTy->isLValueReferenceType() ? VK_LValue675 : ParamTy->isRValueReferenceType() ? VK_XValue676 : VK_PRValue);677 }678 // Handle arrays and functions decay.679 auto NewType = NewTSI->getType();680 if (NewType->isArrayType() || NewType->isFunctionType())681 NewType = SemaRef.Context.getDecayedType(NewType);682 683 ParmVarDecl *NewParam = ParmVarDecl::Create(684 SemaRef.Context, DC, OldParam->getInnerLocStart(),685 OldParam->getLocation(), OldParam->getIdentifier(), NewType, NewTSI,686 OldParam->getStorageClass(), NewDefArg.get());687 NewParam->setScopeInfo(OldParam->getFunctionScopeDepth(),688 OldParam->getFunctionScopeIndex());689 SemaRef.CurrentInstantiationScope->InstantiatedLocal(OldParam, NewParam);690 return NewParam;691 }692};693 694// Find all template parameters that appear in the given DeducedArgs.695// Return the indices of the template parameters in the TemplateParams.696SmallVector<unsigned> TemplateParamsReferencedInTemplateArgumentList(697 Sema &SemaRef, const TemplateParameterList *TemplateParamsList,698 ArrayRef<TemplateArgument> DeducedArgs) {699 700 llvm::SmallBitVector ReferencedTemplateParams(TemplateParamsList->size());701 SemaRef.MarkUsedTemplateParameters(702 DeducedArgs, TemplateParamsList->getDepth(), ReferencedTemplateParams);703 704 auto MarkDefaultArgs = [&](auto *Param) {705 if (!Param->hasDefaultArgument())706 return;707 SemaRef.MarkUsedTemplateParameters(708 Param->getDefaultArgument().getArgument(),709 TemplateParamsList->getDepth(), ReferencedTemplateParams);710 };711 712 for (unsigned Index = 0; Index < TemplateParamsList->size(); ++Index) {713 if (!ReferencedTemplateParams[Index])714 continue;715 auto *Param = TemplateParamsList->getParam(Index);716 if (auto *TTPD = dyn_cast<TemplateTypeParmDecl>(Param))717 MarkDefaultArgs(TTPD);718 else if (auto *NTTPD = dyn_cast<NonTypeTemplateParmDecl>(Param))719 MarkDefaultArgs(NTTPD);720 else721 MarkDefaultArgs(cast<TemplateTemplateParmDecl>(Param));722 }723 724 SmallVector<unsigned> Results;725 for (unsigned Index = 0; Index < TemplateParamsList->size(); ++Index) {726 if (ReferencedTemplateParams[Index])727 Results.push_back(Index);728 }729 return Results;730}731 732bool hasDeclaredDeductionGuides(DeclarationName Name, DeclContext *DC) {733 // Check whether we've already declared deduction guides for this template.734 // FIXME: Consider storing a flag on the template to indicate this.735 assert(Name.getNameKind() ==736 DeclarationName::NameKind::CXXDeductionGuideName &&737 "name must be a deduction guide name");738 auto Existing = DC->lookup(Name);739 for (auto *D : Existing)740 if (D->isImplicit())741 return true;742 return false;743}744 745// Returns all source deduction guides associated with the declared746// deduction guides that have the specified deduction guide name.747llvm::DenseSet<const NamedDecl *> getSourceDeductionGuides(DeclarationName Name,748 DeclContext *DC) {749 assert(Name.getNameKind() ==750 DeclarationName::NameKind::CXXDeductionGuideName &&751 "name must be a deduction guide name");752 llvm::DenseSet<const NamedDecl *> Result;753 for (auto *D : DC->lookup(Name)) {754 if (const auto *FTD = dyn_cast<FunctionTemplateDecl>(D))755 D = FTD->getTemplatedDecl();756 757 if (const auto *GD = dyn_cast<CXXDeductionGuideDecl>(D)) {758 assert(GD->getSourceDeductionGuide() &&759 "deduction guide for alias template must have a source deduction "760 "guide");761 Result.insert(GD->getSourceDeductionGuide());762 }763 }764 return Result;765}766 767// Build the associated constraints for the alias deduction guides.768// C++ [over.match.class.deduct]p3.3:769// The associated constraints ([temp.constr.decl]) are the conjunction of the770// associated constraints of g and a constraint that is satisfied if and only771// if the arguments of A are deducible (see below) from the return type.772//773// The return result is expected to be the require-clause for the synthesized774// alias deduction guide.775Expr *776buildAssociatedConstraints(Sema &SemaRef, FunctionTemplateDecl *F,777 TypeAliasTemplateDecl *AliasTemplate,778 ArrayRef<DeducedTemplateArgument> DeduceResults,779 unsigned FirstUndeducedParamIdx, Expr *IsDeducible) {780 Expr *RC = F->getTemplateParameters()->getRequiresClause();781 if (!RC)782 return IsDeducible;783 784 ASTContext &Context = SemaRef.Context;785 LocalInstantiationScope Scope(SemaRef);786 787 // In the clang AST, constraint nodes are deliberately not instantiated unless788 // they are actively being evaluated. Consequently, occurrences of template789 // parameters in the require-clause expression have a subtle "depth"790 // difference compared to normal occurrences in places, such as function791 // parameters. When transforming the require-clause, we must take this792 // distinction into account:793 //794 // 1) In the transformed require-clause, occurrences of template parameters795 // must use the "uninstantiated" depth;796 // 2) When substituting on the require-clause expr of the underlying797 // deduction guide, we must use the entire set of template argument lists;798 //799 // It's important to note that we're performing this transformation on an800 // *instantiated* AliasTemplate.801 802 // For 1), if the alias template is nested within a class template, we803 // calcualte the 'uninstantiated' depth by adding the substitution level back.804 unsigned AdjustDepth = 0;805 if (auto *PrimaryTemplate =806 AliasTemplate->getInstantiatedFromMemberTemplate())807 AdjustDepth = PrimaryTemplate->getTemplateDepth();808 809 // We rebuild all template parameters with the uninstantiated depth, and810 // build template arguments refer to them.811 SmallVector<TemplateArgument> AdjustedAliasTemplateArgs;812 813 for (auto *TP : *AliasTemplate->getTemplateParameters()) {814 // Rebuild any internal references to earlier parameters and reindex815 // as we go.816 MultiLevelTemplateArgumentList Args;817 Args.setKind(TemplateSubstitutionKind::Rewrite);818 Args.addOuterTemplateArguments(AdjustedAliasTemplateArgs);819 NamedDecl *NewParam = transformTemplateParameter(820 SemaRef, AliasTemplate->getDeclContext(), TP, Args,821 /*NewIndex=*/AdjustedAliasTemplateArgs.size(),822 getDepthAndIndex(TP).first + AdjustDepth);823 824 TemplateArgument NewTemplateArgument =825 Context.getInjectedTemplateArg(NewParam);826 AdjustedAliasTemplateArgs.push_back(NewTemplateArgument);827 }828 // Template arguments used to transform the template arguments in829 // DeducedResults.830 SmallVector<TemplateArgument> TemplateArgsForBuildingRC(831 F->getTemplateParameters()->size());832 // Transform the transformed template args833 MultiLevelTemplateArgumentList Args;834 Args.setKind(TemplateSubstitutionKind::Rewrite);835 Args.addOuterTemplateArguments(AdjustedAliasTemplateArgs);836 837 for (unsigned Index = 0; Index < DeduceResults.size(); ++Index) {838 const auto &D = DeduceResults[Index];839 if (D.isNull()) { // non-deduced template parameters of f840 NamedDecl *TP = F->getTemplateParameters()->getParam(Index);841 MultiLevelTemplateArgumentList Args;842 Args.setKind(TemplateSubstitutionKind::Rewrite);843 Args.addOuterTemplateArguments(TemplateArgsForBuildingRC);844 // Rebuild the template parameter with updated depth and index.845 NamedDecl *NewParam =846 transformTemplateParameter(SemaRef, F->getDeclContext(), TP, Args,847 /*NewIndex=*/FirstUndeducedParamIdx,848 getDepthAndIndex(TP).first + AdjustDepth);849 FirstUndeducedParamIdx += 1;850 assert(TemplateArgsForBuildingRC[Index].isNull());851 TemplateArgsForBuildingRC[Index] =852 Context.getInjectedTemplateArg(NewParam);853 continue;854 }855 TemplateArgumentLoc Input =856 SemaRef.getTrivialTemplateArgumentLoc(D, QualType(), SourceLocation{});857 TemplateArgumentLoc Output;858 if (!SemaRef.SubstTemplateArgument(Input, Args, Output)) {859 assert(TemplateArgsForBuildingRC[Index].isNull() &&860 "InstantiatedArgs must be null before setting");861 TemplateArgsForBuildingRC[Index] = Output.getArgument();862 }863 }864 865 // A list of template arguments for transforming the require-clause of F.866 // It must contain the entire set of template argument lists.867 MultiLevelTemplateArgumentList ArgsForBuildingRC;868 ArgsForBuildingRC.setKind(clang::TemplateSubstitutionKind::Rewrite);869 ArgsForBuildingRC.addOuterTemplateArguments(TemplateArgsForBuildingRC);870 // For 2), if the underlying deduction guide F is nested in a class template,871 // we need the entire template argument list, as the constraint AST in the872 // require-clause of F remains completely uninstantiated.873 //874 // For example:875 // template <typename T> // depth 0876 // struct Outer {877 // template <typename U>878 // struct Foo { Foo(U); };879 //880 // template <typename U> // depth 1881 // requires C<U>882 // Foo(U) -> Foo<int>;883 // };884 // template <typename U>885 // using AFoo = Outer<int>::Foo<U>;886 //887 // In this scenario, the deduction guide for `Foo` inside `Outer<int>`:888 // - The occurrence of U in the require-expression is [depth:1, index:0]889 // - The occurrence of U in the function parameter is [depth:0, index:0]890 // - The template parameter of U is [depth:0, index:0]891 //892 // We add the outer template arguments which is [int] to the multi-level arg893 // list to ensure that the occurrence U in `C<U>` will be replaced with int894 // during the substitution.895 //896 // NOTE: The underlying deduction guide F is instantiated -- either from an897 // explicitly-written deduction guide member, or from a constructor.898 // getInstantiatedFromMemberTemplate() can only handle the former case, so we899 // check the DeclContext kind.900 if (F->getLexicalDeclContext()->getDeclKind() ==901 clang::Decl::ClassTemplateSpecialization) {902 auto OuterLevelArgs = SemaRef.getTemplateInstantiationArgs(903 F, F->getLexicalDeclContext(),904 /*Final=*/false, /*Innermost=*/std::nullopt,905 /*RelativeToPrimary=*/true,906 /*Pattern=*/nullptr,907 /*ForConstraintInstantiation=*/true);908 for (auto It : OuterLevelArgs)909 ArgsForBuildingRC.addOuterTemplateArguments(It.Args);910 }911 912 ExprResult E = SemaRef.SubstExpr(RC, ArgsForBuildingRC);913 if (E.isInvalid())914 return nullptr;915 916 auto Conjunction =917 SemaRef.BuildBinOp(SemaRef.getCurScope(), SourceLocation{},918 BinaryOperatorKind::BO_LAnd, E.get(), IsDeducible);919 if (Conjunction.isInvalid())920 return nullptr;921 return Conjunction.getAs<Expr>();922}923// Build the is_deducible constraint for the alias deduction guides.924// [over.match.class.deduct]p3.3:925// ... and a constraint that is satisfied if and only if the arguments926// of A are deducible (see below) from the return type.927Expr *buildIsDeducibleConstraint(Sema &SemaRef,928 TypeAliasTemplateDecl *AliasTemplate,929 QualType ReturnType,930 SmallVector<NamedDecl *> TemplateParams) {931 ASTContext &Context = SemaRef.Context;932 // Constraint AST nodes must use uninstantiated depth.933 if (auto *PrimaryTemplate =934 AliasTemplate->getInstantiatedFromMemberTemplate();935 PrimaryTemplate && TemplateParams.size() > 0) {936 LocalInstantiationScope Scope(SemaRef);937 938 // Adjust the depth for TemplateParams.939 unsigned AdjustDepth = PrimaryTemplate->getTemplateDepth();940 SmallVector<TemplateArgument> TransformedTemplateArgs;941 for (auto *TP : TemplateParams) {942 // Rebuild any internal references to earlier parameters and reindex943 // as we go.944 MultiLevelTemplateArgumentList Args;945 Args.setKind(TemplateSubstitutionKind::Rewrite);946 Args.addOuterTemplateArguments(TransformedTemplateArgs);947 NamedDecl *NewParam = transformTemplateParameter(948 SemaRef, AliasTemplate->getDeclContext(), TP, Args,949 /*NewIndex=*/TransformedTemplateArgs.size(),950 getDepthAndIndex(TP).first + AdjustDepth);951 952 TemplateArgument NewTemplateArgument =953 Context.getInjectedTemplateArg(NewParam);954 TransformedTemplateArgs.push_back(NewTemplateArgument);955 }956 // Transformed the ReturnType to restore the uninstantiated depth.957 MultiLevelTemplateArgumentList Args;958 Args.setKind(TemplateSubstitutionKind::Rewrite);959 Args.addOuterTemplateArguments(TransformedTemplateArgs);960 ReturnType = SemaRef.SubstType(961 ReturnType, Args, AliasTemplate->getLocation(),962 Context.DeclarationNames.getCXXDeductionGuideName(AliasTemplate));963 }964 965 SmallVector<TypeSourceInfo *> IsDeducibleTypeTraitArgs = {966 Context.getTrivialTypeSourceInfo(967 Context.getDeducedTemplateSpecializationType(968 ElaboratedTypeKeyword::None, TemplateName(AliasTemplate),969 /*DeducedType=*/QualType(),970 /*IsDependent=*/true),971 AliasTemplate->getLocation()), // template specialization type whose972 // arguments will be deduced.973 Context.getTrivialTypeSourceInfo(974 ReturnType, AliasTemplate->getLocation()), // type from which template975 // arguments are deduced.976 };977 return TypeTraitExpr::Create(978 Context, Context.getLogicalOperationType(), AliasTemplate->getLocation(),979 TypeTrait::BTT_IsDeducible, IsDeducibleTypeTraitArgs,980 AliasTemplate->getLocation(), /*Value*/ false);981}982 983std::pair<TemplateDecl *, llvm::ArrayRef<TemplateArgument>>984getRHSTemplateDeclAndArgs(Sema &SemaRef, TypeAliasTemplateDecl *AliasTemplate) {985 auto RhsType = AliasTemplate->getTemplatedDecl()->getUnderlyingType();986 TemplateDecl *Template = nullptr;987 llvm::ArrayRef<TemplateArgument> AliasRhsTemplateArgs;988 if (const auto *TST = RhsType->getAs<TemplateSpecializationType>()) {989 // Cases where the RHS of the alias is dependent. e.g.990 // template<typename T>991 // using AliasFoo1 = Foo<T>; // a class/type alias template specialization992 Template = TST->getTemplateName().getAsTemplateDecl();993 AliasRhsTemplateArgs =994 TST->getAsNonAliasTemplateSpecializationType()->template_arguments();995 } else if (const auto *RT = RhsType->getAs<RecordType>()) {996 // Cases where template arguments in the RHS of the alias are not997 // dependent. e.g.998 // using AliasFoo = Foo<bool>;999 if (const auto *CTSD =1000 dyn_cast<ClassTemplateSpecializationDecl>(RT->getDecl())) {1001 Template = CTSD->getSpecializedTemplate();1002 AliasRhsTemplateArgs = CTSD->getTemplateArgs().asArray();1003 }1004 }1005 return {Template, AliasRhsTemplateArgs};1006}1007 1008bool IsNonDeducedArgument(const TemplateArgument &TA) {1009 // The following cases indicate the template argument is non-deducible:1010 // 1. The result is null. E.g. When it comes from a default template1011 // argument that doesn't appear in the alias declaration.1012 // 2. The template parameter is a pack and that cannot be deduced from1013 // the arguments within the alias declaration.1014 // Non-deducible template parameters will persist in the transformed1015 // deduction guide.1016 return TA.isNull() ||1017 (TA.getKind() == TemplateArgument::Pack &&1018 llvm::any_of(TA.pack_elements(), IsNonDeducedArgument));1019}1020 1021// Build deduction guides for a type alias template from the given underlying1022// deduction guide F.1023FunctionTemplateDecl *1024BuildDeductionGuideForTypeAlias(Sema &SemaRef,1025 TypeAliasTemplateDecl *AliasTemplate,1026 FunctionTemplateDecl *F, SourceLocation Loc) {1027 LocalInstantiationScope Scope(SemaRef);1028 Sema::NonSFINAEContext _1(SemaRef);1029 Sema::InstantiatingTemplate BuildingDeductionGuides(1030 SemaRef, AliasTemplate->getLocation(), F,1031 Sema::InstantiatingTemplate::BuildingDeductionGuidesTag{});1032 if (BuildingDeductionGuides.isInvalid())1033 return nullptr;1034 1035 auto &Context = SemaRef.Context;1036 auto [Template, AliasRhsTemplateArgs] =1037 getRHSTemplateDeclAndArgs(SemaRef, AliasTemplate);1038 1039 // We need both types desugared, before we continue to perform type deduction.1040 // The intent is to get the template argument list 'matched', e.g. in the1041 // following case:1042 //1043 //1044 // template <class T>1045 // struct A {};1046 // template <class T>1047 // using Foo = A<A<T>>;1048 // template <class U = int>1049 // using Bar = Foo<U>;1050 //1051 // In terms of Bar, we want U (which has the default argument) to appear in1052 // the synthesized deduction guide, but U would remain undeduced if we deduced1053 // A<A<T>> using Foo<U> directly.1054 //1055 // Instead, we need to canonicalize both against A, i.e. A<A<T>> and A<A<U>>,1056 // such that T can be deduced as U.1057 auto RType = F->getTemplatedDecl()->getReturnType();1058 // The (trailing) return type of the deduction guide.1059 const auto *FReturnType = RType->getAs<TemplateSpecializationType>();1060 if (const auto *ICNT = RType->getAsCanonical<InjectedClassNameType>())1061 // implicitly-generated deduction guide.1062 FReturnType = cast<TemplateSpecializationType>(1063 ICNT->getDecl()->getCanonicalTemplateSpecializationType(1064 SemaRef.Context));1065 assert(FReturnType && "expected to see a return type");1066 // Deduce template arguments of the deduction guide f from the RHS of1067 // the alias.1068 //1069 // C++ [over.match.class.deduct]p3: ...For each function or function1070 // template f in the guides of the template named by the1071 // simple-template-id of the defining-type-id, the template arguments1072 // of the return type of f are deduced from the defining-type-id of A1073 // according to the process in [temp.deduct.type] with the exception1074 // that deduction does not fail if not all template arguments are1075 // deduced.1076 //1077 //1078 // template<typename X, typename Y>1079 // f(X, Y) -> f<Y, X>;1080 //1081 // template<typename U>1082 // using alias = f<int, U>;1083 //1084 // The RHS of alias is f<int, U>, we deduced the template arguments of1085 // the return type of the deduction guide from it: Y->int, X->U1086 sema::TemplateDeductionInfo TDeduceInfo(Loc);1087 // Must initialize n elements, this is required by DeduceTemplateArguments.1088 SmallVector<DeducedTemplateArgument> DeduceResults(1089 F->getTemplateParameters()->size());1090 1091 // FIXME: DeduceTemplateArguments stops immediately at the first1092 // non-deducible template argument. However, this doesn't seem to cause1093 // issues for practice cases, we probably need to extend it to continue1094 // performing deduction for rest of arguments to align with the C++1095 // standard.1096 SemaRef.DeduceTemplateArguments(1097 F->getTemplateParameters(), FReturnType->template_arguments(),1098 AliasRhsTemplateArgs, TDeduceInfo, DeduceResults,1099 /*NumberOfArgumentsMustMatch=*/false);1100 1101 SmallVector<TemplateArgument> DeducedArgs;1102 SmallVector<unsigned> NonDeducedTemplateParamsInFIndex;1103 // !!NOTE: DeduceResults respects the sequence of template parameters of1104 // the deduction guide f.1105 for (unsigned Index = 0; Index < DeduceResults.size(); ++Index) {1106 const auto &D = DeduceResults[Index];1107 if (!IsNonDeducedArgument(D))1108 DeducedArgs.push_back(D);1109 else1110 NonDeducedTemplateParamsInFIndex.push_back(Index);1111 }1112 auto DeducedAliasTemplateParams =1113 TemplateParamsReferencedInTemplateArgumentList(1114 SemaRef, AliasTemplate->getTemplateParameters(), DeducedArgs);1115 // All template arguments null by default.1116 SmallVector<TemplateArgument> TemplateArgsForBuildingFPrime(1117 F->getTemplateParameters()->size());1118 1119 // Create a template parameter list for the synthesized deduction guide f'.1120 //1121 // C++ [over.match.class.deduct]p3.2:1122 // If f is a function template, f' is a function template whose template1123 // parameter list consists of all the template parameters of A1124 // (including their default template arguments) that appear in the above1125 // deductions or (recursively) in their default template arguments1126 SmallVector<NamedDecl *> FPrimeTemplateParams;1127 // Store template arguments that refer to the newly-created template1128 // parameters, used for building `TemplateArgsForBuildingFPrime`.1129 SmallVector<TemplateArgument, 16> TransformedDeducedAliasArgs(1130 AliasTemplate->getTemplateParameters()->size());1131 // We might be already within a pack expansion, but rewriting template1132 // parameters is independent of that. (We may or may not expand new packs1133 // when rewriting. So clear the state)1134 Sema::ArgPackSubstIndexRAII PackSubstReset(SemaRef, std::nullopt);1135 1136 for (unsigned AliasTemplateParamIdx : DeducedAliasTemplateParams) {1137 auto *TP =1138 AliasTemplate->getTemplateParameters()->getParam(AliasTemplateParamIdx);1139 // Rebuild any internal references to earlier parameters and reindex as1140 // we go.1141 MultiLevelTemplateArgumentList Args;1142 Args.setKind(TemplateSubstitutionKind::Rewrite);1143 Args.addOuterTemplateArguments(TransformedDeducedAliasArgs);1144 NamedDecl *NewParam = transformTemplateParameter(1145 SemaRef, AliasTemplate->getDeclContext(), TP, Args,1146 /*NewIndex=*/FPrimeTemplateParams.size(), getDepthAndIndex(TP).first);1147 FPrimeTemplateParams.push_back(NewParam);1148 1149 TemplateArgument NewTemplateArgument =1150 Context.getInjectedTemplateArg(NewParam);1151 TransformedDeducedAliasArgs[AliasTemplateParamIdx] = NewTemplateArgument;1152 }1153 unsigned FirstUndeducedParamIdx = FPrimeTemplateParams.size();1154 1155 // To form a deduction guide f' from f, we leverage clang's instantiation1156 // mechanism, we construct a template argument list where the template1157 // arguments refer to the newly-created template parameters of f', and1158 // then apply instantiation on this template argument list to instantiate1159 // f, this ensures all template parameter occurrences are updated1160 // correctly.1161 //1162 // The template argument list is formed, in order, from1163 // 1) For the template parameters of the alias, the corresponding deduced1164 // template arguments1165 // 2) For the non-deduced template parameters of f. the1166 // (rebuilt) template arguments corresponding.1167 //1168 // Note: the non-deduced template arguments of `f` might refer to arguments1169 // deduced in 1), as in a type constraint.1170 MultiLevelTemplateArgumentList Args;1171 Args.setKind(TemplateSubstitutionKind::Rewrite);1172 Args.addOuterTemplateArguments(TransformedDeducedAliasArgs);1173 for (unsigned Index = 0; Index < DeduceResults.size(); ++Index) {1174 const auto &D = DeduceResults[Index];1175 auto *TP = F->getTemplateParameters()->getParam(Index);1176 if (IsNonDeducedArgument(D)) {1177 // 2): Non-deduced template parameters would be substituted later.1178 continue;1179 }1180 TemplateArgumentLoc Input =1181 SemaRef.getTrivialTemplateArgumentLoc(D, QualType(), SourceLocation{});1182 TemplateArgumentListInfo Output;1183 if (SemaRef.SubstTemplateArguments(Input, Args, Output))1184 return nullptr;1185 assert(TemplateArgsForBuildingFPrime[Index].isNull() &&1186 "InstantiatedArgs must be null before setting");1187 // CheckTemplateArgument is necessary for NTTP initializations.1188 // FIXME: We may want to call CheckTemplateArguments instead, but we cannot1189 // match packs as usual, since packs can appear in the middle of the1190 // parameter list of a synthesized CTAD guide. See also the FIXME in1191 // test/SemaCXX/cxx20-ctad-type-alias.cpp:test25.1192 Sema::CheckTemplateArgumentInfo CTAI;1193 for (auto TA : Output.arguments())1194 if (SemaRef.CheckTemplateArgument(1195 TP, TA, F, F->getLocation(), F->getLocation(),1196 /*ArgumentPackIndex=*/-1, CTAI,1197 Sema::CheckTemplateArgumentKind::CTAK_Specified))1198 return nullptr;1199 if (Input.getArgument().getKind() == TemplateArgument::Pack) {1200 // We will substitute the non-deduced template arguments with these1201 // transformed (unpacked at this point) arguments, where that substitution1202 // requires a pack for the corresponding parameter packs.1203 TemplateArgsForBuildingFPrime[Index] =1204 TemplateArgument::CreatePackCopy(Context, CTAI.SugaredConverted);1205 } else {1206 assert(Output.arguments().size() == 1);1207 TemplateArgsForBuildingFPrime[Index] = CTAI.SugaredConverted[0];1208 }1209 }1210 1211 // Case 2)1212 // ...followed by the template parameters of f that were not deduced1213 // (including their default template arguments)1214 for (unsigned FTemplateParamIdx : NonDeducedTemplateParamsInFIndex) {1215 auto *TP = F->getTemplateParameters()->getParam(FTemplateParamIdx);1216 MultiLevelTemplateArgumentList Args;1217 Args.setKind(TemplateSubstitutionKind::Rewrite);1218 // We take a shortcut here, it is ok to reuse the1219 // TemplateArgsForBuildingFPrime.1220 Args.addOuterTemplateArguments(TemplateArgsForBuildingFPrime);1221 NamedDecl *NewParam = transformTemplateParameter(1222 SemaRef, F->getDeclContext(), TP, Args, FPrimeTemplateParams.size(),1223 getDepthAndIndex(TP).first);1224 FPrimeTemplateParams.push_back(NewParam);1225 1226 assert(TemplateArgsForBuildingFPrime[FTemplateParamIdx].isNull() &&1227 "The argument must be null before setting");1228 TemplateArgsForBuildingFPrime[FTemplateParamIdx] =1229 Context.getInjectedTemplateArg(NewParam);1230 }1231 1232 auto *TemplateArgListForBuildingFPrime =1233 TemplateArgumentList::CreateCopy(Context, TemplateArgsForBuildingFPrime);1234 // Form the f' by substituting the template arguments into f.1235 if (auto *FPrime = SemaRef.InstantiateFunctionDeclaration(1236 F, TemplateArgListForBuildingFPrime, AliasTemplate->getLocation(),1237 Sema::CodeSynthesisContext::BuildingDeductionGuides)) {1238 auto *GG = cast<CXXDeductionGuideDecl>(FPrime);1239 1240 Expr *IsDeducible = buildIsDeducibleConstraint(1241 SemaRef, AliasTemplate, FPrime->getReturnType(), FPrimeTemplateParams);1242 Expr *RequiresClause =1243 buildAssociatedConstraints(SemaRef, F, AliasTemplate, DeduceResults,1244 FirstUndeducedParamIdx, IsDeducible);1245 1246 auto *FPrimeTemplateParamList = TemplateParameterList::Create(1247 Context, AliasTemplate->getTemplateParameters()->getTemplateLoc(),1248 AliasTemplate->getTemplateParameters()->getLAngleLoc(),1249 FPrimeTemplateParams,1250 AliasTemplate->getTemplateParameters()->getRAngleLoc(),1251 /*RequiresClause=*/RequiresClause);1252 auto *Result = cast<FunctionTemplateDecl>(buildDeductionGuide(1253 SemaRef, AliasTemplate, FPrimeTemplateParamList,1254 GG->getCorrespondingConstructor(), GG->getExplicitSpecifier(),1255 GG->getTypeSourceInfo(), AliasTemplate->getBeginLoc(),1256 AliasTemplate->getLocation(), AliasTemplate->getEndLoc(),1257 F->isImplicit()));1258 auto *DGuide = cast<CXXDeductionGuideDecl>(Result->getTemplatedDecl());1259 DGuide->setDeductionCandidateKind(GG->getDeductionCandidateKind());1260 DGuide->setSourceDeductionGuide(1261 cast<CXXDeductionGuideDecl>(F->getTemplatedDecl()));1262 DGuide->setSourceDeductionGuideKind(1263 CXXDeductionGuideDecl::SourceDeductionGuideKind::Alias);1264 return Result;1265 }1266 return nullptr;1267}1268 1269void DeclareImplicitDeductionGuidesForTypeAlias(1270 Sema &SemaRef, TypeAliasTemplateDecl *AliasTemplate, SourceLocation Loc) {1271 if (AliasTemplate->isInvalidDecl())1272 return;1273 auto &Context = SemaRef.Context;1274 auto [Template, AliasRhsTemplateArgs] =1275 getRHSTemplateDeclAndArgs(SemaRef, AliasTemplate);1276 if (!Template)1277 return;1278 auto SourceDeductionGuides = getSourceDeductionGuides(1279 Context.DeclarationNames.getCXXDeductionGuideName(AliasTemplate),1280 AliasTemplate->getDeclContext());1281 1282 DeclarationNameInfo NameInfo(1283 Context.DeclarationNames.getCXXDeductionGuideName(Template), Loc);1284 LookupResult Guides(SemaRef, NameInfo, clang::Sema::LookupOrdinaryName);1285 SemaRef.LookupQualifiedName(Guides, Template->getDeclContext());1286 Guides.suppressDiagnostics();1287 1288 for (auto *G : Guides) {1289 if (auto *DG = dyn_cast<CXXDeductionGuideDecl>(G)) {1290 if (SourceDeductionGuides.contains(DG))1291 continue;1292 // The deduction guide is a non-template function decl, we just clone it.1293 auto *FunctionType =1294 SemaRef.Context.getTrivialTypeSourceInfo(DG->getType());1295 FunctionProtoTypeLoc FPTL =1296 FunctionType->getTypeLoc().castAs<FunctionProtoTypeLoc>();1297 1298 // Clone the parameters.1299 for (unsigned I = 0, N = DG->getNumParams(); I != N; ++I) {1300 const auto *P = DG->getParamDecl(I);1301 auto *TSI = SemaRef.Context.getTrivialTypeSourceInfo(P->getType());1302 ParmVarDecl *NewParam = ParmVarDecl::Create(1303 SemaRef.Context, G->getDeclContext(),1304 DG->getParamDecl(I)->getBeginLoc(), P->getLocation(), nullptr,1305 TSI->getType(), TSI, SC_None, nullptr);1306 NewParam->setScopeInfo(0, I);1307 FPTL.setParam(I, NewParam);1308 }1309 auto *Transformed = cast<CXXDeductionGuideDecl>(buildDeductionGuide(1310 SemaRef, AliasTemplate, /*TemplateParams=*/nullptr,1311 /*Constructor=*/nullptr, DG->getExplicitSpecifier(), FunctionType,1312 AliasTemplate->getBeginLoc(), AliasTemplate->getLocation(),1313 AliasTemplate->getEndLoc(), DG->isImplicit()));1314 Transformed->setSourceDeductionGuide(DG);1315 Transformed->setSourceDeductionGuideKind(1316 CXXDeductionGuideDecl::SourceDeductionGuideKind::Alias);1317 1318 // FIXME: Here the synthesized deduction guide is not a templated1319 // function. Per [dcl.decl]p4, the requires-clause shall be present only1320 // if the declarator declares a templated function, a bug in standard?1321 AssociatedConstraint Constraint(buildIsDeducibleConstraint(1322 SemaRef, AliasTemplate, Transformed->getReturnType(), {}));1323 if (const AssociatedConstraint &RC = DG->getTrailingRequiresClause()) {1324 auto Conjunction = SemaRef.BuildBinOp(1325 SemaRef.getCurScope(), SourceLocation{},1326 BinaryOperatorKind::BO_LAnd, const_cast<Expr *>(RC.ConstraintExpr),1327 const_cast<Expr *>(Constraint.ConstraintExpr));1328 if (!Conjunction.isInvalid()) {1329 Constraint.ConstraintExpr = Conjunction.getAs<Expr>();1330 Constraint.ArgPackSubstIndex = RC.ArgPackSubstIndex;1331 }1332 }1333 Transformed->setTrailingRequiresClause(Constraint);1334 continue;1335 }1336 FunctionTemplateDecl *F = dyn_cast<FunctionTemplateDecl>(G);1337 if (!F || SourceDeductionGuides.contains(F->getTemplatedDecl()))1338 continue;1339 // The **aggregate** deduction guides are handled in a different code path1340 // (DeclareAggregateDeductionGuideFromInitList), which involves the tricky1341 // cache.1342 if (cast<CXXDeductionGuideDecl>(F->getTemplatedDecl())1343 ->getDeductionCandidateKind() == DeductionCandidate::Aggregate)1344 continue;1345 1346 BuildDeductionGuideForTypeAlias(SemaRef, AliasTemplate, F, Loc);1347 }1348}1349 1350// Build an aggregate deduction guide for a type alias template.1351FunctionTemplateDecl *DeclareAggregateDeductionGuideForTypeAlias(1352 Sema &SemaRef, TypeAliasTemplateDecl *AliasTemplate,1353 MutableArrayRef<QualType> ParamTypes, SourceLocation Loc) {1354 TemplateDecl *RHSTemplate =1355 getRHSTemplateDeclAndArgs(SemaRef, AliasTemplate).first;1356 if (!RHSTemplate)1357 return nullptr;1358 1359 llvm::SmallVector<TypedefNameDecl *> TypedefDecls;1360 llvm::SmallVector<QualType> NewParamTypes;1361 ExtractTypeForDeductionGuide TypeAliasTransformer(SemaRef, TypedefDecls);1362 for (QualType P : ParamTypes) {1363 QualType Type = TypeAliasTransformer.TransformType(P);1364 if (Type.isNull())1365 return nullptr;1366 NewParamTypes.push_back(Type);1367 }1368 1369 auto *RHSDeductionGuide = SemaRef.DeclareAggregateDeductionGuideFromInitList(1370 RHSTemplate, NewParamTypes, Loc);1371 if (!RHSDeductionGuide)1372 return nullptr;1373 1374 for (TypedefNameDecl *TD : TypedefDecls)1375 TD->setDeclContext(RHSDeductionGuide->getTemplatedDecl());1376 1377 return BuildDeductionGuideForTypeAlias(SemaRef, AliasTemplate,1378 RHSDeductionGuide, Loc);1379}1380 1381} // namespace1382 1383FunctionTemplateDecl *Sema::DeclareAggregateDeductionGuideFromInitList(1384 TemplateDecl *Template, MutableArrayRef<QualType> ParamTypes,1385 SourceLocation Loc) {1386 llvm::FoldingSetNodeID ID;1387 ID.AddPointer(Template);1388 for (auto &T : ParamTypes)1389 T.getCanonicalType().Profile(ID);1390 unsigned Hash = ID.ComputeHash();1391 1392 auto Found = AggregateDeductionCandidates.find(Hash);1393 if (Found != AggregateDeductionCandidates.end()) {1394 CXXDeductionGuideDecl *GD = Found->getSecond();1395 return GD->getDescribedFunctionTemplate();1396 }1397 1398 if (auto *AliasTemplate = llvm::dyn_cast<TypeAliasTemplateDecl>(Template)) {1399 if (auto *FTD = DeclareAggregateDeductionGuideForTypeAlias(1400 *this, AliasTemplate, ParamTypes, Loc)) {1401 auto *GD = cast<CXXDeductionGuideDecl>(FTD->getTemplatedDecl());1402 GD->setDeductionCandidateKind(DeductionCandidate::Aggregate);1403 AggregateDeductionCandidates[Hash] = GD;1404 return FTD;1405 }1406 }1407 1408 if (CXXRecordDecl *DefRecord =1409 cast<CXXRecordDecl>(Template->getTemplatedDecl())->getDefinition()) {1410 if (TemplateDecl *DescribedTemplate =1411 DefRecord->getDescribedClassTemplate())1412 Template = DescribedTemplate;1413 }1414 1415 DeclContext *DC = Template->getDeclContext();1416 if (DC->isDependentContext())1417 return nullptr;1418 1419 ConvertConstructorToDeductionGuideTransform Transform(1420 *this, cast<ClassTemplateDecl>(Template));1421 if (!isCompleteType(Loc, Transform.DeducedType))1422 return nullptr;1423 1424 // In case we were expanding a pack when we attempted to declare deduction1425 // guides, turn off pack expansion for everything we're about to do.1426 ArgPackSubstIndexRAII SubstIndex(*this, std::nullopt);1427 // Create a template instantiation record to track the "instantiation" of1428 // constructors into deduction guides.1429 InstantiatingTemplate BuildingDeductionGuides(1430 *this, Loc, Template,1431 Sema::InstantiatingTemplate::BuildingDeductionGuidesTag{});1432 if (BuildingDeductionGuides.isInvalid())1433 return nullptr;1434 1435 ClassTemplateDecl *Pattern =1436 Transform.NestedPattern ? Transform.NestedPattern : Transform.Template;1437 ContextRAII SavedContext(*this, Pattern->getTemplatedDecl());1438 1439 auto *FTD = cast<FunctionTemplateDecl>(1440 Transform.buildSimpleDeductionGuide(ParamTypes));1441 SavedContext.pop();1442 auto *GD = cast<CXXDeductionGuideDecl>(FTD->getTemplatedDecl());1443 GD->setDeductionCandidateKind(DeductionCandidate::Aggregate);1444 AggregateDeductionCandidates[Hash] = GD;1445 return FTD;1446}1447 1448void Sema::DeclareImplicitDeductionGuides(TemplateDecl *Template,1449 SourceLocation Loc) {1450 if (auto *AliasTemplate = llvm::dyn_cast<TypeAliasTemplateDecl>(Template)) {1451 DeclareImplicitDeductionGuidesForTypeAlias(*this, AliasTemplate, Loc);1452 return;1453 }1454 CXXRecordDecl *DefRecord =1455 dyn_cast_or_null<CXXRecordDecl>(Template->getTemplatedDecl());1456 if (!DefRecord)1457 return;1458 if (const CXXRecordDecl *Definition = DefRecord->getDefinition()) {1459 if (TemplateDecl *DescribedTemplate =1460 Definition->getDescribedClassTemplate())1461 Template = DescribedTemplate;1462 }1463 1464 DeclContext *DC = Template->getDeclContext();1465 if (DC->isDependentContext())1466 return;1467 1468 ConvertConstructorToDeductionGuideTransform Transform(1469 *this, cast<ClassTemplateDecl>(Template));1470 if (!isCompleteType(Loc, Transform.DeducedType))1471 return;1472 1473 if (hasDeclaredDeductionGuides(Transform.DeductionGuideName, DC))1474 return;1475 1476 // In case we were expanding a pack when we attempted to declare deduction1477 // guides, turn off pack expansion for everything we're about to do.1478 ArgPackSubstIndexRAII SubstIndex(*this, std::nullopt);1479 // Create a template instantiation record to track the "instantiation" of1480 // constructors into deduction guides.1481 InstantiatingTemplate BuildingDeductionGuides(1482 *this, Loc, Template,1483 Sema::InstantiatingTemplate::BuildingDeductionGuidesTag{});1484 if (BuildingDeductionGuides.isInvalid())1485 return;1486 1487 // Convert declared constructors into deduction guide templates.1488 // FIXME: Skip constructors for which deduction must necessarily fail (those1489 // for which some class template parameter without a default argument never1490 // appears in a deduced context).1491 ClassTemplateDecl *Pattern =1492 Transform.NestedPattern ? Transform.NestedPattern : Transform.Template;1493 ContextRAII SavedContext(*this, Pattern->getTemplatedDecl());1494 llvm::SmallPtrSet<NamedDecl *, 8> ProcessedCtors;1495 bool AddedAny = false;1496 for (NamedDecl *D : LookupConstructors(Pattern->getTemplatedDecl())) {1497 D = D->getUnderlyingDecl();1498 if (D->isInvalidDecl() || D->isImplicit())1499 continue;1500 1501 D = cast<NamedDecl>(D->getCanonicalDecl());1502 1503 // Within C++20 modules, we may have multiple same constructors in1504 // multiple same RecordDecls. And it doesn't make sense to create1505 // duplicated deduction guides for the duplicated constructors.1506 if (ProcessedCtors.count(D))1507 continue;1508 1509 auto *FTD = dyn_cast<FunctionTemplateDecl>(D);1510 auto *CD =1511 dyn_cast_or_null<CXXConstructorDecl>(FTD ? FTD->getTemplatedDecl() : D);1512 // Class-scope explicit specializations (MS extension) do not result in1513 // deduction guides.1514 if (!CD || (!FTD && CD->isFunctionTemplateSpecialization()))1515 continue;1516 1517 // Cannot make a deduction guide when unparsed arguments are present.1518 if (llvm::any_of(CD->parameters(), [](ParmVarDecl *P) {1519 return !P || P->hasUnparsedDefaultArg();1520 }))1521 continue;1522 1523 ProcessedCtors.insert(D);1524 Transform.transformConstructor(FTD, CD);1525 AddedAny = true;1526 }1527 1528 // C++17 [over.match.class.deduct]1529 // -- If C is not defined or does not declare any constructors, an1530 // additional function template derived as above from a hypothetical1531 // constructor C().1532 if (!AddedAny)1533 Transform.buildSimpleDeductionGuide({});1534 1535 // -- An additional function template derived as above from a hypothetical1536 // constructor C(C), called the copy deduction candidate.1537 cast<CXXDeductionGuideDecl>(1538 cast<FunctionTemplateDecl>(1539 Transform.buildSimpleDeductionGuide(Transform.DeducedType))1540 ->getTemplatedDecl())1541 ->setDeductionCandidateKind(DeductionCandidate::Copy);1542 1543 SavedContext.pop();1544}1545