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,130 @@ +// -*- 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> + struct __cache_base { + iterator_t<_View> __cached_begin{}; + }; + + template + struct __cache_base<_View, false> { }; + + template + class drop_view + : public view_interface>, + private __cache_base<_View> { + + using _Cache = __cache_base<_View>; + + _View __base; + range_difference_t<_View> __count; + +public: + constexpr drop_view() noexcept : __base(_View()), __count(0) {} + + 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)) + { + if constexpr (forward_range<_View>) + if (_Cache::__cached_begin != iterator_t<_View>()) + return _Cache::__cached_begin; + + auto __tmp = ranges::begin(__base); + ranges::advance(__tmp, __count, ranges::end(__base)); + if constexpr (forward_range<_View>) + _Cache::__cached_begin = __tmp; + return __tmp; + } + + constexpr auto begin() const + requires random_access_range && sized_range + { + auto __tmp = ranges::begin(__base); + 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); } + + static constexpr auto __size(auto& __self) { + const auto __s = ranges::size(__self.__base); + const auto __c = static_cast(__self.__count); + return __s < __c ? 0 : __s - __c; + } + + constexpr auto size() + requires sized_range<_View> + { return __size(*this); } + + constexpr auto size() const + requires sized_range + { return __size(*this); } + }; + + 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,257 @@ +//===----------------------------------------------------------------------===// +// +// 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 +#include +#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); + +// CTAD +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; +} + +template +bool orderedFibonacci(View v, int n = 1) { + if (v.size() < 3) + return true; + + if (v[2] != v[0] + v[1]) + return false; + + return orderedFibonacci(ranges::drop_view(v.base(), n), n + 1); +} + +template +ranges::view auto makeEven(View v) { + return ranges::drop_view(v, v.size() % 2); +} + +template +int indexOf(View v, T element) { + int index = 0; + for (auto e : v) { + if (e == element) + return index; + index++; + } + return -1; +} + +template +ranges::view auto removeBefore(View v, T element) { + ranges::drop_view out(v, indexOf(v, element) + 1); + return View(out.begin(), out.end()); +} + +template<> +constexpr bool ranges::enable_view> = true; + +template<> +constexpr bool ranges::enable_view> = true; + +template<> +constexpr bool ranges::enable_view = true; + +int main(int, char**) { + test(); + static_assert(test()); + + const std::vector vec = {1,1,2,3,5,8,13}; + assert(orderedFibonacci(ranges::drop_view(vec, 0))); + const std::vector vec2 = {1,1,2,3,5,8,14}; + assert(!orderedFibonacci(ranges::drop_view(vec2, 0))); + + const std::list l = {1, 2, 3}; + auto el = makeEven(l); + assert(el.size() == 2); + assert(*el.begin() == 2); + + const std::string s = "Hello, World"; + assert(removeBefore(s, ' ') == "World"); + + return 0; +}