[Bug libstdc++/100387] New: ranges::minmax compares moved-out value

[Bug libstdc++/100387] New: ranges::minmax compares moved-out value

[hewillk at gmail dot com]

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

            Bug ID: 100387
           Summary: ranges::minmax compares moved-out value
           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: ---

In ranges_algo.h#L3301:

  if (std::__invoke(__comp,
                    std::__invoke(__proj, __tmp),
                    std::__invoke(__proj, __result.min)))
    __result.min = std::move(__tmp);
  if (!(bool)std::__invoke(__comp,
                           std::__invoke(__proj, __tmp),
                           std::__invoke(__proj, __result.max)))
    __result.max = std::move(__tmp);

we compare the moved-out __tmp in the second if statement.
test: https://godbolt.org/z/W6WTG6sdG

[Bug libstdc++/100387] ranges::minmax compares moved-out value

[hewillk at gmail dot com]

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

--- Comment #1 from 康桓瑋 <hewillk at gmail dot com> ---
Also, in std::shift_right:

std::move(std::move(__first), std::move(__dest_head),
          std::move(__result));
return __result;

we return the moved-out __result.

[Bug libstdc++/100387] ranges::minmax compares moved-out value

[ppalka at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
           Assignee|unassigned at gcc dot gnu.org      |ppalka at gcc dot gnu.org
             Status|UNCONFIRMED                 |ASSIGNED
                 CC|                            |ppalka at gcc dot gnu.org
   Last reconfirmed|                            |2021-05-03

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

[Bug libstdc++/100387] ranges::minmax compares moved-out value

[ppalka at gcc dot gnu.org]

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

--- Comment #3 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Also, our minmax and minmax_element perform up to 2n comparisons, violating the
complexity requirements:

minmax: At most 3 / 2 * ranges::distance(r) comparisons and twice as many
applications of the projection.

minmax_element: At most max(floor((3/2)*(N−1)), 0) applications of the
comparison and twice as many applications of the projection, where N =
ranges::distance(first, last).

[Bug libstdc++/100387] ranges::minmax compares moved-out value

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 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:cc9c94d43dcfa98436152af9c00f011e9dab25f6

commit r12-1656-gcc9c94d43dcfa98436152af9c00f011e9dab25f6
Author: Patrick Palka <ppalka@redhat.com>
Date:   Fri Jun 18 19:33:39 2021 -0400

    libstdc++: Reduce ranges::minmax/minmax_element comparison complexity

    This rewrites ranges::minmax and ranges::minmax_element so that it
    performs at most 3*N/2 many comparisons, as required by the standard.
    In passing, this also fixes PR100387 by avoiding a premature std::move
    in ranges::minmax and in std::shift_right.

            PR libstdc++/100387

    libstdc++-v3/ChangeLog:

            * include/bits/ranges_algo.h (__minmax_fn::operator()): Rewrite
            to limit comparison complexity to 3*N/2.
            (__minmax_element_fn::operator()): Likewise.
            (shift_right): Avoid premature std::move of __result.
            * testsuite/25_algorithms/minmax/constrained.cc (test04, test05):
            New tests.
            * testsuite/25_algorithms/minmax_element/constrained.cc (test02):
            Likewise.

[Bug libstdc++/100387] ranges::minmax compares moved-out value

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 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:927548b42c4850094eb41c7ae882cbe219b24231

commit r11-8728-g927548b42c4850094eb41c7ae882cbe219b24231
Author: Patrick Palka <ppalka@redhat.com>
Date:   Fri Jun 18 19:33:39 2021 -0400

    libstdc++: Reduce ranges::minmax/minmax_element comparison complexity

    This rewrites ranges::minmax and ranges::minmax_element so that it
    performs at most 3*N/2 many comparisons, as required by the standard.
    In passing, this also fixes PR100387 by avoiding a premature std::move
    in ranges::minmax and in std::shift_right.

            PR libstdc++/100387

    libstdc++-v3/ChangeLog:

            * include/bits/ranges_algo.h (__minmax_fn::operator()): Rewrite
            to limit comparison complexity to 3*N/2.
            (__minmax_element_fn::operator()): Likewise.
            (shift_right): Avoid premature std::move of __result.
            * testsuite/25_algorithms/minmax/constrained.cc (test04, test05):
            New tests.
            * testsuite/25_algorithms/minmax_element/constrained.cc (test02):
            Likewise.

    (cherry picked from commit cc9c94d43dcfa98436152af9c00f011e9dab25f6)

[Bug libstdc++/100387] ranges::minmax compares moved-out value

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 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:1335d35a530f31f60874cea1d5c98de81deed335

commit r10-10196-g1335d35a530f31f60874cea1d5c98de81deed335
Author: Patrick Palka <ppalka@redhat.com>
Date:   Fri Jun 18 19:33:39 2021 -0400

    libstdc++: Reduce ranges::minmax/minmax_element comparison complexity

    This rewrites ranges::minmax and ranges::minmax_element so that it
    performs at most 3*N/2 many comparisons, as required by the standard.
    In passing, this also fixes PR100387 by avoiding a premature std::move
    in ranges::minmax and in std::shift_right.

            PR libstdc++/100387

    libstdc++-v3/ChangeLog:

            * include/bits/ranges_algo.h (__minmax_fn::operator()): Rewrite
            to limit comparison complexity to 3*N/2.
            (__minmax_element_fn::operator()): Likewise.
            (shift_right): Avoid premature std::move of __result.
            * testsuite/25_algorithms/minmax/constrained.cc (test04, test05):
            New tests.
            * testsuite/25_algorithms/minmax_element/constrained.cc (test02):
            Likewise.

    (cherry picked from commit cc9c94d43dcfa98436152af9c00f011e9dab25f6)

[Bug libstdc++/100387] ranges::minmax compares moved-out value

[ppalka at gcc dot gnu.org]

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

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

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

--- Comment #7 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Fixed for GCC 10.4/11.3/12

[Bug libstdc++/100387] ranges::minmax compares moved-out value

[ppalka at gcc dot gnu.org]

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

--- Comment #8 from Patrick Palka <ppalka at gcc dot gnu.org> ---
(In reply to Patrick Palka from comment #7)
> Fixed for GCC 10.4/11.3/12

For the record this fix is also present in 11.2