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