Pushed to v16. On Fri, Jul 25, 2025 at 4:08 PM Patrick Palka <ppa...@redhat.com> wrote:
> On Fri, 18 Jul 2025, Jonathan Wakely wrote: > > > When the C++98 std::distance and std::advance functions (and C++11 > > std::next and std::prev) are used with C++20 iterators there can be > > unexpected results, ranging from compilation failure to decreased > > performance to undefined behaviour. > > > > An iterator which satisfies std::input_iterator but does not meet the > > Cpp17InputIterator requirements might have std::output_iterator_tag for > > its std::iterator_traits<I>::iterator_category, which means it currently > > cannot be used with std::advance at all. However, the implementation of > > std::advance for a Cpp17InputIterator doesn't do anything that isn't > > valid for iterator types satsifying C++20 std::input_iterator. > > > > Similarly, a type satisfying C++20 std::bidirectional_iterator might be > > usable with std::prev, if it weren't for the fact that its C++17 > > iterator_category is std::input_iterator_tag. > > > > Finally, a type satisfying C++20 std::random_access_iterator might use a > > slower implementation for std::distance or std::advance if its C++17 > > iterator_category is not std::random_access_iterator_tag. > > > > This commit adds a __promotable_iterator concept to detect C++20 > > iterators which explicitly define an iterator_concept member, and which > > either have no iterator_category, or their iterator_category is weaker > > than their iterator_concept. This is used by std::distance and > > std::advance to detect iterators which should dispatch based on their > > iterator_concept instead of their iterator_category. This means that > > those functions just work and do the right thing for C++20 iterators > > which would otherwise fail to compile or have suboptimal performance. > > > > This is related to LWG 3197, which considers making it undefined to use > > std::prev with types which do not meet the Cpp17BidirectionalIterator > > requirements. I think making it work, as in this commit, is a better > > solution than banning it (or rejecting it at compile-time as libc++ > > does). > > > > libstdc++-v3/ChangeLog: > > > > PR libstdc++/102181 > > * include/bits/stl_iterator_base_funcs.h (distance, advance): > > Check C++20 iterator concepts and handle appropriately. > > (__detail::__iter_category_converts_to_concept): New concept. > > (__detail::__promotable_iterator): New concept. > > * testsuite/24_iterators/operations/cxx20_iterators.cc: New > > test. > > LGTM too > > > --- > > > > This is something I've been experimenting with to try and remove some of > > the differences between C++17 iterators and C++20 iterators. It would be > > really nice if the basic utilities for working with old iterators > > (std::next, std::distance, etc.) were usable with C++20 iterators. > > > > I'm not going to commit this now, because I'm about to be offline for a > > while. Please take a look, think about whether this works and is safe, > > and whether it seems like a direction we should pursue. > > > > The reason for the __promotable_iterator concept (rather than just > > checking the C++20 category and dispatching based on that alone) is that > > some C++17 iterators appear to satisfy the C++20 concepts BUT THEY LIE, > > e.g. see https://gcc.gnu.org/gcc-15/porting_to.html#cxx20-iterators > > > > Iterator adaptors and facades which provide all operators, but which > > define iterator_category as std::forward_iterator_tag, might satisfy the > > std::random_access_iterator concept. But if you try to actually use > > those operators, they fail outside the immediate context. So we need to > > trust what the iterator tells us: if it has an iterator_category, do not > > assume we can ignore it. So __promotable_iterator only considers > > iterators which explicitly define iterator_concept, because those are > > definitely claiming to be C++20 iterators. > > > > If you think this is useful and safe, feel free to push it on my behalf. > > It passes the testsuite (at least now that _Utf_iterator has the missing > > bidirectional operations, it failed ext/unicode/view.cc until then). > > > > .../include/bits/stl_iterator_base_funcs.h | 68 ++++++++++++++++++- > > .../operations/cxx20_iterators.cc | 60 ++++++++++++++++ > > 2 files changed, 125 insertions(+), 3 deletions(-) > > create mode 100644 > libstdc++-v3/testsuite/24_iterators/operations/cxx20_iterators.cc > > > > diff --git a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h > b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h > > index 637159fffc83..f78e5356d090 100644 > > --- a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h > > +++ b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h > > @@ -130,6 +130,28 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > > __distance(_OutputIterator, _OutputIterator, output_iterator_tag) = > delete; > > #endif > > > > +#ifdef __glibcxx_concepts > > +namespace __detail > > +{ > > + // Satisfied if ITER_TRAITS(Iter)::iterator_category is valid and is > > + // at least as strong as ITER_TRAITS(Iter)::iterator_concept. > > + template<typename _Iter> > > + concept __iter_category_converts_to_concept > > + = convertible_to<typename __iter_traits<_Iter>::iterator_category, > > + typename __iter_traits<_Iter>::iterator_concept>; > > + > > + // Satisfied if the type is a C++20 iterator that defines > iterator_concept, > > + // and its iterator_concept is stronger than its iterator_category > (if any). > > + // Used by std::distance and std::advance to detect iterators which > should > > + // dispatch based on their C++20 concept not their C++17 category. > > + template<typename _Iter> > > + concept __promotable_iterator > > + = input_iterator<_Iter> > > + && requires { typename __iter_traits<_Iter>::iterator_concept; } > > + && ! __iter_category_converts_to_concept<_Iter>; > > +} // namespace __detail > > +#endif > > + > > /** > > * @brief A generalization of pointer arithmetic. > > * @param __first An input iterator. > > @@ -149,6 +171,24 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > > typename iterator_traits<_InputIterator>::difference_type > > distance(_InputIterator __first, _InputIterator __last) > > { > > +#ifdef __glibcxx_concepts > > + // A type which satisfies the C++20 random_access_iterator > concept might > > + // have input_iterator_tag as its iterator_category type, which > would > > + // mean we select the O(n) __distance. Or a C++20 > std::input_iterator > > + // that is not a Cpp17InputIterator might have > output_iterator_tag as > > + // its iterator_category type and then calling __distance with > > + // std::__iterator_category(__first) would be ill-formed. > > + // So for C++20 iterator types we can just choose to do the right > thing. > > + if constexpr (__detail::__promotable_iterator<_InputIterator>) > > + { > > + if constexpr (random_access_iterator<_InputIterator>) > > + return __last - __first; > > + else > > + return std::__distance(std::move(__first), std::move(__last), > > + input_iterator_tag()); > > + } > > + else // assume it meets the Cpp17InputIterator requirements: > > +#endif > > // concept requirements -- taken care of in __distance > > return std::__distance(__first, __last, > > std::__iterator_category(__first)); > > @@ -221,9 +261,31 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > > inline _GLIBCXX17_CONSTEXPR void > > advance(_InputIterator& __i, _Distance __n) > > { > > - // concept requirements -- taken care of in __advance > > - typename iterator_traits<_InputIterator>::difference_type __d = > __n; > > - std::__advance(__i, __d, std::__iterator_category(__i)); > > +#ifdef __glibcxx_concepts > > + // A type which satisfies the C++20 bidirectional_iterator > concept might > > + // have input_iterator_tag as its iterator_category type, which > would > > + // mean we select the __advance overload which cannot move > backwards. > > + // A C++20 random_access_iterator we might select the O(n) > __advance > > + // if it doesn't meet the Cpp17RandomAccessIterator requirements. > > + // So for C++20 iterator types we can just choose to do the right > thing. > > + if constexpr (__detail::__promotable_iterator<_InputIterator> > > + && ranges::__detail::__is_integer_like<_Distance>) > > + { > > + auto __d = static_cast<iter_difference_t<_InputIterator>>(__n); > > + if constexpr (random_access_iterator<_InputIterator>) > > + std::__advance(__i, __d, random_access_iterator_tag()); > > + else if constexpr (bidirectional_iterator<_InputIterator>) > > + std::__advance(__i, __d, bidirectional_iterator_tag()); > > + else > > + std::__advance(__i, __d, input_iterator_tag()); > > + } > > + else // assume it meets the Cpp17InputIterator requirements: > > +#endif > > + { > > + // concept requirements -- taken care of in __advance > > + typename iterator_traits<_InputIterator>::difference_type __d = > __n; > > + std::__advance(__i, __d, std::__iterator_category(__i)); > > + } > > } > > > > #if __cplusplus >= 201103L > > diff --git > a/libstdc++-v3/testsuite/24_iterators/operations/cxx20_iterators.cc > b/libstdc++-v3/testsuite/24_iterators/operations/cxx20_iterators.cc > > new file mode 100644 > > index 000000000000..b613c3793b1a > > --- /dev/null > > +++ b/libstdc++-v3/testsuite/24_iterators/operations/cxx20_iterators.cc > > @@ -0,0 +1,60 @@ > > +// { dg-do run { target c++20 } } > > + > > +#include <ranges> > > +#include <testsuite_iterators.h> > > +#include <testsuite_hooks.h> > > + > > +// Bug 102181 std::advance and std::views::iota<std::int64_t> don't work > > +void > > +test_pr102181() > > +{ > > +#ifdef __SIZEOF_INT128__ > > + using type = unsigned __int128; > > +#else > > + using type = unsigned long; > > +#endif > > + auto v = std::ranges::iota_view(type(0), type(10)); > > + auto b = v.begin(); > > + VERIFY( std::distance(b, std::next(b)) == 1 ); > > + std::advance(b, std::iter_difference_t<decltype(b)>(1)); > > + VERIFY( *b == 1 ); > > + VERIFY( std::distance(b, v.end()) == 9 ); > > +} > > + > > +// > https://stackoverflow.com/questions/68100775/rangesviewtransform-produces-an-inputiterator-preventing-the-use-of-stdpre > > +void > > +test_transform_view_iterator() > > +{ > > + int a[] = {0, 1, 2, 3}; > > + __gnu_test::random_access_container<int> rr(a); > > + auto rx = std::ranges::views::transform(rr, std::identity{}); > > + auto re = rx.end(); > > + VERIFY( *std::prev(re) == 3 ); > > + VERIFY( std::distance(rx.begin(), re) == 4 ); > > + > > + __gnu_test::bidirectional_container<int> br(a); > > + auto bx = std::ranges::views::transform(br, std::identity{}); > > + auto be = bx.end(); > > + VERIFY( *std::prev(be) == 3 ); > > + VERIFY( std::distance(bx.begin(), be) == 4 ); > > + > > + __gnu_test::forward_container<int> fr(a); > > + auto fx = std::ranges::views::transform(br, std::identity{}); > > + auto fb = fx.begin(); > > + VERIFY( *std::next(fb) == 1 ); > > + VERIFY( std::distance(fb, fx.end()) == 4 ); > > + > > + __gnu_test::test_input_range<int> ir(a); > > + auto ix = std::ranges::views::transform(ir, std::identity{}); > > + auto ii = ix.begin(); > > + std::advance(ii, 1); > > + VERIFY( *ii == 1 ); > > + // N.B. cannot use std::distance or std::next here because there is no > > + // iterator_traits<decltype(ii)>::difference_type for this iterator. > > +} > > + > > +int main() > > +{ > > + test_pr102181(); > > + test_transform_view_iterator(); > > +} > > -- > > 2.50.1 > > > > > >
