[Concepts] Correctly handle failure when checking concepts recursively

[erichkeane]

Summary

Based on discussion on the core reflector, it was made clear that a
concept that depends on itself should be a hard error, not a constraint
failure. This patch implements a stack of constraint-checks-in-progress
to make sure we quit, rather than hitting stack-exhaustion.

Note that we DO need to be careful to make sure we still check
constraints properly that are caused by a previous constraint, but not
derived from (such as when a check causes us to check special member
function generation), so we cannot use the existing logic to see if this
is being instantiated.

This fixes https://github.com/llvm/llvm-project/issues/44304 and
https://github.com/llvm/llvm-project/issues/50891

[erichkeane]

Add release notes.

Please feel free to review this!

[erichkeane]

Add DELETE_ME so that the libcxx tests run. Due to the nature of this patch, it is possible that I will have missed a few cases where we should be 're-starting' the substitution stack checking.

[luken-google]

Looks good to me!

[erichkeane]

ACTUALLY add the libcxx testing, also rebase so hopefully it applies cleanly.

[erichkeane]

fix clang format

[aaron.ballman]

clang/docs/ReleaseNotes.rst

272 ↗

(On Diff #472268)

clang/include/clang/Sema/Sema.h

7233

clang/lib/Sema/SemaConcept.cpp

150

Er, it'd be nice for this not to shadow the name of the class from Sema, that's pretty confusing.

278–280

What are the chances that this O(N^2) operation is going to come back to bite us in terms of compile time performance?

[erichkeane]

clang/lib/Sema/SemaConcept.cpp

150

What do you mean? What name does it shadow?

278–280

I'd hope not too much? This is just going through the whole list of template arguments on this expression, so I think that makes this O(M*N), where M and N are limited by the number of template arguments we allow.

[erichkeane]

Fix issues aaron came up with.

[aaron.ballman]

clang/lib/Sema/SemaConcept.cpp

150

Sema.h:7239 (code you added in this patch).

278–280

Okay, I was mostly worried about STL headers where there may be a long list of template arguments and not a lot of recursion to worry about. We don't really memoize whether we've already determined a given constraint is not recursive so that we don't have to repeat this work over and over again, but if performance is a concern in practice, we could explore that as an option.

[erichkeane]

clang/lib/Sema/SemaConcept.cpp

150

Yikes! Thanks, good catch!

278–280

I'm somewhat worried there too, but I'd hope that an M*N < ~1000 would be a small impact. We actually DO memoize this, at least on a per instantiation basis, as we cache constraint evaluations.

[erichkeane]

A quick 'quality of life' improvement, otherwise same as before. Should be ready for commit?

[ychen]

Thanks for the patch. It looks good to me.

About

Note that we DO need to be careful to make sure we still check
constraints properly that are caused by a previous constraint, but not
derived from (such as when a check causes us to check special member
function generation), so we cannot use the existing logic to see if this
is being instantiated.

For the derived from case, I think we also end up getting the infinite recursion? Why do we disable the check for the derived from case?

[erichkeane]

In D136975#3899703, @ychen wrote:

Thanks for the patch. It looks good to me.

About

Note that we DO need to be careful to make sure we still check
constraints properly that are caused by a previous constraint, but not
derived from (such as when a check causes us to check special member
function generation), so we cannot use the existing logic to see if this
is being instantiated.

For the derived from case, I think we also end up getting the infinite recursion? Why do we disable the check for the derived from case?

Can you clarify what you mean? I'm not sure which test case you're speaking of.

[ychen]

In D136975#3899717, @erichkeane wrote:

In D136975#3899703, @ychen wrote:

Thanks for the patch. It looks good to me.

About

Note that we DO need to be careful to make sure we still check
constraints properly that are caused by a previous constraint, but not
derived from (such as when a check causes us to check special member
function generation), so we cannot use the existing logic to see if this
is being instantiated.

For the derived from case, I think we also end up getting the infinite recursion? Why do we disable the check for the derived from case?

Can you clarify what you mean? I'm not sure which test case you're speaking of.

I was confused about the reason for resetting SatisfactionStack. Never mind :-). I think I understand it now.

[ychen]

LGTM

clang/include/clang/Basic/DiagnosticSemaKinds.td

def note_function_template_spec_matched : Note<
     "function template %q0 matches specialization %1">;
 def err_function_template_partial_spec : Error<
     "function template partial specialization is not allowed">;
 
 // C++ Template Instantiation
 def err_template_recursion_depth_exceeded : Error<
   "recursive template instantiation exceeded maximum depth of %0">,
   DefaultFatal, NoSFINAE;
+def err_constraint_depends_on_self : Error<
+  "satisfaction of constraints on %0 depends on itself">, NoSFINAE;
 def note_template_recursion_depth : Note<
   "use -ftemplate-depth=N to increase recursive template instantiation depth">;
 
 def err_template_instantiate_within_definition : Error<
   "%select{implicit|explicit}0 instantiation of template %1 within its"
   " own definition">;
 def err_template_instantiate_undefined : Error<
   "%select{implicit|explicit}0 instantiation of undefined template %1">;

clang/include/clang/Sema/Sema.h

private:
   /// Used during constraint checking, sets up the constraint template argument
   /// lists, and calls SetupConstraintScope to set up the
   /// LocalInstantiationScope to have the proper set of ParVarDecls configured.
   llvm::Optional<MultiLevelTemplateArgumentList>
   SetupConstraintCheckingTemplateArgumentsAndScope(
       FunctionDecl *FD, llvm::Optional<ArrayRef<TemplateArgument>> TemplateArgs,
       LocalInstantiationScope &Scope);
 
+private:
+  // The current stack of constraint satisfactions, so we can exit-early.
+  llvm::SmallVector<llvm::FoldingSetNodeID, 10>
+      SatisfactionStack;
 public:
+  void PushSatisfactionStackEntry(const llvm::FoldingSetNodeID &ID) {
+    SatisfactionStack.push_back(ID);
+  }
+
+  void PopSatisfactionStackEntry() {
+    SatisfactionStack.pop_back();
+  }
+
+  bool SatisfactionStackContains(const llvm::FoldingSetNodeID &ID) {
+   return llvm::find(SatisfactionStack, ID) != SatisfactionStack.end();
+  }
+
+  void
+  SwapSatisfactionStack(llvm::SmallVectorImpl<llvm::FoldingSetNodeID> &NewSS) {
+    SatisfactionStack.swap(NewSS);
+  }
+
   const NormalizedConstraint *
   getNormalizedAssociatedConstraints(
       NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints);
 
   /// \brief Check whether the given declaration's associated constraints are
   /// at least as constrained than another declaration's according to the
   /// partial ordering of constraints.
   ///

clang/lib/Sema/SemaConcept.cpp

if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) {
     return false;
   }
 
   if (PossibleNonPrimary)
       *PossibleNonPrimary = false;
   return true;
 }
 
+namespace {
+  struct SatisfactionStackRAII {
+    Sema &SemaRef;
+    SatisfactionStackRAII(Sema &SemaRef, llvm::FoldingSetNodeID FSNID) :SemaRef(SemaRef) {
+      SemaRef.PushSatisfactionStackEntry(FSNID);
+    }
+    ~SatisfactionStackRAII() {
+      SemaRef.PopSatisfactionStackEntry();
+    }
+  };
+}
+
 template <typename AtomicEvaluator>
 static ExprResult
 calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
                                 ConstraintSatisfaction &Satisfaction,
                                 AtomicEvaluator &&Evaluator) {
   ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
 
   if (LogicalBinOp BO = ConstraintExpr) {
calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
 
   return SubstitutedAtomicExpr;
 }
 
 static ExprResult calculateConstraintSatisfaction(
     Sema &S, const NamedDecl *Template, SourceLocation TemplateNameLoc,
     const MultiLevelTemplateArgumentList &MLTAL, const Expr *ConstraintExpr,
     ConstraintSatisfaction &Satisfaction) {
   return calculateConstraintSatisfaction(
       S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) {
         EnterExpressionEvaluationContext ConstantEvaluated(
             S, Sema::ExpressionEvaluationContext::ConstantEvaluated,
             Sema::ReuseLambdaContextDecl);
 
         // Atomic constraint - substitute arguments and check satisfaction.
         ExprResult SubstitutedExpression;
         {
           TemplateDeductionInfo Info(TemplateNameLoc);
           Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(),
               Sema::InstantiatingTemplate::ConstraintSubstitution{},
               const_cast<NamedDecl *>(Template), Info,
               AtomicExpr->getSourceRange());
           if (Inst.isInvalid())
             return ExprError();
+
+// TODO: ERICH: Cleanup
+llvm::FoldingSetNodeID ID;
+AtomicExpr->Profile(ID, S.Context, /*Canonical=*/true);
+for (const auto &List : MLTAL)
+  for (const auto &TemplateArg : List.Args)
+    TemplateArg.Profile(ID, S.Context);
+
+if (S.SatisfactionStackContains(ID)) {
+  // TODO: ERICH: Figure out how to better print the constraint?
+  // TODO: ERICH: make sure we add tests from 
+  // : recurse_crash.cpp
+  // : https://github.com/llvm/llvm-project/issues/44304
+  // : https://github.com/llvm/llvm-project/issues/50891
+  // : https://reviews.llvm.org/D133052
+  S.Diag(AtomicExpr->getExprLoc(), diag::err_constraint_depends_on_self)
+      << "The Bad thing" << AtomicExpr->getSourceRange();
+  Satisfaction.IsSatisfied = false;
+  Satisfaction.ContainsErrors = true;
+  return ExprError();
+}
+
+SatisfactionStackRAII StackRAII(S, ID);
+
+
           // We do not want error diagnostics escaping here.
           Sema::SFINAETrap Trap(S);
           SubstitutedExpression =
               S.SubstConstraintExpr(const_cast<Expr *>(AtomicExpr), MLTAL);
           // Substitution might have stripped off a contextual conversion to
           // bool if this is the operand of an '&&' or '||'. For example, we
           // might lose an lvalue-to-rvalue conversion here. If so, put it back
           // before we try to evaluate.

clang/lib/Sema/SemaOverload.cpp

DiagnoseTwoPhaseOperatorLookup(Sema &SemaRef, OverloadedOperatorKind Op,
   return DiagnoseTwoPhaseLookup(SemaRef, OpLoc, CXXScopeSpec(), R,
                                 OverloadCandidateSet::CSK_Operator,
                                 /*ExplicitTemplateArgs=*/nullptr, Args);
 }
 
 namespace {
 class BuildRecoveryCallExprRAII {
   Sema &SemaRef;
+  llvm::SmallVector<llvm::FoldingSetNodeID, 10> SatisfactionStack;
 public:
   BuildRecoveryCallExprRAII(Sema &S) : SemaRef(S) {
     assert(SemaRef.IsBuildingRecoveryCallExpr == false);
     SemaRef.IsBuildingRecoveryCallExpr = true;
+    // Ensure we clear the satisfaction stack here, so that we don't fail
+    // incorrectly for recursive lookups.
+    SemaRef.SwapSatisfactionStack(SatisfactionStack);
   }
 
   ~BuildRecoveryCallExprRAII() {
     SemaRef.IsBuildingRecoveryCallExpr = false;
+    SemaRef.SwapSatisfactionStack(SatisfactionStack);
   }
 };
 
 }
 
 /// Attempts to recover from a call where no functions were found.
 ///
 /// This function will do one of three things:

clang/test/SemaTemplate/concepts-GH53213.cpp

 // RUN: %clang_cc1 -std=c++20 -verify %s
-namespace GH53213 {
-template<typename T>
-concept c = requires(T t) { f(t); }; // #CDEF
-
-auto f(c auto); // #FDEF
-
-void g() {
-  f(0);
-  // expected-error@-1{{no matching function for call to 'f'}}
-  // expected-note@#FDEF{{constraints not satisfied}}
-  // expected-note@#FDEF{{because 'int' does not satisfy 'c'}}
-  // expected-note@#CDEF{{because 'f(t)' would be invalid: no matching function for call to 'f'}}
-}
-} // namespace GH53213 
+//namespace GH53213 {
+//template<typename T>
+//concept c = requires(T t) { f(t); }; // #CDEF
+//
+//auto f(c auto); // #FDEF
+//
+//void g() {
+//  f(0);
+//  // expected-error@-1{{no matching function for call to 'f'}}
+//  // expected-note@#FDEF{{constraints not satisfied}}
+//  // expected-note@#FDEF{{because 'int' does not satisfy 'c'}}
+//  // expected-note@#CDEF{{because 'f(t)' would be invalid: no matching function for call to 'f'}}
+//}
+//} // namespace GH53213 
 
 namespace GH45736 {
 struct constrained;
 
 template<typename T>
   struct type {
   };
 template<typename T>