[3/3] libstdc++: Implement C++20 range adaptors

Message ID	20200204020724.217468-3-ppalka@redhat.com
State	New
Headers	show Return-Path: <gcc-patches-return-518823-incoming=patchwork.ozlabs.org@gcc.gnu.org> DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; q=dns; s= default; b=NZK2kau3f+2gAyGqcuM2Pt5CeaYWvIUmtWsTpAl7ezLOxXiYvSaiv tro3tv8/Rq33fh9iSCm/p8CAL1thz3BwqbvNyRra2evcUE2AxVpFtUHKn0X9536V NHoF7YdkzGwQK5H60H5OvI1gW2tfv/YXJmVJTm7dCAL7n+zke9KhaY= Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk Sender: gcc-patches-owner@gcc.gnu.org From: Patrick Palka <ppalka@redhat.com> To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, jwakely@redhat.com, Patrick Palka <ppalka@redhat.com> Subject: [PATCH 3/3] libstdc++: Implement C++20 range adaptors Date: Mon, 3 Feb 2020 21:07:24 -0500 Message-Id: <20200204020724.217468-3-ppalka@redhat.com> In-Reply-To: <20200204020724.217468-1-ppalka@redhat.com> References: <20200204020724.217468-1-ppalka@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Series	[1/3] libstdc++: Apply the move_iterator changes described in P1207R4 \| expand [1/3] libstdc++: Apply the move_iterator changes described in P1207R4 [2/3] libstdc++: Implement C++20 constrained algorithms [3/3] libstdc++: Implement C++20 range adaptors

On Thu, 6 Feb 2020, Jonathan Wakely wrote: > 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. Fixed. > > > #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. Fixed by quarantining these classes into the namespace __adaptor. > > > + 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). Fixed, for good measure I replaced every call to addressof with 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. Yeah, I suppose not given their simplicity. > > > + 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. Fixed by removing 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. Fixed by removing this overload too. > > > + 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. In the new version of the patch this local copy of mismatch_result and made mismatch() return a pair<_Iter1, _Iter2> instead. > > > + { > > + [[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. Fixed by removing mismatch_result altogether. > > > + 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. Fixed here and everywhere else. > > > + 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. Fixed. > > > + } > > > > > + 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. Oops! It looks like it's also mispelled in the definition of iota_view earlier in this file. > > > + 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? That makes sense, fixed. > > > + 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. I've tried to add an assertion it whenever the spec explicitly listed a precondition, there weren't very many of them here. > > > + 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. Fixed. > > > > + > > + 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. Fixed here and everywhere else. > > > + 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. Fixed. > > > + friend constexpr compare_three_way_result_t<iterator_t<_Base>> > > Same issue with the return type. Fixed. > > > + 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). Fixed here and in the other tests. Here's an updated patch that fixes all of the above and adds a missing piece of the ranges header that was present at the end of its synopsis in the spec. It also makes some minor formatting fixes and fixes some accidental deviations from the spec. Incremental changes can be seen at https://gcc.gnu.org/git/gitweb.cgi?p=gcc.git;a=shortlog;h=refs/users/ppalka/heads/libstdcxx-constrained-algos-adaptors -- >8 -- libstdc++-v3/ChangeLog: Implement C++20 range adaptors * include/std/ranges: Include <functional>. (subrange::_S_store_size): Mark as const instead of constexpr to avoid what seems to be a bug in GCC. (__detail::__box): Give it defaulted copy and move constructors. (ranges::views::_Single::operator()): Mark constexpr. (ranges::views::_Iota::operator()): Mark constexpr. (__detail::Empty): Define. (ranges::views::__closure::_RangeAdaptor, ranges::views::__closure::_RangeAdaptorClosure, ref_view, all_view, ranges::views::all, ranges::__detail::find_if, ranges::__detail::find_if_not, ranges::__detail::mismatch, ranges::detail::min, filter_view, ranges::views::filter, transform_view, ranges::views::transform, take_view, ranges::views::take, take_while_view, ranges::views::take_while, drop_view, ranges::views::drop, join_view, ranges::views::join, __detail::require_constant, __detail::tiny_range, split_view, ranges::views::split, ranges::views::_Counted, ranges::views::counted, common_view, ranges::views::common, reverse_view, ranges::views::reverse, ranges::views::__detail::__is_reversible_subrange, ranges::views::__detail::__is_reverse_view, reverse_view, ranges::views::reverse, __detail::__has_tuple_element, elements_view, ranges::views::elements, ranges::views::keys, ranges::views::values): Define. (views): Alias for ranges::views. (tuple_size<ranges::subrange<>>, tuple_element<0, ranges::subrange, tuple_element<1, ranges::subrange): New partial specializations. * testsuite/std/ranges/adaptors/all.cc: New test. * testsuite/std/ranges/adaptors/common.cc: Likewise. * testsuite/std/ranges/adaptors/counted.cc: Likewise. * testsuite/std/ranges/adaptors/drop.cc: Likewise. * testsuite/std/ranges/adaptors/drop_while.cc: Likewise. * testsuite/std/ranges/adaptors/elements.cc: Likewise. * testsuite/std/ranges/adaptors/filter.cc: Likewise. * testsuite/std/ranges/adaptors/join.cc: Likewise. * testsuite/std/ranges/adaptors/reverse.cc: Likewise. * testsuite/std/ranges/adaptors/split.cc: Likewise. * testsuite/std/ranges/adaptors/take.cc: Likewise. * testsuite/std/ranges/adaptors/take_while.cc: Likewise. * testsuite/std/ranges/adaptors/transform.cc: Likewise. --- libstdc++-v3/include/std/ranges | 2405 +++++++++++++++++++- libstdc++-v3/testsuite/std/ranges/adaptors/all.cc | 122 + .../testsuite/std/ranges/adaptors/common.cc | 68 + .../testsuite/std/ranges/adaptors/counted.cc | 64 + libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc | 107 + .../testsuite/std/ranges/adaptors/drop_while.cc | 63 + .../testsuite/std/ranges/adaptors/elements.cc | 52 + .../testsuite/std/ranges/adaptors/filter.cc | 97 + libstdc++-v3/testsuite/std/ranges/adaptors/join.cc | 112 + .../testsuite/std/ranges/adaptors/reverse.cc | 86 + .../testsuite/std/ranges/adaptors/split.cc | 82 + libstdc++-v3/testsuite/std/ranges/adaptors/take.cc | 95 + .../testsuite/std/ranges/adaptors/take_while.cc | 62 + .../testsuite/std/ranges/adaptors/transform.cc | 86 + 14 files changed, 3496 insertions(+), 5 deletions(-) diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 860f7283be5..8a8fefb6f19 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -38,11 +38,13 @@ #if __cpp_lib_concepts +#include <bits/refwrap.h> #include <compare> #include <initializer_list> #include <iterator> #include <limits> #include <optional> +#include <tuple> /** * @defgroup ranges Ranges @@ -255,7 +257,8 @@ namespace ranges class subrange : public view_interface<subrange<_It, _Sent, _Kind>> { private: - static constexpr bool _S_store_size + // XXX: gcc complains when using constexpr here + static const bool _S_store_size = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>; _It _M_begin = _It(); @@ -507,6 +510,9 @@ namespace ranges : std::optional<_Tp>{std::in_place} { } + __box(const __box&) = default; + __box(__box&&) = default; + using std::optional<_Tp>::operator=; __box& @@ -922,7 +928,7 @@ namespace views struct _Single { template<typename _Tp> - auto + constexpr auto operator()(_Tp&& __e) const { return single_view{std::forward<_Tp>(__e)}; } }; @@ -932,20 +938,2409 @@ namespace views struct _Iota { template<typename _Tp> - auto + constexpr auto operator()(_Tp&& __e) const { return iota_view{std::forward<_Tp>(__e)}; } template<typename _Tp, typename _Up> - auto + constexpr auto operator()(_Tp&& __e, _Up&& __f) const { return iota_view{std::forward<_Tp>(__e), std::forward<_Tp>(__f)}; } }; inline constexpr _Iota iota{}; +} // namespace views + +namespace __detail +{ + struct _Empty { }; +} // namespace __detail + +namespace views +{ + namespace __adaptor + { + 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) + requires (!is_default_constructible_v<_Callable>) + : _M_callable(std::move(__callable)) + { } + + template<typename... _Args> + requires (sizeof...(_Args) >= 1) + constexpr auto + operator()(_Args&&... __args) const + { + if constexpr (is_invocable_v<_Callable, _Args...>) + { + static_assert(sizeof...(_Args) != 1, + "a _RangeAdaptor that accepts only one argument " + "should be defined as a _RangeAdaptorClosure"); + return _Callable{}(std::forward<_Args>(__args)...); + } + else + { + auto __closure = [__args...] <typename _Range> (_Range&& __r) { + return _Callable{}(std::forward<_Range>(__r), __args...); + }; + using _ClosureType = decltype(__closure); + return _RangeAdaptorClosure<_ClosureType>(std::move(__closure)); + } + } + }; + + template<typename _Callable> + struct _RangeAdaptorClosure : public _RangeAdaptor<_Callable> + { + using _RangeAdaptor<_Callable>::_RangeAdaptor; + + template<viewable_range _Range> + requires requires { declval<_Callable>()(declval<_Range>()); } + constexpr auto + operator()(_Range&& __r) const + { + if constexpr (is_default_constructible_v<_Callable>) + return _Callable{}(std::forward<_Range>(__r)); + else + return this->_M_callable(std::forward<_Range>(__r)); + } + + template<viewable_range _Range> + requires requires { declval<_Callable>()(declval<_Range>()); } + friend constexpr auto + operator|(_Range&& __r, const _RangeAdaptorClosure& __o) + { return __o(std::forward<_Range>(__r)); } + template<typename _Tp> + friend constexpr auto + operator|(const _RangeAdaptorClosure<_Tp>& __x, + const _RangeAdaptorClosure& __y) + { + if constexpr (is_default_constructible_v<_Tp> + && is_default_constructible_v<_Callable>) + { + auto __closure = [] <typename _Up> (_Up&& __e) { + return std::forward<_Up>(__e) | decltype(__x){} | decltype(__y){}; + }; + return _RangeAdaptorClosure<decltype(__closure)>(__closure); + } + else if constexpr (is_default_constructible_v<_Tp> + && !is_default_constructible_v<_Callable>) + { + auto __closure = [__y] <typename _Up> (_Up&& __e) { + return std::forward<_Up>(__e) | decltype(__x){} | __y; + }; + return _RangeAdaptorClosure<decltype(__closure)>(__closure); + } + else if constexpr (!is_default_constructible_v<_Tp> + && is_default_constructible_v<_Callable>) + { + auto __closure = [__x] <typename _Up> (_Up&& __e) { + return std::forward<_Up>(__e) | __x | decltype(__y){}; + }; + return _RangeAdaptorClosure<decltype(__closure)>(__closure); + } + else + { + auto __closure = [__x, __y] <typename _Up> (_Up&& __e) { + return std::forward<_Up>(__e) | __x | __y; + }; + return _RangeAdaptorClosure<decltype(__closure)>(__closure); + } + } + }; + + template<typename _Callable> + _RangeAdaptorClosure(_Callable) -> _RangeAdaptorClosure<_Callable>; + } // namespace __adaptor } // namespace views -} // namespace ranges + + template<range _Range> requires is_object_v<_Range> + class ref_view : public view_interface<ref_view<_Range>> + { + private: + _Range* _M_r = nullptr; + + static void _S_fun(_Range&); // not defined + static void _S_fun(_Range&&) = delete; + + public: + constexpr + ref_view() noexcept = default; + + 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(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t)))) + { } + + constexpr _Range& + base() const + { return *_M_r; } + + constexpr iterator_t<_Range> + begin() const + { return ranges::begin(*_M_r); } + + constexpr sentinel_t<_Range> + end() const + { return ranges::end(*_M_r); } + + constexpr bool + empty() const requires requires { ranges::empty(*_M_r); } + { return ranges::empty(*_M_r); } + + constexpr auto + size() const requires sized_range<_Range> + { return ranges::size(*_M_r); } + + constexpr auto + data() const requires contiguous_range<_Range> + { return ranges::data(*_M_r); } + }; + + template<typename _Range> + ref_view(_Range&) -> ref_view<_Range>; + + template<typename _Tp> + inline constexpr bool enable_safe_range<ref_view<_Tp>> = true; + + namespace views + { + inline constexpr __adaptor::_RangeAdaptorClosure all + = [] <viewable_range _Range> (_Range&& __r) + { + if constexpr (view<decay_t<_Range>>) + return std::forward<_Range>(__r); + else if constexpr (requires { ref_view{std::forward<_Range>(__r)}; }) + return ref_view{std::forward<_Range>(__r)}; + else + return subrange{std::forward<_Range>(__r)}; + }; + } // namespace views + + template<viewable_range _Range> + using all_view = decltype(views::all(declval<_Range>())); + + // XXX: the following algos are copied from ranges_algo.h to avoid a circular + // dependency with that header. + 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_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<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<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, + input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + typename _Pred = ranges::equal_to, + typename _Proj1 = identity, typename _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + constexpr pair<_Iter1, _Iter2> + mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) + { + while (__first1 != __last1 && __first2 != __last2 + && (bool)std::__invoke(__pred, + std::__invoke(__proj1, *__first1), + std::__invoke(__proj2, *__first2))) + { + ++__first1; + ++__first2; + } + return { std::move(__first1), std::move(__first2) }; + } + } // namespace __detail + + template<input_range _Vp, + indirect_unary_predicate<iterator_t<_Vp>> _Pred> + requires view<_Vp> && is_object_v<_Pred> + class filter_view : public view_interface<filter_view<_Vp, _Pred>> + { + private: + struct _Sentinel; + + struct _Iterator + { + private: + static constexpr auto + _S_iter_concept() + { + if constexpr (bidirectional_range<_Vp>) + return bidirectional_iterator_tag{}; + else if constexpr (forward_range<_Vp>) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + + static constexpr auto + _S_iter_cat() + { + using _Cat = iterator_traits<iterator_t<_Vp>>::iterator_category; + if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) + return bidirectional_iterator_tag{}; + else if constexpr (derived_from<_Cat, forward_iterator_tag>) + return forward_iterator_tag{}; + else + return _Cat{}; + } + + friend filter_view; + + iterator_t<_Vp> _M_current = iterator_t<_Vp>(); + filter_view* _M_parent = nullptr; + + public: + using iterator_concept = decltype(_S_iter_concept()); + using iterator_category = decltype(_S_iter_cat()); + using value_type = range_value_t<_Vp>; + using difference_type = range_difference_t<_Vp>; + + _Iterator() = default; + + constexpr + _Iterator(filter_view& __parent, iterator_t<_Vp> __current) + : _M_current(std::move(__current)), + _M_parent(std::__addressof(__parent)) + { } + + 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 (!std::__invoke(*_M_parent->_M_pred, *_M_current)); + return *this; + } + + constexpr _Iterator + operator--(int) requires bidirectional_range<_Vp> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + requires equality_comparable<iterator_t<_Vp>> + { return __x._M_current == __y._M_current; } + + friend constexpr range_rvalue_reference_t<_Vp> + iter_move(const _Iterator& __i) + noexcept(noexcept(ranges::iter_move(__i._M_current))) + { return ranges::iter_move(__i._M_current); } + + friend constexpr void + iter_swap(const _Iterator& __x, const _Iterator& __y) + noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current))) + requires indirectly_swappable<iterator_t<_Vp>> + { ranges::iter_swap(__x._M_current, __y._M_current); } + }; + + struct _Sentinel + { + private: + sentinel_t<_Vp> _M_end = sentinel_t<_Vp>(); + + constexpr bool + __equal(const _Iterator& __i) const + { return __i._M_current == _M_end; } + + public: + _Sentinel() = default; + + constexpr explicit + _Sentinel(filter_view& __parent) + : _M_end(ranges::end(__parent._M_base)) + { } + + constexpr sentinel_t<_Vp> + base() const + { return _M_end; } + + friend constexpr bool + operator==(const _Iterator& __x, const _Sentinel& __y) + { return __y.__equal(__x); } + }; + + _Vp _M_base = _Vp(); + __detail::__box<_Pred> _M_pred; + + public: + filter_view() = default; + + constexpr + filter_view(_Vp __base, _Pred __pred) + : _M_base(std::move(__base)), _M_pred(std::move(__pred)) + { } + + /* XXX: P3280 removes this constructor + template<input_range _Range> + requires viewable_range<_Range> + && constructible_from<_Vp, all_view<_Range>> + constexpr + filter_view(_Range&& __r, _Pred __pred) + : _M_base(views::all(std::forward<_Range>(__r))), + _M_pred(std::move(__pred)) + { } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + 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(ranges::begin(_M_base), + ranges::end(_M_base), + std::ref(*_M_pred))}; + } + + constexpr auto + end() + { + if constexpr (common_range<_Vp>) + return _Iterator{*this, ranges::end(_M_base)}; + else + return _Sentinel{*this}; + } + }; + + template<typename _Range, typename _Pred> + filter_view(_Range&&, _Pred) -> filter_view<all_view<_Range>, _Pred>; + + namespace views + { + inline constexpr __adaptor::_RangeAdaptor filter + = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p) + { + return filter_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)}; + }; + } // namespace views + + template<input_range _Vp, copy_constructible _Fp> + requires view<_Vp> && is_object_v<_Fp> + && regular_invocable<_Fp&, range_reference_t<_Vp>> + class transform_view : public view_interface<transform_view<_Vp, _Fp>> + { + private: + template<bool _Const> + struct _Sentinel; + + template<bool _Const> + struct _Iterator + { + private: + using _Parent + = conditional_t<_Const, const transform_view, transform_view>; + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + static constexpr auto + _S_iter_concept() + { + if constexpr (random_access_range<_Vp>) + return random_access_iterator_tag{}; + else if constexpr (bidirectional_range<_Vp>) + return bidirectional_iterator_tag{}; + else if constexpr (forward_range<_Vp>) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + + static constexpr auto + _S_iter_cat() + { + using _Cat = iterator_traits<iterator_t<_Base>>::iterator_category; + if constexpr (derived_from<_Cat, contiguous_iterator_tag>) + return random_access_iterator_tag{}; + else + return _Cat{}; + } + + static constexpr decltype(auto) + __iter_move(const _Iterator& __i = {}) + noexcept(noexcept(std::__invoke(*__i._M_parent->_M_fun, + *__i._M_current))) + { + if constexpr (is_lvalue_reference_v<decltype(*__i)>) + return std::move(*__i); + else + return *__i; + } + + iterator_t<_Base> _M_current = iterator_t<_Base>(); + _Parent* _M_parent = nullptr; + + public: + using iterator_concept = decltype(_S_iter_concept()); + using iterator_category = decltype(_S_iter_cat()); + using value_type + = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>; + using difference_type = range_difference_t<_Base>; + + _Iterator() = default; + + constexpr + _Iterator(_Parent& __parent, iterator_t<_Base> __current) + : _M_current(std::move(__current)), + _M_parent(std::__addressof(__parent)) + { } + + constexpr + _Iterator(_Iterator<!_Const> __i) + requires _Const + && convertible_to<iterator_t<_Vp>, iterator_t<_Base>> + : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent) + { } + + constexpr iterator_t<_Base> + base() const & + requires copyable<iterator_t<_Base>> + { return _M_current; } + + constexpr iterator_t<_Base> + base() && + { return std::move(_M_current); } + + constexpr decltype(auto) + operator*() const + { return std::__invoke(*_M_parent->_M_fun, *_M_current); } + + constexpr _Iterator& + operator++() + { + ++_M_current; + return *this; + } + + constexpr void + operator++(int) + { ++_M_current; } + + constexpr _Iterator + operator++(int) requires forward_range<_Base> + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() requires bidirectional_range<_Base> + { + --_M_current; + return *this; + } + + constexpr _Iterator + operator--(int) requires bidirectional_range<_Base> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + constexpr _Iterator& + operator+=(difference_type __n) requires random_access_range<_Base> + { + _M_current += __n; + return *this; + } + + constexpr _Iterator& + operator-=(difference_type __n) requires random_access_range<_Base> + { + _M_current -= __n; + return *this; + } + + constexpr decltype(auto) + operator[](difference_type __n) const + requires random_access_range<_Base> + { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); } + + 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_three_way_comparison + friend constexpr auto + 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 _Iterator + operator+(_Iterator __i, difference_type __n) + requires random_access_range<_Base> + { return {*__i._M_parent, __i._M_current + __n}; } + + friend constexpr _Iterator + operator+(difference_type __n, _Iterator __i) + requires random_access_range<_Base> + { return {*__i._M_parent, __i._M_current + __n}; } + + friend constexpr _Iterator + operator-(_Iterator __i, difference_type __n) + requires random_access_range<_Base> + { return {*__i._M_parent, __i._M_current - __n}; } + + friend constexpr difference_type + operator-(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __x._M_current - __y._M_current; } + + friend constexpr decltype(auto) + iter_move(const _Iterator& __i) noexcept(noexcept(__iter_move())) + { return __iter_move(__i); } + + friend constexpr void + iter_swap(const _Iterator& __x, const _Iterator& __y) + noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current))) + requires indirectly_swappable<iterator_t<_Base>> + { return ranges::iter_swap(__x._M_current, __y._M_current); } + + friend _Sentinel<_Const>; + }; + + template<bool _Const> + struct _Sentinel + { + private: + using _Parent + = conditional_t<_Const, const transform_view, transform_view>; + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + constexpr range_difference_t<_Base> + __distance_from(const _Iterator<_Const>& __i) const + { return _M_end - __i._M_current; } + + constexpr bool + __equal(const _Iterator<_Const>& __i) const + { return __i._M_current == _M_end; } + + sentinel_t<_Base> _M_end = sentinel_t<_Base>(); + + public: + _Sentinel() = default; + + constexpr explicit + _Sentinel(sentinel_t<_Base> __end) + : _M_end(__end) + { } + + constexpr + _Sentinel(_Sentinel<!_Const> __i) + requires _Const + && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> + : _M_end(std::move(__i._M_end)) + { } + + constexpr sentinel_t<_Base> + base() const + { return _M_end; } + + friend constexpr bool + operator==(const _Iterator<_Const>& __x, const _Sentinel& __y) + { return __y.__equal(__x); } + + friend constexpr range_difference_t<_Base> + operator-(const _Iterator<_Const>& __x, const _Sentinel& __y) + requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>> + { return -__y.__distance_from(__x); } + + friend constexpr range_difference_t<_Base> + operator-(const _Sentinel& __y, const _Iterator<_Const>& __x) + requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>> + { return __y.__distance_from(__x); } + }; + + _Vp _M_base = _Vp(); + __detail::__box<_Fp> _M_fun; + + public: + transform_view() = default; + + constexpr + transform_view(_Vp __base, _Fp __fun) + : _M_base(std::move(__base)), _M_fun(std::move(__fun)) + { } + + /* XXX: P3280 removes this constructor + template<input_range _Range> + requires viewable_range<_Range> + && constructible_from<_Vp, all_view<_Range>> + constexpr + transform_view(_Range&& __r, _Fp __fun) + : _M_base(views::all(std::forward<_Range>(__r))) + { + } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base ; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr _Iterator<false> + begin() + { return _Iterator<false>{*this, ranges::begin(_M_base)}; } + + constexpr _Iterator<true> + begin() const + requires range<const _Vp> + && regular_invocable<const _Fp&, range_reference_t<const _Vp>> + { return _Iterator<true>{*this, ranges::begin(_M_base)}; } + + constexpr _Sentinel<false> + end() + { return _Sentinel<false>{ranges::end(_M_base)}; } + + constexpr _Iterator<false> + end() requires common_range<_Vp> + { return _Iterator<false>{*this, ranges::end(_M_base)}; } + + constexpr _Sentinel<true> + end() const + requires range<const _Vp> + && regular_invocable<const _Fp&, range_reference_t<const _Vp>> + { return _Sentinel<true>{ranges::end(_M_base)}; } + + constexpr _Iterator<true> + end() const + requires common_range<const _Vp> + && regular_invocable<const _Fp&, range_reference_t<const _Vp>> + { return _Iterator<true>{*this, ranges::end(_M_base)}; } + + constexpr auto + size() requires sized_range<_Vp> + { return ranges::size(_M_base); } + + constexpr auto + size() const requires sized_range<const _Vp> + { return ranges::size(_M_base); } + }; + + template<typename _Range, typename _Fp> + transform_view(_Range&&, _Fp) -> transform_view<all_view<_Range>, _Fp>; + + namespace views + { + inline constexpr __adaptor::_RangeAdaptor transform + = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f) + { + return transform_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)}; + }; + } // namespace views + + template<view _Vp> + class take_view : public view_interface<take_view<_Vp>> + { + private: + template<bool _Const> + struct _Sentinel + { + private: + using _Base = conditional_t<_Const, const _Vp, _Vp>; + using _CI = counted_iterator<iterator_t<_Base>>; + + sentinel_t<_Base> _M_end = sentinel_t<_Base>(); + + public: + _Sentinel() = default; + + constexpr explicit + _Sentinel(sentinel_t<_Base> __end) + : _M_end(__end) + { } + + constexpr + _Sentinel(_Sentinel<!_Const> __s) + requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> + : _M_end(std::move(__s._M_end)) + { } + + constexpr sentinel_t<_Base> + base() const + { return _M_end; } + + friend constexpr bool operator==(const _CI& __y, const _Sentinel& __x) + { return __y.count() == 0 || __y.base() == __x._M_end; } + }; + + _Vp _M_base = _Vp(); + range_difference_t<_Vp> _M_count = 0; + + public: + take_view() = default; + + constexpr + take_view(_Vp base, range_difference_t<_Vp> __count) + : _M_base(std::move(base)), _M_count(std::move(__count)) + { } + + /* XXX: P3280 removes this constructor + template<viewable_range _Range> + requires constructible_from<_Vp, all_view<_Range>> + constexpr + take_view(_Range&& __r, range_difference_t<_Vp> __count) + : _M_base(views::all(std::forward<_Range>(__r))), _M_count(__count) + { } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() requires (!__detail::__simple_view<_Vp>) + { + if constexpr (sized_range<_Vp>) + { + if constexpr (random_access_range<_Vp>) + return ranges::begin(_M_base); + else + return counted_iterator{ranges::begin(_M_base), size()}; + } + else + return counted_iterator{ranges::begin(_M_base), _M_count}; + } + + constexpr auto + begin() const requires range<const _Vp> + { + if constexpr (sized_range<const _Vp>) + { + if constexpr (random_access_range<const _Vp>) + return ranges::begin(_M_base); + else + return counted_iterator{ranges::begin(_M_base), size()}; + } + else + return counted_iterator{ranges::begin(_M_base), _M_count}; + } + + constexpr auto + end() requires (!__detail::__simple_view<_Vp>) + { + if constexpr (sized_range<_Vp>) + { + if constexpr (random_access_range<_Vp>) + return ranges::begin(_M_base) + size(); + else + return default_sentinel; + } + else + return _Sentinel<false>{ranges::end(_M_base)}; + } + + constexpr auto + end() const requires range<const _Vp> + { + if constexpr (sized_range<const _Vp>) + { + if constexpr (random_access_range<const _Vp>) + return ranges::begin(_M_base) + size(); + else + return default_sentinel; + } + else + return _Sentinel<true>{ranges::end(_M_base)}; + } + + constexpr auto + size() requires sized_range<_Vp> + { + auto __n = ranges::size(_M_base); + return __detail::min(__n, static_cast<decltype(__n)>(_M_count)); + } + + constexpr auto + size() const requires sized_range<const _Vp> + { + auto __n = ranges::size(_M_base); + return __detail::min(__n, static_cast<decltype(__n)>(_M_count)); + } + }; + + template<range _Range> + take_view(_Range&&, range_difference_t<_Range>) + -> take_view<all_view<_Range>>; + + namespace views + { + inline constexpr __adaptor::_RangeAdaptor take + = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n) + { + return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)}; + }; + } // namespace views + + template<view _Vp, typename _Pred> + requires input_range<_Vp> && is_object_v<_Pred> + && indirect_unary_predicate<const _Pred, iterator_t<_Vp>> + class take_while_view : public view_interface<take_while_view<_Vp, _Pred>> + { + template<bool _Const> + struct _Sentinel + { + private: + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + sentinel_t<_Base> _M_end = sentinel_t<_Base>(); + const _Pred* _M_pred = nullptr; + + public: + _Sentinel() = default; + + constexpr explicit + _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred) + : _M_end(__end), _M_pred(__pred) + { } + + constexpr + _Sentinel(_Sentinel<!_Const> __s) + requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> + : _M_end(__s._M_end), _M_pred(__s._M_pred) + { } + + constexpr sentinel_t<_Base> + base() const { return _M_end; } + + friend constexpr bool + operator==(const iterator_t<_Base>& __x, const _Sentinel& __y) + { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); } + }; + + _Vp _M_base; + __detail::__box<_Pred> _M_pred; + + public: + take_while_view() = default; + + constexpr + take_while_view(_Vp base, _Pred __pred) + : _M_base(std::move(base)), _M_pred(std::move(__pred)) + { + } + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr const _Pred& + pred() const + { return *_M_pred; } + + constexpr auto + begin() requires (!__detail::__simple_view<_Vp>) + { return ranges::begin(_M_base); } + + constexpr auto + begin() const requires range<const _Vp> + { return ranges::begin(_M_base); } + + constexpr auto + end() requires (!__detail::__simple_view<_Vp>) + { return _Sentinel<false>(ranges::end(_M_base), + std::__addressof(*_M_pred)); } + + constexpr auto + end() const requires range<const _Vp> + { return _Sentinel<true>(ranges::end(_M_base), + std::__addressof(*_M_pred)); } + }; + + template<typename _Range, typename _Pred> + take_while_view(_Range&&, _Pred) + -> take_while_view<all_view<_Range>, _Pred>; + + namespace views + { + inline constexpr __adaptor::_RangeAdaptor take_while + = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p) + { + 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); } + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() requires (!(__detail::__simple_view<_Vp> + && random_access_range<_Vp>)) + { + // XXX: we need to cache the result here as per [range.drop.view] + return ranges::next(ranges::begin(_M_base), _M_count, + ranges::end(_M_base)); + } + + constexpr auto + begin() const requires random_access_range<const _Vp> + { + return ranges::next(ranges::begin(_M_base), _M_count, + ranges::end(_M_base)); + } + + constexpr auto + end() requires (!__detail::__simple_view<_Vp>) + { return ranges::end(_M_base); } + + constexpr auto + end() const requires range<const _Vp> + { return ranges::end(_M_base); } + + constexpr auto + size() requires sized_range<_Vp> + { + const auto __s = ranges::size(_M_base); + const auto __c = static_cast<decltype(__s)>(_M_count); + return __s < __c ? 0 : __s - __c; + } + + constexpr auto + size() const requires sized_range<const _Vp> + { + const auto __s = ranges::size(_M_base); + const auto __c = static_cast<decltype(__s)>(_M_count); + return __s < __c ? 0 : __s - __c; + } + }; + + template<typename _Range> + drop_view(_Range&&, range_difference_t<_Range>) + -> drop_view<all_view<_Range>>; + + namespace views + { + inline constexpr __adaptor::_RangeAdaptor drop + = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n) + { + return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)}; + }; + } // namespace views + + template<view _Vp, typename _Pred> + requires input_range<_Vp> && is_object_v<_Pred> + && indirect_unary_predicate<const _Pred, iterator_t<_Vp>> + class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>> + { + private: + _Vp _M_base; + __detail::__box<_Pred> _M_pred; + + public: + drop_while_view() = default; + + constexpr + drop_while_view(_Vp __base, _Pred __pred) + : _M_base(std::move(__base)), _M_pred(std::move(__pred)) + { } + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr const _Pred& + pred() const + { return *_M_pred; } + + constexpr auto + begin() + { + // XXX: we need to cache the result here as per [range.drop.while.view] + return __detail::find_if_not(ranges::begin(_M_base), + ranges::end(_M_base), + std::cref(*_M_pred)); + } + + constexpr auto + end() + { return ranges::end(_M_base); } + }; + + template<typename _Range, typename _Pred> + drop_while_view(_Range&&, _Pred) + -> drop_while_view<all_view<_Range>, _Pred>; + + namespace views + { + inline constexpr __adaptor::_RangeAdaptor drop_while + = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p) + { + return drop_while_view{std::forward<_Range>(__r), + std::forward<_Pred>(__p)}; + }; + } // namespace views + + template<input_range _Vp> + requires view<_Vp> && input_range<range_reference_t<_Vp>> + && (is_reference_v<range_reference_t<_Vp>> + || view<range_value_t<_Vp>>) + class join_view : public view_interface<join_view<_Vp>> + { + private: + using _InnerRange = range_reference_t<_Vp>; + + template<bool _Const> + struct _Sentinel; + + template<bool _Const> + struct _Iterator + { + private: + using _Parent = conditional_t<_Const, const join_view, join_view>; + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + static constexpr bool _S_ref_is_glvalue + = is_reference_v<range_reference_t<_Base>>; + + constexpr void + _M_satisfy() + { + auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto& + { + if constexpr (_S_ref_is_glvalue) + return __x; + else + return (_M_parent->_M_inner = views::all(std::move(__x))); + }; + + for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer) + { + auto& inner = __update_inner(*_M_outer); + _M_inner = ranges::begin(inner); + if (_M_inner != ranges::end(inner)) + return; + } + + if constexpr (_S_ref_is_glvalue) + _M_inner = iterator_t<range_reference_t<_Base>>(); + } + + static constexpr auto + _S_iter_concept() + { + if constexpr (_S_ref_is_glvalue + && bidirectional_range<_Base> + && bidirectional_range<range_reference_t<_Base>>) + return bidirectional_iterator_tag{}; + else if constexpr (_S_ref_is_glvalue + && forward_range<_Base> + && forward_range<range_reference_t<_Base>>) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + + static constexpr auto + _S_iter_cat() + { + using _OuterCat + = iterator_traits<iterator_t<_Base>>::iterator_category; + using _InnerCat + = iterator_traits<iterator_t<range_reference_t<_Base>>> + ::iterator_category; + if constexpr (_S_ref_is_glvalue + && derived_from<_OuterCat, bidirectional_iterator_tag> + && derived_from<_InnerCat, bidirectional_iterator_tag>) + return bidirectional_iterator_tag{}; + else if constexpr (_S_ref_is_glvalue + && derived_from<_OuterCat, forward_iterator_tag> + && derived_from<_InnerCat, forward_iterator_tag>) + return forward_iterator_tag{}; + else if constexpr (derived_from<_OuterCat, input_iterator_tag> + && derived_from<_InnerCat, input_iterator_tag>) + return input_iterator_tag{}; + else + return output_iterator_tag{}; + } + + iterator_t<_Base> _M_outer = iterator_t<_Base>(); + iterator_t<range_reference_t<_Base>> _M_inner + = iterator_t<range_reference_t<_Base>>(); + _Parent* _M_parent = nullptr; + + public: + using iterator_concept = decltype(_S_iter_concept()); + using iterator_category = decltype(_S_iter_cat()); + using value_type = range_value_t<range_reference_t<_Base>>; + using difference_type + = common_type_t<range_difference_t<_Base>, + range_difference_t<range_reference_t<_Base>>>; + + _Iterator() = default; + + // XXX: had to change the type of __outer from iterator_t<_Vp> to + // iterator_t<_Base> here, a possible defect in the spec? + constexpr + _Iterator(_Parent& __parent, iterator_t<_Base> __outer) + : _M_outer(std::move(__outer)), + _M_parent(std::__addressof(__parent)) + { _M_satisfy(); } + + constexpr + _Iterator(_Iterator<!_Const> __i) + requires _Const + && convertible_to<iterator_t<_Vp>, iterator_t<_Base>> + && convertible_to<iterator_t<_InnerRange>, + iterator_t<range_reference_t<_Base>>> + : _M_outer(std::move(__i._M_outer)), _M_inner(__i._M_inner), + _M_parent(__i._M_parent) + { } + + constexpr decltype(auto) + operator*() const + { return *_M_inner; } + + constexpr iterator_t<_Base> + operator->() const + requires __detail::__has_arrow<iterator_t<_Base>> + && copyable<iterator_t<_Base>> + { return _M_inner; } + + constexpr _Iterator& + operator++() + { + auto&& __inner_range = [this] () -> decltype(auto) { + if constexpr (_S_ref_is_glvalue) + return *_M_outer; + else + return _M_parent->_M_inner; + }(); + if (++_M_inner == ranges::end(__inner_range)) + { + ++_M_outer; + _M_satisfy(); + } + return *this; + } + + constexpr void + operator++(int) + { ++*this; } + + constexpr _Iterator + operator++(int) + requires _S_ref_is_glvalue && forward_range<_Base> + && forward_range<range_reference_t<_Base>> + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() + requires _S_ref_is_glvalue && bidirectional_range<_Base> + && bidirectional_range<range_reference_t<_Base>> + { + if (_M_outer == ranges::end(_M_parent->_M_base)) + _M_inner = ranges::end(*--_M_outer); + while (_M_inner == ranges::begin(*_M_outer)) + _M_inner = ranges::end(*--_M_outer); + --_M_inner; + return *this; + } + + constexpr _Iterator + operator--(int) + requires _S_ref_is_glvalue && bidirectional_range<_Base> + && bidirectional_range<range_reference_t<_Base>> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + requires _S_ref_is_glvalue + && equality_comparable<iterator_t<_Base>> + && equality_comparable<iterator_t<range_reference_t<_Base>>> + { + return (__x._M_outer == __y._M_outer + && __x._M_inner == __y._M_inner); + } + + friend constexpr decltype(auto) + iter_move(const _Iterator& __i) + noexcept(noexcept(ranges::iter_move(__i._M_inner))) + { return ranges::iter_move(__i._M_inner); } + + friend constexpr void + iter_swap(const _Iterator& __x, const _Iterator& __y) + noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner))) + { return ranges::iter_swap(__x._M_inner, __y._M_inner); } + + friend _Sentinel<_Const>; + }; + + template<bool _Const> + struct _Sentinel + { + private: + using _Parent = conditional_t<_Const, const join_view, join_view>; + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + constexpr bool + __equal(const _Iterator<_Const>& __i) const + { return __i._M_outer == _M_end; } + + sentinel_t<_Base> _M_end = sentinel_t<_Base>(); + + public: + _Sentinel() = default; + + constexpr explicit + _Sentinel(_Parent& __parent) + : _M_end(ranges::end(__parent._M_base)) + { } + + constexpr + _Sentinel(_Sentinel<!_Const> __s) + requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> + : _M_end(std::move(__s._M_end)) + { } + + friend constexpr bool + operator==(const _Iterator<_Const>& __x, const _Sentinel& __y) + { return __y.__equal(__x); } + }; + + _Vp _M_base = _Vp(); + + // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>" + // Applied P3278 and made this field mutable. + [[no_unique_address]] mutable + conditional_t<!is_reference_v<_InnerRange>, + all_view<_InnerRange>, __detail::_Empty> _M_inner; + + public: + join_view() = default; + + constexpr explicit + join_view(_Vp __base) + : _M_base(std::move(__base)) + { } + + /* XXX: P3280 removes this constructor + template<input_range _Range> + requires viewable_range<_Range> + && constructible_from<_Vp, all_view<_Range>> + constexpr explicit + join_view(_Range&& __r) + : _M_base(views::all(std::forward<_Range>(__r))) + { } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() + { + return _Iterator<__detail::__simple_view<_Vp>>{*this, + ranges::begin(_M_base)}; + } + + constexpr auto + begin() const + requires input_range<const _Vp> + && is_reference_v<range_reference_t<const _Vp>> + { + return _Iterator<true>{*this, ranges::begin(_M_base)}; + } + + constexpr auto + end() + { + if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange> + && forward_range<_InnerRange> + && common_range<_Vp> && common_range<_InnerRange>) + return _Iterator<__detail::__simple_view<_Vp>>{*this, + ranges::end(_M_base)}; + else + return _Sentinel<__detail::__simple_view<_Vp>>{*this}; + } + + constexpr auto + end() const + requires input_range<const _Vp> + && is_reference_v<range_reference_t<const _Vp>> + { + if constexpr (forward_range<const _Vp> + && is_reference_v<range_reference_t<const _Vp>> + && forward_range<range_reference_t<const _Vp>> + && common_range<const _Vp> + && common_range<range_reference_t<const _Vp>>) + return _Iterator<true>{*this, ranges::end(_M_base)}; + else + return _Sentinel<true>{*this}; + } + }; + + template<typename _Range> + explicit join_view(_Range&&) -> join_view<all_view<_Range>>; + + namespace views + { + inline constexpr __adaptor::_RangeAdaptorClosure join + = [] <viewable_range _Range> (_Range&& __r) + { + return join_view{std::forward<_Range>(__r)}; + }; + } // namespace views + + namespace __detail + { + template<auto> + struct __require_constant; + + template<typename _Range> + concept __tiny_range = sized_range<_Range> + && requires + { typename __require_constant<remove_reference_t<_Range>::size()>; } + && (remove_reference_t<_Range>::size() <= 1); + } + + template<input_range _Vp, forward_range _Pattern> + requires view<_Vp> && view<_Pattern> + && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>, + ranges::equal_to> + && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>) + class split_view : public view_interface<split_view<_Vp, _Pattern>> + { + private: + template<bool _Const> + struct _InnerIter; + + template<bool _Const> + struct _OuterIter + { + private: + using _Parent = conditional_t<_Const, const split_view, split_view>; + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + constexpr bool + __at_end() const + { return _M_current == ranges::end(_M_parent->_M_base); } + + // XXX: [24.7.11.3.1] + // Many of the following specifications refer to the notional member + // current of outer-iterator. current is equivalent to current_ if + // V models forward_range, and parent_->current_ otherwise. + constexpr auto& + __current() + { + if constexpr (forward_range<_Vp>) + return _M_current; + else + return _M_parent->_M_current; + } + + constexpr auto& + __current() const + { + if constexpr (forward_range<_Vp>) + return _M_current; + else + return _M_parent->_M_current; + } + + _Parent* _M_parent = nullptr; + + // XXX: _M_current is present only if "V models forward_range" + [[no_unique_address]] + conditional_t<forward_range<_Vp>, + iterator_t<_Base>, __detail::_Empty> _M_current; + + public: + using iterator_concept = conditional_t<forward_range<_Base>, + forward_iterator_tag, + input_iterator_tag>; + using iterator_category = input_iterator_tag; + using difference_type = range_difference_t<_Base>; + + struct value_type : view_interface<value_type> + { + private: + _OuterIter _M_i = _OuterIter(); + + public: + value_type() = default; + + constexpr explicit + value_type(_OuterIter __i) + : _M_i(std::move(__i)) + { } + + constexpr _InnerIter<_Const> + begin() const + requires copyable<_OuterIter> + { return _InnerIter<_Const>{_M_i}; } + + constexpr _InnerIter<_Const> + begin() + requires (!copyable<_OuterIter>) + { return _InnerIter<_Const>{std::move(_M_i)}; } + + constexpr default_sentinel_t + end() const + { return default_sentinel; } + }; + + _OuterIter() = default; + + constexpr explicit + _OuterIter(_Parent& __parent) requires (!forward_range<_Base>) + : _M_parent(address(__parent)) + { } + + constexpr + _OuterIter(_Parent& __parent, iterator_t<_Base> __current) + requires forward_range<_Base> + : _M_parent(std::__addressof(__parent)), + _M_current(std::move(__current)) + { } + + constexpr + _OuterIter(_OuterIter<!_Const> __i) + requires _Const + && convertible_to<iterator_t<_Vp>, iterator_t<const _Vp>> + : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current)) + { } + + constexpr value_type + operator*() const + { return value_type{*this}; } + + constexpr _OuterIter& + operator++() + { + const auto __end = ranges::end(_M_parent->_M_base); + if (_M_current == __end) + return *this; + const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern}; + if (__pbegin == __pend) + ++_M_current; + else + do + { + auto [__b, __p] + = __detail::mismatch(std::move(_M_current), __end, + __pbegin, __pend); + _M_current = std::move(__b); + if (__p == __pend) + break; + } while (++_M_current != __end); + return *this; + } + + constexpr decltype(auto) + operator++(int) + { + if constexpr (forward_range<_Base>) + { + auto __tmp = *this; + ++*this; + return __tmp; + } + else + ++*this; + } + + friend constexpr bool + operator==(const _OuterIter& __x, const _OuterIter& __y) + requires forward_range<_Base> + { return __x._M_current == __y._M_current; } + + friend constexpr bool + operator==(const _OuterIter& __x, default_sentinel_t) + { return __x.__at_end(); }; + + friend _InnerIter<_Const>; + }; + + template<bool _Const> + struct _InnerIter + { + private: + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + constexpr bool + __at_end() const + { + auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern}; + auto __end = ranges::end(_M_i._M_parent->_M_base); + if constexpr (__detail::__tiny_range<_Pattern>) + { + const auto& __cur = _M_i.__current(); + if (__cur == __end) + return true; + if (__pcur == __pend) + return _M_incremented; + return *__cur == *__pcur; + } + else + { + auto __cur = _M_i.__current(); + if (__cur == __end) + return true; + if (__pcur == __pend) + return _M_incremented; + do + { + if (*__cur != *__pcur) + return false; + if (++__pcur == __pend) + return true; + } while (++__cur != __end); + return false; + } + } + + static constexpr auto + _S_iter_cat() + { + using _Cat = iterator_traits<iterator_t<_Base>>::iterator_category; + if constexpr (derived_from<_Cat, forward_iterator_tag>) + return forward_iterator_tag{}; + else + return _Cat{}; + } + + static constexpr decltype(auto) + __iter_move(const _InnerIter& __i = {}) + noexcept(noexcept(ranges::iter_move(__i._M_i.__current()))) + { return ranges::iter_move(__i._M_i.__current()); } + + static constexpr void + __iter_swap(const _InnerIter& __x = {}, const _InnerIter& __y = {}) + noexcept(noexcept(ranges::iter_swap(__x._M_i.__current(), + __y._M_i.__current()))) + { ranges::iter_swap(__x._M_i.__current(), __y._M_i.__current()); } + + _OuterIter<_Const> _M_i = _OuterIter<_Const>(); + bool _M_incremented = false; + + public: + using iterator_concept = typename _OuterIter<_Const>::iterator_concept; + using iterator_category = decltype(_S_iter_cat()); + using value_type = range_value_t<_Base>; + using difference_type = range_difference_t<_Base>; + + _InnerIter() = default; + + constexpr explicit + _InnerIter(_OuterIter<_Const> __i) + : _M_i(std::move(__i)) + { } + + constexpr decltype(auto) + operator*() const + { return *_M_i._M_current; } + + constexpr _InnerIter& + operator++() + { + _M_incremented = true; + if constexpr (!forward_range<_Base>) + if constexpr (_Pattern::size() == 0) + return *this; + ++_M_i.__current(); + return *this; + } + + constexpr decltype(auto) + operator++(int) + { + if constexpr (forward_range<_Vp>) + { + auto __tmp = *this; + ++*this; + return __tmp; + } + else + ++*this; + } + + friend constexpr bool + operator==(const _InnerIter& __x, const _InnerIter& __y) + requires forward_range<_Base> + { return __x._M_i.__current() == __y._M_i.__current(); } + + friend constexpr bool + operator==(const _InnerIter& __x, default_sentinel_t) + { return __x.__at_end(); } + + friend constexpr decltype(auto) + iter_move(const _InnerIter& __i) noexcept(noexcept(__iter_move())) + { return __iter_move(__i); } + + friend constexpr void + iter_swap(const _InnerIter& __x, const _InnerIter& __y) + noexcept(noexcept(__iter_swap())) + requires indirectly_swappable<iterator_t<_Base>> + { __iter_swap(__x, __y); } + }; + + _Vp _M_base = _Vp(); + _Pattern _M_pattern = _Pattern(); + + // XXX: _M_current is "present only if !forward_range<V>" + [[no_unique_address]] + conditional_t<!forward_range<_Vp>, + iterator_t<_Vp>, __detail::_Empty> _M_current; + + + public: + split_view() = default; + + constexpr + split_view(_Vp __base, _Pattern __pattern) + : _M_base(std::move(__base)), _M_pattern(std::move(__pattern)) + { } + + /* XXX: P3280 removes this constructor + template<input_range _Range, forward_range _Pred> + requires constructible_from<_Vp, all_view<_Range>> + && constructible_from<_Pattern, all_view<_Pred>> + constexpr + split_view(_Range&& __r, _Pred&& __p) + : _M_base(views::all(std::forward<_Range>(__r))), + _M_pattern(views::all(std::forward<_Pred>(__p))) + { } + */ + + template<input_range _Range> + requires constructible_from<_Vp, all_view<_Range>> + && constructible_from<_Pattern, single_view<range_value_t<_Range>>> + constexpr + split_view(_Range&& __r, range_value_t<_Range> __e) + : _M_base(views::all(std::forward<_Range>(__r))), + _M_pattern(std::move(__e)) + { } + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() + { + if constexpr (forward_range<_Vp>) + return _OuterIter<__detail::__simple_view<_Vp>>{*this, + ranges::begin(_M_base)}; + else + { + _M_current = ranges::begin(_M_base); + return _OuterIter<false>{*this}; + } + } + + constexpr auto + begin() const requires forward_range<_Vp> && forward_range<const _Vp> + { + return _OuterIter<true>{*this, ranges::begin(_M_base)}; + } + + constexpr auto + end() requires forward_range<_Vp> && common_range<_Vp> + { + return _OuterIter<__detail::__simple_view<_Vp>>{*this, ranges::end(_M_base)}; + } + + constexpr auto + end() const + { + if constexpr (forward_range<_Vp> + && forward_range<const _Vp> + && common_range<const _Vp>) + return _OuterIter<true>{*this, ranges::end(_M_base)}; + else + return default_sentinel; + } + }; + + template<typename _Range, typename _Pred> + split_view(_Range&&, _Pred&&) + -> split_view<all_view<_Range>, all_view<_Pred>>; + + template<input_range _Range> + split_view(_Range&&, range_value_t<_Range>) + -> split_view<all_view<_Range>, single_view<range_value_t<_Range>>>; + + namespace views + { + inline constexpr __adaptor::_RangeAdaptor split + = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f) + { + return split_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)}; + }; + } // namespace views + + namespace views + { + struct _Counted + { + template<input_or_output_iterator _Iter> + constexpr auto + operator()(_Iter __i, iter_difference_t<_Iter> __n) const + { + if constexpr (random_access_iterator<_Iter>) + return subrange{__i, __i + __n}; + else + return subrange{counted_iterator{std::move(__i), __n}, + default_sentinel}; + } + }; + + inline constexpr _Counted counted{}; + } // namespace views + + template<view _Vp> + requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>> + class common_view : public view_interface<common_view<_Vp>> + { + private: + _Vp _M_base = _Vp(); + + public: + common_view() = default; + + constexpr explicit + common_view(_Vp __r) + : _M_base(std::move(__r)) + { } + + /* XXX: P3280 doesn't remove this constructor, but I think it should? + template<viewable_range _Range> + requires (!common_range<_Range>) && constructible_from<_Vp, all_view<_Range>> + constexpr explicit + common_view(_Range&& __r) + : _M_base(views::all(std::forward<_Range>(__r))) + { } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() + { + if constexpr (random_access_range<_Vp> && sized_range<_Vp>) + return ranges::begin(_M_base); + else + return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>> + (ranges::begin(_M_base)); + } + + constexpr auto + begin() const requires range<const _Vp> + { + if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>) + return ranges::begin(_M_base); + else + return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>> + (ranges::begin(_M_base)); + } + + constexpr auto + end() + { + if constexpr (random_access_range<_Vp> && sized_range<_Vp>) + return ranges::begin(_M_base) + ranges::size(_M_base); + else + return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>> + (ranges::end(_M_base)); + } + + constexpr auto + end() const requires range<const _Vp> + { + if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>) + return ranges::begin(_M_base) + ranges::size(_M_base); + else + return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>> + (ranges::end(_M_base)); + } + + constexpr auto + size() requires sized_range<_Vp> + { return ranges::size(_M_base); } + + constexpr auto + size() const requires sized_range<const _Vp> + { return ranges::size(_M_base); } + }; + + template<typename _Range> + common_view(_Range&&) -> common_view<all_view<_Range>>; + + namespace views + { + inline constexpr __adaptor::_RangeAdaptorClosure common + = [] <viewable_range _Range> (_Range&& __r) + { + if constexpr (common_range<_Range> + && requires { views::all(std::forward<_Range>(__r)); }) + return views::all(std::forward<_Range>(__r)); + else + return common_view{std::forward<_Range>(__r)}; + }; + + } // namespace views + + template<view _Vp> + requires bidirectional_range<_Vp> + class reverse_view : public view_interface<reverse_view<_Vp>> + { + private: + _Vp _M_base = _Vp(); + + public: + reverse_view() = default; + + constexpr explicit + reverse_view(_Vp __r) + : _M_base(std::move(__r)) + { } + + /* XXX: P3280 removes this constructor + template<viewable_range _Range> + requires bidirectional_range<_Range> && constructible_from<_Vp, all_view<_Range>> + constexpr explicit + reverse_view(_Range&& __r) + : _M_base(views::all(std::forward<_Range>(__r))) + { } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr reverse_iterator<iterator_t<_Vp>> + begin() + { + // XXX: we need to cache the result here as per [range.reverse.view] + return make_reverse_iterator(ranges::next(ranges::begin(_M_base), + ranges::end(_M_base))); + } + + constexpr auto + begin() requires common_range<_Vp> + { return make_reverse_iterator(ranges::end(_M_base)); } + + constexpr auto + begin() const requires common_range<const _Vp> + { return make_reverse_iterator(ranges::end(_M_base)); } + + constexpr reverse_iterator<iterator_t<_Vp>> + end() + { return make_reverse_iterator(ranges::begin(_M_base)); } + + constexpr auto + end() const requires common_range<const _Vp> + { return make_reverse_iterator(ranges::begin(_M_base)); } + + constexpr auto + size() requires sized_range<_Vp> + { return ranges::size(_M_base); } + + constexpr auto + size() const requires sized_range<const _Vp> + { return ranges::size(_M_base); } + }; + + template<typename _Range> + reverse_view(_Range&&) -> reverse_view<all_view<_Range>>; + + namespace views + { + namespace __detail + { + template<typename> + inline constexpr bool __is_reversible_subrange = false; + + template<typename _Iter, subrange_kind _Kind> + inline constexpr bool + __is_reversible_subrange<subrange<reverse_iterator<_Iter>, + reverse_iterator<_Iter>, + _Kind>> = true; + + template<typename> + inline constexpr bool __is_reverse_view = false; + + template<typename _Vp> + inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true; + } + + inline constexpr __adaptor::_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 + { std::get<_Nm>(__t) } + -> convertible_to<const tuple_element_t<_Nm, _Tp>&>; + }; + } + + template<input_range _Vp, size_t _Nm> + requires view<_Vp> + && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm> + && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>, + _Nm> + class elements_view : public view_interface<elements_view<_Vp, _Nm>> + { + public: + elements_view() = default; + + constexpr explicit + elements_view(_Vp base) + : _M_base(std::move(base)) + { } + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() requires (!__detail::__simple_view<_Vp>) + { return _Iterator<false>(ranges::begin(_M_base)); } + + constexpr auto + begin() const requires __detail::__simple_view<_Vp> + { return _Iterator<true>(ranges::begin(_M_base)); } + + constexpr auto + end() requires (!__detail::__simple_view<_Vp>) + { return ranges::end(_M_base); } + + constexpr auto + end() const requires __detail::__simple_view<_Vp> + { return ranges::end(_M_base); } + + constexpr auto + size() requires sized_range<_Vp> + { return ranges::size(_M_base); } + + constexpr auto + size() const requires sized_range<const _Vp> + { return ranges::size(_M_base); } + + private: + template<bool _Const> + struct _Iterator + { + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + iterator_t<_Base> _M_current; + + friend _Iterator<!_Const>; + + public: + using iterator_category + = typename iterator_traits<iterator_t<_Base>>::iterator_category; + using value_type + = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>; + using difference_type = range_difference_t<_Base>; + + _Iterator() = default; + + constexpr explicit + _Iterator(iterator_t<_Base> current) + : _M_current(std::move(current)) + { } + + constexpr + _Iterator(_Iterator<!_Const> i) + requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>> + : _M_current(std::move(i._M_current)) + { } + + constexpr iterator_t<_Base> + base() const& + requires copyable<iterator_t<_Base>> + { return _M_current; } + + constexpr iterator_t<_Base> + base() && + { return std::move(_M_current); } + + constexpr decltype(auto) + operator*() const + { return std::get<_Nm>(*_M_current); } + + constexpr _Iterator& + operator++() + { + ++_M_current; + return *this; + } + + constexpr void + operator++(int) requires (!forward_range<_Base>) + { ++_M_current; } + + constexpr _Iterator + operator++(int) requires forward_range<_Base> + { + auto __tmp = *this; + ++_M_current; + return __tmp; + } + + constexpr _Iterator& + operator--() requires bidirectional_range<_Base> + { + --_M_current; + return *this; + } + + constexpr _Iterator + operator--(int) requires bidirectional_range<_Base> + { + auto __tmp = *this; + --_M_current; + return __tmp; + } + + constexpr _Iterator& + operator+=(difference_type __n) + requires random_access_range<_Base> + { + _M_current += __n; + return *this; + } + + constexpr _Iterator& + operator-=(difference_type __n) + requires random_access_range<_Base> + { + _M_current -= __n; + return *this; + } + + constexpr decltype(auto) + operator[](difference_type __n) const + requires random_access_range<_Base> + { return std::get<_Nm>(*(_M_current + __n)); } + + 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 sentinel_t<_Base>& __y) + { return __x._M_current == __y; } + + 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._M_current < __x._M_current; } + + friend constexpr bool + operator<=(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return !(__y._M_current > __x._M_current); } + + friend constexpr bool + operator>=(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return !(__x._M_current > __y._M_current); } + +#ifdef __cpp_lib_three_way_comparison + friend constexpr auto + 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 _Iterator + operator+(const _Iterator& __x, difference_type __y) + requires random_access_range<_Base> + { return _Iterator{__x} += __y; } + + friend constexpr _Iterator + operator+(difference_type __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __y + __x; } + + friend constexpr _Iterator + operator-(const _Iterator& __x, difference_type __y) + requires random_access_range<_Base> + { return _Iterator{__x} -= __y; } + + friend constexpr difference_type + operator-(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __x._M_current - __y._M_current; } + + friend constexpr difference_type + operator-(const _Iterator<_Const>& __x, const sentinel_t<_Base>& __y) + requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>> + { return __x._M_current - __y; } + + friend constexpr difference_type + operator-(const sentinel_t<_Base>& __x, const _Iterator<_Const>& __y) + requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>> + { return -(__y - __x); } + }; + + _Vp _M_base = _Vp(); + }; + + template<typename _Range> + using keys_view = elements_view<all_view<_Range>, 0>; + + template<typename _Range> + using values_view = elements_view<all_view<_Range>, 1>; + + namespace views + { + template<size_t _Nm> + inline constexpr __adaptor::_RangeAdaptorClosure elements + = [] <viewable_range _Range> (_Range&& __r) + { + return elements_view<all_view<_Range>, _Nm>{std::forward<_Range>(__r)}; + }; + + inline constexpr __adaptor::_RangeAdaptorClosure keys = elements<0>; + inline constexpr __adaptor::_RangeAdaptorClosure values = elements<1>; + } // namespace views + +} // namespace ranges + + namespace views = ranges::views; + + template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> + struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>> + : integral_constant<size_t, 2> + { }; + + template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> + struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>> + { using type = _Iter; }; + + template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> + struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>> + { using type = _Sent; }; + _GLIBCXX_END_NAMESPACE_VERSION } // namespace #endif // library concepts diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/all.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/all.cc new file mode 100644 index 00000000000..577ce7460e6 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/all.cc @@ -0,0 +1,122 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + int x[] = {1,2,3,4,5}; + auto v = views::all(x); + + static_assert(ranges::view<decltype(v)>); + static_assert(ranges::random_access_range<decltype(v)>); + + VERIFY( ranges::size(v) == 5 ); + VERIFY( ranges::size(x | views::all) == 5 ); + VERIFY( ranges::size(v | views::all | views::all) == 5 ); + VERIFY( ranges::size(v | (views::all | views::all)) == 5 ); + + ranges::reverse(v); + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); +} + +void +test02() +{ + int x[5] = { 0 }; + int k = 0; + for (auto&& i : ranges::ref_view{x}) + i += ++k; + VERIFY( ranges::equal(x, (int[]){1,2,3,4,5}) ); +} + +constexpr bool +test03() +{ + std::array ints{0,1,2,3,4,5}; + auto even = [] (int i) { return i%2==0; }; + auto odd = [] (int i) { return i%2==1; }; + auto square = [] (int i) { return i*i; }; + int sum = 0; + for (auto v : (ints + | (views::all + | (views::filter(even) + | (views::filter(odd) | views::all))) + | views::transform(square))) + sum += v; + return sum == 0; +} + +constexpr bool +test04() +{ + auto odd = [] (int i) { return i%2==1; }; + auto square = [] (int i) { return i*i; }; + auto increment = [] (int i) { return i+1; }; + auto small = [] (int i) { return i<30; }; + auto non_negative = [] (int i) { return i>=0; }; + auto negative = [] (int i) { return i<0; }; + return ranges::equal(views::iota(-5) + | views::drop_while(negative) + | views::take_while(non_negative) + | views::transform(increment) + | views::filter(odd) + | views::take(3) + | views::all + | views::transform(square), + views::iota(-5) + | views::drop_while(negative) + | views::drop(1) + | views::filter(odd) + | views::transform(square) + | views::take_while(small) + | views::take_while(small)); +} + +static_assert(std::is_empty_v<decltype(views::common + | views::join + | views::all + | views::common + | views::keys + | views::reverse)>); +static_assert(sizeof(decltype(views::take(5) | views::drop(5))) + == sizeof(decltype(views::take(5) + | views::join + | views::common + | views::all + | views::keys + | views::drop(5) + | views::reverse))); + +int +main() +{ + test01(); + test02(); + static_assert(test03()); + static_assert(test04()); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/common.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/common.cc new file mode 100644 index 00000000000..b73796835be --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/common.cc @@ -0,0 +1,68 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + int x[] = {1,2,1,3}; + auto v = x | views::common; + VERIFY( std::count(v.begin(), v.end(), 1) == 2); + static_assert(ranges::common_range<decltype(v)>); + static_assert(ranges::view<decltype(v)>); + static_assert(ranges::random_access_range<decltype(v)>); + static_assert(std::same_as<decltype(v), decltype(views::common(v))>); + + auto v2 = v | (views::common | views::common); + VERIFY( std::count(v2.begin(), v2.end(), 1) == 2); +} + +void +test02() +{ + int x[] = {1,2,1,3}; + test_range<int, forward_iterator_wrapper> rx(x); + auto v = ranges::common_view(rx); + VERIFY( std::count(v.begin(), v.end(), 1) == 2); + static_assert(ranges::common_range<decltype(v)>); + static_assert(ranges::view<decltype(v)>); + static_assert(ranges::forward_range<decltype(v)>); + static_assert(std::same_as<decltype(v), decltype(views::common(v))>); + + auto v2 = v | (views::common | views::common); + VERIFY( std::count(v2.begin(), v2.end(), 1) == 2); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/counted.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/counted.cc new file mode 100644 index 00000000000..e81f9062d39 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/counted.cc @@ -0,0 +1,64 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + 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); + static_assert(ranges::view<R>); + static_assert(ranges::sized_range<R>); + static_assert(ranges::common_range<R>); + static_assert(ranges::random_access_range<R>); +} + +void +test02() +{ + int x[] = {0,1,2,3,4,5,0,1,2,3,4,5}; + test_range<int, forward_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>); + static_assert(ranges::sized_range<R>); + static_assert(!ranges::common_range<R>); + static_assert(!ranges::bidirectional_range<R>); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc new file mode 100644 index 00000000000..93fbafcf5a3 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc @@ -0,0 +1,107 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::bidirectional_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + int x[] = {1,2,3,4,5}; + auto v = x | views::drop(3); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(ranges::sized_range<R>); + static_assert(ranges::random_access_range<R>); + VERIFY( ranges::equal(v, (int[]){4,5}) ); +} + +void +test02() +{ + int x[] = {1,2,3,4,5}; + auto t = views::drop(3) | views::reverse; + auto v = x | t; + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(ranges::sized_range<R>); + static_assert(ranges::random_access_range<R>); + VERIFY( ranges::equal(v, (int[]){5,4}) ); +} + +void +test03() +{ + int x[] = {1,2,3,4,5}; + test_range<int, bidirectional_iterator_wrapper> rx(x); + auto v = rx | views::drop(3); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::sized_range<R>); + static_assert(ranges::bidirectional_range<R>); + VERIFY( ranges::equal(v, (int[]){4,5}) ); +} + + +void +test04() +{ + auto v = views::iota(0) | views::drop(10); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::sized_range<R>); + VERIFY( ranges::equal(v | views::take(3), (int[]){10,11,12}) ); +} + +void +test05() +{ + int x[] = {1,2,3}; + auto r = ranges::subrange(x, x+1); + auto v = views::drop(r, 2); + VERIFY( ranges::begin(v) == x+1 ); + VERIFY( ranges::size(v) == 0 ); +} + +void +test06() +{ + int x[] = {1,2,3}; + VERIFY( ranges::empty(x | views::drop(10)) ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); + test06(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc new file mode 100644 index 00000000000..be47551563d --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc @@ -0,0 +1,63 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::bidirectional_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + auto p = [] (int i) { return i != 16; }; + auto v = views::iota(10) | views::drop_while(p); + VERIFY( ranges::equal(v | views::take(5), (int[]){16,17,18,19,20}) ); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::random_access_range<R>); +} + +void +test02() +{ + int x[] = {1,2,3,4,5}; + test_range<int, bidirectional_iterator_wrapper> rx(x); + auto v = rx | views::drop_while([] (int i) { return i<4; }); + VERIFY( ranges::equal(v, (int[]){4,5}) ); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::bidirectional_range<R>); +} + +int +main() +{ + test01(); + test02(); +} + diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc new file mode 100644 index 00000000000..d846c4cf33e --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc @@ -0,0 +1,52 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> +#include <tuple> + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + std::tuple<int, int> x[] = {{1,2},{3,4},{5,6}}; + auto v0 = x | views::elements<0>; + VERIFY( ranges::equal(v0, (int[]){1,3,5}) ); + VERIFY( ranges::equal(v0, x | views::keys) ); + VERIFY( ranges::size(v0) == 3 ); + + using R0 = decltype(v0); + static_assert(ranges::random_access_range<R0>); + static_assert(ranges::sized_range<R0>); + + auto v1 = x | views::reverse | views::elements<1> | views::reverse; + VERIFY( ranges::equal(v1, (int[]){2,4,6}) ); + VERIFY( ranges::equal(v1, x | views::values) ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc new file mode 100644 index 00000000000..83d52967a0f --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc @@ -0,0 +1,97 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::bidirectional_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + int x[] = {1,2,3,4,5,6}; + auto is_odd = [] (int i) { return i%2==1; }; + auto v = x | views::filter(is_odd); + using R = decltype(v); + static_assert(std::same_as<int&, decltype(*v.begin())>); + static_assert(ranges::view<R>); + static_assert(ranges::input_range<R>); + static_assert(ranges::common_range<R>); + static_assert(!ranges::sized_range<R>); + static_assert(ranges::bidirectional_range<R>); + static_assert(!ranges::random_access_range<R>); + static_assert(ranges::range<ranges::all_view<R>>); + VERIFY( ranges::equal(v, (int[]){1,3,5}) ); + VERIFY( ranges::equal(v | views::reverse, (int[]){5,3,1}) ); +} + +void +test02() +{ + int x[] = {1,2,3,4,5,6}; + auto f = [flag=false] (int) mutable { return flag = !flag; }; + auto v = views::filter(f)(x); + using R = decltype(v); + static_assert(std::same_as<int&, decltype(*v.begin())>); + static_assert(ranges::range<R>); + static_assert(std::copyable<R>); + static_assert(!ranges::view<const R>); + VERIFY( ranges::equal(v, (int[]){1,3,5}) ); +} + +struct X +{ + int i, j; +}; + +void +test03() +{ + X x[] = {{1,3}, {2,5}, {3,7}, {4,9}}; + test_range<X, bidirectional_iterator_wrapper> rx(x); + auto v = rx | views::filter([] (auto&& p) { return p.i%2==0; }); + int sum = 0; + for (auto i = v.begin(); i != v.end(); ++i) + sum += i->j; + VERIFY( sum == 14 ); +} + +void +test04() +{ + auto yes = [] (int) { return true; }; + VERIFY( ranges::equal(views::iota(0) | views::filter(yes) | views::take(1), + (int[]){0}) ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc new file mode 100644 index 00000000000..d3e652da009 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc @@ -0,0 +1,112 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <string> +#include <string_view> +#include <vector> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + using namespace std::literals; + std::string_view cs[] = {"the", "quick", "brown", "fox"}; + auto v = cs | views::join; + VERIFY( ranges::equal(v, "thequickbrownfox"sv) ); + using R = decltype(v); + static_assert(ranges::bidirectional_range<R>); + static_assert(ranges::bidirectional_range<const R>); + static_assert(ranges::common_range<R>); + static_assert(ranges::common_range<const R>); +} + +void +test02() +{ + auto v = (views::iota(0,4) + | views::transform([] (int i) { return views::iota(0,i); }) + | views::join); + VERIFY( ranges::equal(v, (int[]){0,0,1,0,1,2}) ); + using R = decltype(v); + static_assert(ranges::input_range<R>); + static_assert(!ranges::range<const R>); + static_assert(!ranges::forward_range<R>); + static_assert(!ranges::common_range<const R>); +} + +void +test03() +{ + auto v = (views::iota(0,4) + | views::transform([] (int i) { return views::iota(0,i); }) + | views::filter([] (auto) { return true; }) + | views::join); + VERIFY( ranges::equal(v, (int[]){0,0,1,0,1,2}) ); + using R = decltype(v); + static_assert(ranges::input_range<R>); + static_assert(!ranges::range<const R>); + static_assert(!ranges::forward_range<R>); + static_assert(!ranges::common_range<const R>); +} + +void +test04() +{ + auto v = (views::iota(0,4) + | views::transform([] (int i) { return views::iota(0,i); })); + auto v2 = ranges::ref_view{v}; + VERIFY( ranges::equal(v2 | views::join, (int[]){0,0,1,0,1,2}) ); + using R = decltype(v2); + static_assert(ranges::random_access_range<R>); + static_assert(ranges::range<const R>); + static_assert(ranges::common_range<const R>); + static_assert(ranges::random_access_range<ranges::range_reference_t<R>>); + static_assert(!std::is_reference_v<ranges::range_reference_t<R>>); +} + +void +test05() +{ + using namespace std::literals; + std::vector<std::string> x = {"the", " ", "quick", " ", "brown", " ", "fox"}; + auto v = x | views::join | views::split(' '); + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc new file mode 100644 index 00000000000..0c6aceabbed --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc @@ -0,0 +1,86 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::bidirectional_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + int x[] = {1,2,3,4,5}; + auto v = x | views::reverse; + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); + VERIFY( ranges::equal(v | views::reverse, x) ); + 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)>); +} + +void +test02() +{ + int x[] = {1,2,3,4,5}; + test_range<int, bidirectional_iterator_wrapper> rx(x); + auto v = views::reverse(rx); + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); + VERIFY( ranges::equal(v | views::reverse, rx) ); + 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::bidirectional_range<decltype(v)>); +} + +void +test03() +{ + int x[] = {1,7,3,6,5,2,4,8}; + auto is_even = [] (int i) { return i%2==0; }; + int sum = 0; + for (auto i : x | views::reverse | views::filter(is_even)) + sum += i; + VERIFY( sum == 20 ); +} + +void +test04() +{ + int x[] = {1,2,3,4,5}; + VERIFY( ranges::equal(x | views::reverse | (views::reverse | views::reverse), + (int[]){5,4,3,2,1}) ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc new file mode 100644 index 00000000000..129a8249f21 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc @@ -0,0 +1,82 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <string> +#include <string_view> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +using namespace std::literals; + +void +test01() +{ + auto x = "the quick brown fox"sv; + auto p = std::string{" "}; + auto v = x | views::split(p); + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +void +test02() +{ + auto x = "the quick brown fox"sv; + auto v = x | views::split(' '); + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +void +test03() +{ + char x[] = "the quick brown fox"; + test_range<char, forward_iterator_wrapper> rx(x); + auto v = rx | views::split(' '); + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/take.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/take.cc new file mode 100644 index 00000000000..e2d2edbe0a8 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/take.cc @@ -0,0 +1,95 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::bidirectional_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + auto v = views::iota(0) | views::take(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)>); + VERIFY( ranges::equal(v, (int[]){0,1,2,3,4}) ); +} + +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)>); + VERIFY( ranges::equal(v, (int[]){0,1,2,3,4}) ); +} + +void +test03() +{ + int x[] = {0,1,2,3,4,5}; + auto is_odd = [] (int i) { return i%2 == 1; }; + auto v = x | views::filter(is_odd) | views::take(3); + ranges::begin(v); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::sized_range<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::forward_range<R>); + static_assert(!ranges::random_access_range<R>); + static_assert(!ranges::range<const R>); + VERIFY( ranges::equal(v, (int[]){1,3,5}) ); +} + +void +test04() +{ + int x[] = {1,2,3,4,5}; + test_range<int, bidirectional_iterator_wrapper> rx(x); + auto v = ranges::take_view{rx, 3}; + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::sized_range<R>); + static_assert(ranges::bidirectional_range<R>); + VERIFY( ranges::equal(v | views::take(5), (int[]){1,2,3}) ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/take_while.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/take_while.cc new file mode 100644 index 00000000000..b261ffd1aae --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/take_while.cc @@ -0,0 +1,62 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + auto p = [] (int i) { return i != 16; }; + auto v = views::iota(10) | views::take_while(p); + VERIFY( ranges::equal(v, (int[]){10,11,12,13,14,15}) ); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::random_access_range<R>); +} + +void +test02() +{ + int x[] = {1,2,3,4,5}; + test_range<int, forward_iterator_wrapper> rx(x); + auto v = rx | views::take_while([] (int i) { return i<4; }); + VERIFY( ranges::equal(v, (int[]){1,2,3}) ); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::forward_range<R>); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/transform.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/transform.cc new file mode 100644 index 00000000000..ad51fffb43d --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/transform.cc @@ -0,0 +1,86 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::random_access_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + int x[] = {1,2,3,4,5}; + auto is_odd = [] (int i) { return i%2==1; }; + auto v = x | views::transform(is_odd); + VERIFY( ranges::equal(v, (int[]){1,0,1,0,1}) ); + using R = decltype(v); + static_assert(std::same_as<bool, decltype(*ranges::begin(v))>); + static_assert(ranges::view<R>); + static_assert(ranges::sized_range<R>); + static_assert(ranges::random_access_range<R>); +} + +struct X +{ + int i,j; +}; + +void +test02() +{ + X x[] = {{1,2},{3,4},{5,6},{7,8},{9,10}}; + test_range<X, random_access_iterator_wrapper> rx(x); + auto v = rx | views::transform(&X::i); + VERIFY( ranges::size(v) == 5 ); + VERIFY( ranges::distance(v.begin(), v.end()) == 5 ); + VERIFY( ranges::equal(v, (int[]){1,3,5,7,9}) ); + VERIFY( ranges::equal(v | views::reverse, (int[]){9,7,5,3,1}) ); + using R = decltype(v); + static_assert(std::same_as<int&, decltype(*ranges::begin(v))>); + static_assert(std::same_as<int, std::iter_value_t<ranges::iterator_t<R>>>); + static_assert(ranges::view<R>); + static_assert(ranges::sized_range<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::random_access_range<R>); +} + +void +test03() +{ + auto id = [] (int i) { return i; }; + auto v = views::iota(0) | (views::filter(id) + | views::transform(id) + | views::take(5)); + VERIFY( ranges::equal(v, (int[]){1,2,3,4,5}) ); +} + +int +main() +{ + test01(); + test02(); + test03(); +}

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index ea558c76c9d..947e223f7f9 100644 --- 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 #include <initializer_list> #include <iterator> #include <limits> @@ -255,7 +256,8 @@ namespace ranges class subrange : public view_interface<subrange<_It, _Sent, _Kind>> { private: - static constexpr bool _S_store_size + // XXX: gcc complains when using constexpr here + static const bool _S_store_size = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>; _It _M_begin = _It(); @@ -507,6 +509,9 @@ namespace ranges : std::optional<_Tp>{std::in_place} { } + __box(const __box&) = default; + __box(__box&&) = default; + using std::optional<_Tp>::operator=; __box& @@ -922,7 +927,7 @@ namespace views struct _Single { template<typename _Tp> - auto + constexpr auto operator()(_Tp&& __e) const { return single_view{std::forward<_Tp>(__e)}; } }; @@ -932,19 +937,2421 @@ namespace views struct _Iota { template<typename _Tp> - auto + constexpr auto operator()(_Tp&& __e) const { return iota_view{std::forward<_Tp>(__e)}; } template<typename _Tp, typename _Up> - auto + constexpr auto operator()(_Tp&& __e, _Up&& __f) const { return iota_view{std::forward<_Tp>(__e), std::forward<_Tp>(__f)}; } }; inline constexpr _Iota iota{}; +} // namespace views + +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) + requires (!is_default_constructible_v<_Callable>) + : _M_callable(std::move(__callable)) + { } + + template<typename... _Args> + requires (sizeof...(_Args) >= 1) + constexpr auto + operator()(_Args&&... __args) const + { + if constexpr (is_invocable_v<_Callable, _Args...>) + { + static_assert(sizeof...(_Args) != 1, + "a _RangeAdaptor that accepts only one argument " + "should be defined as a _RangeAdaptorClosure"); + return _Callable{}(std::forward<_Args>(__args)...); + } + else + { + auto __closure = [__args...] <typename _Range> (_Range&& __r) { + return _Callable{}(std::forward<_Range>(__r), __args...); + }; + using _ClosureType = decltype(__closure); + return _RangeAdaptorClosure<_ClosureType>(std::move(__closure)); + } + } + }; + + template<typename _Callable> + struct _RangeAdaptorClosure : public _RangeAdaptor<_Callable> + { + using _RangeAdaptor<_Callable>::_RangeAdaptor; + + template<viewable_range _Range> + requires requires { declval<_Callable>()(declval<_Range>()); } + constexpr auto + operator()(_Range&& __r) const + { + if constexpr (is_default_constructible_v<_Callable>) + return _Callable{}(std::forward<_Range>(__r)); + else + return this->_M_callable(std::forward<_Range>(__r)); + } + + template<viewable_range _Range> + requires requires { declval<_Callable>()(declval<_Range>()); } + friend constexpr auto + operator|(_Range&& __r, const _RangeAdaptorClosure& __o) + { return __o(std::forward<_Range>(__r)); } + + template<typename _Tp> + friend constexpr auto + operator|(const _RangeAdaptorClosure<_Tp>& __x, + const _RangeAdaptorClosure& __y) + { + if constexpr (is_default_constructible_v<_Tp> + && is_default_constructible_v<_Callable>) + { + auto __closure = [] <typename _Up> (_Up&& __e) { + return std::forward<_Up>(__e) | decltype(__x){} | decltype(__y){}; + }; + return _RangeAdaptorClosure<decltype(__closure)>(__closure); + } + else if constexpr (is_default_constructible_v<_Tp> + && !is_default_constructible_v<_Callable>) + { + auto __closure = [__y] <typename _Up> (_Up&& __e) { + return std::forward<_Up>(__e) | decltype(__x){} | __y; + }; + return _RangeAdaptorClosure<decltype(__closure)>(__closure); + } + else if constexpr (!is_default_constructible_v<_Tp> + && is_default_constructible_v<_Callable>) + { + auto __closure = [__x] <typename _Up> (_Up&& __e) { + return std::forward<_Up>(__e) | __x | decltype(__y){}; + }; + return _RangeAdaptorClosure<decltype(__closure)>(__closure); + } + else + { + auto __closure = [__x, __y] <typename _Up> (_Up&& __e) { + return std::forward<_Up>(__e) | __x | __y; + }; + return _RangeAdaptorClosure<decltype(__closure)>(__closure); + } + } + }; + template<typename _Callable> + _RangeAdaptorClosure(_Callable) -> _RangeAdaptorClosure<_Callable>; } // namespace views + + template<range _Range> requires is_object_v<_Range> + class ref_view : public view_interface<ref_view<_Range>> + { + private: + _Range* _M_r = nullptr; + + static void _S_fun(_Range&); // not defined + static void _S_fun(_Range&&) = delete; + + public: + constexpr + ref_view() noexcept = default; + + 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)))) + { } + + constexpr _Range& + base() const + { return *_M_r; } + + constexpr iterator_t<_Range> + begin() const + { return ranges::begin(*_M_r); } + + constexpr sentinel_t<_Range> + end() const + { return ranges::end(*_M_r); } + + constexpr bool + empty() const requires requires { ranges::empty(*_M_r); } + { return ranges::empty(*_M_r); } + + constexpr auto + size() const requires sized_range<_Range> + { return ranges::size(*_M_r); } + + constexpr auto + data() const requires contiguous_range<_Range> + { return ranges::data(*_M_r); } + }; + + template<typename _Range> + ref_view(_Range&) -> ref_view<_Range>; + + template<typename _Tp> + inline constexpr bool enable_safe_range<ref_view<_Tp>> = true; + + namespace views + { + inline constexpr _RangeAdaptorClosure all + = [] <viewable_range _Range> (_Range&& __r) + { + if constexpr (view<decay_t<_Range>>) + return std::forward<_Range>(__r); + else if constexpr (requires { ref_view{std::forward<_Range>(__r)}; }) + return ref_view{std::forward<_Range>(__r)}; + else + return subrange{std::forward<_Range>(__r)}; + }; + } // namespace views + + template<viewable_range _Range> + using all_view = decltype(views::all(declval<_Range>())); + + // XXX: the following algos are copied verbatim from ranges_algo.h to avoid a + // circular dependency with that header. + 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)); + } + + 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)); + } + + 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 + { + [[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)}; + } + }; + + template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, + input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + typename _Pred = ranges::equal_to, + typename _Proj1 = identity, typename _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + constexpr mismatch_result<_Iter1, _Iter2> + mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) + { + while (__first1 != __last1 && __first2 != __last2 + && (bool)std::__invoke(__pred, + std::__invoke(__proj1, *__first1), + std::__invoke(__proj2, *__first2))) + { + ++__first1; + ++__first2; + } + return { std::move(__first1), std::move(__first2) }; + } + } // namespace __detail + + template<input_range _Vp, + indirect_unary_predicate<iterator_t<_Vp>> _Pred> + requires view<_Vp> && is_object_v<_Pred> + class filter_view : public view_interface<filter_view<_Vp, _Pred>> + { + private: + struct _Sentinel; + + struct _Iterator + { + private: + static constexpr auto + _S_iter_concept() + { + if constexpr (bidirectional_range<_Vp>) + return bidirectional_iterator_tag{}; + else if constexpr (forward_range<_Vp>) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + + static constexpr auto + _S_iter_cat() + { + using _Cat = iterator_traits<iterator_t<_Vp>>::iterator_category; + if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) + return bidirectional_iterator_tag{}; + else if constexpr (derived_from<_Cat, forward_iterator_tag>) + return forward_iterator_tag{}; + else + return _Cat{}; + } + + friend filter_view; + + iterator_t<_Vp> _M_current = iterator_t<_Vp>(); + filter_view* _M_parent = nullptr; + + public: + using iterator_concept = decltype(_S_iter_concept()); + using iterator_category = decltype(_S_iter_cat()); + using value_type = range_value_t<_Vp>; + using difference_type = range_difference_t<_Vp>; + + _Iterator() = default; + + constexpr + _Iterator(filter_view& __parent, iterator_t<_Vp> __current) + : _M_current(std::move(__current)), + _M_parent(addressof(__parent)) + { } + + 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)); + return *this; + } + + constexpr _Iterator + operator--(int) requires bidirectional_range<_Vp> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + requires equality_comparable<iterator_t<_Vp>> + { return __x._M_current == __y._M_current; } + + friend constexpr range_rvalue_reference_t<_Vp> + iter_move(const _Iterator& __i) + noexcept(noexcept(ranges::iter_move(__i._M_current))) + { return ranges::iter_move(__i._M_current); } + + friend constexpr void + iter_swap(const _Iterator& __x, const _Iterator& __y) + noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current))) + requires indirectly_swappable<iterator_t<_Vp>> + { ranges::iter_swap(__x._M_current, __y._M_current); } + }; + + struct _Sentinel + { + private: + sentinel_t<_Vp> _M_end = sentinel_t<_Vp>(); + + constexpr bool + __equal(const _Iterator& __i) const + { return __i._M_current == _M_end; } + + public: + _Sentinel() = default; + + constexpr explicit + _Sentinel(filter_view& __parent) + : _M_end(ranges::end(__parent._M_base)) + { } + + constexpr sentinel_t<_Vp> + base() const + { return _M_end; } + + friend constexpr bool + operator==(const _Iterator& __x, const _Sentinel& __y) + { return __y.__equal(__x); } + }; + + _Vp _M_base = _Vp(); + __detail::__box<_Pred> _M_pred; + + public: + filter_view() = default; + + constexpr + filter_view(_Vp __base, _Pred __pred) + : _M_base(std::move(__base)), _M_pred(std::move(__pred)) + { } + + /* XXX: P3280 removes this constructor + template<input_range _Range> + requires viewable_range<_Range> + && constructible_from<_Vp, all_view<_Range>> + constexpr + filter_view(_Range&& __r, _Pred __pred) + : _M_base(views::all(std::forward<_Range>(__r))), + _M_pred(std::move(__pred)) + { } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + 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))}; + } + + constexpr auto + end() + { + if constexpr (common_range<_Vp>) + return _Iterator{*this, ranges::end(_M_base)}; + else + return _Sentinel{*this}; + } + }; + + template<typename _Range, typename _Pred> + filter_view(_Range&&, _Pred) -> filter_view<all_view<_Range>, _Pred>; + + namespace views + { + inline constexpr _RangeAdaptor filter + = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p) + { + return filter_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)}; + }; + } // namespace views + + template<input_range _Vp, copy_constructible _Fp> + requires view<_Vp> && is_object_v<_Fp> + && regular_invocable<_Fp&, range_reference_t<_Vp>> + class transform_view : public view_interface<transform_view<_Vp, _Fp>> + { + private: + template<bool _Const> + struct _Sentinel; + + template<bool _Const> + struct _Iterator + { + private: + using _Parent + = conditional_t<_Const, const transform_view, transform_view>; + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + static constexpr auto + _S_iter_concept() + { + if constexpr (random_access_range<_Vp>) + return random_access_iterator_tag{}; + else if constexpr (bidirectional_range<_Vp>) + return bidirectional_iterator_tag{}; + else if constexpr (forward_range<_Vp>) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + + static constexpr auto + _S_iter_cat() + { + using _Cat = iterator_traits<iterator_t<_Vp>>::iterator_category; + if constexpr (derived_from<_Cat, contiguous_iterator_tag>) + return random_access_iterator_tag{}; + else + return _Cat{}; + } + + static constexpr decltype(auto) + __iter_move(const _Iterator& __i = {}) + noexcept(noexcept(invoke(*__i._M_parent->_M_fun, *__i._M_current))) + { + if constexpr (is_lvalue_reference_v<decltype(*__i)>) + return std::move(*__i); + else + return *__i; + } + + iterator_t<_Base> _M_current = iterator_t<_Base>(); + _Parent* _M_parent = nullptr; + + public: + using iterator_concept = decltype(_S_iter_concept()); + using iterator_category = decltype(_S_iter_cat()); + using value_type + = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>; + using difference_type = range_difference_t<_Base>; + + _Iterator() = default; + + constexpr + _Iterator(_Parent& __parent, iterator_t<_Base> __current) + : _M_current(std::move(__current)), _M_parent(addressof(__parent)) + { } + + constexpr + _Iterator(_Iterator<!_Const> __i) + requires _Const + && convertible_to<iterator_t<_Vp>, iterator_t<_Base>> + : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent) + { } + + constexpr iterator_t<_Base> + base() const & + requires copyable<iterator_t<_Base>> + { return _M_current; } + + constexpr iterator_t<_Base> + base() && + { return std::move(_M_current); } + + constexpr decltype(auto) + operator*() const + { return invoke(*_M_parent->_M_fun, *_M_current); } + + constexpr _Iterator& + operator++() + { + ++_M_current; + return *this; + } + + constexpr void + operator++(int) + { ++_M_current; } + + constexpr _Iterator + operator++(int) requires forward_range<_Base> + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() requires bidirectional_range<_Base> + { + --_M_current; + return *this; + } + + constexpr _Iterator + operator--(int) requires bidirectional_range<_Base> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + constexpr _Iterator& + operator+=(difference_type __n) requires random_access_range<_Base> + { + _M_current += __n; + return *this; + } + + constexpr _Iterator& + operator-=(difference_type __n) requires random_access_range<_Base> + { + _M_current -= __n; + return *this; + } + + constexpr decltype(auto) + operator[](difference_type __n) const + requires random_access_range<_Base> + { return invoke(*_M_parent->_M_fun, _M_current[__n]); } + + 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 + friend constexpr compare_three_way_result_t<iterator_t<_Base>> + 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 _Iterator + operator+(_Iterator __i, difference_type __n) + requires random_access_range<_Base> + { return {*__i._M_parent, __i._M_current + __n}; } + + friend constexpr _Iterator + operator+(difference_type __n, _Iterator __i) + requires random_access_range<_Base> + { return {*__i._M_parent, __i._M_current + __n}; } + + friend constexpr _Iterator + operator-(_Iterator __i, difference_type __n) + requires random_access_range<_Base> + { return {*__i._M_parent, __i._M_current - __n}; } + + friend constexpr difference_type + operator-(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __x._M_current - __y._M_current; } + + friend constexpr decltype(auto) + iter_move(const _Iterator& __i) noexcept(noexcept(__iter_move())) + { return __iter_move(__i); } + + friend constexpr void + iter_swap(const _Iterator& __x, const _Iterator& __y) + noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current))) + requires indirectly_swappable<iterator_t<_Base>> + { return ranges::iter_swap(__x._M_current, __y._M_current); } + + friend _Sentinel<_Const>; + }; + + template<bool _Const> + struct _Sentinel + { + private: + using _Parent + = conditional_t<_Const, const transform_view, transform_view>; + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + constexpr range_difference_t<_Base> + __distance_from(const _Iterator<_Const>& __i) const + { return _M_end - __i._M_current; } + + constexpr bool + __equal(const _Iterator<_Const>& __i) const + { return __i._M_current == _M_end; } + + sentinel_t<_Base> _M_end = sentinel_t<_Base>(); + + public: + _Sentinel() = default; + + constexpr explicit + _Sentinel(sentinel_t<_Base> __end) + : _M_end(__end) + { } + + constexpr + _Sentinel(_Sentinel<!_Const> __i) + requires _Const + && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> + : _M_end(std::move(__i._M_end)) + { } + + constexpr sentinel_t<_Base> + base() const + { return _M_end; } + + friend constexpr bool + operator==(const _Iterator<_Const>& __x, const _Sentinel& __y) + { return __y.__equal(__x); } + + friend constexpr range_difference_t<_Base> + operator-(const _Iterator<_Const>& __x, const _Sentinel& __y) + requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>> + { return -__y.__distance_from(__x); } + + friend constexpr range_difference_t<_Base> + operator-(const _Sentinel& __y, const _Iterator<_Const>& __x) + requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>> + { return __y.__distance_from(__x); } + }; + + _Vp _M_base = _Vp(); + __detail::__box<_Fp> _M_fun; + + public: + transform_view() = default; + + constexpr + transform_view(_Vp __base, _Fp __fun) + : _M_base(std::move(__base)), _M_fun(std::move(__fun)) + { } + + /* XXX: P3280 removes this constructor + template<input_range _Range> + requires viewable_range<_Range> + && constructible_from<_Vp, all_view<_Range>> + constexpr + transform_view(_Range&& __r, _Fp __fun) + : _M_base(views::all(std::forward<_Range>(__r))) + { + } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base ; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr _Iterator<false> + begin() + { return _Iterator<false>{*this, ranges::begin(_M_base)}; } + + constexpr _Iterator<true> + begin() const + requires range<const _Vp> + && regular_invocable<const _Fp&, range_reference_t<const _Vp>> + { return _Iterator<true>{*this, ranges::begin(_M_base)}; } + + constexpr _Sentinel<false> + end() + { return _Sentinel<false>{ranges::end(_M_base)}; } + + constexpr _Iterator<false> + end() requires common_range<_Vp> + { return _Iterator<false>{*this, ranges::end(_M_base)}; } + + constexpr _Sentinel<true> + end() const + requires range<const _Vp> + && regular_invocable<const _Fp&, range_reference_t<const _Vp>> + { return _Sentinel<true>{ranges::end(_M_base)}; } + + constexpr _Iterator<true> + end() const + requires common_range<const _Vp> + && regular_invocable<const _Fp&, range_reference_t<const _Vp>> + { return _Iterator<true>{*this, ranges::end(_M_base)}; } + + constexpr auto + size() requires sized_range<_Vp> + { return ranges::size(_M_base); } + + constexpr auto + size() const requires sized_range<const _Vp> + { return ranges::size(_M_base); } + }; + + template<typename _Range, typename _Fp> + transform_view(_Range&&, _Fp) -> transform_view<all_view<_Range>, _Fp>; + + namespace views + { + inline constexpr _RangeAdaptor transform + = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f) + { + return transform_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)}; + }; + } // namespace views + + template<view _Vp> + class take_view : public view_interface<take_view<_Vp>> + { + private: + template<bool _Const> + struct _Sentinel + { + private: + using _Base = conditional_t<_Const, const _Vp, _Vp>; + using _CI = counted_iterator<iterator_t<_Base>>; + + sentinel_t<_Base> _M_end = sentinel_t<_Base>(); + + public: + _Sentinel() = default; + + constexpr explicit + _Sentinel(sentinel_t<_Base> __end) + : _M_end(__end) + { } + + constexpr + _Sentinel(_Sentinel<!_Const> __s) + requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> + : _M_end(std::move(__s._M_end)) + { } + + constexpr sentinel_t<_Base> + base() const + { return _M_end; } + + friend constexpr bool operator==(const _CI& __y, const _Sentinel& __x) + { return __y.count() == 0 || __y.base() == __x._M_end; } + }; + + _Vp _M_base = _Vp(); + range_difference_t<_Vp> _M_count = 0; + + public: + take_view() = default; + + constexpr + take_view(_Vp base, range_difference_t<_Vp> __count) + : _M_base(std::move(base)), _M_count(std::move(__count)) + { } + + /* XXX: P3280 removes this constructor + template<viewable_range _Range> + requires constructible_from<_Vp, all_view<_Range>> + constexpr + take_view(_Range&& __r, range_difference_t<_Vp> __count) + : _M_base(views::all(std::forward<_Range>(__r))), _M_count(__count) + { } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() requires (!__detail::__simple_view<_Vp>) + { + if constexpr (sized_range<_Vp>) { + if constexpr (random_access_range<_Vp>) + return ranges::begin(_M_base); + else + return counted_iterator{ranges::begin(_M_base), size()}; + } else + return counted_iterator{ranges::begin(_M_base), _M_count}; + } + + constexpr auto + begin() const requires range<const _Vp> + { + if constexpr (sized_range<const _Vp>) { + if constexpr (random_access_range<const _Vp>) + return ranges::begin(_M_base); + else + return counted_iterator{ranges::begin(_M_base), size()}; + } else + return counted_iterator{ranges::begin(_M_base), _M_count}; + } + + constexpr auto + end() requires (!__detail::__simple_view<_Vp>) + { + if constexpr (sized_range<_Vp>) { + if constexpr (random_access_range<_Vp>) + return ranges::begin(_M_base) + size(); + else + return default_sentinel; + } else + return _Sentinel<false>{ranges::end(_M_base)}; + } + + constexpr auto + end() const requires range<const _Vp> + { + if constexpr (sized_range<const _Vp>) { + if constexpr (random_access_range<const _Vp>) + return ranges::begin(_M_base) + size(); + else + return default_sentinel; + } else + return _Sentinel<true>{ranges::end(_M_base)}; + } + + constexpr auto + size() requires sized_range<_Vp> + { + auto __n = ranges::size(_M_base); + return __detail::min(__n, static_cast<decltype(__n)>(_M_count)); + } + + constexpr auto + size() const requires sized_range<const _Vp> + { + auto __n = ranges::size(_M_base); + return __detail::min(__n, static_cast<decltype(__n)>(_M_count)); + } + }; + + template<range _Range> + take_view(_Range&&, range_difference_t<_Range>) + -> take_view<all_view<_Range>>; + + namespace views + { + inline constexpr _RangeAdaptor take + = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n) + { + return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)}; + }; + } // namespace views + + template<view _Vp, typename _Pred> + requires input_range<_Vp> && is_object_v<_Pred> + && indirect_unary_predicate<const _Pred, iterator_t<_Vp>> + class take_while_view : public view_interface<take_while_view<_Vp, _Pred>> + { + template<bool _Const> + struct _Sentinel + { + private: + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + sentinel_t<_Base> _M_end = sentinel_t<_Base>(); + const _Pred* _M_pred = nullptr; + + public: + _Sentinel() = default; + + constexpr explicit + _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred) + : _M_end(__end), _M_pred(__pred) + { } + + constexpr + _Sentinel(_Sentinel<!_Const> __s) + requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> + : _M_end(__s._M_end), _M_pred(__s._M_pred) + { } + + constexpr sentinel_t<_Base> + base() const { return _M_end; } + + friend constexpr bool + operator==(const iterator_t<_Base>& __x, const _Sentinel& __y) + { return __y._M_end == __x || !invoke(*__y._M_pred, *__x); } + }; + + _Vp _M_base; + __detail::__box<_Pred> _M_pred; + + public: + take_while_view() = default; + + constexpr + take_while_view(_Vp base, _Pred __pred) + : _M_base(std::move(base)), _M_pred(std::move(__pred)) + { + } + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr const _Pred& + pred() const + { return *_M_pred; } + + constexpr auto + begin() requires (!__detail::__simple_view<_Vp>) + { return ranges::begin(_M_base); } + + constexpr auto + begin() const requires range<const _Vp> + { return ranges::begin(_M_base); } + + constexpr auto + end() requires (!__detail::__simple_view<_Vp>) + { return _Sentinel<false>(ranges::end(_M_base), + addressof(*_M_pred)); } + + constexpr auto + end() const requires range<const _Vp> + { return _Sentinel<true>(ranges::end(_M_base), + addressof(*_M_pred)); } + }; + + template<typename _Range, typename _Pred> + take_while_view(_Range&&, _Pred) + -> take_while_view<all_view<_Range>, _Pred>; + + namespace views + { + inline constexpr _RangeAdaptor take_while + = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p) + { + 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); } + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() requires (!(__detail::__simple_view<_Vp> + && random_access_range<_Vp>)) + { + // XXX: we need to cache the result here as per [range.drop.view] + return ranges::next(ranges::begin(_M_base), _M_count, + ranges::end(_M_base)); + } + + constexpr auto + begin() const requires random_access_range<const _Vp> + { + return ranges::next(ranges::begin(_M_base), _M_count, + ranges::end(_M_base)); + } + + constexpr auto + end() requires (!__detail::__simple_view<_Vp>) + { return ranges::end(_M_base); } + + constexpr auto + end() const requires range<const _Vp> + { return ranges::end(_M_base); } + + constexpr auto + size() requires sized_range<_Vp> + { + const auto __s = ranges::size(_M_base); + const auto __c = static_cast<decltype(__s)>(_M_count); + return __s < __c ? 0 : __s - __c; + } + + constexpr auto + size() const requires sized_range<const _Vp> + { + const auto __s = ranges::size(_M_base); + const auto __c = static_cast<decltype(__s)>(_M_count); + return __s < __c ? 0 : __s - __c; + } + }; + + template<typename _Range> + drop_view(_Range&&, range_difference_t<_Range>) + -> drop_view<all_view<_Range>>; + + namespace views + { + inline constexpr _RangeAdaptor drop + = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n) + { + return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)}; + }; + } // namespace views + + template<view _Vp, typename _Pred> + requires input_range<_Vp> && is_object_v<_Pred> + && indirect_unary_predicate<const _Pred, iterator_t<_Vp>> + class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>> + { + private: + _Vp _M_base; + __detail::__box<_Pred> _M_pred; + + public: + drop_while_view() = default; + + constexpr + drop_while_view(_Vp __base, _Pred __pred) + : _M_base(std::move(__base)), _M_pred(std::move(__pred)) + { } + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr const _Pred& + pred() const + { return *_M_pred; } + + 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)); + } + + constexpr auto + end() + { return ranges::end(_M_base); } + }; + + template<typename _Range, typename _Pred> + drop_while_view(_Range&&, _Pred) + -> drop_while_view<all_view<_Range>, _Pred>; + + namespace views + { + inline constexpr _RangeAdaptor drop_while + = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p) + { + return drop_while_view{std::forward<_Range>(__r), + std::forward<_Pred>(__p)}; + }; + } // namespace views + + template<input_range _Vp> + requires view<_Vp> && input_range<range_reference_t<_Vp>> + && (is_reference_v<range_reference_t<_Vp>> + || view<range_value_t<_Vp>>) + class join_view : public view_interface<join_view<_Vp>> + { + private: + using _InnerRange = range_reference_t<_Vp>; + + template<bool _Const> + struct _Sentinel; + + template<bool _Const> + struct _Iterator + { + private: + using _Parent = conditional_t<_Const, const join_view, join_view>; + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + static constexpr bool _S_ref_is_glvalue + = is_reference_v<range_reference_t<_Base>>; + + constexpr void + _M_satisfy() + { + auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto& + { + if constexpr (_S_ref_is_glvalue) + return __x; + else + return (_M_parent->_M_inner = views::all(std::move(__x))); + }; + + for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer) + { + auto& inner = __update_inner(*_M_outer); + _M_inner = ranges::begin(inner); + if (_M_inner != ranges::end(inner)) + return; + } + + if constexpr (_S_ref_is_glvalue) + _M_inner = iterator_t<range_reference_t<_Base>>(); + } + + static constexpr auto + _S_iter_concept() + { + if constexpr (_S_ref_is_glvalue + && bidirectional_range<_Base> + && bidirectional_range<range_reference_t<_Base>>) + return bidirectional_iterator_tag{}; + else if constexpr (_S_ref_is_glvalue + && forward_range<_Base> + && forward_range<range_reference_t<_Base>>) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + + static constexpr auto + _S_iter_cat() + { + using _OuterCat + = iterator_traits<iterator_t<_Base>>::iterator_category; + using _InnerCat + = iterator_traits<iterator_t<range_reference_t<_Base>>> + ::iterator_category; + if constexpr (_S_ref_is_glvalue + && derived_from<_OuterCat, bidirectional_iterator_tag> + && derived_from<_InnerCat, bidirectional_iterator_tag>) + return bidirectional_iterator_tag{}; + else if constexpr (_S_ref_is_glvalue + && derived_from<_OuterCat, forward_iterator_tag> + && derived_from<_InnerCat, forward_iterator_tag>) + return forward_iterator_tag{}; + else if constexpr (derived_from<_OuterCat, input_iterator_tag> + && derived_from<_InnerCat, input_iterator_tag>) + return input_iterator_tag{}; + else + return output_iterator_tag{}; + } + + iterator_t<_Base> _M_outer = iterator_t<_Base>(); + iterator_t<range_reference_t<_Base>> _M_inner + = iterator_t<range_reference_t<_Base>>(); + _Parent* _M_parent = nullptr; + + public: + using iterator_concept = decltype(_S_iter_concept()); + using iterator_category = decltype(_S_iter_cat()); + using value_type = range_value_t<range_reference_t<_Base>>; + using difference_type + = common_type_t<range_difference_t<_Base>, + range_difference_t<range_reference_t<_Base>>>; + + _Iterator() = default; + + // XXX: had to change the type of __outer from iterator_t<_Vp> to + // iterator_t<_Base> here, a possible defect in the spec? + constexpr + _Iterator(_Parent& __parent, iterator_t<_Base> __outer) + : _M_outer(std::move(__outer)), _M_parent(addressof(__parent)) + { _M_satisfy(); } + + constexpr + _Iterator(_Iterator<!_Const> __i) + requires _Const + && convertible_to<iterator_t<_Vp>, iterator_t<_Base>> + && convertible_to<iterator_t<_InnerRange>, + iterator_t<range_reference_t<_Base>>> + : _M_outer(std::move(__i._M_outer)), _M_inner(__i._M_inner), + _M_parent(__i._M_parent) + { } + + constexpr decltype(auto) + operator*() const + { return *_M_inner; } + + constexpr iterator_t<_Base> + operator->() const + requires __detail::__has_arrow<iterator_t<_Base>> + && copyable<iterator_t<_Base>> + { return _M_inner; } + + constexpr _Iterator& + operator++() + { + auto&& __inner_range = [this] () -> decltype(auto) { + if constexpr (_S_ref_is_glvalue) + return *_M_outer; + else + return _M_parent->_M_inner; + }(); + if (++_M_inner == ranges::end(__inner_range)) + { + ++_M_outer; + _M_satisfy(); + } + return *this; + } + + constexpr void + operator++(int) + { ++*this; } + + constexpr _Iterator + operator++(int) + requires _S_ref_is_glvalue && forward_range<_Base> + && forward_range<range_reference_t<_Base>> + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() + requires _S_ref_is_glvalue && bidirectional_range<_Base> + && bidirectional_range<range_reference_t<_Base>> + { + if (_M_outer == ranges::end(_M_parent->_M_base)) + _M_inner = ranges::end(*--_M_outer); + while (_M_inner == ranges::begin(*_M_outer)) + _M_inner = ranges::end(*--_M_outer); + --_M_inner; + return *this; + } + + constexpr _Iterator + operator--(int) + requires _S_ref_is_glvalue && bidirectional_range<_Base> + && bidirectional_range<range_reference_t<_Base>> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + requires _S_ref_is_glvalue + && equality_comparable<iterator_t<_Base>> + && equality_comparable<iterator_t<range_reference_t<_Base>>> + { + return (__x._M_outer == __y._M_outer + && __x._M_inner == __y._M_inner); + } + + friend constexpr decltype(auto) + iter_move(const _Iterator& __i) + noexcept(noexcept(ranges::iter_move(__i._M_inner))) + { return ranges::iter_move(__i._M_inner); } + + friend constexpr void + iter_swap(const _Iterator& __x, const _Iterator& __y) + noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner))) + { return ranges::iter_swap(__x._M_inner, __y._M_inner); } + + friend _Sentinel<_Const>; + }; + + template<bool _Const> + struct _Sentinel + { + private: + using _Parent = conditional_t<_Const, const join_view, join_view>; + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + constexpr bool + __equal(const _Iterator<_Const>& __i) const + { return __i._M_outer == _M_end; } + + sentinel_t<_Base> _M_end = sentinel_t<_Base>(); + + public: + _Sentinel() = default; + + constexpr explicit + _Sentinel(_Parent& __parent) + : _M_end(ranges::end(__parent._M_base)) + { } + + constexpr + _Sentinel(_Sentinel<!_Const> __s) + requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> + : _M_end(std::move(__s._M_end)) + { } + + friend constexpr bool + operator==(const _Iterator<_Const>& __x, const _Sentinel& __y) + { return __y.__equal(__x); } + }; + + _Vp _M_base = _Vp(); + + // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>" + // Applied P3278 and made this field mutable. + [[no_unique_address]] mutable + conditional_t<!is_reference_v<_InnerRange>, + all_view<_InnerRange>, __detail::_Empty> _M_inner; + + public: + join_view() = default; + + constexpr explicit + join_view(_Vp __base) + : _M_base(std::move(__base)) + { } + + /* XXX: P3280 removes this constructor + template<input_range _Range> + requires viewable_range<_Range> + && constructible_from<_Vp, all_view<_Range>> + constexpr explicit + join_view(_Range&& __r) + : _M_base(views::all(std::forward<_Range>(__r))) + { } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() + { + return _Iterator<__detail::__simple_view<_Vp>>{*this, + ranges::begin(_M_base)}; + } + + constexpr auto + begin() const + requires input_range<const _Vp> + && is_reference_v<range_reference_t<const _Vp>> + { + return _Iterator<true>{*this, ranges::begin(_M_base)}; + } + + constexpr auto + end() + { + if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange> + && forward_range<_InnerRange> + && common_range<_Vp> && common_range<_InnerRange>) + return _Iterator<__detail::__simple_view<_Vp>>{*this, + ranges::end(_M_base)}; + else + return _Sentinel<__detail::__simple_view<_Vp>>{*this}; + } + + constexpr auto + end() const + requires input_range<const _Vp> + && is_reference_v<range_reference_t<const _Vp>> + { + if constexpr (forward_range<const _Vp> + && is_reference_v<range_reference_t<const _Vp>> + && forward_range<range_reference_t<const _Vp>> + && common_range<const _Vp> + && common_range<range_reference_t<const _Vp>>) + return _Iterator<true>{*this, ranges::end(_M_base)}; + else + return _Sentinel<true>{*this}; + } + }; + + template<typename _Range> + explicit join_view(_Range&&) -> join_view<all_view<_Range>>; + + namespace views + { + inline constexpr _RangeAdaptorClosure join + = [] <viewable_range _Range> (_Range&& __r) + { + return join_view{std::forward<_Range>(__r)}; + }; + } // namespace views + + namespace __detail + { + template<auto> + struct __require_constant; + + template<typename _Range> + concept __tiny_range = sized_range<_Range> + && requires + { typename __require_constant<remove_reference_t<_Range>::size()>; } + && (remove_reference_t<_Range>::size() <= 1); + } + + template<input_range _Vp, forward_range _Pattern> + requires view<_Vp> && view<_Pattern> + && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>, + ranges::equal_to> + && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>) + class split_view : public view_interface<split_view<_Vp, _Pattern>> + { + private: + template<bool _Const> + struct _InnerIter; + + template<bool _Const> + struct _OuterIter + { + private: + using _Parent = conditional_t<_Const, const split_view, split_view>; + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + constexpr bool + __at_end() const + { return _M_current == ranges::end(_M_parent->_M_base); } + + // XXX: [24.7.11.3.1] + // Many of the following specifications refer to the notional member + // current of outer-iterator. current is equivalent to current_ if + // V models forward_range, and parent_->current_ otherwise. + constexpr auto& + __current() + { + if constexpr (forward_range<_Vp>) + return _M_current; + else + return _M_parent->_M_current; + } + + constexpr auto& + __current() const + { + if constexpr (forward_range<_Vp>) + return _M_current; + else + return _M_parent->_M_current; + } + + _Parent* _M_parent = nullptr; + + // XXX: _M_current is present only if "V models forward_range" + [[no_unique_address]] + conditional_t<forward_range<_Vp>, + iterator_t<_Base>, __detail::_Empty> _M_current; + + public: + using iterator_concept = conditional_t<forward_range<_Base>, + forward_iterator_tag, + input_iterator_tag>; + using iterator_category = input_iterator_tag; + using difference_type = range_difference_t<_Base>; + + struct value_type : view_interface<value_type> + { + private: + _OuterIter _M_i = _OuterIter(); + + public: + value_type() = default; + + constexpr explicit + value_type(_OuterIter __i) + : _M_i(std::move(__i)) + { } + + constexpr _InnerIter<_Const> + begin() const + requires copyable<_OuterIter> + { return _InnerIter<_Const>{_M_i}; } + + constexpr _InnerIter<_Const> + begin() + requires (!copyable<_OuterIter>) + { return _InnerIter<_Const>{std::move(_M_i)}; } + + constexpr default_sentinel_t + end() const + { return default_sentinel; } + }; + + _OuterIter() = default; + + constexpr explicit + _OuterIter(_Parent& __parent) requires (!forward_range<_Base>) + : _M_parent(address(__parent)) + { } + + constexpr + _OuterIter(_Parent& __parent, iterator_t<_Base> __current) + requires forward_range<_Base> + : _M_parent(addressof(__parent)), _M_current(std::move(__current)) + { } + + constexpr + _OuterIter(_OuterIter<!_Const> __i) + requires _Const + && convertible_to<iterator_t<_Vp>, iterator_t<const _Vp>> + : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current)) + { } + + constexpr value_type + operator*() const + { return value_type{*this}; } + + constexpr _OuterIter& + operator++() + { + const auto __end = ranges::end(_M_parent->_M_base); + if (_M_current == __end) + return *this; + const auto __pbegin = ranges::begin(_M_parent->_M_pattern); + const auto __pend = ranges::end(_M_parent->_M_pattern); + if (__pbegin == __pend) + ++_M_current; + else + do + { + auto [__b, __p] + = __detail::mismatch(std::move(_M_current), __end, + __pbegin, __pend); + _M_current = std::move(__b); + if (__p == __pend) + break; + } while (++_M_current != __end); + return *this; + } + + constexpr decltype(auto) + operator++(int) + { + if constexpr (forward_range<_Base>) + { + auto __tmp = *this; + ++*this; + return __tmp; + } + else + ++*this; + } + + friend constexpr bool + operator==(const _OuterIter& __x, const _OuterIter& __y) + requires forward_range<_Base> + { return __x._M_current == __y._M_current; } + + friend constexpr bool + operator==(const _OuterIter& __x, default_sentinel_t) + { return __x.__at_end(); }; + + friend _InnerIter<_Const>; + }; + + template<bool _Const> + struct _InnerIter + { + private: + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + constexpr bool + __at_end() const + { + // XXX: the spec says + // auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern}; + // but a subrange cannot be decomposed with a structured binding + auto& __pattern = _M_i._M_parent->_M_pattern; + auto __pcur = ranges::begin(__pattern); + auto __pend = ranges::end(__pattern); + + auto __end = ranges::end(_M_i._M_parent->_M_base); + if constexpr (__detail::__tiny_range<_Pattern>) + { + const auto& __cur = _M_i.__current(); + if (__cur == __end) + return true; + if (__pcur == __pend) + return _M_incremented; + return *__cur == *__pcur; + } + else + { + auto __cur = _M_i.__current(); + if (__cur == __end) + return true; + if (__pcur == __pend) + return _M_incremented; + do + { + if (*__cur != *__pcur) + return false; + if (++__pcur == __pend) + return true; + } while (++__cur != __end); + return false; + } + } + + static constexpr auto + _S_iter_cat() + { + using _Cat = iterator_traits<iterator_t<_Base>>::iterator_category; + if constexpr (derived_from<_Cat, forward_iterator_tag>) + return forward_iterator_tag{}; + else + return _Cat{}; + } + + static constexpr decltype(auto) + __iter_move(const _InnerIter& __i = {}) + noexcept(noexcept(ranges::iter_move(__i._M_i.__current()))) + { return ranges::iter_move(__i._M_i.__current()); } + + static constexpr void + __iter_swap(const _InnerIter& __x = {}, const _InnerIter& __y = {}) + noexcept(noexcept(ranges::iter_swap(__x._M_i.__current(), + __y._M_i.__current()))) + { ranges::iter_swap(__x._M_i.__current(), __y._M_i.__current()); } + + _OuterIter<_Const> _M_i = _OuterIter<_Const>(); + bool _M_incremented = false; + + public: + using iterator_concept = typename _OuterIter<_Const>::iterator_concept; + using iterator_category = decltype(_S_iter_cat()); + using value_type = range_value_t<_Base>; + using difference_type = range_difference_t<_Base>; + + _InnerIter() = default; + + constexpr explicit + _InnerIter(_OuterIter<_Const> __i) + : _M_i(std::move(__i)) + { } + + constexpr decltype(auto) + operator*() const + { return *_M_i._M_current; } + + constexpr _InnerIter& + operator++() + { + _M_incremented = true; + if constexpr (!forward_range<_Base>) + if constexpr (_Pattern::size() == 0) + return *this; + ++_M_i.__current(); + return *this; + } + + constexpr decltype(auto) + operator++(int) + { + if constexpr (forward_range<_Vp>) + { + auto __tmp = *this; + ++*this; + return __tmp; + } + else + ++*this; + } + + friend constexpr bool + operator==(const _InnerIter& __x, const _InnerIter& __y) + requires forward_range<_Base> + { return __x._M_i.__current() == __y._M_i.__current(); } + + friend constexpr bool + operator==(const _InnerIter& __x, default_sentinel_t) + { return __x.__at_end(); } + + friend constexpr decltype(auto) + iter_move(const _InnerIter& __i) noexcept(noexcept(__iter_move())) + { return __iter_move(__i); } + + friend constexpr void + iter_swap(const _InnerIter& __x, const _InnerIter& __y) + noexcept(noexcept(__iter_swap())) + requires indirectly_swappable<iterator_t<_Base>> + { __iter_swap(__x, __y); } + }; + + _Vp _M_base = _Vp(); + _Pattern _M_pattern = _Pattern(); + + // XXX: _M_current is "present only if !forward_range<V>" + [[no_unique_address]] + conditional_t<!forward_range<_Vp>, + iterator_t<_Vp>, __detail::_Empty> _M_current; + + + public: + split_view() = default; + + constexpr + split_view(_Vp __base, _Pattern __pattern) + : _M_base(std::move(__base)), _M_pattern(std::move(__pattern)) + { } + + /* XXX: P3280 removes this constructor + template<input_range _Range, forward_range _Pred> + requires constructible_from<_Vp, all_view<_Range>> + && constructible_from<_Pattern, all_view<_Pred>> + constexpr + split_view(_Range&& __r, _Pred&& __p) + : _M_base(views::all(std::forward<_Range>(__r))), + _M_pattern(views::all(std::forward<_Pred>(__p))) + { } + */ + + template<input_range _Range> + requires constructible_from<_Vp, all_view<_Range>> + && constructible_from<_Pattern, single_view<range_value_t<_Range>>> + constexpr + split_view(_Range&& __r, range_value_t<_Range> __e) + : _M_base(views::all(std::forward<_Range>(__r))), + _M_pattern(std::move(__e)) + { } + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() + { + if constexpr (forward_range<_Vp>) + return _OuterIter<__detail::__simple_view<_Vp>>{*this, + ranges::begin(_M_base)}; + else + { + _M_current = ranges::begin(_M_base); + return _OuterIter<false>{*this}; + } + } + + constexpr auto + begin() const requires forward_range<_Vp> && forward_range<const _Vp> + { + return _OuterIter<true>{*this, ranges::begin(_M_base)}; + } + + constexpr auto + end() requires forward_range<_Vp> && common_range<_Vp> + { + return _OuterIter<__detail::__simple_view<_Vp>>{*this, ranges::end(_M_base)}; + } + + constexpr auto + end() const + { + if constexpr (forward_range<_Vp> + && forward_range<const _Vp> + && common_range<const _Vp>) + return _OuterIter<true>{*this, ranges::end(_M_base)}; + else + return default_sentinel; + } + }; + + template<typename _Range, typename _Pred> + split_view(_Range&&, _Pred&&) + -> split_view<all_view<_Range>, all_view<_Pred>>; + + template<input_range _Range> + split_view(_Range&&, range_value_t<_Range>) + -> split_view<all_view<_Range>, single_view<range_value_t<_Range>>>; + + namespace views + { + inline constexpr _RangeAdaptor split + = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f) + { + return split_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)}; + }; + } // namespace views + + namespace views + { + struct _Counted + { + template<input_or_output_iterator _Iter> + constexpr auto + operator()(_Iter __i, iter_difference_t<_Iter> __n) const + { + if constexpr (random_access_iterator<_Iter>) + return subrange{__i, __i + __n}; + else + return subrange{counted_iterator{__i, __n}, default_sentinel}; + } + }; + + inline constexpr _Counted counted{}; + } // namespace views + + template<view _Vp> + requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>> + class common_view : public view_interface<common_view<_Vp>> + { + private: + _Vp _M_base = _Vp(); + + public: + common_view() = default; + + constexpr explicit + common_view(_Vp __r) + : _M_base(std::move(__r)) + { } + + /* XXX: P3280 doesn't remove this constructor, but I think it should? + template<viewable_range _Range> + requires (!common_range<_Range>) && constructible_from<_Vp, all_view<_Range>> + constexpr explicit + common_view(_Range&& __r) + : _M_base(views::all(std::forward<_Range>(__r))) + { } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() + { + if constexpr (random_access_range<_Vp> && sized_range<_Vp>) + return ranges::begin(_M_base); + else + return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>> + (ranges::begin(_M_base)); + } + + constexpr auto + begin() const requires range<const _Vp> + { + if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>) + return ranges::begin(_M_base); + else + return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>> + (ranges::begin(_M_base)); + } + + constexpr auto + end() + { + if constexpr (random_access_range<_Vp> && sized_range<_Vp>) + return ranges::begin(_M_base) + ranges::size(_M_base); + else + return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>> + (ranges::end(_M_base)); + } + + constexpr auto + end() const requires range<const _Vp> + { + if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>) + return ranges::begin(_M_base) + ranges::size(_M_base); + else + return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>> + (ranges::end(_M_base)); + } + + constexpr auto + size() requires sized_range<_Vp> + { return ranges::size(_M_base); } + + constexpr auto + size() const requires sized_range<const _Vp> + { return ranges::size(_M_base); } + }; + + template<typename _Range> + common_view(_Range&&) -> common_view<all_view<_Range>>; + + namespace views + { + inline constexpr _RangeAdaptorClosure common + = [] <viewable_range _Range> (_Range&& __r) + { + if constexpr (common_range<_Range> + && requires { views::all(std::forward<_Range>(__r)); }) + return views::all(std::forward<_Range>(__r)); + else + return common_view{std::forward<_Range>(__r)}; + }; + + } // namespace views + + template<view _Vp> + requires bidirectional_range<_Vp> + class reverse_view : public view_interface<reverse_view<_Vp>> + { + private: + _Vp _M_base = _Vp(); + + public: + reverse_view() = default; + + constexpr explicit + reverse_view(_Vp __r) + : _M_base(std::move(__r)) + { } + + /* XXX: P3280 removes this constructor + template<viewable_range _Range> + requires bidirectional_range<_Range> && constructible_from<_Vp, all_view<_Range>> + constexpr explicit + reverse_view(_Range&& __r) + : _M_base(views::all(std::forward<_Range>(__r))) + { } + */ + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr reverse_iterator<iterator_t<_Vp>> + begin() + { + // XXX: we need to cache the result here as per [range.reverse.view] + return make_reverse_iterator(ranges::next(ranges::begin(_M_base), + ranges::end(_M_base))); + } + + constexpr auto + begin() requires common_range<_Vp> + { return make_reverse_iterator(ranges::end(_M_base)); } + + constexpr auto + begin() const requires common_range<const _Vp> + { return make_reverse_iterator(ranges::end(_M_base)); } + + constexpr reverse_iterator<iterator_t<_Vp>> + end() + { return make_reverse_iterator(ranges::begin(_M_base)); } + + constexpr auto + end() const requires common_range<const _Vp> + { return make_reverse_iterator(ranges::begin(_M_base)); } + + constexpr auto + size() requires sized_range<_Vp> + { return ranges::size(_M_base); } + + constexpr auto + size() const requires sized_range<const _Vp> + { return ranges::size(_M_base); } + }; + + template<typename _Range> + reverse_view(_Range&&) -> reverse_view<all_view<_Range>>; + + namespace views + { + namespace __detail + { + template<typename> + inline constexpr bool __is_reversible_subrange = false; + + template<typename _Iter, subrange_kind _Kind> + inline constexpr bool + __is_reversible_subrange<subrange<reverse_iterator<_Iter>, + reverse_iterator<_Iter>, + _Kind>> = true; + + template<typename> + inline constexpr bool __is_reverse_view = false; + + template<typename _Vp> + inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true; + } + + 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>&>; + }; + } + + template<input_range _Vp, size_t _Nm> + requires view<_Vp> + && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm> + && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>, + _Nm> + class elements_view : public view_interface<elements_view<_Vp, _Nm>> + { + public: + elements_view() = default; + + constexpr explicit + elements_view(_Vp base) + : _M_base(std::move(base)) + { } + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() requires (!__detail::__simple_view<_Vp>) + { return _Iterator<false>(ranges::begin(_M_base)); } + + constexpr auto + begin() const requires __detail::__simple_view<_Vp> + { return _Iterator<true>(ranges::begin(_M_base)); } + + constexpr auto + end() requires (!__detail::__simple_view<_Vp>) + { return ranges::end(_M_base); } + + constexpr auto + end() const requires __detail::__simple_view<_Vp> + { return ranges::end(_M_base); } + + constexpr auto + size() requires sized_range<_Vp> + { return ranges::size(_M_base); } + + constexpr auto + size() const requires sized_range<const _Vp> + { return ranges::size(_M_base); } + + private: + template<bool _Const> + struct _Iterator + { + using _Base = conditional_t<_Const, const _Vp, _Vp>; + + iterator_t<_Base> _M_current; + + friend _Iterator<!_Const>; + + public: + using iterator_category + = typename iterator_traits<iterator_t<_Base>>::iterator_category; + using value_type + = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>; + using difference_type = range_difference_t<_Base>; + + _Iterator() = default; + + constexpr explicit + _Iterator(iterator_t<_Base> current) + : _M_current(std::move(current)) + { } + + constexpr + _Iterator(_Iterator<!_Const> i) + requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>> + : _M_current(std::move(i._M_current)) + { } + + constexpr iterator_t<_Base> + base() const& + requires copyable<iterator_t<_Base>> + { return _M_current; } + + constexpr iterator_t<_Base> + base() && + { return std::move(_M_current); } + + constexpr decltype(auto) + operator*() const + { return get<_Nm>(*_M_current); } + + constexpr _Iterator& + operator++() + { + ++_M_current; + return *this; + } + + constexpr void + operator++(int) requires (!forward_range<_Base>) + { ++_M_current; } + + constexpr _Iterator + operator++(int) requires forward_range<_Base> + { + auto __tmp = *this; + ++_M_current; + return __tmp; + } + + constexpr _Iterator& + operator--() requires bidirectional_range<_Base> + { + --_M_current; + return *this; + } + + constexpr _Iterator + operator--(int) requires bidirectional_range<_Base> + { + auto __tmp = *this; + --_M_current; + return __tmp; + } + + constexpr _Iterator& + operator+=(difference_type __n) + requires random_access_range<_Base> + { + _M_current += __n; + return *this; + } + + constexpr _Iterator& + operator-=(difference_type __n) + requires random_access_range<_Base> + { + _M_current -= __n; + return *this; + } + + constexpr decltype(auto) + operator[](difference_type __n) const + requires random_access_range<_Base> + { return get<_Nm>(*(_M_current + __n)); } + + 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 sentinel_t<_Base>& __y) + { return __x._M_current == __y; } + + 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._M_current < __x._M_current; } + + friend constexpr bool + operator<=(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return !(__y._M_current > __x._M_current); } + + friend constexpr bool + operator>=(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return !(__x._M_current > __y._M_current); } + +#ifdef __cpp_lib_threeway_comparison + friend constexpr compare_three_way_result_t<iterator_t<_Base>> + 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 _Iterator + operator+(const _Iterator& __x, difference_type __y) + requires random_access_range<_Base> + { return _Iterator{__x} += __y; } + + friend constexpr _Iterator + operator+(difference_type __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __y + __x; } + + friend constexpr _Iterator + operator-(const _Iterator& __x, difference_type __y) + requires random_access_range<_Base> + { return _Iterator{__x} -= __y; } + + friend constexpr difference_type + operator-(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __x._M_current - __y._M_current; } + + friend constexpr difference_type + operator-(const _Iterator<_Const>& __x, const sentinel_t<_Base>& __y) + requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>> + { return __x._M_current - __y; } + + friend constexpr difference_type + operator-(const sentinel_t<_Base>& __x, const _Iterator<_Const>& __y) + requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>> + { return -(__y - __x); } + }; + + _Vp _M_base = _Vp(); + }; + + template<typename _Range> + using keys_view = elements_view<all_view<_Range>, 0>; + + template<typename _Range> + using values_view = elements_view<all_view<_Range>, 1>; + + namespace views + { + template<size_t _Nm> + inline constexpr _RangeAdaptorClosure elements + = [] <viewable_range _Range> (_Range&& __r) + { + return elements_view<all_view<_Range>, _Nm>{std::forward<_Range>(__r)}; + }; + + inline constexpr _RangeAdaptorClosure keys = elements<0>; + inline constexpr _RangeAdaptorClosure values = elements<1>; + } // namespace views + } // namespace ranges _GLIBCXX_END_NAMESPACE_VERSION } // namespace diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/all.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/all.cc new file mode 100644 index 00000000000..7815475ed24 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/all.cc @@ -0,0 +1,124 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + int x[] = {1,2,3,4,5}; + auto v = views::all(x); + + static_assert(ranges::view<decltype(v)>); + static_assert(ranges::random_access_range<decltype(v)>); + + VERIFY( ranges::size(v) == 5 ); + VERIFY( ranges::size(x | views::all) == 5 ); + VERIFY( ranges::size(v | views::all | views::all) == 5 ); + VERIFY( ranges::size(v | (views::all | views::all)) == 5 ); + + ranges::reverse(v); + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); +} + +void +test02() +{ + int x[5] = { 0 }; + int k = 0; + for (auto&& i : ranges::ref_view{x}) + i += ++k; + VERIFY( ranges::equal(x, (int[]){1,2,3,4,5}) ); +} + +constexpr bool +test03() +{ + std::array ints{0,1,2,3,4,5}; + auto even = [] (int i) { return i%2==0; }; + auto odd = [] (int i) { return i%2==1; }; + auto square = [] (int i) { return i*i; }; + int count = 0; + for (auto v : (ints + | (views::all + | (views::filter(even) + | (views::filter(odd) | views::all))) + | views::transform(square))) + count++; + return count == 0; +} + +constexpr bool +test04() +{ + auto even = [] (int i) { return i%2==0; }; + auto odd = [] (int i) { return i%2==1; }; + auto square = [] (int i) { return i*i; }; + auto increment = [] (int i) { return i+1; }; + auto small = [] (int i) { return i<30; }; + auto non_negative = [] (int i) { return i>=0; }; + auto negative = [] (int i) { return i<0; }; + int count = 0; + return ranges::equal(views::iota(-5) + | views::drop_while(negative) + | views::take_while(non_negative) + | views::transform(increment) + | views::filter(odd) + | views::take(3) + | views::all + | views::transform(square), + views::iota(-5) + | views::drop_while(negative) + | views::drop(1) + | views::filter(odd) + | views::transform(square) + | views::take_while(small) + | views::take_while(small)); +} + +static_assert(std::is_empty_v<decltype(views::common + | views::join + | views::all + | views::common + | views::keys + | views::reverse)>); +static_assert(sizeof(decltype(views::take(5) | views::drop(5))) + == sizeof(decltype(views::take(5) + | views::join + | views::common + | views::all + | views::keys + | views::drop(5) + | views::reverse))); + +int +main() +{ + test01(); + test02(); + static_assert(test03()); + static_assert(test04()); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/common.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/common.cc 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. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + int x[] = {1,2,1,3}; + auto v = x | views::common; + VERIFY( std::count(v.begin(), v.end(), 1) == 2); + static_assert(ranges::common_range<decltype(v)>); + static_assert(ranges::view<decltype(v)>); + static_assert(ranges::random_access_range<decltype(v)>); + static_assert(std::same_as<decltype(v), decltype(views::common(v))>); + + auto v2 = v | (views::common | views::common); + VERIFY( std::count(v2.begin(), v2.end(), 1) == 2); +} + +void +test02() +{ + int x[] = {1,2,1,3}; + test_range<int, forward_iterator_wrapper> rx(x); + auto v = ranges::common_view(rx); + VERIFY( std::count(v.begin(), v.end(), 1) == 2); + static_assert(ranges::common_range<decltype(v)>); + static_assert(ranges::view<decltype(v)>); + static_assert(ranges::forward_range<decltype(v)>); + static_assert(std::same_as<decltype(v), decltype(views::common(v))>); + + auto v2 = v | (views::common | views::common); + VERIFY( std::count(v2.begin(), v2.end(), 1) == 2); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/counted.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/counted.cc new file mode 100644 index 00000000000..c81a8a89741 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/counted.cc @@ -0,0 +1,64 @@ +// Copyright (C) 2019-2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + 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); + static_assert(ranges::view<R>); + static_assert(ranges::sized_range<R>); + static_assert(ranges::common_range<R>); + static_assert(ranges::random_access_range<R>); +} + +void +test02() +{ + int x[] = {0,1,2,3,4,5,0,1,2,3,4,5}; + test_range<int, forward_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>); + static_assert(ranges::sized_range<R>); + static_assert(!ranges::common_range<R>); + static_assert(!ranges::bidirectional_range<R>); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc new file mode 100644 index 00000000000..93fbafcf5a3 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc @@ -0,0 +1,107 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::bidirectional_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + int x[] = {1,2,3,4,5}; + auto v = x | views::drop(3); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(ranges::sized_range<R>); + static_assert(ranges::random_access_range<R>); + VERIFY( ranges::equal(v, (int[]){4,5}) ); +} + +void +test02() +{ + int x[] = {1,2,3,4,5}; + auto t = views::drop(3) | views::reverse; + auto v = x | t; + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(ranges::sized_range<R>); + static_assert(ranges::random_access_range<R>); + VERIFY( ranges::equal(v, (int[]){5,4}) ); +} + +void +test03() +{ + int x[] = {1,2,3,4,5}; + test_range<int, bidirectional_iterator_wrapper> rx(x); + auto v = rx | views::drop(3); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::sized_range<R>); + static_assert(ranges::bidirectional_range<R>); + VERIFY( ranges::equal(v, (int[]){4,5}) ); +} + + +void +test04() +{ + auto v = views::iota(0) | views::drop(10); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::sized_range<R>); + VERIFY( ranges::equal(v | views::take(3), (int[]){10,11,12}) ); +} + +void +test05() +{ + int x[] = {1,2,3}; + auto r = ranges::subrange(x, x+1); + auto v = views::drop(r, 2); + VERIFY( ranges::begin(v) == x+1 ); + VERIFY( ranges::size(v) == 0 ); +} + +void +test06() +{ + int x[] = {1,2,3}; + VERIFY( ranges::empty(x | views::drop(10)) ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); + test06(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc new file mode 100644 index 00000000000..be47551563d --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc @@ -0,0 +1,63 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::bidirectional_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + auto p = [] (int i) { return i != 16; }; + auto v = views::iota(10) | views::drop_while(p); + VERIFY( ranges::equal(v | views::take(5), (int[]){16,17,18,19,20}) ); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::random_access_range<R>); +} + +void +test02() +{ + int x[] = {1,2,3,4,5}; + test_range<int, bidirectional_iterator_wrapper> rx(x); + auto v = rx | views::drop_while([] (int i) { return i<4; }); + VERIFY( ranges::equal(v, (int[]){4,5}) ); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::bidirectional_range<R>); +} + +int +main() +{ + test01(); + test02(); +} + diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc new file mode 100644 index 00000000000..0c6ee4bf58d --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc @@ -0,0 +1,52 @@ +// Copyright (C) 2019-2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> +#include <tuple> + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + std::tuple<int, int> x[] = {{1,2},{3,4},{5,6}}; + auto v0 = x | views::elements<0>; + VERIFY( ranges::equal(v0, (int[]){1,3,5}) ); + VERIFY( ranges::equal(v0, x | views::keys) ); + VERIFY( ranges::size(v0) == 3 ); + + using R0 = decltype(v0); + static_assert(ranges::random_access_range<R0>); + static_assert(ranges::sized_range<R0>); + + auto v1 = x | views::reverse | views::elements<1> | views::reverse; + VERIFY( ranges::equal(v1, (int[]){2,4,6}) ); + VERIFY( ranges::equal(v1, x | views::values) ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc new file mode 100644 index 00000000000..83d52967a0f --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc @@ -0,0 +1,97 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::bidirectional_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + int x[] = {1,2,3,4,5,6}; + auto is_odd = [] (int i) { return i%2==1; }; + auto v = x | views::filter(is_odd); + using R = decltype(v); + static_assert(std::same_as<int&, decltype(*v.begin())>); + static_assert(ranges::view<R>); + static_assert(ranges::input_range<R>); + static_assert(ranges::common_range<R>); + static_assert(!ranges::sized_range<R>); + static_assert(ranges::bidirectional_range<R>); + static_assert(!ranges::random_access_range<R>); + static_assert(ranges::range<ranges::all_view<R>>); + VERIFY( ranges::equal(v, (int[]){1,3,5}) ); + VERIFY( ranges::equal(v | views::reverse, (int[]){5,3,1}) ); +} + +void +test02() +{ + int x[] = {1,2,3,4,5,6}; + auto f = [flag=false] (int) mutable { return flag = !flag; }; + auto v = views::filter(f)(x); + using R = decltype(v); + static_assert(std::same_as<int&, decltype(*v.begin())>); + static_assert(ranges::range<R>); + static_assert(std::copyable<R>); + static_assert(!ranges::view<const R>); + VERIFY( ranges::equal(v, (int[]){1,3,5}) ); +} + +struct X +{ + int i, j; +}; + +void +test03() +{ + X x[] = {{1,3}, {2,5}, {3,7}, {4,9}}; + test_range<X, bidirectional_iterator_wrapper> rx(x); + auto v = rx | views::filter([] (auto&& p) { return p.i%2==0; }); + int sum = 0; + for (auto i = v.begin(); i != v.end(); ++i) + sum += i->j; + VERIFY( sum == 14 ); +} + +void +test04() +{ + auto yes = [] (int) { return true; }; + VERIFY( ranges::equal(views::iota(0) | views::filter(yes) | views::take(1), + (int[]){0}) ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc new file mode 100644 index 00000000000..d3e652da009 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc @@ -0,0 +1,112 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <string> +#include <string_view> +#include <vector> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + using namespace std::literals; + std::string_view cs[] = {"the", "quick", "brown", "fox"}; + auto v = cs | views::join; + VERIFY( ranges::equal(v, "thequickbrownfox"sv) ); + using R = decltype(v); + static_assert(ranges::bidirectional_range<R>); + static_assert(ranges::bidirectional_range<const R>); + static_assert(ranges::common_range<R>); + static_assert(ranges::common_range<const R>); +} + +void +test02() +{ + auto v = (views::iota(0,4) + | views::transform([] (int i) { return views::iota(0,i); }) + | views::join); + VERIFY( ranges::equal(v, (int[]){0,0,1,0,1,2}) ); + using R = decltype(v); + static_assert(ranges::input_range<R>); + static_assert(!ranges::range<const R>); + static_assert(!ranges::forward_range<R>); + static_assert(!ranges::common_range<const R>); +} + +void +test03() +{ + auto v = (views::iota(0,4) + | views::transform([] (int i) { return views::iota(0,i); }) + | views::filter([] (auto) { return true; }) + | views::join); + VERIFY( ranges::equal(v, (int[]){0,0,1,0,1,2}) ); + using R = decltype(v); + static_assert(ranges::input_range<R>); + static_assert(!ranges::range<const R>); + static_assert(!ranges::forward_range<R>); + static_assert(!ranges::common_range<const R>); +} + +void +test04() +{ + auto v = (views::iota(0,4) + | views::transform([] (int i) { return views::iota(0,i); })); + auto v2 = ranges::ref_view{v}; + VERIFY( ranges::equal(v2 | views::join, (int[]){0,0,1,0,1,2}) ); + using R = decltype(v2); + static_assert(ranges::random_access_range<R>); + static_assert(ranges::range<const R>); + static_assert(ranges::common_range<const R>); + static_assert(ranges::random_access_range<ranges::range_reference_t<R>>); + static_assert(!std::is_reference_v<ranges::range_reference_t<R>>); +} + +void +test05() +{ + using namespace std::literals; + std::vector<std::string> x = {"the", " ", "quick", " ", "brown", " ", "fox"}; + auto v = x | views::join | views::split(' '); + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc new file mode 100644 index 00000000000..b3f2e7eef3b --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc @@ -0,0 +1,86 @@ +// Copyright (C) 2019-2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::bidirectional_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + int x[] = {1,2,3,4,5}; + auto v = x | views::reverse; + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); + VERIFY( ranges::equal(v | views::reverse, x) ); + 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)>); +} + +void +test02() +{ + int x[] = {1,2,3,4,5}; + test_range<int, bidirectional_iterator_wrapper> rx(x); + auto v = views::reverse(rx); + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); + VERIFY( ranges::equal(v | views::reverse, rx) ); + 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::bidirectional_range<decltype(v)>); +} + +void +test03() +{ + int x[] = {1,7,3,6,5,2,4,8}; + auto is_even = [] (int i) { return i%2==0; }; + int sum = 0; + for (auto i : x | views::reverse | views::filter(is_even)) + sum += i; + VERIFY( sum == 20 ); +} + +void +test04() +{ + int x[] = {1,2,3,4,5}; + VERIFY( ranges::equal(x | views::reverse | (views::reverse | views::reverse), + (int[]){5,4,3,2,1}) ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc new file mode 100644 index 00000000000..129a8249f21 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc @@ -0,0 +1,82 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <string> +#include <string_view> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +using namespace std::literals; + +void +test01() +{ + auto x = "the quick brown fox"sv; + auto p = std::string{" "}; + auto v = x | views::split(p); + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +void +test02() +{ + auto x = "the quick brown fox"sv; + auto v = x | views::split(' '); + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +void +test03() +{ + char x[] = "the quick brown fox"; + test_range<char, forward_iterator_wrapper> rx(x); + auto v = rx | views::split(' '); + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/take.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/take.cc new file mode 100644 index 00000000000..32ea9fc5107 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/take.cc @@ -0,0 +1,95 @@ +// Copyright (C) 2019-2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::bidirectional_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = ranges::views; + +void +test01() +{ + auto v = views::iota(0) | views::take(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)>); + VERIFY( ranges::equal(v, (int[]){0,1,2,3,4}) ); +} + +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)>); + VERIFY( ranges::equal(v, (int[]){0,1,2,3,4}) ); +} + +void +test03() +{ + int x[] = {0,1,2,3,4,5}; + auto is_odd = [] (int i) { return i%2 == 1; }; + auto v = x | views::filter(is_odd) | views::take(3); + ranges::begin(v); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::sized_range<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::forward_range<R>); + static_assert(!ranges::random_access_range<R>); + static_assert(!ranges::range<const R>); + VERIFY( ranges::equal(v, (int[]){1,3,5}) ); +} + +void +test04() +{ + int x[] = {1,2,3,4,5}; + test_range<int, bidirectional_iterator_wrapper> rx(x); + auto v = ranges::take_view{rx, 3}; + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::sized_range<R>); + static_assert(ranges::bidirectional_range<R>); + VERIFY( ranges::equal(v | views::take(5), (int[]){1,2,3}) ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/take_while.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/take_while.cc new file mode 100644 index 00000000000..b261ffd1aae --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/take_while.cc @@ -0,0 +1,62 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + auto p = [] (int i) { return i != 16; }; + auto v = views::iota(10) | views::take_while(p); + VERIFY( ranges::equal(v, (int[]){10,11,12,13,14,15}) ); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::random_access_range<R>); +} + +void +test02() +{ + int x[] = {1,2,3,4,5}; + test_range<int, forward_iterator_wrapper> rx(x); + auto v = rx | views::take_while([] (int i) { return i<4; }); + VERIFY( ranges::equal(v, (int[]){1,2,3}) ); + using R = decltype(v); + static_assert(ranges::view<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::forward_range<R>); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/transform.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/transform.cc new file mode 100644 index 00000000000..ad51fffb43d --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/transform.cc @@ -0,0 +1,86 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::random_access_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +void +test01() +{ + int x[] = {1,2,3,4,5}; + auto is_odd = [] (int i) { return i%2==1; }; + auto v = x | views::transform(is_odd); + VERIFY( ranges::equal(v, (int[]){1,0,1,0,1}) ); + using R = decltype(v); + static_assert(std::same_as<bool, decltype(*ranges::begin(v))>); + static_assert(ranges::view<R>); + static_assert(ranges::sized_range<R>); + static_assert(ranges::random_access_range<R>); +} + +struct X +{ + int i,j; +}; + +void +test02() +{ + X x[] = {{1,2},{3,4},{5,6},{7,8},{9,10}}; + test_range<X, random_access_iterator_wrapper> rx(x); + auto v = rx | views::transform(&X::i); + VERIFY( ranges::size(v) == 5 ); + VERIFY( ranges::distance(v.begin(), v.end()) == 5 ); + VERIFY( ranges::equal(v, (int[]){1,3,5,7,9}) ); + VERIFY( ranges::equal(v | views::reverse, (int[]){9,7,5,3,1}) ); + using R = decltype(v); + static_assert(std::same_as<int&, decltype(*ranges::begin(v))>); + static_assert(std::same_as<int, std::iter_value_t<ranges::iterator_t<R>>>); + static_assert(ranges::view<R>); + static_assert(ranges::sized_range<R>); + static_assert(!ranges::common_range<R>); + static_assert(ranges::random_access_range<R>); +} + +void +test03() +{ + auto id = [] (int i) { return i; }; + auto v = views::iota(0) | (views::filter(id) + | views::transform(id) + | views::take(5)); + VERIFY( ranges::equal(v, (int[]){1,2,3,4,5}) ); +} + +int +main() +{ + test01(); + test02(); + test03(); +}

[3/3] libstdc++: Implement C++20 range adaptors

Commit Message

Comments

Patch