diff --git a/libcxx/docs/FeatureTestMacroTable.rst b/libcxx/docs/FeatureTestMacroTable.rst --- a/libcxx/docs/FeatureTestMacroTable.rst +++ b/libcxx/docs/FeatureTestMacroTable.rst @@ -98,6 +98,8 @@ ------------------------------------------------- ----------------- ``__cpp_lib_filesystem`` ``201703L`` ------------------------------------------------- ----------------- + ``__cpp_lib_find_last`` ``202207L`` + ------------------------------------------------- ----------------- ``__cpp_lib_gcd_lcm`` ``201606L`` ------------------------------------------------- ----------------- ``__cpp_lib_hardware_interference_size`` ``201703L`` diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst --- a/libcxx/docs/ReleaseNotes.rst +++ b/libcxx/docs/ReleaseNotes.rst @@ -39,6 +39,7 @@ ------------------ - P2520R0 - ``move_iterator`` should be a random access iterator - P1328R1 - ``constexpr type_info::operator==()`` +- P1223R5 - ``find_last`` Improvements and New Features ----------------------------- diff --git a/libcxx/docs/Status/Cxx2bPapers.csv b/libcxx/docs/Status/Cxx2bPapers.csv --- a/libcxx/docs/Status/Cxx2bPapers.csv +++ b/libcxx/docs/Status/Cxx2bPapers.csv @@ -55,7 +55,7 @@ "`P0429R9 `__","LWG","A Standard ``flat_map``","July 2022","","" "`P1169R4 `__","LWG","``static operator()``","July 2022","|Complete|","16.0" "`P1222R4 `__","LWG","A Standard ``flat_set``","July 2022","","" -"`P1223R5 `__","LWG","``ranges::find_last()``, ``ranges::find_last_if()``, and ``ranges::find_last_if_not()``","July 2022","","","|ranges|" +"`P1223R5 `__","LWG","``ranges::find_last()``, ``ranges::find_last_if()``, and ``ranges::find_last_if_not()``","July 2022","|Complete|","","|ranges|" "`P1467R9 `__","LWG","Extended ``floating-point`` types and standard names","July 2022","","" "`P1642R11 `__","LWG","Freestanding ``[utilities]``, ``[ranges]``, and ``[iterators]``","July 2022","","" "`P1899R3 `__","LWG","``stride_view``","July 2022","","","|ranges|" diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -90,6 +90,9 @@ __algorithm/ranges_find_first_of.h __algorithm/ranges_find_if.h __algorithm/ranges_find_if_not.h + __algorithm/ranges_find_last.h + __algorithm/ranges_find_last_if.h + __algorithm/ranges_find_last_if_not.h __algorithm/ranges_for_each.h __algorithm/ranges_for_each_n.h __algorithm/ranges_generate.h diff --git a/libcxx/include/__algorithm/ranges_find_last.h b/libcxx/include/__algorithm/ranges_find_last.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_last.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_LAST_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H + +#include <__algorithm/ranges_find_last_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 >= 23 + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __find_last { +struct __fn { + template _Sp, class _Tp, class _Proj = identity> + requires indirect_binary_predicate, const _Tp*> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Ip> operator()(_Ip __first, _Sp __last, const _Tp& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __e) { return std::forward(__e) == __value; }; + return ranges::__find_last_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template + requires indirect_binary_predicate, _Proj>, const _Tp*> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __e) { return std::forward(__e) == __value; }; + return ranges::__find_last_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } +}; +} // namespace __find_last + +inline namespace __cpo { + inline constexpr auto find_last = __find_last::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 23 + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H \ No newline at end of file diff --git a/libcxx/include/__algorithm/ranges_find_last_if.h b/libcxx/include/__algorithm/ranges_find_last_if.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_last_if.h @@ -0,0 +1,77 @@ +//===----------------------------------------------------------------------===// +// +// 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_LAST_IF_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_LAST_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 <__ranges/range_adaptor.h> +#include <__ranges/subrange.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER >= 23 + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template +_LIBCPP_HIDE_FROM_ABI static constexpr +subrange<_Ip> __find_last_if_impl(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj) { + auto __prev = __last; + while (__first != __last) { + auto __tmp = std::prev(__last); + if (std::invoke(__pred, std::invoke(__proj, *__tmp))) { + __prev = __tmp; + break; + } + __last = __tmp; + } + return { __prev, __last }; +} + +namespace __find_last_if { +struct __fn { + template , _Proj>> _Pred> + _LIBCPP_NODISCARD_EXT constexpr + borrowed_subrange_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + return ranges::__find_last_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } + template _Sp, class _Proj = identity, + indirect_unary_predicate> _Pred> + _LIBCPP_NODISCARD_EXT constexpr + subrange<_Ip> operator()(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj = {}) const { + return ranges::__find_last_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } +}; +} // namespace __find_last_if + +inline namespace __cpo { + inline constexpr auto find_last_if = __find_last_if::__fn{}; +} // namespace __cpo +} // namespace ranges + + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 23 + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_LAST_IF_H \ No newline at end of file diff --git a/libcxx/include/__algorithm/ranges_find_last_if_not.h b/libcxx/include/__algorithm/ranges_find_last_if_not.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_last_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_LAST_IF_NOT_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_LAST_IF_NOT_H + +#include <__algorithm/ranges_find_last_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 >= 23 + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __find_last_if_not { +struct __fn { + template _Sp, class _Proj = identity, + indirect_unary_predicate> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_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_last_if_impl(std::move(__first), std::move(__last), __pred2, __proj); + } + + template , _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + auto __pred2 = [&](auto&& __e) { return !std::invoke(__pred, std::forward(__e)); }; + return ranges::__find_last_if_impl(ranges::begin(__r), ranges::end(__r), __pred2, __proj); + } +}; +} // namespace __find_last_if_not + +inline namespace __cpo { + inline constexpr auto find_last_if_not = __find_last_if_not::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 23 + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_LAST_IF_NOT_H \ No newline at end of file diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -99,6 +99,33 @@ constexpr borrowed_iterator_t find_if_not(R&& r, Pred pred, Proj proj = {}); // since C++20 + template S, class T, class Proj = identity> + requires indirect_binary_predicate, const T*> + constexpr subrange ranges::find_last(I first, S last, const T& value, Proj proj = {}); // since C++23 + + template + requires indirect_binary_predicate, Proj>, const T*> + constexpr borrowed_subrange_t + ranges::find_last(R&& r, const T& value, Proj proj = {}); //since C++23 + + template S, class Proj = identity, + indirect_unary_predicate> Pred> + constexpr subrange ranges::find_last_if(I first, S last, Pred pred, Proj proj = {}); // since C++23 + + template, Proj>> Pred> + constexpr borrowed_subrange_t + ranges::find_last_if(R&& r, Pred pred, Proj proj = {}); // since C++23 + + template S, class Proj = identity, + indirect_unary_predicate> Pred> + constexpr subrange ranges::find_last_if_not(I first, S last, Pred pred, Proj proj = {}); // since C++23 + + template, Proj>> Pred> + constexpr borrowed_subrange_t + ranges::find_last_if_not(R&& r, Pred pred, Proj proj = {}); // since C++23 + template> Comp = ranges::less> constexpr const T& min(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20 @@ -1809,6 +1836,9 @@ #include <__algorithm/ranges_find_first_of.h> #include <__algorithm/ranges_find_if.h> #include <__algorithm/ranges_find_if_not.h> +#include <__algorithm/ranges_find_last.h> +#include <__algorithm/ranges_find_last_if.h> +#include <__algorithm/ranges_find_last_if_not.h> #include <__algorithm/ranges_for_each.h> #include <__algorithm/ranges_for_each_n.h> #include <__algorithm/ranges_generate.h> diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -362,6 +362,9 @@ module ranges_find_first_of { private header "__algorithm/ranges_find_first_of.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_find_last { private header "__algorithm/ranges_find_last.h" } + module ranges_find_last_if { private header "__algorithm/ranges_find_last_if.h" } + module ranges_find_last_if_not { private header "__algorithm/ranges_find_last_if_not.h" } module ranges_for_each { private header "__algorithm/ranges_for_each.h" export algorithm.__algorithm.in_fun_result diff --git a/libcxx/include/version b/libcxx/include/version --- a/libcxx/include/version +++ b/libcxx/include/version @@ -84,6 +84,7 @@ 201603L // C++17 __cpp_lib_expected 202202L __cpp_lib_filesystem 201703L +__cpp_lib_find_last 202207L __cpp_lib_format 202106L __cpp_lib_forward_like 202207L __cpp_lib_gcd_lcm 201606L @@ -341,6 +342,7 @@ # if !defined(_LIBCPP_AVAILABILITY_DISABLE_FTM___cpp_lib_format) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_FORMAT) // # define __cpp_lib_format 202106L # endif +# define __cpp_lib_find_last 202207L # define __cpp_lib_generic_unordered_lookup 201811L # define __cpp_lib_int_pow2 202002L # define __cpp_lib_integer_comparison_functions 202002L diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -127,6 +127,9 @@ #include <__algorithm/ranges_find_first_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_first_of.h'}} #include <__algorithm/ranges_find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if.h'}} #include <__algorithm/ranges_find_if_not.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if_not.h'}} +#include <__algorithm/ranges_find_last.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_last.h'}} +#include <__algorithm/ranges_find_last_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_last_if.h'}} +#include <__algorithm/ranges_find_last_if_not.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_last_if_not.h'}} #include <__algorithm/ranges_for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each.h'}} #include <__algorithm/ranges_for_each_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each_n.h'}} #include <__algorithm/ranges_generate.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_generate.h'}} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last.pass.cpp @@ -0,0 +1,248 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++20 + +// template S, class T, class Proj = identity> +// requires indirect_binary_predicate, const T*> +// constexpr subrange ranges::find_last(I first, S last, const T& value, Proj proj = {}); +// template +// requires indirect_binary_predicate, Proj>, const T*> +// constexpr borrowed_subrange_t +// ranges::find_last(R&& r, const T& value, Proj proj = {}); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +struct NotEqualityComparable {}; + +template +concept HasFindIt = requires(It it, Sent sent) { std::ranges::find_last(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_last(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); + +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() { + + { + // 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_last(a, a + 4, a + 3, [](int& i) { return &i; }); + assert(ret.data() == a + 3); + } + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_last(a, a + 3, [](int& i) { return &i; }); + assert(ret.data() == a + 3); + } + } + + { // check that the end element is returned + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::find_last(a, 0, &S::comp); + assert(ret.data() == a + 2); + assert(ret.data()->comp == 0); + assert(ret.data()->other == 1); + } + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::find_last(a, a + 3, 0, &S::comp); + assert(ret.data() == a + 2); + assert(ret.data()->comp == 0); + assert(ret.data()->other == 1); + } + } + + { // check that end + 1 iterator is returned with no match + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find_last(a, a + 3, 0); + assert(ret.data() == a + 3); + } + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find_last(a, 0); + assert(ret.data() == a + 3); + } + } + + { + // check that ranges::dangling is returned + [[maybe_unused]] std::same_as auto ret = + std::ranges::find_last(std::array{1, 2}, 3); + } + + { + // check that an iterator is returned with a borrowing range + int a[] = {1, 1, 2, 3, 4}; + auto ret = std::ranges::find_last(std::views::all(a), 1); + assert(ret.data() == a + 1); + assert(*(ret.data()) == 1); + } + + { + // check that std::invoke is used + struct S { int i; }; + S a[] = { S{1}, S{3}, S{2} }; + auto ret = std::ranges::find_last(a, 4, &S::i); + assert(ret.data() == a + 3); + } + + { + // count invocations of the projection + { + int a[] = {1, 2, 2, 3, 4}; + int projection_count = 0; + auto ret = std::ranges::find_last(a, a + 5, 2, [&](int i) { ++projection_count; return i; }); + assert(ret.data() == a + 2); + assert(*(ret.data()) == 2); + assert(projection_count == 3); + } + { + int a[] = {1, 2, 2, 3, 4}; + int projection_count = 0; + auto ret = std::ranges::find_last(a, 2, [&](int i) { ++projection_count; return i; }); + assert(ret.data() == a + 2); + assert(*(ret.data()) == 2); + assert(projection_count == 3); + } + } + + { + // check comparison order + { + OneWayComparable a[] = { OneWayComparable{true} }; + auto ret = std::ranges::find_last(a, a + 1, OneWayComparable{false}); + assert(ret.data() == a); + } + { + OneWayComparable a[] = { OneWayComparable{true} }; + auto ret = std::ranges::find_last(a, OneWayComparable{false}); + assert(ret.data() == a); + } + } + + { + // check that the return type of `iter::operator*` doesn't change + { + NonConstComparableLValue a[] = { NonConstComparableLValue{} }; + auto ret = std::ranges::find_last(a, a + 1, NonConstComparableLValue{}); + assert(ret.data() == a); + } + { + using It = std::move_iterator; + NonConstComparableRValue a[] = { NonConstComparableRValue{} }; + auto ret = std::ranges::find_last(It(a), It(a + 1), NonConstComparableRValue{}); + assert(ret.begin().base() == a); + } + { + NonConstComparableLValue a[] = { NonConstComparableLValue{} }; + auto ret = std::ranges::find_last(a, NonConstComparableLValue{}); + assert(ret.data() == a); + } + { + using It = std::move_iterator; + NonConstComparableRValue a[] = { NonConstComparableRValue{} }; + auto range = std::ranges::subrange(It(a), It(a + 1)); + auto ret = std::ranges::find_last(range, NonConstComparableRValue{}); + assert(ret.begin().base() == a); + } + } + + { + // check that an empty range works + { + std::array a = {}; + auto ret = std::ranges::find_last(a.begin(), a.end(), 1); + assert(ret.data() == a.begin()); + } + { + std::array a = {}; + auto ret = std::ranges::find_last(a, 1); + assert(ret.data() == a.begin()); + } + } + + { + // check that the implicit conversion to bool works + { + StrictComparable a[] = {1, 2, 2, 3, 4}; + auto ret = std::ranges::find_last(a, a + 4, StrictComparable{2}); + assert(ret.data() == a + 2); + } + { + StrictComparable a[] = {1, 2, 2, 3, 4}; + auto ret = std::ranges::find_last(a, StrictComparable{2}); + assert(ret.data() == a + 2); + } + } + + return true; +} + +int main(int, char**) { + test(); + assert(test()); + + return 0; +} \ No newline at end of file diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last_if.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last_if.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last_if.pass.cpp @@ -0,0 +1,233 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++20 + +// template S, class Proj = identity, +// indirect_unary_predicate> Pred> +// constexpr subrange ranges::find_last_if(I first, S last, Pred pred, Proj proj = {}); +// template, Proj>> Pred> +// constexpr borrowed_subrange_t +// ranges::find_last_if(R&& r, Pred pred, Proj proj = {}); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +struct Predicate { + bool operator()(int); +}; + +template +concept HasFindIfIt = requires(It it, Sent sent) { + std::ranges::find_last_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_last_if(it, it, pred); +}; + +static_assert(!HasFindIfPred); +static_assert(!HasFindIfPred); + +template +concept HasFindIfR = requires(R r) { + std::ranges::find_last_if(r, Predicate{}); +}; +static_assert(HasFindIfR>); +static_assert(!HasFindIfR); +static_assert(!HasFindIfR); +static_assert(!HasFindIfR); +static_assert(!HasFindIfR); +static_assert(!HasFindIfR); +static_assert(!HasFindIfR); + +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() { + + { + // 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_last_if( + a, a + 4, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }); + assert(ret.data() == a + 3); + } + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_last_if( + a, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }); + assert(ret.data() == a + 3); + } + } + + { + // check that the last element is returned + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::find_last_if(a, [](int i) { return i == 0; }, &S::comp); + assert(ret.data() == a + 2); + assert(ret.data()->comp == 0); + assert(ret.data()->other == 1); + } + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::find_last_if( + a, a + 3, [](int i) { return i == 0; }, &S::comp); + assert(ret.data() == a + 2); + assert(ret.data()->comp == 0); + assert(ret.data()->other == 1); + } + } + + { + // check that end + 1 iterator is returned with no match + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find_last_if(a, a + 3, [](int) { return false; }); + assert(ret.data() == a + 3); + } + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find_last_if(a, [](int) { return false; }); + assert(ret.data() == a + 3); + } + } + + { + // check that ranges::dangling is returned + [[maybe_unused]] std::same_as auto ret = + std::ranges::find_last_if(std::array{1, 2}, [](int) { return false; }); + } + + { + // check that an iterator is returned with a borrowing range + int a[] = {1, 1, 2, 3, 4}; + auto ret = std::ranges::find_last_if(std::views::all(a), [](int) { return true; }); + assert(ret.data() == a + 4); + } + + { + // check that std::invoke is used + struct S { int i; }; + S a[] = {S{1}, S{3}, S{2}}; + auto ret = std::ranges::find_last_if(a, [](int) { return false; }, &S::i); + assert(ret.data() == a + 3); + } + + { + // count projection and predicate invocation count + { + int a[] = {1, 2, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::find_last_if(a, a + 5, + [&](int i) { ++predicate_count; return i == 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret.data() == a + 2); + assert(*(ret.data()) == 2); + assert(predicate_count == 3); + assert(projection_count == 3); + } + { + int a[] = {1, 2, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::find_last_if(a, + [&](int i) { ++predicate_count; return i == 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret.data() == a + 2); + assert(*(ret.data()) == 2); + assert(predicate_count == 3); + assert(projection_count == 3); + } + } + + { + // check that the return type of `iter::operator*` doesn't change + { + NonConstComparable a[] = {NonConstComparable{}}; + auto ret = std::ranges::find_last_if(a, a + 1, [](auto&& e) { return e == NonConstComparable{}; }); + assert(ret.data() == a); + } + { + NonConstComparable a[] = {NonConstComparable{}}; + auto ret = std::ranges::find_last_if(a, [](auto&& e) { return e == NonConstComparable{}; }); + assert(ret.data() == a); + } + } + + { + // check that an empty range works + { + std::array a = {}; + auto ret = std::ranges::find_last_if(a.begin(), a.end(), [](int) { return true; }); + assert(ret.data() == a.begin()); + } + { + std::array a = {}; + auto ret = std::ranges::find_last_if(a, [](int) { return true; }); + assert(ret.data() == a.begin()); + } + } + + { + // check that the implicit conversion to bool works + { + int a[] = {1, 2, 3, 3, 4}; + auto ret = std::ranges::find_last_if(a, a + 4, [](const int& i) { return BooleanTestable{i == 3}; }); + assert(ret.data() == a + 3); + } + { + int a[] = {1, 2, 3, 3, 4}; + auto ret = std::ranges::find_last_if(a, [](const int& b) { return BooleanTestable{b == 3}; }); + assert(ret.data() == a + 3); + } + } + + return true; +} + +int main(int, char**) { + test(); + assert(test()); + + return 0; +} \ No newline at end of file diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last_if_not.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last_if_not.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last_if_not.pass.cpp @@ -0,0 +1,219 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++20 + +// template S, class Proj = identity, +// indirect_unary_predicate> Pred> +// constexpr subrange ranges::find_last_if_not(I first, S last, Pred pred, Proj proj = {}); +// template, Proj>> Pred> +// constexpr borrowed_subrange_t +// ranges::find_last_if_not(R&& r, Pred pred, Proj proj = {}); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.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); + +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() { + + { // check that projections are used properly and that they are called with the iterator directly + { + int a[] = {1, 2, 3, 4, 5}; + auto ret = std::ranges::find_last_if_not(a, a + 5, [&](int* i) { return i != a + 3; }, [](int& i) { return &i; }); + assert(ret.data() == a + 3); + } + { + int a[] = {1, 2, 3, 4, 5}; + auto ret = std::ranges::find_last_if_not(a, [&](int* i) { return i != a + 3; }, [](int& i) { return &i; }); + assert(ret.data() == 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_last_if_not(a, [](int i){ return i != 0; }, &S::comp); + assert(ret.data() == a + 2); + assert(ret.data()->comp == 0); + assert(ret.data()->other == 1); + } + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::find_last_if_not(a, a + 3, [](int i) { return i != 0; }, &S::comp); + assert(ret.data() == a + 2); + assert(ret.data()->comp == 0); + assert(ret.data()->other == 1); + } + } + + { + // check that end iterator is returned with no match + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find_last_if_not(a, a + 3, [](int) { return false; }); + assert(ret.data() == a + 2); + } + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::find_last_if_not(a, [](int){ return false; }); + assert(ret.data() == a + 2); + } + } + + { // check that ranges::dangling is returned + [[maybe_unused]] std::same_as auto ret = + std::ranges::find_last_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}; + auto ret = std::ranges::find_last_if_not(std::views::all(a), [](int){ return false; }); + assert(ret.data() == a + 3); + assert(*ret.data() == 4); + } + + { // check that std::invoke is used + struct S { int i; }; + S a[] = { S{1}, S{3}, S{2} }; + auto ret = std::ranges::find_last_if_not(a, [](int) { return true; }, &S::i); + assert(ret.data() == 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_last_if_not(a, a + 4, + [&](int i) { ++predicate_count; return i != 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret.data() == a + 1); + assert(*ret.data() == 2); + assert(predicate_count == 3); + assert(projection_count == 3); + } + { + int a[] = {1, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::find_last_if_not(a, + [&](int i) { ++predicate_count; return i != 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret.data() == a + 1); + assert(*ret.data() == 2); + assert(predicate_count == 3); + assert(projection_count == 3); + } + } + + { // check that the return type of `iter::operator*` doesn't change + { + NonConstComparableLValue a[] = { NonConstComparableLValue{} }; + auto ret = std::ranges::find_last_if_not(a, a + 1, [](auto&& e) { return e != NonConstComparableLValue{}; }); + assert(ret.data() == a); + } + { + NonConstComparableLValue a[] = { NonConstComparableLValue{} }; + auto ret = std::ranges::find_last_if_not(a, [](auto&& e) { return e != NonConstComparableLValue{}; }); + assert(ret.data() == a); + } + } + + { + // check that an empty range works + { + std::array a = {}; + auto ret = std::ranges::find_last_if_not(a.begin(), a.end(), [](int) { return true; }); + assert(ret.data() == a.begin()); + } + { + std::array a = {}; + auto ret = std::ranges::find_last_if_not(a, [](int) { return true; }); + assert(ret.data() == a.begin()); + } + } + + { + // check that the implicit conversion to bool works + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_last_if_not(a, a + 4, [](const int& i) { return BooleanTestable{i != 3}; }); + assert(ret.data() == a + 2); + } + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_last_if_not(a, [](const int& b) { return BooleanTestable{b != 3}; }); + assert(ret.data() == a + 2); + } + } + + return true; +} + +int main(int, char**) { + test(); + assert(test()); + + return 0; +} diff --git a/llvm/utils/gn/secondary/libcxx/include/BUILD.gn b/llvm/utils/gn/secondary/libcxx/include/BUILD.gn --- a/llvm/utils/gn/secondary/libcxx/include/BUILD.gn +++ b/llvm/utils/gn/secondary/libcxx/include/BUILD.gn @@ -165,6 +165,9 @@ "__algorithm/ranges_find_first_of.h", "__algorithm/ranges_find_if.h", "__algorithm/ranges_find_if_not.h", + "__algorithm/ranges_find_last.h", + "__algorithm/ranges_find_last_if.h", + "__algorithm/ranges_find_last_if_not.h", "__algorithm/ranges_for_each.h", "__algorithm/ranges_for_each_n.h", "__algorithm/ranges_generate.h",