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 namespace {
32 class LogicalBinOp {
33   OverloadedOperatorKind Op = OO_None;
34   const Expr *LHS = nullptr;
35   const Expr *RHS = nullptr;
36 
37 public:
38   LogicalBinOp(const Expr *E) {
39     if (auto *BO = dyn_cast<BinaryOperator>(E)) {
40       Op = BinaryOperator::getOverloadedOperator(BO->getOpcode());
41       LHS = BO->getLHS();
42       RHS = BO->getRHS();
43     } else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(E)) {
44       Op = OO->getOperator();
45       LHS = OO->getArg(0);
46       RHS = OO->getArg(1);
47     }
48   }
49 
50   bool isAnd() const { return Op == OO_AmpAmp; }
51   bool isOr() const { return Op == OO_PipePipe; }
52   explicit operator bool() const { return isAnd() || isOr(); }
53 
54   const Expr *getLHS() const { return LHS; }
55   const Expr *getRHS() const { return RHS; }
56 };
57 }
58 
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.
64 
65   ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts();
66 
67   if (LogicalBinOp BO = ConstraintExpression) {
68     return CheckConstraintExpression(BO.getLHS(), NextToken,
69                                      PossibleNonPrimary) &&
70            CheckConstraintExpression(BO.getRHS(), NextToken,
71                                      PossibleNonPrimary);
72   } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression))
73     return CheckConstraintExpression(C->getSubExpr(), NextToken,
74                                      PossibleNonPrimary);
75 
76   QualType Type = ConstraintExpression->getType();
77 
78   auto CheckForNonPrimary = [&] {
79     if (PossibleNonPrimary)
80       *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;
100   };
101 
102   // An atomic constraint!
103   if (ConstraintExpression->isTypeDependent()) {
104     CheckForNonPrimary();
105     return true;
106   }
107 
108   if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) {
109     Diag(ConstraintExpression->getExprLoc(),
110          diag::err_non_bool_atomic_constraint) << Type
111         << ConstraintExpression->getSourceRange();
112     CheckForNonPrimary();
113     return false;
114   }
115 
116   if (PossibleNonPrimary)
117       *PossibleNonPrimary = false;
118   return true;
119 }
120 
121 template <typename AtomicEvaluator>
122 static bool
123 calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
124                                 ConstraintSatisfaction &Satisfaction,
125                                 AtomicEvaluator &&Evaluator) {
126   ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
127 
128   if (LogicalBinOp BO = ConstraintExpr) {
129     if (calculateConstraintSatisfaction(S, BO.getLHS(), Satisfaction,
130                                         Evaluator))
131       return true;
132 
133     bool IsLHSSatisfied = Satisfaction.IsSatisfied;
134 
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.
142       return false;
143 
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.
151       return false;
152 
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));
158   }
159 
160   // An atomic constraint expression
161   ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr);
162 
163   if (SubstitutedAtomicExpr.isInvalid())
164     return true;
165 
166   if (!SubstitutedAtomicExpr.isUsable())
167     // Evaluator has decided satisfaction without yielding an expression.
168     return false;
169 
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);
183     return true;
184   }
185 
186   Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();
187   if (!Satisfaction.IsSatisfied)
188     Satisfaction.Details.emplace_back(ConstraintExpr,
189                                       SubstitutedAtomicExpr.get());
190 
191   return false;
192 }
193 
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);
202 
203         // Atomic constraint - substitute arguments and check satisfaction.
204         ExprResult SubstitutedExpression;
205         {
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())
212             return ExprError();
213           // We do not want error diagnostics escaping here.
214           Sema::SFINAETrap Trap(S);
215           SubstitutedExpression = S.SubstExpr(const_cast<Expr *>(AtomicExpr),
216                                               MLTAL);
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
223               // substitution.
224               return ExprError();
225 
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;
236             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(
242                 AtomicExpr,
243                 new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
244                         SubstDiag.first, StringRef(Mem, MessageSize)});
245             Satisfaction.IsSatisfied = false;
246             return ExprEmpty();
247           }
248         }
249 
250         if (!S.CheckConstraintExpression(SubstitutedExpression.get()))
251           return ExprError();
252 
253         return SubstitutedExpression;
254       });
255 }
256 
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;
264     return false;
265   }
266 
267   for (auto& Arg : TemplateArgs)
268     if (Arg.isInstantiationDependent()) {
269       // No need to check satisfaction for dependent constraint expressions.
270       Satisfaction.IsSatisfied = true;
271       return false;
272     }
273 
274   Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(),
275       Sema::InstantiatingTemplate::ConstraintsCheck{},
276       const_cast<NamedDecl *>(Template), TemplateArgs, TemplateIDRange);
277   if (Inst.isInvalid())
278     return true;
279 
280   MultiLevelTemplateArgumentList MLTAL;
281   MLTAL.addOuterTemplateArguments(TemplateArgs);
282 
283   for (const Expr *ConstraintExpr : ConstraintExprs) {
284     if (calculateConstraintSatisfaction(S, Template, TemplateArgs,
285                                         TemplateIDRange.getBegin(), MLTAL,
286                                         ConstraintExpr, Satisfaction))
287       return true;
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. [...]
293       return false;
294   }
295   return false;
296 }
297 
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;
304     return false;
305   }
306 
307   llvm::FoldingSetNodeID ID;
308   void *InsertPos;
309   ConstraintSatisfaction *Satisfaction = nullptr;
310   bool ShouldCache = LangOpts.ConceptSatisfactionCaching && Template;
311   if (ShouldCache) {
312     ConstraintSatisfaction::Profile(ID, Context, Template, TemplateArgs);
313     Satisfaction = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos);
314     if (Satisfaction) {
315       OutSatisfaction = *Satisfaction;
316       return false;
317     }
318     Satisfaction = new ConstraintSatisfaction(Template, TemplateArgs);
319   } else {
320     Satisfaction = &OutSatisfaction;
321   }
322   if (::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
323                                     TemplateArgs, TemplateIDRange,
324                                     *Satisfaction)) {
325     if (ShouldCache)
326       delete Satisfaction;
327     return true;
328   }
329 
330   if (ShouldCache) {
331     // We cannot use InsertNode here because CheckConstraintSatisfaction might
332     // have invalidated it.
333     SatisfactionCache.InsertNode(Satisfaction);
334     OutSatisfaction = *Satisfaction;
335   }
336   return false;
337 }
338 
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));
345       });
346 }
347 
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;
354     return false;
355   }
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());
361   }
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()),
369       Satisfaction);
370 }
371 
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))
380     return true;
381 
382   if (!Satisfaction.IsSatisfied) {
383     SmallString<128> TemplateArgString;
384     TemplateArgString = " ";
385     TemplateArgString += getTemplateArgumentBindingsText(
386         TD->getTemplateParameters(), TemplateArgs.data(), TemplateArgs.size());
387 
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);
393     return true;
394   }
395   return false;
396 }
397 
398 static void diagnoseUnsatisfiedRequirement(Sema &S,
399                                            concepts::ExprRequirement *Req,
400                                            bool First) {
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");
406       break;
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;
414       else
415         S.Diag(SubstDiag->DiagLoc,
416                diag::note_expr_requirement_expr_unknown_substitution_error)
417             << (int)First << SubstDiag->SubstitutedEntity;
418       break;
419     }
420     case concepts::ExprRequirement::SS_NoexceptNotMet:
421       S.Diag(Req->getNoexceptLoc(),
422              diag::note_expr_requirement_noexcept_not_met)
423           << (int)First << Req->getExpr();
424       break;
425     case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {
426       auto *SubstDiag =
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;
433       else
434         S.Diag(SubstDiag->DiagLoc,
435                diag::note_expr_requirement_type_requirement_unknown_substitution_error)
436             << (int)First << SubstDiag->SubstitutedEntity;
437       break;
438     }
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         Expr *e = Req->getExpr();
446         S.Diag(e->getBeginLoc(),
447                diag::note_expr_requirement_constraints_not_satisfied_simple)
448             << (int)First << S.getDecltypeForParenthesizedExpr(e)
449             << ConstraintExpr->getNamedConcept();
450       } else {
451         S.Diag(ConstraintExpr->getBeginLoc(),
452                diag::note_expr_requirement_constraints_not_satisfied)
453             << (int)First << ConstraintExpr;
454       }
455       S.DiagnoseUnsatisfiedConstraint(ConstraintExpr->getSatisfaction());
456       break;
457     }
458     case concepts::ExprRequirement::SS_Satisfied:
459       llvm_unreachable("We checked this above");
460   }
461 }
462 
463 static void diagnoseUnsatisfiedRequirement(Sema &S,
464                                            concepts::TypeRequirement *Req,
465                                            bool First) {
466   assert(!Req->isSatisfied()
467          && "Diagnose() can only be used on an unsatisfied requirement");
468   switch (Req->getSatisfactionStatus()) {
469   case concepts::TypeRequirement::SS_Dependent:
470     llvm_unreachable("Diagnosing a dependent requirement");
471     return;
472   case concepts::TypeRequirement::SS_SubstitutionFailure: {
473     auto *SubstDiag = Req->getSubstitutionDiagnostic();
474     if (!SubstDiag->DiagMessage.empty())
475       S.Diag(SubstDiag->DiagLoc,
476              diag::note_type_requirement_substitution_error) << (int)First
477           << SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage;
478     else
479       S.Diag(SubstDiag->DiagLoc,
480              diag::note_type_requirement_unknown_substitution_error)
481           << (int)First << SubstDiag->SubstitutedEntity;
482     return;
483   }
484   default:
485     llvm_unreachable("Unknown satisfaction status");
486     return;
487   }
488 }
489 
490 static void diagnoseUnsatisfiedRequirement(Sema &S,
491                                            concepts::NestedRequirement *Req,
492                                            bool First) {
493   if (Req->isSubstitutionFailure()) {
494     concepts::Requirement::SubstitutionDiagnostic *SubstDiag =
495         Req->getSubstitutionDiagnostic();
496     if (!SubstDiag->DiagMessage.empty())
497       S.Diag(SubstDiag->DiagLoc,
498              diag::note_nested_requirement_substitution_error)
499              << (int)First << SubstDiag->SubstitutedEntity
500              << SubstDiag->DiagMessage;
501     else
502       S.Diag(SubstDiag->DiagLoc,
503              diag::note_nested_requirement_unknown_substitution_error)
504           << (int)First << SubstDiag->SubstitutedEntity;
505     return;
506   }
507   S.DiagnoseUnsatisfiedConstraint(Req->getConstraintSatisfaction(), First);
508 }
509 
510 
511 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
512                                                         Expr *SubstExpr,
513                                                         bool First = true) {
514   SubstExpr = SubstExpr->IgnoreParenImpCasts();
515   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) {
516     switch (BO->getOpcode()) {
517     // These two cases will in practice only be reached when using fold
518     // expressions with || and &&, since otherwise the || and && will have been
519     // broken down into atomic constraints during satisfaction checking.
520     case BO_LOr:
521       // Or evaluated to false - meaning both RHS and LHS evaluated to false.
522       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
523       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
524                                                   /*First=*/false);
525       return;
526     case BO_LAnd:
527       bool LHSSatisfied;
528       BO->getLHS()->EvaluateAsBooleanCondition(LHSSatisfied, S.Context);
529       if (LHSSatisfied) {
530         // LHS is true, so RHS must be false.
531         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First);
532         return;
533       }
534       // LHS is false
535       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
536 
537       // RHS might also be false
538       bool RHSSatisfied;
539       BO->getRHS()->EvaluateAsBooleanCondition(RHSSatisfied, S.Context);
540       if (!RHSSatisfied)
541         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
542                                                     /*First=*/false);
543       return;
544     case BO_GE:
545     case BO_LE:
546     case BO_GT:
547     case BO_LT:
548     case BO_EQ:
549     case BO_NE:
550       if (BO->getLHS()->getType()->isIntegerType() &&
551           BO->getRHS()->getType()->isIntegerType()) {
552         Expr::EvalResult SimplifiedLHS;
553         Expr::EvalResult SimplifiedRHS;
554         BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context);
555         BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context);
556         if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) {
557           S.Diag(SubstExpr->getBeginLoc(),
558                  diag::note_atomic_constraint_evaluated_to_false_elaborated)
559               << (int)First << SubstExpr
560               << SimplifiedLHS.Val.getInt().toString(10)
561               << BinaryOperator::getOpcodeStr(BO->getOpcode())
562               << SimplifiedRHS.Val.getInt().toString(10);
563           return;
564         }
565       }
566       break;
567 
568     default:
569       break;
570     }
571   } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) {
572     if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
573       S.Diag(
574           CSE->getSourceRange().getBegin(),
575           diag::
576           note_single_arg_concept_specialization_constraint_evaluated_to_false)
577           << (int)First
578           << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument()
579           << CSE->getNamedConcept();
580     } else {
581       S.Diag(SubstExpr->getSourceRange().getBegin(),
582              diag::note_concept_specialization_constraint_evaluated_to_false)
583           << (int)First << CSE;
584     }
585     S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction());
586     return;
587   } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) {
588     for (concepts::Requirement *Req : RE->getRequirements())
589       if (!Req->isDependent() && !Req->isSatisfied()) {
590         if (auto *E = dyn_cast<concepts::ExprRequirement>(Req))
591           diagnoseUnsatisfiedRequirement(S, E, First);
592         else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req))
593           diagnoseUnsatisfiedRequirement(S, T, First);
594         else
595           diagnoseUnsatisfiedRequirement(
596               S, cast<concepts::NestedRequirement>(Req), First);
597         break;
598       }
599     return;
600   }
601 
602   S.Diag(SubstExpr->getSourceRange().getBegin(),
603          diag::note_atomic_constraint_evaluated_to_false)
604       << (int)First << SubstExpr;
605 }
606 
607 template<typename SubstitutionDiagnostic>
608 static void diagnoseUnsatisfiedConstraintExpr(
609     Sema &S, const Expr *E,
610     const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record,
611     bool First = true) {
612   if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){
613     S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)
614         << Diag->second;
615     return;
616   }
617 
618   diagnoseWellFormedUnsatisfiedConstraintExpr(S,
619       Record.template get<Expr *>(), First);
620 }
621 
622 void
623 Sema::DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction& Satisfaction,
624                                     bool First) {
625   assert(!Satisfaction.IsSatisfied &&
626          "Attempted to diagnose a satisfied constraint");
627   for (auto &Pair : Satisfaction.Details) {
628     diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
629     First = false;
630   }
631 }
632 
633 void Sema::DiagnoseUnsatisfiedConstraint(
634     const ASTConstraintSatisfaction &Satisfaction,
635     bool First) {
636   assert(!Satisfaction.IsSatisfied &&
637          "Attempted to diagnose a satisfied constraint");
638   for (auto &Pair : Satisfaction) {
639     diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
640     First = false;
641   }
642 }
643 
644 const NormalizedConstraint *
645 Sema::getNormalizedAssociatedConstraints(
646     NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) {
647   auto CacheEntry = NormalizationCache.find(ConstrainedDecl);
648   if (CacheEntry == NormalizationCache.end()) {
649     auto Normalized =
650         NormalizedConstraint::fromConstraintExprs(*this, ConstrainedDecl,
651                                                   AssociatedConstraints);
652     CacheEntry =
653         NormalizationCache
654             .try_emplace(ConstrainedDecl,
655                          Normalized
656                              ? new (Context) NormalizedConstraint(
657                                  std::move(*Normalized))
658                              : nullptr)
659             .first;
660   }
661   return CacheEntry->second;
662 }
663 
664 static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
665     ConceptDecl *Concept, ArrayRef<TemplateArgument> TemplateArgs,
666     const ASTTemplateArgumentListInfo *ArgsAsWritten) {
667   if (!N.isAtomic()) {
668     if (substituteParameterMappings(S, N.getLHS(), Concept, TemplateArgs,
669                                     ArgsAsWritten))
670       return true;
671     return substituteParameterMappings(S, N.getRHS(), Concept, TemplateArgs,
672                                        ArgsAsWritten);
673   }
674   TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
675 
676   AtomicConstraint &Atomic = *N.getAtomicConstraint();
677   TemplateArgumentListInfo SubstArgs;
678   MultiLevelTemplateArgumentList MLTAL;
679   MLTAL.addOuterTemplateArguments(TemplateArgs);
680   if (!Atomic.ParameterMapping) {
681     llvm::SmallBitVector OccurringIndices(TemplateParams->size());
682     S.MarkUsedTemplateParameters(Atomic.ConstraintExpr, /*OnlyDeduced=*/false,
683                                  /*Depth=*/0, OccurringIndices);
684     Atomic.ParameterMapping.emplace(
685         MutableArrayRef<TemplateArgumentLoc>(
686             new (S.Context) TemplateArgumentLoc[OccurringIndices.count()],
687             OccurringIndices.count()));
688     for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I)
689       if (OccurringIndices[I])
690         new (&(*Atomic.ParameterMapping)[J++]) TemplateArgumentLoc(
691             S.getIdentityTemplateArgumentLoc(TemplateParams->begin()[I],
692                 // Here we assume we do not support things like
693                 // template<typename A, typename B>
694                 // concept C = ...;
695                 //
696                 // template<typename... Ts> requires C<Ts...>
697                 // struct S { };
698                 // The above currently yields a diagnostic.
699                 // We still might have default arguments for concept parameters.
700                 ArgsAsWritten->NumTemplateArgs > I ?
701                 ArgsAsWritten->arguments()[I].getLocation() :
702                 SourceLocation()));
703   }
704   Sema::InstantiatingTemplate Inst(
705       S, ArgsAsWritten->arguments().front().getSourceRange().getBegin(),
706       Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, Concept,
707       SourceRange(ArgsAsWritten->arguments()[0].getSourceRange().getBegin(),
708                   ArgsAsWritten->arguments().back().getSourceRange().getEnd()));
709   if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs))
710     return true;
711   Atomic.ParameterMapping.emplace(
712         MutableArrayRef<TemplateArgumentLoc>(
713             new (S.Context) TemplateArgumentLoc[SubstArgs.size()],
714             SubstArgs.size()));
715   std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(),
716             N.getAtomicConstraint()->ParameterMapping->begin());
717   return false;
718 }
719 
720 Optional<NormalizedConstraint>
721 NormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D,
722                                           ArrayRef<const Expr *> E) {
723   assert(E.size() != 0);
724   auto First = fromConstraintExpr(S, D, E[0]);
725   if (E.size() == 1)
726     return First;
727   auto Second = fromConstraintExpr(S, D, E[1]);
728   if (!Second)
729     return None;
730   llvm::Optional<NormalizedConstraint> Conjunction;
731   Conjunction.emplace(S.Context, std::move(*First), std::move(*Second),
732                       CCK_Conjunction);
733   for (unsigned I = 2; I < E.size(); ++I) {
734     auto Next = fromConstraintExpr(S, D, E[I]);
735     if (!Next)
736       return llvm::Optional<NormalizedConstraint>{};
737     NormalizedConstraint NewConjunction(S.Context, std::move(*Conjunction),
738                                         std::move(*Next), CCK_Conjunction);
739     *Conjunction = std::move(NewConjunction);
740   }
741   return Conjunction;
742 }
743 
744 llvm::Optional<NormalizedConstraint>
745 NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
746   assert(E != nullptr);
747 
748   // C++ [temp.constr.normal]p1.1
749   // [...]
750   // - The normal form of an expression (E) is the normal form of E.
751   // [...]
752   E = E->IgnoreParenImpCasts();
753   if (LogicalBinOp BO = E) {
754     auto LHS = fromConstraintExpr(S, D, BO.getLHS());
755     if (!LHS)
756       return None;
757     auto RHS = fromConstraintExpr(S, D, BO.getRHS());
758     if (!RHS)
759       return None;
760 
761     return NormalizedConstraint(S.Context, std::move(*LHS), std::move(*RHS),
762                                 BO.isAnd() ? CCK_Conjunction : CCK_Disjunction);
763   } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) {
764     const NormalizedConstraint *SubNF;
765     {
766       Sema::InstantiatingTemplate Inst(
767           S, CSE->getExprLoc(),
768           Sema::InstantiatingTemplate::ConstraintNormalization{}, D,
769           CSE->getSourceRange());
770       // C++ [temp.constr.normal]p1.1
771       // [...]
772       // The normal form of an id-expression of the form C<A1, A2, ..., AN>,
773       // where C names a concept, is the normal form of the
774       // constraint-expression of C, after substituting A1, A2, ..., AN for C’s
775       // respective template parameters in the parameter mappings in each atomic
776       // constraint. If any such substitution results in an invalid type or
777       // expression, the program is ill-formed; no diagnostic is required.
778       // [...]
779       ConceptDecl *CD = CSE->getNamedConcept();
780       SubNF = S.getNormalizedAssociatedConstraints(CD,
781                                                    {CD->getConstraintExpr()});
782       if (!SubNF)
783         return None;
784     }
785 
786     Optional<NormalizedConstraint> New;
787     New.emplace(S.Context, *SubNF);
788 
789     if (substituteParameterMappings(
790             S, *New, CSE->getNamedConcept(),
791             CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten()))
792       return None;
793 
794     return New;
795   }
796   return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)};
797 }
798 
799 using NormalForm =
800     llvm::SmallVector<llvm::SmallVector<AtomicConstraint *, 2>, 4>;
801 
802 static NormalForm makeCNF(const NormalizedConstraint &Normalized) {
803   if (Normalized.isAtomic())
804     return {{Normalized.getAtomicConstraint()}};
805 
806   NormalForm LCNF = makeCNF(Normalized.getLHS());
807   NormalForm RCNF = makeCNF(Normalized.getRHS());
808   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) {
809     LCNF.reserve(LCNF.size() + RCNF.size());
810     while (!RCNF.empty())
811       LCNF.push_back(RCNF.pop_back_val());
812     return LCNF;
813   }
814 
815   // Disjunction
816   NormalForm Res;
817   Res.reserve(LCNF.size() * RCNF.size());
818   for (auto &LDisjunction : LCNF)
819     for (auto &RDisjunction : RCNF) {
820       NormalForm::value_type Combined;
821       Combined.reserve(LDisjunction.size() + RDisjunction.size());
822       std::copy(LDisjunction.begin(), LDisjunction.end(),
823                 std::back_inserter(Combined));
824       std::copy(RDisjunction.begin(), RDisjunction.end(),
825                 std::back_inserter(Combined));
826       Res.emplace_back(Combined);
827     }
828   return Res;
829 }
830 
831 static NormalForm makeDNF(const NormalizedConstraint &Normalized) {
832   if (Normalized.isAtomic())
833     return {{Normalized.getAtomicConstraint()}};
834 
835   NormalForm LDNF = makeDNF(Normalized.getLHS());
836   NormalForm RDNF = makeDNF(Normalized.getRHS());
837   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) {
838     LDNF.reserve(LDNF.size() + RDNF.size());
839     while (!RDNF.empty())
840       LDNF.push_back(RDNF.pop_back_val());
841     return LDNF;
842   }
843 
844   // Conjunction
845   NormalForm Res;
846   Res.reserve(LDNF.size() * RDNF.size());
847   for (auto &LConjunction : LDNF) {
848     for (auto &RConjunction : RDNF) {
849       NormalForm::value_type Combined;
850       Combined.reserve(LConjunction.size() + RConjunction.size());
851       std::copy(LConjunction.begin(), LConjunction.end(),
852                 std::back_inserter(Combined));
853       std::copy(RConjunction.begin(), RConjunction.end(),
854                 std::back_inserter(Combined));
855       Res.emplace_back(Combined);
856     }
857   }
858   return Res;
859 }
860 
861 template<typename AtomicSubsumptionEvaluator>
862 static bool subsumes(NormalForm PDNF, NormalForm QCNF,
863                      AtomicSubsumptionEvaluator E) {
864   // C++ [temp.constr.order] p2
865   //   Then, P subsumes Q if and only if, for every disjunctive clause Pi in the
866   //   disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in
867   //   the conjuctive normal form of Q, where [...]
868   for (const auto &Pi : PDNF) {
869     for (const auto &Qj : QCNF) {
870       // C++ [temp.constr.order] p2
871       //   - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
872       //     and only if there exists an atomic constraint Pia in Pi for which
873       //     there exists an atomic constraint, Qjb, in Qj such that Pia
874       //     subsumes Qjb.
875       bool Found = false;
876       for (const AtomicConstraint *Pia : Pi) {
877         for (const AtomicConstraint *Qjb : Qj) {
878           if (E(*Pia, *Qjb)) {
879             Found = true;
880             break;
881           }
882         }
883         if (Found)
884           break;
885       }
886       if (!Found)
887         return false;
888     }
889   }
890   return true;
891 }
892 
893 template<typename AtomicSubsumptionEvaluator>
894 static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P,
895                      NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes,
896                      AtomicSubsumptionEvaluator E) {
897   // C++ [temp.constr.order] p2
898   //   In order to determine if a constraint P subsumes a constraint Q, P is
899   //   transformed into disjunctive normal form, and Q is transformed into
900   //   conjunctive normal form. [...]
901   auto *PNormalized = S.getNormalizedAssociatedConstraints(DP, P);
902   if (!PNormalized)
903     return true;
904   const NormalForm PDNF = makeDNF(*PNormalized);
905 
906   auto *QNormalized = S.getNormalizedAssociatedConstraints(DQ, Q);
907   if (!QNormalized)
908     return true;
909   const NormalForm QCNF = makeCNF(*QNormalized);
910 
911   Subsumes = subsumes(PDNF, QCNF, E);
912   return false;
913 }
914 
915 bool Sema::IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef<const Expr *> AC1,
916                                   NamedDecl *D2, ArrayRef<const Expr *> AC2,
917                                   bool &Result) {
918   if (AC1.empty()) {
919     Result = AC2.empty();
920     return false;
921   }
922   if (AC2.empty()) {
923     // TD1 has associated constraints and TD2 does not.
924     Result = true;
925     return false;
926   }
927 
928   std::pair<NamedDecl *, NamedDecl *> Key{D1, D2};
929   auto CacheEntry = SubsumptionCache.find(Key);
930   if (CacheEntry != SubsumptionCache.end()) {
931     Result = CacheEntry->second;
932     return false;
933   }
934 
935   if (subsumes(*this, D1, AC1, D2, AC2, Result,
936         [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
937           return A.subsumes(Context, B);
938         }))
939     return true;
940   SubsumptionCache.try_emplace(Key, Result);
941   return false;
942 }
943 
944 bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
945     ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) {
946   if (isSFINAEContext())
947     // No need to work here because our notes would be discarded.
948     return false;
949 
950   if (AC1.empty() || AC2.empty())
951     return false;
952 
953   auto NormalExprEvaluator =
954       [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
955         return A.subsumes(Context, B);
956       };
957 
958   const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;
959   auto IdenticalExprEvaluator =
960       [&] (const AtomicConstraint &A, const AtomicConstraint &B) {
961         if (!A.hasMatchingParameterMapping(Context, B))
962           return false;
963         const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr;
964         if (EA == EB)
965           return true;
966 
967         // Not the same source level expression - are the expressions
968         // identical?
969         llvm::FoldingSetNodeID IDA, IDB;
970         EA->Profile(IDA, Context, /*Cannonical=*/true);
971         EB->Profile(IDB, Context, /*Cannonical=*/true);
972         if (IDA != IDB)
973           return false;
974 
975         AmbiguousAtomic1 = EA;
976         AmbiguousAtomic2 = EB;
977         return true;
978       };
979 
980   {
981     // The subsumption checks might cause diagnostics
982     SFINAETrap Trap(*this);
983     auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1);
984     if (!Normalized1)
985       return false;
986     const NormalForm DNF1 = makeDNF(*Normalized1);
987     const NormalForm CNF1 = makeCNF(*Normalized1);
988 
989     auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2);
990     if (!Normalized2)
991       return false;
992     const NormalForm DNF2 = makeDNF(*Normalized2);
993     const NormalForm CNF2 = makeCNF(*Normalized2);
994 
995     bool Is1AtLeastAs2Normally = subsumes(DNF1, CNF2, NormalExprEvaluator);
996     bool Is2AtLeastAs1Normally = subsumes(DNF2, CNF1, NormalExprEvaluator);
997     bool Is1AtLeastAs2 = subsumes(DNF1, CNF2, IdenticalExprEvaluator);
998     bool Is2AtLeastAs1 = subsumes(DNF2, CNF1, IdenticalExprEvaluator);
999     if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
1000         Is2AtLeastAs1 == Is2AtLeastAs1Normally)
1001       // Same result - no ambiguity was caused by identical atomic expressions.
1002       return false;
1003   }
1004 
1005   // A different result! Some ambiguous atomic constraint(s) caused a difference
1006   assert(AmbiguousAtomic1 && AmbiguousAtomic2);
1007 
1008   Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints)
1009       << AmbiguousAtomic1->getSourceRange();
1010   Diag(AmbiguousAtomic2->getBeginLoc(),
1011        diag::note_ambiguous_atomic_constraints_similar_expression)
1012       << AmbiguousAtomic2->getSourceRange();
1013   return true;
1014 }
1015 
1016 concepts::ExprRequirement::ExprRequirement(
1017     Expr *E, bool IsSimple, SourceLocation NoexceptLoc,
1018     ReturnTypeRequirement Req, SatisfactionStatus Status,
1019     ConceptSpecializationExpr *SubstitutedConstraintExpr) :
1020     Requirement(IsSimple ? RK_Simple : RK_Compound, Status == SS_Dependent,
1021                 Status == SS_Dependent &&
1022                 (E->containsUnexpandedParameterPack() ||
1023                  Req.containsUnexpandedParameterPack()),
1024                 Status == SS_Satisfied), Value(E), NoexceptLoc(NoexceptLoc),
1025     TypeReq(Req), SubstitutedConstraintExpr(SubstitutedConstraintExpr),
1026     Status(Status) {
1027   assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1028          "Simple requirement must not have a return type requirement or a "
1029          "noexcept specification");
1030   assert((Status > SS_TypeRequirementSubstitutionFailure && Req.isTypeConstraint()) ==
1031          (SubstitutedConstraintExpr != nullptr));
1032 }
1033 
1034 concepts::ExprRequirement::ExprRequirement(
1035     SubstitutionDiagnostic *ExprSubstDiag, bool IsSimple,
1036     SourceLocation NoexceptLoc, ReturnTypeRequirement Req) :
1037     Requirement(IsSimple ? RK_Simple : RK_Compound, Req.isDependent(),
1038                 Req.containsUnexpandedParameterPack(), /*IsSatisfied=*/false),
1039     Value(ExprSubstDiag), NoexceptLoc(NoexceptLoc), TypeReq(Req),
1040     Status(SS_ExprSubstitutionFailure) {
1041   assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1042          "Simple requirement must not have a return type requirement or a "
1043          "noexcept specification");
1044 }
1045 
1046 concepts::ExprRequirement::ReturnTypeRequirement::
1047 ReturnTypeRequirement(TemplateParameterList *TPL) :
1048     TypeConstraintInfo(TPL, 0) {
1049   assert(TPL->size() == 1);
1050   const TypeConstraint *TC =
1051       cast<TemplateTypeParmDecl>(TPL->getParam(0))->getTypeConstraint();
1052   assert(TC &&
1053          "TPL must have a template type parameter with a type constraint");
1054   auto *Constraint =
1055       cast_or_null<ConceptSpecializationExpr>(
1056           TC->getImmediatelyDeclaredConstraint());
1057   bool Dependent =
1058       Constraint->getTemplateArgsAsWritten() &&
1059       TemplateSpecializationType::anyInstantiationDependentTemplateArguments(
1060           Constraint->getTemplateArgsAsWritten()->arguments().drop_front(1));
1061   TypeConstraintInfo.setInt(Dependent ? 1 : 0);
1062 }
1063 
1064 concepts::TypeRequirement::TypeRequirement(TypeSourceInfo *T) :
1065     Requirement(RK_Type, T->getType()->isInstantiationDependentType(),
1066                 T->getType()->containsUnexpandedParameterPack(),
1067                 // We reach this ctor with either dependent types (in which
1068                 // IsSatisfied doesn't matter) or with non-dependent type in
1069                 // which the existence of the type indicates satisfaction.
1070                 /*IsSatisfied=*/true),
1071     Value(T),
1072     Status(T->getType()->isInstantiationDependentType() ? SS_Dependent
1073                                                         : SS_Satisfied) {}
1074