On Fri, 18 Jul 2025, 18:51 Jonathan Wakely, <jwak...@redhat.com> 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. > --- > > 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 I think we should change the std::vector::vector(InputIterator, InputIterator) constructor to use __promotable_iterator too. That would still make it fast for iota view iterators, but would not break unconstrained iterator facades. > > 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 > >
