[PATCH 2/2] libstdc++: P1739R4 Avoid template bloat for safe_ranges in combination with ...
Patrick Palka
ppalka@redhat.com
Thu Feb 20 04:53:00 GMT 2020
... 'subrange-y' view adaptors
This implements an interpretation of P1739R4. It's only an "interpretation"
becuase AFAICT there is an issue with the paper's wording as-is. So this patch
deviates from paper when it comes to the problematic wording.
The issue is that the paper's wording for views::take requires that the
views::take of a specialization of subrange is not just another subrange, but
specifically is the same specialization as the input subrange.
But if, say, the input subrange does not model common_range, then the expression
in section 6.1
T{begin(E), begin(E) + min(size(E), F)}
is ill-formed because T -- a specialization of subrange which does not model
common_range -- must be constructed with an iterator-sentinel pair and not an
iterator-iterator pair. A similar issue arises with the views::take of an
iota_view whose value type differs from the type of its bound.
So in light of this issue, this patch deviates from the paper's wording here by
allowing the views::take of a subrange/iota_view input to be a different
specialization than that of the input.
Moreover, I found myself needing to define an extra constrained constructor
iota_view(iterator_, iterator_) alongside the newly added
iota_view(iterator_, sentinel_) constructor, so that the expression
in views::take
iota_view<ValueType,ValueType>{begin(E), begin(E) + min(size(E), F)}
is well-formed in general. Despite these deviations, the intended end result
remains the same AFAICT.
libstdc++-v3/ChangeLog:
P1739R4 Avoid template bloat for safe_ranges in combination with
'subrange-y' view adaptors
* include/std/ranges (iota_view): Forward declare class _Sentinel.
(iota_view::_Iterator): Befriend _Sentinel.
(iota_view::_Sentinel): Befriend iota_view.
(iota_view::_Sentinel::_M_equal): New member function.
(iota_view::_Sentinel::operator==): Define in terms of _M_equal.
(iota_view::iota_view): Two new constrained constructors, one taking an
_Iterator and a _Sentinel, and another taking two _Iterators.
(views::__detail::__is_empty_view, views::__detail::is_dynamic_span,
views::__detail::is_basic_string_view, views::__detail::__is_iota_view,
views::__detail::__is_subrange): New helper type traits.
(views::take): Rewrite in accordance with P1739R4.
(views::drop): Likewise.
(views::counted): When _Iter models contiguous_iterator, return
a dynamic-extend span, in according with P1739R4.
* testsuite/std/range/adaptors/counted.cc: Adjust and augment tests to
verify behavior in accordance with P1739R4.
* testsuite/std/range/adaptors/drop.cc: Likewise.
* testsuite/std/range/adaptors/take.cc: Likewise.
---
libstdc++-v3/include/std/ranges | 117 +++++++++++++++++-
.../testsuite/std/ranges/adaptors/counted.cc | 16 ++-
.../testsuite/std/ranges/adaptors/drop.cc | 96 ++++++++++++++
.../testsuite/std/ranges/adaptors/take.cc | 83 ++++++++++++-
4 files changed, 299 insertions(+), 13 deletions(-)
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 1b2bf448e9c..dfd143b23e1 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -43,6 +43,8 @@
#include <initializer_list>
#include <iterator>
#include <optional>
+#include <span>
+#include <string_view>
#include <tuple>
/**
@@ -635,6 +637,8 @@ namespace ranges
class iota_view : public view_interface<iota_view<_Winc, _Bound>>
{
private:
+ struct _Sentinel;
+
struct _Iterator
{
private:
@@ -811,11 +815,19 @@ namespace ranges
private:
_Winc _M_value = _Winc();
+
+ friend _Sentinel;
};
struct _Sentinel
{
private:
+ constexpr bool
+ _M_equal(const _Iterator& __x) const
+ { return __x._M_value == _M_bound; }
+
+ friend iota_view;
+
_Bound _M_bound = _Bound();
public:
@@ -827,7 +839,7 @@ namespace ranges
friend constexpr bool
operator==(const _Iterator& __x, const _Sentinel& __y)
- { return __x._M_value == __y._M_bound; }
+ { return __y._M_equal(__x); }
friend constexpr iter_difference_t<_Winc>
operator-(const _Iterator& __x, const _Sentinel& __y)
@@ -862,6 +874,22 @@ namespace ranges
}
}
+ constexpr
+ iota_view(_Iterator __first, _Sentinel __last)
+ // XXX: this constraint does not appear in P1739R4, but it seems
+ // sensible.
+ requires (!same_as<_Winc, _Bound>)
+ : iota_view(*__first, __last._M_bound)
+ { }
+
+ // XXX: this constructor does not appear in P1739R4, but it's necessary
+ // for the iota_view folding in views::take to work.
+ constexpr
+ iota_view(_Iterator __first, _Iterator __last)
+ requires same_as<_Winc, _Bound>
+ : iota_view(*__first, *__last)
+ { }
+
constexpr _Iterator
begin() const { return _Iterator{_M_value}; }
@@ -1965,10 +1993,70 @@ namespace views
namespace views
{
+ namespace __detail
+ {
+ template<typename _Tp>
+ inline constexpr bool __is_empty_view = false;
+
+ template<typename _Tp>
+ inline constexpr bool __is_empty_view<empty_view<_Tp>> = true;
+
+ template<typename _Tp>
+ inline constexpr bool __is_dynamic_span = false;
+
+ template<typename _Tp>
+ inline constexpr bool __is_dynamic_span<span<_Tp, dynamic_extent>>
+ = true;
+
+ template<typename _Tp>
+ inline constexpr bool __is_basic_string_view = false;
+
+ template<typename _CharT, typename _Traits>
+ inline constexpr bool
+ __is_basic_string_view<basic_string_view<_CharT, _Traits>> = true;
+
+ template<typename _Tp>
+ inline constexpr bool __is_iota_view = false;
+
+ template<weakly_incrementable _Winc, semiregular _Bound>
+ inline constexpr bool __is_iota_view<iota_view<_Winc, _Bound>> = true;
+
+ template<typename _Tp>
+ inline constexpr bool __is_subrange = false;
+
+ template<typename _It, typename _Sent, subrange_kind _Kind>
+ inline constexpr bool
+ __is_subrange<subrange<_It, _Sent, _Kind>> = true;
+ }
+
inline constexpr __adaptor::_RangeAdaptor take
- = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
+ = [] <viewable_range _Range> (_Range&& __r, range_difference_t<_Range> __n)
{
- return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
+ using _Tp = remove_cvref_t<_Range>;
+ if constexpr (__detail::__is_empty_view<_Tp>)
+ return std::forward<_Range>(__r);
+ else if constexpr (random_access_range<_Tp> && sized_range<_Tp>)
+ {
+ // XXX: we diverge from P1739R4 here in the way we fold iota_view
+ // and subrange.
+ auto __begin = ranges::begin(__r);
+ auto __size = std::min<decltype(__n)>(ranges::size(__r), __n);
+ if constexpr (__detail::__is_dynamic_span<_Tp>
+ || __detail::__is_basic_string_view<_Tp>)
+ return _Tp{__begin, __begin + __size};
+ else if constexpr (__detail::__is_iota_view<_Tp>)
+ {
+ using _ValueType = range_value_t<_Tp>;
+ return iota_view<_ValueType, _ValueType>{__begin,
+ __begin + __size};
+ }
+ else if constexpr (__detail::__is_subrange<_Tp>)
+ return subrange{__begin, __begin + __size};
+ else
+ return take_view{std::forward<_Range>(__r), __n};
+ }
+ else
+ return take_view{std::forward<_Range>(__r), __n};
};
} // namespace views
@@ -2135,9 +2223,24 @@ namespace views
namespace views
{
inline constexpr __adaptor::_RangeAdaptor drop
- = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
+ = [] <viewable_range _Range> (_Range&& __r, range_difference_t<_Range> __n)
{
- return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
+ using _Tp = remove_cvref_t<_Range>;
+ if constexpr (__detail::__is_empty_view<_Tp>)
+ return std::forward<_Range>(__r);
+ else if constexpr (random_access_range<_Tp> && sized_range<_Tp>
+ && (__detail::__is_dynamic_span<_Tp>
+ || __detail::__is_basic_string_view<_Tp>
+ || __detail::__is_iota_view<_Tp>
+ || __detail::__is_subrange<_Tp>))
+ {
+ auto __begin = ranges::begin(__r);
+ auto __size = std::min<decltype(__n)>(ranges::size(__r), __n);
+ auto __end = ranges::end(__r);
+ return _Tp{__begin + __size, __end};
+ }
+ else
+ return drop_view{std::forward<_Range>(__r), __n};
};
} // namespace views
@@ -2903,7 +3006,9 @@ namespace views
constexpr auto
operator()(_Iter __i, iter_difference_t<_Iter> __n) const
{
- if constexpr (random_access_iterator<_Iter>)
+ if constexpr (contiguous_iterator<_Iter>)
+ return span{to_address(std::move(__i)), __n};
+ else if constexpr (random_access_iterator<_Iter>)
return subrange{__i, __i + __n};
else
return subrange{counted_iterator{std::move(__i), __n},
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/counted.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/counted.cc
index e81f9062d39..0b6415e44df 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/counted.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/counted.cc
@@ -25,6 +25,7 @@
using __gnu_test::test_range;
using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
namespace ranges = std::ranges;
namespace views = ranges::views;
@@ -33,7 +34,8 @@ void
test01()
{
int x[] = {0,1,2,3,4,5,0,1,2,3,4,5};
- auto v = views::counted(x, 5);
+ test_range<int, random_access_iterator_wrapper> rx(x);
+ auto v = views::counted(rx.begin(), 5);
VERIFY( ranges::equal(v, (int[]){0,1,2,3,4}) );
using R = decltype(v);
static_assert(ranges::view<R>);
@@ -56,9 +58,21 @@ test02()
static_assert(!ranges::bidirectional_range<R>);
}
+void
+test03()
+{
+ int x[] = {0,1,2,3,4,5,0,1,2,3,4,5};
+ auto v = views::counted(x, 5);
+ VERIFY( ranges::equal(v, (int[]){0,1,2,3,4}) );
+ using R = decltype(v);
+ // P1739R4: The views::take of a contiguous_iterator is a span.
+ static_assert(std::same_as<R, std::span<int>>);
+}
+
int
main()
{
test01();
test02();
+ test03();
}
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
index 93fbafcf5a3..786acf668ff 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
@@ -24,7 +24,9 @@
#include <testsuite_iterators.h>
using __gnu_test::test_range;
+using __gnu_test::test_sized_range;
using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
namespace ranges = std::ranges;
namespace views = ranges::views;
@@ -95,6 +97,93 @@ test06()
VERIFY( ranges::empty(x | views::drop(10)) );
}
+void
+test07()
+{
+ auto v = views::iota(0,5) | views::drop(3);
+ using R = decltype(v);
+ // P1739R4: The views::drop of an iota_view is an iota_view.
+ static_assert(std::same_as<R, ranges::iota_view<int, int>>);
+ VERIFY( ranges::equal(v, (int[]){3,4}) );
+}
+
+void
+test08()
+{
+ int x[] = {1,2,3,4,5};
+ std::span rx{x, 5};
+ auto v = rx | views::drop(2);
+ using R = decltype(v);
+ // P1739R4: The views::drop of a dynamic-extent span is a dynamic-extent span.
+ static_assert(std::same_as<R, std::span<int>>);
+ VERIFY( ranges::equal(v, (int[]){3,4,5}) );
+ VERIFY( ranges::empty(rx | views::drop(100)) );
+}
+
+void
+test09()
+{
+ using namespace std::literals;
+ std::string_view rx = "hello world!";
+ auto v = rx | views::drop(6);
+ using R = decltype(v);
+ // P1739R4: The views::drop of a string_view is a string_view.
+ static_assert(std::same_as<R, std::string_view>);
+ VERIFY( ranges::equal(v, "world!"sv) );
+ VERIFY( ranges::empty(rx | views::drop(100)) );
+}
+
+void
+test10()
+{
+ int x[] = {1,2,3,4,5};
+ ranges::subrange<int*> rx{x, x+4};
+ auto v = rx | views::drop(2);
+ using R = decltype(v);
+ // P1739R4: The views::drop of a subrange is a subrange.
+ static_assert(std::same_as<R, ranges::subrange<int*>>);
+ VERIFY( ranges::equal(v, (int[]){3,4}) );
+ VERIFY( ranges::empty(rx | views::drop(100)) );
+}
+
+void
+test11()
+{
+ int x[] = {1,2,3,4,5};
+ test_sized_range<int, random_access_iterator_wrapper> y(x);
+ ranges::subrange rx{y.begin(), y.end()};
+ auto v = rx | views::drop(2);
+ using R = decltype(v);
+ // P1739R4: The views::drop of a subrange is a subrange.
+ static_assert(std::same_as<R, decltype(rx)>);
+ VERIFY( ranges::equal(v, (int[]){3,4,5}) );
+ VERIFY( ranges::empty(rx | views::drop(100)) );
+}
+
+void
+test12()
+{
+ ranges::empty_view<int> rx;
+ auto v = rx | views::drop(1);
+ using R = decltype(v);
+ // P1739R4: The views::drop of an empty_view is an empty_view.
+ static_assert(std::same_as<R, ranges::empty_view<int>>);
+}
+
+void
+test13()
+{
+ int x[] = {1,2,3,4,5};
+ auto it = std::counted_iterator(x, 4);
+ auto v = views::iota(it, std::default_sentinel) | views::drop(2);
+ using R = decltype(v);
+ static_assert(std::same_as<R, ranges::iota_view<std::counted_iterator<int*>,
+ std::default_sentinel_t>>);
+ VERIFY( ranges::size(v) == 2 );
+ VERIFY( (*ranges::begin(v)).base() == x+2 );
+ VERIFY( (*(ranges::begin(v)+1)).base() == x+3 );
+}
+
int
main()
{
@@ -104,4 +193,11 @@ main()
test04();
test05();
test06();
+ test07();
+ test08();
+ test09();
+ test10();
+ test11();
+ test12();
+ test13();
}
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/take.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/take.cc
index e2d2edbe0a8..3663f12aa68 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/take.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/take.cc
@@ -20,11 +20,15 @@
#include <algorithm>
#include <ranges>
+#include <span>
+#include <string_view>
#include <testsuite_hooks.h>
#include <testsuite_iterators.h>
using __gnu_test::test_range;
+using __gnu_test::test_sized_range;
using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
namespace ranges = std::ranges;
namespace views = ranges::views;
@@ -46,12 +50,9 @@ void
test02()
{
auto v = views::take(views::iota(0, 20), 5);
- static_assert(ranges::view<decltype(v)>);
- static_assert(ranges::sized_range<decltype(v)>);
- static_assert(ranges::common_range<decltype(v)>);
- static_assert(ranges::random_access_range<decltype(v)>);
- static_assert(!ranges::contiguous_range<decltype(v)>);
- static_assert(ranges::range<const decltype(v)>);
+ using R = decltype(v);
+ // P1739R4: The views::take of an iota_view is an iota_view.
+ static_assert(std::same_as<R, ranges::iota_view<int, int>>);
VERIFY( ranges::equal(v, (int[]){0,1,2,3,4}) );
}
@@ -85,6 +86,71 @@ test04()
VERIFY( ranges::equal(v | views::take(5), (int[]){1,2,3}) );
}
+void
+test05()
+{
+ int x[] = {1,2,3,4,5};
+ std::span rx{x, 5};
+ auto v = rx | views::take(3);
+ using R = decltype(v);
+ // P1739R4: The views::take of a dynamic-extent span is a dynamic-extent span.
+ static_assert(std::same_as<R, std::span<int>>);
+ VERIFY( ranges::equal(v, (int[]){1,2,3}) );
+ VERIFY( ranges::equal(rx | views::take(100), rx) );
+}
+
+void
+test06()
+{
+ using namespace std::literals;
+ std::string_view rx = "hello world!";
+ auto v = rx | views::take(5);
+ using R = decltype(v);
+ // P1739R4: The views::take of a string_view is a string_view.
+ static_assert(std::same_as<R, std::string_view>);
+ VERIFY( ranges::equal(v, "hello"sv) );
+ VERIFY( ranges::equal(rx | views::take(100), rx) );
+}
+
+void
+test07()
+{
+ int x[] = {1,2,3,4,5};
+ ranges::subrange rx{x, x+4};
+ auto v = rx | views::take(3);
+ using R = decltype(v);
+ // P1739R4: The views::take of a subrange is a subrange.
+ static_assert(std::same_as<R, ranges::subrange<int*>>);
+ VERIFY( ranges::equal(v, (int[]){1,2,3}) );
+ VERIFY( ranges::equal(rx | views::take(100), rx) );
+}
+
+void
+test08()
+{
+ int x[] = {1,2,3,4,5};
+ test_sized_range<int, random_access_iterator_wrapper> y(x);
+ ranges::subrange rx{y.begin(), y.end()};
+ auto v = rx | views::take(3);
+ using R = decltype(v);
+ // P1739R4: The views::take of a subrange is a subrange.
+ static_assert(std::same_as<R, ranges::subrange<random_access_iterator_wrapper<int>>>);
+ // ... but not necessarily the same specialization as the input subrange
+ static_assert(!std::same_as<R, decltype(rx)>);
+ VERIFY( ranges::equal(v, (int[]){1,2,3}) );
+ VERIFY( ranges::equal(rx | views::take(100), rx) );
+}
+
+void
+test09()
+{
+ ranges::empty_view<int> rx;
+ auto v = rx | views::take(1);
+ using R = decltype(v);
+ // P1739R4: The views::take of an empty_view is an empty_view.
+ static_assert(std::same_as<R, ranges::empty_view<int>>);
+}
+
int
main()
{
@@ -92,4 +158,9 @@ main()
test02();
test03();
test04();
+ test05();
+ test06();
+ test07();
+ test08();
+ test09();
}
--
2.25.1.291.ge68e29171c
More information about the Libstdc++
mailing list