[Bug libstdc++/100249] New: missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[Bug libstdc++/100249] New: missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[hewillk at gmail dot com]

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

            Bug ID: 100249
           Summary: missing forwarding std::__invoke result in
                    ranges::is_permutation and ranges::clamp
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hewillk at gmail dot com
  Target Milestone: ---

Hey, in ranges::is_permutation in ranges_algo.h#L808:

    auto __proj_scan = std::__invoke(__proj1, *__scan);
    auto __comp_scan = [&] <typename _Tp> (_Tp&& __arg) {
      return std::__invoke(__pred, __proj_scan,
                           std::forward<_Tp>(__arg));
    };

the __proj_scan seems to forget to use auto&& to receive the std::__ invoke
call, which will cause compile failure if the return type is non-copyable:
https://godbolt.org/z/WaKc7bWM4

also, we should perfect forward the type of __proj_scan to the next
std::__invoke call, and ranges::clamp in ranges_algo.h#L3232 has the same
issue:

    auto&& __proj_val = std::__invoke(__proj, __val);
    if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo)))
      return __lo;

when the type of __proj_val is an rvalue reference, we need to convert it to
rvalue for the next std::__invoke call: https://godbolt.org/z/1G7aqxs3c.

So I think it should be relatively safe to inline all std::__invoke calls.

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[hewillk at gmail dot com]

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

--- Comment #1 from 康桓瑋 <hewillk at gmail dot com> ---
(In reply to 康桓瑋 from comment #0)

> when the type of __proj_val is an rvalue reference, we need to convert it to
> rvalue for the next std::__invoke call: https://godbolt.org/z/1G7aqxs3c.

More simple case: https://godbolt.org/z/Y11c71cq6

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[ppalka at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-04-26
                 CC|                            |ppalka at gcc dot gnu.org

--- Comment #2 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Confirmed.

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[ppalka at gcc dot gnu.org]

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

--- Comment #3 from Patrick Palka <ppalka at gcc dot gnu.org> ---
(In reply to 康桓瑋 from comment #0)
> So I think it should be relatively safe to inline all std::__invoke calls.

I'm not sure we can inline these std::__invoke calls actually, because the
standard has strict limits about the number of times these algorithms can apply
the projection function, see https://eel.is/c++draft/alg.is.permutation#7 and
https://eel.is/c++draft/alg.clamp#5.

So if we e.g. inlined __proj_val in ranges::clamp, we'd be performing up to 4
projection applications instead of 3.

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[ppalka at gcc dot gnu.org]

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

--- Comment #4 from Patrick Palka <ppalka at gcc dot gnu.org> ---
(In reply to 康桓瑋 from comment #0)
> when the type of __proj_val is an rvalue reference, we need to convert it to
> rvalue for the next std::__invoke call: https://godbolt.org/z/1G7aqxs3c.

So it seems the projection application limit of 3 makes it impossible for
ranges::clamp to perfectly support the case where the projection returns an
rvalue reference.

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[hewillk at gmail dot com]

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

--- Comment #5 from 康桓瑋 <hewillk at gmail dot com> ---
(In reply to Patrick Palka from comment #4)
> (In reply to 康桓瑋 from comment #0)
> > when the type of __proj_val is an rvalue reference, we need to convert it to
> > rvalue for the next std::__invoke call: https://godbolt.org/z/1G7aqxs3c.
> 
> So it seems the projection application limit of 3 makes it impossible for
> ranges::clamp to perfectly support the case where the projection returns an
> rvalue reference.

Maybe this can help:

  auto&& __proj_val = std::__invoke(__proj, __val);
      if (std::__invoke(__comp, std::forward<decltype(__proj_val)>(__proj_val),
std::__invoke(__proj, __lo)))
        return __lo;

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[ppalka at gcc dot gnu.org]

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

--- Comment #6 from Patrick Palka <ppalka at gcc dot gnu.org> ---
(In reply to 康桓瑋 from comment #5)
> (In reply to Patrick Palka from comment #4)
> > (In reply to 康桓瑋 from comment #0)
> > > when the type of __proj_val is an rvalue reference, we need to convert it to
> > > rvalue for the next std::__invoke call: https://godbolt.org/z/1G7aqxs3c.
> > 
> > So it seems the projection application limit of 3 makes it impossible for
> > ranges::clamp to perfectly support the case where the projection returns an
> > rvalue reference.
> 
> Maybe this can help:
> 
>   auto&& __proj_val = std::__invoke(__proj, __val);
>       if (std::__invoke(__comp,
> std::forward<decltype(__proj_val)>(__proj_val), std::__invoke(__proj, __lo)))
>         return __lo;

We could safely forward __proj_val only in the second invocation of __comp,
after which __proj_val is no longer used, but I'm not sure that's worthwhile...

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Patrick Palka <ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:d91e7eab3a2c3957c2220ad71e62d9fc78cccb9b

commit r12-178-gd91e7eab3a2c3957c2220ad71e62d9fc78cccb9b
Author: Patrick Palka <ppalka@redhat.com>
Date:   Tue Apr 27 23:21:19 2021 -0400

    libstdc++: Fix various bugs in ranges_algo.h [PR100187, ...]

    This fixes some bugs with our ranges algorithms in uncommon situations,
    such as when the return type of a predicate is a non-copyable class type
    that's implicitly convertible to bool (PR100187), when a comparison
    predicate isn't invocable as an rvalue (PR100237), and when the return
    type of a projection function is non-copyable (PR100249).

    This also fixes PR100287, which reports that we're moving __first twice
    when constructing with it an empty subrange in ranges::partition.

    libstdc++-v3/ChangeLog:

            PR libstdc++/100187
            PR libstdc++/100237
            PR libstdc++/100249
            PR libstdc++/100287
            * include/bits/ranges_algo.h (__search_n_fn::operator()): Give
            the __value_comp lambda an explicit bool return type.
            (__is_permutation_fn::operator()): Give the __proj_scan local
            variable auto&& return type.  Give the __comp_scan lambda an
            explicit bool return type.
            (__remove_fn::operator()): Give the __pred lambda an explicit
            bool return type.
            (__partition_fn::operator()): Don't std::move __first twice
            when returning an empty subrange.
            (__min_fn::operator()): Don't std::move __comp.
            (__max_fn::operator()): Likewise.
            (__minmax_fn::operator()): Likewise.

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[hewillk at gmail dot com]

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

--- Comment #8 from 康桓瑋 <hewillk at gmail dot com> ---
(In reply to Patrick Palka from comment #6)
> > Maybe this can help:
> > 
> >   auto&& __proj_val = std::__invoke(__proj, __val);
> >       if (std::__invoke(__comp,
> > std::forward<decltype(__proj_val)>(__proj_val), std::__invoke(__proj, __lo)))
> >         return __lo;
> 
> We could safely forward __proj_val only in the second invocation of __comp,
> after which __proj_val is no longer used, but I'm not sure that's
> worthwhile...

I specifically asked the forum for this, Tim Song replied that both forwards
are safe, you can see more details in
https://stackoverflow.com/a/67348274/11638718.
Sorry to reply so late.

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[ppalka at gcc dot gnu.org]

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

--- Comment #9 from Patrick Palka <ppalka at gcc dot gnu.org> ---
(In reply to 康桓瑋 from comment #8)
> (In reply to Patrick Palka from comment #6)
> > > Maybe this can help:
> > > 
> > >   auto&& __proj_val = std::__invoke(__proj, __val);
> > >       if (std::__invoke(__comp,
> > > std::forward<decltype(__proj_val)>(__proj_val), std::__invoke(__proj, __lo)))
> > >         return __lo;
> > 
> > We could safely forward __proj_val only in the second invocation of __comp,
> > after which __proj_val is no longer used, but I'm not sure that's
> > worthwhile...
> 
> I specifically asked the forum for this, Tim Song replied that both forwards
> are safe, you can see more details in
> https://stackoverflow.com/a/67348274/11638718.
> Sorry to reply so late.

Thanks for looking into this!

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Patrick Palka
<ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:cb261f0e8fc08fb49f74002582ad5713cda684f7

commit r11-9145-gcb261f0e8fc08fb49f74002582ad5713cda684f7
Author: Patrick Palka <ppalka@redhat.com>
Date:   Tue Apr 27 23:21:19 2021 -0400

    libstdc++: Fix various bugs in ranges_algo.h [PR100187, ...]

    This fixes some bugs with our ranges algorithms in uncommon situations,
    such as when the return type of a predicate is a non-copyable class type
    that's implicitly convertible to bool (PR100187), when a comparison
    predicate isn't invocable as an rvalue (PR100237), and when the return
    type of a projection function is non-copyable (PR100249).

    This also fixes PR100287, which reports that we're moving __first twice
    when constructing with it an empty subrange in ranges::partition.

    libstdc++-v3/ChangeLog:

            PR libstdc++/100187
            PR libstdc++/100237
            PR libstdc++/100249
            PR libstdc++/100287
            * include/bits/ranges_algo.h (__search_n_fn::operator()): Give
            the __value_comp lambda an explicit bool return type.
            (__is_permutation_fn::operator()): Give the __proj_scan local
            variable auto&& return type.  Give the __comp_scan lambda an
            explicit bool return type.
            (__remove_fn::operator()): Give the __pred lambda an explicit
            bool return type.
            (__partition_fn::operator()): Don't std::move __first twice
            when returning an empty subrange.
            (__min_fn::operator()): Don't std::move __comp.
            (__max_fn::operator()): Likewise.
            (__minmax_fn::operator()): Likewise.

    (cherry picked from commit d91e7eab3a2c3957c2220ad71e62d9fc78cccb9b)

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Patrick Palka
<ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:139bafaaba0c775ca65712621bd60e079b488d73

commit r10-10210-g139bafaaba0c775ca65712621bd60e079b488d73
Author: Patrick Palka <ppalka@redhat.com>
Date:   Tue Apr 27 23:21:19 2021 -0400

    libstdc++: Fix various bugs in ranges_algo.h [PR100187, ...]

    This fixes some bugs with our ranges algorithms in uncommon situations,
    such as when the return type of a predicate is a non-copyable class type
    that's implicitly convertible to bool (PR100187), when a comparison
    predicate isn't invocable as an rvalue (PR100237), and when the return
    type of a projection function is non-copyable (PR100249).

    This also fixes PR100287, which reports that we're moving __first twice
    when constructing with it an empty subrange in ranges::partition.

    libstdc++-v3/ChangeLog:

            PR libstdc++/100187
            PR libstdc++/100237
            PR libstdc++/100249
            PR libstdc++/100287
            * include/bits/ranges_algo.h (__search_n_fn::operator()): Give
            the __value_comp lambda an explicit bool return type.
            (__is_permutation_fn::operator()): Give the __proj_scan local
            variable auto&& return type.  Give the __comp_scan lambda an
            explicit bool return type.
            (__remove_fn::operator()): Give the __pred lambda an explicit
            bool return type.
            (__partition_fn::operator()): Don't std::move __first twice
            when returning an empty subrange.
            (__min_fn::operator()): Don't std::move __comp.
            (__max_fn::operator()): Likewise.
            (__minmax_fn::operator()): Likewise.

    (cherry picked from commit d91e7eab3a2c3957c2220ad71e62d9fc78cccb9b)

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
   Target Milestone|---                         |10.4
             Status|NEW                         |RESOLVED

--- Comment #12 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I think this is fixed for 10.4 and 11.3, isn't it?

[Bug libstdc++/100249] missing forwarding std::__invoke result in ranges::is_permutation and ranges::clamp

[de34 at live dot cn]

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

Jiang An <de34 at live dot cn> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |de34 at live dot cn

--- Comment #13 from Jiang An <de34 at live dot cn> ---
This is not completely fixed.

See
- https://github.com/microsoft/STL/issues/3970#issuecomment-1681524306
- https://gcc.godbolt.org/z/3fsdbTx5Y