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
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
