1	//===-- SemaConcept.cpp - Semantic Analysis for Constraints and Concepts --===//
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 semantic analysis for C++ constraints and concepts.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "clang/Sema/SemaConcept.h"
14	#include "TreeTransform.h"
15	#include "clang/AST/ASTLambda.h"
16	#include "clang/AST/DeclCXX.h"
17	#include "clang/AST/ExprConcepts.h"
18	#include "clang/AST/RecursiveASTVisitor.h"
19	#include "clang/Basic/OperatorPrecedence.h"
20	#include "clang/Sema/EnterExpressionEvaluationContext.h"
21	#include "clang/Sema/Initialization.h"
22	#include "clang/Sema/Overload.h"
23	#include "clang/Sema/ScopeInfo.h"
24	#include "clang/Sema/Sema.h"
25	#include "clang/Sema/SemaDiagnostic.h"
26	#include "clang/Sema/SemaInternal.h"
27	#include "clang/Sema/Template.h"
28	#include "clang/Sema/TemplateDeduction.h"
29	#include "llvm/ADT/DenseMap.h"
30	#include "llvm/ADT/PointerUnion.h"
31	#include "llvm/ADT/StringExtras.h"
32	#include <optional>
33
34	using namespace clang;
35	using namespace sema;
36
37	namespace {
38	class LogicalBinOp {
39	SourceLocation Loc;
40	OverloadedOperatorKind Op = OO_None;
41	const Expr *LHS = nullptr;
42	const Expr *RHS = nullptr;
43
44	public:
45	LogicalBinOp(const Expr *E) {
46	if (auto *BO = dyn_cast<BinaryOperator>(Val: E)) {
47	Op = BinaryOperator::getOverloadedOperator(Opc: BO->getOpcode());
48	LHS = BO->getLHS();
49	RHS = BO->getRHS();
50	Loc = BO->getExprLoc();
51	} else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(Val: E)) {
52	// If OO is not || or && it might not have exactly 2 arguments.
53	if (OO->getNumArgs() == 2) {
54	Op = OO->getOperator();
55	LHS = OO->getArg(0);
56	RHS = OO->getArg(1);
57	Loc = OO->getOperatorLoc();
58	}
59	}
60	}
61
62	bool isAnd() const { return Op == OO_AmpAmp; }
63	bool isOr() const { return Op == OO_PipePipe; }
64	explicit operator bool() const { return isAnd() || isOr(); }
65
66	const Expr *getLHS() const { return LHS; }
67	const Expr *getRHS() const { return RHS; }
68
69	ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS) const {
70	return recreateBinOp(SemaRef, LHS, RHS: const_cast<Expr *>(getRHS()));
71	}
72
73	ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS,
74	ExprResult RHS) const {
75	assert((isAnd() || isOr()) && "Not the right kind of op?");
76	assert((!LHS.isInvalid() && !RHS.isInvalid()) && "not good expressions?");
77
78	if (!LHS.isUsable() || !RHS.isUsable())
79	return ExprEmpty();
80
81	// We should just be able to 'normalize' these to the builtin Binary
82	// Operator, since that is how they are evaluated in constriant checks.
83	return BinaryOperator::Create(C: SemaRef.Context, lhs: LHS.get(), rhs: RHS.get(),
84	opc: BinaryOperator::getOverloadedOpcode(OO: Op),
85	ResTy: SemaRef.Context.BoolTy, VK: VK_PRValue,
86	OK: OK_Ordinary, opLoc: Loc, FPFeatures: FPOptionsOverride{});
87	}
88	};
89	}
90
91	bool Sema::CheckConstraintExpression(const Expr *ConstraintExpression,
92	Token NextToken, bool *PossibleNonPrimary,
93	bool IsTrailingRequiresClause) {
94	// C++2a [temp.constr.atomic]p1
95	// ..E shall be a constant expression of type bool.
96
97	ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts();
98
99	if (LogicalBinOp BO = ConstraintExpression) {
100	return CheckConstraintExpression(ConstraintExpression: BO.getLHS(), NextToken,
101	PossibleNonPrimary) &&
102	CheckConstraintExpression(ConstraintExpression: BO.getRHS(), NextToken,
103	PossibleNonPrimary);
104	} else if (auto *C = dyn_cast<ExprWithCleanups>(Val: ConstraintExpression))
105	return CheckConstraintExpression(ConstraintExpression: C->getSubExpr(), NextToken,
106	PossibleNonPrimary);
107
108	QualType Type = ConstraintExpression->getType();
109
110	auto CheckForNonPrimary = [&] {
111	if (!PossibleNonPrimary)
112	return;
113
114	*PossibleNonPrimary =
115	// We have the following case:
116	// template<typename> requires func(0) struct S { };
117	// The user probably isn't aware of the parentheses required around
118	// the function call, and we're only going to parse 'func' as the
119	// primary-expression, and complain that it is of non-bool type.
120	//
121	// However, if we're in a lambda, this might also be:
122	// []<typename> requires var () {};
123	// Which also looks like a function call due to the lambda parentheses,
124	// but unlike the first case, isn't an error, so this check is skipped.
125	(NextToken.is(K: tok::l_paren) &&
126	(IsTrailingRequiresClause ||
127	(Type->isDependentType() &&
128	isa<UnresolvedLookupExpr>(Val: ConstraintExpression) &&
129	!dyn_cast_if_present<LambdaScopeInfo>(Val: getCurFunction())) ||
130	Type->isFunctionType() ||
131	Type->isSpecificBuiltinType(K: BuiltinType::Overload))) ||
132	// We have the following case:
133	// template<typename T> requires size_<T> == 0 struct S { };
134	// The user probably isn't aware of the parentheses required around
135	// the binary operator, and we're only going to parse 'func' as the
136	// first operand, and complain that it is of non-bool type.
137	getBinOpPrecedence(Kind: NextToken.getKind(),
138	/*GreaterThanIsOperator=*/true,
139	CPlusPlus11: getLangOpts().CPlusPlus11) > prec::LogicalAnd;
140	};
141
142	// An atomic constraint!
143	if (ConstraintExpression->isTypeDependent()) {
144	CheckForNonPrimary();
145	return true;
146	}
147
148	if (!Context.hasSameUnqualifiedType(T1: Type, T2: Context.BoolTy)) {
149	Diag(ConstraintExpression->getExprLoc(),
150	diag::err_non_bool_atomic_constraint) << Type
151	<< ConstraintExpression->getSourceRange();
152	CheckForNonPrimary();
153	return false;
154	}
155
156	if (PossibleNonPrimary)
157	*PossibleNonPrimary = false;
158	return true;
159	}
160
161	namespace {
162	struct SatisfactionStackRAII {
163	Sema &SemaRef;
164	bool Inserted = false;
165	SatisfactionStackRAII(Sema &SemaRef, const NamedDecl *ND,
166	const llvm::FoldingSetNodeID &FSNID)
167	: SemaRef(SemaRef) {
168	if (ND) {
169	SemaRef.PushSatisfactionStackEntry(D: ND, ID: FSNID);
170	Inserted = true;
171	}
172	}
173	~SatisfactionStackRAII() {
174	if (Inserted)
175	SemaRef.PopSatisfactionStackEntry();
176	}
177	};
178	} // namespace
179
180	template <typename AtomicEvaluator>
181	static ExprResult
182	calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
183	ConstraintSatisfaction &Satisfaction,
184	AtomicEvaluator &&Evaluator) {
185	ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
186
187	if (LogicalBinOp BO = ConstraintExpr) {
188	size_t EffectiveDetailEndIndex = Satisfaction.Details.size();
189	ExprResult LHSRes = calculateConstraintSatisfaction(
190	S, BO.getLHS(), Satisfaction, Evaluator);
191
192	if (LHSRes.isInvalid())
193	return ExprError();
194
195	bool IsLHSSatisfied = Satisfaction.IsSatisfied;
196
197	if (BO.isOr() && IsLHSSatisfied)
198	// [temp.constr.op] p3
199	// A disjunction is a constraint taking two operands. To determine if
200	// a disjunction is satisfied, the satisfaction of the first operand
201	// is checked. If that is satisfied, the disjunction is satisfied.
202	// Otherwise, the disjunction is satisfied if and only if the second
203	// operand is satisfied.
204	// LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
205	return LHSRes;
206
207	if (BO.isAnd() && !IsLHSSatisfied)
208	// [temp.constr.op] p2
209	// A conjunction is a constraint taking two operands. To determine if
210	// a conjunction is satisfied, the satisfaction of the first operand
211	// is checked. If that is not satisfied, the conjunction is not
212	// satisfied. Otherwise, the conjunction is satisfied if and only if
213	// the second operand is satisfied.
214	// LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
215	return LHSRes;
216
217	ExprResult RHSRes = calculateConstraintSatisfaction(
218	S, BO.getRHS(), Satisfaction, std::forward<AtomicEvaluator>(Evaluator));
219	if (RHSRes.isInvalid())
220	return ExprError();
221
222	bool IsRHSSatisfied = Satisfaction.IsSatisfied;
223	// Current implementation adds diagnostic information about the falsity
224	// of each false atomic constraint expression when it evaluates them.
225	// When the evaluation results to `false || true`, the information
226	// generated during the evaluation of left-hand side is meaningless
227	// because the whole expression evaluates to true.
228	// The following code removes the irrelevant diagnostic information.
229	// FIXME: We should probably delay the addition of diagnostic information
230	// until we know the entire expression is false.
231	if (BO.isOr() && IsRHSSatisfied) {
232	auto EffectiveDetailEnd = Satisfaction.Details.begin();
233	std::advance(i&: EffectiveDetailEnd, n: EffectiveDetailEndIndex);
234	Satisfaction.Details.erase(CS: EffectiveDetailEnd,
235	CE: Satisfaction.Details.end());
236	}
237
238	return BO.recreateBinOp(SemaRef&: S, LHS: LHSRes, RHS: RHSRes);
239	}
240
241	if (auto *C = dyn_cast<ExprWithCleanups>(Val: ConstraintExpr)) {
242	// These aren't evaluated, so we don't care about cleanups, so we can just
243	// evaluate these as if the cleanups didn't exist.
244	return calculateConstraintSatisfaction(
245	S, C->getSubExpr(), Satisfaction,
246	std::forward<AtomicEvaluator>(Evaluator));
247	}
248
249	// An atomic constraint expression
250	ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr);
251
252	if (SubstitutedAtomicExpr.isInvalid())
253	return ExprError();
254
255	if (!SubstitutedAtomicExpr.isUsable())
256	// Evaluator has decided satisfaction without yielding an expression.
257	return ExprEmpty();
258
259	// We don't have the ability to evaluate this, since it contains a
260	// RecoveryExpr, so we want to fail overload resolution. Otherwise,
261	// we'd potentially pick up a different overload, and cause confusing
262	// diagnostics. SO, add a failure detail that will cause us to make this
263	// overload set not viable.
264	if (SubstitutedAtomicExpr.get()->containsErrors()) {
265	Satisfaction.IsSatisfied = false;
266	Satisfaction.ContainsErrors = true;
267
268	PartialDiagnostic Msg = S.PDiag(diag::note_constraint_references_error);
269	SmallString<128> DiagString;
270	DiagString = ": ";
271	Msg.EmitToString(Diags&: S.getDiagnostics(), Buf&: DiagString);
272	unsigned MessageSize = DiagString.size();
273	char *Mem = new (S.Context) char[MessageSize];
274	memcpy(dest: Mem, src: DiagString.c_str(), n: MessageSize);
275	Satisfaction.Details.emplace_back(
276	Args&: ConstraintExpr,
277	Args: new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
278	SubstitutedAtomicExpr.get()->getBeginLoc(),
279	StringRef(Mem, MessageSize)});
280	return SubstitutedAtomicExpr;
281	}
282
283	EnterExpressionEvaluationContext ConstantEvaluated(
284	S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
285	SmallVector<PartialDiagnosticAt, 2> EvaluationDiags;
286	Expr::EvalResult EvalResult;
287	EvalResult.Diag = &EvaluationDiags;
288	if (!SubstitutedAtomicExpr.get()->EvaluateAsConstantExpr(Result&: EvalResult,
289	Ctx: S.Context) ||
290	!EvaluationDiags.empty()) {
291	// C++2a [temp.constr.atomic]p1
292	// ...E shall be a constant expression of type bool.
293	S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(),
294	diag::err_non_constant_constraint_expression)
295	<< SubstitutedAtomicExpr.get()->getSourceRange();
296	for (const PartialDiagnosticAt &PDiag : EvaluationDiags)
297	S.Diag(PDiag.first, PDiag.second);
298	return ExprError();
299	}
300
301	assert(EvalResult.Val.isInt() &&
302	"evaluating bool expression didn't produce int");
303	Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();
304	if (!Satisfaction.IsSatisfied)
305	Satisfaction.Details.emplace_back(Args&: ConstraintExpr,
306	Args: SubstitutedAtomicExpr.get());
307
308	return SubstitutedAtomicExpr;
309	}
310
311	static bool
312	DiagRecursiveConstraintEval(Sema &S, llvm::FoldingSetNodeID &ID,
313	const NamedDecl *Templ, const Expr *E,
314	const MultiLevelTemplateArgumentList &MLTAL) {
315	E->Profile(ID, S.Context, /*Canonical=*/true);
316	for (const auto &List : MLTAL)
317	for (const auto &TemplateArg : List.Args)
318	TemplateArg.Profile(ID, Context: S.Context);
319
320	// Note that we have to do this with our own collection, because there are
321	// times where a constraint-expression check can cause us to need to evaluate
322	// other constriants that are unrelated, such as when evaluating a recovery
323	// expression, or when trying to determine the constexpr-ness of special
324	// members. Otherwise we could just use the
325	// Sema::InstantiatingTemplate::isAlreadyBeingInstantiated function.
326	if (S.SatisfactionStackContains(D: Templ, ID)) {
327	S.Diag(E->getExprLoc(), diag::err_constraint_depends_on_self)
328	<< const_cast<Expr *>(E) << E->getSourceRange();
329	return true;
330	}
331
332	return false;
333	}
334
335	static ExprResult calculateConstraintSatisfaction(
336	Sema &S, const NamedDecl *Template, SourceLocation TemplateNameLoc,
337	const MultiLevelTemplateArgumentList &MLTAL, const Expr *ConstraintExpr,
338	ConstraintSatisfaction &Satisfaction) {
339	return calculateConstraintSatisfaction(
340	S, ConstraintExpr, Satisfaction, Evaluator: [&](const Expr *AtomicExpr) {
341	EnterExpressionEvaluationContext ConstantEvaluated(
342	S, Sema::ExpressionEvaluationContext::ConstantEvaluated,
343	Sema::ReuseLambdaContextDecl);
344
345	// Atomic constraint - substitute arguments and check satisfaction.
346	ExprResult SubstitutedExpression;
347	{
348	TemplateDeductionInfo Info(TemplateNameLoc);
349	Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(),
350	Sema::InstantiatingTemplate::ConstraintSubstitution{},
351	const_cast<NamedDecl *>(Template), Info,
352	AtomicExpr->getSourceRange());
353	if (Inst.isInvalid())
354	return ExprError();
355
356	llvm::FoldingSetNodeID ID;
357	if (Template &&
358	DiagRecursiveConstraintEval(S, ID, Templ: Template, E: AtomicExpr, MLTAL)) {
359	Satisfaction.IsSatisfied = false;
360	Satisfaction.ContainsErrors = true;
361	return ExprEmpty();
362	}
363
364	SatisfactionStackRAII StackRAII(S, Template, ID);
365
366	// We do not want error diagnostics escaping here.
367	Sema::SFINAETrap Trap(S);
368	SubstitutedExpression =
369	S.SubstConstraintExpr(E: const_cast<Expr *>(AtomicExpr), TemplateArgs: MLTAL);
370
371	if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {
372	// C++2a [temp.constr.atomic]p1
373	// ...If substitution results in an invalid type or expression, the
374	// constraint is not satisfied.
375	if (!Trap.hasErrorOccurred())
376	// A non-SFINAE error has occurred as a result of this
377	// substitution.
378	return ExprError();
379
380	PartialDiagnosticAt SubstDiag{SourceLocation(),
381	PartialDiagnostic::NullDiagnostic()};
382	Info.takeSFINAEDiagnostic(PD&: SubstDiag);
383	// FIXME: Concepts: This is an unfortunate consequence of there
384	// being no serialization code for PartialDiagnostics and the fact
385	// that serializing them would likely take a lot more storage than
386	// just storing them as strings. We would still like, in the
387	// future, to serialize the proper PartialDiagnostic as serializing
388	// it as a string defeats the purpose of the diagnostic mechanism.
389	SmallString<128> DiagString;
390	DiagString = ": ";
391	SubstDiag.second.EmitToString(Diags&: S.getDiagnostics(), Buf&: DiagString);
392	unsigned MessageSize = DiagString.size();
393	char *Mem = new (S.Context) char[MessageSize];
394	memcpy(dest: Mem, src: DiagString.c_str(), n: MessageSize);
395	Satisfaction.Details.emplace_back(
396	Args&: AtomicExpr,
397	Args: new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
398	SubstDiag.first, StringRef(Mem, MessageSize)});
399	Satisfaction.IsSatisfied = false;
400	return ExprEmpty();
401	}
402	}
403
404	if (!S.CheckConstraintExpression(ConstraintExpression: SubstitutedExpression.get()))
405	return ExprError();
406
407	// [temp.constr.atomic]p3: To determine if an atomic constraint is
408	// satisfied, the parameter mapping and template arguments are first
409	// substituted into its expression. If substitution results in an
410	// invalid type or expression, the constraint is not satisfied.
411	// Otherwise, the lvalue-to-rvalue conversion is performed if necessary,
412	// and E shall be a constant expression of type bool.
413	//
414	// Perform the L to R Value conversion if necessary. We do so for all
415	// non-PRValue categories, else we fail to extend the lifetime of
416	// temporaries, and that fails the constant expression check.
417	if (!SubstitutedExpression.get()->isPRValue())
418	SubstitutedExpression = ImplicitCastExpr::Create(
419	Context: S.Context, T: SubstitutedExpression.get()->getType(),
420	Kind: CK_LValueToRValue, Operand: SubstitutedExpression.get(),
421	/*BasePath=*/nullptr, Cat: VK_PRValue, FPO: FPOptionsOverride());
422
423	return SubstitutedExpression;
424	});
425	}
426
427	static bool CheckConstraintSatisfaction(
428	Sema &S, const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
429	llvm::SmallVectorImpl<Expr *> &Converted,
430	const MultiLevelTemplateArgumentList &TemplateArgsLists,
431	SourceRange TemplateIDRange, ConstraintSatisfaction &Satisfaction) {
432	if (ConstraintExprs.empty()) {
433	Satisfaction.IsSatisfied = true;
434	return false;
435	}
436
437	if (TemplateArgsLists.isAnyArgInstantiationDependent()) {
438	// No need to check satisfaction for dependent constraint expressions.
439	Satisfaction.IsSatisfied = true;
440	return false;
441	}
442
443	ArrayRef<TemplateArgument> TemplateArgs =
444	TemplateArgsLists.getNumSubstitutedLevels() > 0
445	? TemplateArgsLists.getOutermost()
446	: ArrayRef<TemplateArgument> {};
447	Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(),
448	Sema::InstantiatingTemplate::ConstraintsCheck{},
449	const_cast<NamedDecl *>(Template), TemplateArgs, TemplateIDRange);
450	if (Inst.isInvalid())
451	return true;
452
453	for (const Expr *ConstraintExpr : ConstraintExprs) {
454	ExprResult Res = calculateConstraintSatisfaction(
455	S, Template, TemplateNameLoc: TemplateIDRange.getBegin(), MLTAL: TemplateArgsLists,
456	ConstraintExpr, Satisfaction);
457	if (Res.isInvalid())
458	return true;
459
460	Converted.push_back(Elt: Res.get());
461	if (!Satisfaction.IsSatisfied) {
462	// Backfill the 'converted' list with nulls so we can keep the Converted
463	// and unconverted lists in sync.
464	Converted.append(NumInputs: ConstraintExprs.size() - Converted.size(), Elt: nullptr);
465	// [temp.constr.op] p2
466	// [...] To determine if a conjunction is satisfied, the satisfaction
467	// of the first operand is checked. If that is not satisfied, the
468	// conjunction is not satisfied. [...]
469	return false;
470	}
471	}
472	return false;
473	}
474
475	bool Sema::CheckConstraintSatisfaction(
476	const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
477	llvm::SmallVectorImpl<Expr *> &ConvertedConstraints,
478	const MultiLevelTemplateArgumentList &TemplateArgsLists,
479	SourceRange TemplateIDRange, ConstraintSatisfaction &OutSatisfaction) {
480	if (ConstraintExprs.empty()) {
481	OutSatisfaction.IsSatisfied = true;
482	return false;
483	}
484	if (!Template) {
485	return ::CheckConstraintSatisfaction(
486	S&: *this, Template: nullptr, ConstraintExprs, Converted&: ConvertedConstraints,
487	TemplateArgsLists, TemplateIDRange, Satisfaction&: OutSatisfaction);
488	}
489
490	// A list of the template argument list flattened in a predictible manner for
491	// the purposes of caching. The ConstraintSatisfaction type is in AST so it
492	// has no access to the MultiLevelTemplateArgumentList, so this has to happen
493	// here.
494	llvm::SmallVector<TemplateArgument, 4> FlattenedArgs;
495	for (auto List : TemplateArgsLists)
496	FlattenedArgs.insert(I: FlattenedArgs.end(), From: List.Args.begin(),
497	To: List.Args.end());
498
499	llvm::FoldingSetNodeID ID;
500	ConstraintSatisfaction::Profile(ID, C: Context, ConstraintOwner: Template, TemplateArgs: FlattenedArgs);
501	void *InsertPos;
502	if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
503	OutSatisfaction = *Cached;
504	return false;
505	}
506
507	auto Satisfaction =
508	std::make_unique<ConstraintSatisfaction>(args&: Template, args&: FlattenedArgs);
509	if (::CheckConstraintSatisfaction(S&: *this, Template, ConstraintExprs,
510	Converted&: ConvertedConstraints, TemplateArgsLists,
511	TemplateIDRange, Satisfaction&: *Satisfaction)) {
512	OutSatisfaction = *Satisfaction;
513	return true;
514	}
515
516	if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
517	// The evaluation of this constraint resulted in us trying to re-evaluate it
518	// recursively. This isn't really possible, except we try to form a
519	// RecoveryExpr as a part of the evaluation. If this is the case, just
520	// return the 'cached' version (which will have the same result), and save
521	// ourselves the extra-insert. If it ever becomes possible to legitimately
522	// recursively check a constraint, we should skip checking the 'inner' one
523	// above, and replace the cached version with this one, as it would be more
524	// specific.
525	OutSatisfaction = *Cached;
526	return false;
527	}
528
529	// Else we can simply add this satisfaction to the list.
530	OutSatisfaction = *Satisfaction;
531	// We cannot use InsertPos here because CheckConstraintSatisfaction might have
532	// invalidated it.
533	// Note that entries of SatisfactionCache are deleted in Sema's destructor.
534	SatisfactionCache.InsertNode(N: Satisfaction.release());
535	return false;
536	}
537
538	bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
539	ConstraintSatisfaction &Satisfaction) {
540	return calculateConstraintSatisfaction(
541	S&: *this, ConstraintExpr, Satisfaction,
542	Evaluator: [this](const Expr *AtomicExpr) -> ExprResult {
543	// We only do this to immitate lvalue-to-rvalue conversion.
544	return PerformContextuallyConvertToBool(
545	From: const_cast<Expr *>(AtomicExpr));
546	})
547	.isInvalid();
548	}
549
550	bool Sema::addInstantiatedCapturesToScope(
551	FunctionDecl *Function, const FunctionDecl *PatternDecl,
552	LocalInstantiationScope &Scope,
553	const MultiLevelTemplateArgumentList &TemplateArgs) {
554	const auto *LambdaClass = cast<CXXMethodDecl>(Val: Function)->getParent();
555	const auto *LambdaPattern = cast<CXXMethodDecl>(Val: PatternDecl)->getParent();
556
557	unsigned Instantiated = 0;
558
559	auto AddSingleCapture = [&](const ValueDecl *CapturedPattern,
560	unsigned Index) {
561	ValueDecl *CapturedVar = LambdaClass->getCapture(I: Index)->getCapturedVar();
562	if (CapturedVar->isInitCapture())
563	Scope.InstantiatedLocal(CapturedPattern, CapturedVar);
564	};
565
566	for (const LambdaCapture &CapturePattern : LambdaPattern->captures()) {
567	if (!CapturePattern.capturesVariable()) {
568	Instantiated++;
569	continue;
570	}
571	const ValueDecl *CapturedPattern = CapturePattern.getCapturedVar();
572	if (!CapturedPattern->isParameterPack()) {
573	AddSingleCapture(CapturedPattern, Instantiated++);
574	} else {
575	Scope.MakeInstantiatedLocalArgPack(CapturedPattern);
576	std::optional<unsigned> NumArgumentsInExpansion =
577	getNumArgumentsInExpansion(T: CapturedPattern->getType(), TemplateArgs);
578	if (!NumArgumentsInExpansion)
579	continue;
580	for (unsigned Arg = 0; Arg < *NumArgumentsInExpansion; ++Arg)
581	AddSingleCapture(CapturedPattern, Instantiated++);
582	}
583	}
584	return false;
585	}
586
587	bool Sema::SetupConstraintScope(
588	FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
589	const MultiLevelTemplateArgumentList &MLTAL,
590	LocalInstantiationScope &Scope) {
591	if (FD->isTemplateInstantiation() && FD->getPrimaryTemplate()) {
592	FunctionTemplateDecl *PrimaryTemplate = FD->getPrimaryTemplate();
593	InstantiatingTemplate Inst(
594	*this, FD->getPointOfInstantiation(),
595	Sema::InstantiatingTemplate::ConstraintsCheck{}, PrimaryTemplate,
596	TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
597	SourceRange());
598	if (Inst.isInvalid())
599	return true;
600
601	// addInstantiatedParametersToScope creates a map of 'uninstantiated' to
602	// 'instantiated' parameters and adds it to the context. For the case where
603	// this function is a template being instantiated NOW, we also need to add
604	// the list of current template arguments to the list so that they also can
605	// be picked out of the map.
606	if (auto *SpecArgs = FD->getTemplateSpecializationArgs()) {
607	MultiLevelTemplateArgumentList JustTemplArgs(FD, SpecArgs->asArray(),
608	/*Final=*/false);
609	if (addInstantiatedParametersToScope(
610	Function: FD, PatternDecl: PrimaryTemplate->getTemplatedDecl(), Scope, TemplateArgs: JustTemplArgs))
611	return true;
612	}
613
614	// If this is a member function, make sure we get the parameters that
615	// reference the original primary template.
616	// We walk up the instantiated template chain so that nested lambdas get
617	// handled properly.
618	// We should only collect instantiated parameters from the primary template.
619	// Otherwise, we may have mismatched template parameter depth!
620	if (FunctionTemplateDecl *FromMemTempl =
621	PrimaryTemplate->getInstantiatedFromMemberTemplate()) {
622	while (FromMemTempl->getInstantiatedFromMemberTemplate())
623	FromMemTempl = FromMemTempl->getInstantiatedFromMemberTemplate();
624	if (addInstantiatedParametersToScope(Function: FD, PatternDecl: FromMemTempl->getTemplatedDecl(),
625	Scope, TemplateArgs: MLTAL))
626	return true;
627	}
628
629	return false;
630	}
631
632	if (FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization ||
633	FD->getTemplatedKind() == FunctionDecl::TK_DependentNonTemplate) {
634	FunctionDecl *InstantiatedFrom =
635	FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization
636	? FD->getInstantiatedFromMemberFunction()
637	: FD->getInstantiatedFromDecl();
638
639	InstantiatingTemplate Inst(
640	*this, FD->getPointOfInstantiation(),
641	Sema::InstantiatingTemplate::ConstraintsCheck{}, InstantiatedFrom,
642	TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
643	SourceRange());
644	if (Inst.isInvalid())
645	return true;
646
647	// Case where this was not a template, but instantiated as a
648	// child-function.
649	if (addInstantiatedParametersToScope(Function: FD, PatternDecl: InstantiatedFrom, Scope, TemplateArgs: MLTAL))
650	return true;
651	}
652
653	return false;
654	}
655
656	// This function collects all of the template arguments for the purposes of
657	// constraint-instantiation and checking.
658	std::optional<MultiLevelTemplateArgumentList>
659	Sema::SetupConstraintCheckingTemplateArgumentsAndScope(
660	FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
661	LocalInstantiationScope &Scope) {
662	MultiLevelTemplateArgumentList MLTAL;
663
664	// Collect the list of template arguments relative to the 'primary' template.
665	// We need the entire list, since the constraint is completely uninstantiated
666	// at this point.
667	MLTAL =
668	getTemplateInstantiationArgs(D: FD, DC: FD->getLexicalDeclContext(),
669	/*Final=*/false, /*Innermost=*/std::nullopt,
670	/*RelativeToPrimary=*/true,
671	/*Pattern=*/nullptr,
672	/*ForConstraintInstantiation=*/true);
673	if (SetupConstraintScope(FD, TemplateArgs, MLTAL, Scope))
674	return std::nullopt;
675
676	return MLTAL;
677	}
678
679	bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,
680	ConstraintSatisfaction &Satisfaction,
681	SourceLocation UsageLoc,
682	bool ForOverloadResolution) {
683	// Don't check constraints if the function is dependent. Also don't check if
684	// this is a function template specialization, as the call to
685	// CheckinstantiatedFunctionTemplateConstraints after this will check it
686	// better.
687	if (FD->isDependentContext() ||
688	FD->getTemplatedKind() ==
689	FunctionDecl::TK_FunctionTemplateSpecialization) {
690	Satisfaction.IsSatisfied = true;
691	return false;
692	}
693
694	// A lambda conversion operator has the same constraints as the call operator
695	// and constraints checking relies on whether we are in a lambda call operator
696	// (and may refer to its parameters), so check the call operator instead.
697	// Note that the declarations outside of the lambda should also be
698	// considered. Turning on the 'ForOverloadResolution' flag results in the
699	// LocalInstantiationScope not looking into its parents, but we can still
700	// access Decls from the parents while building a lambda RAII scope later.
701	if (const auto *MD = dyn_cast<CXXConversionDecl>(Val: FD);
702	MD && isLambdaConversionOperator(C: const_cast<CXXConversionDecl *>(MD)))
703	return CheckFunctionConstraints(FD: MD->getParent()->getLambdaCallOperator(),
704	Satisfaction, UsageLoc,
705	/*ShouldAddDeclsFromParentScope=*/ForOverloadResolution: true);
706
707	DeclContext *CtxToSave = const_cast<FunctionDecl *>(FD);
708
709	while (isLambdaCallOperator(DC: CtxToSave) || FD->isTransparentContext()) {
710	if (isLambdaCallOperator(DC: CtxToSave))
711	CtxToSave = CtxToSave->getParent()->getParent();
712	else
713	CtxToSave = CtxToSave->getNonTransparentContext();
714	}
715
716	ContextRAII SavedContext{*this, CtxToSave};
717	LocalInstantiationScope Scope(*this, !ForOverloadResolution);
718	std::optional<MultiLevelTemplateArgumentList> MLTAL =
719	SetupConstraintCheckingTemplateArgumentsAndScope(
720	FD: const_cast<FunctionDecl *>(FD), TemplateArgs: {}, Scope);
721
722	if (!MLTAL)
723	return true;
724
725	Qualifiers ThisQuals;
726	CXXRecordDecl *Record = nullptr;
727	if (auto *Method = dyn_cast<CXXMethodDecl>(Val: FD)) {
728	ThisQuals = Method->getMethodQualifiers();
729	Record = const_cast<CXXRecordDecl *>(Method->getParent());
730	}
731	CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
732
733	LambdaScopeForCallOperatorInstantiationRAII LambdaScope(
734	*this, const_cast<FunctionDecl *>(FD), *MLTAL, Scope,
735	ForOverloadResolution);
736
737	return CheckConstraintSatisfaction(
738	FD, {FD->getTrailingRequiresClause()}, *MLTAL,
739	SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),
740	Satisfaction);
741	}
742
743
744	// Figure out the to-translation-unit depth for this function declaration for
745	// the purpose of seeing if they differ by constraints. This isn't the same as
746	// getTemplateDepth, because it includes already instantiated parents.
747	static unsigned
748	CalculateTemplateDepthForConstraints(Sema &S, const NamedDecl *ND,
749	bool SkipForSpecialization = false) {
750	MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
751	D: ND, DC: ND->getLexicalDeclContext(), /*Final=*/false,
752	/*Innermost=*/std::nullopt,
753	/*RelativeToPrimary=*/true,
754	/*Pattern=*/nullptr,
755	/*ForConstraintInstantiation=*/true, SkipForSpecialization);
756	return MLTAL.getNumLevels();
757	}
758
759	namespace {
760	class AdjustConstraintDepth : public TreeTransform<AdjustConstraintDepth> {
761	unsigned TemplateDepth = 0;
762	public:
763	using inherited = TreeTransform<AdjustConstraintDepth>;
764	AdjustConstraintDepth(Sema &SemaRef, unsigned TemplateDepth)
765	: inherited(SemaRef), TemplateDepth(TemplateDepth) {}
766
767	using inherited::TransformTemplateTypeParmType;
768	QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
769	TemplateTypeParmTypeLoc TL, bool) {
770	const TemplateTypeParmType *T = TL.getTypePtr();
771
772	TemplateTypeParmDecl *NewTTPDecl = nullptr;
773	if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl())
774	NewTTPDecl = cast_or_null<TemplateTypeParmDecl>(
775	TransformDecl(TL.getNameLoc(), OldTTPDecl));
776
777	QualType Result = getSema().Context.getTemplateTypeParmType(
778	T->getDepth() + TemplateDepth, T->getIndex(), T->isParameterPack(),
779	NewTTPDecl);
780	TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(T: Result);
781	NewTL.setNameLoc(TL.getNameLoc());
782	return Result;
783	}
784	};
785	} // namespace
786
787	static const Expr *SubstituteConstraintExpressionWithoutSatisfaction(
788	Sema &S, const Sema::TemplateCompareNewDeclInfo &DeclInfo,
789	const Expr *ConstrExpr) {
790	MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
791	D: DeclInfo.getDecl(), DC: DeclInfo.getLexicalDeclContext(), /*Final=*/false,
792	/*Innermost=*/std::nullopt,
793	/*RelativeToPrimary=*/true,
794	/*Pattern=*/nullptr, /*ForConstraintInstantiation=*/true,
795	/*SkipForSpecialization*/ false);
796
797	if (MLTAL.getNumSubstitutedLevels() == 0)
798	return ConstrExpr;
799
800	Sema::SFINAETrap SFINAE(S, /*AccessCheckingSFINAE=*/false);
801
802	Sema::InstantiatingTemplate Inst(
803	S, DeclInfo.getLocation(),
804	Sema::InstantiatingTemplate::ConstraintNormalization{},
805	const_cast<NamedDecl *>(DeclInfo.getDecl()), SourceRange{});
806	if (Inst.isInvalid())
807	return nullptr;
808
809	// Set up a dummy 'instantiation' scope in the case of reference to function
810	// parameters that the surrounding function hasn't been instantiated yet. Note
811	// this may happen while we're comparing two templates' constraint
812	// equivalence.
813	LocalInstantiationScope ScopeForParameters(S);
814	if (auto *FD = llvm::dyn_cast<FunctionDecl>(Val: DeclInfo.getDecl()))
815	for (auto *PVD : FD->parameters())
816	ScopeForParameters.InstantiatedLocal(PVD, PVD);
817
818	std::optional<Sema::CXXThisScopeRAII> ThisScope;
819
820	// See TreeTransform::RebuildTemplateSpecializationType. A context scope is
821	// essential for having an injected class as the canonical type for a template
822	// specialization type at the rebuilding stage. This guarantees that, for
823	// out-of-line definitions, injected class name types and their equivalent
824	// template specializations can be profiled to the same value, which makes it
825	// possible that e.g. constraints involving C<Class<T>> and C<Class> are
826	// perceived identical.
827	std::optional<Sema::ContextRAII> ContextScope;
828	if (auto *RD = dyn_cast<CXXRecordDecl>(Val: DeclInfo.getDeclContext())) {
829	ThisScope.emplace(S, const_cast<CXXRecordDecl *>(RD), Qualifiers());
830	ContextScope.emplace(S, const_cast<DeclContext *>(cast<DeclContext>(Val: RD)),
831	/*NewThisContext=*/false);
832	}
833	ExprResult SubstConstr = S.SubstConstraintExprWithoutSatisfaction(
834	E: const_cast<clang::Expr *>(ConstrExpr), TemplateArgs: MLTAL);
835	if (SFINAE.hasErrorOccurred() || !SubstConstr.isUsable())
836	return nullptr;
837	return SubstConstr.get();
838	}
839
840	bool Sema::AreConstraintExpressionsEqual(const NamedDecl *Old,
841	const Expr *OldConstr,
842	const TemplateCompareNewDeclInfo &New,
843	const Expr *NewConstr) {
844	if (OldConstr == NewConstr)
845	return true;
846	// C++ [temp.constr.decl]p4
847	if (Old && !New.isInvalid() && !New.ContainsDecl(ND: Old) &&
848	Old->getLexicalDeclContext() != New.getLexicalDeclContext()) {
849	if (const Expr *SubstConstr =
850	SubstituteConstraintExpressionWithoutSatisfaction(S&: *this, DeclInfo: Old,
851	ConstrExpr: OldConstr))
852	OldConstr = SubstConstr;
853	else
854	return false;
855	if (const Expr *SubstConstr =
856	SubstituteConstraintExpressionWithoutSatisfaction(S&: *this, DeclInfo: New,
857	ConstrExpr: NewConstr))
858	NewConstr = SubstConstr;
859	else
860	return false;
861	}
862
863	llvm::FoldingSetNodeID ID1, ID2;
864	OldConstr->Profile(ID1, Context, /*Canonical=*/true);
865	NewConstr->Profile(ID2, Context, /*Canonical=*/true);
866	return ID1 == ID2;
867	}
868
869	bool Sema::FriendConstraintsDependOnEnclosingTemplate(const FunctionDecl *FD) {
870	assert(FD->getFriendObjectKind() && "Must be a friend!");
871
872	// The logic for non-templates is handled in ASTContext::isSameEntity, so we
873	// don't have to bother checking 'DependsOnEnclosingTemplate' for a
874	// non-function-template.
875	assert(FD->getDescribedFunctionTemplate() &&
876	"Non-function templates don't need to be checked");
877
878	SmallVector<const Expr *, 3> ACs;
879	FD->getDescribedFunctionTemplate()->getAssociatedConstraints(ACs);
880
881	unsigned OldTemplateDepth = CalculateTemplateDepthForConstraints(*this, FD);
882	for (const Expr *Constraint : ACs)
883	if (ConstraintExpressionDependsOnEnclosingTemplate(Friend: FD, TemplateDepth: OldTemplateDepth,
884	Constraint))
885	return true;
886
887	return false;
888	}
889
890	bool Sema::EnsureTemplateArgumentListConstraints(
891	TemplateDecl *TD, const MultiLevelTemplateArgumentList &TemplateArgsLists,
892	SourceRange TemplateIDRange) {
893	ConstraintSatisfaction Satisfaction;
894	llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
895	TD->getAssociatedConstraints(AC&: AssociatedConstraints);
896	if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgsLists,
897	TemplateIDRange, Satisfaction))
898	return true;
899
900	if (!Satisfaction.IsSatisfied) {
901	SmallString<128> TemplateArgString;
902	TemplateArgString = " ";
903	TemplateArgString += getTemplateArgumentBindingsText(
904	Params: TD->getTemplateParameters(), Args: TemplateArgsLists.getInnermost().data(),
905	NumArgs: TemplateArgsLists.getInnermost().size());
906
907	Diag(TemplateIDRange.getBegin(),
908	diag::err_template_arg_list_constraints_not_satisfied)
909	<< (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD
910	<< TemplateArgString << TemplateIDRange;
911	DiagnoseUnsatisfiedConstraint(Satisfaction);
912	return true;
913	}
914	return false;
915	}
916
917	bool Sema::CheckInstantiatedFunctionTemplateConstraints(
918	SourceLocation PointOfInstantiation, FunctionDecl *Decl,
919	ArrayRef<TemplateArgument> TemplateArgs,
920	ConstraintSatisfaction &Satisfaction) {
921	// In most cases we're not going to have constraints, so check for that first.
922	FunctionTemplateDecl *Template = Decl->getPrimaryTemplate();
923	// Note - code synthesis context for the constraints check is created
924	// inside CheckConstraintsSatisfaction.
925	SmallVector<const Expr *, 3> TemplateAC;
926	Template->getAssociatedConstraints(TemplateAC);
927	if (TemplateAC.empty()) {
928	Satisfaction.IsSatisfied = true;
929	return false;
930	}
931
932	// Enter the scope of this instantiation. We don't use
933	// PushDeclContext because we don't have a scope.
934	Sema::ContextRAII savedContext(*this, Decl);
935	LocalInstantiationScope Scope(*this);
936
937	std::optional<MultiLevelTemplateArgumentList> MLTAL =
938	SetupConstraintCheckingTemplateArgumentsAndScope(FD: Decl, TemplateArgs,
939	Scope);
940
941	if (!MLTAL)
942	return true;
943
944	Qualifiers ThisQuals;
945	CXXRecordDecl *Record = nullptr;
946	if (auto *Method = dyn_cast<CXXMethodDecl>(Val: Decl)) {
947	ThisQuals = Method->getMethodQualifiers();
948	Record = Method->getParent();
949	}
950
951	CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
952	LambdaScopeForCallOperatorInstantiationRAII LambdaScope(
953	*this, const_cast<FunctionDecl *>(Decl), *MLTAL, Scope);
954
955	llvm::SmallVector<Expr *, 1> Converted;
956	return CheckConstraintSatisfaction(Template, TemplateAC, Converted, *MLTAL,
957	PointOfInstantiation, Satisfaction);
958	}
959
960	static void diagnoseUnsatisfiedRequirement(Sema &S,
961	concepts::ExprRequirement *Req,
962	bool First) {
963	assert(!Req->isSatisfied()
964	&& "Diagnose() can only be used on an unsatisfied requirement");
965	switch (Req->getSatisfactionStatus()) {
966	case concepts::ExprRequirement::SS_Dependent:
967	llvm_unreachable("Diagnosing a dependent requirement");
968	break;
969	case concepts::ExprRequirement::SS_ExprSubstitutionFailure: {
970	auto *SubstDiag = Req->getExprSubstitutionDiagnostic();
971	if (!SubstDiag->DiagMessage.empty())
972	S.Diag(SubstDiag->DiagLoc,
973	diag::note_expr_requirement_expr_substitution_error)
974	<< (int)First << SubstDiag->SubstitutedEntity
975	<< SubstDiag->DiagMessage;
976	else
977	S.Diag(SubstDiag->DiagLoc,
978	diag::note_expr_requirement_expr_unknown_substitution_error)
979	<< (int)First << SubstDiag->SubstitutedEntity;
980	break;
981	}
982	case concepts::ExprRequirement::SS_NoexceptNotMet:
983	S.Diag(Req->getNoexceptLoc(),
984	diag::note_expr_requirement_noexcept_not_met)
985	<< (int)First << Req->getExpr();
986	break;
987	case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {
988	auto *SubstDiag =
989	Req->getReturnTypeRequirement().getSubstitutionDiagnostic();
990	if (!SubstDiag->DiagMessage.empty())
991	S.Diag(SubstDiag->DiagLoc,
992	diag::note_expr_requirement_type_requirement_substitution_error)
993	<< (int)First << SubstDiag->SubstitutedEntity
994	<< SubstDiag->DiagMessage;
995	else
996	S.Diag(SubstDiag->DiagLoc,
997	diag::note_expr_requirement_type_requirement_unknown_substitution_error)
998	<< (int)First << SubstDiag->SubstitutedEntity;
999	break;
1000	}
1001	case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: {
1002	ConceptSpecializationExpr *ConstraintExpr =
1003	Req->getReturnTypeRequirementSubstitutedConstraintExpr();
1004	if (ConstraintExpr->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
1005	// A simple case - expr type is the type being constrained and the concept
1006	// was not provided arguments.
1007	Expr *e = Req->getExpr();
1008	S.Diag(e->getBeginLoc(),
1009	diag::note_expr_requirement_constraints_not_satisfied_simple)
1010	<< (int)First << S.Context.getReferenceQualifiedType(e)
1011	<< ConstraintExpr->getNamedConcept();
1012	} else {
1013	S.Diag(ConstraintExpr->getBeginLoc(),
1014	diag::note_expr_requirement_constraints_not_satisfied)
1015	<< (int)First << ConstraintExpr;
1016	}
1017	S.DiagnoseUnsatisfiedConstraint(Satisfaction: ConstraintExpr->getSatisfaction());
1018	break;
1019	}
1020	case concepts::ExprRequirement::SS_Satisfied:
1021	llvm_unreachable("We checked this above");
1022	}
1023	}
1024
1025	static void diagnoseUnsatisfiedRequirement(Sema &S,
1026	concepts::TypeRequirement *Req,
1027	bool First) {
1028	assert(!Req->isSatisfied()
1029	&& "Diagnose() can only be used on an unsatisfied requirement");
1030	switch (Req->getSatisfactionStatus()) {
1031	case concepts::TypeRequirement::SS_Dependent:
1032	llvm_unreachable("Diagnosing a dependent requirement");
1033	return;
1034	case concepts::TypeRequirement::SS_SubstitutionFailure: {
1035	auto *SubstDiag = Req->getSubstitutionDiagnostic();
1036	if (!SubstDiag->DiagMessage.empty())
1037	S.Diag(SubstDiag->DiagLoc,
1038	diag::note_type_requirement_substitution_error) << (int)First
1039	<< SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage;
1040	else
1041	S.Diag(SubstDiag->DiagLoc,
1042	diag::note_type_requirement_unknown_substitution_error)
1043	<< (int)First << SubstDiag->SubstitutedEntity;
1044	return;
1045	}
1046	default:
1047	llvm_unreachable("Unknown satisfaction status");
1048	return;
1049	}
1050	}
1051	static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
1052	Expr *SubstExpr,
1053	bool First = true);
1054
1055	static void diagnoseUnsatisfiedRequirement(Sema &S,
1056	concepts::NestedRequirement *Req,
1057	bool First) {
1058	using SubstitutionDiagnostic = std::pair<SourceLocation, StringRef>;
1059	for (auto &Pair : Req->getConstraintSatisfaction()) {
1060	if (auto *SubstDiag = Pair.second.dyn_cast<SubstitutionDiagnostic *>())
1061	S.Diag(SubstDiag->first, diag::note_nested_requirement_substitution_error)
1062	<< (int)First << Req->getInvalidConstraintEntity() << SubstDiag->second;
1063	else
1064	diagnoseWellFormedUnsatisfiedConstraintExpr(
1065	S, SubstExpr: Pair.second.dyn_cast<Expr *>(), First);
1066	First = false;
1067	}
1068	}
1069
1070	static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
1071	Expr *SubstExpr,
1072	bool First) {
1073	SubstExpr = SubstExpr->IgnoreParenImpCasts();
1074	if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: SubstExpr)) {
1075	switch (BO->getOpcode()) {
1076	// These two cases will in practice only be reached when using fold
1077	// expressions with || and &&, since otherwise the || and && will have been
1078	// broken down into atomic constraints during satisfaction checking.
1079	case BO_LOr:
1080	// Or evaluated to false - meaning both RHS and LHS evaluated to false.
1081	diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getLHS(), First);
1082	diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getRHS(),
1083	/*First=*/false);
1084	return;
1085	case BO_LAnd: {
1086	bool LHSSatisfied =
1087	BO->getLHS()->EvaluateKnownConstInt(Ctx: S.Context).getBoolValue();
1088	if (LHSSatisfied) {
1089	// LHS is true, so RHS must be false.
1090	diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getRHS(), First);
1091	return;
1092	}
1093	// LHS is false
1094	diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getLHS(), First);
1095
1096	// RHS might also be false
1097	bool RHSSatisfied =
1098	BO->getRHS()->EvaluateKnownConstInt(Ctx: S.Context).getBoolValue();
1099	if (!RHSSatisfied)
1100	diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getRHS(),
1101	/*First=*/false);
1102	return;
1103	}
1104	case BO_GE:
1105	case BO_LE:
1106	case BO_GT:
1107	case BO_LT:
1108	case BO_EQ:
1109	case BO_NE:
1110	if (BO->getLHS()->getType()->isIntegerType() &&
1111	BO->getRHS()->getType()->isIntegerType()) {
1112	Expr::EvalResult SimplifiedLHS;
1113	Expr::EvalResult SimplifiedRHS;
1114	BO->getLHS()->EvaluateAsInt(Result&: SimplifiedLHS, Ctx: S.Context,
1115	AllowSideEffects: Expr::SE_NoSideEffects,
1116	/*InConstantContext=*/true);
1117	BO->getRHS()->EvaluateAsInt(Result&: SimplifiedRHS, Ctx: S.Context,
1118	AllowSideEffects: Expr::SE_NoSideEffects,
1119	/*InConstantContext=*/true);
1120	if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) {
1121	S.Diag(SubstExpr->getBeginLoc(),
1122	diag::note_atomic_constraint_evaluated_to_false_elaborated)
1123	<< (int)First << SubstExpr
1124	<< toString(SimplifiedLHS.Val.getInt(), 10)
1125	<< BinaryOperator::getOpcodeStr(BO->getOpcode())
1126	<< toString(SimplifiedRHS.Val.getInt(), 10);
1127	return;
1128	}
1129	}
1130	break;
1131
1132	default:
1133	break;
1134	}
1135	} else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(Val: SubstExpr)) {
1136	if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
1137	S.Diag(
1138	CSE->getSourceRange().getBegin(),
1139	diag::
1140	note_single_arg_concept_specialization_constraint_evaluated_to_false)
1141	<< (int)First
1142	<< CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument()
1143	<< CSE->getNamedConcept();
1144	} else {
1145	S.Diag(SubstExpr->getSourceRange().getBegin(),
1146	diag::note_concept_specialization_constraint_evaluated_to_false)
1147	<< (int)First << CSE;
1148	}
1149	S.DiagnoseUnsatisfiedConstraint(Satisfaction: CSE->getSatisfaction());
1150	return;
1151	} else if (auto *RE = dyn_cast<RequiresExpr>(Val: SubstExpr)) {
1152	// FIXME: RequiresExpr should store dependent diagnostics.
1153	for (concepts::Requirement *Req : RE->getRequirements())
1154	if (!Req->isDependent() && !Req->isSatisfied()) {
1155	if (auto *E = dyn_cast<concepts::ExprRequirement>(Val: Req))
1156	diagnoseUnsatisfiedRequirement(S, Req: E, First);
1157	else if (auto *T = dyn_cast<concepts::TypeRequirement>(Val: Req))
1158	diagnoseUnsatisfiedRequirement(S, Req: T, First);
1159	else
1160	diagnoseUnsatisfiedRequirement(
1161	S, Req: cast<concepts::NestedRequirement>(Val: Req), First);
1162	break;
1163	}
1164	return;
1165	}
1166
1167	S.Diag(SubstExpr->getSourceRange().getBegin(),
1168	diag::note_atomic_constraint_evaluated_to_false)
1169	<< (int)First << SubstExpr;
1170	}
1171
1172	template<typename SubstitutionDiagnostic>
1173	static void diagnoseUnsatisfiedConstraintExpr(
1174	Sema &S, const Expr *E,
1175	const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record,
1176	bool First = true) {
1177	if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){
1178	S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)
1179	<< Diag->second;
1180	return;
1181	}
1182
1183	diagnoseWellFormedUnsatisfiedConstraintExpr(S,
1184	Record.template get<Expr *>(), First);
1185	}
1186
1187	void
1188	Sema::DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction& Satisfaction,
1189	bool First) {
1190	assert(!Satisfaction.IsSatisfied &&
1191	"Attempted to diagnose a satisfied constraint");
1192	for (auto &Pair : Satisfaction.Details) {
1193	diagnoseUnsatisfiedConstraintExpr(S&: *this, E: Pair.first, Record: Pair.second, First);
1194	First = false;
1195	}
1196	}
1197
1198	void Sema::DiagnoseUnsatisfiedConstraint(
1199	const ASTConstraintSatisfaction &Satisfaction,
1200	bool First) {
1201	assert(!Satisfaction.IsSatisfied &&
1202	"Attempted to diagnose a satisfied constraint");
1203	for (auto &Pair : Satisfaction) {
1204	diagnoseUnsatisfiedConstraintExpr(S&: *this, E: Pair.first, Record: Pair.second, First);
1205	First = false;
1206	}
1207	}
1208
1209	const NormalizedConstraint *
1210	Sema::getNormalizedAssociatedConstraints(
1211	NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) {
1212	// In case the ConstrainedDecl comes from modules, it is necessary to use
1213	// the canonical decl to avoid different atomic constraints with the 'same'
1214	// declarations.
1215	ConstrainedDecl = cast<NamedDecl>(ConstrainedDecl->getCanonicalDecl());
1216
1217	auto CacheEntry = NormalizationCache.find(Val: ConstrainedDecl);
1218	if (CacheEntry == NormalizationCache.end()) {
1219	auto Normalized =
1220	NormalizedConstraint::fromConstraintExprs(S&: *this, D: ConstrainedDecl,
1221	E: AssociatedConstraints);
1222	CacheEntry =
1223	NormalizationCache
1224	.try_emplace(Key: ConstrainedDecl,
1225	Args: Normalized
1226	? new (Context) NormalizedConstraint(
1227	std::move(*Normalized))
1228	: nullptr)
1229	.first;
1230	}
1231	return CacheEntry->second;
1232	}
1233
1234	static bool
1235	substituteParameterMappings(Sema &S, NormalizedConstraint &N,
1236	ConceptDecl *Concept,
1237	const MultiLevelTemplateArgumentList &MLTAL,
1238	const ASTTemplateArgumentListInfo *ArgsAsWritten) {
1239	if (!N.isAtomic()) {
1240	if (substituteParameterMappings(S, N&: N.getLHS(), Concept, MLTAL,
1241	ArgsAsWritten))
1242	return true;
1243	return substituteParameterMappings(S, N&: N.getRHS(), Concept, MLTAL,
1244	ArgsAsWritten);
1245	}
1246	TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
1247
1248	AtomicConstraint &Atomic = *N.getAtomicConstraint();
1249	TemplateArgumentListInfo SubstArgs;
1250	if (!Atomic.ParameterMapping) {
1251	llvm::SmallBitVector OccurringIndices(TemplateParams->size());
1252	S.MarkUsedTemplateParameters(E: Atomic.ConstraintExpr, /*OnlyDeduced=*/false,
1253	/*Depth=*/0, Used&: OccurringIndices);
1254	TemplateArgumentLoc *TempArgs =
1255	new (S.Context) TemplateArgumentLoc[OccurringIndices.count()];
1256	for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I)
1257	if (OccurringIndices[I])
1258	new (&(TempArgs)[J++])
1259	TemplateArgumentLoc(S.getIdentityTemplateArgumentLoc(
1260	Param: TemplateParams->begin()[I],
1261	// Here we assume we do not support things like
1262	// template<typename A, typename B>
1263	// concept C = ...;
1264	//
1265	// template<typename... Ts> requires C<Ts...>
1266	// struct S { };
1267	// The above currently yields a diagnostic.
1268	// We still might have default arguments for concept parameters.
1269	Location: ArgsAsWritten->NumTemplateArgs > I
1270	? ArgsAsWritten->arguments()[I].getLocation()
1271	: SourceLocation()));
1272	Atomic.ParameterMapping.emplace(args&: TempArgs, args: OccurringIndices.count());
1273	}
1274	SourceLocation InstLocBegin =
1275	ArgsAsWritten->arguments().empty()
1276	? ArgsAsWritten->getLAngleLoc()
1277	: ArgsAsWritten->arguments().front().getSourceRange().getBegin();
1278	SourceLocation InstLocEnd =
1279	ArgsAsWritten->arguments().empty()
1280	? ArgsAsWritten->getRAngleLoc()
1281	: ArgsAsWritten->arguments().front().getSourceRange().getEnd();
1282	Sema::InstantiatingTemplate Inst(
1283	S, InstLocBegin,
1284	Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, Concept,
1285	{InstLocBegin, InstLocEnd});
1286	if (Inst.isInvalid())
1287	return true;
1288	if (S.SubstTemplateArguments(Args: *Atomic.ParameterMapping, TemplateArgs: MLTAL, Outputs&: SubstArgs))
1289	return true;
1290
1291	TemplateArgumentLoc *TempArgs =
1292	new (S.Context) TemplateArgumentLoc[SubstArgs.size()];
1293	std::copy(first: SubstArgs.arguments().begin(), last: SubstArgs.arguments().end(),
1294	result: TempArgs);
1295	Atomic.ParameterMapping.emplace(args&: TempArgs, args: SubstArgs.size());
1296	return false;
1297	}
1298
1299	static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
1300	const ConceptSpecializationExpr *CSE) {
1301	MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
1302	D: CSE->getNamedConcept(), DC: CSE->getNamedConcept()->getLexicalDeclContext(),
1303	/*Final=*/false, Innermost: CSE->getTemplateArguments(),
1304	/*RelativeToPrimary=*/true,
1305	/*Pattern=*/nullptr,
1306	/*ForConstraintInstantiation=*/true);
1307
1308	return substituteParameterMappings(S, N, Concept: CSE->getNamedConcept(), MLTAL,
1309	ArgsAsWritten: CSE->getTemplateArgsAsWritten());
1310	}
1311
1312	std::optional<NormalizedConstraint>
1313	NormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D,
1314	ArrayRef<const Expr *> E) {
1315	assert(E.size() != 0);
1316	auto Conjunction = fromConstraintExpr(S, D, E: E[0]);
1317	if (!Conjunction)
1318	return std::nullopt;
1319	for (unsigned I = 1; I < E.size(); ++I) {
1320	auto Next = fromConstraintExpr(S, D, E: E[I]);
1321	if (!Next)
1322	return std::nullopt;
1323	*Conjunction = NormalizedConstraint(S.Context, std::move(*Conjunction),
1324	std::move(*Next), CCK_Conjunction);
1325	}
1326	return Conjunction;
1327	}
1328
1329	std::optional<NormalizedConstraint>
1330	NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
1331	assert(E != nullptr);
1332
1333	// C++ [temp.constr.normal]p1.1
1334	// [...]
1335	// - The normal form of an expression (E) is the normal form of E.
1336	// [...]
1337	E = E->IgnoreParenImpCasts();
1338
1339	// C++2a [temp.param]p4:
1340	// [...] If T is not a pack, then E is E', otherwise E is (E' && ...).
1341	// Fold expression is considered atomic constraints per current wording.
1342	// See http://cplusplus.github.io/concepts-ts/ts-active.html#28
1343
1344	if (LogicalBinOp BO = E) {
1345	auto LHS = fromConstraintExpr(S, D, E: BO.getLHS());
1346	if (!LHS)
1347	return std::nullopt;
1348	auto RHS = fromConstraintExpr(S, D, E: BO.getRHS());
1349	if (!RHS)
1350	return std::nullopt;
1351
1352	return NormalizedConstraint(S.Context, std::move(*LHS), std::move(*RHS),
1353	BO.isAnd() ? CCK_Conjunction : CCK_Disjunction);
1354	} else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(Val: E)) {
1355	const NormalizedConstraint *SubNF;
1356	{
1357	Sema::InstantiatingTemplate Inst(
1358	S, CSE->getExprLoc(),
1359	Sema::InstantiatingTemplate::ConstraintNormalization{}, D,
1360	CSE->getSourceRange());
1361	if (Inst.isInvalid())
1362	return std::nullopt;
1363	// C++ [temp.constr.normal]p1.1
1364	// [...]
1365	// The normal form of an id-expression of the form C<A1, A2, ..., AN>,
1366	// where C names a concept, is the normal form of the
1367	// constraint-expression of C, after substituting A1, A2, ..., AN for C’s
1368	// respective template parameters in the parameter mappings in each atomic
1369	// constraint. If any such substitution results in an invalid type or
1370	// expression, the program is ill-formed; no diagnostic is required.
1371	// [...]
1372	ConceptDecl *CD = CSE->getNamedConcept();
1373	SubNF = S.getNormalizedAssociatedConstraints(CD,
1374	{CD->getConstraintExpr()});
1375	if (!SubNF)
1376	return std::nullopt;
1377	}
1378
1379	std::optional<NormalizedConstraint> New;
1380	New.emplace(args&: S.Context, args: *SubNF);
1381
1382	if (substituteParameterMappings(S, N&: *New, CSE))
1383	return std::nullopt;
1384
1385	return New;
1386	}
1387	return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)};
1388	}
1389
1390	using NormalForm =
1391	llvm::SmallVector<llvm::SmallVector<AtomicConstraint *, 2>, 4>;
1392
1393	static NormalForm makeCNF(const NormalizedConstraint &Normalized) {
1394	if (Normalized.isAtomic())
1395	return {{Normalized.getAtomicConstraint()}};
1396
1397	NormalForm LCNF = makeCNF(Normalized: Normalized.getLHS());
1398	NormalForm RCNF = makeCNF(Normalized: Normalized.getRHS());
1399	if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) {
1400	LCNF.reserve(N: LCNF.size() + RCNF.size());
1401	while (!RCNF.empty())
1402	LCNF.push_back(Elt: RCNF.pop_back_val());
1403	return LCNF;
1404	}
1405
1406	// Disjunction
1407	NormalForm Res;
1408	Res.reserve(N: LCNF.size() * RCNF.size());
1409	for (auto &LDisjunction : LCNF)
1410	for (auto &RDisjunction : RCNF) {
1411	NormalForm::value_type Combined;
1412	Combined.reserve(N: LDisjunction.size() + RDisjunction.size());
1413	std::copy(first: LDisjunction.begin(), last: LDisjunction.end(),
1414	result: std::back_inserter(x&: Combined));
1415	std::copy(first: RDisjunction.begin(), last: RDisjunction.end(),
1416	result: std::back_inserter(x&: Combined));
1417	Res.emplace_back(Args&: Combined);
1418	}
1419	return Res;
1420	}
1421
1422	static NormalForm makeDNF(const NormalizedConstraint &Normalized) {
1423	if (Normalized.isAtomic())
1424	return {{Normalized.getAtomicConstraint()}};
1425
1426	NormalForm LDNF = makeDNF(Normalized: Normalized.getLHS());
1427	NormalForm RDNF = makeDNF(Normalized: Normalized.getRHS());
1428	if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) {
1429	LDNF.reserve(N: LDNF.size() + RDNF.size());
1430	while (!RDNF.empty())
1431	LDNF.push_back(Elt: RDNF.pop_back_val());
1432	return LDNF;
1433	}
1434
1435	// Conjunction
1436	NormalForm Res;
1437	Res.reserve(N: LDNF.size() * RDNF.size());
1438	for (auto &LConjunction : LDNF) {
1439	for (auto &RConjunction : RDNF) {
1440	NormalForm::value_type Combined;
1441	Combined.reserve(N: LConjunction.size() + RConjunction.size());
1442	std::copy(first: LConjunction.begin(), last: LConjunction.end(),
1443	result: std::back_inserter(x&: Combined));
1444	std::copy(first: RConjunction.begin(), last: RConjunction.end(),
1445	result: std::back_inserter(x&: Combined));
1446	Res.emplace_back(Args&: Combined);
1447	}
1448	}
1449	return Res;
1450	}
1451
1452	template<typename AtomicSubsumptionEvaluator>
1453	static bool subsumes(const NormalForm &PDNF, const NormalForm &QCNF,
1454	AtomicSubsumptionEvaluator E) {
1455	// C++ [temp.constr.order] p2
1456	// Then, P subsumes Q if and only if, for every disjunctive clause Pi in the
1457	// disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in
1458	// the conjuctive normal form of Q, where [...]
1459	for (const auto &Pi : PDNF) {
1460	for (const auto &Qj : QCNF) {
1461	// C++ [temp.constr.order] p2
1462	// - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
1463	// and only if there exists an atomic constraint Pia in Pi for which
1464	// there exists an atomic constraint, Qjb, in Qj such that Pia
1465	// subsumes Qjb.
1466	bool Found = false;
1467	for (const AtomicConstraint *Pia : Pi) {
1468	for (const AtomicConstraint *Qjb : Qj) {
1469	if (E(*Pia, *Qjb)) {
1470	Found = true;
1471	break;
1472	}
1473	}
1474	if (Found)
1475	break;
1476	}
1477	if (!Found)
1478	return false;
1479	}
1480	}
1481	return true;
1482	}
1483
1484	template<typename AtomicSubsumptionEvaluator>
1485	static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P,
1486	NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes,
1487	AtomicSubsumptionEvaluator E) {
1488	// C++ [temp.constr.order] p2
1489	// In order to determine if a constraint P subsumes a constraint Q, P is
1490	// transformed into disjunctive normal form, and Q is transformed into
1491	// conjunctive normal form. [...]
1492	auto *PNormalized = S.getNormalizedAssociatedConstraints(ConstrainedDecl: DP, AssociatedConstraints: P);
1493	if (!PNormalized)
1494	return true;
1495	const NormalForm PDNF = makeDNF(Normalized: *PNormalized);
1496
1497	auto *QNormalized = S.getNormalizedAssociatedConstraints(ConstrainedDecl: DQ, AssociatedConstraints: Q);
1498	if (!QNormalized)
1499	return true;
1500	const NormalForm QCNF = makeCNF(Normalized: *QNormalized);
1501
1502	Subsumes = subsumes(PDNF, QCNF, E);
1503	return false;
1504	}
1505
1506	bool Sema::IsAtLeastAsConstrained(NamedDecl *D1,
1507	MutableArrayRef<const Expr *> AC1,
1508	NamedDecl *D2,
1509	MutableArrayRef<const Expr *> AC2,
1510	bool &Result) {
1511	if (const auto *FD1 = dyn_cast<FunctionDecl>(Val: D1)) {
1512	auto IsExpectedEntity = [](const FunctionDecl *FD) {
1513	FunctionDecl::TemplatedKind Kind = FD->getTemplatedKind();
1514	return Kind == FunctionDecl::TK_NonTemplate ||
1515	Kind == FunctionDecl::TK_FunctionTemplate;
1516	};
1517	const auto *FD2 = dyn_cast<FunctionDecl>(Val: D2);
1518	(void)IsExpectedEntity;
1519	(void)FD1;
1520	(void)FD2;
1521	assert(IsExpectedEntity(FD1) && FD2 && IsExpectedEntity(FD2) &&
1522	"use non-instantiated function declaration for constraints partial "
1523	"ordering");
1524	}
1525
1526	if (AC1.empty()) {
1527	Result = AC2.empty();
1528	return false;
1529	}
1530	if (AC2.empty()) {
1531	// TD1 has associated constraints and TD2 does not.
1532	Result = true;
1533	return false;
1534	}
1535
1536	std::pair<NamedDecl *, NamedDecl *> Key{D1, D2};
1537	auto CacheEntry = SubsumptionCache.find(Val: Key);
1538	if (CacheEntry != SubsumptionCache.end()) {
1539	Result = CacheEntry->second;
1540	return false;
1541	}
1542
1543	unsigned Depth1 = CalculateTemplateDepthForConstraints(S&: *this, ND: D1, SkipForSpecialization: true);
1544	unsigned Depth2 = CalculateTemplateDepthForConstraints(S&: *this, ND: D2, SkipForSpecialization: true);
1545
1546	for (size_t I = 0; I != AC1.size() && I != AC2.size(); ++I) {
1547	if (Depth2 > Depth1) {
1548	AC1[I] = AdjustConstraintDepth(*this, Depth2 - Depth1)
1549	.TransformExpr(const_cast<Expr *>(AC1[I]))
1550	.get();
1551	} else if (Depth1 > Depth2) {
1552	AC2[I] = AdjustConstraintDepth(*this, Depth1 - Depth2)
1553	.TransformExpr(const_cast<Expr *>(AC2[I]))
1554	.get();
1555	}
1556	}
1557
1558	if (subsumes(S&: *this, DP: D1, P: AC1, DQ: D2, Q: AC2, Subsumes&: Result,
1559	E: [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
1560	return A.subsumes(C&: Context, Other: B);
1561	}))
1562	return true;
1563	SubsumptionCache.try_emplace(Key, Args&: Result);
1564	return false;
1565	}
1566
1567	bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
1568	ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) {
1569	if (isSFINAEContext())
1570	// No need to work here because our notes would be discarded.
1571	return false;
1572
1573	if (AC1.empty() || AC2.empty())
1574	return false;
1575
1576	auto NormalExprEvaluator =
1577	[this] (const AtomicConstraint &A, const AtomicConstraint &B) {
1578	return A.subsumes(C&: Context, Other: B);
1579	};
1580
1581	const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;
1582	auto IdenticalExprEvaluator =
1583	[&] (const AtomicConstraint &A, const AtomicConstraint &B) {
1584	if (!A.hasMatchingParameterMapping(C&: Context, Other: B))
1585	return false;
1586	const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr;
1587	if (EA == EB)
1588	return true;
1589
1590	// Not the same source level expression - are the expressions
1591	// identical?
1592	llvm::FoldingSetNodeID IDA, IDB;
1593	EA->Profile(IDA, Context, /*Canonical=*/true);
1594	EB->Profile(IDB, Context, /*Canonical=*/true);
1595	if (IDA != IDB)
1596	return false;
1597
1598	AmbiguousAtomic1 = EA;
1599	AmbiguousAtomic2 = EB;
1600	return true;
1601	};
1602
1603	{
1604	// The subsumption checks might cause diagnostics
1605	SFINAETrap Trap(*this);
1606	auto *Normalized1 = getNormalizedAssociatedConstraints(ConstrainedDecl: D1, AssociatedConstraints: AC1);
1607	if (!Normalized1)
1608	return false;
1609	const NormalForm DNF1 = makeDNF(Normalized: *Normalized1);
1610	const NormalForm CNF1 = makeCNF(Normalized: *Normalized1);
1611
1612	auto *Normalized2 = getNormalizedAssociatedConstraints(ConstrainedDecl: D2, AssociatedConstraints: AC2);
1613	if (!Normalized2)
1614	return false;
1615	const NormalForm DNF2 = makeDNF(Normalized: *Normalized2);
1616	const NormalForm CNF2 = makeCNF(Normalized: *Normalized2);
1617
1618	bool Is1AtLeastAs2Normally = subsumes(PDNF: DNF1, QCNF: CNF2, E: NormalExprEvaluator);
1619	bool Is2AtLeastAs1Normally = subsumes(PDNF: DNF2, QCNF: CNF1, E: NormalExprEvaluator);
1620	bool Is1AtLeastAs2 = subsumes(PDNF: DNF1, QCNF: CNF2, E: IdenticalExprEvaluator);
1621	bool Is2AtLeastAs1 = subsumes(PDNF: DNF2, QCNF: CNF1, E: IdenticalExprEvaluator);
1622	if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
1623	Is2AtLeastAs1 == Is2AtLeastAs1Normally)
1624	// Same result - no ambiguity was caused by identical atomic expressions.
1625	return false;
1626	}
1627
1628	// A different result! Some ambiguous atomic constraint(s) caused a difference
1629	assert(AmbiguousAtomic1 && AmbiguousAtomic2);
1630
1631	Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints)
1632	<< AmbiguousAtomic1->getSourceRange();
1633	Diag(AmbiguousAtomic2->getBeginLoc(),
1634	diag::note_ambiguous_atomic_constraints_similar_expression)
1635	<< AmbiguousAtomic2->getSourceRange();
1636	return true;
1637	}
1638
1639	concepts::ExprRequirement::ExprRequirement(
1640	Expr *E, bool IsSimple, SourceLocation NoexceptLoc,
1641	ReturnTypeRequirement Req, SatisfactionStatus Status,
1642	ConceptSpecializationExpr *SubstitutedConstraintExpr) :
1643	Requirement(IsSimple ? RK_Simple : RK_Compound, Status == SS_Dependent,
1644	Status == SS_Dependent &&
1645	(E->containsUnexpandedParameterPack() ||
1646	Req.containsUnexpandedParameterPack()),
1647	Status == SS_Satisfied), Value(E), NoexceptLoc(NoexceptLoc),
1648	TypeReq(Req), SubstitutedConstraintExpr(SubstitutedConstraintExpr),
1649	Status(Status) {
1650	assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1651	"Simple requirement must not have a return type requirement or a "
1652	"noexcept specification");
1653	assert((Status > SS_TypeRequirementSubstitutionFailure && Req.isTypeConstraint()) ==
1654	(SubstitutedConstraintExpr != nullptr));
1655	}
1656
1657	concepts::ExprRequirement::ExprRequirement(
1658	SubstitutionDiagnostic *ExprSubstDiag, bool IsSimple,
1659	SourceLocation NoexceptLoc, ReturnTypeRequirement Req) :
1660	Requirement(IsSimple ? RK_Simple : RK_Compound, Req.isDependent(),
1661	Req.containsUnexpandedParameterPack(), /*IsSatisfied=*/false),
1662	Value(ExprSubstDiag), NoexceptLoc(NoexceptLoc), TypeReq(Req),
1663	Status(SS_ExprSubstitutionFailure) {
1664	assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1665	"Simple requirement must not have a return type requirement or a "
1666	"noexcept specification");
1667	}
1668
1669	concepts::ExprRequirement::ReturnTypeRequirement::
1670	ReturnTypeRequirement(TemplateParameterList *TPL) :
1671	TypeConstraintInfo(TPL, false) {
1672	assert(TPL->size() == 1);
1673	const TypeConstraint *TC =
1674	cast<TemplateTypeParmDecl>(Val: TPL->getParam(Idx: 0))->getTypeConstraint();
1675	assert(TC &&
1676	"TPL must have a template type parameter with a type constraint");
1677	auto *Constraint =
1678	cast<ConceptSpecializationExpr>(Val: TC->getImmediatelyDeclaredConstraint());
1679	bool Dependent =
1680	Constraint->getTemplateArgsAsWritten() &&
1681	TemplateSpecializationType::anyInstantiationDependentTemplateArguments(
1682	Args: Constraint->getTemplateArgsAsWritten()->arguments().drop_front(N: 1));
1683	TypeConstraintInfo.setInt(Dependent ? true : false);
1684	}
1685
1686	concepts::TypeRequirement::TypeRequirement(TypeSourceInfo *T) :
1687	Requirement(RK_Type, T->getType()->isInstantiationDependentType(),
1688	T->getType()->containsUnexpandedParameterPack(),
1689	// We reach this ctor with either dependent types (in which
1690	// IsSatisfied doesn't matter) or with non-dependent type in
1691	// which the existence of the type indicates satisfaction.
1692	/*IsSatisfied=*/true),
1693	Value(T),
1694	Status(T->getType()->isInstantiationDependentType() ? SS_Dependent
1695	: SS_Satisfied) {}
1696