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