sample() of views::indices fails to compile with libstdc++ (because diffmax_t isn't an integral type)

[tonyelewis]

As always: thanks for all your amazing work; apologies if this is a false-positive.

The following compiles under trunk Clang with libc++ but fails under trunk Clang and trunk GCC with libstdc++ :

#include <random>
#include <vector>

#include <range/v3/algorithm/sample.hpp>
#include <range/v3/iterator.hpp>
#include <range/v3/view/indices.hpp>

using ::ranges::begin;
using ::ranges::sample;
using ::ranges::views::indices;
using ::std::mt19937;
using ::std::vector;

void fill_vec_with_random_sample_of_first_n_ints( const size_t   &prm_num_possible_vals,
                                                  vector<size_t> &prm_result,
                                                  mt19937        &prm_rng
                                                  ) {
	sample(
		indices( prm_num_possible_vals ),
		begin( prm_result ),
		static_cast<ptrdiff_t>( prm_result.size() ),
		prm_rng
	);
}

GCC errors (Godbolt using trunk range-v3):

In file included from /opt/compiler-explorer/gcc-trunk-20200719/include/c++/11.0.0/bits/random.h:35,
                 from /opt/compiler-explorer/gcc-trunk-20200719/include/c++/11.0.0/random:49,
                 from <source>:1:
/opt/compiler-explorer/gcc-trunk-20200719/include/c++/11.0.0/bits/uniform_int_dist.h: In instantiation of 'class std::uniform_int_distribution<ranges::detail::diffmax_t>':
/opt/compiler-explorer/libs/rangesv3/trunk/include/range/v3/algorithm/sample.hpp:51:69:   required from 'ranges::sample_result<I, O> ranges::detail::sample_sized_impl(I, S, ranges::iter_difference_t<I>, O, ranges::iter_difference_t<O>, Gen&&) [with I = ranges::basic_iterator<ranges::iota_view<long unsigned int, long unsigned int>::cursor>; S = ranges::basic_iterator<ranges::iota_view<long unsigned int, long unsigned int>::cursor>; O = __gnu_cxx::__normal_iterator<long unsigned int*, std::vector<long unsigned int> >; Gen = std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>&; ranges::sample_result<I, O> = ranges::detail::in_out_result<ranges::basic_iterator<ranges::iota_view<long unsigned int, long unsigned int>::cursor>, __gnu_cxx::__normal_iterator<long unsigned int*, std::vector<long unsigned int> > >; ranges::iter_difference_t<I> = ranges::detail::diffmax_t; ranges::iter_difference_t<O> = long int]'
/opt/compiler-explorer/libs/rangesv3/trunk/include/range/v3/algorithm/sample.hpp:186:49:   required from 'concepts::return_t<ranges::detail::in_out_result<typename ranges::detail::if_then<_borrowed_range<R> >::apply<decltype (ranges::_::begin(declval<Rng&>())), ranges::dangling>, O>, typename std::enable_if<(((((input_range<Rng> && weakly_incrementable<O>) && indirectly_copyable<decltype (ranges::_::begin(declval<Rng&>())), O>) && uniform_random_bit_generator<typename std::remove_reference<_Arg>::type>) && ((random_access_iterator<O> || forward_range<Rng>) || sized_range<Rng>)) && concepts::detail::CPP_true(concepts::detail::Nil{})), void>::type> ranges::sample_fn::operator()(Rng&&, O, ranges::iter_difference_t<I>, Gen&&) const [with Rng = ranges::iota_view<long unsigned int, long unsigned int>; O = __gnu_cxx::__normal_iterator<long unsigned int*, std::vector<long unsigned int> >; Gen = std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>&; concepts::return_t<ranges::detail::in_out_result<typename ranges::detail::if_then<_borrowed_range<R> >::apply<decltype (ranges::_::begin(declval<Rng&>())), ranges::dangling>, O>, typename std::enable_if<(((((input_range<Rng> && weakly_incrementable<O>) && indirectly_copyable<decltype (ranges::_::begin(declval<Rng&>())), O>) && uniform_random_bit_generator<typename std::remove_reference<_Arg>::type>) && ((random_access_iterator<O> || forward_range<Rng>) || sized_range<Rng>)) && concepts::detail::CPP_true(concepts::detail::Nil{})), void>::type> = ranges::detail::in_out_result<ranges::basic_iterator<ranges::iota_view<long unsigned int, long unsigned int>::cursor>, __gnu_cxx::__normal_iterator<long unsigned int*, std::vector<long unsigned int> > >; typename std::enable_if<(((((input_range<Rng> && weakly_incrementable<O>) && indirectly_copyable<decltype (ranges::_::begin(declval<Rng&>())), O>) && uniform_random_bit_generator<typename std::remove_reference<_Arg>::type>) && ((random_access_iterator<O> || forward_range<Rng>) || sized_range<Rng>)) && concepts::detail::CPP_true(concepts::detail::Nil{})), void>::type = void; decltype (ranges::_::begin(declval<Rng&>())) = ranges::basic_iterator<ranges::iota_view<long unsigned int, long unsigned int>::cursor>; typename std::remove_reference<_Arg>::type = std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>; typename ranges::detail::if_then<_borrowed_range<R> >::apply<decltype (ranges::_::begin(declval<Rng&>())), ranges::dangling> = ranges::basic_iterator<ranges::iota_view<long unsigned int, long unsigned int>::cursor>; ranges::iter_difference_t<I> = long int]'
<source>:23:2:   required from here
/opt/compiler-explorer/gcc-trunk-20200719/include/c++/11.0.0/bits/uniform_int_dist.h:76:49: error: static assertion failed: template argument must be an integral type
   76 |       static_assert(std::is_integral<_IntType>::value,
      |                                                 ^~~~~
Compiler returned: 1

Clang errors (Godbolt using trunk range-v3):

In file included from <source>:1:
In file included from /opt/compiler-explorer/gcc-9.2.0/lib/gcc/x86_64-linux-gnu/9.2.0/../../../../include/c++/9.2.0/random:49:
In file included from /opt/compiler-explorer/gcc-9.2.0/lib/gcc/x86_64-linux-gnu/9.2.0/../../../../include/c++/9.2.0/bits/random.h:35:
/opt/compiler-explorer/gcc-9.2.0/lib/gcc/x86_64-linux-gnu/9.2.0/../../../../include/c++/9.2.0/bits/uniform_int_dist.h:60:7: error: static_assert failed due to requirement 'std::is_integral<ranges::detail::diffmax_t>::value' "template argument must be an integral type"
      static_assert(std::is_integral<_IntType>::value,
      ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/libs/rangesv3/trunk/include/range/v3/algorithm/sample.hpp:51:69: note: in instantiation of template class 'std::uniform_int_distribution<ranges::detail::diffmax_t>' requested here
                std::uniform_int_distribution<iter_difference_t<I>> dist;
                                                                    ^
/opt/compiler-explorer/libs/rangesv3/trunk/include/range/v3/algorithm/sample.hpp:186:32: note: in instantiation of function template specialization 'ranges::detail::sample_sized_impl<ranges::basic_iterator<ranges::iota_view<unsigned long, unsigned long>::cursor>, ranges::basic_iterator<ranges::iota_view<unsigned long, unsigned long>::cursor>, __gnu_cxx::__normal_iterator<unsigned long *, std::vector<unsigned long, std::allocator<unsigned long>>>, std::mersenne_twister_engine<unsigned long, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253> &>' requested here
                return detail::sample_sized_impl(begin(rng),
                               ^
<source>:18:8: note: in instantiation of function template specialization 'ranges::sample_fn::operator()<ranges::iota_view<unsigned long, unsigned long>, __gnu_cxx::__normal_iterator<unsigned long *, std::vector<unsigned long, std::allocator<unsigned long>>>, std::mersenne_twister_engine<unsigned long, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253> &>' requested here
        sample(
              ^
In file included from <source>:4:
/opt/compiler-explorer/libs/rangesv3/trunk/include/range/v3/algorithm/sample.hpp:95:24: error: no matching function for call to 'sample_sized_impl'
                return detail::sample_sized_impl(std::move(first),
                       ^~~~~~~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/libs/rangesv3/trunk/include/range/v3/algorithm/sample.hpp:195:24: note: in instantiation of function template specialization 'ranges::sample_fn::operator()<ranges::basic_iterator<ranges::iota_view<unsigned long, unsigned long>::cursor>, ranges::basic_iterator<ranges::iota_view<unsigned long, unsigned long>::cursor>, __gnu_cxx::__normal_iterator<unsigned long *, std::vector<unsigned long, std::allocator<unsigned long>>>, std::mersenne_twister_engine<unsigned long, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253> &>' requested here
                return (*this)(
                       ^
<source>:18:8: note: in instantiation of function template specialization 'ranges::sample_fn::operator()<ranges::iota_view<unsigned long, unsigned long>, __gnu_cxx::__normal_iterator<unsigned long *, std::vector<unsigned long, std::allocator<unsigned long>>>, std::mersenne_twister_engine<unsigned long, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253> &>' requested here
        sample(
              ^
/opt/compiler-explorer/libs/rangesv3/trunk/include/range/v3/algorithm/sample.hpp:45:14: note: candidate template ignored: substitution failure [with I = ranges::basic_iterator<ranges::iota_view<unsigned long, unsigned long>::cursor>, S = ranges::basic_iterator<ranges::iota_view<unsigned long, unsigned long>::cursor>, O = __gnu_cxx::__normal_iterator<unsigned long *, std::vector<unsigned long, std::allocator<unsigned long>>>, Gen = std::mersenne_twister_engine<unsigned long, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253> &]
        auto sample_sized_impl(I first, S last, iter_difference_t<I> pop_size, O out,
             ^
2 errors generated.
Compiler returned: 1

This looks to be related to #1516. From what I can see, you've recently added, eg, is_integer = true to the diffmax_t specialisation of numeric_limits but this doesn't affect std::is_integral and libstdc++'s uniform_int_distribution (in bits/uniform_int_dist.h) statically-asserts that its type is_integral (whereas libc++'s uniform_int_distribution applies no such check).

[tonyelewis]

I can't see any obvious mention of constraints on uniform_­int_­distribution's IntType in rand.dist.uni.int. Perhaps this should just be raised as an issue against libstdc++ that it shouldn't constrain the type or at least should use numeric_limits so that custom types can be used? Or can/should range-v3 work around this?

[ericniebler]

I don't see how I can work around this in range-v3. You might be right, this could be a libstdc++ issue, or else an unfortunate but unavoidable(?) incompatibility.

[tonyelewis]

Yep. Fair enough. Thanks.

I haven't got time for a while to report the potential libstdc++ issue but I'll put it on my to-do list.

[tonyelewis]

I've created https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96731

I'm not sure it's a great report. Feel very free to wade in over there (or indeed to completely ignore :slightly_smiling_face:).

[tonyelewis]

FYI: Jonathan Wakely quickly updated https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96731 to point me to http://eel.is/c++draft/rand#req.genl-1.5, which I'd missed. It says the effect of instantiating the distribution with a type other than a standard int type is undefined.

He has confirmed the issue as an enhancement request.

Out of interest, what pushes range-v3 to introduce a pseudo-int-type diffmax_t? Is this the way of the future? If so, will there be value in a suitably inclusive concept being employed throughout the standard, eg for uniform_­int_­distribution, instead of an explicit list of int types?

[JohelEGP]

You can find the motivation in https://wg21.link/P1522. Basically, it is to make the following example from the paper defined:

iota_view v {size_t(0), SIZE_MAX};
auto d = v.end() - v.begin();// Undefined behavior

[tonyelewis]

Thanks. Blimey. :slightly_smiling_face:

[tonyelewis]

Just FYI: Jonathan Wakely made some progress on relaxing libstc++ but thinks my example can't be made to work because the standard says sample requires an integral type (else the code is ill-formed, diagnostic required). See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96731#c4 .