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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements deduction guides for C++ class template argument
10// 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
58/// Return true if two associated-constraint sets are semantically equal.
59static bool HaveSameAssociatedConstraints(
60 Sema &SemaRef, const NamedDecl *Old, ArrayRef<AssociatedConstraint> OldACs,
61 const NamedDecl *New, ArrayRef<AssociatedConstraint> NewACs) {
62 if (OldACs.size() != NewACs.size())
63 return false;
64 if (OldACs.empty())
65 return true;
66
67 // General case: pairwise compare each associated constraint expression.
68 Sema::TemplateCompareNewDeclInfo NewInfo(New);
69 for (size_t I = 0, E = OldACs.size(); I != E; ++I)
70 if (!SemaRef.AreConstraintExpressionsEqual(
71 Old, OldConstr: OldACs[I].ConstraintExpr, New: NewInfo, NewConstr: NewACs[I].ConstraintExpr))
72 return false;
73
74 return true;
75}
76
77/// Tree transform to "extract" a transformed type from a class template's
78/// constructor to a deduction guide.
79class ExtractTypeForDeductionGuide
80 : public TreeTransform<ExtractTypeForDeductionGuide> {
81 llvm::SmallVectorImpl<TypedefNameDecl *> &MaterializedTypedefs;
82 ClassTemplateDecl *NestedPattern;
83 const MultiLevelTemplateArgumentList *OuterInstantiationArgs;
84 std::optional<TemplateDeclInstantiator> TypedefNameInstantiator;
85
86public:
87 typedef TreeTransform<ExtractTypeForDeductionGuide> Base;
88 ExtractTypeForDeductionGuide(
89 Sema &SemaRef,
90 llvm::SmallVectorImpl<TypedefNameDecl *> &MaterializedTypedefs,
91 ClassTemplateDecl *NestedPattern = nullptr,
92 const MultiLevelTemplateArgumentList *OuterInstantiationArgs = nullptr)
93 : Base(SemaRef), MaterializedTypedefs(MaterializedTypedefs),
94 NestedPattern(NestedPattern),
95 OuterInstantiationArgs(OuterInstantiationArgs) {
96 if (OuterInstantiationArgs)
97 TypedefNameInstantiator.emplace(
98 args&: SemaRef, args: SemaRef.getASTContext().getTranslationUnitDecl(),
99 args: *OuterInstantiationArgs);
100 }
101
102 TypeSourceInfo *transform(TypeSourceInfo *TSI) { return TransformType(TSI); }
103
104 /// Returns true if it's safe to substitute \p Typedef with
105 /// \p OuterInstantiationArgs.
106 bool mightReferToOuterTemplateParameters(TypedefNameDecl *Typedef) {
107 if (!NestedPattern)
108 return false;
109
110 static auto WalkUp = [](DeclContext *DC, DeclContext *TargetDC) {
111 if (DC->Equals(DC: TargetDC))
112 return true;
113 while (DC->isRecord()) {
114 if (DC->Equals(DC: TargetDC))
115 return true;
116 DC = DC->getParent();
117 }
118 return false;
119 };
120
121 if (WalkUp(Typedef->getDeclContext(), NestedPattern->getTemplatedDecl()))
122 return true;
123 if (WalkUp(NestedPattern->getTemplatedDecl(), Typedef->getDeclContext()))
124 return true;
125 return false;
126 }
127
128 QualType RebuildTemplateSpecializationType(
129 ElaboratedTypeKeyword Keyword, TemplateName Template,
130 SourceLocation TemplateNameLoc, TemplateArgumentListInfo &TemplateArgs) {
131 if (!OuterInstantiationArgs ||
132 !isa_and_present<TypeAliasTemplateDecl>(Val: Template.getAsTemplateDecl()))
133 return Base::RebuildTemplateSpecializationType(
134 Keyword, Template, TemplateNameLoc, TemplateArgs);
135
136 auto *TATD = cast<TypeAliasTemplateDecl>(Val: Template.getAsTemplateDecl());
137 auto *Pattern = TATD;
138 while (Pattern->getInstantiatedFromMemberTemplate())
139 Pattern = Pattern->getInstantiatedFromMemberTemplate();
140 if (!mightReferToOuterTemplateParameters(Typedef: Pattern->getTemplatedDecl()))
141 return Base::RebuildTemplateSpecializationType(
142 Keyword, Template, TemplateNameLoc, TemplateArgs);
143
144 Decl *NewD =
145 TypedefNameInstantiator->InstantiateTypeAliasTemplateDecl(D: TATD);
146 if (!NewD)
147 return QualType();
148
149 auto *NewTATD = cast<TypeAliasTemplateDecl>(Val: NewD);
150 MaterializedTypedefs.push_back(Elt: NewTATD->getTemplatedDecl());
151
152 return Base::RebuildTemplateSpecializationType(
153 Keyword, Template: TemplateName(NewTATD), TemplateNameLoc, TemplateArgs);
154 }
155
156 QualType TransformTypedefType(TypeLocBuilder &TLB, TypedefTypeLoc TL) {
157 ASTContext &Context = SemaRef.getASTContext();
158 TypedefNameDecl *OrigDecl = TL.getDecl();
159 TypedefNameDecl *Decl = OrigDecl;
160 const TypedefType *T = TL.getTypePtr();
161 // Transform the underlying type of the typedef and clone the Decl only if
162 // the typedef has a dependent context.
163 bool InDependentContext = OrigDecl->getDeclContext()->isDependentContext();
164
165 // A typedef/alias Decl within the NestedPattern may reference the outer
166 // template parameters. They're substituted with corresponding instantiation
167 // arguments here and in RebuildTemplateSpecializationType() above.
168 // Otherwise, we would have a CTAD guide with "dangling" template
169 // parameters.
170 // For example,
171 // template <class T> struct Outer {
172 // using Alias = S<T>;
173 // template <class U> struct Inner {
174 // Inner(Alias);
175 // };
176 // };
177 if (OuterInstantiationArgs && InDependentContext &&
178 T->isInstantiationDependentType()) {
179 Decl = cast_if_present<TypedefNameDecl>(
180 Val: TypedefNameInstantiator->InstantiateTypedefNameDecl(
181 D: OrigDecl, /*IsTypeAlias=*/isa<TypeAliasDecl>(Val: OrigDecl)));
182 if (!Decl)
183 return QualType();
184 MaterializedTypedefs.push_back(Elt: Decl);
185 } else if (InDependentContext) {
186 TypeLocBuilder InnerTLB;
187 QualType Transformed =
188 TransformType(TLB&: InnerTLB, T: OrigDecl->getTypeSourceInfo()->getTypeLoc());
189 TypeSourceInfo *TSI = InnerTLB.getTypeSourceInfo(Context, T: Transformed);
190 if (isa<TypeAliasDecl>(Val: OrigDecl))
191 Decl = TypeAliasDecl::Create(
192 C&: Context, DC: Context.getTranslationUnitDecl(), StartLoc: OrigDecl->getBeginLoc(),
193 IdLoc: OrigDecl->getLocation(), Id: OrigDecl->getIdentifier(), TInfo: TSI);
194 else {
195 assert(isa<TypedefDecl>(OrigDecl) && "Not a Type alias or typedef");
196 Decl = TypedefDecl::Create(
197 C&: Context, DC: Context.getTranslationUnitDecl(), StartLoc: OrigDecl->getBeginLoc(),
198 IdLoc: OrigDecl->getLocation(), Id: OrigDecl->getIdentifier(), TInfo: TSI);
199 }
200 MaterializedTypedefs.push_back(Elt: Decl);
201 }
202
203 NestedNameSpecifierLoc QualifierLoc = TL.getQualifierLoc();
204 if (QualifierLoc) {
205 QualifierLoc = getDerived().TransformNestedNameSpecifierLoc(NNS: QualifierLoc);
206 if (!QualifierLoc)
207 return QualType();
208 }
209
210 QualType TDTy = Context.getTypedefType(
211 Keyword: T->getKeyword(), Qualifier: QualifierLoc.getNestedNameSpecifier(), Decl);
212 TLB.push<TypedefTypeLoc>(T: TDTy).set(ElaboratedKeywordLoc: TL.getElaboratedKeywordLoc(),
213 QualifierLoc, NameLoc: TL.getNameLoc());
214 return TDTy;
215 }
216};
217
218// Build a deduction guide using the provided information.
219//
220// A deduction guide can be either a template or a non-template function
221// declaration. If \p TemplateParams is null, a non-template function
222// declaration will be created.
223CXXDeductionGuideDecl *
224buildDeductionGuide(Sema &SemaRef, TemplateDecl *OriginalTemplate,
225 TemplateParameterList *TemplateParams,
226 CXXConstructorDecl *Ctor, ExplicitSpecifier ES,
227 TypeSourceInfo *TInfo, SourceLocation LocStart,
228 SourceLocation Loc, SourceLocation LocEnd, bool IsImplicit,
229 llvm::ArrayRef<TypedefNameDecl *> MaterializedTypedefs = {},
230 const AssociatedConstraint &FunctionTrailingRC = {}) {
231 DeclContext *DC = OriginalTemplate->getDeclContext();
232 auto DeductionGuideName =
233 SemaRef.Context.DeclarationNames.getCXXDeductionGuideName(
234 TD: OriginalTemplate);
235
236 DeclarationNameInfo Name(DeductionGuideName, Loc);
237 ArrayRef<ParmVarDecl *> Params =
238 TInfo->getTypeLoc().castAs<FunctionProtoTypeLoc>().getParams();
239
240 // Build the implicit deduction guide template.
241 QualType GuideType = TInfo->getType();
242
243 // In CUDA/HIP mode, avoid duplicate implicit guides that differ only in CUDA
244 // target attributes (same constructor signature and constraints).
245 if (IsImplicit && Ctor && SemaRef.getLangOpts().CUDA) {
246 SmallVector<AssociatedConstraint, 4> NewACs;
247 Ctor->getAssociatedConstraints(ACs&: NewACs);
248
249 for (NamedDecl *Existing : DC->lookup(Name: DeductionGuideName)) {
250 auto *ExistingFT = dyn_cast<FunctionTemplateDecl>(Val: Existing);
251 auto *ExistingGuide =
252 ExistingFT
253 ? dyn_cast<CXXDeductionGuideDecl>(Val: ExistingFT->getTemplatedDecl())
254 : dyn_cast<CXXDeductionGuideDecl>(Val: Existing);
255 if (!ExistingGuide)
256 continue;
257
258 // Only consider guides that were also synthesized from a constructor.
259 auto *ExistingCtor = ExistingGuide->getCorrespondingConstructor();
260 if (!ExistingCtor)
261 continue;
262
263 // If the underlying constructors are overloads (different signatures once
264 // CUDA attributes are ignored), they should each get their own guides.
265 if (SemaRef.IsOverload(New: Ctor, Old: ExistingCtor,
266 /*UseMemberUsingDeclRules=*/false,
267 /*ConsiderCudaAttrs=*/false))
268 continue;
269
270 // At this point, the constructors have the same signature ignoring CUDA
271 // attributes. Decide whether their associated constraints are also the
272 // same; only in that case do we treat one guide as a duplicate of the
273 // other.
274 SmallVector<AssociatedConstraint, 4> ExistingACs;
275 ExistingCtor->getAssociatedConstraints(ACs&: ExistingACs);
276
277 if (HaveSameAssociatedConstraints(SemaRef, Old: ExistingCtor, OldACs: ExistingACs,
278 New: Ctor, NewACs))
279 return ExistingGuide;
280 }
281 }
282
283 auto *Guide = CXXDeductionGuideDecl::Create(
284 C&: SemaRef.Context, DC, StartLoc: LocStart, ES, NameInfo: Name, T: GuideType, TInfo, EndLocation: LocEnd, Ctor,
285 Kind: DeductionCandidate::Normal, TrailingRequiresClause: FunctionTrailingRC);
286 Guide->setImplicit(IsImplicit);
287 Guide->setParams(Params);
288
289 for (auto *Param : Params)
290 Param->setDeclContext(Guide);
291 for (auto *TD : MaterializedTypedefs)
292 TD->setDeclContext(Guide);
293 if (isa<CXXRecordDecl>(Val: DC))
294 Guide->setAccess(AS_public);
295
296 if (!TemplateParams) {
297 DC->addDecl(D: Guide);
298 return Guide;
299 }
300
301 auto *GuideTemplate = FunctionTemplateDecl::Create(
302 C&: SemaRef.Context, DC, L: Loc, Name: DeductionGuideName, Params: TemplateParams, Decl: Guide);
303 GuideTemplate->setImplicit(IsImplicit);
304 Guide->setDescribedFunctionTemplate(GuideTemplate);
305
306 if (isa<CXXRecordDecl>(Val: DC))
307 GuideTemplate->setAccess(AS_public);
308
309 DC->addDecl(D: GuideTemplate);
310 return Guide;
311}
312
313// Transform a given template type parameter `TTP`.
314TemplateTypeParmDecl *
315transformTemplateParam(Sema &SemaRef, DeclContext *DC,
316 TemplateTypeParmDecl *TTP,
317 MultiLevelTemplateArgumentList &Args, unsigned NewDepth,
318 unsigned NewIndex, bool EvaluateConstraint) {
319 // TemplateTypeParmDecl's index cannot be changed after creation, so
320 // substitute it directly.
321 auto *NewTTP = TemplateTypeParmDecl::Create(
322 C: SemaRef.Context, DC, KeyLoc: TTP->getBeginLoc(), NameLoc: TTP->getLocation(), D: NewDepth,
323 P: NewIndex, Id: TTP->getIdentifier(), Typename: TTP->wasDeclaredWithTypename(),
324 ParameterPack: TTP->isParameterPack(), HasTypeConstraint: TTP->hasTypeConstraint(),
325 NumExpanded: TTP->getNumExpansionParameters());
326 if (const auto *TC = TTP->getTypeConstraint())
327 SemaRef.SubstTypeConstraint(Inst: NewTTP, TC, TemplateArgs: Args,
328 /*EvaluateConstraint=*/EvaluateConstraint);
329 if (TTP->hasDefaultArgument()) {
330 TemplateArgumentLoc InstantiatedDefaultArg;
331 if (!SemaRef.SubstTemplateArgument(
332 Input: TTP->getDefaultArgument(), TemplateArgs: Args, Output&: InstantiatedDefaultArg,
333 Loc: TTP->getDefaultArgumentLoc(), Entity: TTP->getDeclName()))
334 NewTTP->setDefaultArgument(C: SemaRef.Context, DefArg: InstantiatedDefaultArg);
335 }
336 SemaRef.CurrentInstantiationScope->InstantiatedLocal(D: TTP, Inst: NewTTP);
337 return NewTTP;
338}
339
340NonTypeTemplateParmDecl *
341transformTemplateParam(Sema &SemaRef, DeclContext *DC,
342 NonTypeTemplateParmDecl *TTP, unsigned NewDepth,
343 unsigned NewIndex,
344 MultiLevelTemplateArgumentList &Args) {
345 NonTypeTemplateParmDecl *NewTTP;
346 if (TTP->isExpandedParameterPack()) {
347 SmallVector<TypeSourceInfo *, 4> ExpandedTypeSourceInfos(
348 TTP->getNumExpansionTypes());
349 SmallVector<QualType, 4> ExpandedTypes(TTP->getNumExpansionTypes());
350 for (unsigned I = 0, N = TTP->getNumExpansionTypes(); I != N; ++I) {
351 TypeSourceInfo *NewTSI =
352 SemaRef.SubstType(T: TTP->getExpansionTypeSourceInfo(I), TemplateArgs: Args,
353 Loc: TTP->getLocation(), Entity: TTP->getDeclName());
354 assert(NewTSI);
355
356 QualType NewT =
357 SemaRef.CheckNonTypeTemplateParameterType(TSI&: NewTSI, Loc: TTP->getLocation());
358 assert(!NewT.isNull());
359
360 ExpandedTypeSourceInfos[I] = NewTSI;
361 ExpandedTypes[I] = NewT;
362 }
363 NewTTP = NonTypeTemplateParmDecl::Create(
364 C: SemaRef.Context, DC, StartLoc: TTP->getBeginLoc(), IdLoc: TTP->getLocation(), D: NewDepth,
365 P: NewIndex, Id: TTP->getIdentifier(), T: TTP->getType(),
366 TInfo: TTP->getTypeSourceInfo(), ExpandedTypes, ExpandedTInfos: ExpandedTypeSourceInfos);
367 } else {
368 TypeSourceInfo *NewTSI = SemaRef.SubstType(
369 T: TTP->getTypeSourceInfo(), TemplateArgs: Args, Loc: TTP->getLocation(), Entity: TTP->getDeclName());
370 assert(NewTSI);
371
372 QualType NewT =
373 SemaRef.CheckNonTypeTemplateParameterType(TSI&: NewTSI, Loc: TTP->getLocation());
374 assert(!NewT.isNull());
375
376 NewTTP = NonTypeTemplateParmDecl::Create(
377 C: SemaRef.Context, DC, StartLoc: TTP->getBeginLoc(), IdLoc: TTP->getLocation(), D: NewDepth,
378 P: NewIndex, Id: TTP->getIdentifier(), T: NewT, ParameterPack: TTP->isParameterPack(), TInfo: NewTSI);
379 }
380
381 if (TypeSourceInfo *TSI = TTP->getTypeSourceInfo();
382 AutoTypeLoc AutoLoc = TSI->getTypeLoc().getContainedAutoTypeLoc()) {
383 if (AutoLoc.isConstrained()) {
384 SourceLocation EllipsisLoc;
385 if (TTP->isExpandedParameterPack())
386 EllipsisLoc =
387 TSI->getTypeLoc().getAs<PackExpansionTypeLoc>().getEllipsisLoc();
388 else if (auto *Constraint = dyn_cast_if_present<CXXFoldExpr>(
389 Val: TTP->getPlaceholderTypeConstraint()))
390 EllipsisLoc = Constraint->getEllipsisLoc();
391 // Note: We attach the non-instantiated constraint here, so that it can be
392 // instantiated relative to the top level, like all our other
393 // constraints.
394 if (SemaRef.AttachTypeConstraint(TL: AutoLoc, /*NewConstrainedParm=*/NewTTP,
395 /*OrigConstrainedParm=*/TTP,
396 EllipsisLoc))
397 llvm_unreachable("unexpected failure attaching type constraint");
398 }
399 }
400
401 NewTTP->setAccess(AS_public);
402 NewTTP->setImplicit(TTP->isImplicit());
403
404 if (TTP->hasDefaultArgument()) {
405 TemplateArgumentLoc InstantiatedDefaultArg;
406 if (!SemaRef.SubstTemplateArgument(
407 Input: TTP->getDefaultArgument(), TemplateArgs: Args, Output&: InstantiatedDefaultArg,
408 Loc: TTP->getDefaultArgumentLoc(), Entity: TTP->getDeclName()))
409 NewTTP->setDefaultArgument(C: SemaRef.Context, DefArg: InstantiatedDefaultArg);
410 }
411
412 SemaRef.CurrentInstantiationScope->InstantiatedLocal(D: TTP, Inst: NewTTP);
413 return NewTTP;
414}
415
416TemplateParameterList *
417transformTemplateParameters(Sema &SemaRef, DeclContext *DC,
418 TemplateParameterList *TPL,
419 MultiLevelTemplateArgumentList &Args,
420 unsigned NewDepth, bool EvaluateConstraint);
421
422TemplateTemplateParmDecl *
423transformTemplateParam(Sema &SemaRef, DeclContext *DC,
424 TemplateTemplateParmDecl *TTP, unsigned NewDepth,
425 unsigned NewIndex, MultiLevelTemplateArgumentList &Args,
426 bool EvaluateConstraint) {
427 TemplateTemplateParmDecl *NewTTP;
428 if (TTP->isExpandedParameterPack()) {
429 SmallVector<TemplateParameterList *, 4> ExpandedTPLs(
430 TTP->getNumExpansionTemplateParameters());
431 for (unsigned I = 0, N = TTP->getNumExpansionTemplateParameters(); I != N;
432 ++I)
433 ExpandedTPLs[I] = transformTemplateParameters(
434 SemaRef, DC, TPL: TTP->getExpansionTemplateParameters(I), Args,
435 NewDepth: NewDepth + 1, EvaluateConstraint);
436 NewTTP = TemplateTemplateParmDecl::Create(
437 C: SemaRef.Context, DC, L: TTP->getLocation(), D: NewDepth, P: NewIndex,
438 Id: TTP->getIdentifier(), ParameterKind: TTP->templateParameterKind(),
439 Typename: TTP->wasDeclaredWithTypename(), Params: TTP->getTemplateParameters(),
440 Expansions: ExpandedTPLs);
441 } else {
442 TemplateParameterList *NewTPL =
443 transformTemplateParameters(SemaRef, DC, TPL: TTP->getTemplateParameters(),
444 Args, NewDepth: NewDepth + 1, EvaluateConstraint);
445 NewTTP = TemplateTemplateParmDecl::Create(
446 C: SemaRef.Context, DC, L: TTP->getLocation(), D: NewDepth, P: NewIndex,
447 ParameterPack: TTP->isParameterPack(), Id: TTP->getIdentifier(),
448 ParameterKind: TTP->templateParameterKind(), Typename: TTP->wasDeclaredWithTypename(), Params: NewTPL);
449 }
450
451 NewTTP->setAccess(AS_public);
452 NewTTP->setImplicit(TTP->isImplicit());
453
454 if (TTP->hasDefaultArgument()) {
455 TemplateArgumentLoc InstantiatedDefaultArg;
456 if (!SemaRef.SubstTemplateArgument(
457 Input: TTP->getDefaultArgument(), TemplateArgs: Args, Output&: InstantiatedDefaultArg,
458 Loc: TTP->getDefaultArgumentLoc(), Entity: TTP->getDeclName()))
459 NewTTP->setDefaultArgument(C: SemaRef.Context, DefArg: InstantiatedDefaultArg);
460 }
461
462 SemaRef.CurrentInstantiationScope->InstantiatedLocal(D: TTP, Inst: NewTTP);
463 return NewTTP;
464}
465
466NamedDecl *transformTemplateParameter(Sema &SemaRef, DeclContext *DC,
467 NamedDecl *TemplateParam,
468 MultiLevelTemplateArgumentList &Args,
469 unsigned NewIndex, unsigned NewDepth,
470 bool EvaluateConstraint = true) {
471 if (auto *TTP = dyn_cast<TemplateTypeParmDecl>(Val: TemplateParam))
472 return transformTemplateParam(SemaRef, DC, TTP, Args, NewDepth, NewIndex,
473 EvaluateConstraint);
474 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Val: TemplateParam))
475 return transformTemplateParam(SemaRef, DC, TTP: NTTP, NewDepth, NewIndex, Args);
476 if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(Val: TemplateParam))
477 return transformTemplateParam(SemaRef, DC, TTP, NewDepth, NewIndex, Args,
478 EvaluateConstraint);
479 llvm_unreachable("Unhandled template parameter types");
480}
481
482TemplateParameterList *
483transformTemplateParameters(Sema &SemaRef, DeclContext *DC,
484 TemplateParameterList *TPL,
485 MultiLevelTemplateArgumentList &Args,
486 unsigned NewDepth, bool EvaluateConstraint) {
487 SmallVector<NamedDecl *, 4> Params(TPL->size());
488 for (unsigned I = 0, E = TPL->size(); I < E; ++I) {
489 Params[I] = transformTemplateParameter(SemaRef, DC, TemplateParam: TPL->getParam(Idx: I), Args,
490 /*NewIndex=*/I, NewDepth,
491 EvaluateConstraint);
492 }
493 return TemplateParameterList::Create(
494 C: SemaRef.Context, TemplateLoc: TPL->getTemplateLoc(), LAngleLoc: TPL->getLAngleLoc(), Params,
495 RAngleLoc: TPL->getRAngleLoc(), RequiresClause: TPL->getRequiresClause());
496}
497
498/// Transform to convert portions of a constructor declaration into the
499/// corresponding deduction guide, per C++1z [over.match.class.deduct]p1.
500struct ConvertConstructorToDeductionGuideTransform {
501 ConvertConstructorToDeductionGuideTransform(Sema &S,
502 ClassTemplateDecl *Template)
503 : SemaRef(S), Template(Template) {
504 // If the template is nested, then we need to use the original
505 // pattern to iterate over the constructors.
506 ClassTemplateDecl *Pattern = Template;
507 while (Pattern->getInstantiatedFromMemberTemplate()) {
508 if (Pattern->isMemberSpecialization())
509 break;
510 Pattern = Pattern->getInstantiatedFromMemberTemplate();
511 NestedPattern = Pattern;
512 }
513
514 if (NestedPattern)
515 OuterInstantiationArgs = SemaRef.getTemplateInstantiationArgs(D: Template);
516 }
517
518 Sema &SemaRef;
519 ClassTemplateDecl *Template;
520 ClassTemplateDecl *NestedPattern = nullptr;
521
522 DeclContext *DC = Template->getDeclContext();
523 CXXRecordDecl *Primary = Template->getTemplatedDecl();
524 DeclarationName DeductionGuideName =
525 SemaRef.Context.DeclarationNames.getCXXDeductionGuideName(TD: Template);
526
527 QualType DeducedType = SemaRef.Context.getCanonicalTagType(TD: Primary);
528
529 // Index adjustment to apply to convert depth-1 template parameters into
530 // depth-0 template parameters.
531 unsigned Depth1IndexAdjustment = Template->getTemplateParameters()->size();
532
533 // Instantiation arguments for the outermost depth-1 templates
534 // when the template is nested
535 MultiLevelTemplateArgumentList OuterInstantiationArgs;
536
537 /// Transform a constructor declaration into a deduction guide.
538 NamedDecl *transformConstructor(FunctionTemplateDecl *FTD,
539 CXXConstructorDecl *CD) {
540 SmallVector<TemplateArgument, 16> SubstArgs;
541
542 LocalInstantiationScope Scope(SemaRef);
543
544 // C++ [over.match.class.deduct]p1:
545 // -- For each constructor of the class template designated by the
546 // template-name, a function template with the following properties:
547
548 // -- The template parameters are the template parameters of the class
549 // template followed by the template parameters (including default
550 // template arguments) of the constructor, if any.
551 TemplateParameterList *TemplateParams =
552 SemaRef.GetTemplateParameterList(TD: Template);
553 SmallVector<TemplateArgument, 16> Depth1Args;
554 AssociatedConstraint OuterRC(TemplateParams->getRequiresClause());
555 if (FTD) {
556 TemplateParameterList *InnerParams = FTD->getTemplateParameters();
557 SmallVector<NamedDecl *, 16> AllParams;
558 AllParams.reserve(N: TemplateParams->size() + InnerParams->size());
559 AllParams.insert(I: AllParams.begin(), From: TemplateParams->begin(),
560 To: TemplateParams->end());
561 SubstArgs.reserve(N: InnerParams->size());
562 Depth1Args.reserve(N: InnerParams->size());
563
564 // Later template parameters could refer to earlier ones, so build up
565 // a list of substituted template arguments as we go.
566 for (NamedDecl *Param : *InnerParams) {
567 MultiLevelTemplateArgumentList Args;
568 Args.setKind(TemplateSubstitutionKind::Rewrite);
569 Args.addOuterTemplateArguments(Args: Depth1Args);
570 Args.addOuterRetainedLevel();
571 if (NestedPattern)
572 Args.addOuterRetainedLevels(Num: NestedPattern->getTemplateDepth());
573 auto [Depth, Index] = getDepthAndIndex(ND: Param);
574 // Depth can be 0 if FTD belongs to a non-template class/a class
575 // template specialization with an empty template parameter list. In
576 // that case, we don't want the NewDepth to overflow, and it should
577 // remain 0.
578 NamedDecl *NewParam = transformTemplateParameter(
579 SemaRef, DC, TemplateParam: Param, Args, NewIndex: Index + Depth1IndexAdjustment,
580 NewDepth: Depth ? Depth - 1 : 0);
581 if (!NewParam)
582 return nullptr;
583 // Constraints require that we substitute depth-1 arguments
584 // to match depths when substituted for evaluation later
585 Depth1Args.push_back(Elt: SemaRef.Context.getInjectedTemplateArg(ParamDecl: NewParam));
586
587 if (NestedPattern) {
588 auto [Depth, Index] = getDepthAndIndex(ND: NewParam);
589 NewParam = transformTemplateParameter(
590 SemaRef, DC, TemplateParam: NewParam, Args&: OuterInstantiationArgs, NewIndex: Index,
591 NewDepth: Depth - OuterInstantiationArgs.getNumSubstitutedLevels(),
592 /*EvaluateConstraint=*/false);
593 }
594
595 assert(getDepthAndIndex(NewParam).first == 0 &&
596 "Unexpected template parameter depth");
597
598 AllParams.push_back(Elt: NewParam);
599 SubstArgs.push_back(Elt: SemaRef.Context.getInjectedTemplateArg(ParamDecl: NewParam));
600 }
601
602 // Substitute new template parameters into requires-clause if present.
603 Expr *RequiresClause = nullptr;
604 if (Expr *InnerRC = InnerParams->getRequiresClause()) {
605 MultiLevelTemplateArgumentList Args;
606 Args.setKind(TemplateSubstitutionKind::Rewrite);
607 Args.addOuterTemplateArguments(Args: Depth1Args);
608 Args.addOuterRetainedLevel();
609 if (NestedPattern)
610 Args.addOuterRetainedLevels(Num: NestedPattern->getTemplateDepth());
611 ExprResult E =
612 SemaRef.SubstConstraintExprWithoutSatisfaction(E: InnerRC, TemplateArgs: Args);
613 if (!E.isUsable())
614 return nullptr;
615 RequiresClause = E.get();
616 }
617
618 TemplateParams = TemplateParameterList::Create(
619 C: SemaRef.Context, TemplateLoc: InnerParams->getTemplateLoc(),
620 LAngleLoc: InnerParams->getLAngleLoc(), Params: AllParams, RAngleLoc: InnerParams->getRAngleLoc(),
621 RequiresClause);
622 }
623
624 // If we built a new template-parameter-list, track that we need to
625 // substitute references to the old parameters into references to the
626 // new ones.
627 MultiLevelTemplateArgumentList Args;
628 Args.setKind(TemplateSubstitutionKind::Rewrite);
629 if (FTD) {
630 Args.addOuterTemplateArguments(Args: SubstArgs);
631 Args.addOuterRetainedLevel();
632 }
633
634 FunctionProtoTypeLoc FPTL = CD->getTypeSourceInfo()
635 ->getTypeLoc()
636 .getAsAdjusted<FunctionProtoTypeLoc>();
637 assert(FPTL && "no prototype for constructor declaration");
638
639 // Transform the type of the function, adjusting the return type and
640 // replacing references to the old parameters with references to the
641 // new ones.
642 TypeLocBuilder TLB;
643 SmallVector<ParmVarDecl *, 8> Params;
644 SmallVector<TypedefNameDecl *, 4> MaterializedTypedefs;
645 QualType NewType = transformFunctionProtoType(TLB, TL: FPTL, Params, Args,
646 MaterializedTypedefs);
647 if (NewType.isNull())
648 return nullptr;
649 TypeSourceInfo *NewTInfo = TLB.getTypeSourceInfo(Context&: SemaRef.Context, T: NewType);
650
651 // At this point, the function parameters are already 'instantiated' in the
652 // current scope. Substitute into the constructor's trailing
653 // requires-clause, if any.
654 AssociatedConstraint FunctionTrailingRC;
655 if (const AssociatedConstraint &RC = CD->getTrailingRequiresClause()) {
656 MultiLevelTemplateArgumentList Args;
657 Args.setKind(TemplateSubstitutionKind::Rewrite);
658 Args.addOuterTemplateArguments(Args: Depth1Args);
659 Args.addOuterRetainedLevel();
660 if (NestedPattern)
661 Args.addOuterRetainedLevels(Num: NestedPattern->getTemplateDepth());
662 ExprResult E = SemaRef.SubstConstraintExprWithoutSatisfaction(
663 E: const_cast<Expr *>(RC.ConstraintExpr), TemplateArgs: Args);
664 if (!E.isUsable())
665 return nullptr;
666 FunctionTrailingRC = AssociatedConstraint(E.get(), RC.ArgPackSubstIndex);
667 }
668
669 // C++ [over.match.class.deduct]p1:
670 // If C is defined, for each constructor of C, a function template with
671 // the following properties:
672 // [...]
673 // - The associated constraints are the conjunction of the associated
674 // constraints of C and the associated constraints of the constructor, if
675 // any.
676 if (OuterRC) {
677 // The outer template parameters are not transformed, so their
678 // associated constraints don't need substitution.
679 // FIXME: Should simply add another field for the OuterRC, instead of
680 // combining them like this.
681 if (!FunctionTrailingRC)
682 FunctionTrailingRC = OuterRC;
683 else
684 FunctionTrailingRC = AssociatedConstraint(
685 BinaryOperator::Create(
686 C: SemaRef.Context,
687 /*lhs=*/const_cast<Expr *>(OuterRC.ConstraintExpr),
688 /*rhs=*/const_cast<Expr *>(FunctionTrailingRC.ConstraintExpr),
689 opc: BO_LAnd, ResTy: SemaRef.Context.BoolTy, VK: VK_PRValue, OK: OK_Ordinary,
690 opLoc: TemplateParams->getTemplateLoc(), FPFeatures: FPOptionsOverride()),
691 FunctionTrailingRC.ArgPackSubstIndex);
692 }
693
694 return buildDeductionGuide(
695 SemaRef, OriginalTemplate: Template, TemplateParams, Ctor: CD, ES: CD->getExplicitSpecifier(),
696 TInfo: NewTInfo, LocStart: CD->getBeginLoc(), Loc: CD->getLocation(), LocEnd: CD->getEndLoc(),
697 /*IsImplicit=*/true, MaterializedTypedefs, FunctionTrailingRC);
698 }
699
700 /// Build a deduction guide with the specified parameter types.
701 CXXDeductionGuideDecl *
702 buildSimpleDeductionGuide(MutableArrayRef<QualType> ParamTypes) {
703 SourceLocation Loc = Template->getLocation();
704
705 // Build the requested type.
706 FunctionProtoType::ExtProtoInfo EPI;
707 EPI.HasTrailingReturn = true;
708 QualType Result = SemaRef.BuildFunctionType(T: DeducedType, ParamTypes, Loc,
709 Entity: DeductionGuideName, EPI);
710 TypeSourceInfo *TSI = SemaRef.Context.getTrivialTypeSourceInfo(T: Result, Loc);
711 if (NestedPattern)
712 TSI = SemaRef.SubstType(T: TSI, TemplateArgs: OuterInstantiationArgs, Loc,
713 Entity: DeductionGuideName);
714
715 if (!TSI)
716 return nullptr;
717
718 FunctionProtoTypeLoc FPTL =
719 TSI->getTypeLoc().castAs<FunctionProtoTypeLoc>();
720
721 // Build the parameters, needed during deduction / substitution.
722 SmallVector<ParmVarDecl *, 4> Params;
723 for (auto T : ParamTypes) {
724 auto *TSI = SemaRef.Context.getTrivialTypeSourceInfo(T, Loc);
725 if (NestedPattern)
726 TSI = SemaRef.SubstType(T: TSI, TemplateArgs: OuterInstantiationArgs, Loc,
727 Entity: DeclarationName());
728 if (!TSI)
729 return nullptr;
730
731 ParmVarDecl *NewParam =
732 ParmVarDecl::Create(C&: SemaRef.Context, DC, StartLoc: Loc, IdLoc: Loc, Id: nullptr,
733 T: TSI->getType(), TInfo: TSI, S: SC_None, DefArg: nullptr);
734 NewParam->setScopeInfo(scopeDepth: 0, parameterIndex: Params.size());
735 FPTL.setParam(i: Params.size(), VD: NewParam);
736 Params.push_back(Elt: NewParam);
737 }
738
739 return buildDeductionGuide(
740 SemaRef, OriginalTemplate: Template, TemplateParams: SemaRef.GetTemplateParameterList(TD: Template), Ctor: nullptr,
741 ES: ExplicitSpecifier(), TInfo: TSI, LocStart: Loc, Loc, LocEnd: Loc, /*IsImplicit=*/true);
742 }
743
744private:
745 QualType transformFunctionProtoType(
746 TypeLocBuilder &TLB, FunctionProtoTypeLoc TL,
747 SmallVectorImpl<ParmVarDecl *> &Params,
748 MultiLevelTemplateArgumentList &Args,
749 SmallVectorImpl<TypedefNameDecl *> &MaterializedTypedefs) {
750 SmallVector<QualType, 4> ParamTypes;
751 const FunctionProtoType *T = TL.getTypePtr();
752
753 // -- The types of the function parameters are those of the constructor.
754 for (auto *OldParam : TL.getParams()) {
755 ParmVarDecl *NewParam = OldParam;
756 // Given
757 // template <class T> struct C {
758 // template <class U> struct D {
759 // template <class V> D(U, V);
760 // };
761 // };
762 // First, transform all the references to template parameters that are
763 // defined outside of the surrounding class template. That is T in the
764 // above example.
765 if (NestedPattern) {
766 NewParam = transformFunctionTypeParam(
767 OldParam: NewParam, Args&: OuterInstantiationArgs, MaterializedTypedefs,
768 /*TransformingOuterPatterns=*/true);
769 if (!NewParam)
770 return QualType();
771 }
772 // Then, transform all the references to template parameters that are
773 // defined at the class template and the constructor. In this example,
774 // they're U and V, respectively.
775 NewParam =
776 transformFunctionTypeParam(OldParam: NewParam, Args, MaterializedTypedefs,
777 /*TransformingOuterPatterns=*/false);
778 if (!NewParam)
779 return QualType();
780 ParamTypes.push_back(Elt: NewParam->getType());
781 Params.push_back(Elt: NewParam);
782 }
783
784 // -- The return type is the class template specialization designated by
785 // the template-name and template arguments corresponding to the
786 // template parameters obtained from the class template.
787 //
788 // We use the injected-class-name type of the primary template instead.
789 // This has the convenient property that it is different from any type that
790 // the user can write in a deduction-guide (because they cannot enter the
791 // context of the template), so implicit deduction guides can never collide
792 // with explicit ones.
793 QualType ReturnType = DeducedType;
794 auto TTL = TLB.push<TagTypeLoc>(T: ReturnType);
795 TTL.setElaboratedKeywordLoc(SourceLocation());
796 TTL.setQualifierLoc(NestedNameSpecifierLoc());
797 TTL.setNameLoc(Primary->getLocation());
798
799 // Resolving a wording defect, we also inherit the variadicness of the
800 // constructor.
801 FunctionProtoType::ExtProtoInfo EPI;
802 EPI.Variadic = T->isVariadic();
803 EPI.HasTrailingReturn = true;
804
805 QualType Result = SemaRef.BuildFunctionType(
806 T: ReturnType, ParamTypes, Loc: TL.getBeginLoc(), Entity: DeductionGuideName, EPI);
807 if (Result.isNull())
808 return QualType();
809
810 FunctionProtoTypeLoc NewTL = TLB.push<FunctionProtoTypeLoc>(T: Result);
811 NewTL.setLocalRangeBegin(TL.getLocalRangeBegin());
812 NewTL.setLParenLoc(TL.getLParenLoc());
813 NewTL.setRParenLoc(TL.getRParenLoc());
814 NewTL.setExceptionSpecRange(SourceRange());
815 NewTL.setLocalRangeEnd(TL.getLocalRangeEnd());
816 for (unsigned I = 0, E = NewTL.getNumParams(); I != E; ++I)
817 NewTL.setParam(i: I, VD: Params[I]);
818
819 return Result;
820 }
821
822 ParmVarDecl *transformFunctionTypeParam(
823 ParmVarDecl *OldParam, MultiLevelTemplateArgumentList &Args,
824 llvm::SmallVectorImpl<TypedefNameDecl *> &MaterializedTypedefs,
825 bool TransformingOuterPatterns) {
826 TypeSourceInfo *OldTSI = OldParam->getTypeSourceInfo();
827 TypeSourceInfo *NewTSI;
828 if (auto PackTL = OldTSI->getTypeLoc().getAs<PackExpansionTypeLoc>()) {
829 // Expand out the one and only element in each inner pack.
830 Sema::ArgPackSubstIndexRAII SubstIndex(SemaRef, 0u);
831 NewTSI =
832 SemaRef.SubstType(TL: PackTL.getPatternLoc(), TemplateArgs: Args,
833 Loc: OldParam->getLocation(), Entity: OldParam->getDeclName());
834 if (!NewTSI)
835 return nullptr;
836 NewTSI =
837 SemaRef.CheckPackExpansion(Pattern: NewTSI, EllipsisLoc: PackTL.getEllipsisLoc(),
838 NumExpansions: PackTL.getTypePtr()->getNumExpansions());
839 } else
840 NewTSI = SemaRef.SubstType(T: OldTSI, TemplateArgs: Args, Loc: OldParam->getLocation(),
841 Entity: OldParam->getDeclName());
842 if (!NewTSI)
843 return nullptr;
844
845 // Extract the type. This (for instance) replaces references to typedef
846 // members of the current instantiations with the definitions of those
847 // typedefs, avoiding triggering instantiation of the deduced type during
848 // deduction.
849 NewTSI = ExtractTypeForDeductionGuide(
850 SemaRef, MaterializedTypedefs, NestedPattern,
851 TransformingOuterPatterns ? &Args : nullptr)
852 .transform(TSI: NewTSI);
853 if (!NewTSI)
854 return nullptr;
855 // Resolving a wording defect, we also inherit default arguments from the
856 // constructor.
857 ExprResult NewDefArg;
858 if (OldParam->hasDefaultArg()) {
859 // We don't care what the value is (we won't use it); just create a
860 // placeholder to indicate there is a default argument.
861 QualType ParamTy = NewTSI->getType();
862 NewDefArg = new (SemaRef.Context)
863 OpaqueValueExpr(OldParam->getDefaultArgRange().getBegin(),
864 ParamTy.getNonLValueExprType(Context: SemaRef.Context),
865 ParamTy->isLValueReferenceType() ? VK_LValue
866 : ParamTy->isRValueReferenceType() ? VK_XValue
867 : VK_PRValue);
868 }
869 // Handle arrays and functions decay.
870 auto NewType = NewTSI->getType();
871 if (NewType->isArrayType() || NewType->isFunctionType())
872 NewType = SemaRef.Context.getDecayedType(T: NewType);
873
874 ParmVarDecl *NewParam = ParmVarDecl::Create(
875 C&: SemaRef.Context, DC, StartLoc: OldParam->getInnerLocStart(),
876 IdLoc: OldParam->getLocation(), Id: OldParam->getIdentifier(), T: NewType, TInfo: NewTSI,
877 S: OldParam->getStorageClass(), DefArg: NewDefArg.get());
878 NewParam->setScopeInfo(scopeDepth: OldParam->getFunctionScopeDepth(),
879 parameterIndex: OldParam->getFunctionScopeIndex());
880 SemaRef.CurrentInstantiationScope->InstantiatedLocal(D: OldParam, Inst: NewParam);
881 return NewParam;
882 }
883};
884
885// Find all template parameters that appear in the given DeducedArgs.
886// Return the indices of the template parameters in the TemplateParams.
887SmallVector<unsigned> TemplateParamsReferencedInTemplateArgumentList(
888 Sema &SemaRef, const TemplateParameterList *TemplateParamsList,
889 ArrayRef<TemplateArgument> DeducedArgs) {
890
891 llvm::SmallBitVector ReferencedTemplateParams(TemplateParamsList->size());
892 SemaRef.MarkUsedTemplateParameters(
893 TemplateArgs: DeducedArgs, Depth: TemplateParamsList->getDepth(), Used&: ReferencedTemplateParams);
894
895 auto MarkDefaultArgs = [&](auto *Param) {
896 if (!Param->hasDefaultArgument())
897 return;
898 SemaRef.MarkUsedTemplateParameters(
899 Param->getDefaultArgument().getArgument(),
900 TemplateParamsList->getDepth(), ReferencedTemplateParams);
901 };
902
903 for (unsigned Index = 0; Index < TemplateParamsList->size(); ++Index) {
904 if (!ReferencedTemplateParams[Index])
905 continue;
906 auto *Param = TemplateParamsList->getParam(Idx: Index);
907 if (auto *TTPD = dyn_cast<TemplateTypeParmDecl>(Val: Param))
908 MarkDefaultArgs(TTPD);
909 else if (auto *NTTPD = dyn_cast<NonTypeTemplateParmDecl>(Val: Param))
910 MarkDefaultArgs(NTTPD);
911 else
912 MarkDefaultArgs(cast<TemplateTemplateParmDecl>(Val: Param));
913 }
914
915 SmallVector<unsigned> Results;
916 for (unsigned Index = 0; Index < TemplateParamsList->size(); ++Index) {
917 if (ReferencedTemplateParams[Index])
918 Results.push_back(Elt: Index);
919 }
920 return Results;
921}
922
923bool hasDeclaredDeductionGuides(DeclarationName Name, DeclContext *DC) {
924 // Check whether we've already declared deduction guides for this template.
925 // FIXME: Consider storing a flag on the template to indicate this.
926 assert(Name.getNameKind() ==
927 DeclarationName::NameKind::CXXDeductionGuideName &&
928 "name must be a deduction guide name");
929 auto Existing = DC->lookup(Name);
930 for (auto *D : Existing)
931 if (D->isImplicit())
932 return true;
933 return false;
934}
935
936// Returns all source deduction guides associated with the declared
937// deduction guides that have the specified deduction guide name.
938llvm::DenseSet<const NamedDecl *> getSourceDeductionGuides(DeclarationName Name,
939 DeclContext *DC) {
940 assert(Name.getNameKind() ==
941 DeclarationName::NameKind::CXXDeductionGuideName &&
942 "name must be a deduction guide name");
943 llvm::DenseSet<const NamedDecl *> Result;
944 for (auto *D : DC->lookup(Name)) {
945 if (const auto *FTD = dyn_cast<FunctionTemplateDecl>(Val: D))
946 D = FTD->getTemplatedDecl();
947
948 if (const auto *GD = dyn_cast<CXXDeductionGuideDecl>(Val: D)) {
949 assert(GD->getSourceDeductionGuide() &&
950 "deduction guide for alias template must have a source deduction "
951 "guide");
952 Result.insert(V: GD->getSourceDeductionGuide());
953 }
954 }
955 return Result;
956}
957
958// Build the associated constraints for the alias deduction guides.
959// C++ [over.match.class.deduct]p3.3:
960// The associated constraints ([temp.constr.decl]) are the conjunction of the
961// associated constraints of g and a constraint that is satisfied if and only
962// if the arguments of A are deducible (see below) from the return type.
963//
964// The return result is expected to be the require-clause for the synthesized
965// alias deduction guide.
966Expr *
967buildAssociatedConstraints(Sema &SemaRef, FunctionTemplateDecl *F,
968 TypeAliasTemplateDecl *AliasTemplate,
969 ArrayRef<DeducedTemplateArgument> DeduceResults,
970 unsigned FirstUndeducedParamIdx, Expr *IsDeducible) {
971 Expr *RC = F->getTemplateParameters()->getRequiresClause();
972 if (!RC)
973 return IsDeducible;
974
975 ASTContext &Context = SemaRef.Context;
976 LocalInstantiationScope Scope(SemaRef);
977
978 // In the clang AST, constraint nodes are deliberately not instantiated unless
979 // they are actively being evaluated. Consequently, occurrences of template
980 // parameters in the require-clause expression have a subtle "depth"
981 // difference compared to normal occurrences in places, such as function
982 // parameters. When transforming the require-clause, we must take this
983 // distinction into account:
984 //
985 // 1) In the transformed require-clause, occurrences of template parameters
986 // must use the "uninstantiated" depth;
987 // 2) When substituting on the require-clause expr of the underlying
988 // deduction guide, we must use the entire set of template argument lists;
989 //
990 // It's important to note that we're performing this transformation on an
991 // *instantiated* AliasTemplate.
992
993 // For 1), if the alias template is nested within a class template, we
994 // calcualte the 'uninstantiated' depth by adding the substitution level back.
995 unsigned AdjustDepth = 0;
996 if (auto *PrimaryTemplate =
997 AliasTemplate->getInstantiatedFromMemberTemplate())
998 AdjustDepth = PrimaryTemplate->getTemplateDepth();
999
1000 // We rebuild all template parameters with the uninstantiated depth, and
1001 // build template arguments refer to them.
1002 SmallVector<TemplateArgument> AdjustedAliasTemplateArgs;
1003
1004 for (auto *TP : *AliasTemplate->getTemplateParameters()) {
1005 // Rebuild any internal references to earlier parameters and reindex
1006 // as we go.
1007 MultiLevelTemplateArgumentList Args;
1008 Args.setKind(TemplateSubstitutionKind::Rewrite);
1009 Args.addOuterTemplateArguments(Args: AdjustedAliasTemplateArgs);
1010 NamedDecl *NewParam = transformTemplateParameter(
1011 SemaRef, DC: AliasTemplate->getDeclContext(), TemplateParam: TP, Args,
1012 /*NewIndex=*/AdjustedAliasTemplateArgs.size(),
1013 NewDepth: getDepthAndIndex(ND: TP).first + AdjustDepth);
1014
1015 TemplateArgument NewTemplateArgument =
1016 Context.getInjectedTemplateArg(ParamDecl: NewParam);
1017 AdjustedAliasTemplateArgs.push_back(Elt: NewTemplateArgument);
1018 }
1019 // Template arguments used to transform the template arguments in
1020 // DeducedResults.
1021 SmallVector<TemplateArgument> TemplateArgsForBuildingRC(
1022 F->getTemplateParameters()->size());
1023 // Transform the transformed template args
1024 MultiLevelTemplateArgumentList Args;
1025 Args.setKind(TemplateSubstitutionKind::Rewrite);
1026 Args.addOuterTemplateArguments(Args: AdjustedAliasTemplateArgs);
1027
1028 for (unsigned Index = 0; Index < DeduceResults.size(); ++Index) {
1029 const auto &D = DeduceResults[Index];
1030 if (D.isNull()) { // non-deduced template parameters of f
1031 NamedDecl *TP = F->getTemplateParameters()->getParam(Idx: Index);
1032 MultiLevelTemplateArgumentList Args;
1033 Args.setKind(TemplateSubstitutionKind::Rewrite);
1034 Args.addOuterTemplateArguments(Args: TemplateArgsForBuildingRC);
1035 // Rebuild the template parameter with updated depth and index.
1036 NamedDecl *NewParam =
1037 transformTemplateParameter(SemaRef, DC: F->getDeclContext(), TemplateParam: TP, Args,
1038 /*NewIndex=*/FirstUndeducedParamIdx,
1039 NewDepth: getDepthAndIndex(ND: TP).first + AdjustDepth);
1040 FirstUndeducedParamIdx += 1;
1041 assert(TemplateArgsForBuildingRC[Index].isNull());
1042 TemplateArgsForBuildingRC[Index] =
1043 Context.getInjectedTemplateArg(ParamDecl: NewParam);
1044 continue;
1045 }
1046 TemplateArgumentLoc Input =
1047 SemaRef.getTrivialTemplateArgumentLoc(Arg: D, NTTPType: QualType(), Loc: SourceLocation{});
1048 TemplateArgumentLoc Output;
1049 if (!SemaRef.SubstTemplateArgument(Input, TemplateArgs: Args, Output)) {
1050 assert(TemplateArgsForBuildingRC[Index].isNull() &&
1051 "InstantiatedArgs must be null before setting");
1052 TemplateArgsForBuildingRC[Index] = Output.getArgument();
1053 }
1054 }
1055
1056 // A list of template arguments for transforming the require-clause of F.
1057 // It must contain the entire set of template argument lists.
1058 MultiLevelTemplateArgumentList ArgsForBuildingRC;
1059 ArgsForBuildingRC.setKind(clang::TemplateSubstitutionKind::Rewrite);
1060 ArgsForBuildingRC.addOuterTemplateArguments(Args: TemplateArgsForBuildingRC);
1061 // For 2), if the underlying deduction guide F is nested in a class template,
1062 // we need the entire template argument list, as the constraint AST in the
1063 // require-clause of F remains completely uninstantiated.
1064 //
1065 // For example:
1066 // template <typename T> // depth 0
1067 // struct Outer {
1068 // template <typename U>
1069 // struct Foo { Foo(U); };
1070 //
1071 // template <typename U> // depth 1
1072 // requires C<U>
1073 // Foo(U) -> Foo<int>;
1074 // };
1075 // template <typename U>
1076 // using AFoo = Outer<int>::Foo<U>;
1077 //
1078 // In this scenario, the deduction guide for `Foo` inside `Outer<int>`:
1079 // - The occurrence of U in the require-expression is [depth:1, index:0]
1080 // - The occurrence of U in the function parameter is [depth:0, index:0]
1081 // - The template parameter of U is [depth:0, index:0]
1082 //
1083 // We add the outer template arguments which is [int] to the multi-level arg
1084 // list to ensure that the occurrence U in `C<U>` will be replaced with int
1085 // during the substitution.
1086 //
1087 // NOTE: The underlying deduction guide F is instantiated -- either from an
1088 // explicitly-written deduction guide member, or from a constructor.
1089 // getInstantiatedFromMemberTemplate() can only handle the former case, so we
1090 // check the DeclContext kind.
1091 if (F->getLexicalDeclContext()->getDeclKind() ==
1092 clang::Decl::ClassTemplateSpecialization) {
1093 auto OuterLevelArgs = SemaRef.getTemplateInstantiationArgs(
1094 D: F, DC: F->getLexicalDeclContext(),
1095 /*Final=*/false, /*Innermost=*/std::nullopt,
1096 /*RelativeToPrimary=*/true,
1097 /*Pattern=*/nullptr,
1098 /*ForConstraintInstantiation=*/true);
1099 for (auto It : OuterLevelArgs)
1100 ArgsForBuildingRC.addOuterTemplateArguments(Args: It.Args);
1101 }
1102
1103 ExprResult E = SemaRef.SubstExpr(E: RC, TemplateArgs: ArgsForBuildingRC);
1104 if (E.isInvalid())
1105 return nullptr;
1106
1107 auto Conjunction =
1108 SemaRef.BuildBinOp(S: SemaRef.getCurScope(), OpLoc: SourceLocation{},
1109 Opc: BinaryOperatorKind::BO_LAnd, LHSExpr: E.get(), RHSExpr: IsDeducible);
1110 if (Conjunction.isInvalid())
1111 return nullptr;
1112 return Conjunction.getAs<Expr>();
1113}
1114// Build the is_deducible constraint for the alias deduction guides.
1115// [over.match.class.deduct]p3.3:
1116// ... and a constraint that is satisfied if and only if the arguments
1117// of A are deducible (see below) from the return type.
1118Expr *buildIsDeducibleConstraint(Sema &SemaRef,
1119 TypeAliasTemplateDecl *AliasTemplate,
1120 QualType ReturnType,
1121 SmallVector<NamedDecl *> TemplateParams) {
1122 ASTContext &Context = SemaRef.Context;
1123 // Constraint AST nodes must use uninstantiated depth.
1124 if (auto *PrimaryTemplate =
1125 AliasTemplate->getInstantiatedFromMemberTemplate();
1126 PrimaryTemplate && TemplateParams.size() > 0) {
1127 LocalInstantiationScope Scope(SemaRef);
1128
1129 // Adjust the depth for TemplateParams.
1130 unsigned AdjustDepth = PrimaryTemplate->getTemplateDepth();
1131 SmallVector<TemplateArgument> TransformedTemplateArgs;
1132 for (auto *TP : TemplateParams) {
1133 // Rebuild any internal references to earlier parameters and reindex
1134 // as we go.
1135 MultiLevelTemplateArgumentList Args;
1136 Args.setKind(TemplateSubstitutionKind::Rewrite);
1137 Args.addOuterTemplateArguments(Args: TransformedTemplateArgs);
1138 NamedDecl *NewParam = transformTemplateParameter(
1139 SemaRef, DC: AliasTemplate->getDeclContext(), TemplateParam: TP, Args,
1140 /*NewIndex=*/TransformedTemplateArgs.size(),
1141 NewDepth: getDepthAndIndex(ND: TP).first + AdjustDepth);
1142
1143 TemplateArgument NewTemplateArgument =
1144 Context.getInjectedTemplateArg(ParamDecl: NewParam);
1145 TransformedTemplateArgs.push_back(Elt: NewTemplateArgument);
1146 }
1147 // Transformed the ReturnType to restore the uninstantiated depth.
1148 MultiLevelTemplateArgumentList Args;
1149 Args.setKind(TemplateSubstitutionKind::Rewrite);
1150 Args.addOuterTemplateArguments(Args: TransformedTemplateArgs);
1151 ReturnType = SemaRef.SubstType(
1152 T: ReturnType, TemplateArgs: Args, Loc: AliasTemplate->getLocation(),
1153 Entity: Context.DeclarationNames.getCXXDeductionGuideName(TD: AliasTemplate));
1154 }
1155
1156 SmallVector<TypeSourceInfo *> IsDeducibleTypeTraitArgs = {
1157 Context.getTrivialTypeSourceInfo(
1158 T: Context.getDeducedTemplateSpecializationType(
1159 DK: DeducedKind::DeducedAsDependent,
1160 /*DeducedAsType=*/QualType(), Keyword: ElaboratedTypeKeyword::None,
1161 Template: TemplateName(AliasTemplate)),
1162 Loc: AliasTemplate->getLocation()), // template specialization type whose
1163 // arguments will be deduced.
1164 Context.getTrivialTypeSourceInfo(
1165 T: ReturnType, Loc: AliasTemplate->getLocation()), // type from which template
1166 // arguments are deduced.
1167 };
1168 return TypeTraitExpr::Create(
1169 C: Context, T: Context.getLogicalOperationType(), Loc: AliasTemplate->getLocation(),
1170 Kind: TypeTrait::BTT_IsDeducible, Args: IsDeducibleTypeTraitArgs,
1171 RParenLoc: AliasTemplate->getLocation(), /*Value*/ false);
1172}
1173
1174std::pair<TemplateDecl *, llvm::ArrayRef<TemplateArgument>>
1175getRHSTemplateDeclAndArgs(Sema &SemaRef, TypeAliasTemplateDecl *AliasTemplate) {
1176 auto RhsType = AliasTemplate->getTemplatedDecl()->getUnderlyingType();
1177 TemplateDecl *Template = nullptr;
1178 llvm::ArrayRef<TemplateArgument> AliasRhsTemplateArgs;
1179 if (const auto *TST = RhsType->getAs<TemplateSpecializationType>()) {
1180 // Cases where the RHS of the alias is dependent. e.g.
1181 // template<typename T>
1182 // using AliasFoo1 = Foo<T>; // a class/type alias template specialization
1183 Template = TST->getTemplateName().getAsTemplateDecl();
1184 AliasRhsTemplateArgs =
1185 TST->getAsNonAliasTemplateSpecializationType()->template_arguments();
1186 } else if (const auto *RT = RhsType->getAs<RecordType>()) {
1187 // Cases where template arguments in the RHS of the alias are not
1188 // dependent. e.g.
1189 // using AliasFoo = Foo<bool>;
1190 if (const auto *CTSD =
1191 dyn_cast<ClassTemplateSpecializationDecl>(Val: RT->getDecl())) {
1192 Template = CTSD->getSpecializedTemplate();
1193 AliasRhsTemplateArgs = CTSD->getTemplateArgs().asArray();
1194 }
1195 }
1196 return {Template, AliasRhsTemplateArgs};
1197}
1198
1199bool IsNonDeducedArgument(const TemplateArgument &TA) {
1200 // The following cases indicate the template argument is non-deducible:
1201 // 1. The result is null. E.g. When it comes from a default template
1202 // argument that doesn't appear in the alias declaration.
1203 // 2. The template parameter is a pack and that cannot be deduced from
1204 // the arguments within the alias declaration.
1205 // Non-deducible template parameters will persist in the transformed
1206 // deduction guide.
1207 return TA.isNull() ||
1208 (TA.getKind() == TemplateArgument::Pack &&
1209 llvm::any_of(Range: TA.pack_elements(), P: IsNonDeducedArgument));
1210}
1211
1212// Build deduction guides for a type alias template from the given underlying
1213// source deduction guide.
1214CXXDeductionGuideDecl *BuildDeductionGuideForTypeAlias(
1215 Sema &SemaRef, TypeAliasTemplateDecl *AliasTemplate,
1216 CXXDeductionGuideDecl *SourceDeductionGuide, SourceLocation Loc) {
1217 FunctionTemplateDecl *F =
1218 SourceDeductionGuide->getDescribedFunctionTemplate();
1219 assert(F && "deduction guide for alias template must be a function template");
1220
1221 LocalInstantiationScope Scope(SemaRef);
1222 Sema::NonSFINAEContext _1(SemaRef);
1223 Sema::InstantiatingTemplate BuildingDeductionGuides(
1224 SemaRef, AliasTemplate->getLocation(), F,
1225 Sema::InstantiatingTemplate::BuildingDeductionGuidesTag{});
1226 if (BuildingDeductionGuides.isInvalid())
1227 return nullptr;
1228
1229 auto &Context = SemaRef.Context;
1230 auto [Template, AliasRhsTemplateArgs] =
1231 getRHSTemplateDeclAndArgs(SemaRef, AliasTemplate);
1232
1233 // We need both types desugared, before we continue to perform type deduction.
1234 // The intent is to get the template argument list 'matched', e.g. in the
1235 // following case:
1236 //
1237 //
1238 // template <class T>
1239 // struct A {};
1240 // template <class T>
1241 // using Foo = A<A<T>>;
1242 // template <class U = int>
1243 // using Bar = Foo<U>;
1244 //
1245 // In terms of Bar, we want U (which has the default argument) to appear in
1246 // the synthesized deduction guide, but U would remain undeduced if we deduced
1247 // A<A<T>> using Foo<U> directly.
1248 //
1249 // Instead, we need to canonicalize both against A, i.e. A<A<T>> and A<A<U>>,
1250 // such that T can be deduced as U.
1251 auto RType = SourceDeductionGuide->getReturnType();
1252 // The (trailing) return type of the deduction guide.
1253 const auto *FReturnType = RType->getAs<TemplateSpecializationType>();
1254 if (const auto *ICNT = RType->getAsCanonical<InjectedClassNameType>())
1255 // implicitly-generated deduction guide.
1256 FReturnType = cast<TemplateSpecializationType>(
1257 Val: ICNT->getDecl()->getCanonicalTemplateSpecializationType(
1258 Ctx: SemaRef.Context));
1259
1260 ArrayRef<TemplateArgument> FReturnTemplateArgs;
1261 if (FReturnType) {
1262 FReturnTemplateArgs = FReturnType->template_arguments();
1263 } else if (const auto *RT = RType->getAs<RecordType>()) {
1264 // If the return type is a non-dependent class template specialization,
1265 // it might be resolved to a RecordType.
1266 if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(Val: RT->getDecl()))
1267 FReturnTemplateArgs = CTSD->getTemplateArgs().asArray();
1268 }
1269 assert(!FReturnTemplateArgs.empty() && "expected to see template arguments");
1270
1271 // Deduce template arguments of the deduction guide f from the RHS of
1272 // the alias.
1273 //
1274 // C++ [over.match.class.deduct]p3: ...For each function or function
1275 // template f in the guides of the template named by the
1276 // simple-template-id of the defining-type-id, the template arguments
1277 // of the return type of f are deduced from the defining-type-id of A
1278 // according to the process in [temp.deduct.type] with the exception
1279 // that deduction does not fail if not all template arguments are
1280 // deduced.
1281 //
1282 //
1283 // template<typename X, typename Y>
1284 // f(X, Y) -> f<Y, X>;
1285 //
1286 // template<typename U>
1287 // using alias = f<int, U>;
1288 //
1289 // The RHS of alias is f<int, U>, we deduced the template arguments of
1290 // the return type of the deduction guide from it: Y->int, X->U
1291 sema::TemplateDeductionInfo TDeduceInfo(Loc);
1292 // Must initialize n elements, this is required by DeduceTemplateArguments.
1293 SmallVector<DeducedTemplateArgument> DeduceResults(
1294 F->getTemplateParameters()->size());
1295
1296 // FIXME: DeduceTemplateArguments stops immediately at the first
1297 // non-deducible template argument. However, this doesn't seem to cause
1298 // issues for practice cases, we probably need to extend it to continue
1299 // performing deduction for rest of arguments to align with the C++
1300 // standard.
1301 SemaRef.DeduceTemplateArguments(
1302 TemplateParams: F->getTemplateParameters(), Ps: FReturnTemplateArgs,
1303 As: AliasRhsTemplateArgs, Info&: TDeduceInfo, Deduced&: DeduceResults,
1304 /*NumberOfArgumentsMustMatch=*/false);
1305
1306 SmallVector<TemplateArgument> DeducedArgs;
1307 SmallVector<unsigned> NonDeducedTemplateParamsInFIndex;
1308 // !!NOTE: DeduceResults respects the sequence of template parameters of
1309 // the deduction guide f.
1310 for (unsigned Index = 0; Index < DeduceResults.size(); ++Index) {
1311 const auto &D = DeduceResults[Index];
1312 if (!IsNonDeducedArgument(TA: D))
1313 DeducedArgs.push_back(Elt: D);
1314 else
1315 NonDeducedTemplateParamsInFIndex.push_back(Elt: Index);
1316 }
1317 auto DeducedAliasTemplateParams =
1318 TemplateParamsReferencedInTemplateArgumentList(
1319 SemaRef, TemplateParamsList: AliasTemplate->getTemplateParameters(), DeducedArgs);
1320 // All template arguments null by default.
1321 SmallVector<TemplateArgument> TemplateArgsForBuildingFPrime(
1322 F->getTemplateParameters()->size());
1323
1324 // Create a template parameter list for the synthesized deduction guide f'.
1325 //
1326 // C++ [over.match.class.deduct]p3.2:
1327 // If f is a function template, f' is a function template whose template
1328 // parameter list consists of all the template parameters of A
1329 // (including their default template arguments) that appear in the above
1330 // deductions or (recursively) in their default template arguments
1331 SmallVector<NamedDecl *> FPrimeTemplateParams;
1332 // Store template arguments that refer to the newly-created template
1333 // parameters, used for building `TemplateArgsForBuildingFPrime`.
1334 SmallVector<TemplateArgument, 16> TransformedDeducedAliasArgs(
1335 AliasTemplate->getTemplateParameters()->size());
1336 // We might be already within a pack expansion, but rewriting template
1337 // parameters is independent of that. (We may or may not expand new packs
1338 // when rewriting. So clear the state)
1339 Sema::ArgPackSubstIndexRAII PackSubstReset(SemaRef, std::nullopt);
1340
1341 for (unsigned AliasTemplateParamIdx : DeducedAliasTemplateParams) {
1342 auto *TP =
1343 AliasTemplate->getTemplateParameters()->getParam(Idx: AliasTemplateParamIdx);
1344 // Rebuild any internal references to earlier parameters and reindex as
1345 // we go.
1346 MultiLevelTemplateArgumentList Args;
1347 Args.setKind(TemplateSubstitutionKind::Rewrite);
1348 Args.addOuterTemplateArguments(Args: TransformedDeducedAliasArgs);
1349 NamedDecl *NewParam = transformTemplateParameter(
1350 SemaRef, DC: AliasTemplate->getDeclContext(), TemplateParam: TP, Args,
1351 /*NewIndex=*/FPrimeTemplateParams.size(), NewDepth: getDepthAndIndex(ND: TP).first);
1352 FPrimeTemplateParams.push_back(Elt: NewParam);
1353
1354 TemplateArgument NewTemplateArgument =
1355 Context.getInjectedTemplateArg(ParamDecl: NewParam);
1356 TransformedDeducedAliasArgs[AliasTemplateParamIdx] = NewTemplateArgument;
1357 }
1358 unsigned FirstUndeducedParamIdx = FPrimeTemplateParams.size();
1359
1360 // To form a deduction guide f' from f, we leverage clang's instantiation
1361 // mechanism, we construct a template argument list where the template
1362 // arguments refer to the newly-created template parameters of f', and
1363 // then apply instantiation on this template argument list to instantiate
1364 // f, this ensures all template parameter occurrences are updated
1365 // correctly.
1366 //
1367 // The template argument list is formed, in order, from
1368 // 1) For the template parameters of the alias, the corresponding deduced
1369 // template arguments
1370 // 2) For the non-deduced template parameters of f. the
1371 // (rebuilt) template arguments corresponding.
1372 //
1373 // Note: the non-deduced template arguments of `f` might refer to arguments
1374 // deduced in 1), as in a type constraint.
1375 MultiLevelTemplateArgumentList Args;
1376 Args.setKind(TemplateSubstitutionKind::Rewrite);
1377 Args.addOuterTemplateArguments(Args: TransformedDeducedAliasArgs);
1378 for (unsigned Index = 0; Index < DeduceResults.size(); ++Index) {
1379 const auto &D = DeduceResults[Index];
1380 auto *TP = F->getTemplateParameters()->getParam(Idx: Index);
1381 if (IsNonDeducedArgument(TA: D)) {
1382 // 2): Non-deduced template parameters would be substituted later.
1383 continue;
1384 }
1385 TemplateArgumentLoc Input =
1386 SemaRef.getTrivialTemplateArgumentLoc(Arg: D, NTTPType: QualType(), Loc: SourceLocation{});
1387 TemplateArgumentListInfo Output;
1388 if (SemaRef.SubstTemplateArguments(Args: Input, TemplateArgs: Args, Outputs&: Output))
1389 return nullptr;
1390 assert(TemplateArgsForBuildingFPrime[Index].isNull() &&
1391 "InstantiatedArgs must be null before setting");
1392 // CheckTemplateArgument is necessary for NTTP initializations.
1393 // FIXME: We may want to call CheckTemplateArguments instead, but we cannot
1394 // match packs as usual, since packs can appear in the middle of the
1395 // parameter list of a synthesized CTAD guide. See also the FIXME in
1396 // test/SemaCXX/cxx20-ctad-type-alias.cpp:test25.
1397 Sema::CheckTemplateArgumentInfo CTAI;
1398 for (auto TA : Output.arguments())
1399 if (SemaRef.CheckTemplateArgument(
1400 Param: TP, Arg&: TA, Template: F, TemplateLoc: F->getLocation(), RAngleLoc: F->getLocation(),
1401 /*ArgumentPackIndex=*/-1, CTAI,
1402 CTAK: Sema::CheckTemplateArgumentKind::CTAK_Specified))
1403 return nullptr;
1404 if (Input.getArgument().getKind() == TemplateArgument::Pack) {
1405 // We will substitute the non-deduced template arguments with these
1406 // transformed (unpacked at this point) arguments, where that substitution
1407 // requires a pack for the corresponding parameter packs.
1408 TemplateArgsForBuildingFPrime[Index] =
1409 TemplateArgument::CreatePackCopy(Context, Args: CTAI.SugaredConverted);
1410 } else {
1411 assert(Output.arguments().size() == 1);
1412 TemplateArgsForBuildingFPrime[Index] = CTAI.SugaredConverted[0];
1413 }
1414 }
1415
1416 // Case 2)
1417 // ...followed by the template parameters of f that were not deduced
1418 // (including their default template arguments)
1419 for (unsigned FTemplateParamIdx : NonDeducedTemplateParamsInFIndex) {
1420 auto *TP = F->getTemplateParameters()->getParam(Idx: FTemplateParamIdx);
1421 MultiLevelTemplateArgumentList Args;
1422 Args.setKind(TemplateSubstitutionKind::Rewrite);
1423 // We take a shortcut here, it is ok to reuse the
1424 // TemplateArgsForBuildingFPrime.
1425 Args.addOuterTemplateArguments(Args: TemplateArgsForBuildingFPrime);
1426 NamedDecl *NewParam = transformTemplateParameter(
1427 SemaRef, DC: F->getDeclContext(), TemplateParam: TP, Args, NewIndex: FPrimeTemplateParams.size(),
1428 NewDepth: getDepthAndIndex(ND: TP).first);
1429 FPrimeTemplateParams.push_back(Elt: NewParam);
1430
1431 assert(TemplateArgsForBuildingFPrime[FTemplateParamIdx].isNull() &&
1432 "The argument must be null before setting");
1433 TemplateArgsForBuildingFPrime[FTemplateParamIdx] =
1434 Context.getInjectedTemplateArg(ParamDecl: NewParam);
1435 }
1436
1437 auto *TemplateArgListForBuildingFPrime =
1438 TemplateArgumentList::CreateCopy(Context, Args: TemplateArgsForBuildingFPrime);
1439 // Form the f' by substituting the template arguments into f.
1440 if (auto *FPrime = SemaRef.InstantiateFunctionDeclaration(
1441 FTD: F, Args: TemplateArgListForBuildingFPrime, Loc: AliasTemplate->getLocation(),
1442 CSC: Sema::CodeSynthesisContext::BuildingDeductionGuides)) {
1443 auto *GG = cast<CXXDeductionGuideDecl>(Val: FPrime);
1444
1445 Expr *IsDeducible = buildIsDeducibleConstraint(
1446 SemaRef, AliasTemplate, ReturnType: FPrime->getReturnType(), TemplateParams: FPrimeTemplateParams);
1447 Expr *RequiresClause =
1448 buildAssociatedConstraints(SemaRef, F, AliasTemplate, DeduceResults,
1449 FirstUndeducedParamIdx, IsDeducible);
1450
1451 TemplateParameterList *FPrimeTemplateParamList = nullptr;
1452 if (!FPrimeTemplateParams.empty())
1453 FPrimeTemplateParamList = TemplateParameterList::Create(
1454 C: Context, TemplateLoc: AliasTemplate->getTemplateParameters()->getTemplateLoc(),
1455 LAngleLoc: AliasTemplate->getTemplateParameters()->getLAngleLoc(),
1456 Params: FPrimeTemplateParams,
1457 RAngleLoc: AliasTemplate->getTemplateParameters()->getRAngleLoc(),
1458 /*RequiresClause=*/RequiresClause);
1459
1460 auto *DGuide = buildDeductionGuide(
1461 SemaRef, OriginalTemplate: AliasTemplate, TemplateParams: FPrimeTemplateParamList,
1462 Ctor: GG->getCorrespondingConstructor(), ES: GG->getExplicitSpecifier(),
1463 TInfo: GG->getTypeSourceInfo(), LocStart: AliasTemplate->getBeginLoc(),
1464 Loc: AliasTemplate->getLocation(), LocEnd: AliasTemplate->getEndLoc(),
1465 IsImplicit: F->isImplicit());
1466 DGuide->setDeductionCandidateKind(GG->getDeductionCandidateKind());
1467 DGuide->setSourceDeductionGuide(SourceDeductionGuide);
1468 DGuide->setSourceDeductionGuideKind(
1469 CXXDeductionGuideDecl::SourceDeductionGuideKind::Alias);
1470 return DGuide;
1471 }
1472 return nullptr;
1473}
1474
1475void DeclareImplicitDeductionGuidesForTypeAlias(
1476 Sema &SemaRef, TypeAliasTemplateDecl *AliasTemplate, SourceLocation Loc) {
1477 if (AliasTemplate->isInvalidDecl())
1478 return;
1479 auto &Context = SemaRef.Context;
1480 auto [Template, AliasRhsTemplateArgs] =
1481 getRHSTemplateDeclAndArgs(SemaRef, AliasTemplate);
1482 if (!Template)
1483 return;
1484 auto SourceDeductionGuides = getSourceDeductionGuides(
1485 Name: Context.DeclarationNames.getCXXDeductionGuideName(TD: AliasTemplate),
1486 DC: AliasTemplate->getDeclContext());
1487
1488 DeclarationNameInfo NameInfo(
1489 Context.DeclarationNames.getCXXDeductionGuideName(TD: Template), Loc);
1490 LookupResult Guides(SemaRef, NameInfo, clang::Sema::LookupOrdinaryName);
1491 SemaRef.LookupQualifiedName(R&: Guides, LookupCtx: Template->getDeclContext());
1492 Guides.suppressDiagnostics();
1493
1494 for (auto *G : Guides) {
1495 if (auto *DG = dyn_cast<CXXDeductionGuideDecl>(Val: G)) {
1496 if (SourceDeductionGuides.contains(V: DG))
1497 continue;
1498 // The deduction guide is a non-template function decl, we just clone it.
1499 auto *FunctionType =
1500 SemaRef.Context.getTrivialTypeSourceInfo(T: DG->getType());
1501 FunctionProtoTypeLoc FPTL =
1502 FunctionType->getTypeLoc().castAs<FunctionProtoTypeLoc>();
1503
1504 // Clone the parameters.
1505 for (unsigned I = 0, N = DG->getNumParams(); I != N; ++I) {
1506 const auto *P = DG->getParamDecl(i: I);
1507 auto *TSI = SemaRef.Context.getTrivialTypeSourceInfo(T: P->getType());
1508 ParmVarDecl *NewParam = ParmVarDecl::Create(
1509 C&: SemaRef.Context, DC: G->getDeclContext(),
1510 StartLoc: DG->getParamDecl(i: I)->getBeginLoc(), IdLoc: P->getLocation(), Id: nullptr,
1511 T: TSI->getType(), TInfo: TSI, S: SC_None, DefArg: nullptr);
1512 NewParam->setScopeInfo(scopeDepth: 0, parameterIndex: I);
1513 FPTL.setParam(i: I, VD: NewParam);
1514 }
1515 auto *Transformed = cast<CXXDeductionGuideDecl>(Val: buildDeductionGuide(
1516 SemaRef, OriginalTemplate: AliasTemplate, /*TemplateParams=*/nullptr,
1517 /*Constructor=*/Ctor: nullptr, ES: DG->getExplicitSpecifier(), TInfo: FunctionType,
1518 LocStart: AliasTemplate->getBeginLoc(), Loc: AliasTemplate->getLocation(),
1519 LocEnd: AliasTemplate->getEndLoc(), IsImplicit: DG->isImplicit()));
1520 Transformed->setSourceDeductionGuide(DG);
1521 Transformed->setSourceDeductionGuideKind(
1522 CXXDeductionGuideDecl::SourceDeductionGuideKind::Alias);
1523
1524 // FIXME: Here the synthesized deduction guide is not a templated
1525 // function. Per [dcl.decl]p4, the requires-clause shall be present only
1526 // if the declarator declares a templated function, a bug in standard?
1527 AssociatedConstraint Constraint(buildIsDeducibleConstraint(
1528 SemaRef, AliasTemplate, ReturnType: Transformed->getReturnType(), TemplateParams: {}));
1529 if (const AssociatedConstraint &RC = DG->getTrailingRequiresClause()) {
1530 auto Conjunction = SemaRef.BuildBinOp(
1531 S: SemaRef.getCurScope(), OpLoc: SourceLocation{},
1532 Opc: BinaryOperatorKind::BO_LAnd, LHSExpr: const_cast<Expr *>(RC.ConstraintExpr),
1533 RHSExpr: const_cast<Expr *>(Constraint.ConstraintExpr));
1534 if (!Conjunction.isInvalid()) {
1535 Constraint.ConstraintExpr = Conjunction.getAs<Expr>();
1536 Constraint.ArgPackSubstIndex = RC.ArgPackSubstIndex;
1537 }
1538 }
1539 Transformed->setTrailingRequiresClause(Constraint);
1540 continue;
1541 }
1542 FunctionTemplateDecl *F = dyn_cast<FunctionTemplateDecl>(Val: G);
1543 if (!F || SourceDeductionGuides.contains(V: F->getTemplatedDecl()))
1544 continue;
1545 // The **aggregate** deduction guides are handled in a different code path
1546 // (DeclareAggregateDeductionGuideFromInitList), which involves the tricky
1547 // cache.
1548 auto *DGuide = cast<CXXDeductionGuideDecl>(Val: F->getTemplatedDecl());
1549 if (DGuide->getDeductionCandidateKind() == DeductionCandidate::Aggregate)
1550 continue;
1551
1552 BuildDeductionGuideForTypeAlias(SemaRef, AliasTemplate, SourceDeductionGuide: DGuide, Loc);
1553 }
1554}
1555
1556// Build an aggregate deduction guide for a type alias template.
1557CXXDeductionGuideDecl *DeclareAggregateDeductionGuideForTypeAlias(
1558 Sema &SemaRef, TypeAliasTemplateDecl *AliasTemplate,
1559 MutableArrayRef<QualType> ParamTypes, SourceLocation Loc) {
1560 TemplateDecl *RHSTemplate =
1561 getRHSTemplateDeclAndArgs(SemaRef, AliasTemplate).first;
1562 if (!RHSTemplate)
1563 return nullptr;
1564
1565 llvm::SmallVector<TypedefNameDecl *> TypedefDecls;
1566 llvm::SmallVector<QualType> NewParamTypes;
1567 ExtractTypeForDeductionGuide TypeAliasTransformer(SemaRef, TypedefDecls);
1568 for (QualType P : ParamTypes) {
1569 QualType Type = TypeAliasTransformer.TransformType(T: P);
1570 if (Type.isNull())
1571 return nullptr;
1572 NewParamTypes.push_back(Elt: Type);
1573 }
1574
1575 auto *RHSDeductionGuide = SemaRef.DeclareAggregateDeductionGuideFromInitList(
1576 Template: RHSTemplate, ParamTypes: NewParamTypes, Loc);
1577 if (!RHSDeductionGuide)
1578 return nullptr;
1579
1580 for (TypedefNameDecl *TD : TypedefDecls)
1581 TD->setDeclContext(RHSDeductionGuide);
1582
1583 return BuildDeductionGuideForTypeAlias(SemaRef, AliasTemplate,
1584 SourceDeductionGuide: RHSDeductionGuide, Loc);
1585}
1586
1587} // namespace
1588
1589CXXDeductionGuideDecl *Sema::DeclareAggregateDeductionGuideFromInitList(
1590 TemplateDecl *Template, MutableArrayRef<QualType> ParamTypes,
1591 SourceLocation Loc) {
1592 llvm::FoldingSetNodeID ID;
1593 ID.AddPointer(Ptr: Template);
1594 for (auto &T : ParamTypes)
1595 T.getCanonicalType().Profile(ID);
1596 unsigned Hash = ID.ComputeHash();
1597
1598 auto Found = AggregateDeductionCandidates.find(Val: Hash);
1599 if (Found != AggregateDeductionCandidates.end())
1600 return Found->getSecond();
1601
1602 if (auto *AliasTemplate = llvm::dyn_cast<TypeAliasTemplateDecl>(Val: Template)) {
1603 if (auto *GD = DeclareAggregateDeductionGuideForTypeAlias(
1604 SemaRef&: *this, AliasTemplate, ParamTypes, Loc)) {
1605 GD->setDeductionCandidateKind(DeductionCandidate::Aggregate);
1606 AggregateDeductionCandidates[Hash] = GD;
1607 return GD;
1608 }
1609 }
1610
1611 if (CXXRecordDecl *DefRecord =
1612 cast<CXXRecordDecl>(Val: Template->getTemplatedDecl())->getDefinition()) {
1613 if (TemplateDecl *DescribedTemplate =
1614 DefRecord->getDescribedClassTemplate())
1615 Template = DescribedTemplate;
1616 }
1617
1618 DeclContext *DC = Template->getDeclContext();
1619 if (DC->isDependentContext())
1620 return nullptr;
1621
1622 ConvertConstructorToDeductionGuideTransform Transform(
1623 *this, cast<ClassTemplateDecl>(Val: Template));
1624 if (!isCompleteType(Loc, T: Transform.DeducedType))
1625 return nullptr;
1626
1627 // In case we were expanding a pack when we attempted to declare deduction
1628 // guides, turn off pack expansion for everything we're about to do.
1629 ArgPackSubstIndexRAII SubstIndex(*this, std::nullopt);
1630 // Create a template instantiation record to track the "instantiation" of
1631 // constructors into deduction guides.
1632 InstantiatingTemplate BuildingDeductionGuides(
1633 *this, Loc, Template,
1634 Sema::InstantiatingTemplate::BuildingDeductionGuidesTag{});
1635 if (BuildingDeductionGuides.isInvalid())
1636 return nullptr;
1637
1638 ClassTemplateDecl *Pattern =
1639 Transform.NestedPattern ? Transform.NestedPattern : Transform.Template;
1640 ContextRAII SavedContext(*this, Pattern->getTemplatedDecl());
1641
1642 CXXDeductionGuideDecl *GD = Transform.buildSimpleDeductionGuide(ParamTypes);
1643 SavedContext.pop();
1644 GD->setDeductionCandidateKind(DeductionCandidate::Aggregate);
1645 AggregateDeductionCandidates[Hash] = GD;
1646 return GD;
1647}
1648
1649void Sema::DeclareImplicitDeductionGuides(TemplateDecl *Template,
1650 SourceLocation Loc) {
1651 if (auto *AliasTemplate = llvm::dyn_cast<TypeAliasTemplateDecl>(Val: Template)) {
1652 DeclareImplicitDeductionGuidesForTypeAlias(SemaRef&: *this, AliasTemplate, Loc);
1653 return;
1654 }
1655 CXXRecordDecl *DefRecord =
1656 dyn_cast_or_null<CXXRecordDecl>(Val: Template->getTemplatedDecl());
1657 if (!DefRecord)
1658 return;
1659 if (const CXXRecordDecl *Definition = DefRecord->getDefinition()) {
1660 if (TemplateDecl *DescribedTemplate =
1661 Definition->getDescribedClassTemplate())
1662 Template = DescribedTemplate;
1663 }
1664
1665 DeclContext *DC = Template->getDeclContext();
1666 if (DC->isDependentContext())
1667 return;
1668
1669 ConvertConstructorToDeductionGuideTransform Transform(
1670 *this, cast<ClassTemplateDecl>(Val: Template));
1671 if (!isCompleteType(Loc, T: Transform.DeducedType))
1672 return;
1673
1674 if (hasDeclaredDeductionGuides(Name: Transform.DeductionGuideName, DC))
1675 return;
1676
1677 // In case we were expanding a pack when we attempted to declare deduction
1678 // guides, turn off pack expansion for everything we're about to do.
1679 ArgPackSubstIndexRAII SubstIndex(*this, std::nullopt);
1680 // Create a template instantiation record to track the "instantiation" of
1681 // constructors into deduction guides.
1682 InstantiatingTemplate BuildingDeductionGuides(
1683 *this, Loc, Template,
1684 Sema::InstantiatingTemplate::BuildingDeductionGuidesTag{});
1685 if (BuildingDeductionGuides.isInvalid())
1686 return;
1687
1688 // Convert declared constructors into deduction guide templates.
1689 // FIXME: Skip constructors for which deduction must necessarily fail (those
1690 // for which some class template parameter without a default argument never
1691 // appears in a deduced context).
1692 ClassTemplateDecl *Pattern =
1693 Transform.NestedPattern ? Transform.NestedPattern : Transform.Template;
1694 ContextRAII SavedContext(*this, Pattern->getTemplatedDecl());
1695 llvm::SmallPtrSet<NamedDecl *, 8> ProcessedCtors;
1696 bool AddedAny = false;
1697 for (NamedDecl *D : LookupConstructors(Class: Pattern->getTemplatedDecl())) {
1698 D = D->getUnderlyingDecl();
1699 if (D->isInvalidDecl() || D->isImplicit())
1700 continue;
1701
1702 D = cast<NamedDecl>(Val: D->getCanonicalDecl());
1703
1704 // Within C++20 modules, we may have multiple same constructors in
1705 // multiple same RecordDecls. And it doesn't make sense to create
1706 // duplicated deduction guides for the duplicated constructors.
1707 if (ProcessedCtors.count(Ptr: D))
1708 continue;
1709
1710 auto *FTD = dyn_cast<FunctionTemplateDecl>(Val: D);
1711 auto *CD =
1712 dyn_cast_or_null<CXXConstructorDecl>(Val: FTD ? FTD->getTemplatedDecl() : D);
1713 // Class-scope explicit specializations (MS extension) do not result in
1714 // deduction guides.
1715 if (!CD || (!FTD && CD->isFunctionTemplateSpecialization()))
1716 continue;
1717
1718 // Cannot make a deduction guide when unparsed arguments are present.
1719 if (llvm::any_of(Range: CD->parameters(), P: [](ParmVarDecl *P) {
1720 return !P || P->hasUnparsedDefaultArg();
1721 }))
1722 continue;
1723
1724 ProcessedCtors.insert(Ptr: D);
1725 Transform.transformConstructor(FTD, CD);
1726 AddedAny = true;
1727 }
1728
1729 // C++17 [over.match.class.deduct]
1730 // -- If C is not defined or does not declare any constructors, an
1731 // additional function template derived as above from a hypothetical
1732 // constructor C().
1733 if (!AddedAny)
1734 Transform.buildSimpleDeductionGuide(ParamTypes: {});
1735
1736 // -- An additional function template derived as above from a hypothetical
1737 // constructor C(C), called the copy deduction candidate.
1738 Transform.buildSimpleDeductionGuide(ParamTypes: Transform.DeducedType)
1739 ->setDeductionCandidateKind(DeductionCandidate::Copy);
1740
1741 SavedContext.pop();
1742}
1743