1//===-- SemaConcept.h - 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 provides semantic analysis for C++ constraints and concepts.
10///
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CLANG_SEMA_SEMACONCEPT_H
14#define LLVM_CLANG_SEMA_SEMACONCEPT_H
15#include "clang/AST/ASTConcept.h"
16#include "clang/AST/ASTContext.h"
17#include "clang/AST/DeclTemplate.h"
18#include "clang/AST/Expr.h"
19#include "clang/Basic/SourceLocation.h"
20#include "llvm/ADT/FoldingSet.h"
21#include "llvm/ADT/PointerUnion.h"
22#include "llvm/ADT/STLFunctionalExtras.h"
23#include "llvm/ADT/SmallVector.h"
24#include <optional>
25#include <utility>
26
27namespace clang {
28class Sema;
29
30enum { ConstraintAlignment = 8 };
31
32struct alignas(ConstraintAlignment) AtomicConstraint {
33 const Expr *ConstraintExpr;
34 const NamedDecl *ConstraintDecl;
35 std::optional<ArrayRef<TemplateArgumentLoc>> ParameterMapping;
36
37 AtomicConstraint(const Expr *ConstraintExpr, const NamedDecl *ConstraintDecl)
38 : ConstraintExpr(ConstraintExpr), ConstraintDecl(ConstraintDecl) {};
39
40 bool hasMatchingParameterMapping(ASTContext &C,
41 const AtomicConstraint &Other) const {
42 if (!ParameterMapping != !Other.ParameterMapping)
43 return false;
44 if (!ParameterMapping)
45 return true;
46 if (ParameterMapping->size() != Other.ParameterMapping->size())
47 return false;
48
49 for (unsigned I = 0, S = ParameterMapping->size(); I < S; ++I) {
50 llvm::FoldingSetNodeID IDA, IDB;
51 C.getCanonicalTemplateArgument(Arg: (*ParameterMapping)[I].getArgument())
52 .Profile(ID&: IDA, Context: C);
53 C.getCanonicalTemplateArgument(Arg: (*Other.ParameterMapping)[I].getArgument())
54 .Profile(ID&: IDB, Context: C);
55 if (IDA != IDB)
56 return false;
57 }
58 return true;
59 }
60};
61
62struct alignas(ConstraintAlignment) NormalizedConstraintPair;
63struct alignas(ConstraintAlignment) FoldExpandedConstraint;
64
65/// \brief A normalized constraint, as defined in C++ [temp.constr.normal], is
66/// either an atomic constraint, a conjunction of normalized constraints or a
67/// disjunction of normalized constraints.
68struct NormalizedConstraint {
69 friend class Sema;
70
71 enum CompoundConstraintKind { CCK_Conjunction, CCK_Disjunction };
72
73 using CompoundConstraint = llvm::PointerIntPair<NormalizedConstraintPair *, 1,
74 CompoundConstraintKind>;
75
76 llvm::PointerUnion<AtomicConstraint *, FoldExpandedConstraint *,
77 CompoundConstraint>
78 Constraint;
79
80 NormalizedConstraint(AtomicConstraint *C): Constraint{C} { };
81 NormalizedConstraint(FoldExpandedConstraint *C) : Constraint{C} {};
82
83 NormalizedConstraint(ASTContext &C, NormalizedConstraint LHS,
84 NormalizedConstraint RHS, CompoundConstraintKind Kind);
85
86 NormalizedConstraint(ASTContext &C, const NormalizedConstraint &Other);
87 NormalizedConstraint(NormalizedConstraint &&Other):
88 Constraint(Other.Constraint) {
89 Other.Constraint = nullptr;
90 }
91 NormalizedConstraint &operator=(const NormalizedConstraint &Other) = delete;
92 NormalizedConstraint &operator=(NormalizedConstraint &&Other) {
93 if (&Other != this) {
94 NormalizedConstraint Temp(std::move(Other));
95 std::swap(a&: Constraint, b&: Temp.Constraint);
96 }
97 return *this;
98 }
99
100 bool isAtomic() const { return llvm::isa<AtomicConstraint *>(Val: Constraint); }
101 bool isFoldExpanded() const {
102 return llvm::isa<FoldExpandedConstraint *>(Val: Constraint);
103 }
104 bool isCompound() const { return llvm::isa<CompoundConstraint>(Val: Constraint); }
105
106 CompoundConstraintKind getCompoundKind() const;
107
108 NormalizedConstraint &getLHS() const;
109 NormalizedConstraint &getRHS() const;
110
111 AtomicConstraint *getAtomicConstraint() const;
112
113 FoldExpandedConstraint *getFoldExpandedConstraint() const;
114
115private:
116 static std::optional<NormalizedConstraint>
117 fromAssociatedConstraints(Sema &S, const NamedDecl *D,
118 ArrayRef<AssociatedConstraint> ACs);
119 static std::optional<NormalizedConstraint>
120 fromConstraintExpr(Sema &S, const NamedDecl *D, const Expr *E);
121};
122
123struct alignas(ConstraintAlignment) NormalizedConstraintPair {
124 NormalizedConstraint LHS, RHS;
125};
126
127struct alignas(ConstraintAlignment) FoldExpandedConstraint {
128 enum class FoldOperatorKind { And, Or } Kind;
129 NormalizedConstraint Constraint;
130 const Expr *Pattern;
131
132 FoldExpandedConstraint(FoldOperatorKind K, NormalizedConstraint C,
133 const Expr *Pattern)
134 : Kind(K), Constraint(std::move(C)), Pattern(Pattern) {};
135
136 static bool AreCompatibleForSubsumption(const FoldExpandedConstraint &A,
137 const FoldExpandedConstraint &B);
138};
139
140const NormalizedConstraint *getNormalizedAssociatedConstraints(
141 Sema &S, const NamedDecl *ConstrainedDecl,
142 ArrayRef<AssociatedConstraint> AssociatedConstraints);
143
144/// \brief SubsumptionChecker establishes subsumption
145/// between two set of constraints.
146class SubsumptionChecker {
147public:
148 using SubsumptionCallable = llvm::function_ref<bool(
149 const AtomicConstraint &, const AtomicConstraint &)>;
150
151 SubsumptionChecker(Sema &SemaRef, SubsumptionCallable Callable = {});
152
153 std::optional<bool> Subsumes(const NamedDecl *DP,
154 ArrayRef<AssociatedConstraint> P,
155 const NamedDecl *DQ,
156 ArrayRef<AssociatedConstraint> Q);
157
158 bool Subsumes(const NormalizedConstraint *P, const NormalizedConstraint *Q);
159
160private:
161 Sema &SemaRef;
162 SubsumptionCallable Callable;
163
164 // Each Literal has a unique value that is enough to establish
165 // its identity.
166 // Some constraints (fold expended) require special subsumption
167 // handling logic beyond comparing values, so we store a flag
168 // to let us quickly dispatch to each kind of variable.
169 struct Literal {
170 enum Kind { Atomic, FoldExpanded };
171
172 unsigned Value : 16;
173 LLVM_PREFERRED_TYPE(Kind)
174 unsigned Kind : 1;
175
176 bool operator==(const Literal &Other) const { return Value == Other.Value; }
177 bool operator<(const Literal &Other) const { return Value < Other.Value; }
178 };
179 using Clause = llvm::SmallVector<Literal>;
180 using Formula = llvm::SmallVector<Clause, 5>;
181
182 struct CNFFormula : Formula {
183 static constexpr auto Kind = NormalizedConstraint::CCK_Conjunction;
184 using Formula::Formula;
185 };
186 struct DNFFormula : Formula {
187 static constexpr auto Kind = NormalizedConstraint::CCK_Disjunction;
188 using Formula::Formula;
189 };
190
191 struct MappedAtomicConstraint {
192 AtomicConstraint *Constraint;
193 Literal ID;
194 };
195
196 struct FoldExpendedConstraintKey {
197 FoldExpandedConstraint::FoldOperatorKind Kind;
198 AtomicConstraint *Constraint;
199 Literal ID;
200 };
201
202 llvm::DenseMap<const Expr *, llvm::SmallDenseMap<llvm::FoldingSetNodeID,
203 MappedAtomicConstraint>>
204 AtomicMap;
205
206 llvm::DenseMap<const Expr *, std::vector<FoldExpendedConstraintKey>> FoldMap;
207
208 // A map from a literal to a corresponding associated constraint.
209 // We do not have enough bits left for a pointer union here :(
210 llvm::DenseMap<uint16_t, void *> ReverseMap;
211
212 // Fold expanded constraints ask us to recursively establish subsumption.
213 // This caches the result.
214 llvm::SmallDenseMap<
215 std::pair<const FoldExpandedConstraint *, const FoldExpandedConstraint *>,
216 bool>
217 FoldSubsumptionCache;
218
219 // Each <atomic, fold expanded constraint> is represented as a single ID.
220 // This is intentionally kept small we can't handle a large number of
221 // constraints anyway.
222 uint16_t NextID;
223
224 bool Subsumes(const DNFFormula &P, const CNFFormula &Q);
225 bool Subsumes(Literal A, Literal B);
226 bool Subsumes(const FoldExpandedConstraint *A,
227 const FoldExpandedConstraint *B);
228 bool DNFSubsumes(const Clause &P, const Clause &Q);
229
230 CNFFormula CNF(const NormalizedConstraint &C);
231 DNFFormula DNF(const NormalizedConstraint &C);
232
233 template <typename FormulaType>
234 FormulaType Normalize(const NormalizedConstraint &C);
235 void AddUniqueClauseToFormula(Formula &F, Clause C);
236
237 Literal find(AtomicConstraint *);
238 Literal find(FoldExpandedConstraint *);
239
240 uint16_t getNewLiteralId();
241};
242
243} // clang
244
245#endif // LLVM_CLANG_SEMA_SEMACONCEPT_H
246