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