1 //===-- SemaConcept.cpp - Semantic Analysis for Constraints and Concepts --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements semantic analysis for C++ constraints and concepts.
12 //===----------------------------------------------------------------------===//
14 #include "clang/Sema/SemaConcept.h"
15 #include "clang/Sema/Sema.h"
16 #include "clang/Sema/SemaInternal.h"
17 #include "clang/Sema/SemaDiagnostic.h"
18 #include "clang/Sema/TemplateDeduction.h"
19 #include "clang/Sema/Template.h"
20 #include "clang/Sema/Overload.h"
21 #include "clang/Sema/Initialization.h"
22 #include "clang/Sema/SemaInternal.h"
23 #include "clang/AST/ExprConcepts.h"
24 #include "clang/AST/RecursiveASTVisitor.h"
25 #include "clang/Basic/OperatorPrecedence.h"
26 #include "llvm/ADT/DenseMap.h"
27 #include "llvm/ADT/PointerUnion.h"
28 using namespace clang;
33 OverloadedOperatorKind Op = OO_None;
34 const Expr *LHS = nullptr;
35 const Expr *RHS = nullptr;
38 LogicalBinOp(const Expr *E) {
39 if (auto *BO = dyn_cast<BinaryOperator>(E)) {
40 Op = BinaryOperator::getOverloadedOperator(BO->getOpcode());
43 } else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(E)) {
44 Op = OO->getOperator();
50 bool isAnd() const { return Op == OO_AmpAmp; }
51 bool isOr() const { return Op == OO_PipePipe; }
52 explicit operator bool() const { return isAnd() || isOr(); }
54 const Expr *getLHS() const { return LHS; }
55 const Expr *getRHS() const { return RHS; }
59 bool Sema::CheckConstraintExpression(const Expr *ConstraintExpression,
60 Token NextToken, bool *PossibleNonPrimary,
61 bool IsTrailingRequiresClause) {
62 // C++2a [temp.constr.atomic]p1
63 // ..E shall be a constant expression of type bool.
65 ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts();
67 if (LogicalBinOp BO = ConstraintExpression) {
68 return CheckConstraintExpression(BO.getLHS(), NextToken,
69 PossibleNonPrimary) &&
70 CheckConstraintExpression(BO.getRHS(), NextToken,
72 } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression))
73 return CheckConstraintExpression(C->getSubExpr(), NextToken,
76 QualType Type = ConstraintExpression->getType();
78 auto CheckForNonPrimary = [&] {
79 if (PossibleNonPrimary)
81 // We have the following case:
82 // template<typename> requires func(0) struct S { };
83 // The user probably isn't aware of the parentheses required around
84 // the function call, and we're only going to parse 'func' as the
85 // primary-expression, and complain that it is of non-bool type.
86 (NextToken.is(tok::l_paren) &&
87 (IsTrailingRequiresClause ||
88 (Type->isDependentType() &&
89 isa<UnresolvedLookupExpr>(ConstraintExpression)) ||
90 Type->isFunctionType() ||
91 Type->isSpecificBuiltinType(BuiltinType::Overload))) ||
92 // We have the following case:
93 // template<typename T> requires size_<T> == 0 struct S { };
94 // The user probably isn't aware of the parentheses required around
95 // the binary operator, and we're only going to parse 'func' as the
96 // first operand, and complain that it is of non-bool type.
97 getBinOpPrecedence(NextToken.getKind(),
98 /*GreaterThanIsOperator=*/true,
99 getLangOpts().CPlusPlus11) > prec::LogicalAnd;
102 // An atomic constraint!
103 if (ConstraintExpression->isTypeDependent()) {
104 CheckForNonPrimary();
108 if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) {
109 Diag(ConstraintExpression->getExprLoc(),
110 diag::err_non_bool_atomic_constraint) << Type
111 << ConstraintExpression->getSourceRange();
112 CheckForNonPrimary();
116 if (PossibleNonPrimary)
117 *PossibleNonPrimary = false;
121 template <typename AtomicEvaluator>
123 calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
124 ConstraintSatisfaction &Satisfaction,
125 AtomicEvaluator &&Evaluator) {
126 ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
128 if (LogicalBinOp BO = ConstraintExpr) {
129 if (calculateConstraintSatisfaction(S, BO.getLHS(), Satisfaction,
133 bool IsLHSSatisfied = Satisfaction.IsSatisfied;
135 if (BO.isOr() && IsLHSSatisfied)
136 // [temp.constr.op] p3
137 // A disjunction is a constraint taking two operands. To determine if
138 // a disjunction is satisfied, the satisfaction of the first operand
139 // is checked. If that is satisfied, the disjunction is satisfied.
140 // Otherwise, the disjunction is satisfied if and only if the second
141 // operand is satisfied.
144 if (BO.isAnd() && !IsLHSSatisfied)
145 // [temp.constr.op] p2
146 // A conjunction is a constraint taking two operands. To determine if
147 // a conjunction is satisfied, the satisfaction of the first operand
148 // is checked. If that is not satisfied, the conjunction is not
149 // satisfied. Otherwise, the conjunction is satisfied if and only if
150 // the second operand is satisfied.
153 return calculateConstraintSatisfaction(
154 S, BO.getRHS(), Satisfaction, std::forward<AtomicEvaluator>(Evaluator));
155 } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr)) {
156 return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction,
157 std::forward<AtomicEvaluator>(Evaluator));
160 // An atomic constraint expression
161 ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr);
163 if (SubstitutedAtomicExpr.isInvalid())
166 if (!SubstitutedAtomicExpr.isUsable())
167 // Evaluator has decided satisfaction without yielding an expression.
170 EnterExpressionEvaluationContext ConstantEvaluated(
171 S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
172 SmallVector<PartialDiagnosticAt, 2> EvaluationDiags;
173 Expr::EvalResult EvalResult;
174 EvalResult.Diag = &EvaluationDiags;
175 if (!SubstitutedAtomicExpr.get()->EvaluateAsRValue(EvalResult, S.Context)) {
176 // C++2a [temp.constr.atomic]p1
177 // ...E shall be a constant expression of type bool.
178 S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(),
179 diag::err_non_constant_constraint_expression)
180 << SubstitutedAtomicExpr.get()->getSourceRange();
181 for (const PartialDiagnosticAt &PDiag : EvaluationDiags)
182 S.Diag(PDiag.first, PDiag.second);
186 Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();
187 if (!Satisfaction.IsSatisfied)
188 Satisfaction.Details.emplace_back(ConstraintExpr,
189 SubstitutedAtomicExpr.get());
194 static bool calculateConstraintSatisfaction(
195 Sema &S, const NamedDecl *Template, ArrayRef<TemplateArgument> TemplateArgs,
196 SourceLocation TemplateNameLoc, MultiLevelTemplateArgumentList &MLTAL,
197 const Expr *ConstraintExpr, ConstraintSatisfaction &Satisfaction) {
198 return calculateConstraintSatisfaction(
199 S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) {
200 EnterExpressionEvaluationContext ConstantEvaluated(
201 S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
203 // Atomic constraint - substitute arguments and check satisfaction.
204 ExprResult SubstitutedExpression;
206 TemplateDeductionInfo Info(TemplateNameLoc);
207 Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(),
208 Sema::InstantiatingTemplate::ConstraintSubstitution{},
209 const_cast<NamedDecl *>(Template), Info,
210 AtomicExpr->getSourceRange());
211 if (Inst.isInvalid())
213 // We do not want error diagnostics escaping here.
214 Sema::SFINAETrap Trap(S);
215 SubstitutedExpression = S.SubstExpr(const_cast<Expr *>(AtomicExpr),
217 if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {
218 // C++2a [temp.constr.atomic]p1
219 // ...If substitution results in an invalid type or expression, the
220 // constraint is not satisfied.
221 if (!Trap.hasErrorOccurred())
222 // A non-SFINAE error has occured as a result of this
226 PartialDiagnosticAt SubstDiag{SourceLocation(),
227 PartialDiagnostic::NullDiagnostic()};
228 Info.takeSFINAEDiagnostic(SubstDiag);
229 // FIXME: Concepts: This is an unfortunate consequence of there
230 // being no serialization code for PartialDiagnostics and the fact
231 // that serializing them would likely take a lot more storage than
232 // just storing them as strings. We would still like, in the
233 // future, to serialize the proper PartialDiagnostic as serializing
234 // it as a string defeats the purpose of the diagnostic mechanism.
235 SmallString<128> DiagString;
237 SubstDiag.second.EmitToString(S.getDiagnostics(), DiagString);
238 unsigned MessageSize = DiagString.size();
239 char *Mem = new (S.Context) char[MessageSize];
240 memcpy(Mem, DiagString.c_str(), MessageSize);
241 Satisfaction.Details.emplace_back(
243 new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
244 SubstDiag.first, StringRef(Mem, MessageSize)});
245 Satisfaction.IsSatisfied = false;
250 if (!S.CheckConstraintExpression(SubstitutedExpression.get()))
253 return SubstitutedExpression;
257 static bool CheckConstraintSatisfaction(Sema &S, const NamedDecl *Template,
258 ArrayRef<const Expr *> ConstraintExprs,
259 ArrayRef<TemplateArgument> TemplateArgs,
260 SourceRange TemplateIDRange,
261 ConstraintSatisfaction &Satisfaction) {
262 if (ConstraintExprs.empty()) {
263 Satisfaction.IsSatisfied = true;
267 for (auto& Arg : TemplateArgs)
268 if (Arg.isInstantiationDependent()) {
269 // No need to check satisfaction for dependent constraint expressions.
270 Satisfaction.IsSatisfied = true;
274 Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(),
275 Sema::InstantiatingTemplate::ConstraintsCheck{},
276 const_cast<NamedDecl *>(Template), TemplateArgs, TemplateIDRange);
277 if (Inst.isInvalid())
280 MultiLevelTemplateArgumentList MLTAL;
281 MLTAL.addOuterTemplateArguments(TemplateArgs);
283 for (const Expr *ConstraintExpr : ConstraintExprs) {
284 if (calculateConstraintSatisfaction(S, Template, TemplateArgs,
285 TemplateIDRange.getBegin(), MLTAL,
286 ConstraintExpr, Satisfaction))
288 if (!Satisfaction.IsSatisfied)
289 // [temp.constr.op] p2
290 // [...] To determine if a conjunction is satisfied, the satisfaction
291 // of the first operand is checked. If that is not satisfied, the
292 // conjunction is not satisfied. [...]
298 bool Sema::CheckConstraintSatisfaction(
299 const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
300 ArrayRef<TemplateArgument> TemplateArgs, SourceRange TemplateIDRange,
301 ConstraintSatisfaction &OutSatisfaction) {
302 if (ConstraintExprs.empty()) {
303 OutSatisfaction.IsSatisfied = true;
307 llvm::FoldingSetNodeID ID;
309 ConstraintSatisfaction *Satisfaction = nullptr;
310 bool ShouldCache = LangOpts.ConceptSatisfactionCaching && Template;
312 ConstraintSatisfaction::Profile(ID, Context, Template, TemplateArgs);
313 Satisfaction = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos);
315 OutSatisfaction = *Satisfaction;
318 Satisfaction = new ConstraintSatisfaction(Template, TemplateArgs);
320 Satisfaction = &OutSatisfaction;
322 if (::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
323 TemplateArgs, TemplateIDRange,
331 // We cannot use InsertNode here because CheckConstraintSatisfaction might
332 // have invalidated it.
333 SatisfactionCache.InsertNode(Satisfaction);
334 OutSatisfaction = *Satisfaction;
339 bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
340 ConstraintSatisfaction &Satisfaction) {
341 return calculateConstraintSatisfaction(
342 *this, ConstraintExpr, Satisfaction,
343 [](const Expr *AtomicExpr) -> ExprResult {
344 return ExprResult(const_cast<Expr *>(AtomicExpr));
348 bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,
349 ConstraintSatisfaction &Satisfaction,
350 SourceLocation UsageLoc) {
351 const Expr *RC = FD->getTrailingRequiresClause();
352 if (RC->isInstantiationDependent()) {
353 Satisfaction.IsSatisfied = true;
356 Qualifiers ThisQuals;
357 CXXRecordDecl *Record = nullptr;
358 if (auto *Method = dyn_cast<CXXMethodDecl>(FD)) {
359 ThisQuals = Method->getMethodQualifiers();
360 Record = const_cast<CXXRecordDecl *>(Method->getParent());
362 CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
363 // We substitute with empty arguments in order to rebuild the atomic
364 // constraint in a constant-evaluated context.
365 // FIXME: Should this be a dedicated TreeTransform?
366 return CheckConstraintSatisfaction(
367 FD, {RC}, /*TemplateArgs=*/{},
368 SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),
372 bool Sema::EnsureTemplateArgumentListConstraints(
373 TemplateDecl *TD, ArrayRef<TemplateArgument> TemplateArgs,
374 SourceRange TemplateIDRange) {
375 ConstraintSatisfaction Satisfaction;
376 llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
377 TD->getAssociatedConstraints(AssociatedConstraints);
378 if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgs,
379 TemplateIDRange, Satisfaction))
382 if (!Satisfaction.IsSatisfied) {
383 SmallString<128> TemplateArgString;
384 TemplateArgString = " ";
385 TemplateArgString += getTemplateArgumentBindingsText(
386 TD->getTemplateParameters(), TemplateArgs.data(), TemplateArgs.size());
388 Diag(TemplateIDRange.getBegin(),
389 diag::err_template_arg_list_constraints_not_satisfied)
390 << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD
391 << TemplateArgString << TemplateIDRange;
392 DiagnoseUnsatisfiedConstraint(Satisfaction);
398 static void diagnoseUnsatisfiedRequirement(Sema &S,
399 concepts::ExprRequirement *Req,
401 assert(!Req->isSatisfied()
402 && "Diagnose() can only be used on an unsatisfied requirement");
403 switch (Req->getSatisfactionStatus()) {
404 case concepts::ExprRequirement::SS_Dependent:
405 llvm_unreachable("Diagnosing a dependent requirement");
407 case concepts::ExprRequirement::SS_ExprSubstitutionFailure: {
408 auto *SubstDiag = Req->getExprSubstitutionDiagnostic();
409 if (!SubstDiag->DiagMessage.empty())
410 S.Diag(SubstDiag->DiagLoc,
411 diag::note_expr_requirement_expr_substitution_error)
412 << (int)First << SubstDiag->SubstitutedEntity
413 << SubstDiag->DiagMessage;
415 S.Diag(SubstDiag->DiagLoc,
416 diag::note_expr_requirement_expr_unknown_substitution_error)
417 << (int)First << SubstDiag->SubstitutedEntity;
420 case concepts::ExprRequirement::SS_NoexceptNotMet:
421 S.Diag(Req->getNoexceptLoc(),
422 diag::note_expr_requirement_noexcept_not_met)
423 << (int)First << Req->getExpr();
425 case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {
427 Req->getReturnTypeRequirement().getSubstitutionDiagnostic();
428 if (!SubstDiag->DiagMessage.empty())
429 S.Diag(SubstDiag->DiagLoc,
430 diag::note_expr_requirement_type_requirement_substitution_error)
431 << (int)First << SubstDiag->SubstitutedEntity
432 << SubstDiag->DiagMessage;
434 S.Diag(SubstDiag->DiagLoc,
435 diag::note_expr_requirement_type_requirement_unknown_substitution_error)
436 << (int)First << SubstDiag->SubstitutedEntity;
439 case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: {
440 ConceptSpecializationExpr *ConstraintExpr =
441 Req->getReturnTypeRequirementSubstitutedConstraintExpr();
442 if (ConstraintExpr->getTemplateArgsAsWritten()->NumTemplateArgs == 1)
443 // A simple case - expr type is the type being constrained and the concept
444 // was not provided arguments.
445 S.Diag(ConstraintExpr->getBeginLoc(),
446 diag::note_expr_requirement_constraints_not_satisfied_simple)
447 << (int)First << S.BuildDecltypeType(Req->getExpr(),
448 Req->getExpr()->getBeginLoc())
449 << ConstraintExpr->getNamedConcept();
451 S.Diag(ConstraintExpr->getBeginLoc(),
452 diag::note_expr_requirement_constraints_not_satisfied)
453 << (int)First << ConstraintExpr;
454 S.DiagnoseUnsatisfiedConstraint(ConstraintExpr->getSatisfaction());
457 case concepts::ExprRequirement::SS_Satisfied:
458 llvm_unreachable("We checked this above");
462 static void diagnoseUnsatisfiedRequirement(Sema &S,
463 concepts::TypeRequirement *Req,
465 assert(!Req->isSatisfied()
466 && "Diagnose() can only be used on an unsatisfied requirement");
467 switch (Req->getSatisfactionStatus()) {
468 case concepts::TypeRequirement::SS_Dependent:
469 llvm_unreachable("Diagnosing a dependent requirement");
471 case concepts::TypeRequirement::SS_SubstitutionFailure: {
472 auto *SubstDiag = Req->getSubstitutionDiagnostic();
473 if (!SubstDiag->DiagMessage.empty())
474 S.Diag(SubstDiag->DiagLoc,
475 diag::note_type_requirement_substitution_error) << (int)First
476 << SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage;
478 S.Diag(SubstDiag->DiagLoc,
479 diag::note_type_requirement_unknown_substitution_error)
480 << (int)First << SubstDiag->SubstitutedEntity;
484 llvm_unreachable("Unknown satisfaction status");
489 static void diagnoseUnsatisfiedRequirement(Sema &S,
490 concepts::NestedRequirement *Req,
492 if (Req->isSubstitutionFailure()) {
493 concepts::Requirement::SubstitutionDiagnostic *SubstDiag =
494 Req->getSubstitutionDiagnostic();
495 if (!SubstDiag->DiagMessage.empty())
496 S.Diag(SubstDiag->DiagLoc,
497 diag::note_nested_requirement_substitution_error)
498 << (int)First << SubstDiag->SubstitutedEntity
499 << SubstDiag->DiagMessage;
501 S.Diag(SubstDiag->DiagLoc,
502 diag::note_nested_requirement_unknown_substitution_error)
503 << (int)First << SubstDiag->SubstitutedEntity;
506 S.DiagnoseUnsatisfiedConstraint(Req->getConstraintSatisfaction(), First);
510 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
513 SubstExpr = SubstExpr->IgnoreParenImpCasts();
514 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) {
515 switch (BO->getOpcode()) {
516 // These two cases will in practice only be reached when using fold
517 // expressions with || and &&, since otherwise the || and && will have been
518 // broken down into atomic constraints during satisfaction checking.
520 // Or evaluated to false - meaning both RHS and LHS evaluated to false.
521 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
522 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
527 BO->getLHS()->EvaluateAsBooleanCondition(LHSSatisfied, S.Context);
529 // LHS is true, so RHS must be false.
530 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First);
534 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
536 // RHS might also be false
538 BO->getRHS()->EvaluateAsBooleanCondition(RHSSatisfied, S.Context);
540 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
549 if (BO->getLHS()->getType()->isIntegerType() &&
550 BO->getRHS()->getType()->isIntegerType()) {
551 Expr::EvalResult SimplifiedLHS;
552 Expr::EvalResult SimplifiedRHS;
553 BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context);
554 BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context);
555 if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) {
556 S.Diag(SubstExpr->getBeginLoc(),
557 diag::note_atomic_constraint_evaluated_to_false_elaborated)
558 << (int)First << SubstExpr
559 << SimplifiedLHS.Val.getInt().toString(10)
560 << BinaryOperator::getOpcodeStr(BO->getOpcode())
561 << SimplifiedRHS.Val.getInt().toString(10);
570 } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) {
571 if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
573 CSE->getSourceRange().getBegin(),
575 note_single_arg_concept_specialization_constraint_evaluated_to_false)
577 << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument()
578 << CSE->getNamedConcept();
580 S.Diag(SubstExpr->getSourceRange().getBegin(),
581 diag::note_concept_specialization_constraint_evaluated_to_false)
582 << (int)First << CSE;
584 S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction());
586 } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) {
587 for (concepts::Requirement *Req : RE->getRequirements())
588 if (!Req->isDependent() && !Req->isSatisfied()) {
589 if (auto *E = dyn_cast<concepts::ExprRequirement>(Req))
590 diagnoseUnsatisfiedRequirement(S, E, First);
591 else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req))
592 diagnoseUnsatisfiedRequirement(S, T, First);
594 diagnoseUnsatisfiedRequirement(
595 S, cast<concepts::NestedRequirement>(Req), First);
601 S.Diag(SubstExpr->getSourceRange().getBegin(),
602 diag::note_atomic_constraint_evaluated_to_false)
603 << (int)First << SubstExpr;
606 template<typename SubstitutionDiagnostic>
607 static void diagnoseUnsatisfiedConstraintExpr(
608 Sema &S, const Expr *E,
609 const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record,
611 if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){
612 S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)
617 diagnoseWellFormedUnsatisfiedConstraintExpr(S,
618 Record.template get<Expr *>(), First);
622 Sema::DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction& Satisfaction,
624 assert(!Satisfaction.IsSatisfied &&
625 "Attempted to diagnose a satisfied constraint");
626 for (auto &Pair : Satisfaction.Details) {
627 diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
632 void Sema::DiagnoseUnsatisfiedConstraint(
633 const ASTConstraintSatisfaction &Satisfaction,
635 assert(!Satisfaction.IsSatisfied &&
636 "Attempted to diagnose a satisfied constraint");
637 for (auto &Pair : Satisfaction) {
638 diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
643 const NormalizedConstraint *
644 Sema::getNormalizedAssociatedConstraints(
645 NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) {
646 auto CacheEntry = NormalizationCache.find(ConstrainedDecl);
647 if (CacheEntry == NormalizationCache.end()) {
649 NormalizedConstraint::fromConstraintExprs(*this, ConstrainedDecl,
650 AssociatedConstraints);
653 .try_emplace(ConstrainedDecl,
655 ? new (Context) NormalizedConstraint(
656 std::move(*Normalized))
660 return CacheEntry->second;
663 static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
664 ConceptDecl *Concept, ArrayRef<TemplateArgument> TemplateArgs,
665 const ASTTemplateArgumentListInfo *ArgsAsWritten) {
667 if (substituteParameterMappings(S, N.getLHS(), Concept, TemplateArgs,
670 return substituteParameterMappings(S, N.getRHS(), Concept, TemplateArgs,
673 TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
675 AtomicConstraint &Atomic = *N.getAtomicConstraint();
676 TemplateArgumentListInfo SubstArgs;
677 MultiLevelTemplateArgumentList MLTAL;
678 MLTAL.addOuterTemplateArguments(TemplateArgs);
679 if (!Atomic.ParameterMapping) {
680 llvm::SmallBitVector OccurringIndices(TemplateParams->size());
681 S.MarkUsedTemplateParameters(Atomic.ConstraintExpr, /*OnlyDeduced=*/false,
682 /*Depth=*/0, OccurringIndices);
683 Atomic.ParameterMapping.emplace(
684 MutableArrayRef<TemplateArgumentLoc>(
685 new (S.Context) TemplateArgumentLoc[OccurringIndices.count()],
686 OccurringIndices.count()));
687 for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I)
688 if (OccurringIndices[I])
689 new (&(*Atomic.ParameterMapping)[J++]) TemplateArgumentLoc(
690 S.getIdentityTemplateArgumentLoc(TemplateParams->begin()[I],
691 // Here we assume we do not support things like
692 // template<typename A, typename B>
695 // template<typename... Ts> requires C<Ts...>
697 // The above currently yields a diagnostic.
698 // We still might have default arguments for concept parameters.
699 ArgsAsWritten->NumTemplateArgs > I ?
700 ArgsAsWritten->arguments()[I].getLocation() :
703 Sema::InstantiatingTemplate Inst(
704 S, ArgsAsWritten->arguments().front().getSourceRange().getBegin(),
705 Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, Concept,
706 SourceRange(ArgsAsWritten->arguments()[0].getSourceRange().getBegin(),
707 ArgsAsWritten->arguments().back().getSourceRange().getEnd()));
708 if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs))
710 Atomic.ParameterMapping.emplace(
711 MutableArrayRef<TemplateArgumentLoc>(
712 new (S.Context) TemplateArgumentLoc[SubstArgs.size()],
714 std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(),
715 N.getAtomicConstraint()->ParameterMapping->begin());
719 Optional<NormalizedConstraint>
720 NormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D,
721 ArrayRef<const Expr *> E) {
722 assert(E.size() != 0);
723 auto First = fromConstraintExpr(S, D, E[0]);
726 auto Second = fromConstraintExpr(S, D, E[1]);
729 llvm::Optional<NormalizedConstraint> Conjunction;
730 Conjunction.emplace(S.Context, std::move(*First), std::move(*Second),
732 for (unsigned I = 2; I < E.size(); ++I) {
733 auto Next = fromConstraintExpr(S, D, E[I]);
735 return llvm::Optional<NormalizedConstraint>{};
736 NormalizedConstraint NewConjunction(S.Context, std::move(*Conjunction),
737 std::move(*Next), CCK_Conjunction);
738 *Conjunction = std::move(NewConjunction);
743 llvm::Optional<NormalizedConstraint>
744 NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
745 assert(E != nullptr);
747 // C++ [temp.constr.normal]p1.1
749 // - The normal form of an expression (E) is the normal form of E.
751 E = E->IgnoreParenImpCasts();
752 if (LogicalBinOp BO = E) {
753 auto LHS = fromConstraintExpr(S, D, BO.getLHS());
756 auto RHS = fromConstraintExpr(S, D, BO.getRHS());
760 return NormalizedConstraint(S.Context, std::move(*LHS), std::move(*RHS),
761 BO.isAnd() ? CCK_Conjunction : CCK_Disjunction);
762 } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) {
763 const NormalizedConstraint *SubNF;
765 Sema::InstantiatingTemplate Inst(
766 S, CSE->getExprLoc(),
767 Sema::InstantiatingTemplate::ConstraintNormalization{}, D,
768 CSE->getSourceRange());
769 // C++ [temp.constr.normal]p1.1
771 // The normal form of an id-expression of the form C<A1, A2, ..., AN>,
772 // where C names a concept, is the normal form of the
773 // constraint-expression of C, after substituting A1, A2, ..., AN for C’s
774 // respective template parameters in the parameter mappings in each atomic
775 // constraint. If any such substitution results in an invalid type or
776 // expression, the program is ill-formed; no diagnostic is required.
778 ConceptDecl *CD = CSE->getNamedConcept();
779 SubNF = S.getNormalizedAssociatedConstraints(CD,
780 {CD->getConstraintExpr()});
785 Optional<NormalizedConstraint> New;
786 New.emplace(S.Context, *SubNF);
788 if (substituteParameterMappings(
789 S, *New, CSE->getNamedConcept(),
790 CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten()))
795 return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)};
799 llvm::SmallVector<llvm::SmallVector<AtomicConstraint *, 2>, 4>;
801 static NormalForm makeCNF(const NormalizedConstraint &Normalized) {
802 if (Normalized.isAtomic())
803 return {{Normalized.getAtomicConstraint()}};
805 NormalForm LCNF = makeCNF(Normalized.getLHS());
806 NormalForm RCNF = makeCNF(Normalized.getRHS());
807 if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) {
808 LCNF.reserve(LCNF.size() + RCNF.size());
809 while (!RCNF.empty())
810 LCNF.push_back(RCNF.pop_back_val());
816 Res.reserve(LCNF.size() * RCNF.size());
817 for (auto &LDisjunction : LCNF)
818 for (auto &RDisjunction : RCNF) {
819 NormalForm::value_type Combined;
820 Combined.reserve(LDisjunction.size() + RDisjunction.size());
821 std::copy(LDisjunction.begin(), LDisjunction.end(),
822 std::back_inserter(Combined));
823 std::copy(RDisjunction.begin(), RDisjunction.end(),
824 std::back_inserter(Combined));
825 Res.emplace_back(Combined);
830 static NormalForm makeDNF(const NormalizedConstraint &Normalized) {
831 if (Normalized.isAtomic())
832 return {{Normalized.getAtomicConstraint()}};
834 NormalForm LDNF = makeDNF(Normalized.getLHS());
835 NormalForm RDNF = makeDNF(Normalized.getRHS());
836 if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) {
837 LDNF.reserve(LDNF.size() + RDNF.size());
838 while (!RDNF.empty())
839 LDNF.push_back(RDNF.pop_back_val());
845 Res.reserve(LDNF.size() * RDNF.size());
846 for (auto &LConjunction : LDNF) {
847 for (auto &RConjunction : RDNF) {
848 NormalForm::value_type Combined;
849 Combined.reserve(LConjunction.size() + RConjunction.size());
850 std::copy(LConjunction.begin(), LConjunction.end(),
851 std::back_inserter(Combined));
852 std::copy(RConjunction.begin(), RConjunction.end(),
853 std::back_inserter(Combined));
854 Res.emplace_back(Combined);
860 template<typename AtomicSubsumptionEvaluator>
861 static bool subsumes(NormalForm PDNF, NormalForm QCNF,
862 AtomicSubsumptionEvaluator E) {
863 // C++ [temp.constr.order] p2
864 // Then, P subsumes Q if and only if, for every disjunctive clause Pi in the
865 // disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in
866 // the conjuctive normal form of Q, where [...]
867 for (const auto &Pi : PDNF) {
868 for (const auto &Qj : QCNF) {
869 // C++ [temp.constr.order] p2
870 // - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
871 // and only if there exists an atomic constraint Pia in Pi for which
872 // there exists an atomic constraint, Qjb, in Qj such that Pia
875 for (const AtomicConstraint *Pia : Pi) {
876 for (const AtomicConstraint *Qjb : Qj) {
892 template<typename AtomicSubsumptionEvaluator>
893 static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P,
894 NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes,
895 AtomicSubsumptionEvaluator E) {
896 // C++ [temp.constr.order] p2
897 // In order to determine if a constraint P subsumes a constraint Q, P is
898 // transformed into disjunctive normal form, and Q is transformed into
899 // conjunctive normal form. [...]
900 auto *PNormalized = S.getNormalizedAssociatedConstraints(DP, P);
903 const NormalForm PDNF = makeDNF(*PNormalized);
905 auto *QNormalized = S.getNormalizedAssociatedConstraints(DQ, Q);
908 const NormalForm QCNF = makeCNF(*QNormalized);
910 Subsumes = subsumes(PDNF, QCNF, E);
914 bool Sema::IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef<const Expr *> AC1,
915 NamedDecl *D2, ArrayRef<const Expr *> AC2,
918 Result = AC2.empty();
922 // TD1 has associated constraints and TD2 does not.
927 std::pair<NamedDecl *, NamedDecl *> Key{D1, D2};
928 auto CacheEntry = SubsumptionCache.find(Key);
929 if (CacheEntry != SubsumptionCache.end()) {
930 Result = CacheEntry->second;
934 if (subsumes(*this, D1, AC1, D2, AC2, Result,
935 [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
936 return A.subsumes(Context, B);
939 SubsumptionCache.try_emplace(Key, Result);
943 bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
944 ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) {
945 if (isSFINAEContext())
946 // No need to work here because our notes would be discarded.
949 if (AC1.empty() || AC2.empty())
952 auto NormalExprEvaluator =
953 [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
954 return A.subsumes(Context, B);
957 const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;
958 auto IdenticalExprEvaluator =
959 [&] (const AtomicConstraint &A, const AtomicConstraint &B) {
960 if (!A.hasMatchingParameterMapping(Context, B))
962 const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr;
966 // Not the same source level expression - are the expressions
968 llvm::FoldingSetNodeID IDA, IDB;
969 EA->Profile(IDA, Context, /*Cannonical=*/true);
970 EB->Profile(IDB, Context, /*Cannonical=*/true);
974 AmbiguousAtomic1 = EA;
975 AmbiguousAtomic2 = EB;
980 // The subsumption checks might cause diagnostics
981 SFINAETrap Trap(*this);
982 auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1);
985 const NormalForm DNF1 = makeDNF(*Normalized1);
986 const NormalForm CNF1 = makeCNF(*Normalized1);
988 auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2);
991 const NormalForm DNF2 = makeDNF(*Normalized2);
992 const NormalForm CNF2 = makeCNF(*Normalized2);
994 bool Is1AtLeastAs2Normally = subsumes(DNF1, CNF2, NormalExprEvaluator);
995 bool Is2AtLeastAs1Normally = subsumes(DNF2, CNF1, NormalExprEvaluator);
996 bool Is1AtLeastAs2 = subsumes(DNF1, CNF2, IdenticalExprEvaluator);
997 bool Is2AtLeastAs1 = subsumes(DNF2, CNF1, IdenticalExprEvaluator);
998 if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
999 Is2AtLeastAs1 == Is2AtLeastAs1Normally)
1000 // Same result - no ambiguity was caused by identical atomic expressions.
1004 // A different result! Some ambiguous atomic constraint(s) caused a difference
1005 assert(AmbiguousAtomic1 && AmbiguousAtomic2);
1007 Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints)
1008 << AmbiguousAtomic1->getSourceRange();
1009 Diag(AmbiguousAtomic2->getBeginLoc(),
1010 diag::note_ambiguous_atomic_constraints_similar_expression)
1011 << AmbiguousAtomic2->getSourceRange();
1015 concepts::ExprRequirement::ExprRequirement(
1016 Expr *E, bool IsSimple, SourceLocation NoexceptLoc,
1017 ReturnTypeRequirement Req, SatisfactionStatus Status,
1018 ConceptSpecializationExpr *SubstitutedConstraintExpr) :
1019 Requirement(IsSimple ? RK_Simple : RK_Compound, Status == SS_Dependent,
1020 Status == SS_Dependent &&
1021 (E->containsUnexpandedParameterPack() ||
1022 Req.containsUnexpandedParameterPack()),
1023 Status == SS_Satisfied), Value(E), NoexceptLoc(NoexceptLoc),
1024 TypeReq(Req), SubstitutedConstraintExpr(SubstitutedConstraintExpr),
1026 assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1027 "Simple requirement must not have a return type requirement or a "
1028 "noexcept specification");
1029 assert((Status > SS_TypeRequirementSubstitutionFailure && Req.isTypeConstraint()) ==
1030 (SubstitutedConstraintExpr != nullptr));
1033 concepts::ExprRequirement::ExprRequirement(
1034 SubstitutionDiagnostic *ExprSubstDiag, bool IsSimple,
1035 SourceLocation NoexceptLoc, ReturnTypeRequirement Req) :
1036 Requirement(IsSimple ? RK_Simple : RK_Compound, Req.isDependent(),
1037 Req.containsUnexpandedParameterPack(), /*IsSatisfied=*/false),
1038 Value(ExprSubstDiag), NoexceptLoc(NoexceptLoc), TypeReq(Req),
1039 Status(SS_ExprSubstitutionFailure) {
1040 assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1041 "Simple requirement must not have a return type requirement or a "
1042 "noexcept specification");
1045 concepts::ExprRequirement::ReturnTypeRequirement::
1046 ReturnTypeRequirement(TemplateParameterList *TPL) :
1047 TypeConstraintInfo(TPL, 0) {
1048 assert(TPL->size() == 1);
1049 const TypeConstraint *TC =
1050 cast<TemplateTypeParmDecl>(TPL->getParam(0))->getTypeConstraint();
1052 "TPL must have a template type parameter with a type constraint");
1054 cast_or_null<ConceptSpecializationExpr>(
1055 TC->getImmediatelyDeclaredConstraint());
1056 bool Dependent = false;
1057 if (Constraint->getTemplateArgsAsWritten()) {
1059 Constraint->getTemplateArgsAsWritten()->arguments().drop_front(1)) {
1060 if (ArgLoc.getArgument().isDependent()) {
1066 TypeConstraintInfo.setInt(Dependent ? 1 : 0);
1069 concepts::TypeRequirement::TypeRequirement(TypeSourceInfo *T) :
1070 Requirement(RK_Type, T->getType()->isDependentType(),
1071 T->getType()->containsUnexpandedParameterPack(),
1072 // We reach this ctor with either dependent types (in which
1073 // IsSatisfied doesn't matter) or with non-dependent type in
1074 // which the existence of the type indicates satisfaction.
1075 /*IsSatisfied=*/true
1077 Status(T->getType()->isDependentType() ? SS_Dependent : SS_Satisfied) {}