Concept causes infinite loops at compile time (-Wstack-exhausted)

[marehr]

Bugzilla Link	44959
Version	trunk
OS	Linux
CC	@zygoloid

Extended Description

The following code should compile:

#include <type_traits>

template <typename T>
concept semialphabet = requires(T const &t, T const &u) {t == u;};

template <typename>
concept always_false = false;

template <typename derived_type, int size> struct alphabet_base {
  friend bool operator==(derived_type, derived_type) { return false; };
};

template <int size>
struct semialphabet_any : alphabet_base<semialphabet_any<size>, size> {
  template <typename other_alph_t, typename = std::enable_if_t<always_false<other_alph_t> && semialphabet<other_alph_t>>>
  operator other_alph_t();
};

template <typename derived_type, int size>
struct aminoacid_base : public alphabet_base<derived_type, size> {
  template <typename other_aa_type, typename = std::enable_if_t<always_false<other_aa_type> && semialphabet<other_aa_type>>>
  aminoacid_base(other_aa_type);
};

struct aa10li : public aminoacid_base<aa10li, 10> {
  using base_t = aminoacid_base;
  using base_t::base_t;
};

semialphabet_any<10> letter0;

static_assert(!std::is_convertible_v<semialphabet_any<10>, aa10li>);

I would expect that the expression always_false<other_aa_type> && semialphabet<other_aa_type> evaluates from left to right and sees that this expression is the same as false && semialphabet<other_aa_type> and thus does not evaluate semialphabet<other_aa_type>. If I define semialphabet via SFINAE instead of concepts short-circuiting works.

https://godbolt.org/z/KBgLpi

Error message:

<source>:14:8: warning: stack nearly exhausted; compilation time may suffer, and crashes due to stack overflow are likely [-Wstack-exhausted]

struct semialphabet_any : alphabet_base<semialphabet_any<size>, size> {
       ^
<source>:4:58: note: in instantiation of requirement here
concept semialphabet = requires(T const &t, T const &u) {t == u;};
                                                         ^~~~~~
<source>:4:24: note: while substituting template arguments into constraint expression here
concept semialphabet = requires(T const &t, T const &u) {t == u;};
                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<source>:15:94: note: while checking the satisfaction of concept 'semialphabet<semialphabet_any<10> >' requested here
  template <typename other_alph_t, typename = std::enable_if_t<always_false<other_alph_t> && semialphabet<other_alph_t>>>
                                                                                             ^~~~~~~~~~~~~~~~~~~~~~~~~~
<source>:16:3: note: in instantiation of default argument for 'operator type-parameter-0-0<semialphabet_any<10> >' required here
  operator other_alph_t();
  ^~~~~~~~~~~~~~~~~~~~~~~
<source>:4:58: note: while substituting deduced template arguments into function template 'operator type-parameter-0-0' [with other_alph_t = semialphabet_any<10>, $1 = (no value)]
concept semialphabet = requires(T const &t, T const &u) {t == u;};
                                                         ^
<source>:4:58: note: (skipping 1516 contexts in backtrace; use -ftemplate-backtrace-limit=0 to see all)
/opt/compiler-explorer/gcc-9.2.0/lib/gcc/x86_64-linux-gnu/9.2.0/../../../../include/c++/9.2.0/type_traits:1322:2: note: in instantiation of default argument for '__test<semialphabet_any<10>, aa10li>' required here
        __test(int);
        ^~~~~~~~~~~
/opt/compiler-explorer/gcc-9.2.0/lib/gcc/x86_64-linux-gnu/9.2.0/../../../../include/c++/9.2.0/type_traits:1329:24: note: while substituting deduced template arguments into function template '__test' [with _From1 = semialphabet_any<10>, _To1 = aa10li, $2 = (no value)]
      typedef decltype(__test<_From, _To>(0)) type;
                       ^
/opt/compiler-explorer/gcc-9.2.0/lib/gcc/x86_64-linux-gnu/9.2.0/../../../../include/c++/9.2.0/type_traits:1336:14: note: in instantiation of template class 'std::__is_convertible_helper<semialphabet_any<10>, aa10li, false>' requested here
    : public __is_convertible_helper<_From, _To>::type
             ^
/opt/compiler-explorer/gcc-9.2.0/lib/gcc/x86_64-linux-gnu/9.2.0/../../../../include/c++/9.2.0/type_traits:2964:44: note: in instantiation of template class 'std::is_convertible<semialphabet_any<10>, aa10li>' requested here
  inline constexpr bool is_convertible_v = is_convertible<_From, _To>::value;
                                           ^
<source>:32:21: note: in instantiation of variable template specialization 'std::is_convertible_v<semialphabet_any<10>, aa10li>' requested here
static_assert(!std::is_convertible_v<semialphabet_any<10>, aa10li>);
                    ^
Compiler returned: 255

[zygoloid]

The always_false<...> && here does not save you from any further substitution. The entire expression is substituted before any evaluation happens, so you always get the substitution cycle here.

I would guess what the other compilers are doing is detecting the cycle in substitution and triggering substitution failure as a result. (I don't believe there is any language rule that requires -- or even permits -- that behavior, but such is life.)

The non-concepts formulation only works because the second time round the cycle, while in the middle of instantiating is_semialphabet::value, we try to look at is_semialphabet::value again and see it doesn't (yet) exist, and bail out rather than trying to instantiate it again.

This works if you use a requires clause instead of an enable_if (https://godbolt.org/z/TMcFAd) because (the top-level &&s and ||s in a) requires clauses get the interleaved substitution and evaluation you were expecting here.

Leaving this open: we should decide whether we want to detect a self-recursive concept satisfaction check, and if so, what we want to do about it. (Issuing a non-SFINAE error seems reasonable, and better than an infinite recursion.)

[erichkeane]

Note, closing in on fixing this here: https://reviews.llvm.org/D136975

[llvmbot]

@llvm/issue-subscribers-clang-frontend