Coverage Report

Created: 2022-07-16 07:03

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