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 @@ -137,7 +137,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 @@ -320,6 +320,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/forward.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& noexcept { 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 @@ -790,6 +790,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,15 @@ +//===----------------------------------------------------------------------===// +// +// 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(base(base(end.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(base(base(end.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(base(base(end.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(base(base(end.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/iterator/arrow.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/arrow.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/arrow.pass.cpp @@ -0,0 +1,120 @@ +//===----------------------------------------------------------------------===// +// +// 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_t operator->() const +// requires has-arrow> && copyable> + +#include + +#include +#include +#include +#include +#include +#include "test_iterators.h" +#include "test_macros.h" +#include "../types.h" + +struct Point { + int x; + int y; +}; + +template +concept has_arrow = requires (T t) { + { t->x }; +}; + +struct WithoutArrowOperator : std::ranges::view_base { + struct iterator : contiguous_iterator { + Point* operator->() const = delete; + iterator& operator++(); + iterator operator++(int); + }; + + iterator begin() const; + sentinel_wrapper end() const; +}; + +struct WithNonCopyableIterator : std::ranges::view_base { + struct iterator : contiguous_iterator { + iterator(iterator&&) = default; + iterator& operator=(iterator&&) = default; + + iterator(iterator const&) = delete; + iterator& operator=(iterator const&) = delete; + + Point* operator->() const; + iterator& operator++(); + iterator operator++(int); + + friend Point* base(iterator const&); + }; + + iterator begin() const; + sentinel_wrapper end() const; +}; + +template > +constexpr void test() { + std::array array{{{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}}}; + using View = minimal_view; + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + + auto make_filter_view = [](auto begin, auto end, auto pred) { + View view{Iterator(begin), Sentinel(Iterator(end))}; + return FilterView(std::move(view), pred); + }; + + for (std::ptrdiff_t n = 0; n != 5; ++n) { + FilterView view = make_filter_view(array.begin(), array.end(), AlwaysTrue{}); + FilterIterator const iter(view, Iterator(array.begin() + n)); + std::same_as auto result = iter.operator->(); + assert(base(result) == array.begin() + n); + assert(iter->x == n); + assert(iter->y == n); + } +} + +constexpr bool tests() { + // TODO: None of these archetypes should actually provide operator-> by default. + test>(); + // cpp20_input_iterator is not copyable, so it doesn't get operator-> + test>(); + test>(); + test>(); + test>(); + + // Make sure filter_view::iterator doesn't have operator-> if the + // underlying iterator doesn't have one. + { + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + static_assert(!has_arrow); + } + + // Make sure filter_view::iterator doesn't have operator-> if the + // underlying iterator is not copyable. + { + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + static_assert(!has_arrow); + } + return true; +} + +int main(int, char**) { + tests(); + static_assert(tests()); + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/base.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/base.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/base.pass.cpp @@ -0,0 +1,70 @@ +//===----------------------------------------------------------------------===// +// +// 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_t const& base() const& noexcept; +// constexpr iterator_t base() &&; + +#include + +#include +#include +#include +#include +#include "test_iterators.h" +#include "test_macros.h" +#include "../types.h" + +template > +constexpr void test() { + using View = minimal_view; + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + + auto make_filter_view = [](auto begin, auto end, auto pred) { + View view{Iterator(begin), Sentinel(Iterator(end))}; + return FilterView(std::move(view), pred); + }; + + std::array array{0, 1, 2, 3, 4}; + FilterView view = make_filter_view(array.begin(), array.end(), AlwaysTrue{}); + + // Test the const& version + { + FilterIterator const iter(view, Iterator(array.begin())); + std::same_as auto& result = iter.base(); + ASSERT_NOEXCEPT(iter.base()); + assert(base(result) == array.begin()); + } + + // Test the && version + { + FilterIterator iter(view, Iterator(array.begin())); + std::same_as auto result = std::move(iter).base(); + assert(base(result) == array.begin()); + } +} + +constexpr bool tests() { + test>(); + test>(); + test>(); + test>(); + test>(); + test>(); + return true; +} + +int main(int, char**) { + tests(); + static_assert(tests()); + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/compare.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/compare.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/compare.pass.cpp @@ -0,0 +1,83 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// friend constexpr bool operator==(iterator const&, iterator const&) +// requires equality_comparable> + +#include + +#include +#include +#include +#include +#include "test_iterators.h" +#include "test_macros.h" +#include "../types.h" + +template +concept has_equal = requires (T const& x, T const& y) { { x == y }; }; + +template +using FilterIteratorFor = std::ranges::iterator_t< + std::ranges::filter_view>, AlwaysTrue> +>; + +template > +constexpr void test() { + using View = minimal_view; + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + + auto make_filter_view = [](auto begin, auto end, auto pred) { + View view{Iterator(begin), Sentinel(Iterator(end))}; + return FilterView(std::move(view), pred); + }; + + { + std::array array{0, 1, 2, 3, 4}; + FilterView view = make_filter_view(array.begin(), array.end(), AlwaysTrue{}); + FilterIterator it1 = view.begin(); + FilterIterator it2 = view.begin(); + std::same_as auto result = (it1 == it2); + assert(result); + + ++it1; + assert(!(it1 == it2)); + } + + { + std::array array{0, 1, 2, 3, 4}; + FilterView view = make_filter_view(array.begin(), array.end(), AlwaysTrue{}); + assert(!(view.begin() == view.end())); + } +} + +constexpr bool tests() { + test>(); + test>(); + test>(); + test>(); + test>(); + + // Make sure `operator==` isn't provided for non comparable iterators + { + static_assert(!has_equal>>); + } + + return true; +} + +int main(int, char**) { + tests(); + static_assert(tests()); + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/ctor.default.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/ctor.default.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/ctor.default.pass.cpp @@ -0,0 +1,56 @@ +//===----------------------------------------------------------------------===// +// +// 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::ranges::filter_view::() requires default_initializable> = default; + +#include + +#include +#include +#include "test_iterators.h" +#include "../types.h" + +template +constexpr void test_default_constructible() { + // Make sure the iterator is default constructible when the underlying iterator is. + using View = minimal_view>; + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + FilterIterator iter1{}; + FilterIterator iter2; + assert(iter1 == iter2); +} + +template +constexpr void test_not_default_constructible() { + // Make sure the iterator is *not* default constructible when the underlying iterator isn't. + using View = minimal_view>; + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + static_assert(!std::is_default_constructible_v); +} + +constexpr bool tests() { + test_not_default_constructible>(); + test_not_default_constructible>(); + test_default_constructible>(); + test_default_constructible>(); + test_default_constructible>(); + test_default_constructible>(); + return true; +} + +int main(int, char**) { + tests(); + static_assert(tests()); + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/ctor.parent_iter.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/ctor.parent_iter.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/ctor.parent_iter.pass.cpp @@ -0,0 +1,51 @@ +//===----------------------------------------------------------------------===// +// +// 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 std::ranges::filter_view::(filter_view&, iterator_t); + +#include + +#include +#include +#include "test_iterators.h" +#include "../types.h" + +template > +constexpr void test() { + using View = minimal_view; + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + + std::array array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + View view(Iterator(array.begin()), Sentinel(Iterator(array.end()))); + Iterator iter = view.begin(); + + FilterView filter_view(std::move(view), AlwaysTrue{}); + FilterIterator filter_iter(filter_view, std::move(iter)); + assert(base(filter_iter.base()) == array.begin()); +} + +constexpr bool tests() { + test>(); + test>(); + test>(); + test>(); + test>(); + test>(); + return true; +} + +int main(int, char**) { + tests(); + static_assert(tests()); + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/decrement.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/decrement.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/decrement.pass.cpp @@ -0,0 +1,136 @@ +//===----------------------------------------------------------------------===// +// +// 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& operator--() requires bidirectional_range; +// constexpr iterator operator--(int) requires bidirectional_range; + +#include + +#include +#include +#include +#include +#include +#include "test_iterators.h" +#include "test_macros.h" +#include "../types.h" + +struct EqualTo { + int x; + constexpr bool operator()(int y) const { return x == y; } +}; + +template +concept has_pre_decrement = requires (T t) { { --t }; }; + +template +concept has_post_decrement = requires (T t) { { t-- }; }; + +template +using FilterIteratorFor = std::ranges::iterator_t< + std::ranges::filter_view>, EqualTo> +>; + +template > +constexpr void test() { + using View = minimal_view; + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + + auto make_filter_view = [](auto begin, auto end, auto pred) { + View view{Iterator(begin), Sentinel(Iterator(end))}; + return FilterView(std::move(view), pred); + }; + + // Test with a single satisfied value + { + std::array array{0, 1, 2, 3, 4}; + FilterView view = make_filter_view(array.begin(), array.end(), EqualTo{1}); + FilterIterator it = std::ranges::next(view.begin(), view.end()); + assert(base(it.base()) == array.end()); // test the test + + std::same_as auto& result = --it; + assert(&result == &it); + assert(base(result.base()) == array.begin() + 1); + } + + // Test with more than one satisfied value + { + std::array array{0, 1, 2, 3, 1, 4}; + FilterView view = make_filter_view(array.begin(), array.end(), EqualTo{1}); + FilterIterator it = std::ranges::next(view.begin(), view.end()); + assert(base(it.base()) == array.end()); // test the test + + std::same_as auto& result = --it; + assert(&result == &it); + assert(base(result.base()) == array.begin() + 4); + + --it; + assert(base(it.base()) == array.begin() + 1); + } + + // Test going forward and then backward on the same iterator + { + std::array array{0, 1, 2, 3, 1, 1, 4, 5, 1, 6}; + FilterView view = make_filter_view(array.begin(), array.end(), EqualTo{1}); + FilterIterator it = view.begin(); + ++it; + --it; assert(base(it.base()) == array.begin() + 1); + ++it; ++it; + --it; assert(base(it.base()) == array.begin() + 4); + ++it; ++it; + --it; assert(base(it.base()) == array.begin() + 5); + ++it; ++it; + --it; assert(base(it.base()) == array.begin() + 8); + } + + // Test post-decrement + { + std::array array{0, 1, 2, 3, 1, 4}; + FilterView view = make_filter_view(array.begin(), array.end(), EqualTo{1}); + FilterIterator it = std::ranges::next(view.begin(), view.end()); + assert(base(it.base()) == array.end()); // test the test + + std::same_as auto result = it--; + assert(base(result.base()) == array.end()); + assert(base(it.base()) == array.begin() + 4); + + result = it--; + assert(base(result.base()) == array.begin() + 4); + assert(base(it.base()) == array.begin() + 1); + } +} + +constexpr bool tests() { + test>(); + test>(); + test>(); + + // Make sure `operator--` isn't provided for non bidirectional ranges + { + static_assert(!has_pre_decrement>>); + static_assert(!has_pre_decrement>>); + static_assert(!has_pre_decrement>>); + + static_assert(!has_post_decrement>>); + static_assert(!has_post_decrement>>); + static_assert(!has_post_decrement>>); + } + + return true; +} + +int main(int, char**) { + tests(); + static_assert(tests()); + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/deref.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/deref.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/deref.pass.cpp @@ -0,0 +1,60 @@ +//===----------------------------------------------------------------------===// +// +// 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 range_reference_t operator*() const; + +#include + +#include +#include +#include +#include +#include "test_iterators.h" +#include "test_macros.h" +#include "../types.h" + +template > +constexpr void test() { + using View = minimal_view; + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + + auto make_filter_view = [](auto begin, auto end, auto pred) { + View view{Iterator(begin), Sentinel(Iterator(end))}; + return FilterView(std::move(view), pred); + }; + + std::array array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + FilterView view = make_filter_view(array.begin(), array.end(), AlwaysTrue{}); + + for (std::ptrdiff_t n = 0; n != 9; ++n) { + FilterIterator const iter(view, Iterator(array.begin() + n)); + std::same_as auto& result = *iter; + assert(&result == array.begin() + n); + } +} + +constexpr bool tests() { + test>(); + test>(); + test>(); + test>(); + test>(); + test>(); + return true; +} + +int main(int, char**) { + tests(); + static_assert(tests()); + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/increment.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/increment.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/increment.pass.cpp @@ -0,0 +1,140 @@ +//===----------------------------------------------------------------------===// +// +// 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& operator++(); +// constexpr void operator++(int); +// constexpr iterator operator++(int) requires forward_range; + +#include + +#include +#include +#include +#include +#include +#include "test_iterators.h" +#include "test_macros.h" +#include "../types.h" + +struct EqualTo { + int x; + constexpr bool operator()(int y) const { return x == y; } +}; + +template > +constexpr void test() { + using View = minimal_view; + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + + auto make_filter_view = [](auto begin, auto end, auto pred) { + View view{Iterator(begin), Sentinel(Iterator(end))}; + return FilterView(std::move(view), pred); + }; + + // Increment an iterator when it won't find another satisfied value after begin() + { + std::array array{0, 1, 2, 3, 4}; + FilterView view = make_filter_view(array.begin(), array.end(), EqualTo{1}); + + FilterIterator it = view.begin(); + std::same_as auto& result = ++it; + assert(&result == &it); + assert(base(result.base()) == array.end()); + } + + // Increment the iterator and it finds another value after begin() + { + std::array array{99, 1, 99, 1, 99}; + FilterView view = make_filter_view(array.begin(), array.end(), EqualTo{1}); + + FilterIterator it = view.begin(); + ++it; + assert(base(it.base()) == array.begin() + 3); + } + + // Increment advances all the way to the end of the range + { + std::array array{99, 1, 99, 99, 1}; + FilterView view = make_filter_view(array.begin(), array.end(), EqualTo{1}); + + FilterIterator it = view.begin(); + ++it; + assert(base(it.base()) == array.begin() + 4); + } + + // Increment an iterator multiple times + { + std::array array{0, 1, 2, 3, 1, 1, 4, 5, 1, 6}; + FilterView view = make_filter_view(array.begin(), array.end(), EqualTo{1}); + + FilterIterator it = view.begin(); + assert(base(it.base()) == array.begin() + 1); + ++it; assert(base(it.base()) == array.begin() + 4); + ++it; assert(base(it.base()) == array.begin() + 5); + ++it; assert(base(it.base()) == array.begin() + 8); + ++it; assert(base(it.base()) == array.end()); + } + + // Check post-increment for input ranges + if constexpr (!std::ranges::forward_range) { + std::array array{0, 1, 2, 3, 1, 1, 4, 5, 1, 6}; + FilterView view = make_filter_view(array.begin(), array.end(), EqualTo{1}); + + FilterIterator it = view.begin(); + assert(base(it.base()) == array.begin() + 1); + it++; assert(base(it.base()) == array.begin() + 4); + it++; assert(base(it.base()) == array.begin() + 5); + it++; assert(base(it.base()) == array.begin() + 8); + it++; assert(base(it.base()) == array.end()); + static_assert(std::is_same_v); + } + + // Check post-increment for forward ranges + if constexpr (std::ranges::forward_range) { + std::array array{0, 1, 2, 3, 1, 1, 4, 5, 1, 6}; + FilterView view = make_filter_view(array.begin(), array.end(), EqualTo{1}); + + FilterIterator it = view.begin(); + std::same_as auto result = it++; + assert(base(result.base()) == array.begin() + 1); + assert(base(it.base()) == array.begin() + 4); + + result = it++; + assert(base(result.base()) == array.begin() + 4); + assert(base(it.base()) == array.begin() + 5); + + result = it++; + assert(base(result.base()) == array.begin() + 5); + assert(base(it.base()) == array.begin() + 8); + + result = it++; + assert(base(result.base()) == array.begin() + 8); + assert(base(it.base()) == array.end()); + } +} + +constexpr bool tests() { + test>(); + test>(); + test>(); + test>(); + test>(); + test>(); + return true; +} + +int main(int, char**) { + tests(); + // static_assert(tests()); + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/iter_move.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/iter_move.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/iter_move.pass.cpp @@ -0,0 +1,60 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// friend constexpr range_rvalue_reference_t iter_move(iterator const& i) +// noexcept(noexcept(ranges::iter_move(i.current_))); + +#include + +#include +#include +#include +#include "test_iterators.h" +#include "test_macros.h" +#include "../types.h" + +template > +constexpr void test() { + using View = minimal_view; + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + + auto make_filter_view = [](auto begin, auto end, auto pred) { + View view{Iterator(begin), Sentinel(Iterator(end))}; + return FilterView(std::move(view), pred); + }; + + { + std::array array{0, 1, 2, 3, 4}; + FilterView view = make_filter_view(array.begin(), array.end(), AlwaysTrue{}); + FilterIterator const it = view.begin(); + + int&& result = iter_move(it); + assert(&result == array.begin()); + } +} + +constexpr bool tests() { + test>(); + test>(); + test>(); + test>(); + test>(); + test>(); + return true; +} + +int main(int, char**) { + tests(); + static_assert(tests()); + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/iter_swap.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/iter_swap.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/iter_swap.pass.cpp @@ -0,0 +1,71 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// friend constexpr void iter_swap(iterator const& x, iterator const& y) +// noexcept(noexcept(ranges::iter_swap(x.current_, y.current_))) +// requires(indirectly_swappable>); + +#include + +#include +#include +#include +#include +#include "test_iterators.h" +#include "test_macros.h" +#include "../types.h" + +struct IsEven { + constexpr bool operator()(int x) const { return x % 2 == 0; } +}; + +template > +constexpr void test() { + using View = minimal_view; + using FilterView = std::ranges::filter_view; + using FilterIterator = std::ranges::iterator_t; + + auto make_filter_view = [](auto begin, auto end, auto pred) { + View view{Iterator(begin), Sentinel(Iterator(end))}; + return FilterView(std::move(view), pred); + }; + + { + std::array array{1, 2, 1, 4, 1}; + FilterView view = make_filter_view(array.begin(), array.end(), IsEven{}); + FilterIterator const it1 = view.begin(); + FilterIterator const it2 = std::ranges::next(view.begin()); + + static_assert(std::is_same_v); + ASSERT_NOT_NOEXCEPT(iter_swap(it1, it2)); + + assert(*it1 == 2 && *it2 == 4); // test the test + iter_swap(it1, it2); + assert(*it1 == 4 && *it2 == 2); + } +} + +constexpr bool tests() { + test>(); + test>(); + test>(); + test>(); + test>(); + test>(); + return true; +} + +int main(int, char**) { + tests(); + static_assert(tests()); + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/types.compile.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/types.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.filter/iterator/types.compile.pass.cpp @@ -0,0 +1,74 @@ +//===----------------------------------------------------------------------===// +// +// 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::filter_view::::difference_type +// std::filter_view::::value_type +// std::filter_view::::iterator_category +// std::filter_view::::iterator_concept + +#include + +#include +#include "test_iterators.h" +#include "../types.h" + +template +concept HasIteratorCategory = requires { + typename T::iterator_category; +}; + +template