diff --git a/libcxx/docs/Status/RangesPaper.csv b/libcxx/docs/Status/RangesPaper.csv --- a/libcxx/docs/Status/RangesPaper.csv +++ b/libcxx/docs/Status/RangesPaper.csv @@ -136,7 +136,7 @@ | [range.subrange]",Christopher Di Bella,✅ `[range.all] `_,`view::all `_,"[range.subrange], [range.view.ref]",Zoe Carver,✅ `[range.view.ref] `_,`ref-view `_,[view.interface],Zoe Carver,✅ -`[range.filter] `_,filter_view,[range.all],Louis Dionne,Not started +`[range.filter] `_,`filter_view `_,[range.all],Louis Dionne,✅ `[range.transform] `_,`transform_view `_,[range.all],Zoe Carver,✅ `[range.iota] `_,iota_view,[range.all],Zoe Carver,✅ `[range.take] `_,take_view,[range.all],Zoe Carver,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -227,6 +227,7 @@ __ranges/empty.h __ranges/enable_borrowed_range.h __ranges/enable_view.h + __ranges/filter_view.h __ranges/iota_view.h __ranges/join_view.h __ranges/non_propagating_cache.h diff --git a/libcxx/include/__ranges/filter_view.h b/libcxx/include/__ranges/filter_view.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__ranges/filter_view.h @@ -0,0 +1,274 @@ +// -*- 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_FILTER_VIEW_H +#define _LIBCPP___RANGES_FILTER_VIEW_H + +// #include <__ranges/find_if.h> // TODO: Use this when available +#include <__config> +#include <__debug> +#include <__functional/reference_wrapper.h> +#include <__iterator/concepts.h> +#include <__memory/addressof.h> +#include <__ranges/access.h> +#include <__ranges/all.h> +#include <__ranges/concepts.h> +#include <__ranges/copyable_box.h> +#include <__ranges/non_propagating_cache.h> +#include <__ranges/range_adaptor.h> +#include <__ranges/view_interface.h> +#include <__utility/move.h> +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if !defined(_LIBCPP_HAS_NO_RANGES) + +namespace ranges { + //////////// TODO: Remove this when ranges::find_if lands + template _Sp, class _Proj = identity, + indirect_unary_predicate> _Pred> + _LIBCPP_HIDE_FROM_ABI + constexpr _Ip find_if(_Ip __first, const _Sp __last, _Pred __pred, _Proj __proj = {}) { + for (; __first != __last; ++__first) { + if (_VSTD::invoke(__pred, _VSTD::invoke(__proj, *__first))) { + return __first; + } + } + return __first; + } + + template, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI + constexpr borrowed_iterator_t<_Range> find_if(_Range&& __range, _Pred __pred, _Proj __proj = {}) { + return ranges::find_if(ranges::begin(__range), ranges::end(__range), _VSTD::move(__pred), _VSTD::move(__proj)); + } + ////////////////////////////////////////// + + template> _Pred> + requires view<_View> && is_object_v<_Pred> + class filter_view : public view_interface> { + [[no_unique_address]] __copyable_box<_Pred> __pred_; + [[no_unique_address]] _View __base_ = _View(); + + // We cache the result of begin() to allow providing an amortized O(1) begin() whenever + // the underlying range is at least a forward_range. + static constexpr bool _UseCache = forward_range<_View>; + using _Cache = _If<_UseCache, __non_propagating_cache>, __empty_cache>; + [[no_unique_address]] _Cache __cached_begin_ = _Cache(); + + class __iterator; + class __sentinel; + + public: + _LIBCPP_HIDE_FROM_ABI + filter_view() requires default_initializable<_View> && default_initializable<_Pred> = default; + + _LIBCPP_HIDE_FROM_ABI + constexpr filter_view(_View __base, _Pred __pred) + : __pred_(in_place, _VSTD::move(__pred)), __base_(_VSTD::move(__base)) + { } + + template + _LIBCPP_HIDE_FROM_ABI + constexpr _View base() const& requires copy_constructible<_Vp> { return __base_; } + _LIBCPP_HIDE_FROM_ABI + constexpr _View base() && { return _VSTD::move(__base_); } + + _LIBCPP_HIDE_FROM_ABI + constexpr _Pred const& pred() const { return *__pred_; } + + _LIBCPP_HIDE_FROM_ABI + constexpr __iterator begin() { + _LIBCPP_ASSERT(__pred_.__has_value(), "Trying to call begin() on a filter_view that does not have a valid predicate."); + if constexpr (_UseCache) { + if (!__cached_begin_.__has_value()) { + __cached_begin_.__emplace(ranges::find_if(__base_, _VSTD::ref(*__pred_))); + } + return {*this, *__cached_begin_}; + } else { + return {*this, ranges::find_if(__base_, _VSTD::ref(*__pred_))}; + } + } + + _LIBCPP_HIDE_FROM_ABI + constexpr auto end() { + if constexpr (common_range<_View>) + return __iterator{*this, ranges::end(__base_)}; + else + return __sentinel{*this}; + } + }; + + template + filter_view(_Range&&, _Pred) -> filter_view, _Pred>; + + template + struct __filter_iterator_category { }; + + template + struct __filter_iterator_category<_View> { + using _Cat = typename iterator_traits>::iterator_category; + using iterator_category = + _If, bidirectional_iterator_tag, + _If, forward_iterator_tag, + /* else */ _Cat + >>; + }; + + template> _Pred> + requires view<_View> && is_object_v<_Pred> + class filter_view<_View, _Pred>::__iterator : public __filter_iterator_category<_View> { + public: + [[no_unique_address]] iterator_t<_View> __current_ = iterator_t<_View>(); + [[no_unique_address]] filter_view* __parent_ = nullptr; + + using iterator_concept = + _If, bidirectional_iterator_tag, + _If, forward_iterator_tag, + /* else */ input_iterator_tag + >>; + // using iterator_category = inherited; + using value_type = range_value_t<_View>; + using difference_type = range_difference_t<_View>; + + _LIBCPP_HIDE_FROM_ABI + __iterator() requires default_initializable> = default; + + _LIBCPP_HIDE_FROM_ABI + constexpr __iterator(filter_view& __parent, iterator_t<_View> __current) + : __current_(_VSTD::move(__current)), __parent_(_VSTD::addressof(__parent)) + { } + + _LIBCPP_HIDE_FROM_ABI + constexpr iterator_t<_View> const& base() const& { return __current_; } + _LIBCPP_HIDE_FROM_ABI + constexpr iterator_t<_View> base() && { return _VSTD::move(__current_); } + + _LIBCPP_HIDE_FROM_ABI + constexpr range_reference_t<_View> operator*() const { return *__current_; } + _LIBCPP_HIDE_FROM_ABI + constexpr iterator_t<_View> operator->() const + requires __has_arrow> && copyable> + { + return __current_; + } + + _LIBCPP_HIDE_FROM_ABI + constexpr __iterator& operator++() { + __current_ = ranges::find_if(_VSTD::move(++__current_), ranges::end(__parent_->__base_), + _VSTD::ref(*__parent_->__pred_)); + return *this; + } + _LIBCPP_HIDE_FROM_ABI + constexpr void operator++(int) { ++*this; } + _LIBCPP_HIDE_FROM_ABI + constexpr __iterator operator++(int) requires forward_range<_View> + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + _LIBCPP_HIDE_FROM_ABI + constexpr __iterator& operator--() requires bidirectional_range<_View> { + do { + --__current_; + } while (_VSTD::invoke(*__parent_->__pred_, *__current_)); + return *this; + } + _LIBCPP_HIDE_FROM_ABI + constexpr __iterator operator--(int) requires bidirectional_range<_View> { + auto tmp = *this; + --*this; + return tmp; + } + + _LIBCPP_HIDE_FROM_ABI + friend constexpr bool operator==(__iterator const& __x, __iterator const& __y) + requires equality_comparable> + { + return __x.__current_ == __y.__current_; + } + + _LIBCPP_HIDE_FROM_ABI + friend constexpr range_rvalue_reference_t<_View> iter_move(__iterator const& __it) + noexcept(noexcept(ranges::iter_move(__it.__current_))) + { + return ranges::iter_move(__it.__current_); + } + + _LIBCPP_HIDE_FROM_ABI + friend constexpr void iter_swap(__iterator const& __x, __iterator const& __y) + noexcept(noexcept(ranges::iter_swap(__x.__current_, __y.__current_))) + requires indirectly_swappable> + { + return ranges::iter_swap(__x.__current_, __y.__current_); + } + }; + + template> _Pred> + requires view<_View> && is_object_v<_Pred> + class filter_view<_View, _Pred>::__sentinel { + public: + sentinel_t<_View> __end_ = sentinel_t<_View>(); + + _LIBCPP_HIDE_FROM_ABI + __sentinel() = default; + + _LIBCPP_HIDE_FROM_ABI + constexpr explicit __sentinel(filter_view& __parent) + : __end_(ranges::end(__parent.__base_)) + { } + + _LIBCPP_HIDE_FROM_ABI + constexpr sentinel_t<_View> base() const { return __end_; } + + _LIBCPP_HIDE_FROM_ABI + friend constexpr bool operator==(__iterator const& __x, __sentinel const& __y) { + return __x.__current_ == __y.__end_; + } + }; + +namespace views { +namespace __filter { + struct __fn { + template + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI + constexpr auto operator()(_Range&& __range, _Pred&& __pred) const + noexcept(noexcept(filter_view(_VSTD::forward<_Range>(__range), _VSTD::forward<_Pred>(__pred)))) + -> decltype( filter_view(_VSTD::forward<_Range>(__range), _VSTD::forward<_Pred>(__pred))) + { return filter_view(_VSTD::forward<_Range>(__range), _VSTD::forward<_Pred>(__pred)); } + + template + requires constructible_from, _Pred> + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI + constexpr auto operator()(_Pred&& __pred) const + noexcept(is_nothrow_constructible_v, _Pred>) + { return __range_adaptor_closure_t(_VSTD::__bind_back(*this, _VSTD::forward<_Pred>(__pred))); } + }; +} + +inline namespace __cpo { + inline constexpr auto filter = __filter::__fn{}; +} +} // namespace views + +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___RANGES_FILTER_VIEW_H diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -670,6 +670,7 @@ module empty_view { private header "__ranges/empty_view.h" } module enable_borrowed_range { private header "__ranges/enable_borrowed_range.h" } module enable_view { private header "__ranges/enable_view.h" } + module filter_view { private header "__ranges/filter_view.h" } module iota_view { private header "__ranges/iota_view.h" } module join_view { private header "__ranges/join_view.h" } module non_propagating_cache { private header "__ranges/non_propagating_cache.h" } diff --git a/libcxx/include/ranges b/libcxx/include/ranges --- a/libcxx/include/ranges +++ b/libcxx/include/ranges @@ -135,6 +135,15 @@ template inline constexpr bool enable_borrowed_range> = true; + // [range.filter], filter view + template> Pred> + requires view && is_object_v + class filter_view; + + namespace views { + inline constexpr unspecified filter = unspecified; + } + // [range.drop], drop view template class drop_view; @@ -211,6 +220,7 @@ #include <__ranges/empty.h> #include <__ranges/enable_borrowed_range.h> #include <__ranges/enable_view.h> +#include <__ranges/filter_view.h> #include <__ranges/iota_view.h> #include <__ranges/join_view.h> #include <__ranges/ref_view.h> diff --git a/libcxx/test/libcxx/diagnostics/detail.headers/ranges/filter_view.module.verify.cpp b/libcxx/test/libcxx/diagnostics/detail.headers/ranges/filter_view.module.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/detail.headers/ranges/filter_view.module.verify.cpp @@ -0,0 +1,16 @@ +// -*- 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 +// +//===----------------------------------------------------------------------===// + +// REQUIRES: modules-build + +// WARNING: This test was generated by 'generate_private_header_tests.py' +// and should not be edited manually. + +// expected-error@*:* {{use of private header from outside its module: '__ranges/filter_view.h'}} +#include <__ranges/filter_view.h> diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/adaptor.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/adaptor.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/adaptor.pass.cpp @@ -0,0 +1,172 @@ +//===----------------------------------------------------------------------===// +// +// 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: libcpp-has-no-incomplete-ranges + +// std::views::filter + +#include + +#include +#include +#include +#include +#include + +#include "test_iterators.h" + +template +concept CanBePiped = requires (View&& view, T&& t) { + { std::forward(view) | std::forward(t) }; +}; + +struct NonCopyablePredicate { + NonCopyablePredicate(NonCopyablePredicate const&) = delete; + template + constexpr bool operator()(T x) const { return x % 2 == 0; } +}; + +struct Range : std::ranges::view_base { + using Iterator = forward_iterator; + using Sentinel = sentinel_wrapper; + constexpr explicit Range(int* b, int* e) : begin_(b), end_(e) { } + constexpr Iterator begin() const { return Iterator(begin_); } + constexpr Sentinel end() const { return Sentinel(Iterator(end_)); } + +private: + int* begin_; + int* end_; +}; + +struct Pred { + constexpr bool operator()(int i) const { return i % 2 == 0; } +}; + +template +constexpr void compareViews(View v, std::initializer_list list) { + auto b1 = v.begin(); + auto e1 = v.end(); + auto b2 = list.begin(); + auto e2 = list.end(); + for (; b1 != e1 && b2 != e2; ++b1, ++b2) { + assert(*b1 == *b2); + } + assert(b1 == e1); + assert(b2 == e2); +} + +constexpr bool test() { + int buff[8] = {0, 1, 2, 3, 4, 5, 6, 7}; + + // Test `views::filter(pred)(v)` + { + using Result = std::ranges::filter_view; + Range const range(buff, buff + 8); + Pred pred; + + { + std::same_as auto result = std::views::filter(pred)(range); + compareViews(result, {0, 2, 4, 6}); + } + { + auto const partial = std::views::filter(pred); + std::same_as auto result = partial(range); + compareViews(result, {0, 2, 4, 6}); + } + } + + // Test `v | views::filter(pred)` + { + using Result = std::ranges::filter_view; + Range const range(buff, buff + 8); + Pred pred; + + { + std::same_as auto result = range | std::views::filter(pred); + compareViews(result, {0, 2, 4, 6}); + } + { + auto const partial = std::views::filter(pred); + std::same_as auto result = range | partial; + compareViews(result, {0, 2, 4, 6}); + } + } + + // Test `views::filter(v, pred)` + { + using Result = std::ranges::filter_view; + Range const range(buff, buff + 8); + Pred pred; + + std::same_as auto result = std::views::filter(range, pred); + compareViews(result, {0, 2, 4, 6}); + } + + // Test that one can call std::views::filter with arbitrary stuff, as long as we + // don't try to actually complete the call by passing it a range. + // + // That makes no sense and we can't do anything with the result, but it's valid. + { + struct X { }; + auto partial = std::views::filter(X{}); + (void)partial; + } + + // Test `adaptor | views::filter(pred)` + { + Range const range(buff, buff + 8); + + { + auto pred1 = [](int i) { return i % 2 == 0; }; + auto pred2 = [](int i) { return i % 3 == 0; }; + using Result = std::ranges::filter_view, decltype(pred2)>; + std::same_as auto result = range | std::views::filter(pred1) | std::views::filter(pred2); + compareViews(result, {0, 6}); + } + { + auto pred1 = [](int i) { return i % 2 == 0; }; + auto pred2 = [](int i) { return i % 3 == 0; }; + using Result = std::ranges::filter_view, decltype(pred2)>; + auto const partial = std::views::filter(pred1) | std::views::filter(pred2); + std::same_as auto result = range | partial; + compareViews(result, {0, 6}); + } + } + + // Test SFINAE friendliness + { + struct NotAView { }; + struct NotInvocable { }; + + static_assert(!CanBePiped); + static_assert( CanBePiped); + static_assert(!CanBePiped); + static_assert(!CanBePiped); + + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + static_assert( std::is_invocable_v); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + } + + { + static_assert(std::is_same_v); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/base.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/base.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/base.pass.cpp @@ -0,0 +1,93 @@ +//===----------------------------------------------------------------------===// +// +// 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: libcpp-has-no-incomplete-ranges + +// constexpr View base() const& requires copy_constructible; +// constexpr View base() &&; + +#include + +#include +#include +#include + +struct Range : std::ranges::view_base { + constexpr explicit Range(int* b, int* e) : begin_(b), end_(e) { } + constexpr Range(Range const& other) : begin_(other.begin_), end_(other.end_), wasCopyInitialized(true) { } + constexpr Range(Range&& other) : begin_(other.begin_), end_(other.end_), wasMoveInitialized(true) { } + Range& operator=(Range const&) = default; + Range& operator=(Range&&) = default; + constexpr int* begin() const { return begin_; } + constexpr int* end() const { return end_; } + + int* begin_; + int* end_; + bool wasCopyInitialized = false; + bool wasMoveInitialized = false; +}; + +struct Pred { + bool operator()(int) const; +}; + +struct NoCopyRange : std::ranges::view_base { + explicit NoCopyRange(int*, int*); + NoCopyRange(NoCopyRange const&) = delete; + NoCopyRange(NoCopyRange&&) = default; + NoCopyRange& operator=(NoCopyRange const&) = default; + NoCopyRange& operator=(NoCopyRange&&) = default; + int* begin() const; + int* end() const; +}; + +template +concept can_call_base_on = requires(T t) { std::forward(t).base(); }; + +constexpr bool test() { + int buff[] = {1, 2, 3, 4, 5, 6, 7, 8}; + + // Check the const& overload + { + Range range(buff, buff + 8); + std::ranges::filter_view const view(range, Pred{}); + std::same_as decltype(auto) result = view.base(); + assert(result.wasCopyInitialized); + assert(result.begin() == buff); + assert(result.end() == buff + 8); + } + + // Check the && overload + { + Range range(buff, buff + 8); + std::ranges::filter_view view(range, Pred{}); + std::same_as decltype(auto) result = std::move(view).base(); + assert(result.wasMoveInitialized); + assert(result.begin() == buff); + assert(result.end() == buff + 8); + } + + // Ensure the const& overload is not considered when the base is not copy-constructible + { + static_assert(!can_call_base_on const&>); + static_assert(!can_call_base_on&>); + static_assert( can_call_base_on&&>); + static_assert( can_call_base_on>); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/begin.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/begin.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/begin.pass.cpp @@ -0,0 +1,187 @@ +//===----------------------------------------------------------------------===// +// +// 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: libcpp-has-no-incomplete-ranges + +// constexpr iterator begin(); + +#include + +#include +#include "test_iterators.h" +#include "types.h" + +struct Range : std::ranges::view_base { + using Iterator = forward_iterator; + using Sentinel = sentinel_wrapper; + constexpr explicit Range(int* b, int* e) : begin_(b), end_(e) { } + constexpr Iterator begin() const { return Iterator(begin_); } + constexpr Sentinel end() const { return Sentinel(Iterator(end_)); } + +private: + int* begin_; + int* end_; +}; + +// A range that isn't a forward_range, used to test filter_view +// when we don't cache the result of begin() +struct InputRange : std::ranges::view_base { + using Iterator = cpp17_input_iterator; + using Sentinel = sentinel_wrapper; + constexpr explicit InputRange(int* b, int* e) : begin_(b), end_(e) { } + constexpr Iterator begin() const { return Iterator(begin_); } + constexpr Sentinel end() const { return Sentinel(Iterator(end_)); } + +private: + int* begin_; + int* end_; +}; + +struct TrackingPred : TrackInitialization { + using TrackInitialization::TrackInitialization; + constexpr bool operator()(int i) const { return i % 2 == 0; } +}; + +template +constexpr void general_tests() { + int buff[] = {1, 2, 3, 4, 5, 6, 7, 8}; + + // begin() over an empty range + { + Range range(buff, buff); + auto pred = [](int) { return true; }; + std::ranges::filter_view view(range, pred); + auto it = view.begin(); + assert(it.base().base() == buff); + assert(it == view.end()); + } + + // begin() over a 1-element range + { + { + Range range(buff, buff + 1); + auto pred = [](int i) { return i == 1; }; + std::ranges::filter_view view(range, pred); + auto it = view.begin(); + assert(it.base().base() == buff); + } + { + Range range(buff, buff + 1); + auto pred = [](int) { return false; }; + std::ranges::filter_view view(range, pred); + auto it = view.begin(); + assert(it.base().base() == buff + 1); + assert(it == view.end()); + } + } + + // begin() over a 2-element range + { + { + Range range(buff, buff + 2); + auto pred = [](int i) { return i == 1; }; + std::ranges::filter_view view(range, pred); + auto it = view.begin(); + assert(it.base().base() == buff); + } + { + Range range(buff, buff + 2); + auto pred = [](int i) { return i == 2; }; + std::ranges::filter_view view(range, pred); + auto it = view.begin(); + assert(it.base().base() == buff + 1); + } + { + Range range(buff, buff + 2); + auto pred = [](int) { return false; }; + std::ranges::filter_view view(range, pred); + auto it = view.begin(); + assert(it.base().base() == buff + 2); + assert(it == view.end()); + } + } + + // begin() over a N-element range + { + for (int k = 1; k != 8; ++k) { + Range range(buff, buff + 8); + auto pred = [=](int i) { return i == k; }; + std::ranges::filter_view view(range, pred); + auto it = view.begin(); + assert(it.base().base() == buff + (k - 1)); + } + { + Range range(buff, buff + 8); + auto pred = [](int) { return false; }; + std::ranges::filter_view view(range, pred); + auto it = view.begin(); + assert(it.base().base() == buff + 8); + assert(it == view.end()); + } + } + + // Make sure we do not make a copy of the predicate when we call begin() + // (we should be passing it to ranges::find_if using std::ref) + { + bool moved = false, copied = false; + Range range(buff, buff + 2); + std::ranges::filter_view view(range, TrackingPred(&moved, &copied)); + moved = false; + copied = false; + auto it = view.begin(); (void)it; + assert(!moved); + assert(!copied); + } + + // Test with a non-const predicate + { + struct MutablePred { + constexpr bool operator()(int i) { return i % 2 == 0; } + }; + Range range(buff, buff + 8); + MutablePred pred; + std::ranges::filter_view view(range, pred); + auto it = view.begin(); + assert(it.base().base() == buff + 1); + } +} + +template +constexpr void cache_tests() { + int buff[] = {1, 2, 3, 4, 5, 6, 7, 8}; + + // Make sure that we cache the result of begin() on subsequent calls + // (only applies to forward_ranges) + ForwardRange range(buff, buff + 8); + int called = 0; + auto pred = [&](int i) { ++called; return i == 3; }; + + std::ranges::filter_view view(range, pred); + assert(called == 0); + for (int k = 0; k != 3; ++k) { + auto it = view.begin(); + assert(it.base().base() == buff + 2); + assert(called == 3); + } +} + +constexpr bool test() { + general_tests(); + general_tests(); // test when we don't cache the result + cache_tests(); + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/constraints.compile.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/constraints.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/constraints.compile.pass.cpp @@ -0,0 +1,111 @@ +//===----------------------------------------------------------------------===// +// +// 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: libcpp-has-no-incomplete-ranges + +// Check constraints on the type itself. +// +// template> Pred> +// requires view && is_object_v +// class filter_view; + +#include + +#include +#include +#include +#include + +template +concept can_form_filter_view = requires { + typename std::ranges::filter_view; +}; + +// filter_view is not valid when the view is not an input_range +namespace test1 { + struct View : std::ranges::view_base { + struct NotInputIterator { + NotInputIterator& operator++(); + void operator++(int); + int& operator*() const; + using difference_type = std::ptrdiff_t; + friend bool operator==(NotInputIterator const&, NotInputIterator const&); + }; + NotInputIterator begin() const; + NotInputIterator end() const; + }; + struct Pred { bool operator()(int) const; }; + + static_assert(!std::ranges::input_range); + static_assert( std::indirect_unary_predicate); + static_assert( std::ranges::view); + static_assert( std::is_object_v); + static_assert(!can_form_filter_view); +} + +// filter_view is not valid when the predicate is not indirect_unary_predicate +namespace test2 { + struct View : std::ranges::view_base { + int* begin() const; + int* end() const; + }; + struct Pred { }; + + static_assert( std::ranges::input_range); + static_assert(!std::indirect_unary_predicate); + static_assert( std::ranges::view); + static_assert( std::is_object_v); + static_assert(!can_form_filter_view); +} + +// filter_view is not valid when the view is not a view +namespace test3 { + struct View { + int* begin() const; + int* end() const; + }; + struct Pred { bool operator()(int) const; }; + + static_assert( std::ranges::input_range); + static_assert( std::indirect_unary_predicate); + static_assert(!std::ranges::view); + static_assert( std::is_object_v); + static_assert(!can_form_filter_view); +} + +// filter_view is not valid when the predicate is not an object type +namespace test4 { + struct View : std::ranges::view_base { + int* begin() const; + int* end() const; + }; + using Pred = bool(&)(int); + + static_assert( std::ranges::input_range); + static_assert( std::indirect_unary_predicate); + static_assert( std::ranges::view); + static_assert(!std::is_object_v); + static_assert(!can_form_filter_view); +} + +// filter_view is valid when all the constraints are satisfied (test the test) +namespace test5 { + struct View : std::ranges::view_base { + int* begin() const; + int* end() const; + }; + struct Pred { bool operator()(int) const; }; + + static_assert( std::ranges::input_range); + static_assert( std::indirect_unary_predicate); + static_assert( std::ranges::view); + static_assert( std::is_object_v); + static_assert( can_form_filter_view); +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/ctad.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/ctad.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/ctad.pass.cpp @@ -0,0 +1,63 @@ +//===----------------------------------------------------------------------===// +// +// 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: libcpp-has-no-incomplete-ranges + +// template +// filter_view(Range&&, Pred) -> filter_view, Pred>; + +#include + +#include +#include +#include "test_iterators.h" + +struct View : std::ranges::view_base { + View() = default; + forward_iterator begin() const; + sentinel_wrapper> end() const; +}; + +// A range, but not a view +struct Range { + Range() = default; + forward_iterator begin() const; + sentinel_wrapper> end() const; +}; + +struct Pred { + constexpr bool operator()(int i) const { return i % 2 == 0; } +}; + +constexpr bool test() { + { + View v; + Pred pred; + std::ranges::filter_view view(v, pred); + static_assert(std::is_same_v>); + } + + // Test with a range that isn't a view, to make sure we properly use views::all_t in the implementation. + { + Range r; + Pred pred; + std::ranges::filter_view view(r, pred); + static_assert(std::is_same_v, Pred>>); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/ctor.default.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/ctor.default.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/ctor.default.pass.cpp @@ -0,0 +1,81 @@ +//===----------------------------------------------------------------------===// +// +// 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: libcpp-has-no-incomplete-ranges + +// filter_view() requires std::default_initializable && +// std::default_initializable = default; + +#include + +#include +#include + +constexpr int buff[] = {1, 2, 3, 4, 5, 6, 7, 8}; + +struct DefaultConstructibleView : std::ranges::view_base { + constexpr DefaultConstructibleView() : begin_(buff), end_(buff + 8) { } + constexpr int const* begin() const { return begin_; } + constexpr int const* end() const { return end_; } +private: + int const* begin_; + int const* end_; +}; + +struct DefaultConstructiblePredicate { + DefaultConstructiblePredicate() = default; + constexpr bool operator()(int i) const { return i % 2 == 0; } +}; + +struct NoDefaultView : std::ranges::view_base { + NoDefaultView() = delete; + int* begin() const; + int* end() const; +}; + +struct NoDefaultPredicate { + NoDefaultPredicate() = delete; + constexpr bool operator()(int) const; +}; + +constexpr bool test() { + { + std::ranges::filter_view view; + auto it = view.begin(), end = view.end(); + assert(*it++ == 2); + assert(*it++ == 4); + assert(*it++ == 6); + assert(*it++ == 8); + assert(it == end); + } + + { + std::ranges::filter_view view = {}; + auto it = view.begin(), end = view.end(); + assert(*it++ == 2); + assert(*it++ == 4); + assert(*it++ == 6); + assert(*it++ == 8); + assert(it == end); + } + + static_assert(!std::is_default_constructible_v>); + static_assert(!std::is_default_constructible_v>); + static_assert(!std::is_default_constructible_v>); + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/ctor.view_pred.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/ctor.view_pred.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/ctor.view_pred.pass.cpp @@ -0,0 +1,102 @@ +//===----------------------------------------------------------------------===// +// +// 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: libcpp-has-no-incomplete-ranges + +// constexpr filter_view(View, Pred); + +#include + +#include +#include "types.h" + +struct Range : std::ranges::view_base { + constexpr explicit Range(int* b, int* e) : begin_(b), end_(e) { } + constexpr int* begin() const { return begin_; } + constexpr int* end() const { return end_; } + +private: + int* begin_; + int* end_; +}; + +struct Pred { + constexpr bool operator()(int i) const { return i % 2 != 0; } +}; + +struct TrackingPred : TrackInitialization { + using TrackInitialization::TrackInitialization; + constexpr bool operator()(int) const; +}; + +struct TrackingRange : TrackInitialization, std::ranges::view_base { + using TrackInitialization::TrackInitialization; + int* begin() const; + int* end() const; +}; + +constexpr bool test() { + int buff[] = {1, 2, 3, 4, 5, 6, 7, 8}; + + // Test explicit syntax + { + Range range(buff, buff + 8); + Pred pred; + std::ranges::filter_view view(range, pred); + auto it = view.begin(), end = view.end(); + assert(*it++ == 1); + assert(*it++ == 3); + assert(*it++ == 5); + assert(*it++ == 7); + assert(it == end); + } + + // Test implicit syntax + { + Range range(buff, buff + 8); + Pred pred; + std::ranges::filter_view view = {range, pred}; + auto it = view.begin(), end = view.end(); + assert(*it++ == 1); + assert(*it++ == 3); + assert(*it++ == 5); + assert(*it++ == 7); + assert(it == end); + } + + // Make sure we move the view + { + bool moved = false, copied = false; + TrackingRange range(&moved, &copied); + Pred pred; + std::ranges::filter_view view(std::move(range), pred); (void)view; + assert(moved); + assert(!copied); + } + + // Make sure we move the predicate + { + bool moved = false, copied = false; + Range range(buff, buff + 8); + TrackingPred pred(&moved, &copied); + std::ranges::filter_view view(range, std::move(pred)); (void)view; + assert(moved); + assert(!copied); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/end.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/end.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/end.pass.cpp @@ -0,0 +1,107 @@ +//===----------------------------------------------------------------------===// +// +// 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: libcpp-has-no-incomplete-ranges + +// constexpr auto end(); + +#include + +#include +#include +#include "test_iterators.h" + +struct Range : std::ranges::view_base { + using Iterator = forward_iterator; + using Sentinel = sentinel_wrapper; + constexpr explicit Range(int* b, int* e) : begin_(b), end_(e) { } + constexpr Iterator begin() const { return Iterator(begin_); } + constexpr Sentinel end() const { return Sentinel(Iterator(end_)); } + +private: + int* begin_; + int* end_; +}; + +struct CommonRange : std::ranges::view_base { + using Iterator = forward_iterator; + constexpr explicit CommonRange(int* b, int* e) : begin_(b), end_(e) { } + constexpr Iterator begin() const { return Iterator(begin_); } + constexpr Iterator end() const { return Iterator(end_); } + +private: + int* begin_; + int* end_; +}; + +constexpr bool test() { + int buff[] = {1, 2, 3, 4, 5, 6, 7, 8}; + + // end() on an empty range + { + Range range(buff, buff); + auto pred = [](int) { return true; }; + std::ranges::filter_view view(range, pred); + auto end = view.end(); + assert(end.base().base().base() == buff); + static_assert(!std::is_same_v); + } + + // end() on a 1-element range + { + Range range(buff, buff + 1); + auto pred = [](int) { return true; }; + std::ranges::filter_view view(range, pred); + auto end = view.end(); + assert(end.base().base().base() == buff + 1); + static_assert(!std::is_same_v); + } + + // end() on a 2-element range + { + Range range(buff, buff + 2); + auto pred = [](int) { return true; }; + std::ranges::filter_view view(range, pred); + auto end = view.end(); + assert(end.base().base().base() == buff + 2); + static_assert(!std::is_same_v); + } + + // end() on a N-element range + { + for (int k = 1; k != 8; ++k) { + Range range(buff, buff + 8); + auto pred = [=](int i) { return i == k; }; + std::ranges::filter_view view(range, pred); + auto end = view.end(); + assert(end.base().base().base() == buff + 8); + static_assert(!std::is_same_v); + } + } + + // end() on a common_range + { + CommonRange range(buff, buff + 8); + auto pred = [](int i) { return i % 2 == 0; }; + std::ranges::filter_view view(range, pred); + auto end = view.end(); + assert(end.base().base() == buff + 8); + static_assert(std::is_same_v); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/pred.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/pred.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/pred.pass.cpp @@ -0,0 +1,66 @@ +//===----------------------------------------------------------------------===// +// +// 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: libcpp-has-no-incomplete-ranges + +// Older Clangs don't properly deduce decltype(auto) with a concept constraint +// XFAIL: clang-11, clang-12 +// XFAIL: apple-clang-12, apple-clang-13 + +// constexpr Pred const& pred() const; + +#include + +#include +#include + +struct Range : std::ranges::view_base { + int* begin() const; + int* end() const; +}; + +struct Pred { + bool operator()(int) const; + int value; +}; + +constexpr bool test() { + { + Pred pred{42}; + std::ranges::filter_view const view(Range{}, pred); + std::same_as decltype(auto) result = view.pred(); + assert(result.value == 42); + + // Make sure we're really holding a reference to something inside the view + std::same_as decltype(auto) result2 = view.pred(); + assert(&result == &result2); + } + + // Same, but calling on a non-const view + { + Pred pred{42}; + std::ranges::filter_view view(Range{}, pred); + std::same_as decltype(auto) result = view.pred(); + assert(result.value == 42); + + // Make sure we're really holding a reference to something inside the view + std::same_as decltype(auto) result2 = view.pred(); + assert(&result == &result2); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/types.h b/libcxx/test/std/ranges/range.adaptors/range.filter/types.h new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/types.h @@ -0,0 +1,26 @@ +//===----------------------------------------------------------------------===// +// +// 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_FILTER_TYPES_H +#define TEST_STD_RANGES_RANGE_ADAPTORS_RANGE_FILTER_TYPES_H + +struct TrackInitialization { + constexpr explicit TrackInitialization(bool* moved, bool* copied) : moved_(moved), copied_(copied) { } + constexpr TrackInitialization(TrackInitialization const& other) : moved_(other.moved_), copied_(other.copied_) { + *copied_ = true; + } + constexpr TrackInitialization(TrackInitialization&& other) : moved_(other.moved_), copied_(other.copied_) { + *moved_ = true; + } + TrackInitialization& operator=(TrackInitialization const&) = default; + TrackInitialization& operator=(TrackInitialization&&) = default; + bool* moved_; + bool* copied_; +}; + +#endif // TEST_STD_RANGES_RANGE_ADAPTORS_RANGE_FILTER_TYPES_H