diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -41,6 +41,7 @@ __ranges/concepts.h __ranges/empty.h __ranges/data.h + __ranges/drop_view.h __ranges/enable_borrowed_range.h __ranges/size.h __ranges/ref_view.h diff --git a/libcxx/include/__iterator/primitives.h b/libcxx/include/__iterator/primitives.h --- a/libcxx/include/__iterator/primitives.h +++ b/libcxx/include/__iterator/primitives.h @@ -95,7 +95,7 @@ // * If `n < 0`, [bound, i) denotes a range, `I` models `bidirectional_iterator`, and `I` and `S` model `same_as`. // Returns: `n - M`, where `M` is the difference between the the ending and starting position. template _Sp> - [[nodiscard]] constexpr iter_difference_t<_Ip> operator()(_Ip& __i, iter_difference_t<_Ip> __n, _Sp __bound) const { + constexpr iter_difference_t<_Ip> operator()(_Ip& __i, iter_difference_t<_Ip> __n, _Sp __bound) const { _LIBCPP_ASSERT(__n >= 0 || (bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>), "If `n < 0`, then `bidirectional_iterator && same_as` must be true."); // If `S` and `I` model `sized_sentinel_for`: diff --git a/libcxx/include/__ranges/drop_view.h b/libcxx/include/__ranges/drop_view.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__ranges/drop_view.h @@ -0,0 +1,120 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +#ifndef _LIBCPP___RANGES_DROP_VIEW_H +#define _LIBCPP___RANGES_DROP_VIEW_H + +#include <__config> +#include <__iterator/iterator_traits.h> +#include <__iterator/concepts.h> +#include <__ranges/access.h> +#include <__ranges/view_interface.h> +#include <__ranges/views_all.h> +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if !defined(_LIBCPP_HAS_NO_RANGES) + +// clang-format off +namespace ranges { + template + concept __simple_view = + view<_Range> && range && + same_as, iterator_t> && + same_as, sentinel_t>; + + template + class drop_view : public view_interface> { + _View __base = _View(); + range_difference_t<_View> __count = 0; + iterator_t<_View> __cached_begin = ranges::begin(__base); + +public: + constexpr drop_view() noexcept = default; + + constexpr drop_view(_View __base, range_difference_t<_View> __count) + : __base(_VSTD::move(__base)), __count(__count) { + _LIBCPP_ASSERT(__count >= 0, "count must be greater than or equal to zero."); + } + + constexpr _View base() const& requires copy_constructible<_View> { return __base; } + constexpr _View base() && { return _VSTD::move(__base); } + + constexpr auto begin() + requires (!(__simple_view<_View> && + random_access_range && sized_range)) { + auto __tmp = ranges::begin(__base); + if constexpr (forward_range<_View>) { + if (__cached_begin != __tmp || __count == 0) + return __cached_begin; + } else {} + ranges::advance(__tmp, __count, ranges::end(__base)); + __cached_begin = __tmp; + return __tmp; + } + + constexpr auto begin() const + requires random_access_range && sized_range { + auto __tmp = ranges::begin(__base); + if (__cached_begin != __tmp || __count == 0) + return __cached_begin; + ranges::advance(__tmp, __count, ranges::end(__base)); + return __tmp; + } + + constexpr auto end() + requires (!__simple_view<_View>) + { return ranges::end(__base); } + + constexpr auto end() const + requires range + { return ranges::end(__base); } + + constexpr auto size() + requires sized_range<_View> + { + const auto __s = ranges::size(__base); + const auto __c = static_cast(__count); + return __s < __c ? 0 : __s - __c; + } + + constexpr auto size() const + requires sized_range + { + const auto __s = ranges::size(__base); + const auto __c = static_cast(__count); + return __s < __c ? 0 : __s - __c; + } + + }; + + template + drop_view(_Range&&, range_difference_t<_Range>) + // TODO: this is just recreating all_t. + -> drop_view()))>; + +} // namespace ranges + +// clang-format off + +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___RANGES_DROP_VIEW_H diff --git a/libcxx/include/__ranges/views_all.h b/libcxx/include/__ranges/views_all.h --- a/libcxx/include/__ranges/views_all.h +++ b/libcxx/include/__ranges/views_all.h @@ -15,6 +15,8 @@ #include <__ranges/concepts.h> #include <__ranges/access.h> #include <__ranges/view.h> +#include <__ranges/ref_view.h> +#include <__ranges/subrange.h> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) diff --git a/libcxx/include/ranges b/libcxx/include/ranges --- a/libcxx/include/ranges +++ b/libcxx/include/ranges @@ -74,6 +74,7 @@ #include <__ranges/concepts.h> #include <__ranges/empty.h> #include <__ranges/data.h> +#include <__ranges/drop_view.h> #include <__ranges/enable_borrowed_range.h> #include <__ranges/size.h> #include <__ranges/ref_view.h> diff --git a/libcxx/test/std/ranges/range.adaptors/range.drop/range.drop.view.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.drop/range.drop.view.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.drop/range.drop.view.pass.cpp @@ -0,0 +1,196 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// class std::ranges::drop_view; + +#include + +#include +#include "test_macros.h" +#include "test_iterators.h" + +namespace ranges = std::ranges; + +int globalBuff[8]; + +template +concept ValidDropView = requires { typename ranges::drop_view; }; + +struct View : std::ranges::view_base { + int start; + constexpr View(int start = 0) : start(start) {} + constexpr View(View&&) = default; + constexpr View& operator=(View&&) = default; + constexpr friend int* begin(View& view) { return globalBuff + view.start; } + constexpr friend int* begin(View const& view) { return globalBuff + view.start; } + constexpr friend int* end(View&) { return globalBuff + 8; } + constexpr friend int* end(View const&) { return globalBuff + 8; } +}; + +struct CopyableView : std::ranges::view_base { + int start; + constexpr CopyableView(int start = 0) : start(start) {} + constexpr CopyableView(CopyableView const&) = default; + constexpr CopyableView& operator=(CopyableView const&) = default; + constexpr friend int* begin(CopyableView& view) { return globalBuff + view.start; } + constexpr friend int* begin(CopyableView const& view) { return globalBuff + view.start; } + constexpr friend int* end(CopyableView&) { return globalBuff + 8; } + constexpr friend int* end(CopyableView const&) { return globalBuff + 8; } +}; + +using ForwardIter = forward_iterator; +struct ForwardView : std::ranges::view_base { + constexpr ForwardView() = default; + constexpr ForwardView(ForwardView&&) = default; + constexpr ForwardView& operator=(ForwardView&&) = default; + constexpr friend ForwardIter begin(ForwardView&) { return ForwardIter(globalBuff); } + constexpr friend ForwardIter begin(ForwardView const&) { return ForwardIter(globalBuff); } + constexpr friend ForwardIter end(ForwardView&) { return ForwardIter(globalBuff + 8); } + constexpr friend ForwardIter end(ForwardView const&) { return ForwardIter(globalBuff + 8); } +}; + +struct InputView : std::ranges::view_base { + constexpr input_iterator begin() const { return input_iterator(globalBuff); } + constexpr int* end() const { return globalBuff + 8; } + constexpr input_iterator begin() { return input_iterator(globalBuff); } + constexpr int* end() { return globalBuff + 8; } +}; + +constexpr bool operator==(input_iterator lhs, int* rhs) { return lhs.base() == rhs; } +constexpr bool operator==(int* lhs, input_iterator rhs) { return rhs.base() == lhs; } + +struct Range { + friend int* begin(Range const&); + friend int* end(Range const&); + friend int* begin(Range&); + friend int* end(Range&); +}; + +using CountedIter = stride_counting_iterator>; +struct CountedView : std::ranges::view_base { + constexpr CountedIter begin() { return CountedIter(ForwardIter(globalBuff)); } + constexpr CountedIter begin() const { return CountedIter(ForwardIter(globalBuff)); } + constexpr CountedIter end() { return CountedIter(ForwardIter(globalBuff + 8)); } + constexpr CountedIter end() const { return CountedIter(ForwardIter(globalBuff + 8)); } +}; + +static_assert(ValidDropView); +static_assert(!ValidDropView); + +static_assert(std::same_as>); +static_assert(std::same_as>); +static_assert(std::same_as>); +static_assert(std::same_as>); + +template +concept BeginInvocable = requires(ranges::drop_view t) { t.begin(); }; + +template +concept SizeInvocable = requires(ranges::drop_view t) { t.size(); }; + +constexpr bool test() { + { + // drop_view::base + ranges::drop_view dropView1; + auto base1 = std::move(dropView1).base(); + assert(ranges::begin(base1) == globalBuff); + + // Note: we should *not* drop two elements here. + ranges::drop_view dropView2(View{4}, 2); + auto base2 = std::move(dropView2).base(); + assert(ranges::begin(base2) == globalBuff + 4); + + ranges::drop_view dropView3; + auto base3 = dropView3.base(); + assert(ranges::begin(base3) == globalBuff); + auto base4 = std::move(dropView3).base(); + assert(ranges::begin(base4) == globalBuff); + } + + { + // drop_view::begin + ranges::drop_view dropView1(View(), 4); + assert(dropView1.begin() == globalBuff + 4); + + ranges::drop_view dropView2(ForwardView(), 4); + assert(dropView2.begin().base() == globalBuff + 4); + + ranges::drop_view dropView3(InputView(), 4); + assert(dropView3.begin().base() == globalBuff + 4); + + ranges::drop_view dropView4(View(), 8); + assert(dropView4.begin() == globalBuff + 8); + + ranges::drop_view dropView5(View(), 0); + assert(dropView5.begin() == globalBuff); + + const ranges::drop_view dropView6(View(), 0); + assert(dropView6.begin() == globalBuff); + + ranges::drop_view dropView7(View(), 10); + assert(dropView7.begin() == globalBuff + 8); + + CountedView view8; + ranges::drop_view dropView8(view8, 5); + assert(dropView8.begin().base().base() == globalBuff + 5); + assert(dropView8.begin().distance_traversed() == 5); + assert(dropView8.begin().base().base() == globalBuff + 5); + assert(dropView8.begin().distance_traversed() == 5); + + static_assert(!BeginInvocable); + } + + { + // drop_view::end + ranges::drop_view dropView1(View(), 4); + assert(dropView1.end() == globalBuff + 8); + + ranges::drop_view dropView2(InputView(), 4); + assert(dropView2.end() == globalBuff + 8); + + const ranges::drop_view dropView3(View(), 0); + assert(dropView3.end() == globalBuff + 8); + + const ranges::drop_view dropView4(InputView(), 2); + assert(dropView4.end() == globalBuff + 8); + + ranges::drop_view dropView5(View(), 10); + assert(dropView5.end() == globalBuff + 8); + } + + { + // drop_view::size + ranges::drop_view dropView1(View(), 4); + assert(dropView1.size() == 4); + + ranges::drop_view dropView2(View(), 0); + assert(dropView2.size() == 8); + + ranges::drop_view dropView3(View(), 8); + assert(dropView3.size() == 0); + + ranges::drop_view dropView4(View(), 10); + assert(dropView4.size() == 0); + + // Because ForwardView is not a sized_range. + static_assert(!SizeInvocable); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +}