From aecea4158f4e547af349657a3d16cb031a30ec3b Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Mon, 21 Sep 2020 23:43:25 +0100 Subject: [PATCH] libstdc++: Fix constraints for drop_view::begin() const [LWG 3482] libstdc++-v3/ChangeLog: * include/std/ranges (drop_view::begin()): Adjust constraints to match the correct condition for O(1) ranges::next (LWG 3482). * testsuite/std/ranges/adaptors/drop.cc: Check that iterator is cached for non-sized_range. --- libstdc++-v3/include/std/ranges | 17 ++- .../testsuite/std/ranges/adaptors/drop.cc | 128 ++++++++++++++++-- 2 files changed, 131 insertions(+), 14 deletions(-) diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 005e89f94b2..1bf894dd570 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -2238,7 +2238,10 @@ namespace views _Vp _M_base = _Vp(); range_difference_t<_Vp> _M_count = 0; - static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>; + // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies + // both random_access_range and sized_range. Otherwise, cache its result. + static constexpr bool _S_needs_cached_begin + = !(random_access_range && sized_range); [[no_unique_address]] __detail::__maybe_present_t<_S_needs_cached_begin, __detail::_CachedPosition<_Vp>> @@ -2260,9 +2263,12 @@ namespace views base() && { return std::move(_M_base); } + // This overload is disabled for simple views with constant-time begin(). constexpr auto - begin() requires (!(__detail::__simple_view<_Vp> - && random_access_range<_Vp>)) + begin() + requires (!(__detail::__simple_view<_Vp> + && random_access_range + && sized_range)) { if constexpr (_S_needs_cached_begin) if (_M_cached_begin._M_has_value()) @@ -2275,8 +2281,11 @@ namespace views return __it; } + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 3482. drop_view's const begin should additionally require sized_range constexpr auto - begin() const requires random_access_range + begin() const + requires random_access_range && sized_range { return ranges::next(ranges::begin(_M_base), _M_count, ranges::end(_M_base)); diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc index 3c82caea772..5fe94b67507 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc @@ -26,6 +26,7 @@ using __gnu_test::test_range; using __gnu_test::forward_iterator_wrapper; using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; namespace ranges = std::ranges; namespace views = ranges::views; @@ -123,8 +124,52 @@ struct test_wrapper : forward_iterator_wrapper forward_iterator_wrapper::operator++(); return *this; } +}; - test_wrapper +void +test07() +{ + int x[] = {1,2,3,4,5}; + test_range rx(x); + auto v = rx | views::drop(3); + VERIFY( test_wrapper::increment_count == 0 ); + (void) v.begin(); + VERIFY( test_wrapper::increment_count == 3 ); + (void) v.begin(); + VERIFY( test_wrapper::increment_count == 3 ); + VERIFY( ranges::equal(v, (int[]){4,5}) ); + VERIFY( test_wrapper::increment_count == 5 ); + VERIFY( ranges::equal(v, (int[]){4,5}) ); + VERIFY( test_wrapper::increment_count == 7 ); +} + +template +struct ra_test_wrapper : random_access_iterator_wrapper +{ + static inline int increment_count = 0; + + using random_access_iterator_wrapper::random_access_iterator_wrapper; + + ra_test_wrapper() : random_access_iterator_wrapper() + { } + + ra_test_wrapper + operator++(int) + { + auto tmp = *this; + ++*this; + return tmp; + } + + ra_test_wrapper& + operator++() + { + ++increment_count; + random_access_iterator_wrapper::operator++(); + return *this; + } + + ra_test_wrapper operator--(int) { auto tmp = *this; @@ -132,23 +177,85 @@ struct test_wrapper : forward_iterator_wrapper return tmp; } - test_wrapper& + ra_test_wrapper& operator--() { - forward_iterator_wrapper::operator--(); + random_access_iterator_wrapper::operator--(); + return *this; + } + + ra_test_wrapper& + operator+=(std::ptrdiff_t n) + { + random_access_iterator_wrapper::operator+=(n); return *this; } + + ra_test_wrapper& + operator-=(std::ptrdiff_t n) + { return *this += -n; } + + ra_test_wrapper + operator+(std::ptrdiff_t n) const + { + auto tmp = *this; + return tmp += n; + } + + ra_test_wrapper + operator-(std::ptrdiff_t n) const + { + auto tmp = *this; + return tmp -= n; + } + + std::ptrdiff_t + operator-(const ra_test_wrapper& it) const + { + return static_cast&>(*this) - it; + } + + friend ra_test_wrapper + operator+(std::ptrdiff_t n, const ra_test_wrapper& it) + { return it + n; } }; void -test07() +test08() { - int x[] = {1,2,3,4,5}; - test_range rx(x); - auto v = rx | views::drop(3); - VERIFY( ranges::equal(v, (int[]){4,5}) ); - VERIFY( ranges::equal(v, (int[]){4,5}) ); - VERIFY( test_wrapper::increment_count == 7 ); + // LWG 3482 - drop_view's const begin should additionally require sized_range + + short a[10]{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; + test_range ra(a); + static_assert( ranges::random_access_range ); + ranges::subrange nonsized = {ra.begin(), std::unreachable_sentinel}; + using Nonsized = decltype(nonsized); + static_assert( ranges::random_access_range ); + static_assert( ! ranges::sized_range ); + auto v1 = nonsized | views::drop(5); + VERIFY( ra_test_wrapper::increment_count == 0 ); + auto b1 = v1.begin(); + VERIFY( ra_test_wrapper::increment_count == 5 ); + VERIFY( v1.begin() == b1 ); + VERIFY( ra_test_wrapper::increment_count == 5 ); + VERIFY( *b1 == 5 ); + VERIFY( *v1.begin() == 5 ); + VERIFY( ra_test_wrapper::increment_count == 5 ); + + long b[10]{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; + test_range rb(b); + ranges::subrange sized = {rb.begin(), rb.begin()+6}; + using Sized = decltype(sized); + static_assert( ranges::random_access_range ); + static_assert( ranges::sized_range ); + auto v2 = sized | views::drop(6); + auto b2 = v2.begin(); + VERIFY( ra_test_wrapper::increment_count == 0 ); + VERIFY( v2.begin() == b2 ); + VERIFY( ra_test_wrapper::increment_count == 0 ); + VERIFY( *b2 == 6 ); + VERIFY( *v2.begin() == 6 ); + VERIFY( ra_test_wrapper::increment_count == 0 ); } int @@ -161,4 +268,5 @@ main() test05(); test06(); test07(); + test08(); } -- 2.30.2