Coverage Report

Created: 2020-11-24 06:42

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