clang/Sema/SemaConcept.h

0001 //===-- SemaConcept.h - Semantic Analysis for Constraints and Concepts ----===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 //  This file provides semantic analysis for C++ constraints and concepts.
0010 ///
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_CLANG_SEMA_SEMACONCEPT_H
0014 #define LLVM_CLANG_SEMA_SEMACONCEPT_H
0015 #include "clang/AST/ASTConcept.h"
0016 #include "clang/AST/ASTContext.h"
0017 #include "clang/AST/Expr.h"
0018 #include "clang/AST/DeclTemplate.h"
0019 #include "clang/Basic/SourceLocation.h"
0020 #include "llvm/ADT/PointerUnion.h"
0021 #include "llvm/ADT/SmallVector.h"
0022 #include <optional>
0023 #include <string>
0024 #include <utility>
0025
0026 namespace clang {
0027 class Sema;
0028
0029 enum { ConstraintAlignment = 8 };
0030
0031 struct alignas(ConstraintAlignment) AtomicConstraint {
0032   const Expr *ConstraintExpr;
0033   NamedDecl *ConstraintDecl;
0034   std::optional<ArrayRef<TemplateArgumentLoc>> ParameterMapping;
0035
0036   AtomicConstraint(const Expr *ConstraintExpr, NamedDecl *ConstraintDecl)
0037       : ConstraintExpr(ConstraintExpr), ConstraintDecl(ConstraintDecl) {};
0038
0039   bool hasMatchingParameterMapping(ASTContext &C,
0040                                    const AtomicConstraint &Other) const {
0041     if (!ParameterMapping != !Other.ParameterMapping)
0042       return false;
0043     if (!ParameterMapping)
0044       return true;
0045     if (ParameterMapping->size() != Other.ParameterMapping->size())
0046       return false;
0047
0048     for (unsigned I = 0, S = ParameterMapping->size(); I < S; ++I) {
0049       llvm::FoldingSetNodeID IDA, IDB;
0050       C.getCanonicalTemplateArgument((*ParameterMapping)[I].getArgument())
0051           .Profile(IDA, C);
0052       C.getCanonicalTemplateArgument((*Other.ParameterMapping)[I].getArgument())
0053           .Profile(IDB, C);
0054       if (IDA != IDB)
0055         return false;
0056     }
0057     return true;
0058   }
0059
0060   bool subsumes(ASTContext &C, const AtomicConstraint &Other) const {
0061     // C++ [temp.constr.order] p2
0062     //   - an atomic constraint A subsumes another atomic constraint B
0063     //     if and only if the A and B are identical [...]
0064     //
0065     // C++ [temp.constr.atomic] p2
0066     //   Two atomic constraints are identical if they are formed from the
0067     //   same expression and the targets of the parameter mappings are
0068     //   equivalent according to the rules for expressions [...]
0069
0070     // We do not actually substitute the parameter mappings into the
0071     // constraint expressions, therefore the constraint expressions are
0072     // the originals, and comparing them will suffice.
0073     if (ConstraintExpr != Other.ConstraintExpr)
0074       return false;
0075
0076     // Check that the parameter lists are identical
0077     return hasMatchingParameterMapping(C, Other);
0078   }
0079 };
0080
0081 struct alignas(ConstraintAlignment) FoldExpandedConstraint;
0082
0083 using NormalFormConstraint =
0084     llvm::PointerUnion<AtomicConstraint *, FoldExpandedConstraint *>;
0085 struct NormalizedConstraint;
0086 using NormalForm =
0087     llvm::SmallVector<llvm::SmallVector<NormalFormConstraint, 2>, 4>;
0088
0089 // A constraint is in conjunctive normal form when it is a conjunction of
0090 // clauses where each clause is a disjunction of atomic constraints. For atomic
0091 // constraints A, B, and C, the constraint A  ∧ (B  ∨ C) is in conjunctive
0092 // normal form.
0093 NormalForm makeCNF(const NormalizedConstraint &Normalized);
0094
0095 // A constraint is in disjunctive normal form when it is a disjunction of
0096 // clauses where each clause is a conjunction of atomic constraints. For atomic
0097 // constraints A, B, and C, the disjunctive normal form of the constraint A
0098 //  ∧ (B  ∨ C) is (A  ∧ B)  ∨ (A  ∧ C).
0099 NormalForm makeDNF(const NormalizedConstraint &Normalized);
0100
0101 struct alignas(ConstraintAlignment) NormalizedConstraintPair;
0102
0103 /// \brief A normalized constraint, as defined in C++ [temp.constr.normal], is
0104 /// either an atomic constraint, a conjunction of normalized constraints or a
0105 /// disjunction of normalized constraints.
0106 struct NormalizedConstraint {
0107   friend class Sema;
0108
0109   enum CompoundConstraintKind { CCK_Conjunction, CCK_Disjunction };
0110
0111   using CompoundConstraint = llvm::PointerIntPair<NormalizedConstraintPair *, 1,
0112                                                   CompoundConstraintKind>;
0113
0114   llvm::PointerUnion<AtomicConstraint *, FoldExpandedConstraint *,
0115                      CompoundConstraint>
0116       Constraint;
0117
0118   NormalizedConstraint(AtomicConstraint *C): Constraint{C} { };
0119   NormalizedConstraint(FoldExpandedConstraint *C) : Constraint{C} {};
0120
0121   NormalizedConstraint(ASTContext &C, NormalizedConstraint LHS,
0122                        NormalizedConstraint RHS, CompoundConstraintKind Kind);
0123
0124   NormalizedConstraint(ASTContext &C, const NormalizedConstraint &Other);
0125   NormalizedConstraint(NormalizedConstraint &&Other):
0126       Constraint(Other.Constraint) {
0127     Other.Constraint = nullptr;
0128   }
0129   NormalizedConstraint &operator=(const NormalizedConstraint &Other) = delete;
0130   NormalizedConstraint &operator=(NormalizedConstraint &&Other) {
0131     if (&Other != this) {
0132       NormalizedConstraint Temp(std::move(Other));
0133       std::swap(Constraint, Temp.Constraint);
0134     }
0135     return *this;
0136   }
0137
0138   bool isAtomic() const { return llvm::isa<AtomicConstraint *>(Constraint); }
0139   bool isFoldExpanded() const {
0140     return llvm::isa<FoldExpandedConstraint *>(Constraint);
0141   }
0142   bool isCompound() const { return llvm::isa<CompoundConstraint>(Constraint); }
0143
0144   CompoundConstraintKind getCompoundKind() const;
0145
0146   NormalizedConstraint &getLHS() const;
0147   NormalizedConstraint &getRHS() const;
0148
0149   AtomicConstraint *getAtomicConstraint() const;
0150
0151   FoldExpandedConstraint *getFoldExpandedConstraint() const;
0152
0153 private:
0154   static std::optional<NormalizedConstraint>
0155   fromConstraintExprs(Sema &S, NamedDecl *D, ArrayRef<const Expr *> E);
0156   static std::optional<NormalizedConstraint>
0157   fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E);
0158 };
0159
0160 struct alignas(ConstraintAlignment) NormalizedConstraintPair {
0161   NormalizedConstraint LHS, RHS;
0162 };
0163
0164 struct alignas(ConstraintAlignment) FoldExpandedConstraint {
0165   enum class FoldOperatorKind { And, Or } Kind;
0166   NormalizedConstraint Constraint;
0167   const Expr *Pattern;
0168
0169   FoldExpandedConstraint(FoldOperatorKind K, NormalizedConstraint C,
0170                          const Expr *Pattern)
0171       : Kind(K), Constraint(std::move(C)), Pattern(Pattern) {};
0172
0173   template <typename AtomicSubsumptionEvaluator>
0174   bool subsumes(const FoldExpandedConstraint &Other,
0175                 const AtomicSubsumptionEvaluator &E) const;
0176
0177   static bool AreCompatibleForSubsumption(const FoldExpandedConstraint &A,
0178                                           const FoldExpandedConstraint &B);
0179 };
0180
0181 const NormalizedConstraint *getNormalizedAssociatedConstraints(
0182     Sema &S, NamedDecl *ConstrainedDecl,
0183     ArrayRef<const Expr *> AssociatedConstraints);
0184
0185 template <typename AtomicSubsumptionEvaluator>
0186 bool subsumes(const NormalForm &PDNF, const NormalForm &QCNF,
0187               const AtomicSubsumptionEvaluator &E) {
0188   // C++ [temp.constr.order] p2
0189   //   Then, P subsumes Q if and only if, for every disjunctive clause Pi in the
0190   //   disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in
0191   //   the conjuctive normal form of Q, where [...]
0192   for (const auto &Pi : PDNF) {
0193     for (const auto &Qj : QCNF) {
0194       // C++ [temp.constr.order] p2
0195       //   - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
0196       //     and only if there exists an atomic constraint Pia in Pi for which
0197       //     there exists an atomic constraint, Qjb, in Qj such that Pia
0198       //     subsumes Qjb.
0199       bool Found = false;
0200       for (NormalFormConstraint Pia : Pi) {
0201         for (NormalFormConstraint Qjb : Qj) {
0202           if (isa<FoldExpandedConstraint *>(Pia) &&
0203               isa<FoldExpandedConstraint *>(Qjb)) {
0204             if (cast<FoldExpandedConstraint *>(Pia)->subsumes(
0205                     *cast<FoldExpandedConstraint *>(Qjb), E)) {
0206               Found = true;
0207               break;
0208             }
0209           } else if (isa<AtomicConstraint *>(Pia) &&
0210                      isa<AtomicConstraint *>(Qjb)) {
0211             if (E(*cast<AtomicConstraint *>(Pia),
0212                   *cast<AtomicConstraint *>(Qjb))) {
0213               Found = true;
0214               break;
0215             }
0216           }
0217         }
0218         if (Found)
0219           break;
0220       }
0221       if (!Found)
0222         return false;
0223     }
0224   }
0225   return true;
0226 }
0227
0228 template <typename AtomicSubsumptionEvaluator>
0229 bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P, NamedDecl *DQ,
0230               ArrayRef<const Expr *> Q, bool &Subsumes,
0231               const AtomicSubsumptionEvaluator &E) {
0232   // C++ [temp.constr.order] p2
0233   //   In order to determine if a constraint P subsumes a constraint Q, P is
0234   //   transformed into disjunctive normal form, and Q is transformed into
0235   //   conjunctive normal form. [...]
0236   const NormalizedConstraint *PNormalized =
0237       getNormalizedAssociatedConstraints(S, DP, P);
0238   if (!PNormalized)
0239     return true;
0240   NormalForm PDNF = makeDNF(*PNormalized);
0241
0242   const NormalizedConstraint *QNormalized =
0243       getNormalizedAssociatedConstraints(S, DQ, Q);
0244   if (!QNormalized)
0245     return true;
0246   NormalForm QCNF = makeCNF(*QNormalized);
0247
0248   Subsumes = subsumes(PDNF, QCNF, E);
0249   return false;
0250 }
0251
0252 template <typename AtomicSubsumptionEvaluator>
0253 bool FoldExpandedConstraint::subsumes(
0254     const FoldExpandedConstraint &Other,
0255     const AtomicSubsumptionEvaluator &E) const {
0256
0257   // [C++26] [temp.constr.order]
0258   // a fold expanded constraint A subsumes another fold expanded constraint B if
0259   // they are compatible for subsumption, have the same fold-operator, and the
0260   // constraint of A subsumes that of B
0261
0262   if (Kind != Other.Kind || !AreCompatibleForSubsumption(*this, Other))
0263     return false;
0264
0265   NormalForm PDNF = makeDNF(this->Constraint);
0266   NormalForm QCNF = makeCNF(Other.Constraint);
0267   return clang::subsumes(PDNF, QCNF, E);
0268 }
0269
0270 } // clang
0271
0272 #endif // LLVM_CLANG_SEMA_SEMACONCEPT_H