diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -140,6 +140,7 @@ __ranges/all.h __ranges/concepts.h __ranges/data.h + __ranges/drop_view.h __ranges/empty.h __ranges/empty_view.h __ranges/enable_borrowed_range.h 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,157 @@ +// -*- 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/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) + +namespace ranges { + template + class drop_view + : public view_interface> { + + static constexpr bool _UseCache = forward_range<_View> && !random_access_range<_View>; + using _Cache = optional>; + struct _Empty { }; + + // For forward ranges use std::optional to cache the begin iterator. + // No unique address + _Empty means we don't use any extra space when this + // is not a forward iterator. + [[no_unique_address]] conditional_t<_UseCache, _Cache, _Empty> __cached_begin_; + _View __base_; + range_difference_t<_View> __count_; + +public: + constexpr drop_view() noexcept(noexcept(_View())) + requires default_initializable<_View> + : __cached_begin_() + , __base_(_View()) + , __count_(0) + { } + + constexpr drop_view(_View __base, range_difference_t<_View> __count) + : __cached_begin_() + , __base_(_VSTD::move(__base)) + , __count_(__count) + { + _LIBCPP_ASSERT(__count_ >= 0, "count must be greater than or equal to zero."); + } + + constexpr drop_view(drop_view const& __other) + : __cached_begin_() // Intentionally not propagating the cached begin iterator. + , __base_(__other.__base_) + , __count_(__other.__count_) + { } + + constexpr drop_view(drop_view&& __other) + : __cached_begin_() // Intentionally not propagating the cached begin iterator. + , __base_(_VSTD::move(__other.__base_)) + , __count_(_VSTD::move(__other.__count_)) + { } + + constexpr drop_view& operator=(drop_view const& __other) { + if constexpr (_UseCache) { + __cached_begin_.reset(); + } + __base_ = __other.__base_; + __count_ = __other.__count_; + return *this; + } + + constexpr drop_view& operator=(drop_view&& __other) { + if constexpr (_UseCache) { + __cached_begin_.reset(); + __other.__cached_begin_.reset(); + } + __base_ = _VSTD::move(__other.__base_); + __count_ = _VSTD::move(__other.__count_); + return *this; + } + + 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 (_UseCache) + if (__cached_begin_) + return *__cached_begin_; + + auto __tmp = ranges::begin(__base_); + ranges::advance(__tmp, __count_, ranges::end(__base_)); + if constexpr (_UseCache) + __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 + +#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 b/libcxx/include/ranges --- a/libcxx/include/ranges +++ b/libcxx/include/ranges @@ -97,6 +97,7 @@ #include <__ranges/all.h> #include <__ranges/concepts.h> #include <__ranges/data.h> +#include <__ranges/drop_view.h> #include <__ranges/empty.h> #include <__ranges/empty_view.h> #include <__ranges/enable_borrowed_range.h> diff --git a/libcxx/test/std/ranges/range.adaptors/range.drop/base.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.drop/base.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.drop/base.pass.cpp @@ -0,0 +1,44 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#include "types.h" + +constexpr bool test() { + std::ranges::drop_view dropView1; + auto base1 = std::move(dropView1).base(); + assert(std::ranges::begin(base1) == globalBuff); + + // Note: we should *not* drop two elements here. + std::ranges::drop_view dropView2(View{4}, 2); + auto base2 = std::move(dropView2).base(); + assert(std::ranges::begin(base2) == globalBuff + 4); + + std::ranges::drop_view dropView3; + auto base3 = dropView3.base(); + assert(std::ranges::begin(base3) == globalBuff); + auto base4 = std::move(dropView3).base(); + assert(std::ranges::begin(base4) == globalBuff); + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.drop/begin.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.drop/begin.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.drop/begin.pass.cpp @@ -0,0 +1,62 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#include "types.h" + +template +concept BeginInvocable = requires(std::ranges::drop_view t) { t.begin(); }; + +constexpr bool test() { + std::ranges::drop_view dropView1(View(), 4); + assert(dropView1.begin() == globalBuff + 4); + + std::ranges::drop_view dropView2(ForwardView(), 4); + assert(dropView2.begin().base() == globalBuff + 4); + + std::ranges::drop_view dropView3(InputView(), 4); + assert(dropView3.begin().base() == globalBuff + 4); + + std::ranges::drop_view dropView4(View(), 8); + assert(dropView4.begin() == globalBuff + 8); + + std::ranges::drop_view dropView5(View(), 0); + assert(dropView5.begin() == globalBuff); + + const std::ranges::drop_view dropView6(View(), 0); + assert(dropView6.begin() == globalBuff); + + std::ranges::drop_view dropView7(View(), 10); + assert(dropView7.begin() == globalBuff + 8); + + CountedView view8; + std::ranges::drop_view dropView8(view8, 5); + assert(dropView8.begin().base().base() == globalBuff + 5); + assert(dropView8.begin().stride_count() == 5); + assert(dropView8.begin().base().base() == globalBuff + 5); + assert(dropView8.begin().stride_count() == 5); + + static_assert(!BeginInvocable); + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.drop/ctad.compile.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.drop/ctad.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.drop/ctad.compile.pass.cpp @@ -0,0 +1,31 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#include "types.h" + +namespace ranges = std::ranges; + +static_assert(std::same_as>); +static_assert(std::same_as>); +static_assert(std::same_as>); +static_assert(std::same_as>); + +static_assert(std::same_as(), 0)), + ranges::drop_view>>); + +static_assert(std::same_as>>); diff --git a/libcxx/test/std/ranges/range.adaptors/range.drop/end.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.drop/end.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.drop/end.pass.cpp @@ -0,0 +1,44 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#include "types.h" + +constexpr bool test() { + std::ranges::drop_view dropView1(View(), 4); + assert(dropView1.end() == globalBuff + 8); + + std::ranges::drop_view dropView2(InputView(), 4); + assert(dropView2.end() == globalBuff + 8); + + const std::ranges::drop_view dropView3(View(), 0); + assert(dropView3.end() == globalBuff + 8); + + const std::ranges::drop_view dropView4(InputView(), 2); + assert(dropView4.end() == globalBuff + 8); + + std::ranges::drop_view dropView5(View(), 10); + assert(dropView5.end() == globalBuff + 8); + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.drop/general.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.drop/general.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.drop/general.pass.cpp @@ -0,0 +1,119 @@ +//===----------------------------------------------------------------------===// +// +// 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" +#include "types.h" + +template +concept ValidDropView = requires { typename std::ranges::drop_view; }; + +static_assert(ValidDropView); +static_assert(!ValidDropView); + +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(std::ranges::drop_view(v.base(), n), n + 1); +} + +template +std::ranges::view auto makeEven(View v) { + return std::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 +std::ranges::view auto removeBefore(View v, T element) { + std::ranges::drop_view out(v, indexOf(v, element) + 1); + return View(out.begin(), out.end()); +} + +template<> +constexpr bool std::ranges::enable_view> = true; + +template<> +constexpr bool std::ranges::enable_view> = true; + +template<> +constexpr bool std::ranges::enable_view = true; + +struct ZeroOnDestroy : std::ranges::view_base { + unsigned count = 0; + int buff[8] = {1, 2, 3, 4, 5, 6, 7, 8}; + + constexpr ForwardIter begin() { return ForwardIter(buff); } + constexpr ForwardIter begin() const { return ForwardIter(); } + constexpr ForwardIter end() { return ForwardIter(buff + 8); } + constexpr ForwardIter end() const { return ForwardIter(); } + + ~ZeroOnDestroy() { + memset(buff, 0, 8); + } + + static auto dropFirstFour() { + ZeroOnDestroy zod; + std::ranges::drop_view dv(zod, 4); + // Make sure we call begin here so the next call to begin will + // use the cached iterator. + assert(*dv.begin() == 5); + // Intentionally invoke the copy ctor here. + return std::ranges::drop_view(dv); + } +}; + +int main(int, char**) { + const std::vector vec = {1,1,2,3,5,8,13}; + assert(orderedFibonacci(std::ranges::drop_view(vec, 0))); + const std::vector vec2 = {1,1,2,3,5,8,14}; + assert(!orderedFibonacci(std::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"); + + auto noDanlingCache = ZeroOnDestroy::dropFirstFour(); + // If we use the cached version, it will reference the copied-from view. + // Worst case this is a segfault, best case it's an assertion fired. + assert(*noDanlingCache.begin() == 5); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.drop/size.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.drop/size.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.drop/size.pass.cpp @@ -0,0 +1,47 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#include "types.h" + +template +concept SizeInvocable = requires(std::ranges::drop_view t) { t.size(); }; + +constexpr bool test() { + std::ranges::drop_view dropView1(View(), 4); + assert(dropView1.size() == 4); + + std::ranges::drop_view dropView2(View(), 0); + assert(dropView2.size() == 8); + + std::ranges::drop_view dropView3(View(), 8); + assert(dropView3.size() == 0); + + std::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; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.drop/types.h b/libcxx/test/std/ranges/range.adaptors/range.drop/types.h new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.drop/types.h @@ -0,0 +1,92 @@ +//===----------------------------------------------------------------------===// +// +// 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 TEST_STD_RANGES_RANGE_ADAPTORS_RANGE_DROP_TYPES_H +#define TEST_STD_RANGES_RANGE_ADAPTORS_RANGE_DROP_TYPES_H + +#include "test_macros.h" +#include "test_iterators.h" + +int globalBuff[8]; + +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 ForwardRange { + ForwardIter begin() const; + ForwardIter end() const; + ForwardIter begin(); + ForwardIter end(); +}; + +struct BorrowableRange { + friend int* begin(BorrowableRange const& range); + friend int* end(BorrowableRange const&); + friend int* begin(BorrowableRange& range); + friend int* end(BorrowableRange&); +}; + +template<> +inline constexpr bool std::ranges::enable_borrowed_range = true; + +struct InputView : std::ranges::view_base { + constexpr cpp20_input_iterator begin() const { return cpp20_input_iterator(globalBuff); } + constexpr int* end() const { return globalBuff + 8; } + constexpr cpp20_input_iterator begin() { return cpp20_input_iterator(globalBuff); } + constexpr int* end() { return globalBuff + 8; } +}; + +constexpr bool operator==(const cpp20_input_iterator &lhs, int* rhs) { return lhs.base() == rhs; } +constexpr bool operator==(int* lhs, const cpp20_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)); } +}; + +#endif // TEST_STD_RANGES_RANGE_ADAPTORS_RANGE_DROP_TYPES_H