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