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/BuiltinTraits.h"
32#include "clang/Basic/LLVM.h"
33#include "clang/Basic/SourceLocation.h"
34#include "clang/Basic/Specifiers.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(TemplateArgs: DeducedArgs, /*OnlyDeduced=*/false,
893 Depth: TemplateParamsList->getDepth(),
894 Used&: ReferencedTemplateParams);
895
896 auto MarkDefaultArgs = [&](auto *Param) {
897 if (!Param->hasDefaultArgument())
898 return;
899 SemaRef.MarkUsedTemplateParameters(
900 Param->getDefaultArgument().getArgument(), /*OnlyDeduced=*/false,
901 TemplateParamsList->getDepth(), ReferencedTemplateParams);
902 };
903
904 for (unsigned Index = 0; Index < TemplateParamsList->size(); ++Index) {
905 if (!ReferencedTemplateParams[Index])
906 continue;
907 auto *Param = TemplateParamsList->getParam(Idx: Index);
908 if (auto *TTPD = dyn_cast<TemplateTypeParmDecl>(Val: Param))
909 MarkDefaultArgs(TTPD);
910 else if (auto *NTTPD = dyn_cast<NonTypeTemplateParmDecl>(Val: Param))
911 MarkDefaultArgs(NTTPD);
912 else
913 MarkDefaultArgs(cast<TemplateTemplateParmDecl>(Val: Param));
914 }
915
916 SmallVector<unsigned> Results;
917 for (unsigned Index = 0; Index < TemplateParamsList->size(); ++Index) {
918 if (ReferencedTemplateParams[Index])
919 Results.push_back(Elt: Index);
920 }
921 return Results;
922}
923
924bool hasDeclaredDeductionGuides(DeclarationName Name, DeclContext *DC) {
925 // Check whether we've already declared deduction guides for this template.
926 // FIXME: Consider storing a flag on the template to indicate this.
927 assert(Name.getNameKind() ==
928 DeclarationName::NameKind::CXXDeductionGuideName &&
929 "name must be a deduction guide name");
930 auto Existing = DC->lookup(Name);
931 for (auto *D : Existing)
932 if (D->isImplicit())
933 return true;
934 return false;
935}
936
937// Returns all source deduction guides associated with the declared
938// deduction guides that have the specified deduction guide name.
939llvm::DenseSet<const NamedDecl *> getSourceDeductionGuides(DeclarationName Name,
940 DeclContext *DC) {
941 assert(Name.getNameKind() ==
942 DeclarationName::NameKind::CXXDeductionGuideName &&
943 "name must be a deduction guide name");
944 llvm::DenseSet<const NamedDecl *> Result;
945 for (auto *D : DC->lookup(Name)) {
946 if (const auto *FTD = dyn_cast<FunctionTemplateDecl>(Val: D))
947 D = FTD->getTemplatedDecl();
948
949 if (const auto *GD = dyn_cast<CXXDeductionGuideDecl>(Val: D)) {
950 assert(GD->getSourceDeductionGuide() &&
951 "deduction guide for alias template must have a source deduction "
952 "guide");
953 Result.insert(V: GD->getSourceDeductionGuide());
954 }
955 }
956 return Result;
957}
958
959// Build the associated constraints for the alias deduction guides.
960// C++ [over.match.class.deduct]p3.3:
961// The associated constraints ([temp.constr.decl]) are the conjunction of the
962// associated constraints of g and a constraint that is satisfied if and only
963// if the arguments of A are deducible (see below) from the return type.
964//
965// The return result is expected to be the require-clause for the synthesized
966// alias deduction guide.
967Expr *
968buildAssociatedConstraints(Sema &SemaRef, FunctionTemplateDecl *F,
969 TypeAliasTemplateDecl *AliasTemplate,
970 ArrayRef<DeducedTemplateArgument> DeduceResults,
971 unsigned FirstUndeducedParamIdx, Expr *IsDeducible) {
972 Expr *RC = F->getTemplateParameters()->getRequiresClause();
973 if (!RC)
974 return IsDeducible;
975
976 ASTContext &Context = SemaRef.Context;
977 LocalInstantiationScope Scope(SemaRef);
978
979 // In the clang AST, constraint nodes are deliberately not instantiated unless
980 // they are actively being evaluated. Consequently, occurrences of template
981 // parameters in the require-clause expression have a subtle "depth"
982 // difference compared to normal occurrences in places, such as function
983 // parameters. When transforming the require-clause, we must take this
984 // distinction into account:
985 //
986 // 1) In the transformed require-clause, occurrences of template parameters
987 // must use the "uninstantiated" depth;
988 // 2) When substituting on the require-clause expr of the underlying
989 // deduction guide, we must use the entire set of template argument lists;
990 //
991 // It's important to note that we're performing this transformation on an
992 // *instantiated* AliasTemplate.
993
994 // For 1), if the alias template is nested within a class template, we
995 // calcualte the 'uninstantiated' depth by adding the substitution level back.
996 unsigned AdjustDepth = 0;
997 if (auto *PrimaryTemplate =
998 AliasTemplate->getInstantiatedFromMemberTemplate())
999 AdjustDepth = PrimaryTemplate->getTemplateDepth();
1000
1001 // We rebuild all template parameters with the uninstantiated depth, and
1002 // build template arguments refer to them.
1003 SmallVector<TemplateArgument> AdjustedAliasTemplateArgs;
1004
1005 for (auto *TP : *AliasTemplate->getTemplateParameters()) {
1006 // Rebuild any internal references to earlier parameters and reindex
1007 // as we go.
1008 MultiLevelTemplateArgumentList Args;
1009 Args.setKind(TemplateSubstitutionKind::Rewrite);
1010 Args.addOuterTemplateArguments(Args: AdjustedAliasTemplateArgs);
1011 NamedDecl *NewParam = transformTemplateParameter(
1012 SemaRef, DC: AliasTemplate->getDeclContext(), TemplateParam: TP, Args,
1013 /*NewIndex=*/AdjustedAliasTemplateArgs.size(),
1014 NewDepth: getDepthAndIndex(ND: TP).first + AdjustDepth);
1015
1016 TemplateArgument NewTemplateArgument =
1017 Context.getInjectedTemplateArg(ParamDecl: NewParam);
1018 AdjustedAliasTemplateArgs.push_back(Elt: NewTemplateArgument);
1019 }
1020 // Template arguments used to transform the template arguments in
1021 // DeducedResults.
1022 SmallVector<TemplateArgument> TemplateArgsForBuildingRC(
1023 F->getTemplateParameters()->size());
1024 // Transform the transformed template args
1025 MultiLevelTemplateArgumentList Args;
1026 Args.setKind(TemplateSubstitutionKind::Rewrite);
1027 Args.addOuterTemplateArguments(Args: AdjustedAliasTemplateArgs);
1028
1029 for (unsigned Index = 0; Index < DeduceResults.size(); ++Index) {
1030 const auto &D = DeduceResults[Index];
1031 if (D.isNull()) { // non-deduced template parameters of f
1032 NamedDecl *TP = F->getTemplateParameters()->getParam(Idx: Index);
1033 MultiLevelTemplateArgumentList Args;
1034 Args.setKind(TemplateSubstitutionKind::Rewrite);
1035 Args.addOuterTemplateArguments(Args: TemplateArgsForBuildingRC);
1036 // Rebuild the template parameter with updated depth and index.
1037 NamedDecl *NewParam =
1038 transformTemplateParameter(SemaRef, DC: F->getDeclContext(), TemplateParam: TP, Args,
1039 /*NewIndex=*/FirstUndeducedParamIdx,
1040 NewDepth: getDepthAndIndex(ND: TP).first + AdjustDepth);
1041 FirstUndeducedParamIdx += 1;
1042 assert(TemplateArgsForBuildingRC[Index].isNull());
1043 TemplateArgsForBuildingRC[Index] =
1044 Context.getInjectedTemplateArg(ParamDecl: NewParam);
1045 continue;
1046 }
1047 TemplateArgumentLoc Input =
1048 SemaRef.getTrivialTemplateArgumentLoc(Arg: D, NTTPType: QualType(), Loc: SourceLocation{});
1049 TemplateArgumentLoc Output;
1050 if (!SemaRef.SubstTemplateArgument(Input, TemplateArgs: Args, Output)) {
1051 assert(TemplateArgsForBuildingRC[Index].isNull() &&
1052 "InstantiatedArgs must be null before setting");
1053 TemplateArgsForBuildingRC[Index] = Output.getArgument();
1054 }
1055 }
1056
1057 // A list of template arguments for transforming the require-clause of F.
1058 // It must contain the entire set of template argument lists.
1059 MultiLevelTemplateArgumentList ArgsForBuildingRC;
1060 ArgsForBuildingRC.setKind(clang::TemplateSubstitutionKind::Rewrite);
1061 ArgsForBuildingRC.addOuterTemplateArguments(Args: TemplateArgsForBuildingRC);
1062 // For 2), if the underlying deduction guide F is nested in a class template,
1063 // we need the entire template argument list, as the constraint AST in the
1064 // require-clause of F remains completely uninstantiated.
1065 //
1066 // For example:
1067 // template <typename T> // depth 0
1068 // struct Outer {
1069 // template <typename U>
1070 // struct Foo { Foo(U); };
1071 //
1072 // template <typename U> // depth 1
1073 // requires C<U>
1074 // Foo(U) -> Foo<int>;
1075 // };
1076 // template <typename U>
1077 // using AFoo = Outer<int>::Foo<U>;
1078 //
1079 // In this scenario, the deduction guide for `Foo` inside `Outer<int>`:
1080 // - The occurrence of U in the require-expression is [depth:1, index:0]
1081 // - The occurrence of U in the function parameter is [depth:0, index:0]
1082 // - The template parameter of U is [depth:0, index:0]
1083 //
1084 // We add the outer template arguments which is [int] to the multi-level arg
1085 // list to ensure that the occurrence U in `C<U>` will be replaced with int
1086 // during the substitution.
1087 //
1088 // NOTE: The underlying deduction guide F is instantiated -- either from an
1089 // explicitly-written deduction guide member, or from a constructor.
1090 // getInstantiatedFromMemberTemplate() can only handle the former case, so we
1091 // check the DeclContext kind.
1092 if (F->getLexicalDeclContext()->getDeclKind() ==
1093 clang::Decl::ClassTemplateSpecialization) {
1094 auto OuterLevelArgs = SemaRef.getTemplateInstantiationArgs(
1095 D: F, DC: F->getLexicalDeclContext(),
1096 /*Final=*/false, /*Innermost=*/std::nullopt,
1097 /*RelativeToPrimary=*/true,
1098 /*Pattern=*/nullptr,
1099 /*ForConstraintInstantiation=*/true);
1100 for (auto It : OuterLevelArgs)
1101 ArgsForBuildingRC.addOuterTemplateArguments(Args: It.Args);
1102 }
1103
1104 ExprResult E = SemaRef.SubstExpr(E: RC, TemplateArgs: ArgsForBuildingRC);
1105 if (E.isInvalid())
1106 return nullptr;
1107
1108 auto Conjunction =
1109 SemaRef.BuildBinOp(S: SemaRef.getCurScope(), OpLoc: SourceLocation{},
1110 Opc: BinaryOperatorKind::BO_LAnd, LHSExpr: E.get(), RHSExpr: IsDeducible);
1111 if (Conjunction.isInvalid())
1112 return nullptr;
1113 return Conjunction.getAs<Expr>();
1114}
1115// Build the is_deducible constraint for the alias deduction guides.
1116// [over.match.class.deduct]p3.3:
1117// ... and a constraint that is satisfied if and only if the arguments
1118// of A are deducible (see below) from the return type.
1119Expr *buildIsDeducibleConstraint(Sema &SemaRef,
1120 TypeAliasTemplateDecl *AliasTemplate,
1121 QualType ReturnType,
1122 SmallVector<NamedDecl *> TemplateParams) {
1123 ASTContext &Context = SemaRef.Context;
1124 // Constraint AST nodes must use uninstantiated depth.
1125 if (auto *PrimaryTemplate =
1126 AliasTemplate->getInstantiatedFromMemberTemplate();
1127 PrimaryTemplate && TemplateParams.size() > 0) {
1128 LocalInstantiationScope Scope(SemaRef);
1129
1130 // Adjust the depth for TemplateParams.
1131 unsigned AdjustDepth = PrimaryTemplate->getTemplateDepth();
1132 SmallVector<TemplateArgument> TransformedTemplateArgs;
1133 for (auto *TP : TemplateParams) {
1134 // Rebuild any internal references to earlier parameters and reindex
1135 // as we go.
1136 MultiLevelTemplateArgumentList Args;
1137 Args.setKind(TemplateSubstitutionKind::Rewrite);
1138 Args.addOuterTemplateArguments(Args: TransformedTemplateArgs);
1139 NamedDecl *NewParam = transformTemplateParameter(
1140 SemaRef, DC: AliasTemplate->getDeclContext(), TemplateParam: TP, Args,
1141 /*NewIndex=*/TransformedTemplateArgs.size(),
1142 NewDepth: getDepthAndIndex(ND: TP).first + AdjustDepth);
1143
1144 TemplateArgument NewTemplateArgument =
1145 Context.getInjectedTemplateArg(ParamDecl: NewParam);
1146 TransformedTemplateArgs.push_back(Elt: NewTemplateArgument);
1147 }
1148 // Transformed the ReturnType to restore the uninstantiated depth.
1149 MultiLevelTemplateArgumentList Args;
1150 Args.setKind(TemplateSubstitutionKind::Rewrite);
1151 Args.addOuterTemplateArguments(Args: TransformedTemplateArgs);
1152 ReturnType = SemaRef.SubstType(
1153 T: ReturnType, TemplateArgs: Args, Loc: AliasTemplate->getLocation(),
1154 Entity: Context.DeclarationNames.getCXXDeductionGuideName(TD: AliasTemplate));
1155 }
1156
1157 SmallVector<TypeSourceInfo *> IsDeducibleTypeTraitArgs = {
1158 Context.getTrivialTypeSourceInfo(
1159 T: Context.getDeducedTemplateSpecializationType(
1160 DK: DeducedKind::DeducedAsDependent,
1161 /*DeducedAsType=*/QualType(), Keyword: ElaboratedTypeKeyword::None,
1162 Template: TemplateName(AliasTemplate)),
1163 Loc: AliasTemplate->getLocation()), // template specialization type whose
1164 // arguments will be deduced.
1165 Context.getTrivialTypeSourceInfo(
1166 T: ReturnType, Loc: AliasTemplate->getLocation()), // type from which template
1167 // arguments are deduced.
1168 };
1169 return TypeTraitExpr::Create(
1170 C: Context, T: Context.getLogicalOperationType(), Loc: AliasTemplate->getLocation(),
1171 Kind: TypeTrait::BTT_IsDeducible, Args: IsDeducibleTypeTraitArgs,
1172 RParenLoc: AliasTemplate->getLocation(), /*Value*/ false);
1173}
1174
1175std::pair<TemplateDecl *, llvm::ArrayRef<TemplateArgument>>
1176getRHSTemplateDeclAndArgs(Sema &SemaRef, TypeAliasTemplateDecl *AliasTemplate) {
1177 auto RhsType = AliasTemplate->getTemplatedDecl()->getUnderlyingType();
1178 TemplateDecl *Template = nullptr;
1179 llvm::ArrayRef<TemplateArgument> AliasRhsTemplateArgs;
1180 if (const auto *TST = RhsType->getAs<TemplateSpecializationType>()) {
1181 // Cases where the RHS of the alias is dependent. e.g.
1182 // template<typename T>
1183 // using AliasFoo1 = Foo<T>; // a class/type alias template specialization
1184 Template = TST->getTemplateName().getAsTemplateDecl();
1185 AliasRhsTemplateArgs =
1186 TST->getAsNonAliasTemplateSpecializationType()->template_arguments();
1187 } else if (const auto *RT = RhsType->getAs<RecordType>()) {
1188 // Cases where template arguments in the RHS of the alias are not
1189 // dependent. e.g.
1190 // using AliasFoo = Foo<bool>;
1191 if (const auto *CTSD =
1192 dyn_cast<ClassTemplateSpecializationDecl>(Val: RT->getDecl())) {
1193 Template = CTSD->getSpecializedTemplate();
1194 AliasRhsTemplateArgs = CTSD->getTemplateArgs().asArray();
1195 }
1196 }
1197 return {Template, AliasRhsTemplateArgs};
1198}
1199
1200bool IsNonDeducedArgument(const TemplateArgument &TA) {
1201 // The following cases indicate the template argument is non-deducible:
1202 // 1. The result is null. E.g. When it comes from a default template
1203 // argument that doesn't appear in the alias declaration.
1204 // 2. The template parameter is a pack and that cannot be deduced from
1205 // the arguments within the alias declaration.
1206 // Non-deducible template parameters will persist in the transformed
1207 // deduction guide.
1208 return TA.isNull() ||
1209 (TA.getKind() == TemplateArgument::Pack &&
1210 llvm::any_of(Range: TA.pack_elements(), P: IsNonDeducedArgument));
1211}
1212
1213// Build deduction guides for a type alias template from the given underlying
1214// source deduction guide.
1215CXXDeductionGuideDecl *BuildDeductionGuideForTypeAlias(
1216 Sema &SemaRef, TypeAliasTemplateDecl *AliasTemplate,
1217 CXXDeductionGuideDecl *SourceDeductionGuide, SourceLocation Loc) {
1218 FunctionTemplateDecl *F =
1219 SourceDeductionGuide->getDescribedFunctionTemplate();
1220 assert(F && "deduction guide for alias template must be a function template");
1221
1222 LocalInstantiationScope Scope(SemaRef);
1223 Sema::NonSFINAEContext _1(SemaRef);
1224 Sema::InstantiatingTemplate BuildingDeductionGuides(
1225 SemaRef, AliasTemplate->getLocation(), F,
1226 Sema::InstantiatingTemplate::BuildingDeductionGuidesTag{});
1227 if (BuildingDeductionGuides.isInvalid())
1228 return nullptr;
1229
1230 auto &Context = SemaRef.Context;
1231 auto [Template, AliasRhsTemplateArgs] =
1232 getRHSTemplateDeclAndArgs(SemaRef, AliasTemplate);
1233
1234 // We need both types desugared, before we continue to perform type deduction.
1235 // The intent is to get the template argument list 'matched', e.g. in the
1236 // following case:
1237 //
1238 //
1239 // template <class T>
1240 // struct A {};
1241 // template <class T>
1242 // using Foo = A<A<T>>;
1243 // template <class U = int>
1244 // using Bar = Foo<U>;
1245 //
1246 // In terms of Bar, we want U (which has the default argument) to appear in
1247 // the synthesized deduction guide, but U would remain undeduced if we deduced
1248 // A<A<T>> using Foo<U> directly.
1249 //
1250 // Instead, we need to canonicalize both against A, i.e. A<A<T>> and A<A<U>>,
1251 // such that T can be deduced as U.
1252 auto RType = SourceDeductionGuide->getReturnType();
1253 // The (trailing) return type of the deduction guide.
1254 const auto *FReturnType = RType->getAs<TemplateSpecializationType>();
1255 if (const auto *ICNT = RType->getAsCanonical<InjectedClassNameType>())
1256 // implicitly-generated deduction guide.
1257 FReturnType = cast<TemplateSpecializationType>(
1258 Val: ICNT->getDecl()->getCanonicalTemplateSpecializationType(
1259 Ctx: SemaRef.Context));
1260
1261 ArrayRef<TemplateArgument> FReturnTemplateArgs;
1262 if (FReturnType) {
1263 FReturnTemplateArgs = FReturnType->template_arguments();
1264 } else if (const auto *RT = RType->getAs<RecordType>()) {
1265 // If the return type is a non-dependent class template specialization,
1266 // it might be resolved to a RecordType.
1267 if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(Val: RT->getDecl()))
1268 FReturnTemplateArgs = CTSD->getTemplateArgs().asArray();
1269 }
1270 assert(!FReturnTemplateArgs.empty() && "expected to see template arguments");
1271
1272 // Deduce template arguments of the deduction guide f from the RHS of
1273 // the alias.
1274 //
1275 // C++ [over.match.class.deduct]p3: ...For each function or function
1276 // template f in the guides of the template named by the
1277 // simple-template-id of the defining-type-id, the template arguments
1278 // of the return type of f are deduced from the defining-type-id of A
1279 // according to the process in [temp.deduct.type] with the exception
1280 // that deduction does not fail if not all template arguments are
1281 // deduced.
1282 //
1283 //
1284 // template<typename X, typename Y>
1285 // f(X, Y) -> f<Y, X>;
1286 //
1287 // template<typename U>
1288 // using alias = f<int, U>;
1289 //
1290 // The RHS of alias is f<int, U>, we deduced the template arguments of
1291 // the return type of the deduction guide from it: Y->int, X->U
1292 sema::TemplateDeductionInfo TDeduceInfo(Loc);
1293 // Must initialize n elements, this is required by DeduceTemplateArguments.
1294 SmallVector<DeducedTemplateArgument> DeduceResults(
1295 F->getTemplateParameters()->size());
1296
1297 // FIXME: DeduceTemplateArguments stops immediately at the first
1298 // non-deducible template argument. However, this doesn't seem to cause
1299 // issues for practice cases, we probably need to extend it to continue
1300 // performing deduction for rest of arguments to align with the C++
1301 // standard.
1302 SemaRef.DeduceTemplateArguments(
1303 TemplateParams: F->getTemplateParameters(), Ps: FReturnTemplateArgs,
1304 As: AliasRhsTemplateArgs, Info&: TDeduceInfo, Deduced&: DeduceResults,
1305 /*NumberOfArgumentsMustMatch=*/false);
1306
1307 SmallVector<TemplateArgument> DeducedArgs;
1308 SmallVector<unsigned> NonDeducedTemplateParamsInFIndex;
1309 // !!NOTE: DeduceResults respects the sequence of template parameters of
1310 // the deduction guide f.
1311 for (unsigned Index = 0; Index < DeduceResults.size(); ++Index) {
1312 const auto &D = DeduceResults[Index];
1313 if (!IsNonDeducedArgument(TA: D))
1314 DeducedArgs.push_back(Elt: D);
1315 else
1316 NonDeducedTemplateParamsInFIndex.push_back(Elt: Index);
1317 }
1318 auto DeducedAliasTemplateParams =
1319 TemplateParamsReferencedInTemplateArgumentList(
1320 SemaRef, TemplateParamsList: AliasTemplate->getTemplateParameters(), DeducedArgs);
1321 // All template arguments null by default.
1322 SmallVector<TemplateArgument> TemplateArgsForBuildingFPrime(
1323 F->getTemplateParameters()->size());
1324
1325 // Create a template parameter list for the synthesized deduction guide f'.
1326 //
1327 // C++ [over.match.class.deduct]p3.2:
1328 // If f is a function template, f' is a function template whose template
1329 // parameter list consists of all the template parameters of A
1330 // (including their default template arguments) that appear in the above
1331 // deductions or (recursively) in their default template arguments
1332 SmallVector<NamedDecl *> FPrimeTemplateParams;
1333 // Store template arguments that refer to the newly-created template
1334 // parameters, used for building `TemplateArgsForBuildingFPrime`.
1335 SmallVector<TemplateArgument, 16> TransformedDeducedAliasArgs(
1336 AliasTemplate->getTemplateParameters()->size());
1337 // We might be already within a pack expansion, but rewriting template
1338 // parameters is independent of that. (We may or may not expand new packs
1339 // when rewriting. So clear the state)
1340 Sema::ArgPackSubstIndexRAII PackSubstReset(SemaRef, std::nullopt);
1341
1342 for (unsigned AliasTemplateParamIdx : DeducedAliasTemplateParams) {
1343 auto *TP =
1344 AliasTemplate->getTemplateParameters()->getParam(Idx: AliasTemplateParamIdx);
1345 // Rebuild any internal references to earlier parameters and reindex as
1346 // we go.
1347 MultiLevelTemplateArgumentList Args;
1348 Args.setKind(TemplateSubstitutionKind::Rewrite);
1349 Args.addOuterTemplateArguments(Args: TransformedDeducedAliasArgs);
1350 NamedDecl *NewParam = transformTemplateParameter(
1351 SemaRef, DC: AliasTemplate->getDeclContext(), TemplateParam: TP, Args,
1352 /*NewIndex=*/FPrimeTemplateParams.size(), NewDepth: getDepthAndIndex(ND: TP).first);
1353 FPrimeTemplateParams.push_back(Elt: NewParam);
1354
1355 TemplateArgument NewTemplateArgument =
1356 Context.getInjectedTemplateArg(ParamDecl: NewParam);
1357 TransformedDeducedAliasArgs[AliasTemplateParamIdx] = NewTemplateArgument;
1358 }
1359 unsigned FirstUndeducedParamIdx = FPrimeTemplateParams.size();
1360
1361 // To form a deduction guide f' from f, we leverage clang's instantiation
1362 // mechanism, we construct a template argument list where the template
1363 // arguments refer to the newly-created template parameters of f', and
1364 // then apply instantiation on this template argument list to instantiate
1365 // f, this ensures all template parameter occurrences are updated
1366 // correctly.
1367 //
1368 // The template argument list is formed, in order, from
1369 // 1) For the template parameters of the alias, the corresponding deduced
1370 // template arguments
1371 // 2) For the non-deduced template parameters of f. the
1372 // (rebuilt) template arguments corresponding.
1373 //
1374 // Note: the non-deduced template arguments of `f` might refer to arguments
1375 // deduced in 1), as in a type constraint.
1376 MultiLevelTemplateArgumentList Args;
1377 Args.setKind(TemplateSubstitutionKind::Rewrite);
1378 Args.addOuterTemplateArguments(Args: TransformedDeducedAliasArgs);
1379 for (unsigned Index = 0; Index < DeduceResults.size(); ++Index) {
1380 const auto &D = DeduceResults[Index];
1381 auto *TP = F->getTemplateParameters()->getParam(Idx: Index);
1382 if (IsNonDeducedArgument(TA: D)) {
1383 // 2): Non-deduced template parameters would be substituted later.
1384 continue;
1385 }
1386 TemplateArgumentLoc Input =
1387 SemaRef.getTrivialTemplateArgumentLoc(Arg: D, NTTPType: QualType(), Loc: SourceLocation{});
1388 TemplateArgumentListInfo Output;
1389 if (SemaRef.SubstTemplateArguments(Args: Input, TemplateArgs: Args, Outputs&: Output))
1390 return nullptr;
1391 assert(TemplateArgsForBuildingFPrime[Index].isNull() &&
1392 "InstantiatedArgs must be null before setting");
1393 // CheckTemplateArgument is necessary for NTTP initializations.
1394 // FIXME: We may want to call CheckTemplateArguments instead, but we cannot
1395 // match packs as usual, since packs can appear in the middle of the
1396 // parameter list of a synthesized CTAD guide. See also the FIXME in
1397 // test/SemaCXX/cxx20-ctad-type-alias.cpp:test25.
1398 Sema::CheckTemplateArgumentInfo CTAI;
1399 for (auto TA : Output.arguments())
1400 if (SemaRef.CheckTemplateArgument(
1401 Param: TP, Arg&: TA, Template: F, TemplateLoc: F->getLocation(), RAngleLoc: F->getLocation(),
1402 /*ArgumentPackIndex=*/-1, CTAI,
1403 CTAK: Sema::CheckTemplateArgumentKind::CTAK_Specified))
1404 return nullptr;
1405 if (Input.getArgument().getKind() == TemplateArgument::Pack) {
1406 // We will substitute the non-deduced template arguments with these
1407 // transformed (unpacked at this point) arguments, where that substitution
1408 // requires a pack for the corresponding parameter packs.
1409 TemplateArgsForBuildingFPrime[Index] =
1410 TemplateArgument::CreatePackCopy(Context, Args: CTAI.SugaredConverted);
1411 } else {
1412 assert(Output.arguments().size() == 1);
1413 TemplateArgsForBuildingFPrime[Index] = CTAI.SugaredConverted[0];
1414 }
1415 }
1416
1417 // Case 2)
1418 // ...followed by the template parameters of f that were not deduced
1419 // (including their default template arguments)
1420 for (unsigned FTemplateParamIdx : NonDeducedTemplateParamsInFIndex) {
1421 auto *TP = F->getTemplateParameters()->getParam(Idx: FTemplateParamIdx);
1422 MultiLevelTemplateArgumentList Args;
1423 Args.setKind(TemplateSubstitutionKind::Rewrite);
1424 // We take a shortcut here, it is ok to reuse the
1425 // TemplateArgsForBuildingFPrime.
1426 Args.addOuterTemplateArguments(Args: TemplateArgsForBuildingFPrime);
1427 NamedDecl *NewParam = transformTemplateParameter(
1428 SemaRef, DC: F->getDeclContext(), TemplateParam: TP, Args, NewIndex: FPrimeTemplateParams.size(),
1429 NewDepth: getDepthAndIndex(ND: TP).first);
1430 FPrimeTemplateParams.push_back(Elt: NewParam);
1431
1432 assert(TemplateArgsForBuildingFPrime[FTemplateParamIdx].isNull() &&
1433 "The argument must be null before setting");
1434 TemplateArgsForBuildingFPrime[FTemplateParamIdx] =
1435 Context.getInjectedTemplateArg(ParamDecl: NewParam);
1436 }
1437
1438 auto *TemplateArgListForBuildingFPrime =
1439 TemplateArgumentList::CreateCopy(Context, Args: TemplateArgsForBuildingFPrime);
1440 // Form the f' by substituting the template arguments into f.
1441 if (auto *FPrime = SemaRef.InstantiateFunctionDeclaration(
1442 FTD: F, Args: TemplateArgListForBuildingFPrime, Loc: AliasTemplate->getLocation(),
1443 CSC: Sema::CodeSynthesisContext::BuildingDeductionGuides)) {
1444 auto *GG = cast<CXXDeductionGuideDecl>(Val: FPrime);
1445
1446 Expr *IsDeducible = buildIsDeducibleConstraint(
1447 SemaRef, AliasTemplate, ReturnType: FPrime->getReturnType(), TemplateParams: FPrimeTemplateParams);
1448 Expr *RequiresClause =
1449 buildAssociatedConstraints(SemaRef, F, AliasTemplate, DeduceResults,
1450 FirstUndeducedParamIdx, IsDeducible);
1451
1452 TemplateParameterList *FPrimeTemplateParamList = nullptr;
1453 if (!FPrimeTemplateParams.empty())
1454 FPrimeTemplateParamList = TemplateParameterList::Create(
1455 C: Context, TemplateLoc: AliasTemplate->getTemplateParameters()->getTemplateLoc(),
1456 LAngleLoc: AliasTemplate->getTemplateParameters()->getLAngleLoc(),
1457 Params: FPrimeTemplateParams,
1458 RAngleLoc: AliasTemplate->getTemplateParameters()->getRAngleLoc(),
1459 /*RequiresClause=*/RequiresClause);
1460
1461 auto *DGuide = buildDeductionGuide(
1462 SemaRef, OriginalTemplate: AliasTemplate, TemplateParams: FPrimeTemplateParamList,
1463 Ctor: GG->getCorrespondingConstructor(), ES: GG->getExplicitSpecifier(),
1464 TInfo: GG->getTypeSourceInfo(), LocStart: AliasTemplate->getBeginLoc(),
1465 Loc: AliasTemplate->getLocation(), LocEnd: AliasTemplate->getEndLoc(),
1466 IsImplicit: F->isImplicit());
1467 DGuide->setDeductionCandidateKind(GG->getDeductionCandidateKind());
1468 DGuide->setSourceDeductionGuide(SourceDeductionGuide);
1469 DGuide->setSourceDeductionGuideKind(
1470 CXXDeductionGuideDecl::SourceDeductionGuideKind::Alias);
1471 return DGuide;
1472 }
1473 return nullptr;
1474}
1475
1476void DeclareImplicitDeductionGuidesForTypeAlias(
1477 Sema &SemaRef, TypeAliasTemplateDecl *AliasTemplate, SourceLocation Loc) {
1478 if (AliasTemplate->isInvalidDecl())
1479 return;
1480 auto &Context = SemaRef.Context;
1481 auto [Template, AliasRhsTemplateArgs] =
1482 getRHSTemplateDeclAndArgs(SemaRef, AliasTemplate);
1483 if (!Template)
1484 return;
1485 auto SourceDeductionGuides = getSourceDeductionGuides(
1486 Name: Context.DeclarationNames.getCXXDeductionGuideName(TD: AliasTemplate),
1487 DC: AliasTemplate->getDeclContext());
1488
1489 DeclarationNameInfo NameInfo(
1490 Context.DeclarationNames.getCXXDeductionGuideName(TD: Template), Loc);
1491 LookupResult Guides(SemaRef, NameInfo, clang::Sema::LookupOrdinaryName);
1492 SemaRef.LookupQualifiedName(R&: Guides, LookupCtx: Template->getDeclContext());
1493 Guides.suppressDiagnostics();
1494
1495 for (auto *G : Guides) {
1496 if (auto *DG = dyn_cast<CXXDeductionGuideDecl>(Val: G)) {
1497 if (SourceDeductionGuides.contains(V: DG))
1498 continue;
1499 // The deduction guide is a non-template function decl, we just clone it.
1500 auto *FunctionType =
1501 SemaRef.Context.getTrivialTypeSourceInfo(T: DG->getType());
1502 FunctionProtoTypeLoc FPTL =
1503 FunctionType->getTypeLoc().castAs<FunctionProtoTypeLoc>();
1504
1505 // Clone the parameters.
1506 for (unsigned I = 0, N = DG->getNumParams(); I != N; ++I) {
1507 const auto *P = DG->getParamDecl(i: I);
1508 auto *TSI = SemaRef.Context.getTrivialTypeSourceInfo(T: P->getType());
1509 ParmVarDecl *NewParam = ParmVarDecl::Create(
1510 C&: SemaRef.Context, DC: G->getDeclContext(),
1511 StartLoc: DG->getParamDecl(i: I)->getBeginLoc(), IdLoc: P->getLocation(), Id: nullptr,
1512 T: TSI->getType(), TInfo: TSI, S: SC_None, DefArg: nullptr);
1513 NewParam->setScopeInfo(scopeDepth: 0, parameterIndex: I);
1514 FPTL.setParam(i: I, VD: NewParam);
1515 }
1516 auto *Transformed = cast<CXXDeductionGuideDecl>(Val: buildDeductionGuide(
1517 SemaRef, OriginalTemplate: AliasTemplate, /*TemplateParams=*/nullptr,
1518 /*Constructor=*/Ctor: nullptr, ES: DG->getExplicitSpecifier(), TInfo: FunctionType,
1519 LocStart: AliasTemplate->getBeginLoc(), Loc: AliasTemplate->getLocation(),
1520 LocEnd: AliasTemplate->getEndLoc(), IsImplicit: DG->isImplicit()));
1521 Transformed->setSourceDeductionGuide(DG);
1522 Transformed->setSourceDeductionGuideKind(
1523 CXXDeductionGuideDecl::SourceDeductionGuideKind::Alias);
1524
1525 // FIXME: Here the synthesized deduction guide is not a templated
1526 // function. Per [dcl.decl]p4, the requires-clause shall be present only
1527 // if the declarator declares a templated function, a bug in standard?
1528 AssociatedConstraint Constraint(buildIsDeducibleConstraint(
1529 SemaRef, AliasTemplate, ReturnType: Transformed->getReturnType(), TemplateParams: {}));
1530 if (const AssociatedConstraint &RC = DG->getTrailingRequiresClause()) {
1531 auto Conjunction = SemaRef.BuildBinOp(
1532 S: SemaRef.getCurScope(), OpLoc: SourceLocation{},
1533 Opc: BinaryOperatorKind::BO_LAnd, LHSExpr: const_cast<Expr *>(RC.ConstraintExpr),
1534 RHSExpr: const_cast<Expr *>(Constraint.ConstraintExpr));
1535 if (!Conjunction.isInvalid()) {
1536 Constraint.ConstraintExpr = Conjunction.getAs<Expr>();
1537 Constraint.ArgPackSubstIndex = RC.ArgPackSubstIndex;
1538 }
1539 }
1540 Transformed->setTrailingRequiresClause(Constraint);
1541 continue;
1542 }
1543 FunctionTemplateDecl *F = dyn_cast<FunctionTemplateDecl>(Val: G);
1544 if (!F || SourceDeductionGuides.contains(V: F->getTemplatedDecl()))
1545 continue;
1546 // The **aggregate** deduction guides are handled in a different code path
1547 // (DeclareAggregateDeductionGuideFromInitList), which involves the tricky
1548 // cache.
1549 auto *DGuide = cast<CXXDeductionGuideDecl>(Val: F->getTemplatedDecl());
1550 if (DGuide->getDeductionCandidateKind() == DeductionCandidate::Aggregate)
1551 continue;
1552
1553 BuildDeductionGuideForTypeAlias(SemaRef, AliasTemplate, SourceDeductionGuide: DGuide, Loc);
1554 }
1555}
1556
1557// Build an aggregate deduction guide for a type alias template.
1558CXXDeductionGuideDecl *DeclareAggregateDeductionGuideForTypeAlias(
1559 Sema &SemaRef, TypeAliasTemplateDecl *AliasTemplate,
1560 MutableArrayRef<QualType> ParamTypes, SourceLocation Loc) {
1561 TemplateDecl *RHSTemplate =
1562 getRHSTemplateDeclAndArgs(SemaRef, AliasTemplate).first;
1563 if (!RHSTemplate)
1564 return nullptr;
1565
1566 llvm::SmallVector<TypedefNameDecl *> TypedefDecls;
1567 llvm::SmallVector<QualType> NewParamTypes;
1568 ExtractTypeForDeductionGuide TypeAliasTransformer(SemaRef, TypedefDecls);
1569 for (QualType P : ParamTypes) {
1570 QualType Type = TypeAliasTransformer.TransformType(T: P);
1571 if (Type.isNull())
1572 return nullptr;
1573 NewParamTypes.push_back(Elt: Type);
1574 }
1575
1576 auto *RHSDeductionGuide = SemaRef.DeclareAggregateDeductionGuideFromInitList(
1577 Template: RHSTemplate, ParamTypes: NewParamTypes, Loc);
1578 if (!RHSDeductionGuide)
1579 return nullptr;
1580
1581 for (TypedefNameDecl *TD : TypedefDecls)
1582 TD->setDeclContext(RHSDeductionGuide);
1583
1584 return BuildDeductionGuideForTypeAlias(SemaRef, AliasTemplate,
1585 SourceDeductionGuide: RHSDeductionGuide, Loc);
1586}
1587
1588} // namespace
1589
1590CXXDeductionGuideDecl *Sema::DeclareAggregateDeductionGuideFromInitList(
1591 TemplateDecl *Template, MutableArrayRef<QualType> ParamTypes,
1592 SourceLocation Loc) {
1593 llvm::FoldingSetNodeID ID;
1594 ID.AddPointer(Ptr: Template);
1595 for (auto &T : ParamTypes)
1596 T.getCanonicalType().Profile(ID);
1597 unsigned Hash = ID.ComputeHash();
1598
1599 auto Found = AggregateDeductionCandidates.find(Val: Hash);
1600 if (Found != AggregateDeductionCandidates.end())
1601 return Found->getSecond();
1602
1603 if (auto *AliasTemplate = llvm::dyn_cast<TypeAliasTemplateDecl>(Val: Template)) {
1604 if (auto *GD = DeclareAggregateDeductionGuideForTypeAlias(
1605 SemaRef&: *this, AliasTemplate, ParamTypes, Loc)) {
1606 GD->setDeductionCandidateKind(DeductionCandidate::Aggregate);
1607 AggregateDeductionCandidates[Hash] = GD;
1608 return GD;
1609 }
1610 return nullptr;
1611 }
1612
1613 if (CXXRecordDecl *DefRecord =
1614 cast<CXXRecordDecl>(Val: Template->getTemplatedDecl())->getDefinition()) {
1615 if (TemplateDecl *DescribedTemplate =
1616 DefRecord->getDescribedClassTemplate())
1617 Template = DescribedTemplate;
1618 }
1619
1620 DeclContext *DC = Template->getDeclContext();
1621 if (DC->isDependentContext())
1622 return nullptr;
1623
1624 ConvertConstructorToDeductionGuideTransform Transform(
1625 *this, cast<ClassTemplateDecl>(Val: Template));
1626 if (!isCompleteType(Loc, T: Transform.DeducedType))
1627 return nullptr;
1628
1629 // In case we were expanding a pack when we attempted to declare deduction
1630 // guides, turn off pack expansion for everything we're about to do.
1631 ArgPackSubstIndexRAII SubstIndex(*this, std::nullopt);
1632 // Create a template instantiation record to track the "instantiation" of
1633 // constructors into deduction guides.
1634 InstantiatingTemplate BuildingDeductionGuides(
1635 *this, Loc, Template,
1636 Sema::InstantiatingTemplate::BuildingDeductionGuidesTag{});
1637 if (BuildingDeductionGuides.isInvalid())
1638 return nullptr;
1639
1640 ClassTemplateDecl *Pattern =
1641 Transform.NestedPattern ? Transform.NestedPattern : Transform.Template;
1642 ContextRAII SavedContext(*this, Pattern->getTemplatedDecl());
1643
1644 CXXDeductionGuideDecl *GD = Transform.buildSimpleDeductionGuide(ParamTypes);
1645 SavedContext.pop();
1646 GD->setDeductionCandidateKind(DeductionCandidate::Aggregate);
1647 AggregateDeductionCandidates[Hash] = GD;
1648 return GD;
1649}
1650
1651void Sema::DeclareImplicitDeductionGuides(TemplateDecl *Template,
1652 SourceLocation Loc) {
1653 if (auto *AliasTemplate = llvm::dyn_cast<TypeAliasTemplateDecl>(Val: Template)) {
1654 DeclareImplicitDeductionGuidesForTypeAlias(SemaRef&: *this, AliasTemplate, Loc);
1655 return;
1656 }
1657 CXXRecordDecl *DefRecord =
1658 dyn_cast_or_null<CXXRecordDecl>(Val: Template->getTemplatedDecl());
1659 if (!DefRecord)
1660 return;
1661 if (const CXXRecordDecl *Definition = DefRecord->getDefinition()) {
1662 if (TemplateDecl *DescribedTemplate =
1663 Definition->getDescribedClassTemplate())
1664 Template = DescribedTemplate;
1665 }
1666
1667 DeclContext *DC = Template->getDeclContext();
1668 if (DC->isDependentContext())
1669 return;
1670
1671 ConvertConstructorToDeductionGuideTransform Transform(
1672 *this, cast<ClassTemplateDecl>(Val: Template));
1673 if (!isCompleteType(Loc, T: Transform.DeducedType))
1674 return;
1675
1676 if (hasDeclaredDeductionGuides(Name: Transform.DeductionGuideName, DC))
1677 return;
1678
1679 // In case we were expanding a pack when we attempted to declare deduction
1680 // guides, turn off pack expansion for everything we're about to do.
1681 ArgPackSubstIndexRAII SubstIndex(*this, std::nullopt);
1682 // Create a template instantiation record to track the "instantiation" of
1683 // constructors into deduction guides.
1684 InstantiatingTemplate BuildingDeductionGuides(
1685 *this, Loc, Template,
1686 Sema::InstantiatingTemplate::BuildingDeductionGuidesTag{});
1687 if (BuildingDeductionGuides.isInvalid())
1688 return;
1689
1690 // Convert declared constructors into deduction guide templates.
1691 // FIXME: Skip constructors for which deduction must necessarily fail (those
1692 // for which some class template parameter without a default argument never
1693 // appears in a deduced context).
1694 ClassTemplateDecl *Pattern =
1695 Transform.NestedPattern ? Transform.NestedPattern : Transform.Template;
1696 ContextRAII SavedContext(*this, Pattern->getTemplatedDecl());
1697 llvm::SmallPtrSet<NamedDecl *, 8> ProcessedCtors;
1698 bool AddedAny = false;
1699 for (NamedDecl *D : LookupConstructors(Class: Pattern->getTemplatedDecl())) {
1700 D = D->getUnderlyingDecl();
1701 if (D->isInvalidDecl() || D->isImplicit())
1702 continue;
1703
1704 D = cast<NamedDecl>(Val: D->getCanonicalDecl());
1705
1706 // Within C++20 modules, we may have multiple same constructors in
1707 // multiple same RecordDecls. And it doesn't make sense to create
1708 // duplicated deduction guides for the duplicated constructors.
1709 if (ProcessedCtors.count(Ptr: D))
1710 continue;
1711
1712 auto *FTD = dyn_cast<FunctionTemplateDecl>(Val: D);
1713 auto *CD =
1714 dyn_cast_or_null<CXXConstructorDecl>(Val: FTD ? FTD->getTemplatedDecl() : D);
1715 // Class-scope explicit specializations (MS extension) do not result in
1716 // deduction guides.
1717 if (!CD || (!FTD && CD->isFunctionTemplateSpecialization()))
1718 continue;
1719
1720 // Cannot make a deduction guide when unparsed arguments are present.
1721 if (llvm::any_of(Range: CD->parameters(), P: [](ParmVarDecl *P) {
1722 return !P || P->hasUnparsedDefaultArg();
1723 }))
1724 continue;
1725
1726 ProcessedCtors.insert(Ptr: D);
1727 Transform.transformConstructor(FTD, CD);
1728 AddedAny = true;
1729 }
1730
1731 // C++17 [over.match.class.deduct]
1732 // -- If C is not defined or does not declare any constructors, an
1733 // additional function template derived as above from a hypothetical
1734 // constructor C().
1735 if (!AddedAny)
1736 Transform.buildSimpleDeductionGuide(ParamTypes: {});
1737
1738 // -- An additional function template derived as above from a hypothetical
1739 // constructor C(C), called the copy deduction candidate.
1740 Transform.buildSimpleDeductionGuide(ParamTypes: Transform.DeducedType)
1741 ->setDeductionCandidateKind(DeductionCandidate::Copy);
1742
1743 SavedContext.pop();
1744}
1745