[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

clang/include/clang/Sema/Sema.h

7235

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.

276–278

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?

276–278

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).

276–278

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!

276–278

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/docs/ReleaseNotes.rst

 - Fix a crash when trying to form a recovery expression on a call inside a
   constraint, which re-evaluated the same constraint.
   `Issue 53213 <https://github.com/llvm/llvm-project/issues/53213>`_
   `Issue 45736 <https://github.com/llvm/llvm-project/issues/45736>`_
 - Fix an issue when performing constraints partial ordering on non-template
   functions. `Issue 56154 <https://github.com/llvm/llvm-project/issues/56154>`_
 - Fix handling of unexpanded packs in template argument expressions.
   `Issue 58679 <https://github.com/llvm/llvm-project/issues/58679>`_
+- Fix a number of recursively-instantiated constraint issues, which would possibly
+  result in a stack overflow.
+  `Issue 44304 <https://github.com/llvm/llvm-project/issues/44304>`_
+  `Issue 50891 <https://github.com/llvm/llvm-project/issues/50891>`_
 
 Improvements to Clang's diagnostics
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 - Clang will now check compile-time determinable string literals as format strings.
   Fixes `Issue 55805: <https://github.com/llvm/llvm-project/issues/55805>`_.
 - ``-Wformat`` now recognizes ``%b`` for the ``printf``/``scanf`` family of
   functions and ``%B`` for the ``printf`` family of functions. Fixes
   `Issue 56885: <https://github.com/llvm/llvm-project/issues/56885>`_.

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 constraint '%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) const {
+    return llvm::find(SatisfactionStack, ID) != SatisfactionStack.end();
+  }
+
+  class SatisfactionStackRAII {
+    llvm::SmallVector<llvm::FoldingSetNodeID, 10> BackupSatisfactionStack;
+    Sema &SemaRef;
+
   public:
+    SatisfactionStackRAII(Sema &S) : SemaRef(S) {
+      SemaRef.SwapSatisfactionStack(BackupSatisfactionStack);
+    }
+
+    ~SatisfactionStackRAII() {
+      SemaRef.SwapSatisfactionStack(BackupSatisfactionStack);
+    }
+  };
+
+  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(); }
+};
+} // namespace
+
 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,
   Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();
   if (!Satisfaction.IsSatisfied)
     Satisfaction.Details.emplace_back(ConstraintExpr,
                                       SubstitutedAtomicExpr.get());
 
   return SubstitutedAtomicExpr;
 }
 
+static bool
+DiagRecursiveConstraintEval(Sema &S, llvm::FoldingSetNodeID &ID, const Expr *E,
+                            const MultiLevelTemplateArgumentList &MLTAL) {
+  E->Profile(ID, S.Context, /*Canonical=*/true);
+  for (const auto &List : MLTAL)
+    for (const auto &TemplateArg : List.Args)
+      TemplateArg.Profile(ID, S.Context);
+
+  // Note that we have to do this with our own collection, because there are
+  // times where a constraint-expression check can cause us to need to evaluate
+  // other constriants that are unrelated, such as when evaluating a recovery
+  // expression, or when trying to determine the constexpr-ness of special
+  // members. Otherwise we could just use the
+  // Sema::InstantiatingTemplate::isAlreadyBeingInstantiated function.
+  if (S.SatisfactionStackContains(ID)) {
+    S.Diag(E->getExprLoc(), diag::err_constraint_depends_on_self)
+        << const_cast<Expr *>(E) << E->getSourceRange();
+    return true;
+  }
+
+  return false;
+}
+
 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();
+
+          llvm::FoldingSetNodeID ID;
+          if (DiagRecursiveConstraintEval(S, ID, AtomicExpr, MLTAL)) {
+            Satisfaction.IsSatisfied = false;
+            Satisfaction.ContainsErrors = true;
+            return ExprEmpty();
+          }
+
+          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.
if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
     return false;
   }
 
   auto Satisfaction =
       std::make_unique<ConstraintSatisfaction>(Template, FlattenedArgs);
   if (::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
                                     ConvertedConstraints, TemplateArgsLists,
                                     TemplateIDRange, *Satisfaction)) {
+    OutSatisfaction = *Satisfaction;
     return true;
   }
 
   if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
     // The evaluation of this constraint resulted in us trying to re-evaluate it
     // recursively. This isn't really possible, except we try to form a
     // RecoveryExpr as a part of the evaluation.  If this is the case, just
     // return the 'cached' version (which will have the same result), and save

clang/lib/Sema/SemaDeclCXX.cpp

static bool defaultedSpecialMemberIsConstexpr(
   if (Ctor && ClassDecl->getNumVBases())
     return false;
 
   // C++1y [class.copy]p26:
   //   -- [the class] is a literal type, and
   if (!Ctor && !ClassDecl->isLiteral())
     return false;
 
+  // Suppress duplicate constraint checking here, in case a constraint check
+  // caused us to decide to do this.  Any truely recursive checks will get
+  // caught during these checks anyway.
+  Sema::SatisfactionStackRAII SSRAII{S};
+
   //   -- every constructor involved in initializing [...] base class
   //      sub-objects shall be a constexpr constructor;
   //   -- the assignment operator selected to copy/move each direct base
   //      class is a constexpr function, and
   for (const auto &B : ClassDecl->bases()) {
     const RecordType *BaseType = B.getType()->getAs<RecordType>();
-    if (!BaseType) continue;
-
+    if (!BaseType)
+      continue;
     CXXRecordDecl *BaseClassDecl = cast<CXXRecordDecl>(BaseType->getDecl());
     if (!specialMemberIsConstexpr(S, BaseClassDecl, CSM, 0, ConstArg,
                                   InheritedCtor, Inherited))
       return false;
   }
 
   //   -- every constructor involved in initializing non-static data members
   //      [...] shall be a constexpr constructor;

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 GH45736 {
-struct constrained;
-
-template<typename T>
-  struct type {
-  };
-template<typename T>
-  constexpr bool f(type<T>) {
-      return true;
-  }
-
-template<typename T>
-  concept matches = f(type<T>());
-
-
-struct constrained {
-    template<typename U> requires matches<U>
-        explicit constrained(U value) {
-            }
-};
-
-bool f(constrained const &) {
-    return true;
-}
-
-struct outer {
-    constrained state;
-};
-
-bool f(outer const & x) {
-    return f(x.state);
-}
-} // namespace GH45736

clang/test/SemaTemplate/concepts-recursive-inst.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 GH45736 {
+struct constrained;
+
+template<typename T>
+  struct type {
+  };
+template<typename T>
+  constexpr bool f(type<T>) {
+      return true;
+  }
+
+template<typename T>
+  concept matches = f(type<T>());
+
+
+struct constrained {
+    template<typename U> requires matches<U>
+        explicit constrained(U value) {
+            }
+};
+
+bool f(constrained const &) {
+    return true;
+}
+
+struct outer {
+    constrained state;
+};
+
+bool f(outer const & x) {
+    return f(x.state);
+}
+} // namespace GH45736
+
+namespace DirectRecursiveCheck {
+template<class T>
+concept NotInf = true;
+template<class T>
+concept Inf = requires(T& v){ // #INF_REQ
+  {begin(v)}; // #INF_BEGIN_EXPR
+};
+
+void begin(NotInf auto& v){ } // #NOTINF_BEGIN
+// This lookup should fail, since it results in a recursive check.
+// However, this is a 'hard failure'(not a SFINAE failure or constraints
+// violation), so it needs to cause the entire lookup to fail.
+void begin(Inf auto& v){ } // #INF_BEGIN
+
+struct my_range{
+} rng;
+
+void baz() {
+auto it = begin(rng); // #BEGIN_CALL
+// expected-error@#INF_BEGIN {{satisfaction of constraint 'Inf<Inf auto>' depends on itself}}
+// expected-note@#INF_BEGIN {{while substituting template arguments into constraint expression here}}
+// expected-note@#INF_BEGIN_EXPR {{while checking constraint satisfaction for template 'begin<DirectRecursiveCheck::my_range>' required here}}
+// expected-note@#INF_BEGIN_EXPR {{while substituting deduced template arguments into function template 'begin'}}
+// expected-note@#INF_BEGIN_EXPR {{in instantiation of requirement here}}
+// expected-note@#INF_REQ {{while substituting template arguments into constraint expression here}}
+// expected-note@#INF_BEGIN {{while checking the satisfaction of concept 'Inf<DirectRecursiveCheck::my_range>' requested here}}
+// expected-note@#INF_BEGIN {{while substituting template arguments into constraint expression here}}
+// expected-note@#BEGIN_CALL {{while checking constraint satisfaction for template 'begin<DirectRecursiveCheck::my_range>' required here}}
+// expected-note@#BEGIN_CALL {{in instantiation of function template specialization}}
+
+// Fallout of the failure is failed lookup, which is necessary to stop odd
+// cascading errors.
+// expected-error@#BEGIN_CALL {{no matching function for call to 'begin'}}
+// expected-note@#NOTINF_BEGIN {{candidate function}}
+// expected-note@#INF_BEGIN{{candidate template ignored: constraints not satisfied}}
+}
+} // namespace DirectRecursiveCheck
+
+namespace GH50891 {
+  template <typename T>
+  concept Numeric = requires(T a) { // #NUMERIC
+      foo(a); // #FOO_CALL
+    };
+
+  struct Deferred {
+    friend void foo(Deferred);
+    template <Numeric TO> operator TO(); // #OP_TO
+  };
+
+  static_assert(Numeric<Deferred>); // #STATIC_ASSERT
+  // expected-error@#OP_TO {{satisfaction of constraint 'Numeric<TO>' depends on itself}}
+  // expected-note@#OP_TO {{while substituting template arguments into constraint expression here}}
+  // FIXME: The following two refer to type-parameter-0-0, it would be nice to
+  // see if we could instead diagnose with the sugared name.
+  // expected-note@#FOO_CALL {{while checking constraint satisfaction for template}}
+  // expected-note@#FOO_CALL {{while substituting deduced template arguments into function template}}
+  // expected-note@#FOO_CALL {{in instantiation of requirement here}}
+  // expected-note@#NUMERIC {{while substituting template arguments into constraint expression here}}
+  // expected-note@#OP_TO {{skipping 2 contexts in backtrace}}
+  // expected-note@#FOO_CALL {{while checking constraint satisfaction for template}}
+  // expected-note@#FOO_CALL {{in instantiation of function template specialization}}
+  // expected-note@#FOO_CALL {{in instantiation of requirement here}}
+  // expected-note@#NUMERIC {{while substituting template arguments into constraint expression here}}
+  // expected-note@#STATIC_ASSERT{{while checking the satisfaction of concept 'Numeric<Deferred>' requested here}}
+
+  // Fallout of that failure is that deferred does not satisfy numeric,
+  // which is unfortunate, but about what we can accomplish here.
+  // expected-error@#STATIC_ASSERT {{static assertion failed}}
+  // expected-note@#STATIC_ASSERT{{because 'Deferred' does not satisfy 'Numeric'}}
+  // expected-note@#FOO_CALL {{because 'foo(a)' would be invalid}}
+} // namespace GH50891
+