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 static bool calculateConstraintSatisfaction(
171     Sema &S, const NamedDecl *Template, ArrayRef<TemplateArgument> TemplateArgs,
172     SourceLocation TemplateNameLoc, MultiLevelTemplateArgumentList &MLTAL,
173     const Expr *ConstraintExpr, ConstraintSatisfaction &Satisfaction) {
174   return calculateConstraintSatisfaction(
175       S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) {
176         EnterExpressionEvaluationContext ConstantEvaluated(
177             S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
178 
179         // Atomic constraint - substitute arguments and check satisfaction.
180         ExprResult SubstitutedExpression;
181         {
182           TemplateDeductionInfo Info(TemplateNameLoc);
183           Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(),
184               Sema::InstantiatingTemplate::ConstraintSubstitution{},
185               const_cast<NamedDecl *>(Template), Info,
186               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 static bool CheckConstraintSatisfaction(Sema &S, const NamedDecl *Template,
234                                         ArrayRef<const Expr *> ConstraintExprs,
235                                         ArrayRef<TemplateArgument> TemplateArgs,
236                                         SourceRange TemplateIDRange,
237                                         ConstraintSatisfaction &Satisfaction) {
238   if (ConstraintExprs.empty()) {
239     Satisfaction.IsSatisfied = true;
240     return false;
241   }
242 
243   for (auto& Arg : TemplateArgs)
244     if (Arg.isInstantiationDependent()) {
245       // No need to check satisfaction for dependent constraint expressions.
246       Satisfaction.IsSatisfied = true;
247       return false;
248     }
249 
250   Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(),
251       Sema::InstantiatingTemplate::ConstraintsCheck{},
252       const_cast<NamedDecl *>(Template), TemplateArgs, TemplateIDRange);
253   if (Inst.isInvalid())
254     return true;
255 
256   MultiLevelTemplateArgumentList MLTAL;
257   MLTAL.addOuterTemplateArguments(TemplateArgs);
258 
259   for (const Expr *ConstraintExpr : ConstraintExprs) {
260     if (calculateConstraintSatisfaction(S, Template, TemplateArgs,
261                                         TemplateIDRange.getBegin(), MLTAL,
262                                         ConstraintExpr, Satisfaction))
263       return true;
264     if (!Satisfaction.IsSatisfied)
265       // [temp.constr.op] p2
266       //   [...] To determine if a conjunction is satisfied, the satisfaction
267       //   of the first operand is checked. If that is not satisfied, the
268       //   conjunction is not satisfied. [...]
269       return false;
270   }
271   return false;
272 }
273 
274 bool Sema::CheckConstraintSatisfaction(
275     const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
276     ArrayRef<TemplateArgument> TemplateArgs, SourceRange TemplateIDRange,
277     ConstraintSatisfaction &OutSatisfaction) {
278   if (ConstraintExprs.empty()) {
279     OutSatisfaction.IsSatisfied = true;
280     return false;
281   }
282 
283   llvm::FoldingSetNodeID ID;
284   void *InsertPos;
285   ConstraintSatisfaction *Satisfaction = nullptr;
286   bool ShouldCache = LangOpts.ConceptSatisfactionCaching && Template;
287   if (ShouldCache) {
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   if (::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
299                                     TemplateArgs, TemplateIDRange,
300                                     *Satisfaction)) {
301     if (ShouldCache)
302       delete Satisfaction;
303     return true;
304   }
305 
306   if (ShouldCache) {
307     // We cannot use InsertNode here because CheckConstraintSatisfaction might
308     // have invalidated it.
309     SatisfactionCache.InsertNode(Satisfaction);
310     OutSatisfaction = *Satisfaction;
311   }
312   return false;
313 }
314 
315 bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
316                                        ConstraintSatisfaction &Satisfaction) {
317   return calculateConstraintSatisfaction(
318       *this, ConstraintExpr, Satisfaction,
319       [](const Expr *AtomicExpr) -> ExprResult {
320         return ExprResult(const_cast<Expr *>(AtomicExpr));
321       });
322 }
323 
324 bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,
325                                     ConstraintSatisfaction &Satisfaction,
326                                     SourceLocation UsageLoc) {
327   const Expr *RC = FD->getTrailingRequiresClause();
328   if (RC->isInstantiationDependent()) {
329     Satisfaction.IsSatisfied = true;
330     return false;
331   }
332   Qualifiers ThisQuals;
333   CXXRecordDecl *Record = nullptr;
334   if (auto *Method = dyn_cast<CXXMethodDecl>(FD)) {
335     ThisQuals = Method->getMethodQualifiers();
336     Record = const_cast<CXXRecordDecl *>(Method->getParent());
337   }
338   CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
339   // We substitute with empty arguments in order to rebuild the atomic
340   // constraint in a constant-evaluated context.
341   // FIXME: Should this be a dedicated TreeTransform?
342   return CheckConstraintSatisfaction(
343       FD, {RC}, /*TemplateArgs=*/{},
344       SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),
345       Satisfaction);
346 }
347 
348 bool Sema::EnsureTemplateArgumentListConstraints(
349     TemplateDecl *TD, ArrayRef<TemplateArgument> TemplateArgs,
350     SourceRange TemplateIDRange) {
351   ConstraintSatisfaction Satisfaction;
352   llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
353   TD->getAssociatedConstraints(AssociatedConstraints);
354   if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgs,
355                                   TemplateIDRange, Satisfaction))
356     return true;
357 
358   if (!Satisfaction.IsSatisfied) {
359     SmallString<128> TemplateArgString;
360     TemplateArgString = " ";
361     TemplateArgString += getTemplateArgumentBindingsText(
362         TD->getTemplateParameters(), TemplateArgs.data(), TemplateArgs.size());
363 
364     Diag(TemplateIDRange.getBegin(),
365          diag::err_template_arg_list_constraints_not_satisfied)
366         << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD
367         << TemplateArgString << TemplateIDRange;
368     DiagnoseUnsatisfiedConstraint(Satisfaction);
369     return true;
370   }
371   return false;
372 }
373 
374 static void diagnoseUnsatisfiedRequirement(Sema &S,
375                                            concepts::ExprRequirement *Req,
376                                            bool First) {
377   assert(!Req->isSatisfied()
378          && "Diagnose() can only be used on an unsatisfied requirement");
379   switch (Req->getSatisfactionStatus()) {
380     case concepts::ExprRequirement::SS_Dependent:
381       llvm_unreachable("Diagnosing a dependent requirement");
382       break;
383     case concepts::ExprRequirement::SS_ExprSubstitutionFailure: {
384       auto *SubstDiag = Req->getExprSubstitutionDiagnostic();
385       if (!SubstDiag->DiagMessage.empty())
386         S.Diag(SubstDiag->DiagLoc,
387                diag::note_expr_requirement_expr_substitution_error)
388                << (int)First << SubstDiag->SubstitutedEntity
389                << SubstDiag->DiagMessage;
390       else
391         S.Diag(SubstDiag->DiagLoc,
392                diag::note_expr_requirement_expr_unknown_substitution_error)
393             << (int)First << SubstDiag->SubstitutedEntity;
394       break;
395     }
396     case concepts::ExprRequirement::SS_NoexceptNotMet:
397       S.Diag(Req->getNoexceptLoc(),
398              diag::note_expr_requirement_noexcept_not_met)
399           << (int)First << Req->getExpr();
400       break;
401     case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {
402       auto *SubstDiag =
403           Req->getReturnTypeRequirement().getSubstitutionDiagnostic();
404       if (!SubstDiag->DiagMessage.empty())
405         S.Diag(SubstDiag->DiagLoc,
406                diag::note_expr_requirement_type_requirement_substitution_error)
407             << (int)First << SubstDiag->SubstitutedEntity
408             << SubstDiag->DiagMessage;
409       else
410         S.Diag(SubstDiag->DiagLoc,
411                diag::note_expr_requirement_type_requirement_unknown_substitution_error)
412             << (int)First << SubstDiag->SubstitutedEntity;
413       break;
414     }
415     case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: {
416       ConceptSpecializationExpr *ConstraintExpr =
417           Req->getReturnTypeRequirementSubstitutedConstraintExpr();
418       if (ConstraintExpr->getTemplateArgsAsWritten()->NumTemplateArgs == 1)
419         // A simple case - expr type is the type being constrained and the concept
420         // was not provided arguments.
421         S.Diag(ConstraintExpr->getBeginLoc(),
422                diag::note_expr_requirement_constraints_not_satisfied_simple)
423             << (int)First << S.BuildDecltypeType(Req->getExpr(),
424                                                  Req->getExpr()->getBeginLoc())
425             << ConstraintExpr->getNamedConcept();
426       else
427         S.Diag(ConstraintExpr->getBeginLoc(),
428                diag::note_expr_requirement_constraints_not_satisfied)
429             << (int)First << ConstraintExpr;
430       S.DiagnoseUnsatisfiedConstraint(ConstraintExpr->getSatisfaction());
431       break;
432     }
433     case concepts::ExprRequirement::SS_Satisfied:
434       llvm_unreachable("We checked this above");
435   }
436 }
437 
438 static void diagnoseUnsatisfiedRequirement(Sema &S,
439                                            concepts::TypeRequirement *Req,
440                                            bool First) {
441   assert(!Req->isSatisfied()
442          && "Diagnose() can only be used on an unsatisfied requirement");
443   switch (Req->getSatisfactionStatus()) {
444   case concepts::TypeRequirement::SS_Dependent:
445     llvm_unreachable("Diagnosing a dependent requirement");
446     return;
447   case concepts::TypeRequirement::SS_SubstitutionFailure: {
448     auto *SubstDiag = Req->getSubstitutionDiagnostic();
449     if (!SubstDiag->DiagMessage.empty())
450       S.Diag(SubstDiag->DiagLoc,
451              diag::note_type_requirement_substitution_error) << (int)First
452           << SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage;
453     else
454       S.Diag(SubstDiag->DiagLoc,
455              diag::note_type_requirement_unknown_substitution_error)
456           << (int)First << SubstDiag->SubstitutedEntity;
457     return;
458   }
459   default:
460     llvm_unreachable("Unknown satisfaction status");
461     return;
462   }
463 }
464 
465 static void diagnoseUnsatisfiedRequirement(Sema &S,
466                                            concepts::NestedRequirement *Req,
467                                            bool First) {
468   if (Req->isSubstitutionFailure()) {
469     concepts::Requirement::SubstitutionDiagnostic *SubstDiag =
470         Req->getSubstitutionDiagnostic();
471     if (!SubstDiag->DiagMessage.empty())
472       S.Diag(SubstDiag->DiagLoc,
473              diag::note_nested_requirement_substitution_error)
474              << (int)First << SubstDiag->SubstitutedEntity
475              << SubstDiag->DiagMessage;
476     else
477       S.Diag(SubstDiag->DiagLoc,
478              diag::note_nested_requirement_unknown_substitution_error)
479           << (int)First << SubstDiag->SubstitutedEntity;
480     return;
481   }
482   S.DiagnoseUnsatisfiedConstraint(Req->getConstraintSatisfaction(), First);
483 }
484 
485 
486 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
487                                                         Expr *SubstExpr,
488                                                         bool First = true) {
489   SubstExpr = SubstExpr->IgnoreParenImpCasts();
490   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) {
491     switch (BO->getOpcode()) {
492     // These two cases will in practice only be reached when using fold
493     // expressions with || and &&, since otherwise the || and && will have been
494     // broken down into atomic constraints during satisfaction checking.
495     case BO_LOr:
496       // Or evaluated to false - meaning both RHS and LHS evaluated to false.
497       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
498       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
499                                                   /*First=*/false);
500       return;
501     case BO_LAnd:
502       bool LHSSatisfied;
503       BO->getLHS()->EvaluateAsBooleanCondition(LHSSatisfied, S.Context);
504       if (LHSSatisfied) {
505         // LHS is true, so RHS must be false.
506         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First);
507         return;
508       }
509       // LHS is false
510       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
511 
512       // RHS might also be false
513       bool RHSSatisfied;
514       BO->getRHS()->EvaluateAsBooleanCondition(RHSSatisfied, S.Context);
515       if (!RHSSatisfied)
516         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
517                                                     /*First=*/false);
518       return;
519     case BO_GE:
520     case BO_LE:
521     case BO_GT:
522     case BO_LT:
523     case BO_EQ:
524     case BO_NE:
525       if (BO->getLHS()->getType()->isIntegerType() &&
526           BO->getRHS()->getType()->isIntegerType()) {
527         Expr::EvalResult SimplifiedLHS;
528         Expr::EvalResult SimplifiedRHS;
529         BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context);
530         BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context);
531         if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) {
532           S.Diag(SubstExpr->getBeginLoc(),
533                  diag::note_atomic_constraint_evaluated_to_false_elaborated)
534               << (int)First << SubstExpr
535               << SimplifiedLHS.Val.getInt().toString(10)
536               << BinaryOperator::getOpcodeStr(BO->getOpcode())
537               << SimplifiedRHS.Val.getInt().toString(10);
538           return;
539         }
540       }
541       break;
542 
543     default:
544       break;
545     }
546   } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) {
547     if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
548       S.Diag(
549           CSE->getSourceRange().getBegin(),
550           diag::
551           note_single_arg_concept_specialization_constraint_evaluated_to_false)
552           << (int)First
553           << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument()
554           << CSE->getNamedConcept();
555     } else {
556       S.Diag(SubstExpr->getSourceRange().getBegin(),
557              diag::note_concept_specialization_constraint_evaluated_to_false)
558           << (int)First << CSE;
559     }
560     S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction());
561     return;
562   } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) {
563     for (concepts::Requirement *Req : RE->getRequirements())
564       if (!Req->isDependent() && !Req->isSatisfied()) {
565         if (auto *E = dyn_cast<concepts::ExprRequirement>(Req))
566           diagnoseUnsatisfiedRequirement(S, E, First);
567         else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req))
568           diagnoseUnsatisfiedRequirement(S, T, First);
569         else
570           diagnoseUnsatisfiedRequirement(
571               S, cast<concepts::NestedRequirement>(Req), First);
572         break;
573       }
574     return;
575   }
576 
577   S.Diag(SubstExpr->getSourceRange().getBegin(),
578          diag::note_atomic_constraint_evaluated_to_false)
579       << (int)First << SubstExpr;
580 }
581 
582 template<typename SubstitutionDiagnostic>
583 static void diagnoseUnsatisfiedConstraintExpr(
584     Sema &S, const Expr *E,
585     const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record,
586     bool First = true) {
587   if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){
588     S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)
589         << Diag->second;
590     return;
591   }
592 
593   diagnoseWellFormedUnsatisfiedConstraintExpr(S,
594       Record.template get<Expr *>(), First);
595 }
596 
597 void
598 Sema::DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction& Satisfaction,
599                                     bool First) {
600   assert(!Satisfaction.IsSatisfied &&
601          "Attempted to diagnose a satisfied constraint");
602   for (auto &Pair : Satisfaction.Details) {
603     diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
604     First = false;
605   }
606 }
607 
608 void Sema::DiagnoseUnsatisfiedConstraint(
609     const ASTConstraintSatisfaction &Satisfaction,
610     bool First) {
611   assert(!Satisfaction.IsSatisfied &&
612          "Attempted to diagnose a satisfied constraint");
613   for (auto &Pair : Satisfaction) {
614     diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
615     First = false;
616   }
617 }
618 
619 const NormalizedConstraint *
620 Sema::getNormalizedAssociatedConstraints(
621     NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) {
622   auto CacheEntry = NormalizationCache.find(ConstrainedDecl);
623   if (CacheEntry == NormalizationCache.end()) {
624     auto Normalized =
625         NormalizedConstraint::fromConstraintExprs(*this, ConstrainedDecl,
626                                                   AssociatedConstraints);
627     CacheEntry =
628         NormalizationCache
629             .try_emplace(ConstrainedDecl,
630                          Normalized
631                              ? new (Context) NormalizedConstraint(
632                                  std::move(*Normalized))
633                              : nullptr)
634             .first;
635   }
636   return CacheEntry->second;
637 }
638 
639 static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
640     ConceptDecl *Concept, ArrayRef<TemplateArgument> TemplateArgs,
641     const ASTTemplateArgumentListInfo *ArgsAsWritten) {
642   if (!N.isAtomic()) {
643     if (substituteParameterMappings(S, N.getLHS(), Concept, TemplateArgs,
644                                     ArgsAsWritten))
645       return true;
646     return substituteParameterMappings(S, N.getRHS(), Concept, TemplateArgs,
647                                        ArgsAsWritten);
648   }
649   TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
650 
651   AtomicConstraint &Atomic = *N.getAtomicConstraint();
652   TemplateArgumentListInfo SubstArgs;
653   MultiLevelTemplateArgumentList MLTAL;
654   MLTAL.addOuterTemplateArguments(TemplateArgs);
655   if (!Atomic.ParameterMapping) {
656     llvm::SmallBitVector OccurringIndices(TemplateParams->size());
657     S.MarkUsedTemplateParameters(Atomic.ConstraintExpr, /*OnlyDeduced=*/false,
658                                  /*Depth=*/0, OccurringIndices);
659     Atomic.ParameterMapping.emplace(
660         MutableArrayRef<TemplateArgumentLoc>(
661             new (S.Context) TemplateArgumentLoc[OccurringIndices.count()],
662             OccurringIndices.count()));
663     for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I)
664       if (OccurringIndices[I])
665         new (&(*Atomic.ParameterMapping)[J++]) TemplateArgumentLoc(
666             S.getIdentityTemplateArgumentLoc(TemplateParams->begin()[I],
667                 // Here we assume we do not support things like
668                 // template<typename A, typename B>
669                 // concept C = ...;
670                 //
671                 // template<typename... Ts> requires C<Ts...>
672                 // struct S { };
673                 // The above currently yields a diagnostic.
674                 // We still might have default arguments for concept parameters.
675                 ArgsAsWritten->NumTemplateArgs > I ?
676                 ArgsAsWritten->arguments()[I].getLocation() :
677                 SourceLocation()));
678   }
679   Sema::InstantiatingTemplate Inst(
680       S, ArgsAsWritten->arguments().front().getSourceRange().getBegin(),
681       Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, Concept,
682       SourceRange(ArgsAsWritten->arguments()[0].getSourceRange().getBegin(),
683                   ArgsAsWritten->arguments().back().getSourceRange().getEnd()));
684   if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs))
685     return true;
686   Atomic.ParameterMapping.emplace(
687         MutableArrayRef<TemplateArgumentLoc>(
688             new (S.Context) TemplateArgumentLoc[SubstArgs.size()],
689             SubstArgs.size()));
690   std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(),
691             N.getAtomicConstraint()->ParameterMapping->begin());
692   return false;
693 }
694 
695 Optional<NormalizedConstraint>
696 NormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D,
697                                           ArrayRef<const Expr *> E) {
698   assert(E.size() != 0);
699   auto First = fromConstraintExpr(S, D, E[0]);
700   if (E.size() == 1)
701     return First;
702   auto Second = fromConstraintExpr(S, D, E[1]);
703   if (!Second)
704     return None;
705   llvm::Optional<NormalizedConstraint> Conjunction;
706   Conjunction.emplace(S.Context, std::move(*First), std::move(*Second),
707                       CCK_Conjunction);
708   for (unsigned I = 2; I < E.size(); ++I) {
709     auto Next = fromConstraintExpr(S, D, E[I]);
710     if (!Next)
711       return llvm::Optional<NormalizedConstraint>{};
712     NormalizedConstraint NewConjunction(S.Context, std::move(*Conjunction),
713                                         std::move(*Next), CCK_Conjunction);
714     *Conjunction = std::move(NewConjunction);
715   }
716   return Conjunction;
717 }
718 
719 llvm::Optional<NormalizedConstraint>
720 NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
721   assert(E != nullptr);
722 
723   // C++ [temp.constr.normal]p1.1
724   // [...]
725   // - The normal form of an expression (E) is the normal form of E.
726   // [...]
727   E = E->IgnoreParenImpCasts();
728   if (auto *BO = dyn_cast<const BinaryOperator>(E)) {
729     if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) {
730       auto LHS = fromConstraintExpr(S, D, BO->getLHS());
731       if (!LHS)
732         return None;
733       auto RHS = fromConstraintExpr(S, D, BO->getRHS());
734       if (!RHS)
735         return None;
736 
737       return NormalizedConstraint(
738           S.Context, std::move(*LHS), std::move(*RHS),
739           BO->getOpcode() == BO_LAnd ? CCK_Conjunction : CCK_Disjunction);
740     }
741   } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) {
742     const NormalizedConstraint *SubNF;
743     {
744       Sema::InstantiatingTemplate Inst(
745           S, CSE->getExprLoc(),
746           Sema::InstantiatingTemplate::ConstraintNormalization{}, D,
747           CSE->getSourceRange());
748       // C++ [temp.constr.normal]p1.1
749       // [...]
750       // The normal form of an id-expression of the form C<A1, A2, ..., AN>,
751       // where C names a concept, is the normal form of the
752       // constraint-expression of C, after substituting A1, A2, ..., AN for C’s
753       // respective template parameters in the parameter mappings in each atomic
754       // constraint. If any such substitution results in an invalid type or
755       // expression, the program is ill-formed; no diagnostic is required.
756       // [...]
757       ConceptDecl *CD = CSE->getNamedConcept();
758       SubNF = S.getNormalizedAssociatedConstraints(CD,
759                                                    {CD->getConstraintExpr()});
760       if (!SubNF)
761         return None;
762     }
763 
764     Optional<NormalizedConstraint> New;
765     New.emplace(S.Context, *SubNF);
766 
767     if (substituteParameterMappings(
768             S, *New, CSE->getNamedConcept(),
769             CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten()))
770       return None;
771 
772     return New;
773   }
774   return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)};
775 }
776 
777 using NormalForm =
778     llvm::SmallVector<llvm::SmallVector<AtomicConstraint *, 2>, 4>;
779 
780 static NormalForm makeCNF(const NormalizedConstraint &Normalized) {
781   if (Normalized.isAtomic())
782     return {{Normalized.getAtomicConstraint()}};
783 
784   NormalForm LCNF = makeCNF(Normalized.getLHS());
785   NormalForm RCNF = makeCNF(Normalized.getRHS());
786   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) {
787     LCNF.reserve(LCNF.size() + RCNF.size());
788     while (!RCNF.empty())
789       LCNF.push_back(RCNF.pop_back_val());
790     return LCNF;
791   }
792 
793   // Disjunction
794   NormalForm Res;
795   Res.reserve(LCNF.size() * RCNF.size());
796   for (auto &LDisjunction : LCNF)
797     for (auto &RDisjunction : RCNF) {
798       NormalForm::value_type Combined;
799       Combined.reserve(LDisjunction.size() + RDisjunction.size());
800       std::copy(LDisjunction.begin(), LDisjunction.end(),
801                 std::back_inserter(Combined));
802       std::copy(RDisjunction.begin(), RDisjunction.end(),
803                 std::back_inserter(Combined));
804       Res.emplace_back(Combined);
805     }
806   return Res;
807 }
808 
809 static NormalForm makeDNF(const NormalizedConstraint &Normalized) {
810   if (Normalized.isAtomic())
811     return {{Normalized.getAtomicConstraint()}};
812 
813   NormalForm LDNF = makeDNF(Normalized.getLHS());
814   NormalForm RDNF = makeDNF(Normalized.getRHS());
815   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) {
816     LDNF.reserve(LDNF.size() + RDNF.size());
817     while (!RDNF.empty())
818       LDNF.push_back(RDNF.pop_back_val());
819     return LDNF;
820   }
821 
822   // Conjunction
823   NormalForm Res;
824   Res.reserve(LDNF.size() * RDNF.size());
825   for (auto &LConjunction : LDNF) {
826     for (auto &RConjunction : RDNF) {
827       NormalForm::value_type Combined;
828       Combined.reserve(LConjunction.size() + RConjunction.size());
829       std::copy(LConjunction.begin(), LConjunction.end(),
830                 std::back_inserter(Combined));
831       std::copy(RConjunction.begin(), RConjunction.end(),
832                 std::back_inserter(Combined));
833       Res.emplace_back(Combined);
834     }
835   }
836   return Res;
837 }
838 
839 template<typename AtomicSubsumptionEvaluator>
840 static bool subsumes(NormalForm PDNF, NormalForm QCNF,
841                      AtomicSubsumptionEvaluator E) {
842   // C++ [temp.constr.order] p2
843   //   Then, P subsumes Q if and only if, for every disjunctive clause Pi in the
844   //   disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in
845   //   the conjuctive normal form of Q, where [...]
846   for (const auto &Pi : PDNF) {
847     for (const auto &Qj : QCNF) {
848       // C++ [temp.constr.order] p2
849       //   - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
850       //     and only if there exists an atomic constraint Pia in Pi for which
851       //     there exists an atomic constraint, Qjb, in Qj such that Pia
852       //     subsumes Qjb.
853       bool Found = false;
854       for (const AtomicConstraint *Pia : Pi) {
855         for (const AtomicConstraint *Qjb : Qj) {
856           if (E(*Pia, *Qjb)) {
857             Found = true;
858             break;
859           }
860         }
861         if (Found)
862           break;
863       }
864       if (!Found)
865         return false;
866     }
867   }
868   return true;
869 }
870 
871 template<typename AtomicSubsumptionEvaluator>
872 static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P,
873                      NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes,
874                      AtomicSubsumptionEvaluator E) {
875   // C++ [temp.constr.order] p2
876   //   In order to determine if a constraint P subsumes a constraint Q, P is
877   //   transformed into disjunctive normal form, and Q is transformed into
878   //   conjunctive normal form. [...]
879   auto *PNormalized = S.getNormalizedAssociatedConstraints(DP, P);
880   if (!PNormalized)
881     return true;
882   const NormalForm PDNF = makeDNF(*PNormalized);
883 
884   auto *QNormalized = S.getNormalizedAssociatedConstraints(DQ, Q);
885   if (!QNormalized)
886     return true;
887   const NormalForm QCNF = makeCNF(*QNormalized);
888 
889   Subsumes = subsumes(PDNF, QCNF, E);
890   return false;
891 }
892 
893 bool Sema::IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef<const Expr *> AC1,
894                                   NamedDecl *D2, ArrayRef<const Expr *> AC2,
895                                   bool &Result) {
896   if (AC1.empty()) {
897     Result = AC2.empty();
898     return false;
899   }
900   if (AC2.empty()) {
901     // TD1 has associated constraints and TD2 does not.
902     Result = true;
903     return false;
904   }
905 
906   std::pair<NamedDecl *, NamedDecl *> Key{D1, D2};
907   auto CacheEntry = SubsumptionCache.find(Key);
908   if (CacheEntry != SubsumptionCache.end()) {
909     Result = CacheEntry->second;
910     return false;
911   }
912 
913   if (subsumes(*this, D1, AC1, D2, AC2, Result,
914         [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
915           return A.subsumes(Context, B);
916         }))
917     return true;
918   SubsumptionCache.try_emplace(Key, Result);
919   return false;
920 }
921 
922 bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
923     ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) {
924   if (isSFINAEContext())
925     // No need to work here because our notes would be discarded.
926     return false;
927 
928   if (AC1.empty() || AC2.empty())
929     return false;
930 
931   auto NormalExprEvaluator =
932       [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
933         return A.subsumes(Context, B);
934       };
935 
936   const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;
937   auto IdenticalExprEvaluator =
938       [&] (const AtomicConstraint &A, const AtomicConstraint &B) {
939         if (!A.hasMatchingParameterMapping(Context, B))
940           return false;
941         const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr;
942         if (EA == EB)
943           return true;
944 
945         // Not the same source level expression - are the expressions
946         // identical?
947         llvm::FoldingSetNodeID IDA, IDB;
948         EA->Profile(IDA, Context, /*Cannonical=*/true);
949         EB->Profile(IDB, Context, /*Cannonical=*/true);
950         if (IDA != IDB)
951           return false;
952 
953         AmbiguousAtomic1 = EA;
954         AmbiguousAtomic2 = EB;
955         return true;
956       };
957 
958   {
959     // The subsumption checks might cause diagnostics
960     SFINAETrap Trap(*this);
961     auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1);
962     if (!Normalized1)
963       return false;
964     const NormalForm DNF1 = makeDNF(*Normalized1);
965     const NormalForm CNF1 = makeCNF(*Normalized1);
966 
967     auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2);
968     if (!Normalized2)
969       return false;
970     const NormalForm DNF2 = makeDNF(*Normalized2);
971     const NormalForm CNF2 = makeCNF(*Normalized2);
972 
973     bool Is1AtLeastAs2Normally = subsumes(DNF1, CNF2, NormalExprEvaluator);
974     bool Is2AtLeastAs1Normally = subsumes(DNF2, CNF1, NormalExprEvaluator);
975     bool Is1AtLeastAs2 = subsumes(DNF1, CNF2, IdenticalExprEvaluator);
976     bool Is2AtLeastAs1 = subsumes(DNF2, CNF1, IdenticalExprEvaluator);
977     if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
978         Is2AtLeastAs1 == Is2AtLeastAs1Normally)
979       // Same result - no ambiguity was caused by identical atomic expressions.
980       return false;
981   }
982 
983   // A different result! Some ambiguous atomic constraint(s) caused a difference
984   assert(AmbiguousAtomic1 && AmbiguousAtomic2);
985 
986   Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints)
987       << AmbiguousAtomic1->getSourceRange();
988   Diag(AmbiguousAtomic2->getBeginLoc(),
989        diag::note_ambiguous_atomic_constraints_similar_expression)
990       << AmbiguousAtomic2->getSourceRange();
991   return true;
992 }
993 
994 concepts::ExprRequirement::ExprRequirement(
995     Expr *E, bool IsSimple, SourceLocation NoexceptLoc,
996     ReturnTypeRequirement Req, SatisfactionStatus Status,
997     ConceptSpecializationExpr *SubstitutedConstraintExpr) :
998     Requirement(IsSimple ? RK_Simple : RK_Compound, Status == SS_Dependent,
999                 Status == SS_Dependent &&
1000                 (E->containsUnexpandedParameterPack() ||
1001                  Req.containsUnexpandedParameterPack()),
1002                 Status == SS_Satisfied), Value(E), NoexceptLoc(NoexceptLoc),
1003     TypeReq(Req), SubstitutedConstraintExpr(SubstitutedConstraintExpr),
1004     Status(Status) {
1005   assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1006          "Simple requirement must not have a return type requirement or a "
1007          "noexcept specification");
1008   assert((Status > SS_TypeRequirementSubstitutionFailure && Req.isTypeConstraint()) ==
1009          (SubstitutedConstraintExpr != nullptr));
1010 }
1011 
1012 concepts::ExprRequirement::ExprRequirement(
1013     SubstitutionDiagnostic *ExprSubstDiag, bool IsSimple,
1014     SourceLocation NoexceptLoc, ReturnTypeRequirement Req) :
1015     Requirement(IsSimple ? RK_Simple : RK_Compound, Req.isDependent(),
1016                 Req.containsUnexpandedParameterPack(), /*IsSatisfied=*/false),
1017     Value(ExprSubstDiag), NoexceptLoc(NoexceptLoc), TypeReq(Req),
1018     Status(SS_ExprSubstitutionFailure) {
1019   assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1020          "Simple requirement must not have a return type requirement or a "
1021          "noexcept specification");
1022 }
1023 
1024 concepts::ExprRequirement::ReturnTypeRequirement::
1025 ReturnTypeRequirement(TemplateParameterList *TPL) :
1026     TypeConstraintInfo(TPL, 0) {
1027   assert(TPL->size() == 1);
1028   const TypeConstraint *TC =
1029       cast<TemplateTypeParmDecl>(TPL->getParam(0))->getTypeConstraint();
1030   assert(TC &&
1031          "TPL must have a template type parameter with a type constraint");
1032   auto *Constraint =
1033       cast_or_null<ConceptSpecializationExpr>(
1034           TC->getImmediatelyDeclaredConstraint());
1035   bool Dependent = false;
1036   if (Constraint->getTemplateArgsAsWritten()) {
1037     for (auto &ArgLoc :
1038          Constraint->getTemplateArgsAsWritten()->arguments().drop_front(1)) {
1039       if (ArgLoc.getArgument().isDependent()) {
1040         Dependent = true;
1041         break;
1042       }
1043     }
1044   }
1045   TypeConstraintInfo.setInt(Dependent ? 1 : 0);
1046 }
1047 
1048 concepts::TypeRequirement::TypeRequirement(TypeSourceInfo *T) :
1049     Requirement(RK_Type, T->getType()->isDependentType(),
1050                 T->getType()->containsUnexpandedParameterPack(),
1051                 // We reach this ctor with either dependent types (in which
1052                 // IsSatisfied doesn't matter) or with non-dependent type in
1053                 // which the existence of the type indicates satisfaction.
1054                 /*IsSatisfied=*/true
1055                 ), Value(T),
1056     Status(T->getType()->isDependentType() ? SS_Dependent : SS_Satisfied) {}
1057