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