brintos / llvm-project-archived public Read only

1//===-- SemaConcept.cpp - 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-exception6//7//===----------------------------------------------------------------------===//8//9//  This file implements semantic analysis for C++ constraints and concepts.10//11//===----------------------------------------------------------------------===//12 13#include "clang/Sema/SemaConcept.h"14#include "TreeTransform.h"15#include "clang/AST/ASTConcept.h"16#include "clang/AST/ASTLambda.h"17#include "clang/AST/DeclCXX.h"18#include "clang/AST/ExprConcepts.h"19#include "clang/AST/RecursiveASTVisitor.h"20#include "clang/Basic/OperatorPrecedence.h"21#include "clang/Sema/EnterExpressionEvaluationContext.h"22#include "clang/Sema/Initialization.h"23#include "clang/Sema/Overload.h"24#include "clang/Sema/ScopeInfo.h"25#include "clang/Sema/Sema.h"26#include "clang/Sema/SemaInternal.h"27#include "clang/Sema/Template.h"28#include "clang/Sema/TemplateDeduction.h"29#include "llvm/ADT/DenseMap.h"30#include "llvm/ADT/PointerUnion.h"31#include "llvm/ADT/StringExtras.h"32#include "llvm/Support/SaveAndRestore.h"33 34using namespace clang;35using namespace sema;36 37namespace {38class LogicalBinOp {39  SourceLocation Loc;40  OverloadedOperatorKind Op = OO_None;41  const Expr *LHS = nullptr;42  const Expr *RHS = nullptr;43 44public:45  LogicalBinOp(const Expr *E) {46    if (auto *BO = dyn_cast<BinaryOperator>(E)) {47      Op = BinaryOperator::getOverloadedOperator(BO->getOpcode());48      LHS = BO->getLHS();49      RHS = BO->getRHS();50      Loc = BO->getExprLoc();51    } else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(E)) {52      // If OO is not || or && it might not have exactly 2 arguments.53      if (OO->getNumArgs() == 2) {54        Op = OO->getOperator();55        LHS = OO->getArg(0);56        RHS = OO->getArg(1);57        Loc = OO->getOperatorLoc();58      }59    }60  }61 62  bool isAnd() const { return Op == OO_AmpAmp; }63  bool isOr() const { return Op == OO_PipePipe; }64  explicit operator bool() const { return isAnd() || isOr(); }65 66  const Expr *getLHS() const { return LHS; }67  const Expr *getRHS() const { return RHS; }68  OverloadedOperatorKind getOp() const { return Op; }69 70  ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS) const {71    return recreateBinOp(SemaRef, LHS, const_cast<Expr *>(getRHS()));72  }73 74  ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS,75                           ExprResult RHS) const {76    assert((isAnd() || isOr()) && "Not the right kind of op?");77    assert((!LHS.isInvalid() && !RHS.isInvalid()) && "not good expressions?");78 79    if (!LHS.isUsable() || !RHS.isUsable())80      return ExprEmpty();81 82    // We should just be able to 'normalize' these to the builtin Binary83    // Operator, since that is how they are evaluated in constriant checks.84    return BinaryOperator::Create(SemaRef.Context, LHS.get(), RHS.get(),85                                  BinaryOperator::getOverloadedOpcode(Op),86                                  SemaRef.Context.BoolTy, VK_PRValue,87                                  OK_Ordinary, Loc, FPOptionsOverride{});88  }89};90} // namespace91 92bool Sema::CheckConstraintExpression(const Expr *ConstraintExpression,93                                     Token NextToken, bool *PossibleNonPrimary,94                                     bool IsTrailingRequiresClause) {95  // C++2a [temp.constr.atomic]p196  // ..E shall be a constant expression of type bool.97 98  ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts();99 100  if (LogicalBinOp BO = ConstraintExpression) {101    return CheckConstraintExpression(BO.getLHS(), NextToken,102                                     PossibleNonPrimary) &&103           CheckConstraintExpression(BO.getRHS(), NextToken,104                                     PossibleNonPrimary);105  } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression))106    return CheckConstraintExpression(C->getSubExpr(), NextToken,107                                     PossibleNonPrimary);108 109  QualType Type = ConstraintExpression->getType();110 111  auto CheckForNonPrimary = [&] {112    if (!PossibleNonPrimary)113      return;114 115    *PossibleNonPrimary =116        // We have the following case:117        // template<typename> requires func(0) struct S { };118        // The user probably isn't aware of the parentheses required around119        // the function call, and we're only going to parse 'func' as the120        // primary-expression, and complain that it is of non-bool type.121        //122        // However, if we're in a lambda, this might also be:123        // []<typename> requires var () {};124        // Which also looks like a function call due to the lambda parentheses,125        // but unlike the first case, isn't an error, so this check is skipped.126        (NextToken.is(tok::l_paren) &&127         (IsTrailingRequiresClause ||128          (Type->isDependentType() &&129           isa<UnresolvedLookupExpr>(ConstraintExpression) &&130           !dyn_cast_if_present<LambdaScopeInfo>(getCurFunction())) ||131          Type->isFunctionType() ||132          Type->isSpecificBuiltinType(BuiltinType::Overload))) ||133        // We have the following case:134        // template<typename T> requires size_<T> == 0 struct S { };135        // The user probably isn't aware of the parentheses required around136        // the binary operator, and we're only going to parse 'func' as the137        // first operand, and complain that it is of non-bool type.138        getBinOpPrecedence(NextToken.getKind(),139                           /*GreaterThanIsOperator=*/true,140                           getLangOpts().CPlusPlus11) > prec::LogicalAnd;141  };142 143  // An atomic constraint!144  if (ConstraintExpression->isTypeDependent()) {145    CheckForNonPrimary();146    return true;147  }148 149  if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) {150    Diag(ConstraintExpression->getExprLoc(),151         diag::err_non_bool_atomic_constraint)152        << Type << ConstraintExpression->getSourceRange();153    CheckForNonPrimary();154    return false;155  }156 157  if (PossibleNonPrimary)158    *PossibleNonPrimary = false;159  return true;160}161 162namespace {163struct SatisfactionStackRAII {164  Sema &SemaRef;165  bool Inserted = false;166  SatisfactionStackRAII(Sema &SemaRef, const NamedDecl *ND,167                        const llvm::FoldingSetNodeID &FSNID)168      : SemaRef(SemaRef) {169    if (ND) {170      SemaRef.PushSatisfactionStackEntry(ND, FSNID);171      Inserted = true;172    }173  }174  ~SatisfactionStackRAII() {175    if (Inserted)176      SemaRef.PopSatisfactionStackEntry();177  }178};179} // namespace180 181static bool DiagRecursiveConstraintEval(182    Sema &S, llvm::FoldingSetNodeID &ID, const NamedDecl *Templ, const Expr *E,183    const MultiLevelTemplateArgumentList *MLTAL = nullptr) {184  E->Profile(ID, S.Context, /*Canonical=*/true);185  if (MLTAL) {186    for (const auto &List : *MLTAL)187      for (const auto &TemplateArg : List.Args)188        S.Context.getCanonicalTemplateArgument(TemplateArg)189            .Profile(ID, S.Context);190  }191  if (S.SatisfactionStackContains(Templ, ID)) {192    S.Diag(E->getExprLoc(), diag::err_constraint_depends_on_self)193        << E << E->getSourceRange();194    return true;195  }196  return false;197}198 199// Figure out the to-translation-unit depth for this function declaration for200// the purpose of seeing if they differ by constraints. This isn't the same as201// getTemplateDepth, because it includes already instantiated parents.202static unsigned203CalculateTemplateDepthForConstraints(Sema &S, const NamedDecl *ND,204                                     bool SkipForSpecialization = false) {205  MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(206      ND, ND->getLexicalDeclContext(), /*Final=*/false,207      /*Innermost=*/std::nullopt,208      /*RelativeToPrimary=*/true,209      /*Pattern=*/nullptr,210      /*ForConstraintInstantiation=*/true, SkipForSpecialization);211  return MLTAL.getNumLevels();212}213 214namespace {215class AdjustConstraintDepth : public TreeTransform<AdjustConstraintDepth> {216  unsigned TemplateDepth = 0;217 218public:219  using inherited = TreeTransform<AdjustConstraintDepth>;220  AdjustConstraintDepth(Sema &SemaRef, unsigned TemplateDepth)221      : inherited(SemaRef), TemplateDepth(TemplateDepth) {}222 223  using inherited::TransformTemplateTypeParmType;224  QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,225                                         TemplateTypeParmTypeLoc TL, bool) {226    const TemplateTypeParmType *T = TL.getTypePtr();227 228    TemplateTypeParmDecl *NewTTPDecl = nullptr;229    if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl())230      NewTTPDecl = cast_or_null<TemplateTypeParmDecl>(231          TransformDecl(TL.getNameLoc(), OldTTPDecl));232 233    QualType Result = getSema().Context.getTemplateTypeParmType(234        T->getDepth() + TemplateDepth, T->getIndex(), T->isParameterPack(),235        NewTTPDecl);236    TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);237    NewTL.setNameLoc(TL.getNameLoc());238    return Result;239  }240 241  bool AlreadyTransformed(QualType T) {242    if (T.isNull())243      return true;244 245    if (T->isInstantiationDependentType() || T->isVariablyModifiedType() ||246        T->containsUnexpandedParameterPack())247      return false;248    return true;249  }250};251} // namespace252 253namespace {254 255// FIXME: Convert it to DynamicRecursiveASTVisitor256class HashParameterMapping : public RecursiveASTVisitor<HashParameterMapping> {257  using inherited = RecursiveASTVisitor<HashParameterMapping>;258  friend inherited;259 260  Sema &SemaRef;261  const MultiLevelTemplateArgumentList &TemplateArgs;262  llvm::FoldingSetNodeID &ID;263  llvm::SmallVector<TemplateArgument, 10> UsedTemplateArgs;264 265  UnsignedOrNone OuterPackSubstIndex;266 267  bool shouldVisitTemplateInstantiations() const { return true; }268 269public:270  HashParameterMapping(Sema &SemaRef,271                       const MultiLevelTemplateArgumentList &TemplateArgs,272                       llvm::FoldingSetNodeID &ID,273                       UnsignedOrNone OuterPackSubstIndex)274      : SemaRef(SemaRef), TemplateArgs(TemplateArgs), ID(ID),275        OuterPackSubstIndex(OuterPackSubstIndex) {}276 277  bool VisitTemplateTypeParmType(TemplateTypeParmType *T) {278    // A lambda expression can introduce template parameters that don't have279    // corresponding template arguments yet.280    if (T->getDepth() >= TemplateArgs.getNumLevels())281      return true;282 283    // There might not be a corresponding template argument before substituting284    // into the parameter mapping, e.g. a sizeof... expression.285    if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex()))286      return true;287 288    TemplateArgument Arg = TemplateArgs(T->getDepth(), T->getIndex());289 290    if (T->isParameterPack() && SemaRef.ArgPackSubstIndex) {291      assert(Arg.getKind() == TemplateArgument::Pack &&292             "Missing argument pack");293 294      Arg = SemaRef.getPackSubstitutedTemplateArgument(Arg);295    }296 297    UsedTemplateArgs.push_back(298        SemaRef.Context.getCanonicalTemplateArgument(Arg));299    return true;300  }301 302  bool VisitDeclRefExpr(DeclRefExpr *E) {303    NamedDecl *D = E->getDecl();304    NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D);305    if (!NTTP)306      return TraverseDecl(D);307 308    if (NTTP->getDepth() >= TemplateArgs.getNumLevels())309      return true;310 311    if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(), NTTP->getIndex()))312      return true;313 314    TemplateArgument Arg = TemplateArgs(NTTP->getDepth(), NTTP->getPosition());315    if (NTTP->isParameterPack() && SemaRef.ArgPackSubstIndex) {316      assert(Arg.getKind() == TemplateArgument::Pack &&317             "Missing argument pack");318      Arg = SemaRef.getPackSubstitutedTemplateArgument(Arg);319    }320 321    UsedTemplateArgs.push_back(322        SemaRef.Context.getCanonicalTemplateArgument(Arg));323    return true;324  }325 326  bool VisitTypedefType(TypedefType *TT) {327    return inherited::TraverseType(TT->desugar());328  }329 330  bool TraverseDecl(Decl *D) {331    if (auto *VD = dyn_cast<ValueDecl>(D)) {332      if (auto *Var = dyn_cast<VarDecl>(VD))333        TraverseStmt(Var->getInit());334      return TraverseType(VD->getType());335    }336 337    return inherited::TraverseDecl(D);338  }339 340  bool TraverseCallExpr(CallExpr *CE) {341    inherited::TraverseStmt(CE->getCallee());342 343    for (Expr *Arg : CE->arguments())344      inherited::TraverseStmt(Arg);345 346    return true;347  }348 349  bool TraverseTypeLoc(TypeLoc TL, bool TraverseQualifier = true) {350    // We don't care about TypeLocs. So traverse Types instead.351    return TraverseType(TL.getType().getCanonicalType(), TraverseQualifier);352  }353 354  bool TraverseTagType(const TagType *T, bool TraverseQualifier) {355    // T's parent can be dependent while T doesn't have any template arguments.356    // We should have already traversed its qualifier.357    // FIXME: Add an assert to catch cases where we failed to profile the358    // concept.359    return true;360  }361 362  bool TraverseInjectedClassNameType(InjectedClassNameType *T,363                                     bool TraverseQualifier) {364    return TraverseTemplateArguments(T->getTemplateArgs(SemaRef.Context));365  }366 367  bool TraverseTemplateArgument(const TemplateArgument &Arg) {368    if (!Arg.containsUnexpandedParameterPack() || Arg.isPackExpansion()) {369      // Act as if we are fully expanding this pack, if it is a PackExpansion.370      Sema::ArgPackSubstIndexRAII _1(SemaRef, std::nullopt);371      llvm::SaveAndRestore<UnsignedOrNone> _2(OuterPackSubstIndex,372                                              std::nullopt);373      return inherited::TraverseTemplateArgument(Arg);374    }375 376    Sema::ArgPackSubstIndexRAII _1(SemaRef, OuterPackSubstIndex);377    return inherited::TraverseTemplateArgument(Arg);378  }379 380  bool TraverseSizeOfPackExpr(SizeOfPackExpr *SOPE) {381    return TraverseDecl(SOPE->getPack());382  }383 384  bool VisitSubstNonTypeTemplateParmExpr(SubstNonTypeTemplateParmExpr *E) {385    return inherited::TraverseStmt(E->getReplacement());386  }387 388  bool TraverseTemplateName(TemplateName Template) {389    if (auto *TTP = dyn_cast_if_present<TemplateTemplateParmDecl>(390            Template.getAsTemplateDecl());391        TTP && TTP->getDepth() < TemplateArgs.getNumLevels()) {392      if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),393                                            TTP->getPosition()))394        return true;395 396      TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getPosition());397      if (TTP->isParameterPack() && SemaRef.ArgPackSubstIndex) {398        assert(Arg.getKind() == TemplateArgument::Pack &&399               "Missing argument pack");400        Arg = SemaRef.getPackSubstitutedTemplateArgument(Arg);401      }402      assert(!Arg.getAsTemplate().isNull() &&403             "Null template template argument");404      UsedTemplateArgs.push_back(405          SemaRef.Context.getCanonicalTemplateArgument(Arg));406    }407    return inherited::TraverseTemplateName(Template);408  }409 410  void VisitConstraint(const NormalizedConstraintWithParamMapping &Constraint) {411    if (!Constraint.hasParameterMapping()) {412      for (const auto &List : TemplateArgs)413        for (const TemplateArgument &Arg : List.Args)414          SemaRef.Context.getCanonicalTemplateArgument(Arg).Profile(415              ID, SemaRef.Context);416      return;417    }418 419    llvm::ArrayRef<TemplateArgumentLoc> Mapping =420        Constraint.getParameterMapping();421    for (auto &ArgLoc : Mapping) {422      TemplateArgument Canonical =423          SemaRef.Context.getCanonicalTemplateArgument(ArgLoc.getArgument());424      // We don't want sugars to impede the profile of cache.425      UsedTemplateArgs.push_back(Canonical);426      TraverseTemplateArgument(Canonical);427    }428 429    for (auto &Used : UsedTemplateArgs) {430      llvm::FoldingSetNodeID R;431      Used.Profile(R, SemaRef.Context);432      ID.AddNodeID(R);433    }434  }435};436 437class ConstraintSatisfactionChecker {438  Sema &S;439  const NamedDecl *Template;440  SourceLocation TemplateNameLoc;441  UnsignedOrNone PackSubstitutionIndex;442  ConstraintSatisfaction &Satisfaction;443  bool BuildExpression;444 445private:446  ExprResult447  EvaluateAtomicConstraint(const Expr *AtomicExpr,448                           const MultiLevelTemplateArgumentList &MLTAL);449 450  UnsignedOrNone EvaluateFoldExpandedConstraintSize(451      const FoldExpandedConstraint &FE,452      const MultiLevelTemplateArgumentList &MLTAL);453 454  // XXX: It is SLOW! Use it very carefully.455  std::optional<MultiLevelTemplateArgumentList> SubstitutionInTemplateArguments(456      const NormalizedConstraintWithParamMapping &Constraint,457      const MultiLevelTemplateArgumentList &MLTAL,458      llvm::SmallVector<TemplateArgument> &SubstitutedOuterMost);459 460  ExprResult EvaluateSlow(const AtomicConstraint &Constraint,461                          const MultiLevelTemplateArgumentList &MLTAL);462 463  ExprResult Evaluate(const AtomicConstraint &Constraint,464                      const MultiLevelTemplateArgumentList &MLTAL);465 466  ExprResult EvaluateSlow(const FoldExpandedConstraint &Constraint,467                          const MultiLevelTemplateArgumentList &MLTAL);468 469  ExprResult Evaluate(const FoldExpandedConstraint &Constraint,470                      const MultiLevelTemplateArgumentList &MLTAL);471 472  ExprResult EvaluateSlow(const ConceptIdConstraint &Constraint,473                          const MultiLevelTemplateArgumentList &MLTAL,474                          unsigned int Size);475 476  ExprResult Evaluate(const ConceptIdConstraint &Constraint,477                      const MultiLevelTemplateArgumentList &MLTAL);478 479  ExprResult Evaluate(const CompoundConstraint &Constraint,480                      const MultiLevelTemplateArgumentList &MLTAL);481 482public:483  ConstraintSatisfactionChecker(Sema &SemaRef, const NamedDecl *Template,484                                SourceLocation TemplateNameLoc,485                                UnsignedOrNone PackSubstitutionIndex,486                                ConstraintSatisfaction &Satisfaction,487                                bool BuildExpression)488      : S(SemaRef), Template(Template), TemplateNameLoc(TemplateNameLoc),489        PackSubstitutionIndex(PackSubstitutionIndex),490        Satisfaction(Satisfaction), BuildExpression(BuildExpression) {}491 492  ExprResult Evaluate(const NormalizedConstraint &Constraint,493                      const MultiLevelTemplateArgumentList &MLTAL);494};495 496StringRef allocateStringFromConceptDiagnostic(const Sema &S,497                                              const PartialDiagnostic Diag) {498  SmallString<128> DiagString;499  DiagString = ": ";500  Diag.EmitToString(S.getDiagnostics(), DiagString);501  return S.getASTContext().backupStr(DiagString);502}503 504} // namespace505 506ExprResult ConstraintSatisfactionChecker::EvaluateAtomicConstraint(507    const Expr *AtomicExpr, const MultiLevelTemplateArgumentList &MLTAL) {508  EnterExpressionEvaluationContext ConstantEvaluated(509      S, Sema::ExpressionEvaluationContext::ConstantEvaluated,510      Sema::ReuseLambdaContextDecl);511 512  llvm::FoldingSetNodeID ID;513  if (Template &&514      DiagRecursiveConstraintEval(S, ID, Template, AtomicExpr, &MLTAL)) {515    Satisfaction.IsSatisfied = false;516    Satisfaction.ContainsErrors = true;517    return ExprEmpty();518  }519  SatisfactionStackRAII StackRAII(S, Template, ID);520 521  // Atomic constraint - substitute arguments and check satisfaction.522  ExprResult SubstitutedExpression = const_cast<Expr *>(AtomicExpr);523  {524    TemplateDeductionInfo Info(TemplateNameLoc);525    Sema::InstantiatingTemplate Inst(526        S, AtomicExpr->getBeginLoc(),527        Sema::InstantiatingTemplate::ConstraintSubstitution{},528        // FIXME: improve const-correctness of InstantiatingTemplate529        const_cast<NamedDecl *>(Template), AtomicExpr->getSourceRange());530    if (Inst.isInvalid())531      return ExprError();532 533    // We do not want error diagnostics escaping here.534    Sema::SFINAETrap Trap(S, Info);535    SubstitutedExpression =536        S.SubstConstraintExpr(const_cast<Expr *>(AtomicExpr), MLTAL);537 538    if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {539      // C++2a [temp.constr.atomic]p1540      //   ...If substitution results in an invalid type or expression, the541      //   constraint is not satisfied.542      if (!Trap.hasErrorOccurred())543        // A non-SFINAE error has occurred as a result of this544        // substitution.545        return ExprError();546 547      PartialDiagnosticAt SubstDiag{SourceLocation(),548                                    PartialDiagnostic::NullDiagnostic()};549      Info.takeSFINAEDiagnostic(SubstDiag);550      // FIXME: This is an unfortunate consequence of there551      //  being no serialization code for PartialDiagnostics and the fact552      //  that serializing them would likely take a lot more storage than553      //  just storing them as strings. We would still like, in the554      //  future, to serialize the proper PartialDiagnostic as serializing555      //  it as a string defeats the purpose of the diagnostic mechanism.556      Satisfaction.Details.emplace_back(557          new (S.Context) ConstraintSubstitutionDiagnostic{558              SubstDiag.first,559              allocateStringFromConceptDiagnostic(S, SubstDiag.second)});560      Satisfaction.IsSatisfied = false;561      return ExprEmpty();562    }563  }564 565  if (!S.CheckConstraintExpression(SubstitutedExpression.get()))566    return ExprError();567 568  // [temp.constr.atomic]p3: To determine if an atomic constraint is569  // satisfied, the parameter mapping and template arguments are first570  // substituted into its expression.  If substitution results in an571  // invalid type or expression, the constraint is not satisfied.572  // Otherwise, the lvalue-to-rvalue conversion is performed if necessary,573  // and E shall be a constant expression of type bool.574  //575  // Perform the L to R Value conversion if necessary. We do so for all576  // non-PRValue categories, else we fail to extend the lifetime of577  // temporaries, and that fails the constant expression check.578  if (!SubstitutedExpression.get()->isPRValue())579    SubstitutedExpression = ImplicitCastExpr::Create(580        S.Context, SubstitutedExpression.get()->getType(), CK_LValueToRValue,581        SubstitutedExpression.get(),582        /*BasePath=*/nullptr, VK_PRValue, FPOptionsOverride());583 584  return SubstitutedExpression;585}586 587std::optional<MultiLevelTemplateArgumentList>588ConstraintSatisfactionChecker::SubstitutionInTemplateArguments(589    const NormalizedConstraintWithParamMapping &Constraint,590    const MultiLevelTemplateArgumentList &MLTAL,591    llvm::SmallVector<TemplateArgument> &SubstitutedOutermost) {592 593  if (!Constraint.hasParameterMapping())594    return std::move(MLTAL);595 596  // The mapping is empty, meaning no template arguments are needed for597  // evaluation.598  if (Constraint.getParameterMapping().empty())599    return MultiLevelTemplateArgumentList();600 601  TemplateDeductionInfo Info(Constraint.getBeginLoc());602  Sema::SFINAETrap Trap(S, Info);603  Sema::InstantiatingTemplate Inst(604      S, Constraint.getBeginLoc(),605      Sema::InstantiatingTemplate::ConstraintSubstitution{},606      // FIXME: improve const-correctness of InstantiatingTemplate607      const_cast<NamedDecl *>(Template), Constraint.getSourceRange());608  if (Inst.isInvalid())609    return std::nullopt;610 611  TemplateArgumentListInfo SubstArgs;612  Sema::ArgPackSubstIndexRAII SubstIndex(613      S, Constraint.getPackSubstitutionIndex()614             ? Constraint.getPackSubstitutionIndex()615             : PackSubstitutionIndex);616 617  if (S.SubstTemplateArgumentsInParameterMapping(618          Constraint.getParameterMapping(), Constraint.getBeginLoc(), MLTAL,619          SubstArgs, /*BuildPackExpansionTypes=*/true)) {620    Satisfaction.IsSatisfied = false;621    return std::nullopt;622  }623 624  Sema::CheckTemplateArgumentInfo CTAI;625  auto *TD = const_cast<TemplateDecl *>(626      cast<TemplateDecl>(Constraint.getConstraintDecl()));627  if (S.CheckTemplateArgumentList(TD, Constraint.getUsedTemplateParamList(),628                                  TD->getLocation(), SubstArgs,629                                  /*DefaultArguments=*/{},630                                  /*PartialTemplateArgs=*/false, CTAI))631    return std::nullopt;632  const NormalizedConstraint::OccurenceList &Used =633      Constraint.mappingOccurenceList();634  // The empty MLTAL situation should only occur when evaluating non-dependent635  // constraints.636  if (MLTAL.getNumSubstitutedLevels())637    SubstitutedOutermost =638        llvm::to_vector_of<TemplateArgument>(MLTAL.getOutermost());639  unsigned Offset = 0;640  for (unsigned I = 0, MappedIndex = 0; I < Used.size(); I++) {641    TemplateArgument Arg;642    if (Used[I])643      Arg = S.Context.getCanonicalTemplateArgument(644          CTAI.SugaredConverted[MappedIndex++]);645    if (I < SubstitutedOutermost.size()) {646      SubstitutedOutermost[I] = Arg;647      Offset = I + 1;648    } else {649      SubstitutedOutermost.push_back(Arg);650      Offset = SubstitutedOutermost.size();651    }652  }653  if (Offset < SubstitutedOutermost.size())654    SubstitutedOutermost.erase(SubstitutedOutermost.begin() + Offset);655 656  MultiLevelTemplateArgumentList SubstitutedTemplateArgs;657  SubstitutedTemplateArgs.addOuterTemplateArguments(TD, SubstitutedOutermost,658                                                    /*Final=*/false);659  return std::move(SubstitutedTemplateArgs);660}661 662ExprResult ConstraintSatisfactionChecker::EvaluateSlow(663    const AtomicConstraint &Constraint,664    const MultiLevelTemplateArgumentList &MLTAL) {665 666  llvm::SmallVector<TemplateArgument> SubstitutedOutermost;667  std::optional<MultiLevelTemplateArgumentList> SubstitutedArgs =668      SubstitutionInTemplateArguments(Constraint, MLTAL, SubstitutedOutermost);669  if (!SubstitutedArgs) {670    Satisfaction.IsSatisfied = false;671    return ExprEmpty();672  }673 674  Sema::ArgPackSubstIndexRAII SubstIndex(S, PackSubstitutionIndex);675  ExprResult SubstitutedAtomicExpr = EvaluateAtomicConstraint(676      Constraint.getConstraintExpr(), *SubstitutedArgs);677 678  if (SubstitutedAtomicExpr.isInvalid())679    return ExprError();680 681  if (SubstitutedAtomicExpr.isUnset())682    // Evaluator has decided satisfaction without yielding an expression.683    return ExprEmpty();684 685  // We don't have the ability to evaluate this, since it contains a686  // RecoveryExpr, so we want to fail overload resolution.  Otherwise,687  // we'd potentially pick up a different overload, and cause confusing688  // diagnostics. SO, add a failure detail that will cause us to make this689  // overload set not viable.690  if (SubstitutedAtomicExpr.get()->containsErrors()) {691    Satisfaction.IsSatisfied = false;692    Satisfaction.ContainsErrors = true;693 694    PartialDiagnostic Msg = S.PDiag(diag::note_constraint_references_error);695    Satisfaction.Details.emplace_back(696        new (S.Context) ConstraintSubstitutionDiagnostic{697            SubstitutedAtomicExpr.get()->getBeginLoc(),698            allocateStringFromConceptDiagnostic(S, Msg)});699    return SubstitutedAtomicExpr;700  }701 702  if (SubstitutedAtomicExpr.get()->isValueDependent()) {703    Satisfaction.IsSatisfied = true;704    Satisfaction.ContainsErrors = false;705    return SubstitutedAtomicExpr;706  }707 708  EnterExpressionEvaluationContext ConstantEvaluated(709      S, Sema::ExpressionEvaluationContext::ConstantEvaluated);710  SmallVector<PartialDiagnosticAt, 2> EvaluationDiags;711  Expr::EvalResult EvalResult;712  EvalResult.Diag = &EvaluationDiags;713  if (!SubstitutedAtomicExpr.get()->EvaluateAsConstantExpr(EvalResult,714                                                           S.Context) ||715      !EvaluationDiags.empty()) {716    // C++2a [temp.constr.atomic]p1717    //   ...E shall be a constant expression of type bool.718    S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(),719           diag::err_non_constant_constraint_expression)720        << SubstitutedAtomicExpr.get()->getSourceRange();721    for (const PartialDiagnosticAt &PDiag : EvaluationDiags)722      S.Diag(PDiag.first, PDiag.second);723    return ExprError();724  }725 726  assert(EvalResult.Val.isInt() &&727         "evaluating bool expression didn't produce int");728  Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();729  if (!Satisfaction.IsSatisfied)730    Satisfaction.Details.emplace_back(SubstitutedAtomicExpr.get());731 732  return SubstitutedAtomicExpr;733}734 735ExprResult ConstraintSatisfactionChecker::Evaluate(736    const AtomicConstraint &Constraint,737    const MultiLevelTemplateArgumentList &MLTAL) {738 739  unsigned Size = Satisfaction.Details.size();740  llvm::FoldingSetNodeID ID;741  UnsignedOrNone OuterPackSubstIndex =742      Constraint.getPackSubstitutionIndex()743          ? Constraint.getPackSubstitutionIndex()744          : PackSubstitutionIndex;745 746  ID.AddPointer(Constraint.getConstraintExpr());747  ID.AddInteger(OuterPackSubstIndex.toInternalRepresentation());748  HashParameterMapping(S, MLTAL, ID, OuterPackSubstIndex)749      .VisitConstraint(Constraint);750 751  if (auto Iter = S.UnsubstitutedConstraintSatisfactionCache.find(ID);752      Iter != S.UnsubstitutedConstraintSatisfactionCache.end()) {753    auto &Cached = Iter->second.Satisfaction;754    Satisfaction.ContainsErrors = Cached.ContainsErrors;755    Satisfaction.IsSatisfied = Cached.IsSatisfied;756    Satisfaction.Details.insert(Satisfaction.Details.begin() + Size,757                                Cached.Details.begin(), Cached.Details.end());758    return Iter->second.SubstExpr;759  }760 761  ExprResult E = EvaluateSlow(Constraint, MLTAL);762 763  UnsubstitutedConstraintSatisfactionCacheResult Cache;764  Cache.Satisfaction.ContainsErrors = Satisfaction.ContainsErrors;765  Cache.Satisfaction.IsSatisfied = Satisfaction.IsSatisfied;766  Cache.Satisfaction.Details.insert(Cache.Satisfaction.Details.end(),767                                    Satisfaction.Details.begin() + Size,768                                    Satisfaction.Details.end());769  Cache.SubstExpr = E;770  S.UnsubstitutedConstraintSatisfactionCache.insert({ID, std::move(Cache)});771 772  return E;773}774 775UnsignedOrNone776ConstraintSatisfactionChecker::EvaluateFoldExpandedConstraintSize(777    const FoldExpandedConstraint &FE,778    const MultiLevelTemplateArgumentList &MLTAL) {779 780  Expr *Pattern = const_cast<Expr *>(FE.getPattern());781 782  SmallVector<UnexpandedParameterPack, 2> Unexpanded;783  S.collectUnexpandedParameterPacks(Pattern, Unexpanded);784  assert(!Unexpanded.empty() && "Pack expansion without parameter packs?");785  bool Expand = true;786  bool RetainExpansion = false;787  UnsignedOrNone NumExpansions(std::nullopt);788  if (S.CheckParameterPacksForExpansion(789          Pattern->getExprLoc(), Pattern->getSourceRange(), Unexpanded, MLTAL,790          /*FailOnPackProducingTemplates=*/false, Expand, RetainExpansion,791          NumExpansions, /*Diagnose=*/false) ||792      !Expand || RetainExpansion)793    return std::nullopt;794 795  if (NumExpansions && S.getLangOpts().BracketDepth < *NumExpansions)796    return std::nullopt;797  return NumExpansions;798}799 800ExprResult ConstraintSatisfactionChecker::EvaluateSlow(801    const FoldExpandedConstraint &Constraint,802    const MultiLevelTemplateArgumentList &MLTAL) {803 804  bool Conjunction = Constraint.getFoldOperator() ==805                     FoldExpandedConstraint::FoldOperatorKind::And;806  unsigned EffectiveDetailEndIndex = Satisfaction.Details.size();807 808  llvm::SmallVector<TemplateArgument> SubstitutedOutermost;809  // FIXME: Is PackSubstitutionIndex correct?810  llvm::SaveAndRestore _(PackSubstitutionIndex, S.ArgPackSubstIndex);811  std::optional<MultiLevelTemplateArgumentList> SubstitutedArgs =812      SubstitutionInTemplateArguments(813          static_cast<const NormalizedConstraintWithParamMapping &>(Constraint),814          MLTAL, SubstitutedOutermost);815  if (!SubstitutedArgs) {816    Satisfaction.IsSatisfied = false;817    return ExprError();818  }819 820  ExprResult Out;821  UnsignedOrNone NumExpansions =822      EvaluateFoldExpandedConstraintSize(Constraint, *SubstitutedArgs);823  if (!NumExpansions)824    return ExprEmpty();825 826  if (*NumExpansions == 0) {827    Satisfaction.IsSatisfied = Conjunction;828    return ExprEmpty();829  }830 831  for (unsigned I = 0; I < *NumExpansions; I++) {832    Sema::ArgPackSubstIndexRAII SubstIndex(S, I);833    Satisfaction.IsSatisfied = false;834    Satisfaction.ContainsErrors = false;835    ExprResult Expr =836        ConstraintSatisfactionChecker(S, Template, TemplateNameLoc,837                                      UnsignedOrNone(I), Satisfaction,838                                      /*BuildExpression=*/false)839            .Evaluate(Constraint.getNormalizedPattern(), *SubstitutedArgs);840    if (BuildExpression && Expr.isUsable()) {841      if (Out.isUnset())842        Out = Expr;843      else844        Out = BinaryOperator::Create(S.Context, Out.get(), Expr.get(),845                                     Conjunction ? BinaryOperatorKind::BO_LAnd846                                                 : BinaryOperatorKind::BO_LOr,847                                     S.Context.BoolTy, VK_PRValue, OK_Ordinary,848                                     Constraint.getBeginLoc(),849                                     FPOptionsOverride{});850    } else {851      assert(!BuildExpression || !Satisfaction.IsSatisfied);852    }853    if (!Conjunction && Satisfaction.IsSatisfied) {854      Satisfaction.Details.erase(Satisfaction.Details.begin() +855                                     EffectiveDetailEndIndex,856                                 Satisfaction.Details.end());857      break;858    }859    if (Satisfaction.IsSatisfied != Conjunction)860      return Out;861  }862 863  return Out;864}865 866ExprResult ConstraintSatisfactionChecker::Evaluate(867    const FoldExpandedConstraint &Constraint,868    const MultiLevelTemplateArgumentList &MLTAL) {869 870  llvm::FoldingSetNodeID ID;871  ID.AddPointer(Constraint.getPattern());872  HashParameterMapping(S, MLTAL, ID, std::nullopt).VisitConstraint(Constraint);873 874  if (auto Iter = S.UnsubstitutedConstraintSatisfactionCache.find(ID);875      Iter != S.UnsubstitutedConstraintSatisfactionCache.end()) {876 877    auto &Cached = Iter->second.Satisfaction;878    Satisfaction.ContainsErrors = Cached.ContainsErrors;879    Satisfaction.IsSatisfied = Cached.IsSatisfied;880    Satisfaction.Details.insert(Satisfaction.Details.end(),881                                Cached.Details.begin(), Cached.Details.end());882    return Iter->second.SubstExpr;883  }884 885  unsigned Size = Satisfaction.Details.size();886 887  ExprResult E = EvaluateSlow(Constraint, MLTAL);888  UnsubstitutedConstraintSatisfactionCacheResult Cache;889  Cache.Satisfaction.ContainsErrors = Satisfaction.ContainsErrors;890  Cache.Satisfaction.IsSatisfied = Satisfaction.IsSatisfied;891  Cache.Satisfaction.Details.insert(Cache.Satisfaction.Details.end(),892                                    Satisfaction.Details.begin() + Size,893                                    Satisfaction.Details.end());894  Cache.SubstExpr = E;895  S.UnsubstitutedConstraintSatisfactionCache.insert({ID, std::move(Cache)});896  return E;897}898 899ExprResult ConstraintSatisfactionChecker::EvaluateSlow(900    const ConceptIdConstraint &Constraint,901    const MultiLevelTemplateArgumentList &MLTAL, unsigned Size) {902  const ConceptReference *ConceptId = Constraint.getConceptId();903 904  llvm::SmallVector<TemplateArgument> SubstitutedOutermost;905  std::optional<MultiLevelTemplateArgumentList> SubstitutedArgs =906      SubstitutionInTemplateArguments(Constraint, MLTAL, SubstitutedOutermost);907 908  if (!SubstitutedArgs) {909    Satisfaction.IsSatisfied = false;910    // FIXME: diagnostics?911    return ExprError();912  }913 914  Sema::ArgPackSubstIndexRAII SubstIndex(915      S, Constraint.getPackSubstitutionIndex()916             ? Constraint.getPackSubstitutionIndex()917             : PackSubstitutionIndex);918 919  const ASTTemplateArgumentListInfo *Ori =920      ConceptId->getTemplateArgsAsWritten();921  TemplateDeductionInfo Info(TemplateNameLoc);922  Sema::SFINAETrap Trap(S, Info);923  Sema::InstantiatingTemplate _2(924      S, TemplateNameLoc, Sema::InstantiatingTemplate::ConstraintSubstitution{},925      const_cast<NamedDecl *>(Template), Constraint.getSourceRange());926 927  TemplateArgumentListInfo OutArgs(Ori->LAngleLoc, Ori->RAngleLoc);928  if (S.SubstTemplateArguments(Ori->arguments(), *SubstitutedArgs, OutArgs) ||929      Trap.hasErrorOccurred()) {930    Satisfaction.IsSatisfied = false;931    if (!Trap.hasErrorOccurred())932      return ExprError();933 934    PartialDiagnosticAt SubstDiag{SourceLocation(),935                                  PartialDiagnostic::NullDiagnostic()};936    Info.takeSFINAEDiagnostic(SubstDiag);937    // FIXME: This is an unfortunate consequence of there938    //  being no serialization code for PartialDiagnostics and the fact939    //  that serializing them would likely take a lot more storage than940    //  just storing them as strings. We would still like, in the941    //  future, to serialize the proper PartialDiagnostic as serializing942    //  it as a string defeats the purpose of the diagnostic mechanism.943    Satisfaction.Details.insert(944        Satisfaction.Details.begin() + Size,945        new (S.Context) ConstraintSubstitutionDiagnostic{946            SubstDiag.first,947            allocateStringFromConceptDiagnostic(S, SubstDiag.second)});948    return ExprError();949  }950 951  CXXScopeSpec SS;952  SS.Adopt(ConceptId->getNestedNameSpecifierLoc());953 954  ExprResult SubstitutedConceptId = S.CheckConceptTemplateId(955      SS, ConceptId->getTemplateKWLoc(), ConceptId->getConceptNameInfo(),956      ConceptId->getFoundDecl(), ConceptId->getNamedConcept(), &OutArgs,957      /*DoCheckConstraintSatisfaction=*/false);958 959  if (SubstitutedConceptId.isInvalid() || Trap.hasErrorOccurred())960    return ExprError();961 962  if (Size != Satisfaction.Details.size()) {963    Satisfaction.Details.insert(964        Satisfaction.Details.begin() + Size,965        UnsatisfiedConstraintRecord(966            SubstitutedConceptId.getAs<ConceptSpecializationExpr>()967                ->getConceptReference()));968  }969  return SubstitutedConceptId;970}971 972ExprResult ConstraintSatisfactionChecker::Evaluate(973    const ConceptIdConstraint &Constraint,974    const MultiLevelTemplateArgumentList &MLTAL) {975 976  const ConceptReference *ConceptId = Constraint.getConceptId();977 978  UnsignedOrNone OuterPackSubstIndex =979      Constraint.getPackSubstitutionIndex()980          ? Constraint.getPackSubstitutionIndex()981          : PackSubstitutionIndex;982 983  Sema::InstantiatingTemplate InstTemplate(984      S, ConceptId->getBeginLoc(),985      Sema::InstantiatingTemplate::ConstraintsCheck{},986      ConceptId->getNamedConcept(),987      // We may have empty template arguments when checking non-dependent988      // nested constraint expressions.989      // In such cases, non-SFINAE errors would have already been diagnosed990      // during parameter mapping substitution, so the instantiating template991      // arguments are less useful here.992      MLTAL.getNumSubstitutedLevels() ? MLTAL.getInnermost()993                                      : ArrayRef<TemplateArgument>{},994      Constraint.getSourceRange());995  if (InstTemplate.isInvalid())996    return ExprError();997 998  unsigned Size = Satisfaction.Details.size();999 1000  ExprResult E = Evaluate(Constraint.getNormalizedConstraint(), MLTAL);1001 1002  if (E.isInvalid()) {1003    Satisfaction.Details.insert(Satisfaction.Details.begin() + Size, ConceptId);1004    return E;1005  }1006 1007  // ConceptIdConstraint is only relevant for diagnostics,1008  // so if the normalized constraint is satisfied, we should not1009  // substitute into the constraint.1010  if (Satisfaction.IsSatisfied)1011    return E;1012 1013  llvm::FoldingSetNodeID ID;1014  ID.AddPointer(Constraint.getConceptId());1015  ID.AddInteger(OuterPackSubstIndex.toInternalRepresentation());1016  HashParameterMapping(S, MLTAL, ID, OuterPackSubstIndex)1017      .VisitConstraint(Constraint);1018 1019  if (auto Iter = S.UnsubstitutedConstraintSatisfactionCache.find(ID);1020      Iter != S.UnsubstitutedConstraintSatisfactionCache.end()) {1021 1022    auto &Cached = Iter->second.Satisfaction;1023    Satisfaction.ContainsErrors = Cached.ContainsErrors;1024    Satisfaction.IsSatisfied = Cached.IsSatisfied;1025    Satisfaction.Details.insert(Satisfaction.Details.begin() + Size,1026                                Cached.Details.begin(), Cached.Details.end());1027    return Iter->second.SubstExpr;1028  }1029 1030  ExprResult CE = EvaluateSlow(Constraint, MLTAL, Size);1031  if (CE.isInvalid())1032    return E;1033  UnsubstitutedConstraintSatisfactionCacheResult Cache;1034  Cache.Satisfaction.ContainsErrors = Satisfaction.ContainsErrors;1035  Cache.Satisfaction.IsSatisfied = Satisfaction.IsSatisfied;1036  Cache.Satisfaction.Details.insert(Cache.Satisfaction.Details.end(),1037                                    Satisfaction.Details.begin() + Size,1038                                    Satisfaction.Details.end());1039  Cache.SubstExpr = CE;1040  S.UnsubstitutedConstraintSatisfactionCache.insert({ID, std::move(Cache)});1041  return CE;1042}1043 1044ExprResult ConstraintSatisfactionChecker::Evaluate(1045    const CompoundConstraint &Constraint,1046    const MultiLevelTemplateArgumentList &MLTAL) {1047 1048  unsigned EffectiveDetailEndIndex = Satisfaction.Details.size();1049 1050  bool Conjunction =1051      Constraint.getCompoundKind() == NormalizedConstraint::CCK_Conjunction;1052 1053  ExprResult LHS = Evaluate(Constraint.getLHS(), MLTAL);1054 1055  if (Conjunction && (!Satisfaction.IsSatisfied || Satisfaction.ContainsErrors))1056    return LHS;1057 1058  if (!Conjunction && !LHS.isInvalid() && Satisfaction.IsSatisfied &&1059      !Satisfaction.ContainsErrors)1060    return LHS;1061 1062  Satisfaction.ContainsErrors = false;1063  Satisfaction.IsSatisfied = false;1064 1065  ExprResult RHS = Evaluate(Constraint.getRHS(), MLTAL);1066 1067  if (!Conjunction && !RHS.isInvalid() && Satisfaction.IsSatisfied &&1068      !Satisfaction.ContainsErrors)1069    Satisfaction.Details.erase(Satisfaction.Details.begin() +1070                                   EffectiveDetailEndIndex,1071                               Satisfaction.Details.end());1072 1073  if (!BuildExpression)1074    return Satisfaction.ContainsErrors ? ExprError() : ExprEmpty();1075 1076  if (!LHS.isUsable())1077    return RHS;1078 1079  if (!RHS.isUsable())1080    return LHS;1081 1082  return BinaryOperator::Create(S.Context, LHS.get(), RHS.get(),1083                                Conjunction ? BinaryOperatorKind::BO_LAnd1084                                            : BinaryOperatorKind::BO_LOr,1085                                S.Context.BoolTy, VK_PRValue, OK_Ordinary,1086                                Constraint.getBeginLoc(), FPOptionsOverride{});1087}1088 1089ExprResult ConstraintSatisfactionChecker::Evaluate(1090    const NormalizedConstraint &Constraint,1091    const MultiLevelTemplateArgumentList &MLTAL) {1092  switch (Constraint.getKind()) {1093  case NormalizedConstraint::ConstraintKind::Atomic:1094    return Evaluate(static_cast<const AtomicConstraint &>(Constraint), MLTAL);1095 1096  case NormalizedConstraint::ConstraintKind::FoldExpanded:1097    return Evaluate(static_cast<const FoldExpandedConstraint &>(Constraint),1098                    MLTAL);1099 1100  case NormalizedConstraint::ConstraintKind::ConceptId:1101    return Evaluate(static_cast<const ConceptIdConstraint &>(Constraint),1102                    MLTAL);1103 1104  case NormalizedConstraint::ConstraintKind::Compound:1105    return Evaluate(static_cast<const CompoundConstraint &>(Constraint), MLTAL);1106  }1107  llvm_unreachable("Unknown ConstraintKind enum");1108}1109 1110static bool CheckConstraintSatisfaction(1111    Sema &S, const NamedDecl *Template,1112    ArrayRef<AssociatedConstraint> AssociatedConstraints,1113    const MultiLevelTemplateArgumentList &TemplateArgsLists,1114    SourceRange TemplateIDRange, ConstraintSatisfaction &Satisfaction,1115    Expr **ConvertedExpr, const ConceptReference *TopLevelConceptId = nullptr) {1116 1117  if (ConvertedExpr)1118    *ConvertedExpr = nullptr;1119 1120  if (AssociatedConstraints.empty()) {1121    Satisfaction.IsSatisfied = true;1122    return false;1123  }1124 1125  if (TemplateArgsLists.isAnyArgInstantiationDependent()) {1126    // No need to check satisfaction for dependent constraint expressions.1127    Satisfaction.IsSatisfied = true;1128    return false;1129  }1130 1131  llvm::ArrayRef<TemplateArgument> Args;1132  if (TemplateArgsLists.getNumLevels() != 0)1133    Args = TemplateArgsLists.getInnermost();1134 1135  struct SynthesisContextPair {1136    Sema::InstantiatingTemplate Inst;1137    Sema::NonSFINAEContext NSC;1138    SynthesisContextPair(Sema &S, NamedDecl *Template,1139                         ArrayRef<TemplateArgument> TemplateArgs,1140                         SourceRange InstantiationRange)1141        : Inst(S, InstantiationRange.getBegin(),1142               Sema::InstantiatingTemplate::ConstraintsCheck{}, Template,1143               TemplateArgs, InstantiationRange),1144          NSC(S) {}1145  };1146  std::optional<SynthesisContextPair> SynthesisContext;1147  if (!TopLevelConceptId)1148    SynthesisContext.emplace(S, const_cast<NamedDecl *>(Template), Args,1149                             TemplateIDRange);1150 1151  const NormalizedConstraint *C =1152      S.getNormalizedAssociatedConstraints(Template, AssociatedConstraints);1153  if (!C) {1154    Satisfaction.IsSatisfied = false;1155    return true;1156  }1157 1158  if (TopLevelConceptId)1159    C = ConceptIdConstraint::Create(S.getASTContext(), TopLevelConceptId,1160                                    const_cast<NormalizedConstraint *>(C),1161                                    Template, /*CSE=*/nullptr,1162                                    S.ArgPackSubstIndex);1163 1164  ExprResult Res = ConstraintSatisfactionChecker(1165                       S, Template, TemplateIDRange.getBegin(),1166                       S.ArgPackSubstIndex, Satisfaction,1167                       /*BuildExpression=*/ConvertedExpr != nullptr)1168                       .Evaluate(*C, TemplateArgsLists);1169 1170  if (Res.isInvalid())1171    return true;1172 1173  if (Res.isUsable() && ConvertedExpr)1174    *ConvertedExpr = Res.get();1175 1176  return false;1177}1178 1179bool Sema::CheckConstraintSatisfaction(1180    ConstrainedDeclOrNestedRequirement Entity,1181    ArrayRef<AssociatedConstraint> AssociatedConstraints,1182    const MultiLevelTemplateArgumentList &TemplateArgsLists,1183    SourceRange TemplateIDRange, ConstraintSatisfaction &OutSatisfaction,1184    const ConceptReference *TopLevelConceptId, Expr **ConvertedExpr) {1185  if (AssociatedConstraints.empty()) {1186    OutSatisfaction.IsSatisfied = true;1187    return false;1188  }1189  const auto *Template = Entity.dyn_cast<const NamedDecl *>();1190  if (!Template) {1191    return ::CheckConstraintSatisfaction(1192        *this, nullptr, AssociatedConstraints, TemplateArgsLists,1193        TemplateIDRange, OutSatisfaction, ConvertedExpr, TopLevelConceptId);1194  }1195  // Invalid templates could make their way here. Substituting them could result1196  // in dependent expressions.1197  if (Template->isInvalidDecl()) {1198    OutSatisfaction.IsSatisfied = false;1199    return true;1200  }1201 1202  // A list of the template argument list flattened in a predictible manner for1203  // the purposes of caching. The ConstraintSatisfaction type is in AST so it1204  // has no access to the MultiLevelTemplateArgumentList, so this has to happen1205  // here.1206  llvm::SmallVector<TemplateArgument, 4> FlattenedArgs;1207  for (auto List : TemplateArgsLists)1208    for (const TemplateArgument &Arg : List.Args)1209      FlattenedArgs.emplace_back(Context.getCanonicalTemplateArgument(Arg));1210 1211  const NamedDecl *Owner = Template;1212  if (TopLevelConceptId)1213    Owner = TopLevelConceptId->getNamedConcept();1214 1215  llvm::FoldingSetNodeID ID;1216  ConstraintSatisfaction::Profile(ID, Context, Owner, FlattenedArgs);1217  void *InsertPos;1218  if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {1219    OutSatisfaction = *Cached;1220    return false;1221  }1222 1223  auto Satisfaction =1224      std::make_unique<ConstraintSatisfaction>(Owner, FlattenedArgs);1225  if (::CheckConstraintSatisfaction(1226          *this, Template, AssociatedConstraints, TemplateArgsLists,1227          TemplateIDRange, *Satisfaction, ConvertedExpr, TopLevelConceptId)) {1228    OutSatisfaction = std::move(*Satisfaction);1229    return true;1230  }1231 1232  if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {1233    // The evaluation of this constraint resulted in us trying to re-evaluate it1234    // recursively. This isn't really possible, except we try to form a1235    // RecoveryExpr as a part of the evaluation.  If this is the case, just1236    // return the 'cached' version (which will have the same result), and save1237    // ourselves the extra-insert. If it ever becomes possible to legitimately1238    // recursively check a constraint, we should skip checking the 'inner' one1239    // above, and replace the cached version with this one, as it would be more1240    // specific.1241    OutSatisfaction = *Cached;1242    return false;1243  }1244 1245  // Else we can simply add this satisfaction to the list.1246  OutSatisfaction = *Satisfaction;1247  // We cannot use InsertPos here because CheckConstraintSatisfaction might have1248  // invalidated it.1249  // Note that entries of SatisfactionCache are deleted in Sema's destructor.1250  SatisfactionCache.InsertNode(Satisfaction.release());1251  return false;1252}1253 1254static ExprResult1255SubstituteConceptsInConstraintExpression(Sema &S, const NamedDecl *D,1256                                         const ConceptSpecializationExpr *CSE,1257                                         UnsignedOrNone SubstIndex) {1258 1259  // [C++2c] [temp.constr.normal]1260  // Otherwise, to form CE, any non-dependent concept template argument Ai1261  // is substituted into the constraint-expression of C.1262  // If any such substitution results in an invalid concept-id,1263  // the program is ill-formed; no diagnostic is required.1264 1265  ConceptDecl *Concept = CSE->getNamedConcept()->getCanonicalDecl();1266  Sema::ArgPackSubstIndexRAII _(S, SubstIndex);1267 1268  const ASTTemplateArgumentListInfo *ArgsAsWritten =1269      CSE->getTemplateArgsAsWritten();1270  if (llvm::none_of(1271          ArgsAsWritten->arguments(), [&](const TemplateArgumentLoc &ArgLoc) {1272            return !ArgLoc.getArgument().isDependent() &&1273                   ArgLoc.getArgument().isConceptOrConceptTemplateParameter();1274          })) {1275    return Concept->getConstraintExpr();1276  }1277 1278  MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(1279      Concept, Concept->getLexicalDeclContext(),1280      /*Final=*/false, CSE->getTemplateArguments(),1281      /*RelativeToPrimary=*/true,1282      /*Pattern=*/nullptr,1283      /*ForConstraintInstantiation=*/true);1284  return S.SubstConceptTemplateArguments(CSE, Concept->getConstraintExpr(),1285                                         MLTAL);1286}1287 1288bool Sema::CheckConstraintSatisfaction(1289    const ConceptSpecializationExpr *ConstraintExpr,1290    ConstraintSatisfaction &Satisfaction) {1291 1292  ExprResult Res = SubstituteConceptsInConstraintExpression(1293      *this, nullptr, ConstraintExpr, ArgPackSubstIndex);1294  if (!Res.isUsable())1295    return true;1296 1297  llvm::SmallVector<AssociatedConstraint, 1> Constraints;1298  Constraints.emplace_back(Res.get());1299 1300  MultiLevelTemplateArgumentList MLTAL(ConstraintExpr->getNamedConcept(),1301                                       ConstraintExpr->getTemplateArguments(),1302                                       true);1303 1304  return CheckConstraintSatisfaction(1305      ConstraintExpr->getNamedConcept(), Constraints, MLTAL,1306      ConstraintExpr->getSourceRange(), Satisfaction,1307      ConstraintExpr->getConceptReference());1308}1309 1310bool Sema::SetupConstraintScope(1311    FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,1312    const MultiLevelTemplateArgumentList &MLTAL,1313    LocalInstantiationScope &Scope) {1314  assert(!isLambdaCallOperator(FD) &&1315         "Use LambdaScopeForCallOperatorInstantiationRAII to handle lambda "1316         "instantiations");1317  if (FD->isTemplateInstantiation() && FD->getPrimaryTemplate()) {1318    FunctionTemplateDecl *PrimaryTemplate = FD->getPrimaryTemplate();1319    InstantiatingTemplate Inst(1320        *this, FD->getPointOfInstantiation(),1321        Sema::InstantiatingTemplate::ConstraintsCheck{}, PrimaryTemplate,1322        TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},1323        SourceRange());1324    if (Inst.isInvalid())1325      return true;1326 1327    // addInstantiatedParametersToScope creates a map of 'uninstantiated' to1328    // 'instantiated' parameters and adds it to the context. For the case where1329    // this function is a template being instantiated NOW, we also need to add1330    // the list of current template arguments to the list so that they also can1331    // be picked out of the map.1332    if (auto *SpecArgs = FD->getTemplateSpecializationArgs()) {1333      MultiLevelTemplateArgumentList JustTemplArgs(FD, SpecArgs->asArray(),1334                                                   /*Final=*/false);1335      if (addInstantiatedParametersToScope(1336              FD, PrimaryTemplate->getTemplatedDecl(), Scope, JustTemplArgs))1337        return true;1338    }1339 1340    // If this is a member function, make sure we get the parameters that1341    // reference the original primary template.1342    if (FunctionTemplateDecl *FromMemTempl =1343            PrimaryTemplate->getInstantiatedFromMemberTemplate()) {1344      if (addInstantiatedParametersToScope(FD, FromMemTempl->getTemplatedDecl(),1345                                           Scope, MLTAL))1346        return true;1347    }1348 1349    return false;1350  }1351 1352  if (FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization ||1353      FD->getTemplatedKind() == FunctionDecl::TK_DependentNonTemplate) {1354    FunctionDecl *InstantiatedFrom =1355        FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization1356            ? FD->getInstantiatedFromMemberFunction()1357            : FD->getInstantiatedFromDecl();1358 1359    InstantiatingTemplate Inst(1360        *this, FD->getPointOfInstantiation(),1361        Sema::InstantiatingTemplate::ConstraintsCheck{}, InstantiatedFrom,1362        TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},1363        SourceRange());1364    if (Inst.isInvalid())1365      return true;1366 1367    // Case where this was not a template, but instantiated as a1368    // child-function.1369    if (addInstantiatedParametersToScope(FD, InstantiatedFrom, Scope, MLTAL))1370      return true;1371  }1372 1373  return false;1374}1375 1376// This function collects all of the template arguments for the purposes of1377// constraint-instantiation and checking.1378std::optional<MultiLevelTemplateArgumentList>1379Sema::SetupConstraintCheckingTemplateArgumentsAndScope(1380    FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,1381    LocalInstantiationScope &Scope) {1382  MultiLevelTemplateArgumentList MLTAL;1383 1384  // Collect the list of template arguments relative to the 'primary' template.1385  // We need the entire list, since the constraint is completely uninstantiated1386  // at this point.1387  MLTAL =1388      getTemplateInstantiationArgs(FD, FD->getLexicalDeclContext(),1389                                   /*Final=*/false, /*Innermost=*/std::nullopt,1390                                   /*RelativeToPrimary=*/true,1391                                   /*Pattern=*/nullptr,1392                                   /*ForConstraintInstantiation=*/true);1393  // Lambdas are handled by LambdaScopeForCallOperatorInstantiationRAII.1394  if (isLambdaCallOperator(FD))1395    return MLTAL;1396  if (SetupConstraintScope(FD, TemplateArgs, MLTAL, Scope))1397    return std::nullopt;1398 1399  return MLTAL;1400}1401 1402bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,1403                                    ConstraintSatisfaction &Satisfaction,1404                                    SourceLocation UsageLoc,1405                                    bool ForOverloadResolution) {1406  // Don't check constraints if the function is dependent. Also don't check if1407  // this is a function template specialization, as the call to1408  // CheckFunctionTemplateConstraints after this will check it1409  // better.1410  if (FD->isDependentContext() ||1411      FD->getTemplatedKind() ==1412          FunctionDecl::TK_FunctionTemplateSpecialization) {1413    Satisfaction.IsSatisfied = true;1414    return false;1415  }1416 1417  // A lambda conversion operator has the same constraints as the call operator1418  // and constraints checking relies on whether we are in a lambda call operator1419  // (and may refer to its parameters), so check the call operator instead.1420  // Note that the declarations outside of the lambda should also be1421  // considered. Turning on the 'ForOverloadResolution' flag results in the1422  // LocalInstantiationScope not looking into its parents, but we can still1423  // access Decls from the parents while building a lambda RAII scope later.1424  if (const auto *MD = dyn_cast<CXXConversionDecl>(FD);1425      MD && isLambdaConversionOperator(const_cast<CXXConversionDecl *>(MD)))1426    return CheckFunctionConstraints(MD->getParent()->getLambdaCallOperator(),1427                                    Satisfaction, UsageLoc,1428                                    /*ShouldAddDeclsFromParentScope=*/true);1429 1430  DeclContext *CtxToSave = const_cast<FunctionDecl *>(FD);1431 1432  while (isLambdaCallOperator(CtxToSave) || FD->isTransparentContext()) {1433    if (isLambdaCallOperator(CtxToSave))1434      CtxToSave = CtxToSave->getParent()->getParent();1435    else1436      CtxToSave = CtxToSave->getNonTransparentContext();1437  }1438 1439  ContextRAII SavedContext{*this, CtxToSave};1440  LocalInstantiationScope Scope(*this, !ForOverloadResolution);1441  std::optional<MultiLevelTemplateArgumentList> MLTAL =1442      SetupConstraintCheckingTemplateArgumentsAndScope(1443          const_cast<FunctionDecl *>(FD), {}, Scope);1444 1445  if (!MLTAL)1446    return true;1447 1448  Qualifiers ThisQuals;1449  CXXRecordDecl *Record = nullptr;1450  if (auto *Method = dyn_cast<CXXMethodDecl>(FD)) {1451    ThisQuals = Method->getMethodQualifiers();1452    Record = const_cast<CXXRecordDecl *>(Method->getParent());1453  }1454  CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);1455 1456  LambdaScopeForCallOperatorInstantiationRAII LambdaScope(1457      *this, const_cast<FunctionDecl *>(FD), *MLTAL, Scope,1458      ForOverloadResolution);1459 1460  return CheckConstraintSatisfaction(1461      FD, FD->getTrailingRequiresClause(), *MLTAL,1462      SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),1463      Satisfaction);1464}1465 1466static const Expr *SubstituteConstraintExpressionWithoutSatisfaction(1467    Sema &S, const Sema::TemplateCompareNewDeclInfo &DeclInfo,1468    const Expr *ConstrExpr) {1469  MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(1470      DeclInfo.getDecl(), DeclInfo.getDeclContext(), /*Final=*/false,1471      /*Innermost=*/std::nullopt,1472      /*RelativeToPrimary=*/true,1473      /*Pattern=*/nullptr, /*ForConstraintInstantiation=*/true,1474      /*SkipForSpecialization*/ false);1475 1476  if (MLTAL.getNumSubstitutedLevels() == 0)1477    return ConstrExpr;1478 1479  Sema::NonSFINAEContext _(S);1480  Sema::InstantiatingTemplate Inst(1481      S, DeclInfo.getLocation(),1482      Sema::InstantiatingTemplate::ConstraintNormalization{},1483      const_cast<NamedDecl *>(DeclInfo.getDecl()), SourceRange{});1484  if (Inst.isInvalid())1485    return nullptr;1486 1487  // Set up a dummy 'instantiation' scope in the case of reference to function1488  // parameters that the surrounding function hasn't been instantiated yet. Note1489  // this may happen while we're comparing two templates' constraint1490  // equivalence.1491  std::optional<LocalInstantiationScope> ScopeForParameters;1492  if (const NamedDecl *ND = DeclInfo.getDecl();1493      ND && ND->isFunctionOrFunctionTemplate()) {1494    ScopeForParameters.emplace(S, /*CombineWithOuterScope=*/true);1495    const FunctionDecl *FD = ND->getAsFunction();1496    if (FunctionTemplateDecl *Template = FD->getDescribedFunctionTemplate();1497        Template && Template->getInstantiatedFromMemberTemplate())1498      FD = Template->getInstantiatedFromMemberTemplate()->getTemplatedDecl();1499    for (auto *PVD : FD->parameters()) {1500      if (ScopeForParameters->getInstantiationOfIfExists(PVD))1501        continue;1502      if (!PVD->isParameterPack()) {1503        ScopeForParameters->InstantiatedLocal(PVD, PVD);1504        continue;1505      }1506      // This is hacky: we're mapping the parameter pack to a size-of-1 argument1507      // to avoid building SubstTemplateTypeParmPackTypes for1508      // PackExpansionTypes. The SubstTemplateTypeParmPackType node would1509      // otherwise reference the AssociatedDecl of the template arguments, which1510      // is, in this case, the template declaration.1511      //1512      // However, as we are in the process of comparing potential1513      // re-declarations, the canonical declaration is the declaration itself at1514      // this point. So if we didn't expand these packs, we would end up with an1515      // incorrect profile difference because we will be profiling the1516      // canonical types!1517      //1518      // FIXME: Improve the "no-transform" machinery in FindInstantiatedDecl so1519      // that we can eliminate the Scope in the cases where the declarations are1520      // not necessarily instantiated. It would also benefit the noexcept1521      // specifier comparison.1522      ScopeForParameters->MakeInstantiatedLocalArgPack(PVD);1523      ScopeForParameters->InstantiatedLocalPackArg(PVD, PVD);1524    }1525  }1526 1527  std::optional<Sema::CXXThisScopeRAII> ThisScope;1528 1529  // See TreeTransform::RebuildTemplateSpecializationType. A context scope is1530  // essential for having an injected class as the canonical type for a template1531  // specialization type at the rebuilding stage. This guarantees that, for1532  // out-of-line definitions, injected class name types and their equivalent1533  // template specializations can be profiled to the same value, which makes it1534  // possible that e.g. constraints involving C<Class<T>> and C<Class> are1535  // perceived identical.1536  std::optional<Sema::ContextRAII> ContextScope;1537  const DeclContext *DC = [&] {1538    if (!DeclInfo.getDecl())1539      return DeclInfo.getDeclContext();1540    return DeclInfo.getDecl()->getFriendObjectKind()1541               ? DeclInfo.getLexicalDeclContext()1542               : DeclInfo.getDeclContext();1543  }();1544  if (auto *RD = dyn_cast<CXXRecordDecl>(DC)) {1545    ThisScope.emplace(S, const_cast<CXXRecordDecl *>(RD), Qualifiers());1546    ContextScope.emplace(S, const_cast<DeclContext *>(cast<DeclContext>(RD)),1547                         /*NewThisContext=*/false);1548  }1549  EnterExpressionEvaluationContext UnevaluatedContext(1550      S, Sema::ExpressionEvaluationContext::Unevaluated,1551      Sema::ReuseLambdaContextDecl);1552  ExprResult SubstConstr = S.SubstConstraintExprWithoutSatisfaction(1553      const_cast<clang::Expr *>(ConstrExpr), MLTAL);1554  if (!SubstConstr.isUsable())1555    return nullptr;1556  return SubstConstr.get();1557}1558 1559bool Sema::AreConstraintExpressionsEqual(const NamedDecl *Old,1560                                         const Expr *OldConstr,1561                                         const TemplateCompareNewDeclInfo &New,1562                                         const Expr *NewConstr) {1563  if (OldConstr == NewConstr)1564    return true;1565  // C++ [temp.constr.decl]p41566  if (Old && !New.isInvalid() && !New.ContainsDecl(Old) &&1567      Old->getLexicalDeclContext() != New.getLexicalDeclContext()) {1568    if (const Expr *SubstConstr =1569            SubstituteConstraintExpressionWithoutSatisfaction(*this, Old,1570                                                              OldConstr))1571      OldConstr = SubstConstr;1572    else1573      return false;1574    if (const Expr *SubstConstr =1575            SubstituteConstraintExpressionWithoutSatisfaction(*this, New,1576                                                              NewConstr))1577      NewConstr = SubstConstr;1578    else1579      return false;1580  }1581 1582  llvm::FoldingSetNodeID ID1, ID2;1583  OldConstr->Profile(ID1, Context, /*Canonical=*/true);1584  NewConstr->Profile(ID2, Context, /*Canonical=*/true);1585  return ID1 == ID2;1586}1587 1588bool Sema::FriendConstraintsDependOnEnclosingTemplate(const FunctionDecl *FD) {1589  assert(FD->getFriendObjectKind() && "Must be a friend!");1590 1591  // The logic for non-templates is handled in ASTContext::isSameEntity, so we1592  // don't have to bother checking 'DependsOnEnclosingTemplate' for a1593  // non-function-template.1594  assert(FD->getDescribedFunctionTemplate() &&1595         "Non-function templates don't need to be checked");1596 1597  SmallVector<AssociatedConstraint, 3> ACs;1598  FD->getDescribedFunctionTemplate()->getAssociatedConstraints(ACs);1599 1600  unsigned OldTemplateDepth = CalculateTemplateDepthForConstraints(*this, FD);1601  for (const AssociatedConstraint &AC : ACs)1602    if (ConstraintExpressionDependsOnEnclosingTemplate(FD, OldTemplateDepth,1603                                                       AC.ConstraintExpr))1604      return true;1605 1606  return false;1607}1608 1609bool Sema::EnsureTemplateArgumentListConstraints(1610    TemplateDecl *TD, const MultiLevelTemplateArgumentList &TemplateArgsLists,1611    SourceRange TemplateIDRange) {1612  ConstraintSatisfaction Satisfaction;1613  llvm::SmallVector<AssociatedConstraint, 3> AssociatedConstraints;1614  TD->getAssociatedConstraints(AssociatedConstraints);1615  if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgsLists,1616                                  TemplateIDRange, Satisfaction))1617    return true;1618 1619  if (!Satisfaction.IsSatisfied) {1620    SmallString<128> TemplateArgString;1621    TemplateArgString = " ";1622    TemplateArgString += getTemplateArgumentBindingsText(1623        TD->getTemplateParameters(), TemplateArgsLists.getInnermost().data(),1624        TemplateArgsLists.getInnermost().size());1625 1626    Diag(TemplateIDRange.getBegin(),1627         diag::err_template_arg_list_constraints_not_satisfied)1628        << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD1629        << TemplateArgString << TemplateIDRange;1630    DiagnoseUnsatisfiedConstraint(Satisfaction);1631    return true;1632  }1633  return false;1634}1635 1636static bool CheckFunctionConstraintsWithoutInstantiation(1637    Sema &SemaRef, SourceLocation PointOfInstantiation,1638    FunctionTemplateDecl *Template, ArrayRef<TemplateArgument> TemplateArgs,1639    ConstraintSatisfaction &Satisfaction) {1640  SmallVector<AssociatedConstraint, 3> TemplateAC;1641  Template->getAssociatedConstraints(TemplateAC);1642  if (TemplateAC.empty()) {1643    Satisfaction.IsSatisfied = true;1644    return false;1645  }1646 1647  LocalInstantiationScope Scope(SemaRef);1648 1649  FunctionDecl *FD = Template->getTemplatedDecl();1650  // Collect the list of template arguments relative to the 'primary'1651  // template. We need the entire list, since the constraint is completely1652  // uninstantiated at this point.1653 1654  MultiLevelTemplateArgumentList MLTAL;1655  {1656    // getTemplateInstantiationArgs uses this instantiation context to find out1657    // template arguments for uninstantiated functions.1658    // We don't want this RAII object to persist, because there would be1659    // otherwise duplicate diagnostic notes.1660    Sema::InstantiatingTemplate Inst(1661        SemaRef, PointOfInstantiation,1662        Sema::InstantiatingTemplate::ConstraintsCheck{}, Template, TemplateArgs,1663        PointOfInstantiation);1664    if (Inst.isInvalid())1665      return true;1666    MLTAL = SemaRef.getTemplateInstantiationArgs(1667        /*D=*/FD, FD,1668        /*Final=*/false, /*Innermost=*/{}, /*RelativeToPrimary=*/true,1669        /*Pattern=*/nullptr, /*ForConstraintInstantiation=*/true);1670  }1671 1672  Sema::ContextRAII SavedContext(SemaRef, FD);1673  return SemaRef.CheckConstraintSatisfaction(1674      Template, TemplateAC, MLTAL, PointOfInstantiation, Satisfaction);1675}1676 1677bool Sema::CheckFunctionTemplateConstraints(1678    SourceLocation PointOfInstantiation, FunctionDecl *Decl,1679    ArrayRef<TemplateArgument> TemplateArgs,1680    ConstraintSatisfaction &Satisfaction) {1681  // In most cases we're not going to have constraints, so check for that first.1682  FunctionTemplateDecl *Template = Decl->getPrimaryTemplate();1683 1684  if (!Template)1685    return ::CheckFunctionConstraintsWithoutInstantiation(1686        *this, PointOfInstantiation, Decl->getDescribedFunctionTemplate(),1687        TemplateArgs, Satisfaction);1688 1689  // Note - code synthesis context for the constraints check is created1690  // inside CheckConstraintsSatisfaction.1691  SmallVector<AssociatedConstraint, 3> TemplateAC;1692  Template->getAssociatedConstraints(TemplateAC);1693  if (TemplateAC.empty()) {1694    Satisfaction.IsSatisfied = true;1695    return false;1696  }1697 1698  // Enter the scope of this instantiation. We don't use1699  // PushDeclContext because we don't have a scope.1700  Sema::ContextRAII savedContext(*this, Decl);1701  LocalInstantiationScope Scope(*this);1702 1703  std::optional<MultiLevelTemplateArgumentList> MLTAL =1704      SetupConstraintCheckingTemplateArgumentsAndScope(Decl, TemplateArgs,1705                                                       Scope);1706 1707  if (!MLTAL)1708    return true;1709 1710  Qualifiers ThisQuals;1711  CXXRecordDecl *Record = nullptr;1712  if (auto *Method = dyn_cast<CXXMethodDecl>(Decl)) {1713    ThisQuals = Method->getMethodQualifiers();1714    Record = Method->getParent();1715  }1716 1717  CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);1718  LambdaScopeForCallOperatorInstantiationRAII LambdaScope(*this, Decl, *MLTAL,1719                                                          Scope);1720 1721  return CheckConstraintSatisfaction(Template, TemplateAC, *MLTAL,1722                                     PointOfInstantiation, Satisfaction);1723}1724 1725static void diagnoseUnsatisfiedRequirement(Sema &S,1726                                           concepts::ExprRequirement *Req,1727                                           bool First) {1728  assert(!Req->isSatisfied() &&1729         "Diagnose() can only be used on an unsatisfied requirement");1730  switch (Req->getSatisfactionStatus()) {1731  case concepts::ExprRequirement::SS_Dependent:1732    llvm_unreachable("Diagnosing a dependent requirement");1733    break;1734  case concepts::ExprRequirement::SS_ExprSubstitutionFailure: {1735    auto *SubstDiag = Req->getExprSubstitutionDiagnostic();1736    if (!SubstDiag->DiagMessage.empty())1737      S.Diag(SubstDiag->DiagLoc,1738             diag::note_expr_requirement_expr_substitution_error)1739          << (int)First << SubstDiag->SubstitutedEntity1740          << SubstDiag->DiagMessage;1741    else1742      S.Diag(SubstDiag->DiagLoc,1743             diag::note_expr_requirement_expr_unknown_substitution_error)1744          << (int)First << SubstDiag->SubstitutedEntity;1745    break;1746  }1747  case concepts::ExprRequirement::SS_NoexceptNotMet:1748    S.Diag(Req->getNoexceptLoc(), diag::note_expr_requirement_noexcept_not_met)1749        << (int)First << Req->getExpr();1750    break;1751  case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {1752    auto *SubstDiag =1753        Req->getReturnTypeRequirement().getSubstitutionDiagnostic();1754    if (!SubstDiag->DiagMessage.empty())1755      S.Diag(SubstDiag->DiagLoc,1756             diag::note_expr_requirement_type_requirement_substitution_error)1757          << (int)First << SubstDiag->SubstitutedEntity1758          << SubstDiag->DiagMessage;1759    else1760      S.Diag(1761          SubstDiag->DiagLoc,1762          diag::1763              note_expr_requirement_type_requirement_unknown_substitution_error)1764          << (int)First << SubstDiag->SubstitutedEntity;1765    break;1766  }1767  case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: {1768    ConceptSpecializationExpr *ConstraintExpr =1769        Req->getReturnTypeRequirementSubstitutedConstraintExpr();1770    S.DiagnoseUnsatisfiedConstraint(ConstraintExpr);1771    break;1772  }1773  case concepts::ExprRequirement::SS_Satisfied:1774    llvm_unreachable("We checked this above");1775  }1776}1777 1778static void diagnoseUnsatisfiedRequirement(Sema &S,1779                                           concepts::TypeRequirement *Req,1780                                           bool First) {1781  assert(!Req->isSatisfied() &&1782         "Diagnose() can only be used on an unsatisfied requirement");1783  switch (Req->getSatisfactionStatus()) {1784  case concepts::TypeRequirement::SS_Dependent:1785    llvm_unreachable("Diagnosing a dependent requirement");1786    return;1787  case concepts::TypeRequirement::SS_SubstitutionFailure: {1788    auto *SubstDiag = Req->getSubstitutionDiagnostic();1789    if (!SubstDiag->DiagMessage.empty())1790      S.Diag(SubstDiag->DiagLoc, diag::note_type_requirement_substitution_error)1791          << (int)First << SubstDiag->SubstitutedEntity1792          << SubstDiag->DiagMessage;1793    else1794      S.Diag(SubstDiag->DiagLoc,1795             diag::note_type_requirement_unknown_substitution_error)1796          << (int)First << SubstDiag->SubstitutedEntity;1797    return;1798  }1799  default:1800    llvm_unreachable("Unknown satisfaction status");1801    return;1802  }1803}1804 1805static void diagnoseUnsatisfiedConceptIdExpr(Sema &S,1806                                             const ConceptReference *Concept,1807                                             SourceLocation Loc, bool First) {1808  if (Concept->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {1809    S.Diag(1810        Loc,1811        diag::1812            note_single_arg_concept_specialization_constraint_evaluated_to_false)1813        << (int)First1814        << Concept->getTemplateArgsAsWritten()->arguments()[0].getArgument()1815        << Concept->getNamedConcept();1816  } else {1817    S.Diag(Loc, diag::note_concept_specialization_constraint_evaluated_to_false)1818        << (int)First << Concept;1819  }1820}1821 1822static void diagnoseUnsatisfiedConstraintExpr(1823    Sema &S, const UnsatisfiedConstraintRecord &Record, SourceLocation Loc,1824    bool First, concepts::NestedRequirement *Req = nullptr);1825 1826static void DiagnoseUnsatisfiedConstraint(1827    Sema &S, ArrayRef<UnsatisfiedConstraintRecord> Records, SourceLocation Loc,1828    bool First = true, concepts::NestedRequirement *Req = nullptr) {1829  for (auto &Record : Records) {1830    diagnoseUnsatisfiedConstraintExpr(S, Record, Loc, First, Req);1831    Loc = {};1832    First = isa<const ConceptReference *>(Record);1833  }1834}1835 1836static void diagnoseUnsatisfiedRequirement(Sema &S,1837                                           concepts::NestedRequirement *Req,1838                                           bool First) {1839  DiagnoseUnsatisfiedConstraint(S, Req->getConstraintSatisfaction().records(),1840                                Req->hasInvalidConstraint()1841                                    ? SourceLocation()1842                                    : Req->getConstraintExpr()->getExprLoc(),1843                                First, Req);1844}1845 1846static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,1847                                                        const Expr *SubstExpr,1848                                                        bool First) {1849  SubstExpr = SubstExpr->IgnoreParenImpCasts();1850  if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) {1851    switch (BO->getOpcode()) {1852    // These two cases will in practice only be reached when using fold1853    // expressions with || and &&, since otherwise the || and && will have been1854    // broken down into atomic constraints during satisfaction checking.1855    case BO_LOr:1856      // Or evaluated to false - meaning both RHS and LHS evaluated to false.1857      diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);1858      diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),1859                                                  /*First=*/false);1860      return;1861    case BO_LAnd: {1862      bool LHSSatisfied =1863          BO->getLHS()->EvaluateKnownConstInt(S.Context).getBoolValue();1864      if (LHSSatisfied) {1865        // LHS is true, so RHS must be false.1866        diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First);1867        return;1868      }1869      // LHS is false1870      diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);1871 1872      // RHS might also be false1873      bool RHSSatisfied =1874          BO->getRHS()->EvaluateKnownConstInt(S.Context).getBoolValue();1875      if (!RHSSatisfied)1876        diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),1877                                                    /*First=*/false);1878      return;1879    }1880    case BO_GE:1881    case BO_LE:1882    case BO_GT:1883    case BO_LT:1884    case BO_EQ:1885    case BO_NE:1886      if (BO->getLHS()->getType()->isIntegerType() &&1887          BO->getRHS()->getType()->isIntegerType()) {1888        Expr::EvalResult SimplifiedLHS;1889        Expr::EvalResult SimplifiedRHS;1890        BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context,1891                                    Expr::SE_NoSideEffects,1892                                    /*InConstantContext=*/true);1893        BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context,1894                                    Expr::SE_NoSideEffects,1895                                    /*InConstantContext=*/true);1896        if (!SimplifiedLHS.Diag && !SimplifiedRHS.Diag) {1897          S.Diag(SubstExpr->getBeginLoc(),1898                 diag::note_atomic_constraint_evaluated_to_false_elaborated)1899              << (int)First << SubstExpr1900              << toString(SimplifiedLHS.Val.getInt(), 10)1901              << BinaryOperator::getOpcodeStr(BO->getOpcode())1902              << toString(SimplifiedRHS.Val.getInt(), 10);1903          return;1904        }1905      }1906      break;1907 1908    default:1909      break;1910    }1911  } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) {1912    // FIXME: RequiresExpr should store dependent diagnostics.1913    for (concepts::Requirement *Req : RE->getRequirements())1914      if (!Req->isDependent() && !Req->isSatisfied()) {1915        if (auto *E = dyn_cast<concepts::ExprRequirement>(Req))1916          diagnoseUnsatisfiedRequirement(S, E, First);1917        else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req))1918          diagnoseUnsatisfiedRequirement(S, T, First);1919        else1920          diagnoseUnsatisfiedRequirement(1921              S, cast<concepts::NestedRequirement>(Req), First);1922        break;1923      }1924    return;1925  } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) {1926    // Drill down concept ids treated as atomic constraints1927    S.DiagnoseUnsatisfiedConstraint(CSE, First);1928    return;1929  } else if (auto *TTE = dyn_cast<TypeTraitExpr>(SubstExpr);1930             TTE && TTE->getTrait() == clang::TypeTrait::BTT_IsDeducible) {1931    assert(TTE->getNumArgs() == 2);1932    S.Diag(SubstExpr->getSourceRange().getBegin(),1933           diag::note_is_deducible_constraint_evaluated_to_false)1934        << TTE->getArg(0)->getType() << TTE->getArg(1)->getType();1935    return;1936  }1937 1938  S.Diag(SubstExpr->getSourceRange().getBegin(),1939         diag::note_atomic_constraint_evaluated_to_false)1940      << (int)First << SubstExpr;1941  S.DiagnoseTypeTraitDetails(SubstExpr);1942}1943 1944static void diagnoseUnsatisfiedConstraintExpr(1945    Sema &S, const UnsatisfiedConstraintRecord &Record, SourceLocation Loc,1946    bool First, concepts::NestedRequirement *Req) {1947  if (auto *Diag =1948          Record1949              .template dyn_cast<const ConstraintSubstitutionDiagnostic *>()) {1950    if (Req)1951      S.Diag(Diag->first, diag::note_nested_requirement_substitution_error)1952          << (int)First << Req->getInvalidConstraintEntity() << Diag->second;1953    else1954      S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)1955          << Diag->second;1956    return;1957  }1958  if (const auto *Concept = dyn_cast<const ConceptReference *>(Record)) {1959    if (Loc.isInvalid())1960      Loc = Concept->getBeginLoc();1961    diagnoseUnsatisfiedConceptIdExpr(S, Concept, Loc, First);1962    return;1963  }1964  diagnoseWellFormedUnsatisfiedConstraintExpr(1965      S, cast<const class Expr *>(Record), First);1966}1967 1968void Sema::DiagnoseUnsatisfiedConstraint(1969    const ConstraintSatisfaction &Satisfaction, SourceLocation Loc,1970    bool First) {1971 1972  assert(!Satisfaction.IsSatisfied &&1973         "Attempted to diagnose a satisfied constraint");1974  ::DiagnoseUnsatisfiedConstraint(*this, Satisfaction.Details, Loc, First);1975}1976 1977void Sema::DiagnoseUnsatisfiedConstraint(1978    const ConceptSpecializationExpr *ConstraintExpr, bool First) {1979 1980  const ASTConstraintSatisfaction &Satisfaction =1981      ConstraintExpr->getSatisfaction();1982 1983  assert(!Satisfaction.IsSatisfied &&1984         "Attempted to diagnose a satisfied constraint");1985 1986  ::DiagnoseUnsatisfiedConstraint(*this, Satisfaction.records(),1987                                  ConstraintExpr->getBeginLoc(), First);1988}1989 1990namespace {1991 1992class SubstituteParameterMappings {1993  Sema &SemaRef;1994 1995  const MultiLevelTemplateArgumentList *MLTAL;1996  const ASTTemplateArgumentListInfo *ArgsAsWritten;1997 1998  bool InFoldExpr;1999 2000  SubstituteParameterMappings(Sema &SemaRef,2001                              const MultiLevelTemplateArgumentList *MLTAL,2002                              const ASTTemplateArgumentListInfo *ArgsAsWritten,2003                              bool InFoldExpr)2004      : SemaRef(SemaRef), MLTAL(MLTAL), ArgsAsWritten(ArgsAsWritten),2005        InFoldExpr(InFoldExpr) {}2006 2007  void buildParameterMapping(NormalizedConstraintWithParamMapping &N);2008 2009  bool substitute(NormalizedConstraintWithParamMapping &N);2010 2011  bool substitute(ConceptIdConstraint &CC);2012 2013public:2014  SubstituteParameterMappings(Sema &SemaRef, bool InFoldExpr = false)2015      : SemaRef(SemaRef), MLTAL(nullptr), ArgsAsWritten(nullptr),2016        InFoldExpr(InFoldExpr) {}2017 2018  bool substitute(NormalizedConstraint &N);2019};2020 2021void SubstituteParameterMappings::buildParameterMapping(2022    NormalizedConstraintWithParamMapping &N) {2023  TemplateParameterList *TemplateParams =2024      cast<TemplateDecl>(N.getConstraintDecl())->getTemplateParameters();2025 2026  llvm::SmallBitVector OccurringIndices(TemplateParams->size());2027  llvm::SmallBitVector OccurringIndicesForSubsumption(TemplateParams->size());2028 2029  if (N.getKind() == NormalizedConstraint::ConstraintKind::Atomic) {2030    SemaRef.MarkUsedTemplateParameters(2031        static_cast<AtomicConstraint &>(N).getConstraintExpr(),2032        /*OnlyDeduced=*/false,2033        /*Depth=*/0, OccurringIndices);2034 2035    SemaRef.MarkUsedTemplateParametersForSubsumptionParameterMapping(2036        static_cast<AtomicConstraint &>(N).getConstraintExpr(),2037        /*Depth=*/0, OccurringIndicesForSubsumption);2038 2039  } else if (N.getKind() ==2040             NormalizedConstraint::ConstraintKind::FoldExpanded) {2041    SemaRef.MarkUsedTemplateParameters(2042        static_cast<FoldExpandedConstraint &>(N).getPattern(),2043        /*OnlyDeduced=*/false,2044        /*Depth=*/0, OccurringIndices);2045  } else if (N.getKind() == NormalizedConstraint::ConstraintKind::ConceptId) {2046    auto *Args = static_cast<ConceptIdConstraint &>(N)2047                     .getConceptId()2048                     ->getTemplateArgsAsWritten();2049    if (Args)2050      SemaRef.MarkUsedTemplateParameters(Args->arguments(),2051                                         /*Depth=*/0, OccurringIndices);2052  }2053  unsigned Size = OccurringIndices.count();2054  // When the constraint is independent of any template parameters,2055  // we build an empty mapping so that we can distinguish these cases2056  // from cases where no mapping exists at all, e.g. when there are only atomic2057  // constraints.2058  TemplateArgumentLoc *TempArgs =2059      new (SemaRef.Context) TemplateArgumentLoc[Size];2060  llvm::SmallVector<NamedDecl *> UsedParams;2061  for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I) {2062    SourceLocation Loc = ArgsAsWritten->NumTemplateArgs > I2063                             ? ArgsAsWritten->arguments()[I].getLocation()2064                             : SourceLocation();2065    // FIXME: Investigate why we couldn't always preserve the SourceLoc. We2066    // can't assert Loc.isValid() now.2067    if (OccurringIndices[I]) {2068      NamedDecl *Param = TemplateParams->begin()[I];2069      new (&(TempArgs)[J]) TemplateArgumentLoc(2070          SemaRef.getIdentityTemplateArgumentLoc(Param, Loc));2071      UsedParams.push_back(Param);2072      J++;2073    }2074  }2075  auto *UsedList = TemplateParameterList::Create(2076      SemaRef.Context, TemplateParams->getTemplateLoc(),2077      TemplateParams->getLAngleLoc(), UsedParams,2078      /*RAngleLoc=*/SourceLocation(),2079      /*RequiresClause=*/nullptr);2080  N.updateParameterMapping(2081      std::move(OccurringIndices), std::move(OccurringIndicesForSubsumption),2082      MutableArrayRef<TemplateArgumentLoc>{TempArgs, Size}, UsedList);2083}2084 2085bool SubstituteParameterMappings::substitute(2086    NormalizedConstraintWithParamMapping &N) {2087  if (!N.hasParameterMapping())2088    buildParameterMapping(N);2089 2090  // If the parameter mapping is empty, there is nothing to substitute.2091  if (N.getParameterMapping().empty())2092    return false;2093 2094  SourceLocation InstLocBegin, InstLocEnd;2095  llvm::ArrayRef Arguments = ArgsAsWritten->arguments();2096  if (Arguments.empty()) {2097    InstLocBegin = ArgsAsWritten->getLAngleLoc();2098    InstLocEnd = ArgsAsWritten->getRAngleLoc();2099  } else {2100    auto SR = Arguments[0].getSourceRange();2101    InstLocBegin = SR.getBegin();2102    InstLocEnd = SR.getEnd();2103  }2104  Sema::NonSFINAEContext _(SemaRef);2105  Sema::InstantiatingTemplate Inst(2106      SemaRef, InstLocBegin,2107      Sema::InstantiatingTemplate::ParameterMappingSubstitution{},2108      const_cast<NamedDecl *>(N.getConstraintDecl()),2109      {InstLocBegin, InstLocEnd});2110  if (Inst.isInvalid())2111    return true;2112 2113  // TransformTemplateArguments is unable to preserve the source location of a2114  // pack. The SourceLocation is necessary for the instantiation location.2115  // FIXME: The BaseLoc will be used as the location of the pack expansion,2116  // which is wrong.2117  TemplateArgumentListInfo SubstArgs;2118  if (SemaRef.SubstTemplateArgumentsInParameterMapping(2119          N.getParameterMapping(), N.getBeginLoc(), *MLTAL, SubstArgs,2120          /*BuildPackExpansionTypes=*/!InFoldExpr))2121    return true;2122  Sema::CheckTemplateArgumentInfo CTAI;2123  auto *TD =2124      const_cast<TemplateDecl *>(cast<TemplateDecl>(N.getConstraintDecl()));2125  if (SemaRef.CheckTemplateArgumentList(TD, N.getUsedTemplateParamList(),2126                                        TD->getLocation(), SubstArgs,2127                                        /*DefaultArguments=*/{},2128                                        /*PartialTemplateArgs=*/false, CTAI))2129    return true;2130 2131  TemplateArgumentLoc *TempArgs =2132      new (SemaRef.Context) TemplateArgumentLoc[CTAI.SugaredConverted.size()];2133 2134  for (unsigned I = 0; I < CTAI.SugaredConverted.size(); ++I) {2135    SourceLocation Loc;2136    // If this is an empty pack, we have no corresponding SubstArgs.2137    if (I < SubstArgs.size())2138      Loc = SubstArgs.arguments()[I].getLocation();2139 2140    TempArgs[I] = SemaRef.getTrivialTemplateArgumentLoc(2141        CTAI.SugaredConverted[I], QualType(), Loc);2142  }2143 2144  MutableArrayRef<TemplateArgumentLoc> Mapping(TempArgs,2145                                               CTAI.SugaredConverted.size());2146  N.updateParameterMapping(N.mappingOccurenceList(),2147                           N.mappingOccurenceListForSubsumption(), Mapping,2148                           N.getUsedTemplateParamList());2149  return false;2150}2151 2152bool SubstituteParameterMappings::substitute(ConceptIdConstraint &CC) {2153  assert(CC.getConstraintDecl() && MLTAL && ArgsAsWritten);2154 2155  if (substitute(static_cast<NormalizedConstraintWithParamMapping &>(CC)))2156    return true;2157 2158  auto *CSE = CC.getConceptSpecializationExpr();2159  assert(CSE);2160  assert(!CC.getBeginLoc().isInvalid());2161 2162  SourceLocation InstLocBegin, InstLocEnd;2163  if (llvm::ArrayRef Arguments = ArgsAsWritten->arguments();2164      Arguments.empty()) {2165    InstLocBegin = ArgsAsWritten->getLAngleLoc();2166    InstLocEnd = ArgsAsWritten->getRAngleLoc();2167  } else {2168    auto SR = Arguments[0].getSourceRange();2169    InstLocBegin = SR.getBegin();2170    InstLocEnd = SR.getEnd();2171  }2172  Sema::NonSFINAEContext _(SemaRef);2173  // This is useful for name lookup across modules; see Sema::getLookupModules.2174  Sema::InstantiatingTemplate Inst(2175      SemaRef, InstLocBegin,2176      Sema::InstantiatingTemplate::ParameterMappingSubstitution{},2177      const_cast<NamedDecl *>(CC.getConstraintDecl()),2178      {InstLocBegin, InstLocEnd});2179  if (Inst.isInvalid())2180    return true;2181 2182  TemplateArgumentListInfo Out;2183  // TransformTemplateArguments is unable to preserve the source location of a2184  // pack. The SourceLocation is necessary for the instantiation location.2185  // FIXME: The BaseLoc will be used as the location of the pack expansion,2186  // which is wrong.2187  const ASTTemplateArgumentListInfo *ArgsAsWritten =2188      CSE->getTemplateArgsAsWritten();2189  if (SemaRef.SubstTemplateArgumentsInParameterMapping(2190          ArgsAsWritten->arguments(), CC.getBeginLoc(), *MLTAL, Out,2191          /*BuildPackExpansionTypes=*/!InFoldExpr))2192    return true;2193  Sema::CheckTemplateArgumentInfo CTAI;2194  if (SemaRef.CheckTemplateArgumentList(CSE->getNamedConcept(),2195                                        CSE->getConceptNameInfo().getLoc(), Out,2196                                        /*DefaultArgs=*/{},2197                                        /*PartialTemplateArgs=*/false, CTAI,2198                                        /*UpdateArgsWithConversions=*/false))2199    return true;2200  auto TemplateArgs = *MLTAL;2201  TemplateArgs.replaceOutermostTemplateArguments(CSE->getNamedConcept(),2202                                                 CTAI.SugaredConverted);2203  return SubstituteParameterMappings(SemaRef, &TemplateArgs, ArgsAsWritten,2204                                     InFoldExpr)2205      .substitute(CC.getNormalizedConstraint());2206}2207 2208bool SubstituteParameterMappings::substitute(NormalizedConstraint &N) {2209  switch (N.getKind()) {2210  case NormalizedConstraint::ConstraintKind::Atomic: {2211    if (!MLTAL) {2212      assert(!ArgsAsWritten);2213      return false;2214    }2215    return substitute(static_cast<NormalizedConstraintWithParamMapping &>(N));2216  }2217  case NormalizedConstraint::ConstraintKind::FoldExpanded: {2218    auto &FE = static_cast<FoldExpandedConstraint &>(N);2219    if (!MLTAL) {2220      llvm::SaveAndRestore _1(InFoldExpr, true);2221      assert(!ArgsAsWritten);2222      return substitute(FE.getNormalizedPattern());2223    }2224    Sema::ArgPackSubstIndexRAII _(SemaRef, std::nullopt);2225    substitute(static_cast<NormalizedConstraintWithParamMapping &>(FE));2226    return SubstituteParameterMappings(SemaRef, /*InFoldExpr=*/true)2227        .substitute(FE.getNormalizedPattern());2228  }2229  case NormalizedConstraint::ConstraintKind::ConceptId: {2230    auto &CC = static_cast<ConceptIdConstraint &>(N);2231    if (MLTAL) {2232      assert(ArgsAsWritten);2233      return substitute(CC);2234    }2235    assert(!ArgsAsWritten);2236    const ConceptSpecializationExpr *CSE = CC.getConceptSpecializationExpr();2237    ConceptDecl *Concept = CSE->getNamedConcept();2238    MultiLevelTemplateArgumentList MLTAL = SemaRef.getTemplateInstantiationArgs(2239        Concept, Concept->getLexicalDeclContext(),2240        /*Final=*/true, CSE->getTemplateArguments(),2241        /*RelativeToPrimary=*/true,2242        /*Pattern=*/nullptr,2243        /*ForConstraintInstantiation=*/true);2244 2245    return SubstituteParameterMappings(2246               SemaRef, &MLTAL, CSE->getTemplateArgsAsWritten(), InFoldExpr)2247        .substitute(CC.getNormalizedConstraint());2248  }2249  case NormalizedConstraint::ConstraintKind::Compound: {2250    auto &Compound = static_cast<CompoundConstraint &>(N);2251    if (substitute(Compound.getLHS()))2252      return true;2253    return substitute(Compound.getRHS());2254  }2255  }2256  llvm_unreachable("Unknown ConstraintKind enum");2257}2258 2259} // namespace2260 2261NormalizedConstraint *NormalizedConstraint::fromAssociatedConstraints(2262    Sema &S, const NamedDecl *D, ArrayRef<AssociatedConstraint> ACs) {2263  assert(ACs.size() != 0);2264  auto *Conjunction =2265      fromConstraintExpr(S, D, ACs[0].ConstraintExpr, ACs[0].ArgPackSubstIndex);2266  if (!Conjunction)2267    return nullptr;2268  for (unsigned I = 1; I < ACs.size(); ++I) {2269    auto *Next = fromConstraintExpr(S, D, ACs[I].ConstraintExpr,2270                                    ACs[I].ArgPackSubstIndex);2271    if (!Next)2272      return nullptr;2273    Conjunction = CompoundConstraint::CreateConjunction(S.getASTContext(),2274                                                        Conjunction, Next);2275  }2276  return Conjunction;2277}2278 2279NormalizedConstraint *NormalizedConstraint::fromConstraintExpr(2280    Sema &S, const NamedDecl *D, const Expr *E, UnsignedOrNone SubstIndex) {2281  assert(E != nullptr);2282 2283  // C++ [temp.constr.normal]p1.12284  // [...]2285  // - The normal form of an expression (E) is the normal form of E.2286  // [...]2287  E = E->IgnoreParenImpCasts();2288 2289  llvm::FoldingSetNodeID ID;2290  if (D && DiagRecursiveConstraintEval(S, ID, D, E)) {2291    return nullptr;2292  }2293  SatisfactionStackRAII StackRAII(S, D, ID);2294 2295  // C++2a [temp.param]p4:2296  //     [...] If T is not a pack, then E is E', otherwise E is (E' && ...).2297  // Fold expression is considered atomic constraints per current wording.2298  // See http://cplusplus.github.io/concepts-ts/ts-active.html#282299 2300  if (LogicalBinOp BO = E) {2301    auto *LHS = fromConstraintExpr(S, D, BO.getLHS(), SubstIndex);2302    if (!LHS)2303      return nullptr;2304    auto *RHS = fromConstraintExpr(S, D, BO.getRHS(), SubstIndex);2305    if (!RHS)2306      return nullptr;2307 2308    return CompoundConstraint::Create(2309        S.Context, LHS, BO.isAnd() ? CCK_Conjunction : CCK_Disjunction, RHS);2310  } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) {2311    NormalizedConstraint *SubNF;2312    {2313      Sema::NonSFINAEContext _(S);2314      Sema::InstantiatingTemplate Inst(2315          S, CSE->getExprLoc(),2316          Sema::InstantiatingTemplate::ConstraintNormalization{},2317          // FIXME: improve const-correctness of InstantiatingTemplate2318          const_cast<NamedDecl *>(D), CSE->getSourceRange());2319      if (Inst.isInvalid())2320        return nullptr;2321      // C++ [temp.constr.normal]p1.12322      // [...]2323      // The normal form of an id-expression of the form C<A1, A2, ..., AN>,2324      // where C names a concept, is the normal form of the2325      // constraint-expression of C, after substituting A1, A2, ..., AN for C’s2326      // respective template parameters in the parameter mappings in each atomic2327      // constraint. If any such substitution results in an invalid type or2328      // expression, the program is ill-formed; no diagnostic is required.2329      // [...]2330 2331      // Use canonical declarations to merge ConceptDecls across2332      // different modules.2333      ConceptDecl *CD = CSE->getNamedConcept()->getCanonicalDecl();2334 2335      ExprResult Res =2336          SubstituteConceptsInConstraintExpression(S, D, CSE, SubstIndex);2337      if (!Res.isUsable())2338        return nullptr;2339 2340      SubNF = NormalizedConstraint::fromAssociatedConstraints(2341          S, CD, AssociatedConstraint(Res.get(), SubstIndex));2342 2343      if (!SubNF)2344        return nullptr;2345    }2346 2347    return ConceptIdConstraint::Create(S.getASTContext(),2348                                       CSE->getConceptReference(), SubNF, D,2349                                       CSE, SubstIndex);2350 2351  } else if (auto *FE = dyn_cast<const CXXFoldExpr>(E);2352             FE && S.getLangOpts().CPlusPlus26 &&2353             (FE->getOperator() == BinaryOperatorKind::BO_LAnd ||2354              FE->getOperator() == BinaryOperatorKind::BO_LOr)) {2355 2356    // Normalize fold expressions in C++26.2357 2358    FoldExpandedConstraint::FoldOperatorKind Kind =2359        FE->getOperator() == BinaryOperatorKind::BO_LAnd2360            ? FoldExpandedConstraint::FoldOperatorKind::And2361            : FoldExpandedConstraint::FoldOperatorKind::Or;2362 2363    if (FE->getInit()) {2364      auto *LHS = fromConstraintExpr(S, D, FE->getLHS(), SubstIndex);2365      auto *RHS = fromConstraintExpr(S, D, FE->getRHS(), SubstIndex);2366      if (!LHS || !RHS)2367        return nullptr;2368 2369      if (FE->isRightFold())2370        LHS = FoldExpandedConstraint::Create(S.getASTContext(),2371                                             FE->getPattern(), D, Kind, LHS);2372      else2373        RHS = FoldExpandedConstraint::Create(S.getASTContext(),2374                                             FE->getPattern(), D, Kind, RHS);2375 2376      return CompoundConstraint::Create(2377          S.getASTContext(), LHS,2378          (FE->getOperator() == BinaryOperatorKind::BO_LAnd ? CCK_Conjunction2379                                                            : CCK_Disjunction),2380          RHS);2381    }2382    auto *Sub = fromConstraintExpr(S, D, FE->getPattern(), SubstIndex);2383    if (!Sub)2384      return nullptr;2385    return FoldExpandedConstraint::Create(S.getASTContext(), FE->getPattern(),2386                                          D, Kind, Sub);2387  }2388  return AtomicConstraint::Create(S.getASTContext(), E, D, SubstIndex);2389}2390 2391const NormalizedConstraint *Sema::getNormalizedAssociatedConstraints(2392    ConstrainedDeclOrNestedRequirement ConstrainedDeclOrNestedReq,2393    ArrayRef<AssociatedConstraint> AssociatedConstraints) {2394  if (!ConstrainedDeclOrNestedReq) {2395    auto *Normalized = NormalizedConstraint::fromAssociatedConstraints(2396        *this, nullptr, AssociatedConstraints);2397    if (!Normalized ||2398        SubstituteParameterMappings(*this).substitute(*Normalized))2399      return nullptr;2400 2401    return Normalized;2402  }2403 2404  // FIXME: ConstrainedDeclOrNestedReq is never a NestedRequirement!2405  const NamedDecl *ND =2406      ConstrainedDeclOrNestedReq.dyn_cast<const NamedDecl *>();2407  auto CacheEntry = NormalizationCache.find(ConstrainedDeclOrNestedReq);2408  if (CacheEntry == NormalizationCache.end()) {2409    auto *Normalized = NormalizedConstraint::fromAssociatedConstraints(2410        *this, ND, AssociatedConstraints);2411    if (!Normalized) {2412      NormalizationCache.try_emplace(ConstrainedDeclOrNestedReq, nullptr);2413      return nullptr;2414    }2415    // substitute() can invalidate iterators of NormalizationCache.2416    bool Failed = SubstituteParameterMappings(*this).substitute(*Normalized);2417    CacheEntry =2418        NormalizationCache.try_emplace(ConstrainedDeclOrNestedReq, Normalized)2419            .first;2420    if (Failed)2421      return nullptr;2422  }2423  return CacheEntry->second;2424}2425 2426bool FoldExpandedConstraint::AreCompatibleForSubsumption(2427    const FoldExpandedConstraint &A, const FoldExpandedConstraint &B) {2428 2429  // [C++26] [temp.constr.fold]2430  // Two fold expanded constraints are compatible for subsumption2431  // if their respective constraints both contain an equivalent unexpanded pack.2432 2433  llvm::SmallVector<UnexpandedParameterPack> APacks, BPacks;2434  Sema::collectUnexpandedParameterPacks(const_cast<Expr *>(A.getPattern()),2435                                        APacks);2436  Sema::collectUnexpandedParameterPacks(const_cast<Expr *>(B.getPattern()),2437                                        BPacks);2438 2439  for (const UnexpandedParameterPack &APack : APacks) {2440    auto ADI = getDepthAndIndex(APack);2441    if (!ADI)2442      continue;2443    auto It = llvm::find_if(BPacks, [&](const UnexpandedParameterPack &BPack) {2444      return getDepthAndIndex(BPack) == ADI;2445    });2446    if (It != BPacks.end())2447      return true;2448  }2449  return false;2450}2451 2452bool Sema::IsAtLeastAsConstrained(const NamedDecl *D1,2453                                  MutableArrayRef<AssociatedConstraint> AC1,2454                                  const NamedDecl *D2,2455                                  MutableArrayRef<AssociatedConstraint> AC2,2456                                  bool &Result) {2457#ifndef NDEBUG2458  if (const auto *FD1 = dyn_cast<FunctionDecl>(D1)) {2459    auto IsExpectedEntity = [](const FunctionDecl *FD) {2460      FunctionDecl::TemplatedKind Kind = FD->getTemplatedKind();2461      return Kind == FunctionDecl::TK_NonTemplate ||2462             Kind == FunctionDecl::TK_FunctionTemplate;2463    };2464    const auto *FD2 = dyn_cast<FunctionDecl>(D2);2465    assert(IsExpectedEntity(FD1) && FD2 && IsExpectedEntity(FD2) &&2466           "use non-instantiated function declaration for constraints partial "2467           "ordering");2468  }2469#endif2470 2471  if (AC1.empty()) {2472    Result = AC2.empty();2473    return false;2474  }2475  if (AC2.empty()) {2476    // TD1 has associated constraints and TD2 does not.2477    Result = true;2478    return false;2479  }2480 2481  std::pair<const NamedDecl *, const NamedDecl *> Key{D1, D2};2482  auto CacheEntry = SubsumptionCache.find(Key);2483  if (CacheEntry != SubsumptionCache.end()) {2484    Result = CacheEntry->second;2485    return false;2486  }2487 2488  unsigned Depth1 = CalculateTemplateDepthForConstraints(*this, D1, true);2489  unsigned Depth2 = CalculateTemplateDepthForConstraints(*this, D2, true);2490 2491  for (size_t I = 0; I != AC1.size() && I != AC2.size(); ++I) {2492    if (Depth2 > Depth1) {2493      AC1[I].ConstraintExpr =2494          AdjustConstraintDepth(*this, Depth2 - Depth1)2495              .TransformExpr(const_cast<Expr *>(AC1[I].ConstraintExpr))2496              .get();2497    } else if (Depth1 > Depth2) {2498      AC2[I].ConstraintExpr =2499          AdjustConstraintDepth(*this, Depth1 - Depth2)2500              .TransformExpr(const_cast<Expr *>(AC2[I].ConstraintExpr))2501              .get();2502    }2503  }2504 2505  SubsumptionChecker SC(*this);2506  std::optional<bool> Subsumes = SC.Subsumes(D1, AC1, D2, AC2);2507  if (!Subsumes) {2508    // Normalization failed2509    return true;2510  }2511  Result = *Subsumes;2512  SubsumptionCache.try_emplace(Key, *Subsumes);2513  return false;2514}2515 2516bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(2517    const NamedDecl *D1, ArrayRef<AssociatedConstraint> AC1,2518    const NamedDecl *D2, ArrayRef<AssociatedConstraint> AC2) {2519  if (isSFINAEContext())2520    // No need to work here because our notes would be discarded.2521    return false;2522 2523  if (AC1.empty() || AC2.empty())2524    return false;2525 2526  const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;2527  auto IdenticalExprEvaluator = [&](const AtomicConstraint &A,2528                                    const AtomicConstraint &B) {2529    if (!A.hasMatchingParameterMapping(Context, B))2530      return false;2531    const Expr *EA = A.getConstraintExpr(), *EB = B.getConstraintExpr();2532    if (EA == EB)2533      return true;2534 2535    // Not the same source level expression - are the expressions2536    // identical?2537    llvm::FoldingSetNodeID IDA, IDB;2538    EA->Profile(IDA, Context, /*Canonical=*/true);2539    EB->Profile(IDB, Context, /*Canonical=*/true);2540    if (IDA != IDB)2541      return false;2542 2543    AmbiguousAtomic1 = EA;2544    AmbiguousAtomic2 = EB;2545    return true;2546  };2547 2548  {2549    auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1);2550    if (!Normalized1)2551      return false;2552 2553    auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2);2554    if (!Normalized2)2555      return false;2556 2557    SubsumptionChecker SC(*this);2558 2559    bool Is1AtLeastAs2Normally = SC.Subsumes(Normalized1, Normalized2);2560    bool Is2AtLeastAs1Normally = SC.Subsumes(Normalized2, Normalized1);2561 2562    SubsumptionChecker SC2(*this, IdenticalExprEvaluator);2563    bool Is1AtLeastAs2 = SC2.Subsumes(Normalized1, Normalized2);2564    bool Is2AtLeastAs1 = SC2.Subsumes(Normalized2, Normalized1);2565 2566    if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&2567        Is2AtLeastAs1 == Is2AtLeastAs1Normally)2568      // Same result - no ambiguity was caused by identical atomic expressions.2569      return false;2570  }2571  // A different result! Some ambiguous atomic constraint(s) caused a difference2572  assert(AmbiguousAtomic1 && AmbiguousAtomic2);2573 2574  Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints)2575      << AmbiguousAtomic1->getSourceRange();2576  Diag(AmbiguousAtomic2->getBeginLoc(),2577       diag::note_ambiguous_atomic_constraints_similar_expression)2578      << AmbiguousAtomic2->getSourceRange();2579  return true;2580}2581 2582//2583//2584// ------------------------ Subsumption -----------------------------------2585//2586//2587SubsumptionChecker::SubsumptionChecker(Sema &SemaRef,2588                                       SubsumptionCallable Callable)2589    : SemaRef(SemaRef), Callable(Callable), NextID(1) {}2590 2591uint16_t SubsumptionChecker::getNewLiteralId() {2592  assert((unsigned(NextID) + 1 < std::numeric_limits<uint16_t>::max()) &&2593         "too many constraints!");2594  return NextID++;2595}2596 2597auto SubsumptionChecker::find(const AtomicConstraint *Ori) -> Literal {2598  auto &Elems = AtomicMap[Ori->getConstraintExpr()];2599  // C++ [temp.constr.order] p22600  //   - an atomic constraint A subsumes another atomic constraint B2601  //     if and only if the A and B are identical [...]2602  //2603  // C++ [temp.constr.atomic] p22604  //   Two atomic constraints are identical if they are formed from the2605  //   same expression and the targets of the parameter mappings are2606  //   equivalent according to the rules for expressions [...]2607 2608  // Because subsumption of atomic constraints is an identity2609  // relationship that does not require further analysis2610  // We cache the results such that if an atomic constraint literal2611  // subsumes another, their literal will be the same2612 2613  llvm::FoldingSetNodeID ID;2614  ID.AddBoolean(Ori->hasParameterMapping());2615  if (Ori->hasParameterMapping()) {2616    const auto &Mapping = Ori->getParameterMapping();2617    const NormalizedConstraint::OccurenceList &Indexes =2618        Ori->mappingOccurenceListForSubsumption();2619    for (auto [Idx, TAL] : llvm::enumerate(Mapping)) {2620      if (Indexes[Idx])2621        SemaRef.getASTContext()2622            .getCanonicalTemplateArgument(TAL.getArgument())2623            .Profile(ID, SemaRef.getASTContext());2624    }2625  }2626  auto It = Elems.find(ID);2627  if (It == Elems.end()) {2628    It = Elems2629             .insert({ID,2630                      MappedAtomicConstraint{2631                          Ori, {getNewLiteralId(), Literal::Atomic}}})2632             .first;2633    ReverseMap[It->second.ID.Value] = Ori;2634  }2635  return It->getSecond().ID;2636}2637 2638auto SubsumptionChecker::find(const FoldExpandedConstraint *Ori) -> Literal {2639  auto &Elems = FoldMap[Ori->getPattern()];2640 2641  FoldExpendedConstraintKey K;2642  K.Kind = Ori->getFoldOperator();2643 2644  auto It = llvm::find_if(Elems, [&K](const FoldExpendedConstraintKey &Other) {2645    return K.Kind == Other.Kind;2646  });2647  if (It == Elems.end()) {2648    K.ID = {getNewLiteralId(), Literal::FoldExpanded};2649    It = Elems.insert(Elems.end(), std::move(K));2650    ReverseMap[It->ID.Value] = Ori;2651  }2652  return It->ID;2653}2654 2655auto SubsumptionChecker::CNF(const NormalizedConstraint &C) -> CNFFormula {2656  return SubsumptionChecker::Normalize<CNFFormula>(C);2657}2658auto SubsumptionChecker::DNF(const NormalizedConstraint &C) -> DNFFormula {2659  return SubsumptionChecker::Normalize<DNFFormula>(C);2660}2661 2662///2663/// \brief SubsumptionChecker::Normalize2664///2665/// Normalize a formula to Conjunctive Normal Form or2666/// Disjunctive normal form.2667///2668/// Each Atomic (and Fold Expanded) constraint gets represented by2669/// a single id to reduce space.2670///2671/// To minimize risks of exponential blow up, if two atomic2672/// constraints subsumes each other (same constraint and mapping),2673/// they are represented by the same literal.2674///2675template <typename FormulaType>2676FormulaType SubsumptionChecker::Normalize(const NormalizedConstraint &NC) {2677  FormulaType Res;2678 2679  auto Add = [&, this](Clause C) {2680    // Sort each clause and remove duplicates for faster comparisons.2681    llvm::sort(C);2682    C.erase(llvm::unique(C), C.end());2683    AddUniqueClauseToFormula(Res, std::move(C));2684  };2685 2686  switch (NC.getKind()) {2687  case NormalizedConstraint::ConstraintKind::Atomic:2688    return {{find(&static_cast<const AtomicConstraint &>(NC))}};2689 2690  case NormalizedConstraint::ConstraintKind::FoldExpanded:2691    return {{find(&static_cast<const FoldExpandedConstraint &>(NC))}};2692 2693  case NormalizedConstraint::ConstraintKind::ConceptId:2694    return Normalize<FormulaType>(2695        static_cast<const ConceptIdConstraint &>(NC).getNormalizedConstraint());2696 2697  case NormalizedConstraint::ConstraintKind::Compound: {2698    const auto &Compound = static_cast<const CompoundConstraint &>(NC);2699    FormulaType Left, Right;2700    SemaRef.runWithSufficientStackSpace(SourceLocation(), [&] {2701      Left = Normalize<FormulaType>(Compound.getLHS());2702      Right = Normalize<FormulaType>(Compound.getRHS());2703    });2704 2705    if (Compound.getCompoundKind() == FormulaType::Kind) {2706      unsigned SizeLeft = Left.size();2707      Res = std::move(Left);2708      Res.reserve(SizeLeft + Right.size());2709      std::for_each(std::make_move_iterator(Right.begin()),2710                    std::make_move_iterator(Right.end()), Add);2711      return Res;2712    }2713 2714    Res.reserve(Left.size() * Right.size());2715    for (const auto &LTransform : Left) {2716      for (const auto &RTransform : Right) {2717        Clause Combined;2718        Combined.reserve(LTransform.size() + RTransform.size());2719        llvm::copy(LTransform, std::back_inserter(Combined));2720        llvm::copy(RTransform, std::back_inserter(Combined));2721        Add(std::move(Combined));2722      }2723    }2724    return Res;2725  }2726  }2727  llvm_unreachable("Unknown ConstraintKind enum");2728}2729 2730void SubsumptionChecker::AddUniqueClauseToFormula(Formula &F, Clause C) {2731  for (auto &Other : F) {2732    if (llvm::equal(C, Other))2733      return;2734  }2735  F.push_back(C);2736}2737 2738std::optional<bool> SubsumptionChecker::Subsumes(2739    const NamedDecl *DP, ArrayRef<AssociatedConstraint> P, const NamedDecl *DQ,2740    ArrayRef<AssociatedConstraint> Q) {2741  const NormalizedConstraint *PNormalized =2742      SemaRef.getNormalizedAssociatedConstraints(DP, P);2743  if (!PNormalized)2744    return std::nullopt;2745 2746  const NormalizedConstraint *QNormalized =2747      SemaRef.getNormalizedAssociatedConstraints(DQ, Q);2748  if (!QNormalized)2749    return std::nullopt;2750 2751  return Subsumes(PNormalized, QNormalized);2752}2753 2754bool SubsumptionChecker::Subsumes(const NormalizedConstraint *P,2755                                  const NormalizedConstraint *Q) {2756 2757  DNFFormula DNFP = DNF(*P);2758  CNFFormula CNFQ = CNF(*Q);2759  return Subsumes(DNFP, CNFQ);2760}2761 2762bool SubsumptionChecker::Subsumes(const DNFFormula &PDNF,2763                                  const CNFFormula &QCNF) {2764  for (const auto &Pi : PDNF) {2765    for (const auto &Qj : QCNF) {2766      // C++ [temp.constr.order] p22767      //   - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if2768      //     and only if there exists an atomic constraint Pia in Pi for which2769      //     there exists an atomic constraint, Qjb, in Qj such that Pia2770      //     subsumes Qjb.2771      if (!DNFSubsumes(Pi, Qj))2772        return false;2773    }2774  }2775  return true;2776}2777 2778bool SubsumptionChecker::DNFSubsumes(const Clause &P, const Clause &Q) {2779 2780  return llvm::any_of(P, [&](Literal LP) {2781    return llvm::any_of(Q, [this, LP](Literal LQ) { return Subsumes(LP, LQ); });2782  });2783}2784 2785bool SubsumptionChecker::Subsumes(const FoldExpandedConstraint *A,2786                                  const FoldExpandedConstraint *B) {2787  std::pair<const FoldExpandedConstraint *, const FoldExpandedConstraint *> Key{2788      A, B};2789 2790  auto It = FoldSubsumptionCache.find(Key);2791  if (It == FoldSubsumptionCache.end()) {2792    // C++ [temp.constr.order]2793    // a fold expanded constraint A subsumes another fold expanded2794    // constraint B if they are compatible for subsumption, have the same2795    // fold-operator, and the constraint of A subsumes that of B.2796    bool DoesSubsume =2797        A->getFoldOperator() == B->getFoldOperator() &&2798        FoldExpandedConstraint::AreCompatibleForSubsumption(*A, *B) &&2799        Subsumes(&A->getNormalizedPattern(), &B->getNormalizedPattern());2800    It = FoldSubsumptionCache.try_emplace(std::move(Key), DoesSubsume).first;2801  }2802  return It->second;2803}2804 2805bool SubsumptionChecker::Subsumes(Literal A, Literal B) {2806  if (A.Kind != B.Kind)2807    return false;2808  switch (A.Kind) {2809  case Literal::Atomic:2810    if (!Callable)2811      return A.Value == B.Value;2812    return Callable(2813        *static_cast<const AtomicConstraint *>(ReverseMap[A.Value]),2814        *static_cast<const AtomicConstraint *>(ReverseMap[B.Value]));2815  case Literal::FoldExpanded:2816    return Subsumes(2817        static_cast<const FoldExpandedConstraint *>(ReverseMap[A.Value]),2818        static_cast<const FoldExpandedConstraint *>(ReverseMap[B.Value]));2819  }2820  llvm_unreachable("unknown literal kind");2821}2822