[Bug c++/108393] New: circular concept false-positive

[Bug c++/108393] New: circular concept false-positive

[nikolasklauser at berlin dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108393

            Bug ID: 108393
           Summary: circular concept false-positive
           Product: gcc
           Version: 12.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: nikolasklauser at berlin dot de
  Target Milestone: ---

GCC errors on the reproducer below with

./equality_comparable.cpp: In substitution of 'template<class _Iter>  requires 
C<_Iter> constexpr bool operator==(unreachable_sentinel_t, const _Iter&) [with
_Iter = S<unreachable_sentinel_t>]':
./equality_comparable.cpp:6:41:   required by substitution of 'template<class
T>  requires requires(T __t, T __u) {__t == __u;} struct iterator_traits<T>
[with T = S<unreachable_sentinel_t>]'
./equality_comparable.cpp:11:33:   required from here
./equality_comparable.cpp:11:9:   required for the satisfaction of 'C<_Iter>'
[with _Iter = S<unreachable_sentinel_t>]
./equality_comparable.cpp:11:13:   in requirements  [with T =
S<unreachable_sentinel_t>]
./equality_comparable.cpp:11:13: error: satisfaction of atomic constraint
'requires{typename iterator_traits<T>::A;} [with T = T]' depends on itself
   11 | concept C = requires { typename iterator_traits<T>::A; };
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./equality_comparable.cpp: In substitution of 'template<class _Iter>  requires 
C<_Iter> constexpr bool operator==(unreachable_sentinel_t, const _Iter&) [with
_Iter = S<unreachable_sentinel_t>]':
./equality_comparable.cpp:6:41:   required by substitution of 'template<class
T>  requires requires(T __t, T __u) {__t == __u;} struct iterator_traits<T>
[with T = S<unreachable_sentinel_t>]'
./equality_comparable.cpp:11:33:   required from here
./equality_comparable.cpp:11:9:   required for the satisfaction of 'C<_Iter>'
[with _Iter = S<unreachable_sentinel_t>]
./equality_comparable.cpp:11:13:   in requirements  [with T =
S<unreachable_sentinel_t>]
./equality_comparable.cpp:11:13: error: satisfaction of atomic constraint
'requires{typename iterator_traits<T>::A;} [with T = T]' depends on itself

But AFAICT this code should compile just fine.
iterator_traits<unreachable_sentinel_t> should never get instantiated and I
don't see another way this would result in a self-reference.

reproducer (Godbolt: https://godbolt.org/z/cfP5fqcMc):

template<class>
struct iterator_traits
{};

template<class T>
  requires requires(T __t, T __u) { __t == __u; }
struct iterator_traits<T>
{};

template<class T>
concept C = requires { typename iterator_traits<T>::A; };

struct unreachable_sentinel_t
{
  template<C _Iter>
  friend constexpr bool operator==(unreachable_sentinel_t, const _Iter&)
noexcept;
};

template<class T>
struct S
{};

static_assert(!C<S<unreachable_sentinel_t>>);

[Bug c++/108393] circular concept false-positive

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108393

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The concept C checks whether S<unreachable_sentinel_t> satisfies the constraint
for the iterator_traits specialization. That performs ADL for operator== with
S<unreachable_sentinel_t> and unreachable_sentinel_t as associated classes.
That finds the hidden friend function, and then performs overload resolution to
see if it's viable for S<unreachable_sentinel_t> arguments. Overload resolution
checks whether the arguments satisfy the constraints, which means checking if C
is satisfied, which creates the cycle.

The question is whether GCC is correct to check constraint satisfaction for one
argument when the other argument cannot be converted to unreachable_sentinel_t.

[Bug c++/108393] circular concept false-positive

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108393

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Specifically, ADL for __t == __u finds this function:

  template<C _Iter>
  friend constexpr bool operator==(unreachable_sentinel_t, const _Iter&)
noexcept;

making it an overload resolution candidate. It's not viable, because __t and
__u (which are the same type) cannot be converted to unreachable_sentinel_t.
But if the other parameter is checked first, then that means checking whether
S<unreachable_sentinel_t> satisfies C, because of the constraint C _Iter.

[over.match.viable] says:

- First, to be a viable function, a candidate function shall have enough
parameters to agree in number with the arguments in the list.

This condition is met.

- Second, for a function to be viable, if it has associated constraints
([temp.constr.decl]), those constraints shall be satisfied

The associated constraints are that _Iter satisfies C. This is where the cycle
happens.

- Third, for F to be a viable function, there shall exist for each argument an
implicit conversion sequence that converts that argument to the corresponding
parameter of F.

This is when the function would be discarded from the candidate set, because
S<unreachable_sentinel_t> cannot be converted to unreachable_sentinel_t. But
it's too late, we already blew up at the second step.

[Bug c++/108393] circular concept false-positive

[ppalka at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108393

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=99599
                 CC|                            |ppalka at gcc dot gnu.org

--- Comment #3 from Patrick Palka <ppalka at gcc dot gnu.org> ---
IIUC this is a consequence of CWG2369, which made us check check constraints
before checking non-dependent conversions, and which AFAIK only GCC implements.

It can be worked around by encoding the conversion to unreachable_sentinel_t as
an additional constraint guarding the real constraint:

  template<std::convertible_to<unreachable_sentinel_t> T, C _Iter>
  friend constexpr bool operator==(T, const _Iter&) noexcept;

See also PR99599

[Bug c++/108393] circular concept false-positive

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108393

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fsb4000 at yandex dot ru

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 108570 has been marked as a duplicate of this bug. ***

[Bug c++/108393] circular concept false-positive

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108393

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hewillk at gmail dot com

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 106810 has been marked as a duplicate of this bug. ***

[Bug c++/108393] circular concept false-positive

[ppalka at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108393

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|https://gcc.gnu.org/bugzill |
                   |a/show_bug.cgi?id=99599     |
         Resolution|---                         |DUPLICATE
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #6 from Patrick Palka <ppalka at gcc dot gnu.org> ---
GCC trunk after r14-3809 should now avoid this kind of constraint recursion
involving an unreachable_sentinel_t parameter.

*** This bug has been marked as a duplicate of bug 99599 ***