* [PATCH 2/2] libstdc++: P1739R4 Avoid template bloat for safe_ranges in combination with ...
2020-02-20 4:53 [PATCH 1/2] libstdc++: Forward second argument of views::iota using the correct type Patrick Palka
@ 2020-02-20 4:53 ` Patrick Palka
2020-02-20 9:51 ` Jonathan Wakely
2020-02-20 9:24 ` [PATCH 1/2] libstdc++: Forward second argument of views::iota using the correct type Jonathan Wakely
1 sibling, 1 reply; 7+ messages in thread
From: Patrick Palka @ 2020-02-20 4:53 UTC (permalink / raw)
To: gcc-patches; +Cc: libstdc++, jwakely, Patrick Palka
... '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
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH 1/2] libstdc++: Forward second argument of views::iota using the correct type
@ 2020-02-20 4:53 Patrick Palka
2020-02-20 4:53 ` [PATCH 2/2] libstdc++: P1739R4 Avoid template bloat for safe_ranges in combination with Patrick Palka
2020-02-20 9:24 ` [PATCH 1/2] libstdc++: Forward second argument of views::iota using the correct type Jonathan Wakely
0 siblings, 2 replies; 7+ messages in thread
From: Patrick Palka @ 2020-02-20 4:53 UTC (permalink / raw)
To: gcc-patches; +Cc: libstdc++, jwakely, Patrick Palka
We are forwarding the second argument of views::iota using the wrong type,
causing compiling errors when calling it with a value and bound of different
types, like in the test case below.
libstdc++-v3/ChangeLog:
* include/std/ranges (views::_Iota::operator()): Forward __f using the
correct type.
* testsuite/std/ranges/access/ssize.cc (test06): Don't call views::iota
with integers of different signedness, to appease iota_view's deduction
guide.
* testsuite/std/ranges/iota/iota_view.cc: Augment test.
---
libstdc++-v3/include/std/ranges | 2 +-
.../testsuite/std/ranges/access/ssize.cc | 2 +-
.../testsuite/std/ranges/iota/iota_view.cc | 17 +++++++++++++++++
3 files changed, 19 insertions(+), 2 deletions(-)
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 7a66491f2e4..1b2bf448e9c 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -933,7 +933,7 @@ namespace views
template<typename _Tp, typename _Up>
constexpr auto
operator()(_Tp&& __e, _Up&& __f) const
- { return iota_view{std::forward<_Tp>(__e), std::forward<_Tp>(__f)}; }
+ { return iota_view{std::forward<_Tp>(__e), std::forward<_Up>(__f)}; }
};
inline constexpr _Iota iota{};
diff --git a/libstdc++-v3/testsuite/std/ranges/access/ssize.cc b/libstdc++-v3/testsuite/std/ranges/access/ssize.cc
index 5aa05be8f20..31092056c76 100644
--- a/libstdc++-v3/testsuite/std/ranges/access/ssize.cc
+++ b/libstdc++-v3/testsuite/std/ranges/access/ssize.cc
@@ -80,7 +80,7 @@ test05()
void
test06()
{
- auto i = std::views::iota(1ull, 5);
+ auto i = std::views::iota(1ull, 5u);
auto s = std::ranges::ssize(i);
using R = std::ranges::range_difference_t<decltype(i)>;
static_assert( std::same_as<decltype(s), R> );
diff --git a/libstdc++-v3/testsuite/std/ranges/iota/iota_view.cc b/libstdc++-v3/testsuite/std/ranges/iota/iota_view.cc
index 798e745d3f0..65d166fbd3b 100644
--- a/libstdc++-v3/testsuite/std/ranges/iota/iota_view.cc
+++ b/libstdc++-v3/testsuite/std/ranges/iota/iota_view.cc
@@ -61,10 +61,27 @@ test03()
VERIFY( it == v.end() );
}
+void
+test04()
+{
+ int x[] = {1,2,3};
+ auto v = std::ranges::views::iota(std::counted_iterator(x, 3),
+ std::default_sentinel);
+ auto it = v.begin();
+ VERIFY( (*it).base() == x );
+ ++it;
+ VERIFY( (*it).base() == x+1 );
+ ++it;
+ VERIFY( (*it).base() == x+2 );
+ ++it;
+ VERIFY( it == v.end() );
+}
+
int
main()
{
test01();
test02();
test03();
+ test04();
}
--
2.25.1.291.ge68e29171c
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH 1/2] libstdc++: Forward second argument of views::iota using the correct type
2020-02-20 4:53 [PATCH 1/2] libstdc++: Forward second argument of views::iota using the correct type Patrick Palka
2020-02-20 4:53 ` [PATCH 2/2] libstdc++: P1739R4 Avoid template bloat for safe_ranges in combination with Patrick Palka
@ 2020-02-20 9:24 ` Jonathan Wakely
2020-02-20 17:53 ` Patrick Palka
1 sibling, 1 reply; 7+ messages in thread
From: Jonathan Wakely @ 2020-02-20 9:24 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
On 19/02/20 23:53 -0500, Patrick Palka wrote:
>We are forwarding the second argument of views::iota using the wrong type,
>causing compiling errors when calling it with a value and bound of different
>types, like in the test case below.
Good catch, OK for master.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH 2/2] libstdc++: P1739R4 Avoid template bloat for safe_ranges in combination with ...
2020-02-20 4:53 ` [PATCH 2/2] libstdc++: P1739R4 Avoid template bloat for safe_ranges in combination with Patrick Palka
@ 2020-02-20 9:51 ` Jonathan Wakely
2020-02-20 17:35 ` Patrick Palka
0 siblings, 1 reply; 7+ messages in thread
From: Jonathan Wakely @ 2020-02-20 9:51 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
On 19/02/20 23:53 -0500, Patrick Palka wrote:
>... '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.
Please be sure to report these to the LWG chair address so issues can
be opened.
>@@ -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;
I think it should be possible to define these without including <span>
and <string_view>. Either by adding forward declarations of span and
basic_string_view, which is sufficient to define the variable template
specializations, or by defining something here and specializing it in
<span> and <string_view> e.g. in <ranges>:
template<typename _Tp>
inline constexpr bool __is_viewish = false;
And then in <span> add:
template<typename _Tp>
extern inline const bool __is_viewish;
template<typename _Tp>
inline constexpr bool __is_viewish<span<_Tp>> = true;
The first declaration is needed so that <span> works without including
<ranges>, and vice versa.
And in <string_view>:
#if __cplusplus > 201703L
template<typename _Tp>
extern inline const bool __is_viewish;
template<typename _Ch, typename _Tr>
inline constexpr bool __is_viewish<basic_string_view<_Ch, _Tr>>
= true;
#endif
That way we don't need to declare span and string_view in <ranges> at
all. We also don't need two separate variables, one will do. And
finally, doing it this way allows us to enable this feature for
experimental::basic_string_view too:
And in <experimental/string_view>:
#if __cplusplus > 201703L
template<typename _Tp>
extern inline const bool __is_viewish;
template<typename _Ch, typename _Tr>
inline constexpr bool
__is_viewish<experimental::basic_string_view<_Ch, _Tr>> = true;
#endif
This last specialization *must* be defined in
<experimental/string_view> not in <ranges>, because we don't want to
"leak" the non-reserved "experimental" name into <ranges> when the
user hasn't explicitly included a TS header.
A better name than "viewish" would be nice, but it does look like we
can use the same one for span and string_view, since you always treat
them the same.
>+
>+ 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};
Ah, this means we need to include <span> in <ranges> anyway. That's
OK, span isn't the biggest header. I'd still like to avoid including
<string_view> if possible though.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH 2/2] libstdc++: P1739R4 Avoid template bloat for safe_ranges in combination with ...
2020-02-20 9:51 ` Jonathan Wakely
@ 2020-02-20 17:35 ` Patrick Palka
0 siblings, 0 replies; 7+ messages in thread
From: Patrick Palka @ 2020-02-20 17:35 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: Patrick Palka, gcc-patches, libstdc++
On Thu, 20 Feb 2020, Jonathan Wakely wrote:
> On 19/02/20 23:53 -0500, Patrick Palka wrote:
> > ... '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.
>
> Please be sure to report these to the LWG chair address so issues can
> be opened.
Sounds good, I will report them issues probably today or tomorrow.
>
> > @@ -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;
>
> I think it should be possible to define these without including <span>
> and <string_view>. Either by adding forward declarations of span and
> basic_string_view, which is sufficient to define the variable template
> specializations, or by defining something here and specializing it in
> <span> and <string_view> e.g. in <ranges>:
>
> template<typename _Tp>
> inline constexpr bool __is_viewish = false;
>
> And then in <span> add:
>
> template<typename _Tp>
> extern inline const bool __is_viewish;
> template<typename _Tp>
> inline constexpr bool __is_viewish<span<_Tp>> = true;
>
> The first declaration is needed so that <span> works without including
> <ranges>, and vice versa.
>
> And in <string_view>:
>
> #if __cplusplus > 201703L
> template<typename _Tp>
> extern inline const bool __is_viewish;
> template<typename _Ch, typename _Tr>
> inline constexpr bool __is_viewish<basic_string_view<_Ch, _Tr>>
> = true;
> #endif
>
> That way we don't need to declare span and string_view in <ranges> at
> all. We also don't need two separate variables, one will do. And
> finally, doing it this way allows us to enable this feature for
> experimental::basic_string_view too:
>
> And in <experimental/string_view>:
>
> #if __cplusplus > 201703L
> template<typename _Tp>
> extern inline const bool __is_viewish;
> template<typename _Ch, typename _Tr>
> inline constexpr bool
> __is_viewish<experimental::basic_string_view<_Ch, _Tr>> = true;
> #endif
>
> This last specialization *must* be defined in
> <experimental/string_view> not in <ranges>, because we don't want to
> "leak" the non-reserved "experimental" name into <ranges> when the
> user hasn't explicitly included a TS header.
>
> A better name than "viewish" would be nice, but it does look like we
> can use the same one for span and string_view, since you always treat
> them the same.
Thanks for the detailed explanation. I'll update the patch to use this
design.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH 1/2] libstdc++: Forward second argument of views::iota using the correct type
2020-02-20 9:24 ` [PATCH 1/2] libstdc++: Forward second argument of views::iota using the correct type Jonathan Wakely
@ 2020-02-20 17:53 ` Patrick Palka
2020-02-20 18:40 ` Jonathan Wakely
0 siblings, 1 reply; 7+ messages in thread
From: Patrick Palka @ 2020-02-20 17:53 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: Patrick Palka, gcc-patches, libstdc++
On Thu, 20 Feb 2020, Jonathan Wakely wrote:
> On 19/02/20 23:53 -0500, Patrick Palka wrote:
> > We are forwarding the second argument of views::iota using the wrong type,
> > causing compiling errors when calling it with a value and bound of different
> > types, like in the test case below.
>
> Good catch, OK for master.
Oops, the second patch in this series includes a friendship change that
should instead be a part of this patch: iota_view::_Iterator must
befriend iota_view::_Sentinel, so that iota_view::_Sentinel::operator==
can access its private members. This is needed for the new test in
iota_view.cc to compile.
Tested on x86_64-pc-linux-gnu, does this look OK to commit?
-- >8 --
Subject: [PATCH] libstdc++: Forward second argument of views::iota using the
correct type
We are forwarding the second argument of views::iota using the wrong type,
causing compile errors when calling views::iota with a value and bound of
different types, like in the test case below.
libstdc++-v3/ChangeLog:
* include/std/ranges (iota_view): Forward declare _Sentinel.
(iota_view::_Iterator): Befriend _Sentinel.
(iota_view::_Sentinel::_M_equal): New member function.
(iota_view::_Sentinel::operator==): Use it.
(views::_Iota::operator()): Forward __f using the correct type.
* testsuite/std/ranges/access/ssize.cc (test06): Don't call views::iota
with integers of different signedness, to appease iota_view's deduction
guide.
* testsuite/std/ranges/iota/iota_view.cc: Augment test.
---
libstdc++-v3/ChangeLog | 9 +++++++++
libstdc++-v3/include/std/ranges | 12 ++++++++++--
.../testsuite/std/ranges/access/ssize.cc | 2 +-
.../testsuite/std/ranges/iota/iota_view.cc | 17 +++++++++++++++++
4 files changed, 37 insertions(+), 3 deletions(-)
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 30cf706cdae..90098fa9aa5 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,12 @@
+2020-02-20 Patrick Palka <ppalka@redhat.com>
+
+ * include/std/ranges (views::_Iota::operator()): Forward __f using the
+ correct type.
+ * testsuite/std/ranges/access/ssize.cc (test06): Don't call views::iota
+ with integers of different signedness, to appease iota_view's deduction
+ guide.
+ * testsuite/std/ranges/iota/iota_view.cc: Augment test.
+
2020-02-20 Jonathan Wakely <jwakely@redhat.com>
* include/bits/range_access.h (ranges::begin): Reject array of
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 7a66491f2e4..6358ce86f79 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -635,6 +635,8 @@ namespace ranges
class iota_view : public view_interface<iota_view<_Winc, _Bound>>
{
private:
+ struct _Sentinel;
+
struct _Iterator
{
private:
@@ -811,11 +813,17 @@ 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; }
+
_Bound _M_bound = _Bound();
public:
@@ -827,7 +835,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)
@@ -933,7 +941,7 @@ namespace views
template<typename _Tp, typename _Up>
constexpr auto
operator()(_Tp&& __e, _Up&& __f) const
- { return iota_view{std::forward<_Tp>(__e), std::forward<_Tp>(__f)}; }
+ { return iota_view{std::forward<_Tp>(__e), std::forward<_Up>(__f)}; }
};
inline constexpr _Iota iota{};
diff --git a/libstdc++-v3/testsuite/std/ranges/access/ssize.cc b/libstdc++-v3/testsuite/std/ranges/access/ssize.cc
index 6f5478e2bb1..8423654c5f7 100644
--- a/libstdc++-v3/testsuite/std/ranges/access/ssize.cc
+++ b/libstdc++-v3/testsuite/std/ranges/access/ssize.cc
@@ -75,7 +75,7 @@ test05()
void
test06()
{
- auto i = std::views::iota(1ull, 5);
+ auto i = std::views::iota(1ull, 5u);
auto s = std::ranges::ssize(i);
using R = std::ranges::range_difference_t<decltype(i)>;
static_assert( std::same_as<decltype(s), R> );
diff --git a/libstdc++-v3/testsuite/std/ranges/iota/iota_view.cc b/libstdc++-v3/testsuite/std/ranges/iota/iota_view.cc
index 798e745d3f0..65d166fbd3b 100644
--- a/libstdc++-v3/testsuite/std/ranges/iota/iota_view.cc
+++ b/libstdc++-v3/testsuite/std/ranges/iota/iota_view.cc
@@ -61,10 +61,27 @@ test03()
VERIFY( it == v.end() );
}
+void
+test04()
+{
+ int x[] = {1,2,3};
+ auto v = std::ranges::views::iota(std::counted_iterator(x, 3),
+ std::default_sentinel);
+ auto it = v.begin();
+ VERIFY( (*it).base() == x );
+ ++it;
+ VERIFY( (*it).base() == x+1 );
+ ++it;
+ VERIFY( (*it).base() == x+2 );
+ ++it;
+ VERIFY( it == v.end() );
+}
+
int
main()
{
test01();
test02();
test03();
+ test04();
}
--
2.25.1.291.ge68e29171c
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH 1/2] libstdc++: Forward second argument of views::iota using the correct type
2020-02-20 17:53 ` Patrick Palka
@ 2020-02-20 18:40 ` Jonathan Wakely
0 siblings, 0 replies; 7+ messages in thread
From: Jonathan Wakely @ 2020-02-20 18:40 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
On 20/02/20 12:52 -0500, Patrick Palka wrote:
>On Thu, 20 Feb 2020, Jonathan Wakely wrote:
>
>> On 19/02/20 23:53 -0500, Patrick Palka wrote:
>> > We are forwarding the second argument of views::iota using the wrong type,
>> > causing compiling errors when calling it with a value and bound of different
>> > types, like in the test case below.
>>
>> Good catch, OK for master.
>
>Oops, the second patch in this series includes a friendship change that
>should instead be a part of this patch: iota_view::_Iterator must
>befriend iota_view::_Sentinel, so that iota_view::_Sentinel::operator==
>can access its private members. This is needed for the new test in
>iota_view.cc to compile.
>
>Tested on x86_64-pc-linux-gnu, does this look OK to commit?
Yes, OK for master.
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2020-02-20 18:40 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-02-20 4:53 [PATCH 1/2] libstdc++: Forward second argument of views::iota using the correct type Patrick Palka
2020-02-20 4:53 ` [PATCH 2/2] libstdc++: P1739R4 Avoid template bloat for safe_ranges in combination with Patrick Palka
2020-02-20 9:51 ` Jonathan Wakely
2020-02-20 17:35 ` Patrick Palka
2020-02-20 9:24 ` [PATCH 1/2] libstdc++: Forward second argument of views::iota using the correct type Jonathan Wakely
2020-02-20 17:53 ` Patrick Palka
2020-02-20 18:40 ` Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).