Reapply [Clang][C++26] Implement "Ordering of constraints involving fold expressions (#99022)

Implement https://isocpp.org/files/papers/P2963R3.pdf

1 files changed, 412 insertions, 200 deletions

diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index 5489115..84c5753 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -65,6 +65,7 @@ public:
 
   const Expr *getLHS() const { return LHS; }
   const Expr *getRHS() const { return RHS; }
+  OverloadedOperatorKind getOp() const { return Op; }
 
   ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS) const {
     return recreateBinOp(SemaRef, LHS, const_cast<Expr *>(getRHS()));
@@ -177,77 +178,177 @@ struct SatisfactionStackRAII {
 };
 } // namespace
 
-template <typename AtomicEvaluator>
+template <typename ConstraintEvaluator>
 static ExprResult
 calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
                                 ConstraintSatisfaction &Satisfaction,
-                                AtomicEvaluator &&Evaluator) {
-  ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
+                                const ConstraintEvaluator &Evaluator);
 
-  if (LogicalBinOp BO = ConstraintExpr) {
-    size_t EffectiveDetailEndIndex = Satisfaction.Details.size();
-    ExprResult LHSRes = calculateConstraintSatisfaction(
-        S, BO.getLHS(), Satisfaction, Evaluator);
+template <typename ConstraintEvaluator>
+static ExprResult
+calculateConstraintSatisfaction(Sema &S, const Expr *LHS,
+                                OverloadedOperatorKind Op, const Expr *RHS,
+                                ConstraintSatisfaction &Satisfaction,
+                                const ConstraintEvaluator &Evaluator) {
+  size_t EffectiveDetailEndIndex = Satisfaction.Details.size();
 
-    if (LHSRes.isInvalid())
-      return ExprError();
+  ExprResult LHSRes =
+      calculateConstraintSatisfaction(S, LHS, Satisfaction, Evaluator);
 
-    bool IsLHSSatisfied = Satisfaction.IsSatisfied;
+  if (LHSRes.isInvalid())
+    return ExprError();
 
-    if (BO.isOr() && IsLHSSatisfied)
-      // [temp.constr.op] p3
-      //    A disjunction is a constraint taking two operands. To determine if
-      //    a disjunction is satisfied, the satisfaction of the first operand
-      //    is checked. If that is satisfied, the disjunction is satisfied.
-      //    Otherwise, the disjunction is satisfied if and only if the second
-      //    operand is satisfied.
-      // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
-      return LHSRes;
+  bool IsLHSSatisfied = Satisfaction.IsSatisfied;
+
+  if (Op == clang::OO_PipePipe && IsLHSSatisfied)
+    // [temp.constr.op] p3
+    //    A disjunction is a constraint taking two operands. To determine if
+    //    a disjunction is satisfied, the satisfaction of the first operand
+    //    is checked. If that is satisfied, the disjunction is satisfied.
+    //    Otherwise, the disjunction is satisfied if and only if the second
+    //    operand is satisfied.
+    // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
+    return LHSRes;
+
+  if (Op == clang::OO_AmpAmp && !IsLHSSatisfied)
+    // [temp.constr.op] p2
+    //    A conjunction is a constraint taking two operands. To determine if
+    //    a conjunction is satisfied, the satisfaction of the first operand
+    //    is checked. If that is not satisfied, the conjunction is not
+    //    satisfied. Otherwise, the conjunction is satisfied if and only if
+    //    the second operand is satisfied.
+    // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
+    return LHSRes;
+
+  ExprResult RHSRes =
+      calculateConstraintSatisfaction(S, RHS, Satisfaction, Evaluator);
+  if (RHSRes.isInvalid())
+    return ExprError();
 
-    if (BO.isAnd() && !IsLHSSatisfied)
-      // [temp.constr.op] p2
-      //    A conjunction is a constraint taking two operands. To determine if
-      //    a conjunction is satisfied, the satisfaction of the first operand
-      //    is checked. If that is not satisfied, the conjunction is not
-      //    satisfied. Otherwise, the conjunction is satisfied if and only if
-      //    the second operand is satisfied.
-      // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
-      return LHSRes;
-
-    ExprResult RHSRes = calculateConstraintSatisfaction(
-        S, BO.getRHS(), Satisfaction, std::forward<AtomicEvaluator>(Evaluator));
-    if (RHSRes.isInvalid())
+  bool IsRHSSatisfied = Satisfaction.IsSatisfied;
+  // Current implementation adds diagnostic information about the falsity
+  // of each false atomic constraint expression when it evaluates them.
+  // When the evaluation results to `false || true`, the information
+  // generated during the evaluation of left-hand side is meaningless
+  // because the whole expression evaluates to true.
+  // The following code removes the irrelevant diagnostic information.
+  // FIXME: We should probably delay the addition of diagnostic information
+  // until we know the entire expression is false.
+  if (Op == clang::OO_PipePipe && IsRHSSatisfied) {
+    auto EffectiveDetailEnd = Satisfaction.Details.begin();
+    std::advance(EffectiveDetailEnd, EffectiveDetailEndIndex);
+    Satisfaction.Details.erase(EffectiveDetailEnd, Satisfaction.Details.end());
+  }
+
+  if (!LHSRes.isUsable() || !RHSRes.isUsable())
+    return ExprEmpty();
+
+  return BinaryOperator::Create(S.Context, LHSRes.get(), RHSRes.get(),
+                                BinaryOperator::getOverloadedOpcode(Op),
+                                S.Context.BoolTy, VK_PRValue, OK_Ordinary,
+                                LHS->getBeginLoc(), FPOptionsOverride{});
+}
+
+template <typename ConstraintEvaluator>
+static ExprResult
+calculateConstraintSatisfaction(Sema &S, const CXXFoldExpr *FE,
+                                ConstraintSatisfaction &Satisfaction,
+                                const ConstraintEvaluator &Evaluator) {
+  bool Conjunction = FE->getOperator() == BinaryOperatorKind::BO_LAnd;
+  size_t EffectiveDetailEndIndex = Satisfaction.Details.size();
+
+  ExprResult Out;
+  if (FE->isLeftFold() && FE->getInit()) {
+    Out = calculateConstraintSatisfaction(S, FE->getInit(), Satisfaction,
+                                          Evaluator);
+    if (Out.isInvalid())
       return ExprError();
 
+    // If the first clause of a conjunction is not satisfied,
+    // or if the first clause of a disjection is satisfied,
+    // we have established satisfaction of the whole constraint
+    // and we should not continue further.
+    if (Conjunction != Satisfaction.IsSatisfied)
+      return Out;
+  }
+  std::optional<unsigned> NumExpansions =
+      Evaluator.EvaluateFoldExpandedConstraintSize(FE);
+  if (!NumExpansions)
+    return ExprError();
+  for (unsigned I = 0; I < *NumExpansions; I++) {
+    Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(S, I);
+    ExprResult Res = calculateConstraintSatisfaction(S, FE->getPattern(),
+                                                     Satisfaction, Evaluator);
+    if (Res.isInvalid())
+      return ExprError();
     bool IsRHSSatisfied = Satisfaction.IsSatisfied;
-    // Current implementation adds diagnostic information about the falsity
-    // of each false atomic constraint expression when it evaluates them.
-    // When the evaluation results to `false || true`, the information
-    // generated during the evaluation of left-hand side is meaningless
-    // because the whole expression evaluates to true.
-    // The following code removes the irrelevant diagnostic information.
-    // FIXME: We should probably delay the addition of diagnostic information
-    // until we know the entire expression is false.
-    if (BO.isOr() && IsRHSSatisfied) {
+    if (!Conjunction && IsRHSSatisfied) {
       auto EffectiveDetailEnd = Satisfaction.Details.begin();
       std::advance(EffectiveDetailEnd, EffectiveDetailEndIndex);
       Satisfaction.Details.erase(EffectiveDetailEnd,
                                  Satisfaction.Details.end());
     }
+    if (Out.isUnset())
+      Out = Res;
+    else if (!Res.isUnset()) {
+      Out = BinaryOperator::Create(
+          S.Context, Out.get(), Res.get(), FE->getOperator(), S.Context.BoolTy,
+          VK_PRValue, OK_Ordinary, FE->getBeginLoc(), FPOptionsOverride{});
+    }
+    if (Conjunction != IsRHSSatisfied)
+      return Out;
+  }
 
-    return BO.recreateBinOp(S, LHSRes, RHSRes);
+  if (FE->isRightFold() && FE->getInit()) {
+    ExprResult Res = calculateConstraintSatisfaction(S, FE->getInit(),
+                                                     Satisfaction, Evaluator);
+    if (Out.isInvalid())
+      return ExprError();
+
+    if (Out.isUnset())
+      Out = Res;
+    else if (!Res.isUnset()) {
+      Out = BinaryOperator::Create(
+          S.Context, Out.get(), Res.get(), FE->getOperator(), S.Context.BoolTy,
+          VK_PRValue, OK_Ordinary, FE->getBeginLoc(), FPOptionsOverride{});
+    }
   }
 
+  if (Out.isUnset()) {
+    Satisfaction.IsSatisfied = Conjunction;
+    Out = S.BuildEmptyCXXFoldExpr(FE->getBeginLoc(), FE->getOperator());
+  }
+  return Out;
+}
+
+template <typename ConstraintEvaluator>
+static ExprResult
+calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
+                                ConstraintSatisfaction &Satisfaction,
+                                const ConstraintEvaluator &Evaluator) {
+  ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
+
+  if (LogicalBinOp BO = ConstraintExpr)
+    return calculateConstraintSatisfaction(
+        S, BO.getLHS(), BO.getOp(), BO.getRHS(), Satisfaction, Evaluator);
+
   if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr)) {
     // These aren't evaluated, so we don't care about cleanups, so we can just
     // evaluate these as if the cleanups didn't exist.
-    return calculateConstraintSatisfaction(
-        S, C->getSubExpr(), Satisfaction,
-        std::forward<AtomicEvaluator>(Evaluator));
+    return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction,
+                                           Evaluator);
+  }
+
+  if (auto *FE = dyn_cast<CXXFoldExpr>(ConstraintExpr);
+      FE && S.getLangOpts().CPlusPlus26 &&
+      (FE->getOperator() == BinaryOperatorKind::BO_LAnd ||
+       FE->getOperator() == BinaryOperatorKind::BO_LOr)) {
+    return calculateConstraintSatisfaction(S, FE, Satisfaction, Evaluator);
   }
 
   // An atomic constraint expression
-  ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr);
+  ExprResult SubstitutedAtomicExpr =
+      Evaluator.EvaluateAtomicConstraint(ConstraintExpr);
 
   if (SubstitutedAtomicExpr.isInvalid())
     return ExprError();
@@ -334,91 +435,132 @@ static ExprResult calculateConstraintSatisfaction(
     Sema &S, const NamedDecl *Template, SourceLocation TemplateNameLoc,
     const MultiLevelTemplateArgumentList &MLTAL, const Expr *ConstraintExpr,
     ConstraintSatisfaction &Satisfaction) {
-  return calculateConstraintSatisfaction(
-      S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) {
-        EnterExpressionEvaluationContext ConstantEvaluated(
-            S, Sema::ExpressionEvaluationContext::ConstantEvaluated,
-            Sema::ReuseLambdaContextDecl);
-
-        // Atomic constraint - substitute arguments and check satisfaction.
-        ExprResult SubstitutedExpression;
-        {
-          TemplateDeductionInfo Info(TemplateNameLoc);
-          Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(),
-              Sema::InstantiatingTemplate::ConstraintSubstitution{},
-              const_cast<NamedDecl *>(Template), Info,
-              AtomicExpr->getSourceRange());
-          if (Inst.isInvalid())
+
+  struct ConstraintEvaluator {
+    Sema &S;
+    const NamedDecl *Template;
+    SourceLocation TemplateNameLoc;
+    const MultiLevelTemplateArgumentList &MLTAL;
+    ConstraintSatisfaction &Satisfaction;
+
+    ExprResult EvaluateAtomicConstraint(const Expr *AtomicExpr) const {
+      EnterExpressionEvaluationContext ConstantEvaluated(
+          S, Sema::ExpressionEvaluationContext::ConstantEvaluated,
+          Sema::ReuseLambdaContextDecl);
+
+      // Atomic constraint - substitute arguments and check satisfaction.
+      ExprResult SubstitutedExpression;
+      {
+        TemplateDeductionInfo Info(TemplateNameLoc);
+        Sema::InstantiatingTemplate Inst(
+            S, AtomicExpr->getBeginLoc(),
+            Sema::InstantiatingTemplate::ConstraintSubstitution{},
+            const_cast<NamedDecl *>(Template), Info,
+            AtomicExpr->getSourceRange());
+        if (Inst.isInvalid())
+          return ExprError();
+
+        llvm::FoldingSetNodeID ID;
+        if (Template &&
+            DiagRecursiveConstraintEval(S, ID, Template, AtomicExpr, MLTAL)) {
+          Satisfaction.IsSatisfied = false;
+          Satisfaction.ContainsErrors = true;
+          return ExprEmpty();
+        }
+
+        SatisfactionStackRAII StackRAII(S, Template, ID);
+
+        // We do not want error diagnostics escaping here.
+        Sema::SFINAETrap Trap(S);
+        SubstitutedExpression =
+            S.SubstConstraintExpr(const_cast<Expr *>(AtomicExpr), MLTAL);
+
+        if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {
+          // C++2a [temp.constr.atomic]p1
+          //   ...If substitution results in an invalid type or expression, the
+          //   constraint is not satisfied.
+          if (!Trap.hasErrorOccurred())
+            // A non-SFINAE error has occurred as a result of this
+            // substitution.
             return ExprError();
 
-          llvm::FoldingSetNodeID ID;
-          if (Template &&
-              DiagRecursiveConstraintEval(S, ID, Template, AtomicExpr, MLTAL)) {
-            Satisfaction.IsSatisfied = false;
-            Satisfaction.ContainsErrors = true;
-            return ExprEmpty();
-          }
-
-          SatisfactionStackRAII StackRAII(S, Template, ID);
-
-          // We do not want error diagnostics escaping here.
-          Sema::SFINAETrap Trap(S);
-          SubstitutedExpression =
-              S.SubstConstraintExpr(const_cast<Expr *>(AtomicExpr), MLTAL);
-
-          if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {
-            // C++2a [temp.constr.atomic]p1
-            //   ...If substitution results in an invalid type or expression, the
-            //   constraint is not satisfied.
-            if (!Trap.hasErrorOccurred())
-              // A non-SFINAE error has occurred as a result of this
-              // substitution.
-              return ExprError();
-
-            PartialDiagnosticAt SubstDiag{SourceLocation(),
-                                          PartialDiagnostic::NullDiagnostic()};
-            Info.takeSFINAEDiagnostic(SubstDiag);
-            // FIXME: Concepts: This is an unfortunate consequence of there
-            //  being no serialization code for PartialDiagnostics and the fact
-            //  that serializing them would likely take a lot more storage than
-            //  just storing them as strings. We would still like, in the
-            //  future, to serialize the proper PartialDiagnostic as serializing
-            //  it as a string defeats the purpose of the diagnostic mechanism.
-            SmallString<128> DiagString;
-            DiagString = ": ";
-            SubstDiag.second.EmitToString(S.getDiagnostics(), DiagString);
-            unsigned MessageSize = DiagString.size();
-            char *Mem = new (S.Context) char[MessageSize];
-            memcpy(Mem, DiagString.c_str(), MessageSize);
-            Satisfaction.Details.emplace_back(
-                new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
-                    SubstDiag.first, StringRef(Mem, MessageSize)});
-            Satisfaction.IsSatisfied = false;
-            return ExprEmpty();
-          }
+          PartialDiagnosticAt SubstDiag{SourceLocation(),
+                                        PartialDiagnostic::NullDiagnostic()};
+          Info.takeSFINAEDiagnostic(SubstDiag);
+          // FIXME: Concepts: This is an unfortunate consequence of there
+          //  being no serialization code for PartialDiagnostics and the fact
+          //  that serializing them would likely take a lot more storage than
+          //  just storing them as strings. We would still like, in the
+          //  future, to serialize the proper PartialDiagnostic as serializing
+          //  it as a string defeats the purpose of the diagnostic mechanism.
+          SmallString<128> DiagString;
+          DiagString = ": ";
+          SubstDiag.second.EmitToString(S.getDiagnostics(), DiagString);
+          unsigned MessageSize = DiagString.size();
+          char *Mem = new (S.Context) char[MessageSize];
+          memcpy(Mem, DiagString.c_str(), MessageSize);
+          Satisfaction.Details.emplace_back(
+              new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
+                  SubstDiag.first, StringRef(Mem, MessageSize)});
+          Satisfaction.IsSatisfied = false;
+          return ExprEmpty();
         }
+      }
 
-        if (!S.CheckConstraintExpression(SubstitutedExpression.get()))
-          return ExprError();
+      if (!S.CheckConstraintExpression(SubstitutedExpression.get()))
+        return ExprError();
+
+      // [temp.constr.atomic]p3: To determine if an atomic constraint is
+      // satisfied, the parameter mapping and template arguments are first
+      // substituted into its expression.  If substitution results in an
+      // invalid type or expression, the constraint is not satisfied.
+      // Otherwise, the lvalue-to-rvalue conversion is performed if necessary,
+      // and E shall be a constant expression of type bool.
+      //
+      // Perform the L to R Value conversion if necessary. We do so for all
+      // non-PRValue categories, else we fail to extend the lifetime of
+      // temporaries, and that fails the constant expression check.
+      if (!SubstitutedExpression.get()->isPRValue())
+        SubstitutedExpression = ImplicitCastExpr::Create(
+            S.Context, SubstitutedExpression.get()->getType(),
+            CK_LValueToRValue, SubstitutedExpression.get(),
+            /*BasePath=*/nullptr, VK_PRValue, FPOptionsOverride());
+
+      return SubstitutedExpression;
+    }
 
-        // [temp.constr.atomic]p3: To determine if an atomic constraint is
-        // satisfied, the parameter mapping and template arguments are first
-        // substituted into its expression.  If substitution results in an
-        // invalid type or expression, the constraint is not satisfied.
-        // Otherwise, the lvalue-to-rvalue conversion is performed if necessary,
-        // and E shall be a constant expression of type bool.
-        //
-        // Perform the L to R Value conversion if necessary. We do so for all
-        // non-PRValue categories, else we fail to extend the lifetime of
-        // temporaries, and that fails the constant expression check.
-        if (!SubstitutedExpression.get()->isPRValue())
-          SubstitutedExpression = ImplicitCastExpr::Create(
-              S.Context, SubstitutedExpression.get()->getType(),
-              CK_LValueToRValue, SubstitutedExpression.get(),
-              /*BasePath=*/nullptr, VK_PRValue, FPOptionsOverride());
-
-        return SubstitutedExpression;
-      });
+    std::optional<unsigned>
+    EvaluateFoldExpandedConstraintSize(const CXXFoldExpr *FE) const {
+      Expr *Pattern = FE->getPattern();
+
+      SmallVector<UnexpandedParameterPack, 2> Unexpanded;
+      S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
+      assert(!Unexpanded.empty() && "Pack expansion without parameter packs?");
+      bool Expand = true;
+      bool RetainExpansion = false;
+      std::optional<unsigned> OrigNumExpansions = FE->getNumExpansions(),
+                              NumExpansions = OrigNumExpansions;
+      if (S.CheckParameterPacksForExpansion(
+              FE->getEllipsisLoc(), Pattern->getSourceRange(), Unexpanded,
+              MLTAL, Expand, RetainExpansion, NumExpansions) ||
+          !Expand || RetainExpansion)
+        return std::nullopt;
+
+      if (NumExpansions && S.getLangOpts().BracketDepth < NumExpansions) {
+        S.Diag(FE->getEllipsisLoc(),
+               clang::diag::err_fold_expression_limit_exceeded)
+            << *NumExpansions << S.getLangOpts().BracketDepth
+            << FE->getSourceRange();
+        S.Diag(FE->getEllipsisLoc(), diag::note_bracket_depth);
+        return std::nullopt;
+      }
+      return NumExpansions;
+    }
+  };
+
+  return calculateConstraintSatisfaction(
+      S, ConstraintExpr, Satisfaction,
+      ConstraintEvaluator{S, Template, TemplateNameLoc, MLTAL, Satisfaction});
 }
 
 static bool CheckConstraintSatisfaction(
@@ -534,13 +676,21 @@ bool Sema::CheckConstraintSatisfaction(
 
 bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
                                        ConstraintSatisfaction &Satisfaction) {
-  return calculateConstraintSatisfaction(
-             *this, ConstraintExpr, Satisfaction,
-             [this](const Expr *AtomicExpr) -> ExprResult {
-               // We only do this to immitate lvalue-to-rvalue conversion.
-               return PerformContextuallyConvertToBool(
-                   const_cast<Expr *>(AtomicExpr));
-             })
+
+  struct ConstraintEvaluator {
+    Sema &S;
+    ExprResult EvaluateAtomicConstraint(const Expr *AtomicExpr) const {
+      return S.PerformContextuallyConvertToBool(const_cast<Expr *>(AtomicExpr));
+    }
+
+    std::optional<unsigned>
+    EvaluateFoldExpandedConstraintSize(const CXXFoldExpr *FE) const {
+      return 0;
+    }
+  };
+
+  return calculateConstraintSatisfaction(*this, ConstraintExpr, Satisfaction,
+                                         ConstraintEvaluator{*this})
       .isInvalid();
 }
 
@@ -1235,18 +1385,34 @@ Sema::getNormalizedAssociatedConstraints(
   return CacheEntry->second;
 }
 
+const NormalizedConstraint *clang::getNormalizedAssociatedConstraints(
+    Sema &S, NamedDecl *ConstrainedDecl,
+    ArrayRef<const Expr *> AssociatedConstraints) {
+  return S.getNormalizedAssociatedConstraints(ConstrainedDecl,
+                                              AssociatedConstraints);
+}
+
 static bool
 substituteParameterMappings(Sema &S, NormalizedConstraint &N,
                             ConceptDecl *Concept,
                             const MultiLevelTemplateArgumentList &MLTAL,
                             const ASTTemplateArgumentListInfo *ArgsAsWritten) {
-  if (!N.isAtomic()) {
+
+  if (N.isCompound()) {
     if (substituteParameterMappings(S, N.getLHS(), Concept, MLTAL,
                                     ArgsAsWritten))
       return true;
     return substituteParameterMappings(S, N.getRHS(), Concept, MLTAL,
                                        ArgsAsWritten);
   }
+
+  if (N.isFoldExpanded()) {
+    Sema::ArgumentPackSubstitutionIndexRAII _(S, -1);
+    return substituteParameterMappings(
+        S, N.getFoldExpandedConstraint()->Constraint, Concept, MLTAL,
+        ArgsAsWritten);
+  }
+
   TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
 
   AtomicConstraint &Atomic = *N.getAtomicConstraint();
@@ -1313,6 +1479,42 @@ static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
                                      CSE->getTemplateArgsAsWritten());
 }
 
+NormalizedConstraint::NormalizedConstraint(ASTContext &C,
+                                           NormalizedConstraint LHS,
+                                           NormalizedConstraint RHS,
+                                           CompoundConstraintKind Kind)
+    : Constraint{CompoundConstraint{
+          new(C) NormalizedConstraintPair{std::move(LHS), std::move(RHS)},
+          Kind}} {}
+
+NormalizedConstraint::NormalizedConstraint(ASTContext &C,
+                                           const NormalizedConstraint &Other) {
+  if (Other.isAtomic()) {
+    Constraint = new (C) AtomicConstraint(*Other.getAtomicConstraint());
+  } else if (Other.isFoldExpanded()) {
+    Constraint = new (C) FoldExpandedConstraint(
+        Other.getFoldExpandedConstraint()->Kind,
+        NormalizedConstraint(C, Other.getFoldExpandedConstraint()->Constraint),
+        Other.getFoldExpandedConstraint()->Pattern);
+  } else {
+    Constraint = CompoundConstraint(
+        new (C)
+            NormalizedConstraintPair{NormalizedConstraint(C, Other.getLHS()),
+                                     NormalizedConstraint(C, Other.getRHS())},
+        Other.getCompoundKind());
+  }
+}
+
+NormalizedConstraint &NormalizedConstraint::getLHS() const {
+  assert(isCompound() && "getLHS called on a non-compound constraint.");
+  return Constraint.get<CompoundConstraint>().getPointer()->LHS;
+}
+
+NormalizedConstraint &NormalizedConstraint::getRHS() const {
+  assert(isCompound() && "getRHS called on a non-compound constraint.");
+  return Constraint.get<CompoundConstraint>().getPointer()->RHS;
+}
+
 std::optional<NormalizedConstraint>
 NormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D,
                                           ArrayRef<const Expr *> E) {
@@ -1387,17 +1589,75 @@ NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
       return std::nullopt;
 
     return New;
+  } else if (auto *FE = dyn_cast<const CXXFoldExpr>(E);
+             FE && S.getLangOpts().CPlusPlus26 &&
+             (FE->getOperator() == BinaryOperatorKind::BO_LAnd ||
+              FE->getOperator() == BinaryOperatorKind::BO_LOr)) {
+
+    // Normalize fold expressions in C++26.
+
+    FoldExpandedConstraint::FoldOperatorKind Kind =
+        FE->getOperator() == BinaryOperatorKind::BO_LAnd
+            ? FoldExpandedConstraint::FoldOperatorKind::And
+            : FoldExpandedConstraint::FoldOperatorKind::Or;
+
+    if (FE->getInit()) {
+      auto LHS = fromConstraintExpr(S, D, FE->getLHS());
+      auto RHS = fromConstraintExpr(S, D, FE->getRHS());
+      if (!LHS || !RHS)
+        return std::nullopt;
+
+      if (FE->isRightFold())
+        RHS = NormalizedConstraint{new (S.Context) FoldExpandedConstraint{
+            Kind, std::move(*RHS), FE->getPattern()}};
+      else
+        LHS = NormalizedConstraint{new (S.Context) FoldExpandedConstraint{
+            Kind, std::move(*LHS), FE->getPattern()}};
+
+      return NormalizedConstraint(
+          S.Context, std::move(*LHS), std::move(*RHS),
+          FE->getOperator() == BinaryOperatorKind::BO_LAnd ? CCK_Conjunction
+                                                           : CCK_Disjunction);
+    }
+    auto Sub = fromConstraintExpr(S, D, FE->getPattern());
+    if (!Sub)
+      return std::nullopt;
+    return NormalizedConstraint{new (S.Context) FoldExpandedConstraint{
+        Kind, std::move(*Sub), FE->getPattern()}};
   }
+
   return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)};
 }
 
-using NormalForm =
-    llvm::SmallVector<llvm::SmallVector<AtomicConstraint *, 2>, 4>;
+bool FoldExpandedConstraint::AreCompatibleForSubsumption(
+    const FoldExpandedConstraint &A, const FoldExpandedConstraint &B) {
+
+  // [C++26] [temp.constr.fold]
+  // Two fold expanded constraints are compatible for subsumption
+  // if their respective constraints both contain an equivalent unexpanded pack.
 
-static NormalForm makeCNF(const NormalizedConstraint &Normalized) {
+  llvm::SmallVector<UnexpandedParameterPack> APacks, BPacks;
+  Sema::collectUnexpandedParameterPacks(const_cast<Expr *>(A.Pattern), APacks);
+  Sema::collectUnexpandedParameterPacks(const_cast<Expr *>(B.Pattern), BPacks);
+
+  for (const UnexpandedParameterPack &APack : APacks) {
+    std::pair<unsigned, unsigned> DepthAndIndex = getDepthAndIndex(APack);
+    auto it = llvm::find_if(BPacks, [&](const UnexpandedParameterPack &BPack) {
+      return getDepthAndIndex(BPack) == DepthAndIndex;
+    });
+    if (it != BPacks.end())
+      return true;
+  }
+  return false;
+}
+
+NormalForm clang::makeCNF(const NormalizedConstraint &Normalized) {
   if (Normalized.isAtomic())
     return {{Normalized.getAtomicConstraint()}};
 
+  else if (Normalized.isFoldExpanded())
+    return {{Normalized.getFoldExpandedConstraint()}};
+
   NormalForm LCNF = makeCNF(Normalized.getLHS());
   NormalForm RCNF = makeCNF(Normalized.getRHS());
   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) {
@@ -1423,10 +1683,13 @@ static NormalForm makeCNF(const NormalizedConstraint &Normalized) {
   return Res;
 }
 
-static NormalForm makeDNF(const NormalizedConstraint &Normalized) {
+NormalForm clang::makeDNF(const NormalizedConstraint &Normalized) {
   if (Normalized.isAtomic())
     return {{Normalized.getAtomicConstraint()}};
 
+  else if (Normalized.isFoldExpanded())
+    return {{Normalized.getFoldExpandedConstraint()}};
+
   NormalForm LDNF = makeDNF(Normalized.getLHS());
   NormalForm RDNF = makeDNF(Normalized.getRHS());
   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) {
@@ -1453,60 +1716,6 @@ static NormalForm makeDNF(const NormalizedConstraint &Normalized) {
   return Res;
 }
 
-template<typename AtomicSubsumptionEvaluator>
-static bool subsumes(const NormalForm &PDNF, const NormalForm &QCNF,
-                     AtomicSubsumptionEvaluator E) {
-  // C++ [temp.constr.order] p2
-  //   Then, P subsumes Q if and only if, for every disjunctive clause Pi in the
-  //   disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in
-  //   the conjuctive normal form of Q, where [...]
-  for (const auto &Pi : PDNF) {
-    for (const auto &Qj : QCNF) {
-      // C++ [temp.constr.order] p2
-      //   - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
-      //     and only if there exists an atomic constraint Pia in Pi for which
-      //     there exists an atomic constraint, Qjb, in Qj such that Pia
-      //     subsumes Qjb.
-      bool Found = false;
-      for (const AtomicConstraint *Pia : Pi) {
-        for (const AtomicConstraint *Qjb : Qj) {
-          if (E(*Pia, *Qjb)) {
-            Found = true;
-            break;
-          }
-        }
-        if (Found)
-          break;
-      }
-      if (!Found)
-        return false;
-    }
-  }
-  return true;
-}
-
-template<typename AtomicSubsumptionEvaluator>
-static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P,
-                     NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes,
-                     AtomicSubsumptionEvaluator E) {
-  // C++ [temp.constr.order] p2
-  //   In order to determine if a constraint P subsumes a constraint Q, P is
-  //   transformed into disjunctive normal form, and Q is transformed into
-  //   conjunctive normal form. [...]
-  auto *PNormalized = S.getNormalizedAssociatedConstraints(DP, P);
-  if (!PNormalized)
-    return true;
-  const NormalForm PDNF = makeDNF(*PNormalized);
-
-  auto *QNormalized = S.getNormalizedAssociatedConstraints(DQ, Q);
-  if (!QNormalized)
-    return true;
-  const NormalForm QCNF = makeCNF(*QNormalized);
-
-  Subsumes = subsumes(PDNF, QCNF, E);
-  return false;
-}
-
 bool Sema::IsAtLeastAsConstrained(NamedDecl *D1,
                                   MutableArrayRef<const Expr *> AC1,
                                   NamedDecl *D2,
@@ -1559,10 +1768,11 @@ bool Sema::IsAtLeastAsConstrained(NamedDecl *D1,
     }
   }
 
-  if (subsumes(*this, D1, AC1, D2, AC2, Result,
-        [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
-          return A.subsumes(Context, B);
-        }))
+  if (clang::subsumes(
+          *this, D1, AC1, D2, AC2, Result,
+          [this](const AtomicConstraint &A, const AtomicConstraint &B) {
+            return A.subsumes(Context, B);
+          }))
     return true;
   SubsumptionCache.try_emplace(Key, Result);
   return false;
@@ -1619,10 +1829,12 @@ bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
     const NormalForm DNF2 = makeDNF(*Normalized2);
     const NormalForm CNF2 = makeCNF(*Normalized2);
 
-    bool Is1AtLeastAs2Normally = subsumes(DNF1, CNF2, NormalExprEvaluator);
-    bool Is2AtLeastAs1Normally = subsumes(DNF2, CNF1, NormalExprEvaluator);
-    bool Is1AtLeastAs2 = subsumes(DNF1, CNF2, IdenticalExprEvaluator);
-    bool Is2AtLeastAs1 = subsumes(DNF2, CNF1, IdenticalExprEvaluator);
+    bool Is1AtLeastAs2Normally =
+        clang::subsumes(DNF1, CNF2, NormalExprEvaluator);
+    bool Is2AtLeastAs1Normally =
+        clang::subsumes(DNF2, CNF1, NormalExprEvaluator);
+    bool Is1AtLeastAs2 = clang::subsumes(DNF1, CNF2, IdenticalExprEvaluator);
+    bool Is2AtLeastAs1 = clang::subsumes(DNF2, CNF1, IdenticalExprEvaluator);
     if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
         Is2AtLeastAs1 == Is2AtLeastAs1Normally)
       // Same result - no ambiguity was caused by identical atomic expressions.