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 27 namespace clang { 28 class Sema; 29 30 enum { ConstraintAlignment = 8 }; 31 32 struct alignas(ConstraintAlignment) AtomicConstraint { 33 const Expr *ConstraintExpr; 34 const NamedDecl *ConstraintDecl; 35 std::optional<ArrayRef<TemplateArgumentLoc>> ParameterMapping; 36 AtomicConstraintAtomicConstraint37 AtomicConstraint(const Expr *ConstraintExpr, const NamedDecl *ConstraintDecl) 38 : ConstraintExpr(ConstraintExpr), ConstraintDecl(ConstraintDecl) {}; 39 hasMatchingParameterMappingAtomicConstraint40 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((*ParameterMapping)[I].getArgument()) 52 .Profile(IDA, C); 53 C.getCanonicalTemplateArgument((*Other.ParameterMapping)[I].getArgument()) 54 .Profile(IDB, C); 55 if (IDA != IDB) 56 return false; 57 } 58 return true; 59 } 60 }; 61 62 struct alignas(ConstraintAlignment) NormalizedConstraintPair; 63 struct 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. 68 struct 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 NormalizedConstraintNormalizedConstraint80 NormalizedConstraint(AtomicConstraint *C): Constraint{C} { }; NormalizedConstraintNormalizedConstraint81 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); NormalizedConstraintNormalizedConstraint87 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(Constraint, Temp.Constraint); 96 } 97 return *this; 98 } 99 isAtomicNormalizedConstraint100 bool isAtomic() const { return llvm::isa<AtomicConstraint *>(Constraint); } isFoldExpandedNormalizedConstraint101 bool isFoldExpanded() const { 102 return llvm::isa<FoldExpandedConstraint *>(Constraint); 103 } isCompoundNormalizedConstraint104 bool isCompound() const { return llvm::isa<CompoundConstraint>(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 115 private: 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 123 struct alignas(ConstraintAlignment) NormalizedConstraintPair { 124 NormalizedConstraint LHS, RHS; 125 }; 126 127 struct alignas(ConstraintAlignment) FoldExpandedConstraint { 128 enum class FoldOperatorKind { And, Or } Kind; 129 NormalizedConstraint Constraint; 130 const Expr *Pattern; 131 FoldExpandedConstraintFoldExpandedConstraint132 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 140 const NormalizedConstraint *getNormalizedAssociatedConstraints( 141 Sema &S, const NamedDecl *ConstrainedDecl, 142 ArrayRef<AssociatedConstraint> AssociatedConstraints); 143 144 /// \brief SubsumptionChecker establishes subsumption 145 /// between two set of constraints. 146 class SubsumptionChecker { 147 public: 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 160 private: 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