On 03/02/20 21:07 -0500, Patrick Palka wrote:
This patch implements [range.adaptors]. It also includes the changes from P3280
and P3278 and P3323, without which many standard examples won't work.
The implementation is mostly dictated by the spec and there was not much room
for implementation discretion. The most interesting part that was not specified
by the spec is the design of the range adaptors and range adaptor closures,
which I tried to design in a way that minimizes boilerplate and statefulness (so
that e.g. the composition of two stateless closures is stateless).
What is left unimplemented is caching of calls to begin() in filter_view,
drop_view and reverse_view, which is required to guarantee that begin() has
amortized constant time complexity. I can implement this in a subsequent patch.
"Interesting" parts of the patch are marked with XXX comments.
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -39,6 +39,7 @@
#if __cpp_lib_concepts
#include <compare>
+#include <functional> // std::ref
Please use <bits/refwrap.h> instead. <functional> is huge.
#include <initializer_list>
#include <iterator>
#include <limits>
+
+namespace __detail
+{
+ struct _Empty { };
+} // namespace __detail
+
+namespace views
+{
+ template<typename _Callable>
+ struct _RangeAdaptorClosure;
+
+ template<typename _Callable>
+ struct _RangeAdaptor
+ {
+ protected:
+ [[no_unique_address]]
+ conditional_t<!is_default_constructible_v<_Callable>,
+ _Callable, __detail::_Empty> _M_callable;
+
+ public:
+ constexpr
+ _RangeAdaptor(const _Callable& = {})
+ requires is_default_constructible_v<_Callable>
+ { }
+
+ constexpr
+ _RangeAdaptor(_Callable __callable)
As mentioned on IRC, the non-explicit constructors here make me
nervous. I'd either like them to be explicit, or for these typesto be
in their own namespace so that there is never a reason to attempt
implicit conversions to them just because some function related to
them is found in an associated namespace.
+ requires (!is_default_constructible_v<_Callable>)
+ : _M_callable(std::move(__callable))
+ { }
+
+ template<__detail::__not_same_as<ref_view> _Tp>
+ requires convertible_to<_Tp, _Range&>
+ && requires { _S_fun(declval<_Tp>()); }
+ constexpr
+ ref_view(_Tp&& __t)
+ : _M_r(addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
This should be std-qualified to avoid ADL, and should use the internal
std::__addressof function (just to avoid the extra call from
std::addressof).
+ // XXX: the following algos are copied verbatim from ranges_algo.h to avoid a
+ // circular dependency with that header.
Ugh, that's unfortunate, but OK.
I guess we could put the body of the functions in new, unconstrained
functions, and then have the ones in <bits/ranges_algo.h> and these
call those, to reuse the implementations. But they're so small and
simple it's probably not worth it.
+ namespace __detail
+ {
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+ constexpr _Iter
+ find_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
+ {
+ while (__first != __last
+ && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
+ ++__first;
+ return __first;
+ }
+
+ template<input_range _Range, typename _Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
+ _Pred>
+ constexpr safe_iterator_t<_Range>
+ find_if(_Range&& __r, _Pred __pred, _Proj __proj = {})
+ {
+ return __detail::find_if(ranges::begin(__r), ranges::end(__r),
+ std::move(__pred), std::move(__proj));
+ }
It looks like maybe we don't need this overload.
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+ constexpr _Iter
+ find_if_not(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
+ {
+ while (__first != __last
+ && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
+ ++__first;
+ return __first;
+ }
+
+ template<input_range _Range, typename _Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
+ _Pred>
+ constexpr safe_iterator_t<_Range>
+ find_if_not(_Range&& __r, _Pred __pred, _Proj __proj = {})
+ {
+ return __detail::find_if_not(ranges::begin(__r), ranges::end(__r),
+ std::move(__pred), std::move(__proj));
+ }
Nor this one.
+ template<typename _Tp, typename _Proj = identity,
+ indirect_strict_weak_order<projected<const _Tp*, _Proj>>
+ _Comp = ranges::less>
+ constexpr const _Tp&
+ min(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {})
+ {
+ if (std::__invoke(std::move(__comp),
+ std::__invoke(__proj, __b),
+ std::__invoke(__proj, __a)))
+ return __b;
+ else
+ return __a;
+ }
+
+ template<typename _Iter1, typename _Iter2>
+ struct mismatch_result
It seems like these result types could definitely be shared (by
putting them in a new <bits/xxx> header that both include). Duplicated
function templates isn't great, but not too bad. Duplicated class
templates means additional RTTI and debuginfo gets generated. We
should definitely revisit this.
If/when we add a new <bits/ranges_concepts.h> header these kind of
thigns could be moved in there.
+ {
+ [[no_unique_address]] _Iter1 in1;
+ [[no_unique_address]] _Iter2 in2;
+
+ template<typename _IIter1, typename _IIter2>
+ requires convertible_to<const _Iter1&, _IIter1>
+ && convertible_to<const _Iter2&, _IIter2>
+ operator mismatch_result<_IIter1, _IIter2>() const &
+ {
+ return {in1, in2};
+ }
+
+ template<typename _IIter1, typename _IIter2>
+ requires convertible_to<_Iter1, _IIter1>
+ && convertible_to<_Iter2, _IIter2>
+ operator mismatch_result<_IIter1, _IIter2>() &&
+ {
+ return {std::move(in1), std::move(in2)};
+ }
Do we need these conversion operators here? They don't seem to be
needed.
+ constexpr
+ _Iterator(filter_view& __parent, iterator_t<_Vp> __current)
+ : _M_current(std::move(__current)),
+ _M_parent(addressof(__parent))
std::__addressof.
+ { }
+
+ constexpr iterator_t<_Vp>
+ base() const &
+ requires copyable<iterator_t<_Vp>>
+ { return _M_current; }
+
+ constexpr iterator_t<_Vp>
+ base() &&
+ { return std::move(_M_current); }
+
+ constexpr range_reference_t<_Vp>
+ operator*() const
+ { return *_M_current; }
+
+ constexpr iterator_t<_Vp>
+ operator->() const
+ requires __detail::__has_arrow<iterator_t<_Vp>>
+ && copyable<iterator_t<_Vp>>
+ { return _M_current; }
+
+ constexpr _Iterator&
+ operator++()
+ {
+ _M_current = __detail::find_if(std::move(++_M_current),
+ ranges::end(_M_parent->_M_base),
+ std::ref(*_M_parent->_M_pred));
+ return *this;
+ }
+
+ constexpr void
+ operator++(int)
+ { ++*this; }
+
+ constexpr _Iterator
+ operator++(int) requires forward_range<_Vp>
+ {
+ auto __tmp = *this;
+ ++*this;
+ return __tmp;
+ }
+
+ constexpr _Iterator&
+ operator--() requires bidirectional_range<_Vp>
+ {
+ do
+ --_M_current;
+ while (!invoke(*_M_parent->_M_pred, *_M_current));
This should be std::__invoke.
+ constexpr _Iterator
+ begin()
+ {
+ // XXX: we need to cache the result here as per [range.filter.view]
+ __glibcxx_assert(_M_pred.has_value());
+ return {*this, __detail::find_if(_M_base, std::ref(*_M_pred))};
If this used:
__detail::find_if(ranges:begin(_M_base),
ranges::end(_M_base), std::ref(*_M_pred))
We wouldn't need the find_if(_Range&&, ...) overload.
+ }
+ static constexpr decltype(auto)
+ __iter_move(const _Iterator& __i = {})
+ noexcept(noexcept(invoke(*__i._M_parent->_M_fun, *__i._M_current)))
std::__invoke
+ {
+ if constexpr (is_lvalue_reference_v<decltype(*__i)>)
+ return std::move(*__i);
+ else
+ return *__i;
+ }
+ constexpr decltype(auto)
+ operator*() const
+ { return invoke(*_M_parent->_M_fun, *_M_current); }
std::__invoke.
+ constexpr decltype(auto)
+ operator[](difference_type __n) const
+ requires random_access_range<_Base>
+ { return invoke(*_M_parent->_M_fun, _M_current[__n]); }
std::__invoke
+
+ friend constexpr bool
+ operator==(const _Iterator& __x, const _Iterator& __y)
+ requires equality_comparable<iterator_t<_Base>>
+ { return __x._M_current == __y._M_current; }
+
+ friend constexpr bool
+ operator<(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return __x._M_current < __y._M_current; }
+
+ friend constexpr bool
+ operator>(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return __y < __x; }
+
+ friend constexpr bool
+ operator<=(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return !(__y < __x); }
+
+ friend constexpr bool
+ operator>=(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return !(__x < __y); }
+
+#ifdef __cpp_lib_threeway_comparison
This macro is mispelled, should be three_way with an underscore.
+ friend constexpr compare_three_way_result_t<iterator_t<_Base>>
Hmm, I think this return type will be ill-formed and make the whole
class ill-formed if iterator_t<_Base> doesn't satisfy
three_way_comparable. That seems like another library issue.
We should probably just return auto for now, right?
+ operator<=>(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ && three_way_comparable<iterator_t<_Base>>
+ { return __x._M_current <=> __y._M_current; }
+#endif
+ friend constexpr bool
+ operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
+ { return __y._M_end == __x || !invoke(*__y._M_pred, *__x); }
std::__invoke
+ {
+ return take_while_view{std::forward<_Range>(__r),
std::forward<_Pred>(__p)};
+ };
+ } // namespace views
+
+ template<view _Vp>
+ class drop_view : public view_interface<drop_view<_Vp>>
+ {
+ private:
+ _Vp _M_base;
+ range_difference_t<_Vp> _M_count;
+
+ public:
+ drop_view() = default;
+
+ constexpr
+ drop_view(_Vp __base, range_difference_t<_Vp> __count)
+ : _M_base(std::move(__base)), _M_count(__count)
+ { __glibcxx_assert(__count >= 0); }
Thanks for putting these debug assertions in.
+ constexpr auto
+ begin()
+ {
+ // XXX: we need to cache the result here as per [range.drop.while.view]
+ return __detail::find_if_not(_M_base, cref(*_M_pred));
Again, this could use ranges::begin(_M_base) and ranges::end(_M_base)
to avoid one of the duplicated find_if_not overloads.
+
+ inline constexpr _RangeAdaptorClosure reverse
+ = [] <viewable_range _Range> (_Range&& __r)
+ {
+ using _Tp = remove_cvref_t<_Range>;
+ if constexpr (__detail::__is_reverse_view<_Tp>)
+ return std::forward<_Range>(__r).base();
+ else if constexpr (__detail::__is_reversible_subrange<_Tp>)
+ {
+ using _Iter = decltype(ranges::begin(__r).base());
+ if constexpr (sized_range<_Tp>)
+ return subrange<_Iter, _Iter, subrange_kind::sized>
+ (__r.end().base(), __r.begin().base(), __r.size());
+ else
+ return subrange<_Iter, _Iter, subrange_kind::unsized>
+ (__r.end().base(), __r.begin().base());
+ }
+ else
+ return reverse_view{std::forward<_Range>(__r)};
+ };
+ } // namespace views
+
+ namespace __detail
+ {
+ template<typename _Tp, size_t _Nm>
+ concept __has_tuple_element = requires(_Tp __t)
+ {
+ typename tuple_size<_Tp>::type;
+ requires _Nm < tuple_size_v<_Tp>;
+ typename tuple_element_t<_Nm, _Tp>;
+ // XXX: we applied P3323 here
+ { get<_Nm>(__t) } -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
std::get here.
+ constexpr decltype(auto)
+ operator*() const
+ { return get<_Nm>(*_M_current); }
and std::get here.
+ constexpr decltype(auto)
+ operator[](difference_type __n) const
+ requires random_access_range<_Base>
+ { return get<_Nm>(*(_M_current + __n)); }
and std::get here.
+#ifdef __cpp_lib_threeway_comparison
Misspelled macro again.
+ friend constexpr compare_three_way_result_t<iterator_t<_Base>>
Same issue with the return type.
+ operator<=>(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ && three_way_comparable<iterator_t<_Base>>
+ { return __x._M_current <=> __y._M_current; }
+#endif
+
new file mode 100644
index 00000000000..d1600544605
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/common.cc
@@ -0,0 +1,68 @@
+// Copyright (C) 2019-2020 Free Software Foundation, Inc.
Does this actually use any old code from 2019 or should it just be
2020? (Same question for some other new tests).
