xref: /freebsd/contrib/llvm-project/clang/lib/Sema/SemaConcept.cpp (revision 56e766af41cd68310f5583bb893b13c006fcb44f)
1 //===-- SemaConcept.cpp - Semantic Analysis for Constraints and Concepts --===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file implements semantic analysis for C++ constraints and concepts.
11 //
12 //===----------------------------------------------------------------------===//
13 
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;
29 using namespace sema;
30 
31 bool
32 Sema::CheckConstraintExpression(Expr *ConstraintExpression, Token NextToken,
33                                 bool *PossibleNonPrimary,
34                                 bool IsTrailingRequiresClause) {
35   // C++2a [temp.constr.atomic]p1
36   // ..E shall be a constant expression of type bool.
37 
38   ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts();
39 
40   if (auto *BinOp = dyn_cast<BinaryOperator>(ConstraintExpression)) {
41     if (BinOp->getOpcode() == BO_LAnd || BinOp->getOpcode() == BO_LOr)
42       return CheckConstraintExpression(BinOp->getLHS(), NextToken,
43                                        PossibleNonPrimary) &&
44              CheckConstraintExpression(BinOp->getRHS(), NextToken,
45                                        PossibleNonPrimary);
46   } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression))
47     return CheckConstraintExpression(C->getSubExpr(), NextToken,
48                                      PossibleNonPrimary);
49 
50   QualType Type = ConstraintExpression->getType();
51 
52   auto CheckForNonPrimary = [&] {
53     if (PossibleNonPrimary)
54       *PossibleNonPrimary =
55           // We have the following case:
56           // template<typename> requires func(0) struct S { };
57           // The user probably isn't aware of the parentheses required around
58           // the function call, and we're only going to parse 'func' as the
59           // primary-expression, and complain that it is of non-bool type.
60           (NextToken.is(tok::l_paren) &&
61            (IsTrailingRequiresClause ||
62             (Type->isDependentType() &&
63              IsDependentFunctionNameExpr(ConstraintExpression)) ||
64             Type->isFunctionType() ||
65             Type->isSpecificBuiltinType(BuiltinType::Overload))) ||
66           // We have the following case:
67           // template<typename T> requires size_<T> == 0 struct S { };
68           // The user probably isn't aware of the parentheses required around
69           // the binary operator, and we're only going to parse 'func' as the
70           // first operand, and complain that it is of non-bool type.
71           getBinOpPrecedence(NextToken.getKind(),
72                              /*GreaterThanIsOperator=*/true,
73                              getLangOpts().CPlusPlus11) > prec::LogicalAnd;
74   };
75 
76   // An atomic constraint!
77   if (ConstraintExpression->isTypeDependent()) {
78     CheckForNonPrimary();
79     return true;
80   }
81 
82   if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) {
83     Diag(ConstraintExpression->getExprLoc(),
84          diag::err_non_bool_atomic_constraint) << Type
85         << ConstraintExpression->getSourceRange();
86     CheckForNonPrimary();
87     return false;
88   }
89 
90   if (PossibleNonPrimary)
91       *PossibleNonPrimary = false;
92   return true;
93 }
94 
95 template <typename AtomicEvaluator>
96 static bool
97 calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
98                                 ConstraintSatisfaction &Satisfaction,
99                                 AtomicEvaluator &&Evaluator) {
100   ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
101 
102   if (auto *BO = dyn_cast<BinaryOperator>(ConstraintExpr)) {
103     if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) {
104       if (calculateConstraintSatisfaction(S, BO->getLHS(), Satisfaction,
105                                           Evaluator))
106         return true;
107 
108       bool IsLHSSatisfied = Satisfaction.IsSatisfied;
109 
110       if (BO->getOpcode() == BO_LOr && IsLHSSatisfied)
111         // [temp.constr.op] p3
112         //    A disjunction is a constraint taking two operands. To determine if
113         //    a disjunction is satisfied, the satisfaction of the first operand
114         //    is checked. If that is satisfied, the disjunction is satisfied.
115         //    Otherwise, the disjunction is satisfied if and only if the second
116         //    operand is satisfied.
117         return false;
118 
119       if (BO->getOpcode() == BO_LAnd && !IsLHSSatisfied)
120         // [temp.constr.op] p2
121         //    A conjunction is a constraint taking two operands. To determine if
122         //    a conjunction is satisfied, the satisfaction of the first operand
123         //    is checked. If that is not satisfied, the conjunction is not
124         //    satisfied. Otherwise, the conjunction is satisfied if and only if
125         //    the second operand is satisfied.
126         return false;
127 
128       return calculateConstraintSatisfaction(S, BO->getRHS(), Satisfaction,
129           std::forward<AtomicEvaluator>(Evaluator));
130     }
131   }
132   else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr))
133     return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction,
134         std::forward<AtomicEvaluator>(Evaluator));
135 
136   // An atomic constraint expression
137   ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr);
138 
139   if (SubstitutedAtomicExpr.isInvalid())
140     return true;
141 
142   if (!SubstitutedAtomicExpr.isUsable())
143     // Evaluator has decided satisfaction without yielding an expression.
144     return false;
145 
146   EnterExpressionEvaluationContext ConstantEvaluated(
147       S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
148   SmallVector<PartialDiagnosticAt, 2> EvaluationDiags;
149   Expr::EvalResult EvalResult;
150   EvalResult.Diag = &EvaluationDiags;
151   if (!SubstitutedAtomicExpr.get()->EvaluateAsRValue(EvalResult, S.Context)) {
152       // C++2a [temp.constr.atomic]p1
153       //   ...E shall be a constant expression of type bool.
154     S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(),
155            diag::err_non_constant_constraint_expression)
156         << SubstitutedAtomicExpr.get()->getSourceRange();
157     for (const PartialDiagnosticAt &PDiag : EvaluationDiags)
158       S.Diag(PDiag.first, PDiag.second);
159     return true;
160   }
161 
162   Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();
163   if (!Satisfaction.IsSatisfied)
164     Satisfaction.Details.emplace_back(ConstraintExpr,
165                                       SubstitutedAtomicExpr.get());
166 
167   return false;
168 }
169 
170 template <typename TemplateDeclT>
171 static bool calculateConstraintSatisfaction(
172     Sema &S, TemplateDeclT *Template, ArrayRef<TemplateArgument> TemplateArgs,
173     SourceLocation TemplateNameLoc, MultiLevelTemplateArgumentList &MLTAL,
174     const Expr *ConstraintExpr, ConstraintSatisfaction &Satisfaction) {
175   return calculateConstraintSatisfaction(
176       S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) {
177         EnterExpressionEvaluationContext ConstantEvaluated(
178             S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
179 
180         // Atomic constraint - substitute arguments and check satisfaction.
181         ExprResult SubstitutedExpression;
182         {
183           TemplateDeductionInfo Info(TemplateNameLoc);
184           Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(),
185               Sema::InstantiatingTemplate::ConstraintSubstitution{}, Template,
186               Info, AtomicExpr->getSourceRange());
187           if (Inst.isInvalid())
188             return ExprError();
189           // We do not want error diagnostics escaping here.
190           Sema::SFINAETrap Trap(S);
191           SubstitutedExpression = S.SubstExpr(const_cast<Expr *>(AtomicExpr),
192                                               MLTAL);
193           if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {
194             // C++2a [temp.constr.atomic]p1
195             //   ...If substitution results in an invalid type or expression, the
196             //   constraint is not satisfied.
197             if (!Trap.hasErrorOccurred())
198               // A non-SFINAE error has occured as a result of this
199               // substitution.
200               return ExprError();
201 
202             PartialDiagnosticAt SubstDiag{SourceLocation(),
203                                           PartialDiagnostic::NullDiagnostic()};
204             Info.takeSFINAEDiagnostic(SubstDiag);
205             // FIXME: Concepts: This is an unfortunate consequence of there
206             //  being no serialization code for PartialDiagnostics and the fact
207             //  that serializing them would likely take a lot more storage than
208             //  just storing them as strings. We would still like, in the
209             //  future, to serialize the proper PartialDiagnostic as serializing
210             //  it as a string defeats the purpose of the diagnostic mechanism.
211             SmallString<128> DiagString;
212             DiagString = ": ";
213             SubstDiag.second.EmitToString(S.getDiagnostics(), DiagString);
214             unsigned MessageSize = DiagString.size();
215             char *Mem = new (S.Context) char[MessageSize];
216             memcpy(Mem, DiagString.c_str(), MessageSize);
217             Satisfaction.Details.emplace_back(
218                 AtomicExpr,
219                 new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
220                         SubstDiag.first, StringRef(Mem, MessageSize)});
221             Satisfaction.IsSatisfied = false;
222             return ExprEmpty();
223           }
224         }
225 
226         if (!S.CheckConstraintExpression(SubstitutedExpression.get()))
227           return ExprError();
228 
229         return SubstitutedExpression;
230       });
231 }
232 
233 template<typename TemplateDeclT>
234 static bool CheckConstraintSatisfaction(Sema &S, TemplateDeclT *Template,
235                                         ArrayRef<const Expr *> ConstraintExprs,
236                                         ArrayRef<TemplateArgument> TemplateArgs,
237                                         SourceRange TemplateIDRange,
238                                         ConstraintSatisfaction &Satisfaction) {
239   if (ConstraintExprs.empty()) {
240     Satisfaction.IsSatisfied = true;
241     return false;
242   }
243 
244   for (auto& Arg : TemplateArgs)
245     if (Arg.isInstantiationDependent()) {
246       // No need to check satisfaction for dependent constraint expressions.
247       Satisfaction.IsSatisfied = true;
248       return false;
249     }
250 
251   Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(),
252       Sema::InstantiatingTemplate::ConstraintsCheck{}, Template, TemplateArgs,
253       TemplateIDRange);
254   if (Inst.isInvalid())
255     return true;
256 
257   MultiLevelTemplateArgumentList MLTAL;
258   MLTAL.addOuterTemplateArguments(TemplateArgs);
259 
260   for (const Expr *ConstraintExpr : ConstraintExprs) {
261     if (calculateConstraintSatisfaction(S, Template, TemplateArgs,
262                                         TemplateIDRange.getBegin(), MLTAL,
263                                         ConstraintExpr, Satisfaction))
264       return true;
265     if (!Satisfaction.IsSatisfied)
266       // [temp.constr.op] p2
267       //   [...] To determine if a conjunction is satisfied, the satisfaction
268       //   of the first operand is checked. If that is not satisfied, the
269       //   conjunction is not satisfied. [...]
270       return false;
271   }
272   return false;
273 }
274 
275 bool Sema::CheckConstraintSatisfaction(
276     NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
277     ArrayRef<TemplateArgument> TemplateArgs, SourceRange TemplateIDRange,
278     ConstraintSatisfaction &OutSatisfaction) {
279   if (ConstraintExprs.empty()) {
280     OutSatisfaction.IsSatisfied = true;
281     return false;
282   }
283 
284   llvm::FoldingSetNodeID ID;
285   void *InsertPos;
286   ConstraintSatisfaction *Satisfaction = nullptr;
287   if (LangOpts.ConceptSatisfactionCaching) {
288     ConstraintSatisfaction::Profile(ID, Context, Template, TemplateArgs);
289     Satisfaction = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos);
290     if (Satisfaction) {
291       OutSatisfaction = *Satisfaction;
292       return false;
293     }
294     Satisfaction = new ConstraintSatisfaction(Template, TemplateArgs);
295   } else {
296     Satisfaction = &OutSatisfaction;
297   }
298   bool Failed;
299   if (auto *T = dyn_cast<TemplateDecl>(Template))
300     Failed = ::CheckConstraintSatisfaction(*this, T, ConstraintExprs,
301                                            TemplateArgs, TemplateIDRange,
302                                            *Satisfaction);
303   else if (auto *P =
304                dyn_cast<ClassTemplatePartialSpecializationDecl>(Template))
305     Failed = ::CheckConstraintSatisfaction(*this, P, ConstraintExprs,
306                                            TemplateArgs, TemplateIDRange,
307                                            *Satisfaction);
308   else
309     Failed = ::CheckConstraintSatisfaction(
310         *this, cast<VarTemplatePartialSpecializationDecl>(Template),
311         ConstraintExprs, TemplateArgs, TemplateIDRange, *Satisfaction);
312   if (Failed) {
313     if (LangOpts.ConceptSatisfactionCaching)
314       delete Satisfaction;
315     return true;
316   }
317 
318   if (LangOpts.ConceptSatisfactionCaching) {
319     // We cannot use InsertNode here because CheckConstraintSatisfaction might
320     // have invalidated it.
321     SatisfactionCache.InsertNode(Satisfaction);
322     OutSatisfaction = *Satisfaction;
323   }
324   return false;
325 }
326 
327 bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
328                                        ConstraintSatisfaction &Satisfaction) {
329   return calculateConstraintSatisfaction(
330       *this, ConstraintExpr, Satisfaction,
331       [](const Expr *AtomicExpr) -> ExprResult {
332         return ExprResult(const_cast<Expr *>(AtomicExpr));
333       });
334 }
335 
336 bool Sema::EnsureTemplateArgumentListConstraints(
337     TemplateDecl *TD, ArrayRef<TemplateArgument> TemplateArgs,
338     SourceRange TemplateIDRange) {
339   ConstraintSatisfaction Satisfaction;
340   llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
341   TD->getAssociatedConstraints(AssociatedConstraints);
342   if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgs,
343                                   TemplateIDRange, Satisfaction))
344     return true;
345 
346   if (!Satisfaction.IsSatisfied) {
347     SmallString<128> TemplateArgString;
348     TemplateArgString = " ";
349     TemplateArgString += getTemplateArgumentBindingsText(
350         TD->getTemplateParameters(), TemplateArgs.data(), TemplateArgs.size());
351 
352     Diag(TemplateIDRange.getBegin(),
353          diag::err_template_arg_list_constraints_not_satisfied)
354         << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD
355         << TemplateArgString << TemplateIDRange;
356     DiagnoseUnsatisfiedConstraint(Satisfaction);
357     return true;
358   }
359   return false;
360 }
361 
362 static void diagnoseUnsatisfiedRequirement(Sema &S,
363                                            concepts::ExprRequirement *Req,
364                                            bool First) {
365   assert(!Req->isSatisfied()
366          && "Diagnose() can only be used on an unsatisfied requirement");
367   switch (Req->getSatisfactionStatus()) {
368     case concepts::ExprRequirement::SS_Dependent:
369       llvm_unreachable("Diagnosing a dependent requirement");
370       break;
371     case concepts::ExprRequirement::SS_ExprSubstitutionFailure: {
372       auto *SubstDiag = Req->getExprSubstitutionDiagnostic();
373       if (!SubstDiag->DiagMessage.empty())
374         S.Diag(SubstDiag->DiagLoc,
375                diag::note_expr_requirement_expr_substitution_error)
376                << (int)First << SubstDiag->SubstitutedEntity
377                << SubstDiag->DiagMessage;
378       else
379         S.Diag(SubstDiag->DiagLoc,
380                diag::note_expr_requirement_expr_unknown_substitution_error)
381             << (int)First << SubstDiag->SubstitutedEntity;
382       break;
383     }
384     case concepts::ExprRequirement::SS_NoexceptNotMet:
385       S.Diag(Req->getNoexceptLoc(),
386              diag::note_expr_requirement_noexcept_not_met)
387           << (int)First << Req->getExpr();
388       break;
389     case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {
390       auto *SubstDiag =
391           Req->getReturnTypeRequirement().getSubstitutionDiagnostic();
392       if (!SubstDiag->DiagMessage.empty())
393         S.Diag(SubstDiag->DiagLoc,
394                diag::note_expr_requirement_type_requirement_substitution_error)
395             << (int)First << SubstDiag->SubstitutedEntity
396             << SubstDiag->DiagMessage;
397       else
398         S.Diag(SubstDiag->DiagLoc,
399                diag::note_expr_requirement_type_requirement_unknown_substitution_error)
400             << (int)First << SubstDiag->SubstitutedEntity;
401       break;
402     }
403     case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: {
404       ConceptSpecializationExpr *ConstraintExpr =
405           Req->getReturnTypeRequirementSubstitutedConstraintExpr();
406       if (ConstraintExpr->getTemplateArgsAsWritten()->NumTemplateArgs == 1)
407         // A simple case - expr type is the type being constrained and the concept
408         // was not provided arguments.
409         S.Diag(ConstraintExpr->getBeginLoc(),
410                diag::note_expr_requirement_constraints_not_satisfied_simple)
411             << (int)First << S.BuildDecltypeType(Req->getExpr(),
412                                                  Req->getExpr()->getBeginLoc())
413             << ConstraintExpr->getNamedConcept();
414       else
415         S.Diag(ConstraintExpr->getBeginLoc(),
416                diag::note_expr_requirement_constraints_not_satisfied)
417             << (int)First << ConstraintExpr;
418       S.DiagnoseUnsatisfiedConstraint(ConstraintExpr->getSatisfaction());
419       break;
420     }
421     case concepts::ExprRequirement::SS_Satisfied:
422       llvm_unreachable("We checked this above");
423   }
424 }
425 
426 static void diagnoseUnsatisfiedRequirement(Sema &S,
427                                            concepts::TypeRequirement *Req,
428                                            bool First) {
429   assert(!Req->isSatisfied()
430          && "Diagnose() can only be used on an unsatisfied requirement");
431   switch (Req->getSatisfactionStatus()) {
432   case concepts::TypeRequirement::SS_Dependent:
433     llvm_unreachable("Diagnosing a dependent requirement");
434     return;
435   case concepts::TypeRequirement::SS_SubstitutionFailure: {
436     auto *SubstDiag = Req->getSubstitutionDiagnostic();
437     if (!SubstDiag->DiagMessage.empty())
438       S.Diag(SubstDiag->DiagLoc,
439              diag::note_type_requirement_substitution_error) << (int)First
440           << SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage;
441     else
442       S.Diag(SubstDiag->DiagLoc,
443              diag::note_type_requirement_unknown_substitution_error)
444           << (int)First << SubstDiag->SubstitutedEntity;
445     return;
446   }
447   default:
448     llvm_unreachable("Unknown satisfaction status");
449     return;
450   }
451 }
452 
453 static void diagnoseUnsatisfiedRequirement(Sema &S,
454                                            concepts::NestedRequirement *Req,
455                                            bool First) {
456   if (Req->isSubstitutionFailure()) {
457     concepts::Requirement::SubstitutionDiagnostic *SubstDiag =
458         Req->getSubstitutionDiagnostic();
459     if (!SubstDiag->DiagMessage.empty())
460       S.Diag(SubstDiag->DiagLoc,
461              diag::note_nested_requirement_substitution_error)
462              << (int)First << SubstDiag->SubstitutedEntity
463              << SubstDiag->DiagMessage;
464     else
465       S.Diag(SubstDiag->DiagLoc,
466              diag::note_nested_requirement_unknown_substitution_error)
467           << (int)First << SubstDiag->SubstitutedEntity;
468     return;
469   }
470   S.DiagnoseUnsatisfiedConstraint(Req->getConstraintSatisfaction(), First);
471 }
472 
473 
474 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
475                                                         Expr *SubstExpr,
476                                                         bool First = true) {
477   SubstExpr = SubstExpr->IgnoreParenImpCasts();
478   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) {
479     switch (BO->getOpcode()) {
480     // These two cases will in practice only be reached when using fold
481     // expressions with || and &&, since otherwise the || and && will have been
482     // broken down into atomic constraints during satisfaction checking.
483     case BO_LOr:
484       // Or evaluated to false - meaning both RHS and LHS evaluated to false.
485       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
486       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
487                                                   /*First=*/false);
488       return;
489     case BO_LAnd:
490       bool LHSSatisfied;
491       BO->getLHS()->EvaluateAsBooleanCondition(LHSSatisfied, S.Context);
492       if (LHSSatisfied) {
493         // LHS is true, so RHS must be false.
494         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First);
495         return;
496       }
497       // LHS is false
498       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
499 
500       // RHS might also be false
501       bool RHSSatisfied;
502       BO->getRHS()->EvaluateAsBooleanCondition(RHSSatisfied, S.Context);
503       if (!RHSSatisfied)
504         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
505                                                     /*First=*/false);
506       return;
507     case BO_GE:
508     case BO_LE:
509     case BO_GT:
510     case BO_LT:
511     case BO_EQ:
512     case BO_NE:
513       if (BO->getLHS()->getType()->isIntegerType() &&
514           BO->getRHS()->getType()->isIntegerType()) {
515         Expr::EvalResult SimplifiedLHS;
516         Expr::EvalResult SimplifiedRHS;
517         BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context);
518         BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context);
519         if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) {
520           S.Diag(SubstExpr->getBeginLoc(),
521                  diag::note_atomic_constraint_evaluated_to_false_elaborated)
522               << (int)First << SubstExpr
523               << SimplifiedLHS.Val.getInt().toString(10)
524               << BinaryOperator::getOpcodeStr(BO->getOpcode())
525               << SimplifiedRHS.Val.getInt().toString(10);
526           return;
527         }
528       }
529       break;
530 
531     default:
532       break;
533     }
534   } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) {
535     if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
536       S.Diag(
537           CSE->getSourceRange().getBegin(),
538           diag::
539           note_single_arg_concept_specialization_constraint_evaluated_to_false)
540           << (int)First
541           << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument()
542           << CSE->getNamedConcept();
543     } else {
544       S.Diag(SubstExpr->getSourceRange().getBegin(),
545              diag::note_concept_specialization_constraint_evaluated_to_false)
546           << (int)First << CSE;
547     }
548     S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction());
549     return;
550   } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) {
551     for (concepts::Requirement *Req : RE->getRequirements())
552       if (!Req->isDependent() && !Req->isSatisfied()) {
553         if (auto *E = dyn_cast<concepts::ExprRequirement>(Req))
554           diagnoseUnsatisfiedRequirement(S, E, First);
555         else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req))
556           diagnoseUnsatisfiedRequirement(S, T, First);
557         else
558           diagnoseUnsatisfiedRequirement(
559               S, cast<concepts::NestedRequirement>(Req), First);
560         break;
561       }
562     return;
563   }
564 
565   S.Diag(SubstExpr->getSourceRange().getBegin(),
566          diag::note_atomic_constraint_evaluated_to_false)
567       << (int)First << SubstExpr;
568 }
569 
570 template<typename SubstitutionDiagnostic>
571 static void diagnoseUnsatisfiedConstraintExpr(
572     Sema &S, const Expr *E,
573     const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record,
574     bool First = true) {
575   if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){
576     S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)
577         << Diag->second;
578     return;
579   }
580 
581   diagnoseWellFormedUnsatisfiedConstraintExpr(S,
582       Record.template get<Expr *>(), First);
583 }
584 
585 void
586 Sema::DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction& Satisfaction,
587                                     bool First) {
588   assert(!Satisfaction.IsSatisfied &&
589          "Attempted to diagnose a satisfied constraint");
590   for (auto &Pair : Satisfaction.Details) {
591     diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
592     First = false;
593   }
594 }
595 
596 void Sema::DiagnoseUnsatisfiedConstraint(
597     const ASTConstraintSatisfaction &Satisfaction,
598     bool First) {
599   assert(!Satisfaction.IsSatisfied &&
600          "Attempted to diagnose a satisfied constraint");
601   for (auto &Pair : Satisfaction) {
602     diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
603     First = false;
604   }
605 }
606 
607 const NormalizedConstraint *
608 Sema::getNormalizedAssociatedConstraints(
609     NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) {
610   auto CacheEntry = NormalizationCache.find(ConstrainedDecl);
611   if (CacheEntry == NormalizationCache.end()) {
612     auto Normalized =
613         NormalizedConstraint::fromConstraintExprs(*this, ConstrainedDecl,
614                                                   AssociatedConstraints);
615     CacheEntry =
616         NormalizationCache
617             .try_emplace(ConstrainedDecl,
618                          Normalized
619                              ? new (Context) NormalizedConstraint(
620                                  std::move(*Normalized))
621                              : nullptr)
622             .first;
623   }
624   return CacheEntry->second;
625 }
626 
627 static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
628     ConceptDecl *Concept, ArrayRef<TemplateArgument> TemplateArgs,
629     const ASTTemplateArgumentListInfo *ArgsAsWritten) {
630   if (!N.isAtomic()) {
631     if (substituteParameterMappings(S, N.getLHS(), Concept, TemplateArgs,
632                                     ArgsAsWritten))
633       return true;
634     return substituteParameterMappings(S, N.getRHS(), Concept, TemplateArgs,
635                                        ArgsAsWritten);
636   }
637   TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
638 
639   AtomicConstraint &Atomic = *N.getAtomicConstraint();
640   TemplateArgumentListInfo SubstArgs;
641   MultiLevelTemplateArgumentList MLTAL;
642   MLTAL.addOuterTemplateArguments(TemplateArgs);
643   if (!Atomic.ParameterMapping) {
644     llvm::SmallBitVector OccurringIndices(TemplateParams->size());
645     S.MarkUsedTemplateParameters(Atomic.ConstraintExpr, /*OnlyDeduced=*/false,
646                                  /*Depth=*/0, OccurringIndices);
647     Atomic.ParameterMapping.emplace(
648         MutableArrayRef<TemplateArgumentLoc>(
649             new (S.Context) TemplateArgumentLoc[OccurringIndices.count()],
650             OccurringIndices.count()));
651     for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I)
652       if (OccurringIndices[I])
653         new (&(*Atomic.ParameterMapping)[J++]) TemplateArgumentLoc(
654             S.getIdentityTemplateArgumentLoc(TemplateParams->begin()[I],
655                 // Here we assume we do not support things like
656                 // template<typename A, typename B>
657                 // concept C = ...;
658                 //
659                 // template<typename... Ts> requires C<Ts...>
660                 // struct S { };
661                 // The above currently yields a diagnostic.
662                 // We still might have default arguments for concept parameters.
663                 ArgsAsWritten->NumTemplateArgs > I ?
664                 ArgsAsWritten->arguments()[I].getLocation() :
665                 SourceLocation()));
666   }
667   Sema::InstantiatingTemplate Inst(
668       S, ArgsAsWritten->arguments().front().getSourceRange().getBegin(),
669       Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, Concept,
670       SourceRange(ArgsAsWritten->arguments()[0].getSourceRange().getBegin(),
671                   ArgsAsWritten->arguments().back().getSourceRange().getEnd()));
672   if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs))
673     return true;
674   std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(),
675             N.getAtomicConstraint()->ParameterMapping->begin());
676   return false;
677 }
678 
679 Optional<NormalizedConstraint>
680 NormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D,
681                                           ArrayRef<const Expr *> E) {
682   assert(E.size() != 0);
683   auto First = fromConstraintExpr(S, D, E[0]);
684   if (E.size() == 1)
685     return First;
686   auto Second = fromConstraintExpr(S, D, E[1]);
687   if (!Second)
688     return None;
689   llvm::Optional<NormalizedConstraint> Conjunction;
690   Conjunction.emplace(S.Context, std::move(*First), std::move(*Second),
691                       CCK_Conjunction);
692   for (unsigned I = 2; I < E.size(); ++I) {
693     auto Next = fromConstraintExpr(S, D, E[I]);
694     if (!Next)
695       return llvm::Optional<NormalizedConstraint>{};
696     NormalizedConstraint NewConjunction(S.Context, std::move(*Conjunction),
697                                         std::move(*Next), CCK_Conjunction);
698     *Conjunction = std::move(NewConjunction);
699   }
700   return Conjunction;
701 }
702 
703 llvm::Optional<NormalizedConstraint>
704 NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
705   assert(E != nullptr);
706 
707   // C++ [temp.constr.normal]p1.1
708   // [...]
709   // - The normal form of an expression (E) is the normal form of E.
710   // [...]
711   E = E->IgnoreParenImpCasts();
712   if (auto *BO = dyn_cast<const BinaryOperator>(E)) {
713     if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) {
714       auto LHS = fromConstraintExpr(S, D, BO->getLHS());
715       if (!LHS)
716         return None;
717       auto RHS = fromConstraintExpr(S, D, BO->getRHS());
718       if (!RHS)
719         return None;
720 
721       return NormalizedConstraint(
722           S.Context, std::move(*LHS), std::move(*RHS),
723           BO->getOpcode() == BO_LAnd ? CCK_Conjunction : CCK_Disjunction);
724     }
725   } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) {
726     const NormalizedConstraint *SubNF;
727     {
728       Sema::InstantiatingTemplate Inst(
729           S, CSE->getExprLoc(),
730           Sema::InstantiatingTemplate::ConstraintNormalization{}, D,
731           CSE->getSourceRange());
732       // C++ [temp.constr.normal]p1.1
733       // [...]
734       // The normal form of an id-expression of the form C<A1, A2, ..., AN>,
735       // where C names a concept, is the normal form of the
736       // constraint-expression of C, after substituting A1, A2, ..., AN for C’s
737       // respective template parameters in the parameter mappings in each atomic
738       // constraint. If any such substitution results in an invalid type or
739       // expression, the program is ill-formed; no diagnostic is required.
740       // [...]
741       ConceptDecl *CD = CSE->getNamedConcept();
742       SubNF = S.getNormalizedAssociatedConstraints(CD,
743                                                    {CD->getConstraintExpr()});
744       if (!SubNF)
745         return None;
746     }
747 
748     Optional<NormalizedConstraint> New;
749     New.emplace(S.Context, *SubNF);
750 
751     if (substituteParameterMappings(
752             S, *New, CSE->getNamedConcept(),
753             CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten()))
754       return None;
755 
756     return New;
757   }
758   return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)};
759 }
760 
761 using NormalForm =
762     llvm::SmallVector<llvm::SmallVector<AtomicConstraint *, 2>, 4>;
763 
764 static NormalForm makeCNF(const NormalizedConstraint &Normalized) {
765   if (Normalized.isAtomic())
766     return {{Normalized.getAtomicConstraint()}};
767 
768   NormalForm LCNF = makeCNF(Normalized.getLHS());
769   NormalForm RCNF = makeCNF(Normalized.getRHS());
770   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) {
771     LCNF.reserve(LCNF.size() + RCNF.size());
772     while (!RCNF.empty())
773       LCNF.push_back(RCNF.pop_back_val());
774     return LCNF;
775   }
776 
777   // Disjunction
778   NormalForm Res;
779   Res.reserve(LCNF.size() * RCNF.size());
780   for (auto &LDisjunction : LCNF)
781     for (auto &RDisjunction : RCNF) {
782       NormalForm::value_type Combined;
783       Combined.reserve(LDisjunction.size() + RDisjunction.size());
784       std::copy(LDisjunction.begin(), LDisjunction.end(),
785                 std::back_inserter(Combined));
786       std::copy(RDisjunction.begin(), RDisjunction.end(),
787                 std::back_inserter(Combined));
788       Res.emplace_back(Combined);
789     }
790   return Res;
791 }
792 
793 static NormalForm makeDNF(const NormalizedConstraint &Normalized) {
794   if (Normalized.isAtomic())
795     return {{Normalized.getAtomicConstraint()}};
796 
797   NormalForm LDNF = makeDNF(Normalized.getLHS());
798   NormalForm RDNF = makeDNF(Normalized.getRHS());
799   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) {
800     LDNF.reserve(LDNF.size() + RDNF.size());
801     while (!RDNF.empty())
802       LDNF.push_back(RDNF.pop_back_val());
803     return LDNF;
804   }
805 
806   // Conjunction
807   NormalForm Res;
808   Res.reserve(LDNF.size() * RDNF.size());
809   for (auto &LConjunction : LDNF) {
810     for (auto &RConjunction : RDNF) {
811       NormalForm::value_type Combined;
812       Combined.reserve(LConjunction.size() + RConjunction.size());
813       std::copy(LConjunction.begin(), LConjunction.end(),
814                 std::back_inserter(Combined));
815       std::copy(RConjunction.begin(), RConjunction.end(),
816                 std::back_inserter(Combined));
817       Res.emplace_back(Combined);
818     }
819   }
820   return Res;
821 }
822 
823 template<typename AtomicSubsumptionEvaluator>
824 static bool subsumes(NormalForm PDNF, NormalForm QCNF,
825                      AtomicSubsumptionEvaluator E) {
826   // C++ [temp.constr.order] p2
827   //   Then, P subsumes Q if and only if, for every disjunctive clause Pi in the
828   //   disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in
829   //   the conjuctive normal form of Q, where [...]
830   for (const auto &Pi : PDNF) {
831     for (const auto &Qj : QCNF) {
832       // C++ [temp.constr.order] p2
833       //   - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
834       //     and only if there exists an atomic constraint Pia in Pi for which
835       //     there exists an atomic constraint, Qjb, in Qj such that Pia
836       //     subsumes Qjb.
837       bool Found = false;
838       for (const AtomicConstraint *Pia : Pi) {
839         for (const AtomicConstraint *Qjb : Qj) {
840           if (E(*Pia, *Qjb)) {
841             Found = true;
842             break;
843           }
844         }
845         if (Found)
846           break;
847       }
848       if (!Found)
849         return false;
850     }
851   }
852   return true;
853 }
854 
855 template<typename AtomicSubsumptionEvaluator>
856 static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P,
857                      NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes,
858                      AtomicSubsumptionEvaluator E) {
859   // C++ [temp.constr.order] p2
860   //   In order to determine if a constraint P subsumes a constraint Q, P is
861   //   transformed into disjunctive normal form, and Q is transformed into
862   //   conjunctive normal form. [...]
863   auto *PNormalized = S.getNormalizedAssociatedConstraints(DP, P);
864   if (!PNormalized)
865     return true;
866   const NormalForm PDNF = makeDNF(*PNormalized);
867 
868   auto *QNormalized = S.getNormalizedAssociatedConstraints(DQ, Q);
869   if (!QNormalized)
870     return true;
871   const NormalForm QCNF = makeCNF(*QNormalized);
872 
873   Subsumes = subsumes(PDNF, QCNF, E);
874   return false;
875 }
876 
877 bool Sema::IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef<const Expr *> AC1,
878                                   NamedDecl *D2, ArrayRef<const Expr *> AC2,
879                                   bool &Result) {
880   if (AC1.empty()) {
881     Result = AC2.empty();
882     return false;
883   }
884   if (AC2.empty()) {
885     // TD1 has associated constraints and TD2 does not.
886     Result = true;
887     return false;
888   }
889 
890   std::pair<NamedDecl *, NamedDecl *> Key{D1, D2};
891   auto CacheEntry = SubsumptionCache.find(Key);
892   if (CacheEntry != SubsumptionCache.end()) {
893     Result = CacheEntry->second;
894     return false;
895   }
896 
897   if (subsumes(*this, D1, AC1, D2, AC2, Result,
898         [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
899           return A.subsumes(Context, B);
900         }))
901     return true;
902   SubsumptionCache.try_emplace(Key, Result);
903   return false;
904 }
905 
906 bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
907     ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) {
908   if (isSFINAEContext())
909     // No need to work here because our notes would be discarded.
910     return false;
911 
912   if (AC1.empty() || AC2.empty())
913     return false;
914 
915   auto NormalExprEvaluator =
916       [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
917         return A.subsumes(Context, B);
918       };
919 
920   const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;
921   auto IdenticalExprEvaluator =
922       [&] (const AtomicConstraint &A, const AtomicConstraint &B) {
923         if (!A.hasMatchingParameterMapping(Context, B))
924           return false;
925         const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr;
926         if (EA == EB)
927           return true;
928 
929         // Not the same source level expression - are the expressions
930         // identical?
931         llvm::FoldingSetNodeID IDA, IDB;
932         EA->Profile(IDA, Context, /*Cannonical=*/true);
933         EB->Profile(IDB, Context, /*Cannonical=*/true);
934         if (IDA != IDB)
935           return false;
936 
937         AmbiguousAtomic1 = EA;
938         AmbiguousAtomic2 = EB;
939         return true;
940       };
941 
942   {
943     // The subsumption checks might cause diagnostics
944     SFINAETrap Trap(*this);
945     auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1);
946     if (!Normalized1)
947       return false;
948     const NormalForm DNF1 = makeDNF(*Normalized1);
949     const NormalForm CNF1 = makeCNF(*Normalized1);
950 
951     auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2);
952     if (!Normalized2)
953       return false;
954     const NormalForm DNF2 = makeDNF(*Normalized2);
955     const NormalForm CNF2 = makeCNF(*Normalized2);
956 
957     bool Is1AtLeastAs2Normally = subsumes(DNF1, CNF2, NormalExprEvaluator);
958     bool Is2AtLeastAs1Normally = subsumes(DNF2, CNF1, NormalExprEvaluator);
959     bool Is1AtLeastAs2 = subsumes(DNF1, CNF2, IdenticalExprEvaluator);
960     bool Is2AtLeastAs1 = subsumes(DNF2, CNF1, IdenticalExprEvaluator);
961     if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
962         Is2AtLeastAs1 == Is2AtLeastAs1Normally)
963       // Same result - no ambiguity was caused by identical atomic expressions.
964       return false;
965   }
966 
967   // A different result! Some ambiguous atomic constraint(s) caused a difference
968   assert(AmbiguousAtomic1 && AmbiguousAtomic2);
969 
970   Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints)
971       << AmbiguousAtomic1->getSourceRange();
972   Diag(AmbiguousAtomic2->getBeginLoc(),
973        diag::note_ambiguous_atomic_constraints_similar_expression)
974       << AmbiguousAtomic2->getSourceRange();
975   return true;
976 }
977 
978 concepts::ExprRequirement::ExprRequirement(
979     Expr *E, bool IsSimple, SourceLocation NoexceptLoc,
980     ReturnTypeRequirement Req, SatisfactionStatus Status,
981     ConceptSpecializationExpr *SubstitutedConstraintExpr) :
982     Requirement(IsSimple ? RK_Simple : RK_Compound, Status == SS_Dependent,
983                 Status == SS_Dependent &&
984                 (E->containsUnexpandedParameterPack() ||
985                  Req.containsUnexpandedParameterPack()),
986                 Status == SS_Satisfied), Value(E), NoexceptLoc(NoexceptLoc),
987     TypeReq(Req), SubstitutedConstraintExpr(SubstitutedConstraintExpr),
988     Status(Status) {
989   assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
990          "Simple requirement must not have a return type requirement or a "
991          "noexcept specification");
992   assert((Status > SS_TypeRequirementSubstitutionFailure && Req.isTypeConstraint()) ==
993          (SubstitutedConstraintExpr != nullptr));
994 }
995 
996 concepts::ExprRequirement::ExprRequirement(
997     SubstitutionDiagnostic *ExprSubstDiag, bool IsSimple,
998     SourceLocation NoexceptLoc, ReturnTypeRequirement Req) :
999     Requirement(IsSimple ? RK_Simple : RK_Compound, Req.isDependent(),
1000                 Req.containsUnexpandedParameterPack(), /*IsSatisfied=*/false),
1001     Value(ExprSubstDiag), NoexceptLoc(NoexceptLoc), TypeReq(Req),
1002     Status(SS_ExprSubstitutionFailure) {
1003   assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1004          "Simple requirement must not have a return type requirement or a "
1005          "noexcept specification");
1006 }
1007 
1008 concepts::ExprRequirement::ReturnTypeRequirement::
1009 ReturnTypeRequirement(TemplateParameterList *TPL) :
1010     TypeConstraintInfo(TPL, 0) {
1011   assert(TPL->size() == 1);
1012   const TypeConstraint *TC =
1013       cast<TemplateTypeParmDecl>(TPL->getParam(0))->getTypeConstraint();
1014   assert(TC &&
1015          "TPL must have a template type parameter with a type constraint");
1016   auto *Constraint =
1017       cast_or_null<ConceptSpecializationExpr>(
1018           TC->getImmediatelyDeclaredConstraint());
1019   bool Dependent = false;
1020   if (Constraint->getTemplateArgsAsWritten()) {
1021     for (auto &ArgLoc :
1022          Constraint->getTemplateArgsAsWritten()->arguments().drop_front(1)) {
1023       if (ArgLoc.getArgument().isDependent()) {
1024         Dependent = true;
1025         break;
1026       }
1027     }
1028   }
1029   TypeConstraintInfo.setInt(Dependent ? 1 : 0);
1030 }
1031 
1032 concepts::TypeRequirement::TypeRequirement(TypeSourceInfo *T) :
1033     Requirement(RK_Type, T->getType()->isDependentType(),
1034                 T->getType()->containsUnexpandedParameterPack(),
1035                 // We reach this ctor with either dependent types (in which
1036                 // IsSatisfied doesn't matter) or with non-dependent type in
1037                 // which the existence of the type indicates satisfaction.
1038                 /*IsSatisfied=*/true
1039                 ), Value(T),
1040     Status(T->getType()->isDependentType() ? SS_Dependent : SS_Satisfied) {}
1041