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/Sema.h"
15 #include "clang/Sema/SemaInternal.h"
16 #include "clang/Sema/SemaDiagnostic.h"
17 #include "clang/Sema/TemplateDeduction.h"
18 #include "clang/Sema/Template.h"
19 #include "clang/AST/ExprCXX.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/PointerUnion.h"
22 using namespace clang;
23 using namespace sema;
24 
25 bool Sema::CheckConstraintExpression(Expr *ConstraintExpression) {
26   // C++2a [temp.constr.atomic]p1
27   // ..E shall be a constant expression of type bool.
28 
29   ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts();
30 
31   if (auto *BinOp = dyn_cast<BinaryOperator>(ConstraintExpression)) {
32     if (BinOp->getOpcode() == BO_LAnd || BinOp->getOpcode() == BO_LOr)
33       return CheckConstraintExpression(BinOp->getLHS()) &&
34              CheckConstraintExpression(BinOp->getRHS());
35   } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression))
36     return CheckConstraintExpression(C->getSubExpr());
37 
38   // An atomic constraint!
39   if (ConstraintExpression->isTypeDependent())
40     return true;
41 
42   QualType Type = ConstraintExpression->getType();
43   if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) {
44     Diag(ConstraintExpression->getExprLoc(),
45          diag::err_non_bool_atomic_constraint) << Type
46         << ConstraintExpression->getSourceRange();
47     return false;
48   }
49   return true;
50 }
51 
52 template <typename AtomicEvaluator>
53 static bool
54 calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
55                                 ConstraintSatisfaction &Satisfaction,
56                                 AtomicEvaluator &&Evaluator) {
57   ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
58 
59   if (auto *BO = dyn_cast<BinaryOperator>(ConstraintExpr)) {
60     if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) {
61       if (calculateConstraintSatisfaction(S, BO->getLHS(), Satisfaction,
62                                           Evaluator))
63         return true;
64 
65       bool IsLHSSatisfied = Satisfaction.IsSatisfied;
66 
67       if (BO->getOpcode() == BO_LOr && IsLHSSatisfied)
68         // [temp.constr.op] p3
69         //    A disjunction is a constraint taking two operands. To determine if
70         //    a disjunction is satisfied, the satisfaction of the first operand
71         //    is checked. If that is satisfied, the disjunction is satisfied.
72         //    Otherwise, the disjunction is satisfied if and only if the second
73         //    operand is satisfied.
74         return false;
75 
76       if (BO->getOpcode() == BO_LAnd && !IsLHSSatisfied)
77         // [temp.constr.op] p2
78         //    A conjunction is a constraint taking two operands. To determine if
79         //    a conjunction is satisfied, the satisfaction of the first operand
80         //    is checked. If that is not satisfied, the conjunction is not
81         //    satisfied. Otherwise, the conjunction is satisfied if and only if
82         //    the second operand is satisfied.
83         return false;
84 
85       return calculateConstraintSatisfaction(S, BO->getRHS(), Satisfaction,
86           std::forward<AtomicEvaluator>(Evaluator));
87     }
88   }
89   else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr))
90     return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction,
91         std::forward<AtomicEvaluator>(Evaluator));
92 
93   // An atomic constraint expression
94   ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr);
95 
96   if (SubstitutedAtomicExpr.isInvalid())
97     return true;
98 
99   if (!SubstitutedAtomicExpr.isUsable())
100     // Evaluator has decided satisfaction without yielding an expression.
101     return false;
102 
103   EnterExpressionEvaluationContext ConstantEvaluated(
104       S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
105   SmallVector<PartialDiagnosticAt, 2> EvaluationDiags;
106   Expr::EvalResult EvalResult;
107   EvalResult.Diag = &EvaluationDiags;
108   if (!SubstitutedAtomicExpr.get()->EvaluateAsRValue(EvalResult, S.Context)) {
109       // C++2a [temp.constr.atomic]p1
110       //   ...E shall be a constant expression of type bool.
111     S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(),
112            diag::err_non_constant_constraint_expression)
113         << SubstitutedAtomicExpr.get()->getSourceRange();
114     for (const PartialDiagnosticAt &PDiag : EvaluationDiags)
115       S.Diag(PDiag.first, PDiag.second);
116     return true;
117   }
118 
119   Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();
120   if (!Satisfaction.IsSatisfied)
121     Satisfaction.Details.emplace_back(ConstraintExpr,
122                                       SubstitutedAtomicExpr.get());
123 
124   return false;
125 }
126 
127 template <typename TemplateDeclT>
128 static bool calculateConstraintSatisfaction(
129     Sema &S, TemplateDeclT *Template, ArrayRef<TemplateArgument> TemplateArgs,
130     SourceLocation TemplateNameLoc, MultiLevelTemplateArgumentList &MLTAL,
131     const Expr *ConstraintExpr, ConstraintSatisfaction &Satisfaction) {
132   return calculateConstraintSatisfaction(
133       S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) {
134         EnterExpressionEvaluationContext ConstantEvaluated(
135             S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
136 
137         // Atomic constraint - substitute arguments and check satisfaction.
138         ExprResult SubstitutedExpression;
139         {
140           TemplateDeductionInfo Info(TemplateNameLoc);
141           Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(),
142               Sema::InstantiatingTemplate::ConstraintSubstitution{}, Template,
143               Info, AtomicExpr->getSourceRange());
144           if (Inst.isInvalid())
145             return ExprError();
146           // We do not want error diagnostics escaping here.
147           Sema::SFINAETrap Trap(S);
148           SubstitutedExpression = S.SubstExpr(const_cast<Expr *>(AtomicExpr),
149                                               MLTAL);
150           if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {
151             // C++2a [temp.constr.atomic]p1
152             //   ...If substitution results in an invalid type or expression, the
153             //   constraint is not satisfied.
154             if (!Trap.hasErrorOccurred())
155               // A non-SFINAE error has occured as a result of this
156               // substitution.
157               return ExprError();
158 
159             PartialDiagnosticAt SubstDiag{SourceLocation(),
160                                           PartialDiagnostic::NullDiagnostic()};
161             Info.takeSFINAEDiagnostic(SubstDiag);
162             // FIXME: Concepts: This is an unfortunate consequence of there
163             //  being no serialization code for PartialDiagnostics and the fact
164             //  that serializing them would likely take a lot more storage than
165             //  just storing them as strings. We would still like, in the
166             //  future, to serialize the proper PartialDiagnostic as serializing
167             //  it as a string defeats the purpose of the diagnostic mechanism.
168             SmallString<128> DiagString;
169             DiagString = ": ";
170             SubstDiag.second.EmitToString(S.getDiagnostics(), DiagString);
171             unsigned MessageSize = DiagString.size();
172             char *Mem = new (S.Context) char[MessageSize];
173             memcpy(Mem, DiagString.c_str(), MessageSize);
174             Satisfaction.Details.emplace_back(
175                 AtomicExpr,
176                 new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
177                         SubstDiag.first, StringRef(Mem, MessageSize)});
178             Satisfaction.IsSatisfied = false;
179             return ExprEmpty();
180           }
181         }
182 
183         if (!S.CheckConstraintExpression(SubstitutedExpression.get()))
184           return ExprError();
185 
186         return SubstitutedExpression;
187       });
188 }
189 
190 template<typename TemplateDeclT>
191 static bool CheckConstraintSatisfaction(Sema &S, TemplateDeclT *Template,
192                                         ArrayRef<const Expr *> ConstraintExprs,
193                                         ArrayRef<TemplateArgument> TemplateArgs,
194                                         SourceRange TemplateIDRange,
195                                         ConstraintSatisfaction &Satisfaction) {
196   if (ConstraintExprs.empty()) {
197     Satisfaction.IsSatisfied = true;
198     return false;
199   }
200 
201   for (auto& Arg : TemplateArgs)
202     if (Arg.isInstantiationDependent()) {
203       // No need to check satisfaction for dependent constraint expressions.
204       Satisfaction.IsSatisfied = true;
205       return false;
206     }
207 
208   Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(),
209       Sema::InstantiatingTemplate::ConstraintsCheck{}, Template, TemplateArgs,
210       TemplateIDRange);
211   if (Inst.isInvalid())
212     return true;
213 
214   MultiLevelTemplateArgumentList MLTAL;
215   MLTAL.addOuterTemplateArguments(TemplateArgs);
216 
217   for (const Expr *ConstraintExpr : ConstraintExprs) {
218     if (calculateConstraintSatisfaction(S, Template, TemplateArgs,
219                                         TemplateIDRange.getBegin(), MLTAL,
220                                         ConstraintExpr, Satisfaction))
221       return true;
222     if (!Satisfaction.IsSatisfied)
223       // [temp.constr.op] p2
224       //   [...] To determine if a conjunction is satisfied, the satisfaction
225       //   of the first operand is checked. If that is not satisfied, the
226       //   conjunction is not satisfied. [...]
227       return false;
228   }
229   return false;
230 }
231 
232 bool Sema::CheckConstraintSatisfaction(TemplateDecl *Template,
233                                        ArrayRef<const Expr *> ConstraintExprs,
234                                        ArrayRef<TemplateArgument> TemplateArgs,
235                                        SourceRange TemplateIDRange,
236                                        ConstraintSatisfaction &Satisfaction) {
237   return ::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
238                                        TemplateArgs, TemplateIDRange,
239                                        Satisfaction);
240 }
241 
242 bool
243 Sema::CheckConstraintSatisfaction(ClassTemplatePartialSpecializationDecl* Part,
244                                   ArrayRef<const Expr *> ConstraintExprs,
245                                   ArrayRef<TemplateArgument> TemplateArgs,
246                                   SourceRange TemplateIDRange,
247                                   ConstraintSatisfaction &Satisfaction) {
248   return ::CheckConstraintSatisfaction(*this, Part, ConstraintExprs,
249                                        TemplateArgs, TemplateIDRange,
250                                        Satisfaction);
251 }
252 
253 bool
254 Sema::CheckConstraintSatisfaction(VarTemplatePartialSpecializationDecl* Partial,
255                                   ArrayRef<const Expr *> ConstraintExprs,
256                                   ArrayRef<TemplateArgument> TemplateArgs,
257                                   SourceRange TemplateIDRange,
258                                   ConstraintSatisfaction &Satisfaction) {
259   return ::CheckConstraintSatisfaction(*this, Partial, ConstraintExprs,
260                                        TemplateArgs, TemplateIDRange,
261                                        Satisfaction);
262 }
263 
264 bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
265                                        ConstraintSatisfaction &Satisfaction) {
266   return calculateConstraintSatisfaction(
267       *this, ConstraintExpr, Satisfaction,
268       [](const Expr *AtomicExpr) -> ExprResult {
269         return ExprResult(const_cast<Expr *>(AtomicExpr));
270       });
271 }
272 
273 bool Sema::EnsureTemplateArgumentListConstraints(
274     TemplateDecl *TD, ArrayRef<TemplateArgument> TemplateArgs,
275     SourceRange TemplateIDRange) {
276   ConstraintSatisfaction Satisfaction;
277   llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
278   TD->getAssociatedConstraints(AssociatedConstraints);
279   if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgs,
280                                   TemplateIDRange, Satisfaction))
281     return true;
282 
283   if (!Satisfaction.IsSatisfied) {
284     SmallString<128> TemplateArgString;
285     TemplateArgString = " ";
286     TemplateArgString += getTemplateArgumentBindingsText(
287         TD->getTemplateParameters(), TemplateArgs.data(), TemplateArgs.size());
288 
289     Diag(TemplateIDRange.getBegin(),
290          diag::err_template_arg_list_constraints_not_satisfied)
291         << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD
292         << TemplateArgString << TemplateIDRange;
293     DiagnoseUnsatisfiedConstraint(Satisfaction);
294     return true;
295   }
296   return false;
297 }
298 
299 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
300                                                         Expr *SubstExpr,
301                                                         bool First = true) {
302   SubstExpr = SubstExpr->IgnoreParenImpCasts();
303   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) {
304     switch (BO->getOpcode()) {
305     // These two cases will in practice only be reached when using fold
306     // expressions with || and &&, since otherwise the || and && will have been
307     // broken down into atomic constraints during satisfaction checking.
308     case BO_LOr:
309       // Or evaluated to false - meaning both RHS and LHS evaluated to false.
310       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
311       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
312                                                   /*First=*/false);
313       return;
314     case BO_LAnd:
315       bool LHSSatisfied;
316       BO->getLHS()->EvaluateAsBooleanCondition(LHSSatisfied, S.Context);
317       if (LHSSatisfied) {
318         // LHS is true, so RHS must be false.
319         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First);
320         return;
321       }
322       // LHS is false
323       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
324 
325       // RHS might also be false
326       bool RHSSatisfied;
327       BO->getRHS()->EvaluateAsBooleanCondition(RHSSatisfied, S.Context);
328       if (!RHSSatisfied)
329         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
330                                                     /*First=*/false);
331       return;
332     case BO_GE:
333     case BO_LE:
334     case BO_GT:
335     case BO_LT:
336     case BO_EQ:
337     case BO_NE:
338       if (BO->getLHS()->getType()->isIntegerType() &&
339           BO->getRHS()->getType()->isIntegerType()) {
340         Expr::EvalResult SimplifiedLHS;
341         Expr::EvalResult SimplifiedRHS;
342         BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context);
343         BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context);
344         if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) {
345           S.Diag(SubstExpr->getBeginLoc(),
346                  diag::note_atomic_constraint_evaluated_to_false_elaborated)
347               << (int)First << SubstExpr
348               << SimplifiedLHS.Val.getInt().toString(10)
349               << BinaryOperator::getOpcodeStr(BO->getOpcode())
350               << SimplifiedRHS.Val.getInt().toString(10);
351           return;
352         }
353       }
354       break;
355 
356     default:
357       break;
358     }
359   } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) {
360     if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
361       S.Diag(
362           CSE->getSourceRange().getBegin(),
363           diag::
364           note_single_arg_concept_specialization_constraint_evaluated_to_false)
365           << (int)First
366           << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument()
367           << CSE->getNamedConcept();
368     } else {
369       S.Diag(SubstExpr->getSourceRange().getBegin(),
370              diag::note_concept_specialization_constraint_evaluated_to_false)
371           << (int)First << CSE;
372     }
373     S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction());
374     return;
375   }
376 
377   S.Diag(SubstExpr->getSourceRange().getBegin(),
378          diag::note_atomic_constraint_evaluated_to_false)
379       << (int)First << SubstExpr;
380 }
381 
382 template<typename SubstitutionDiagnostic>
383 static void diagnoseUnsatisfiedConstraintExpr(
384     Sema &S, const Expr *E,
385     const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record,
386     bool First = true) {
387   if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){
388     S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)
389         << Diag->second;
390     return;
391   }
392 
393   diagnoseWellFormedUnsatisfiedConstraintExpr(S,
394       Record.template get<Expr *>(), First);
395 }
396 
397 void Sema::DiagnoseUnsatisfiedConstraint(
398     const ConstraintSatisfaction& Satisfaction) {
399   assert(!Satisfaction.IsSatisfied &&
400          "Attempted to diagnose a satisfied constraint");
401   bool First = true;
402   for (auto &Pair : Satisfaction.Details) {
403     diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
404     First = false;
405   }
406 }
407 
408 void Sema::DiagnoseUnsatisfiedConstraint(
409     const ASTConstraintSatisfaction &Satisfaction) {
410   assert(!Satisfaction.IsSatisfied &&
411          "Attempted to diagnose a satisfied constraint");
412   bool First = true;
413   for (auto &Pair : Satisfaction) {
414     diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
415     First = false;
416   }
417 }