diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -2,9 +2,9 @@ Search,any_of,Christopher Di Bella,`D105793 `_ Search,all_of,Christopher Di Bella,`D105793 `_ Search,none_of,Christopher Di Bella,`D105793 `_ -Search,find,Christopher Di Bella,`D105456 `_ -Search,find_if,Christopher Di Bella,`D105792 `_ -Search,find_if_not,Christopher Di Bella,`D105792 `_ +Search,find,Nikolas Klauser,`D121248 `_,✅ +Search,find_if,Nikolas Klauser,`D121248 `_,✅ +Search,find_if_not,Nikolas Klauser,`D121248 `_,✅ Search,find_first_of,Not assigned,n/a,Not started Search,adjacent_find,Not assigned,n/a,Not started Search,mismatch,Nikolas Klauser,`D117817 `,Complete diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -66,6 +66,9 @@ __algorithm/pop_heap.h __algorithm/prev_permutation.h __algorithm/push_heap.h + __algorithm/ranges_find.h + __algorithm/ranges_find_if.h + __algorithm/ranges_find_if_not.h __algorithm/ranges_max_element.h __algorithm/ranges_min_element.h __algorithm/ranges_mismatch.h diff --git a/libcxx/include/__algorithm/ranges_find.h b/libcxx/include/__algorithm/ranges_find.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find.h @@ -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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_H + +#include <__algorithm/ranges_find_if.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __find { +struct __fn { + template _Sp, class _Tp, class _Proj = identity> + requires indirect_binary_predicate, const _Tp*> + _LIBCPP_HIDE_FROM_ABI constexpr + _Ip operator()(_Ip __first, _Sp __last, const _Tp& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __e) { return std::forward(__e) == __value; }; + return ranges::__find_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template + requires indirect_binary_predicate, _Proj>, const _Tp*> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __e) { return std::forward(__e) == __value; }; + return ranges::__find_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } +}; +} // namespace __find + +inline namespace __cpo { + inline constexpr auto find = __find::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_H diff --git a/libcxx/include/__algorithm/ranges_find_if.h b/libcxx/include/__algorithm/ranges_find_if.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_if.h @@ -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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_IF_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_IF_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template +_LIBCPP_HIDE_FROM_ABI static constexpr +_Ip __find_if_impl(_Ip __first, _Sp __last, _Pred& __pred, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) + break; + } + return __first; +} + +namespace __find_if { +struct __fn { + + template _Sp, class _Proj = identity, + indirect_unary_predicate> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + _Ip operator()(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj = {}) const { + return ranges::__find_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template , _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + return ranges::__find_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } +}; +} // namespace __find_if + +inline namespace __cpo { + inline constexpr auto find_if = __find_if::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_IF_H diff --git a/libcxx/include/__algorithm/ranges_find_if_not.h b/libcxx/include/__algorithm/ranges_find_if_not.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_if_not.h @@ -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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_IF_NOT_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_IF_NOT_H + +#include <__algorithm/ranges_find_if.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __find_if_not { +struct __fn { + template _Sp, class _Proj = identity, + indirect_unary_predicate> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + _Ip operator()(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj = {}) const { + auto __pred2 = [&](auto&& __e) { return !std::invoke(__pred, std::forward(__e)); }; + return ranges::__find_if_impl(std::move(__first), std::move(__last), __pred2, __proj); + } + + template , _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + auto __pred2 = [&](auto&& __e) { return !std::invoke(__pred, std::forward(__e)); }; + return ranges::__find_if_impl(ranges::begin(__r), ranges::end(__r), __pred2, __proj); + } +}; +} // namespace __find_if_not + +inline namespace __cpo { + inline constexpr auto find_if_not = __find_if_not::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_IF_NOT_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -56,6 +56,33 @@ requires indirectly_comparable, iterator_t, Pred, Proj1, Proj2> constexpr mismatch_result, borrowed_iterator_t> mismatch(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) // since C++20 + + template S, class T, class Proj = identity> + requires indirect_binary_predicate, const T*> + constexpr I find(I first, S last, const T& value, Proj proj = {}); // since C++20 + + template + requires indirect_binary_predicate, Proj>, const T*> + constexpr borrowed_iterator_t + find(R&& r, const T& value, Proj proj = {}); // since C++20 + + template S, class Proj = identity, + indirect_unary_predicate> Pred> + constexpr I find_if(I first, S last, Pred pred, Proj proj = {}); // since C++20 + + template, Proj>> Pred> + constexpr borrowed_iterator_t + find_if(R&& r, Pred pred, Proj proj = {}); // since C++20 + + template S, class Proj = identity, + indirect_unary_predicate> Pred> + constexpr I find_if_not(I first, S last, Pred pred, Proj proj = {}); // since C++20 + + template, Proj>> Pred> + constexpr borrowed_iterator_t + find_if_not(R&& r, Pred pred, Proj proj = {}); // since C++20 } template @@ -775,6 +802,9 @@ #include <__algorithm/pop_heap.h> #include <__algorithm/prev_permutation.h> #include <__algorithm/push_heap.h> +#include <__algorithm/ranges_find.h> +#include <__algorithm/ranges_find_if.h> +#include <__algorithm/ranges_find_if_not.h> #include <__algorithm/ranges_max_element.h> #include <__algorithm/ranges_min_element.h> #include <__algorithm/ranges_mismatch.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -294,6 +294,9 @@ module pop_heap { private header "__algorithm/pop_heap.h" } module prev_permutation { private header "__algorithm/prev_permutation.h" } module push_heap { private header "__algorithm/push_heap.h" } + module ranges_find { private header "__algorithm/ranges_find.h" } + module ranges_find_if { private header "__algorithm/ranges_find_if.h" } + module ranges_find_if_not { private header "__algorithm/ranges_find_if_not.h" } module ranges_max_element { private header "__algorithm/ranges_max_element.h" } module ranges_min_element { private header "__algorithm/ranges_min_element.h" } module ranges_mismatch { private header "__algorithm/ranges_mismatch.h" } diff --git a/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find.module.verify.cpp b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find.module.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find.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: '__algorithm/ranges_find.h'}} +#include <__algorithm/ranges_find.h> diff --git a/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if.module.verify.cpp b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if.module.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if.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: '__algorithm/ranges_find_if.h'}} +#include <__algorithm/ranges_find_if.h> diff --git a/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if_not.module.verify.cpp b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if_not.module.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if_not.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: '__algorithm/ranges_find_if_not.h'}} +#include <__algorithm/ranges_find_if_not.h> diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp @@ -0,0 +1,258 @@ +//===----------------------------------------------------------------------===// +// +// 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-has-no-incomplete-ranges + +// template S, class T, class Proj = identity> +// requires indirect_binary_predicate, const T*> +// constexpr I ranges::find(I first, S last, const T& value, Proj proj = {}); +// template +// requires indirect_binary_predicate, Proj>, const T*> +// constexpr borrowed_iterator_t +// ranges::find(R&& r, const T& value, Proj proj = {}); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +struct NotEqualityComparable {}; + +template +concept HasFindIt = requires(It it, Sent sent) { std::ranges::find(it, sent, *it); }; +static_assert(HasFindIt); +static_assert(!HasFindIt); +static_assert(!HasFindIt); +static_assert(!HasFindIt); +static_assert(!HasFindIt); +static_assert(!HasFindIt, SentinelForNotSemiregular>); +static_assert(!HasFindIt, InputRangeNotSentinelEqualityComparableWith>); + +static_assert(!HasFindIt); +static_assert(!HasFindIt); + +template +concept HasFindR = requires(Range r) { std::ranges::find(r, ValT{}); }; +static_assert(HasFindR, int>); +static_assert(!HasFindR); +static_assert(!HasFindR, NotEqualityComparable>); +static_assert(!HasFindR); +static_assert(!HasFindR); +static_assert(!HasFindR); +static_assert(!HasFindR); +static_assert(!HasFindR); + +template +constexpr void test_iterators() { + { + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find(It(a), Sent(It(a + 4)), 4); + assert(base(ret) == a + 3); + assert(*ret == 4); + } + { + int a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); + std::same_as auto ret = std::ranges::find(range, 4); + assert(base(ret) == a + 3); + assert(*ret == 4); + } +} + +struct OneWayComparable { + bool isLeft; + friend constexpr bool operator==(OneWayComparable l, OneWayComparable) { return l.isLeft; } +}; + +struct NonConstComparableLValue { + friend constexpr bool operator==(const NonConstComparableLValue&, const NonConstComparableLValue&) { return false; } + friend constexpr bool operator==(NonConstComparableLValue&, NonConstComparableLValue&) { return false; } + friend constexpr bool operator==(const NonConstComparableLValue&, NonConstComparableLValue&) { return false; } + friend constexpr bool operator==(NonConstComparableLValue&, const NonConstComparableLValue&) { return true; } +}; + +struct NonConstComparableRValue { + friend constexpr bool operator==(const NonConstComparableRValue&, const NonConstComparableRValue&) { return false; } + friend constexpr bool operator==(const NonConstComparableRValue&&, const NonConstComparableRValue&&) { return false; } + friend constexpr bool operator==(NonConstComparableRValue&&, NonConstComparableRValue&&) { return false; } + friend constexpr bool operator==(NonConstComparableRValue&&, const NonConstComparableRValue&) { return true; } +}; + +constexpr bool test() { + test_iterators(); + test_iterators(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + + { + // check that projections are used properly and that they are called with the iterator directly + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find(a, a + 4, a + 3, [](int& i) { return &i; }); + assert(ret == a + 3); + } + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find(a, a + 3, [](int& i) { return &i; }); + assert(ret == a + 3); + } + } + + { // check that the first element is returned + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::find(a, 0, &S::comp); + assert(ret == a); + assert(ret->comp == 0); + assert(ret->other == 0); + } + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::find(a, a + 3, 0, &S::comp); + assert(ret == a); + assert(ret->comp == 0); + assert(ret->other == 0); + } + } + + { // check that end + 1 iterator is returned with no match + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find(a, a + 3, 0); + assert(ret == a + 3); + } + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find(a, 0); + assert(ret == a + 3); + } + } + + { + // check that ranges::dangling is returned + [[maybe_unused]] std::same_as auto ret = + std::ranges::find(std::array{1, 2}, 3); + } + + { + // check that an iterator is returned with a borrowing range + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find(std::views::all(a), 1); + assert(ret == a); + assert(*ret == 1); + } + + { + // check that std::invoke is used + struct S { int i; }; + S a[] = { S{1}, S{3}, S{2} }; + std::same_as auto ret = std::ranges::find(a, 4, &S::i); + assert(ret == a + 3); + } + + { + // count invocations of the projection + { + int a[] = {1, 2, 3, 4}; + int projection_count = 0; + auto ret = std::ranges::find(a, a + 4, 2, [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(projection_count == 2); + } + { + int a[] = {1, 2, 3, 4}; + int projection_count = 0; + auto ret = std::ranges::find(a, 2, [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(projection_count == 2); + } + } + + { + // check comparison order + { + OneWayComparable a[] = { OneWayComparable{true} }; + auto ret = std::ranges::find(a, a + 1, OneWayComparable{false}); + assert(ret == a); + } + { + OneWayComparable a[] = { OneWayComparable{true} }; + auto ret = std::ranges::find(a, OneWayComparable{false}); + assert(ret == a); + } + } + + { + // check that the return type of `iter::operator*` doesn't change + { + NonConstComparableLValue a[] = { NonConstComparableLValue{} }; + auto ret = std::ranges::find(a, a + 1, NonConstComparableLValue{}); + assert(ret == a); + } + { + using It = std::move_iterator; + NonConstComparableRValue a[] = { NonConstComparableRValue{} }; + auto ret = std::ranges::find(It(a), It(a + 1), NonConstComparableRValue{}); + assert(ret.base() == a); + } + { + NonConstComparableLValue a[] = { NonConstComparableLValue{} }; + auto ret = std::ranges::find(a, NonConstComparableLValue{}); + assert(ret == a); + } + { + using It = std::move_iterator; + NonConstComparableRValue a[] = { NonConstComparableRValue{} }; + auto range = std::ranges::subrange(It(a), It(a + 1)); + auto ret = std::ranges::find(range, NonConstComparableRValue{}); + assert(ret.base() == a); + } + } + + { + // check that an empty range works + { + std::array a = {}; + auto ret = std::ranges::find(a.begin(), a.end(), 1); + assert(ret == a.begin()); + } + { + std::array a = {}; + auto ret = std::ranges::find(a, 1); + assert(ret == a.begin()); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if.pass.cpp @@ -0,0 +1,235 @@ +//===----------------------------------------------------------------------===// +// +// 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-has-no-incomplete-ranges + +// template S, class Proj = identity, +// indirect_unary_predicate> Pred> +// constexpr I ranges::find_if(I first, S last, Pred pred, Proj proj = {}); +// template, Proj>> Pred> +// constexpr borrowed_iterator_t +// ranges::find_if(R&& r, Pred pred, Proj proj = {}); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +struct Predicate { + bool operator()(int); +}; + +template +concept HasFindIfIt = requires(It it, Sent sent) { std::ranges::find_if(it, sent, Predicate{}); }; +static_assert(HasFindIfIt); +static_assert(!HasFindIfIt); +static_assert(!HasFindIfIt); +static_assert(!HasFindIfIt); +static_assert(!HasFindIfIt, SentinelForNotSemiregular>); +static_assert(!HasFindIfIt, InputRangeNotSentinelEqualityComparableWith>); + +static_assert(!HasFindIfIt); +static_assert(!HasFindIfIt); + +template +concept HasFindIfPred = requires(int* it, Pred pred) {std::ranges::find_if(it, it, pred); }; + +static_assert(!HasFindIfPred); +static_assert(!HasFindIfPred); + +template +concept HasFindIfR = requires(R r) { std::ranges::find_if(r, Predicate{}); }; +static_assert(HasFindIfR>); +static_assert(!HasFindIfR); +static_assert(!HasFindIfR); +static_assert(!HasFindIfR); +static_assert(!HasFindIfR); +static_assert(!HasFindIfR); +static_assert(!HasFindIfR); + +template +constexpr void test_iterators() { + { + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find_if(It(a), Sent(It(a + 4)), [](int x) mutable { return x == 4; }); + assert(base(ret) == a + 3); + assert(*ret == 4); + } + { + int a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); + std::same_as auto ret = std::ranges::find_if(range, [](int x) mutable { return x == 4; }); + assert(base(ret) == a + 3); + assert(*ret == 4); + } +} + +struct NonConstComparable { + friend constexpr bool operator==(const NonConstComparable&, const NonConstComparable&) { return false; } + friend constexpr bool operator==(NonConstComparable&, NonConstComparable&) { return false; } + friend constexpr bool operator==(const NonConstComparable&, NonConstComparable&) { return false; } + friend constexpr bool operator==(NonConstComparable&, const NonConstComparable&) { return true; } +}; + +constexpr bool test() { + test_iterators(); + test_iterators(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + + { + // check that projections are used properly and that they are called with the iterator directly + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_if(a, a + 4, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }); + assert(ret == a + 3); + } + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_if(a, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }); + assert(ret == a + 3); + } + } + + { + // check that the first element is returned + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::find_if(a, [](int i){ return i == 0; }, &S::comp); + assert(ret == a); + assert(ret->comp == 0); + assert(ret->other == 0); + } + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::find_if(a, a + 3, [](int i) { return i == 0; }, &S::comp); + assert(ret == a); + assert(ret->comp == 0); + assert(ret->other == 0); + } + } + + { + // check that end + 1 iterator is returned with no match + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find_if(a, a + 3, [](int) { return false; }); + assert(ret == a + 3); + } + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find_if(a, [](int){ return false; }); + assert(ret == a + 3); + } + } + + { + // check that ranges::dangling is returned + [[maybe_unused]] std::same_as auto ret = + std::ranges::find_if(std::array{1, 2}, [](int){ return false; }); + } + + { + // check that an iterator is returned with a borrowing range + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find_if(std::views::all(a), [](int){ return true; }); + assert(ret == a); + assert(*ret == 1); + } + + { + // check that std::invoke is used + struct S { int i; }; + S a[] = { S{1}, S{3}, S{2} }; + std::same_as auto ret = std::ranges::find_if(a, [](int) { return false; }, &S::i); + assert(ret == a + 3); + } + + { + // count projection and predicate invocation count + { + int a[] = {1, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::find_if(a, a + 4, + [&](int i) { ++predicate_count; return i == 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(predicate_count == 2); + assert(projection_count == 2); + } + { + int a[] = {1, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::find_if(a, + [&](int i) { ++predicate_count; return i == 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(predicate_count == 2); + assert(projection_count == 2); + } + } + + { + // check that the return type of `iter::operator*` doesn't change + { + NonConstComparable a[] = { NonConstComparable{} }; + auto ret = std::ranges::find_if(a, a + 1, [](auto&& e) { return e == NonConstComparable{}; }); + assert(ret == a); + } + { + NonConstComparable a[] = { NonConstComparable{} }; + auto ret = std::ranges::find_if(a, [](auto&& e) { return e == NonConstComparable{}; }); + assert(ret == a); + } + } + + { + // check that an empty range works + { + std::array a = {}; + auto ret = std::ranges::find_if(a.begin(), a.end(), [](int) { return true; }); + assert(ret == a.begin()); + } + { + std::array a = {}; + auto ret = std::ranges::find_if(a, [](int) { return true; }); + assert(ret == a.begin()); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if_not.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if_not.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if_not.pass.cpp @@ -0,0 +1,229 @@ +//===----------------------------------------------------------------------===// +// +// 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-has-no-incomplete-ranges + +// template S, class Proj = identity, +// indirect_unary_predicate> Pred> +// constexpr I ranges::find_if_not(I first, S last, Pred pred, Proj proj = {}); +// template, Proj>> Pred> +// constexpr borrowed_iterator_t +// ranges::find_if_not(R&& r, Pred pred, Proj proj = {}); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +struct Predicate { + bool operator()(int); +}; + +template +concept HasFindIfNotIt = requires(It it, Sent sent) { std::ranges::find_if_not(it, sent, Predicate{}); }; +static_assert(HasFindIfNotIt); +static_assert(!HasFindIfNotIt); +static_assert(!HasFindIfNotIt); +static_assert(!HasFindIfNotIt); +static_assert(!HasFindIfNotIt, SentinelForNotSemiregular>); +static_assert(!HasFindIfNotIt, InputRangeNotSentinelEqualityComparableWith>); + +static_assert(!HasFindIfNotIt); +static_assert(!HasFindIfNotIt); + +template +concept HasFindIfNotPred = requires(int* it, Pred pred) {std::ranges::find_if_not(it, it, pred); }; + +static_assert(!HasFindIfNotPred); +static_assert(!HasFindIfNotPred); + +template +concept HasFindIfNotR = requires(R r) { std::ranges::find_if_not(r, Predicate{}); }; +static_assert(HasFindIfNotR>); +static_assert(!HasFindIfNotR); +static_assert(!HasFindIfNotR); +static_assert(!HasFindIfNotR); +static_assert(!HasFindIfNotR); +static_assert(!HasFindIfNotR); +static_assert(!HasFindIfNotR); + +template +constexpr void test_iterators() { + { + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find_if_not(It(a), Sent(It(a + 4)), [c = 0](int) mutable { return c++ <= 2; }); + assert(base(ret) == a + 3); + assert(*ret == 4); + } + { + int a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); + std::same_as auto ret = std::ranges::find_if_not(range, [c = 0](int) mutable { return c++ <= 2; }); + assert(base(ret) == a + 3); + assert(*ret == 4); + } +} + +struct NonConstComparableLValue { + friend constexpr bool operator==(const NonConstComparableLValue&, const NonConstComparableLValue&) { return false; } + friend constexpr bool operator==(NonConstComparableLValue&, NonConstComparableLValue&) { return false; } + friend constexpr bool operator==(const NonConstComparableLValue&, NonConstComparableLValue&) { return false; } + friend constexpr bool operator==(NonConstComparableLValue&, const NonConstComparableLValue&) { return true; } +}; + +constexpr bool test() { + test_iterators(); + test_iterators(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + + { // check that projections are used properly and that they are called with the iterator directly + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_if_not(a, a + 4, [&](int* i) { return i != a + 3; }, [](int& i) { return &i; }); + assert(ret == a + 3); + } + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_if_not(a, [&](int* i) { return i != a + 3; }, [](int& i) { return &i; }); + assert(ret == a + 3); + } + } + + { + // check that the first element is returned + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::find_if_not(a, [](int i){ return i != 0; }, &S::comp); + assert(ret == a); + assert(ret->comp == 0); + assert(ret->other == 0); + } + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::find_if_not(a, a + 3, [](int i) { return i != 0; }, &S::comp); + assert(ret == a); + assert(ret->comp == 0); + assert(ret->other == 0); + } + } + + { + // check that end + 1 iterator is returned with no match + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find_if(a, a + 3, [](int) { return false; }); + assert(ret == a + 3); + } + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find_if(a, [](int){ return false; }); + assert(ret == a + 3); + } + } + + { // check that ranges::dangling is returned + [[maybe_unused]] std::same_as auto ret = + std::ranges::find_if_not(std::array{1, 2}, [](int){ return true; }); + } + + { // check that an iterator is returned with a borrowing range + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find_if_not(std::views::all(a), [](int){ return false; }); + assert(ret == a); + assert(*ret == 1); + } + + { // check that std::invoke is used + struct S { int i; }; + S a[] = { S{1}, S{3}, S{2} }; + std::same_as auto ret = std::ranges::find_if_not(a, [](int) { return true; }, &S::i); + assert(ret == a + 3); + } + + { // count projection and predicate invocation count + { + int a[] = {1, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::find_if_not(a, a + 4, + [&](int i) { ++predicate_count; return i != 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(predicate_count == 2); + assert(projection_count == 2); + } + { + int a[] = {1, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::find_if_not(a, + [&](int i) { ++predicate_count; return i != 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(predicate_count == 2); + assert(projection_count == 2); + } + } + + { // check that the return type of `iter::operator*` doesn't change + { + NonConstComparableLValue a[] = { NonConstComparableLValue{} }; + auto ret = std::ranges::find_if_not(a, a + 1, [](auto&& e) { return e != NonConstComparableLValue{}; }); + assert(ret == a); + } + { + NonConstComparableLValue a[] = { NonConstComparableLValue{} }; + auto ret = std::ranges::find_if_not(a, [](auto&& e) { return e != NonConstComparableLValue{}; }); + assert(ret == a); + } + } + + { + // check that an empty range works + { + std::array a = {}; + auto ret = std::ranges::find_if_not(a.begin(), a.end(), [](int) { return true; }); + assert(ret == a.begin()); + } + { + std::array a = {}; + auto ret = std::ranges::find_if_not(a, [](int) { return true; }); + assert(ret == a.begin()); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -54,7 +54,7 @@ int *p; int a[10]; -//auto odd = [](int x) { return x % 2 != 0; }; +auto odd = [](int x) { return x % 2 != 0; }; //auto triple = [](int x) { return 3*x; }; //auto plus = [](int x, int y) { return x == y; }; //std::mt19937 g; @@ -77,11 +77,11 @@ //static_assert(test(std::ranges::equal_range, a, 42)); //static_assert(test(std::ranges::fill, a, 42)); //static_assert(test(std::ranges::fill_n, a, 10, 42)); -//static_assert(test(std::ranges::find, a, 42)); +static_assert(test(std::ranges::find, a, 42)); //static_assert(test(std::ranges::find_end, a, a)); //static_assert(test(std::ranges::find_first_of, a, a)); -//static_assert(test(std::ranges::find_if, a, odd)); -//static_assert(test(std::ranges::find_if_not, a, odd)); +static_assert(test(std::ranges::find_if, a, odd)); +static_assert(test(std::ranges::find_if_not, a, odd)); //static_assert(test(std::ranges::for_each, a, odd)); //static_assert(test(std::ranges::for_each_n, a, 10, odd)); //static_assert(test(std::ranges::generate, a, 42)); diff --git a/libcxx/test/support/almost_satisfies_types.h b/libcxx/test/support/almost_satisfies_types.h new file mode 100644 --- /dev/null +++ b/libcxx/test/support/almost_satisfies_types.h @@ -0,0 +1,131 @@ +//===----------------------------------------------------------------------===// +// +// 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 ALMOST_SATISFIES_TYPES_H +#define ALMOST_SATISFIES_TYPES_H + +#include +#include + +#include "test_iterators.h" + +template > +class UncheckedRange { +public: + T begin(); + U end(); +}; + +static_assert(std::ranges::contiguous_range>); + +// almost an input_iterator +class InputIteratorNotDerivedFrom { +public: + using difference_type = long; + using value_type = int; + using iterator_category = void; + + InputIteratorNotDerivedFrom& operator++(); + void operator++(int); + const int& operator*() const; +}; + +using InputRangeNotDerivedFrom = UncheckedRange; + +static_assert(std::input_or_output_iterator); +static_assert(std::indirectly_readable); +static_assert(!std::input_iterator); +static_assert(!std::ranges::input_range); + +class InputIteratorNotIndirectlyReadable { +public: + using difference_type = long; + using iterator_category = std::input_iterator_tag; + + InputIteratorNotIndirectlyReadable& operator++(); + void operator++(int); + const int& operator*() const; +}; + +using InputRangeNotIndirectlyReadable = UncheckedRange; + +static_assert(std::input_or_output_iterator); +static_assert(!std::indirectly_readable); +static_assert(!std::input_iterator); +static_assert(!std::ranges::input_range); + +class InputIteratorNotInputOrOutputIterator { +public: + using difference_type = long; + using value_type = int; + using iterator_category = std::input_iterator_tag; + + int& operator++(); + void operator++(int); + const int& operator*() const; +}; + +using InputRangeNotInputOrOutputIterator = UncheckedRange; + +static_assert(!std::input_or_output_iterator); +static_assert(std::indirectly_readable); +static_assert(!std::input_iterator); +static_assert(!std::ranges::input_range); + +// almost an indirect_unary_predicate +class IndirectUnaryPredicateNotCopyConstructible { +public: + IndirectUnaryPredicateNotCopyConstructible(const IndirectUnaryPredicateNotCopyConstructible&) = delete; + bool operator()(int) const; +}; + +static_assert(std::predicate); +static_assert(!std::indirect_unary_predicate); + +class IndirectUnaryPredicateNotPredicate { +public: + bool operator()(int&&) const; +}; + +static_assert(!std::predicate); +static_assert(!std::indirect_unary_predicate); + +// almost a sentinel_for cpp20_input_iterator +class SentinelForNotSemiregular { +public: + SentinelForNotSemiregular() = delete; + using difference_type = long; + SentinelForNotSemiregular& operator++(); + void operator++(int); + const int& operator*() const; + friend bool operator==(const SentinelForNotSemiregular&, const cpp20_input_iterator&); +}; + +using InputRangeNotSentinelSemiregular = UncheckedRange, SentinelForNotSemiregular>; + +static_assert(std::input_or_output_iterator); +static_assert(!std::semiregular); +static_assert(!std::sentinel_for>); + +// almost a sentinel_for cpp20_input_iterator +class SentinelForNotWeaklyEqualityComparableWith { +public: + using difference_type = long; + SentinelForNotWeaklyEqualityComparableWith& operator++(); + void operator++(int); + const int& operator*() const; +}; + +using InputRangeNotSentinelEqualityComparableWith = + UncheckedRange, SentinelForNotWeaklyEqualityComparableWith>; + +static_assert(std::input_or_output_iterator); +static_assert(std::semiregular); +static_assert(!std::sentinel_for>); + +#endif // ALMOST_SATISFIES_TYPES_H