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/Expr.h" 18 #include "clang/AST/DeclTemplate.h" 19 #include "clang/Basic/SourceLocation.h" 20 #include "llvm/ADT/PointerUnion.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include <optional> 23 #include <string> 24 #include <utility> 25 26 namespace clang { 27 class Sema; 28 29 enum { ConstraintAlignment = 8 }; 30 31 struct alignas(ConstraintAlignment) AtomicConstraint { 32 const Expr *ConstraintExpr; 33 NamedDecl *ConstraintDecl; 34 std::optional<ArrayRef<TemplateArgumentLoc>> ParameterMapping; 35 36 AtomicConstraint(const Expr *ConstraintExpr, NamedDecl *ConstraintDecl) 37 : ConstraintExpr(ConstraintExpr), ConstraintDecl(ConstraintDecl) {}; 38 39 bool hasMatchingParameterMapping(ASTContext &C, 40 const AtomicConstraint &Other) const { 41 if (!ParameterMapping != !Other.ParameterMapping) 42 return false; 43 if (!ParameterMapping) 44 return true; 45 if (ParameterMapping->size() != Other.ParameterMapping->size()) 46 return false; 47 48 for (unsigned I = 0, S = ParameterMapping->size(); I < S; ++I) { 49 llvm::FoldingSetNodeID IDA, IDB; 50 C.getCanonicalTemplateArgument((*ParameterMapping)[I].getArgument()) 51 .Profile(IDA, C); 52 C.getCanonicalTemplateArgument((*Other.ParameterMapping)[I].getArgument()) 53 .Profile(IDB, C); 54 if (IDA != IDB) 55 return false; 56 } 57 return true; 58 } 59 60 bool subsumes(ASTContext &C, const AtomicConstraint &Other) const { 61 // C++ [temp.constr.order] p2 62 // - an atomic constraint A subsumes another atomic constraint B 63 // if and only if the A and B are identical [...] 64 // 65 // C++ [temp.constr.atomic] p2 66 // Two atomic constraints are identical if they are formed from the 67 // same expression and the targets of the parameter mappings are 68 // equivalent according to the rules for expressions [...] 69 70 // We do not actually substitute the parameter mappings into the 71 // constraint expressions, therefore the constraint expressions are 72 // the originals, and comparing them will suffice. 73 if (ConstraintExpr != Other.ConstraintExpr) 74 return false; 75 76 // Check that the parameter lists are identical 77 return hasMatchingParameterMapping(C, Other); 78 } 79 }; 80 81 struct alignas(ConstraintAlignment) FoldExpandedConstraint; 82 83 using NormalFormConstraint = 84 llvm::PointerUnion<AtomicConstraint *, FoldExpandedConstraint *>; 85 struct NormalizedConstraint; 86 using NormalForm = 87 llvm::SmallVector<llvm::SmallVector<NormalFormConstraint, 2>, 4>; 88 89 // A constraint is in conjunctive normal form when it is a conjunction of 90 // clauses where each clause is a disjunction of atomic constraints. For atomic 91 // constraints A, B, and C, the constraint A ∧ (B ∨ C) is in conjunctive 92 // normal form. 93 NormalForm makeCNF(const NormalizedConstraint &Normalized); 94 95 // A constraint is in disjunctive normal form when it is a disjunction of 96 // clauses where each clause is a conjunction of atomic constraints. For atomic 97 // constraints A, B, and C, the disjunctive normal form of the constraint A 98 // ∧ (B ∨ C) is (A ∧ B) ∨ (A ∧ C). 99 NormalForm makeDNF(const NormalizedConstraint &Normalized); 100 101 struct alignas(ConstraintAlignment) NormalizedConstraintPair; 102 103 /// \brief A normalized constraint, as defined in C++ [temp.constr.normal], is 104 /// either an atomic constraint, a conjunction of normalized constraints or a 105 /// disjunction of normalized constraints. 106 struct NormalizedConstraint { 107 friend class Sema; 108 109 enum CompoundConstraintKind { CCK_Conjunction, CCK_Disjunction }; 110 111 using CompoundConstraint = llvm::PointerIntPair<NormalizedConstraintPair *, 1, 112 CompoundConstraintKind>; 113 114 llvm::PointerUnion<AtomicConstraint *, FoldExpandedConstraint *, 115 CompoundConstraint> 116 Constraint; 117 118 NormalizedConstraint(AtomicConstraint *C): Constraint{C} { }; 119 NormalizedConstraint(FoldExpandedConstraint *C) : Constraint{C} {}; 120 121 NormalizedConstraint(ASTContext &C, NormalizedConstraint LHS, 122 NormalizedConstraint RHS, CompoundConstraintKind Kind); 123 124 NormalizedConstraint(ASTContext &C, const NormalizedConstraint &Other); 125 NormalizedConstraint(NormalizedConstraint &&Other): 126 Constraint(Other.Constraint) { 127 Other.Constraint = nullptr; 128 } 129 NormalizedConstraint &operator=(const NormalizedConstraint &Other) = delete; 130 NormalizedConstraint &operator=(NormalizedConstraint &&Other) { 131 if (&Other != this) { 132 NormalizedConstraint Temp(std::move(Other)); 133 std::swap(Constraint, Temp.Constraint); 134 } 135 return *this; 136 } 137 138 bool isAtomic() const { return llvm::isa<AtomicConstraint *>(Constraint); } 139 bool isFoldExpanded() const { 140 return llvm::isa<FoldExpandedConstraint *>(Constraint); 141 } 142 bool isCompound() const { return llvm::isa<CompoundConstraint>(Constraint); } 143 144 CompoundConstraintKind getCompoundKind() const; 145 146 NormalizedConstraint &getLHS() const; 147 NormalizedConstraint &getRHS() const; 148 149 AtomicConstraint *getAtomicConstraint() const; 150 151 FoldExpandedConstraint *getFoldExpandedConstraint() const; 152 153 private: 154 static std::optional<NormalizedConstraint> 155 fromConstraintExprs(Sema &S, NamedDecl *D, ArrayRef<const Expr *> E); 156 static std::optional<NormalizedConstraint> 157 fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E); 158 }; 159 160 struct alignas(ConstraintAlignment) NormalizedConstraintPair { 161 NormalizedConstraint LHS, RHS; 162 }; 163 164 struct alignas(ConstraintAlignment) FoldExpandedConstraint { 165 enum class FoldOperatorKind { And, Or } Kind; 166 NormalizedConstraint Constraint; 167 const Expr *Pattern; 168 169 FoldExpandedConstraint(FoldOperatorKind K, NormalizedConstraint C, 170 const Expr *Pattern) 171 : Kind(K), Constraint(std::move(C)), Pattern(Pattern) {}; 172 173 template <typename AtomicSubsumptionEvaluator> 174 bool subsumes(const FoldExpandedConstraint &Other, 175 const AtomicSubsumptionEvaluator &E) const; 176 177 static bool AreCompatibleForSubsumption(const FoldExpandedConstraint &A, 178 const FoldExpandedConstraint &B); 179 }; 180 181 const NormalizedConstraint *getNormalizedAssociatedConstraints( 182 Sema &S, NamedDecl *ConstrainedDecl, 183 ArrayRef<const Expr *> AssociatedConstraints); 184 185 template <typename AtomicSubsumptionEvaluator> 186 bool subsumes(const NormalForm &PDNF, const NormalForm &QCNF, 187 const AtomicSubsumptionEvaluator &E) { 188 // C++ [temp.constr.order] p2 189 // Then, P subsumes Q if and only if, for every disjunctive clause Pi in the 190 // disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in 191 // the conjuctive normal form of Q, where [...] 192 for (const auto &Pi : PDNF) { 193 for (const auto &Qj : QCNF) { 194 // C++ [temp.constr.order] p2 195 // - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if 196 // and only if there exists an atomic constraint Pia in Pi for which 197 // there exists an atomic constraint, Qjb, in Qj such that Pia 198 // subsumes Qjb. 199 bool Found = false; 200 for (NormalFormConstraint Pia : Pi) { 201 for (NormalFormConstraint Qjb : Qj) { 202 if (isa<FoldExpandedConstraint *>(Pia) && 203 isa<FoldExpandedConstraint *>(Qjb)) { 204 if (cast<FoldExpandedConstraint *>(Pia)->subsumes( 205 *cast<FoldExpandedConstraint *>(Qjb), E)) { 206 Found = true; 207 break; 208 } 209 } else if (isa<AtomicConstraint *>(Pia) && 210 isa<AtomicConstraint *>(Qjb)) { 211 if (E(*cast<AtomicConstraint *>(Pia), 212 *cast<AtomicConstraint *>(Qjb))) { 213 Found = true; 214 break; 215 } 216 } 217 } 218 if (Found) 219 break; 220 } 221 if (!Found) 222 return false; 223 } 224 } 225 return true; 226 } 227 228 template <typename AtomicSubsumptionEvaluator> 229 bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P, NamedDecl *DQ, 230 ArrayRef<const Expr *> Q, bool &Subsumes, 231 const AtomicSubsumptionEvaluator &E) { 232 // C++ [temp.constr.order] p2 233 // In order to determine if a constraint P subsumes a constraint Q, P is 234 // transformed into disjunctive normal form, and Q is transformed into 235 // conjunctive normal form. [...] 236 const NormalizedConstraint *PNormalized = 237 getNormalizedAssociatedConstraints(S, DP, P); 238 if (!PNormalized) 239 return true; 240 NormalForm PDNF = makeDNF(*PNormalized); 241 242 const NormalizedConstraint *QNormalized = 243 getNormalizedAssociatedConstraints(S, DQ, Q); 244 if (!QNormalized) 245 return true; 246 NormalForm QCNF = makeCNF(*QNormalized); 247 248 Subsumes = subsumes(PDNF, QCNF, E); 249 return false; 250 } 251 252 template <typename AtomicSubsumptionEvaluator> 253 bool FoldExpandedConstraint::subsumes( 254 const FoldExpandedConstraint &Other, 255 const AtomicSubsumptionEvaluator &E) const { 256 257 // [C++26] [temp.constr.order] 258 // a fold expanded constraint A subsumes another fold expanded constraint B if 259 // they are compatible for subsumption, have the same fold-operator, and the 260 // constraint of A subsumes that of B 261 262 if (Kind != Other.Kind || !AreCompatibleForSubsumption(*this, Other)) 263 return false; 264 265 NormalForm PDNF = makeDNF(this->Constraint); 266 NormalForm QCNF = makeCNF(Other.Constraint); 267 return clang::subsumes(PDNF, QCNF, E); 268 } 269 270 } // clang 271 272 #endif // LLVM_CLANG_SEMA_SEMACONCEPT_H 273