[Bug libstdc++/100795] New: ranges::sample should not use std::sample directly

[Bug libstdc++/100795] New: ranges::sample should not use std::sample directly

[hewillk at gmail dot com]

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

            Bug ID: 100795
           Summary: ranges::sample should not use std::sample directly
           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: ---

Since some random access ranges are only input ranges in C++17, this will cause
ranges::sample to incorrectly reject the following valid case:


#include <algorithm>
#include <iostream>
#include <random>
#include <ranges>

int main() {
  std::ranges::sample(
    std::views::iota(0, 42),
    std::ostream_iterator<int>{std::cout, " "},
    42,
    std::mt19937{std::random_device{}()});
}

https://godbolt.org/z/dbWWTPKhx

[Bug libstdc++/100795] ranges::sample should not use std::sample directly

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-05-27
     Ever confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This works though:

--- include/bits/ranges_algo.h
+++ include/bits/ranges_algo.h
@@ -1762,8 +1762,10 @@
            // which may take linear time.
            auto __lasti = ranges::next(__first, __last);
            return _GLIBCXX_STD_A::
-             sample(std::move(__first), std::move(__lasti), std::move(__out),
-                    __n, std::forward<_Gen>(__g));
+             __sample(std::move(__first), std::move(__lasti),
+                      forward_iterator_tag{},
+                      std::move(__out), 0,
+                      __n, std::forward<_Gen>(__g));
          }
        else
          {

[Bug libstdc++/100795] ranges::sample should not use std::sample directly

[hewillk at gmail dot com]

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

--- Comment #2 from 康桓瑋 <hewillk at gmail dot com> ---
ranges::inplace_merge has the same issue:


#include <algorithm>
#include <array>
#include <ranges>

int main() {
  std::array a{42, 42, 42};
  auto r = std::views::iota(0, 3) | 
           std::views::transform([&a](int i) -> int& { return a[i]; });
  std::ranges::inplace_merge(r, r.begin());
}

https://godbolt.org/z/q6jbxGMjd

[Bug libstdc++/100795] ranges::sample should not use std::sample directly

[hewillk at gmail dot com]

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

--- Comment #3 from 康桓瑋 <hewillk at gmail dot com> ---
(In reply to 康桓瑋 from comment #2)
> ranges::inplace_merge has the same issue:
> 
> 
> #include <algorithm>
> #include <array>
> #include <ranges>
> 
> int main() {
>   std::array a{42, 42, 42};
>   auto r = std::views::iota(0, 3) | 
>            std::views::transform([&a](int i) -> int& { return a[i]; });
>   std::ranges::inplace_merge(r, r.begin());
> }
> 
> https://godbolt.org/z/q6jbxGMjd

Same for ranges::stable_sort and ranges::stable_partition.
(https://godbolt.org/z/qffGMW477)

[Bug libstdc++/100795] ranges::sample should not use std::sample directly

[hewillk at gmail dot com]

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

--- Comment #4 from 康桓瑋 <hewillk at gmail dot com> ---
Same with ranges::make_heap, ranges::push_heap, ranges::pop_heap, and
ranges::sort_heap when _GLIBCXX_CONCEPT_CHECKS is defined.

[Bug libstdc++/100795] ranges::sample should not use std::sample directly

[hewillk at gmail dot com]

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

--- Comment #5 from 康桓瑋 <hewillk at gmail dot com> ---
(In reply to 康桓瑋 from comment #4)
> Same with ranges::make_heap, ranges::push_heap, ranges::pop_heap, and
> ranges::sort_heap when _GLIBCXX_CONCEPT_CHECKS is defined.

And std::ranges::shuffle.

[Bug libstdc++/100795] ranges::sample should not use std::sample directly

[ppalka at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ppalka at gcc dot gnu.org

--- Comment #6 from Patrick Palka <ppalka at gcc dot gnu.org> ---
(In reply to 康桓瑋 from comment #2)
> ranges::inplace_merge has the same issue:
> 
> 
> #include <algorithm>
> #include <array>
> #include <ranges>
> 
> int main() {
>   std::array a{42, 42, 42};
>   auto r = std::views::iota(0, 3) | 
>            std::views::transform([&a](int i) -> int& { return a[i]; });
>   std::ranges::inplace_merge(r, r.begin());
> }
> 
> https://godbolt.org/z/q6jbxGMjd

Hmm, this one seems more like a problem in the specification of
transform_view::iterator_category.  Shouldn't r's iterator_category be
random_access_iterator here?  AFAICT it satisfies all the requirements of
__LegacyRandomAccessIterator.

[Bug libstdc++/100795] ranges::sample should not use std::sample directly

[hewillk at gmail dot com]

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

--- Comment #7 from 康桓瑋 <hewillk at gmail dot com> ---
(In reply to Patrick Palka from comment #6)
> (In reply to 康桓瑋 from comment #2)
> > ranges::inplace_merge has the same issue:
> > 
> > 
> > #include <algorithm>
> > #include <array>
> > #include <ranges>
> > 
> > int main() {
> >   std::array a{42, 42, 42};
> >   auto r = std::views::iota(0, 3) | 
> >            std::views::transform([&a](int i) -> int& { return a[i]; });
> >   std::ranges::inplace_merge(r, r.begin());
> > }
> > 
> > https://godbolt.org/z/q6jbxGMjd
> 
> Hmm, this one seems more like a problem in the specification of
> transform_view::iterator_category.  Shouldn't r's iterator_category be
> random_access_iterator here?  AFAICT it satisfies all the requirements of
> __LegacyRandomAccessIterator.

Damn, I think you are right. According to [range.transform.iterator#2.1], even
if is_lvalue_reference_v<invoke_result_t<F&, range_reference_t<Base>>> is true,
transform_view::iterator_category is still determined by the
iota_view::iterator_category.

[Bug libstdc++/100795] ranges::sample should not use std::sample directly

[barry.revzin at gmail dot com]

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

Barry Revzin <barry.revzin at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |barry.revzin at gmail dot com

--- Comment #8 from Barry Revzin <barry.revzin at gmail dot com> ---
Related: https://stackoverflow.com/q/70076645/2069064

std::ranges::sort calls std::sort, which then uses std::iter_swap instead of
std::ranges::iter_swap.

[Bug libstdc++/100795] ranges::sample should not use std::sample directly

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |Berenger.Berthoul at onera dot fr

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

[Bug libstdc++/100795] ranges::sample should not use std::sample directly

[hewillk at gmail dot com]

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

--- Comment #10 from 康桓瑋 <hewillk at gmail dot com> ---
For non-std::sample branches, we still have to consider that _Out only works
with its difference_type, so an explicit casting is missing here.

1580 |             return __out + __sample_sz;
     |                    ~~~~~~^~~~~~~~~~~~~

https://godbolt.org/z/T4s99GMrP