diff --git a/libcxx/docs/FeatureTestMacroTable.rst b/libcxx/docs/FeatureTestMacroTable.rst --- a/libcxx/docs/FeatureTestMacroTable.rst +++ b/libcxx/docs/FeatureTestMacroTable.rst @@ -322,6 +322,8 @@ ------------------------------------------------- ----------------- ``__cpp_lib_expected`` ``202202L`` ------------------------------------------------- ----------------- + ``__cpp_lib_find_last`` ``202207L`` + ------------------------------------------------- ----------------- ``__cpp_lib_format_ranges`` ``202207L`` ------------------------------------------------- ----------------- ``__cpp_lib_formatters`` *unimplemented* diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst --- a/libcxx/docs/ReleaseNotes.rst +++ b/libcxx/docs/ReleaseNotes.rst @@ -41,6 +41,7 @@ - P1328R1 - ``constexpr type_info::operator==()`` - P1413R3 - Formatting ``thread::id`` (the ``stacktrace`` is not done yet) - P2675R1 - ``format``'s width estimation is too approximate and not forward compatible +- 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|","17.0","|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 < ranges::equal_to, projected<_Ip, _Proj>, + 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 < ranges::equal_to, projected, _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,78 @@ +//===----------------------------------------------------------------------===// +// +// 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) { + _Ip __current = __first; + subrange<_Ip> __result{__last, __last}; + while (__current != __last) { + if (std::invoke(__pred, std::invoke(__proj, *__current))) { + __result = {__current, __last}; + } + ++__current; + } + return __result; +} + +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,66 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#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 __not_pred = [&](auto&& __e) { return !std::invoke(__pred, std::forward(__e)); }; + return ranges::__find_last_if_impl(std::move(__first), std::move(__last), __not_pred, __proj); + } + + template , _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr borrowed_subrange_t<_Rp> + operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + auto __not_pred = [&](auto&& __e) { return !std::invoke(__pred, std::forward(__e)); }; + return ranges::__find_last_if_impl(ranges::begin(__r), ranges::end(__r), __not_pred, __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,35 @@ 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 +1838,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_format_ranges 202207L __cpp_lib_formatters 202302L @@ -399,6 +400,7 @@ # define __cpp_lib_constexpr_memory 202202L # define __cpp_lib_constexpr_typeinfo 202106L # define __cpp_lib_expected 202202L +# define __cpp_lib_find_last 202207L # if !defined(_LIBCPP_HAS_NO_INCOMPLETE_FORMAT) # define __cpp_lib_format_ranges 202207L # endif 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 @@ -135,6 +135,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,249 @@ +//===----------------------------------------------------------------------===// +// +// 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 == 5); + } + { + 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 == 5); + } + } + + { // 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 = {}; + constexpr int search_value = 1; + auto ret = std::ranges::find_last(a.begin(), a.end(), search_value); + assert(ret.data() == a.end()); + } + { + std::array a = {}; + constexpr int search_value = 1; + auto ret = std::ranges::find_last(a, search_value); + assert(ret.data() == a.end()); + } + } + + { + // 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(); + static_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,256 @@ +//===----------------------------------------------------------------------===// +// +// 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); + +template +constexpr void test_iterators() { + { + int a[] = {1, 2, 3, 4}; + std::same_as> auto ret = + std::ranges::find_last_if(It(a), Sent(It(a + 4)), [](int x) mutable { return x == 4; }); + assert(base(ret.begin()) == a + 3); + assert(*ret.begin() == 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_last_if(range, [](int x) mutable { return x == 4; }); + assert(base(ret.begin()) == a + 3); + assert(*ret.begin() == 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>(); + 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_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 == 5); + assert(projection_count == 5); + } + { + 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 == 5); + assert(projection_count == 5); + } + } + + { // 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(); + static_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,255 @@ +//===----------------------------------------------------------------------===// +// +// 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_last_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_last_if_not(it, it, pred); +}; + +static_assert(!HasFindIfNotPred); +static_assert(!HasFindIfNotPred); + +template +concept HasFindIfNotR = requires(R r) { + std::ranges::find_last_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, 5}; + std::same_as> auto ret = + std::ranges::find_last_if_not(It(a), Sent(It(a + 5)), [c = 0](int) mutable { return c++ <= 2; }); + assert(base(ret.begin()) == a + 4); + assert(*ret.begin() == 5); + } + { + int a[] = {1, 2, 3, 4, 5}; + auto range = std::ranges::subrange(It(a), Sent(It(a + 5))); + std::same_as> auto ret = + std::ranges::find_last_if_not(range, [c = 0](int) mutable { return c++ <= 2; }); + assert(base(ret.begin()) == a + 4); + assert(*ret.begin() == 5); + } +} + +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>(); + 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, 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 == 4); + assert(projection_count == 4); + } + { + 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 == 4); + assert(projection_count == 4); + } + } + + { // 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(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.compile.pass.cpp b/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.compile.pass.cpp --- a/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.compile.pass.cpp +++ b/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.compile.pass.cpp @@ -18,6 +18,7 @@ /* Constant Value __cpp_lib_clamp 201603L [C++17] __cpp_lib_constexpr_algorithms 201806L [C++20] + __cpp_lib_find_last 202207L [C++2b] __cpp_lib_parallel_algorithm 201603L [C++17] __cpp_lib_ranges 202106L [C++20] __cpp_lib_ranges_starts_ends_with 202106L [C++2b] @@ -39,6 +40,10 @@ # error "__cpp_lib_constexpr_algorithms should not be defined before c++20" # endif +# ifdef __cpp_lib_find_last +# error "__cpp_lib_find_last should not be defined before c++2b" +# endif + # ifdef __cpp_lib_parallel_algorithm # error "__cpp_lib_parallel_algorithm should not be defined before c++17" # endif @@ -73,6 +78,10 @@ # error "__cpp_lib_constexpr_algorithms should not be defined before c++20" # endif +# ifdef __cpp_lib_find_last +# error "__cpp_lib_find_last should not be defined before c++2b" +# endif + # ifdef __cpp_lib_parallel_algorithm # error "__cpp_lib_parallel_algorithm should not be defined before c++17" # endif @@ -113,6 +122,10 @@ # error "__cpp_lib_constexpr_algorithms should not be defined before c++20" # endif +# ifdef __cpp_lib_find_last +# error "__cpp_lib_find_last should not be defined before c++2b" +# endif + # if !defined(_LIBCPP_VERSION) # ifndef __cpp_lib_parallel_algorithm # error "__cpp_lib_parallel_algorithm should be defined in c++17" @@ -168,6 +181,10 @@ # error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++20" # endif +# ifdef __cpp_lib_find_last +# error "__cpp_lib_find_last should not be defined before c++2b" +# endif + # if !defined(_LIBCPP_VERSION) # ifndef __cpp_lib_parallel_algorithm # error "__cpp_lib_parallel_algorithm should be defined in c++20" @@ -229,6 +246,13 @@ # error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++2b" # endif +# ifndef __cpp_lib_find_last +# error "__cpp_lib_find_last should be defined in c++2b" +# endif +# if __cpp_lib_find_last != 202207L +# error "__cpp_lib_find_last should have the value 202207L in c++2b" +# endif + # if !defined(_LIBCPP_VERSION) # ifndef __cpp_lib_parallel_algorithm # error "__cpp_lib_parallel_algorithm should be defined in c++2b" diff --git a/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.compile.pass.cpp b/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.compile.pass.cpp --- a/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.compile.pass.cpp +++ b/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.compile.pass.cpp @@ -78,6 +78,7 @@ 201902L [C++20] __cpp_lib_expected 202202L [C++2b] __cpp_lib_filesystem 201703L [C++17] + __cpp_lib_find_last 202207L [C++2b] __cpp_lib_format 202106L [C++20] __cpp_lib_format_ranges 202207L [C++2b] __cpp_lib_formatters 202302L [C++2b] @@ -429,6 +430,10 @@ # error "__cpp_lib_filesystem should not be defined before c++17" # endif +# ifdef __cpp_lib_find_last +# error "__cpp_lib_find_last should not be defined before c++2b" +# endif + # ifdef __cpp_lib_format # error "__cpp_lib_format should not be defined before c++20" # endif @@ -1092,6 +1097,10 @@ # error "__cpp_lib_filesystem should not be defined before c++17" # endif +# ifdef __cpp_lib_find_last +# error "__cpp_lib_find_last should not be defined before c++2b" +# endif + # ifdef __cpp_lib_format # error "__cpp_lib_format should not be defined before c++20" # endif @@ -1869,6 +1878,10 @@ # endif # endif +# ifdef __cpp_lib_find_last +# error "__cpp_lib_find_last should not be defined before c++2b" +# endif + # ifdef __cpp_lib_format # error "__cpp_lib_format should not be defined before c++20" # endif @@ -2916,6 +2929,10 @@ # endif # endif +# ifdef __cpp_lib_find_last +# error "__cpp_lib_find_last should not be defined before c++2b" +# endif + # if !defined(_LIBCPP_VERSION) # ifndef __cpp_lib_format # error "__cpp_lib_format should be defined in c++20" @@ -4161,6 +4178,13 @@ # endif # endif +# ifndef __cpp_lib_find_last +# error "__cpp_lib_find_last should be defined in c++2b" +# endif +# if __cpp_lib_find_last != 202207L +# error "__cpp_lib_find_last should have the value 202207L in c++2b" +# endif + # if !defined(_LIBCPP_VERSION) # ifndef __cpp_lib_format # error "__cpp_lib_format should be defined in c++2b" diff --git a/libcxx/utils/data/ignore_format.txt b/libcxx/utils/data/ignore_format.txt --- a/libcxx/utils/data/ignore_format.txt +++ b/libcxx/utils/data/ignore_format.txt @@ -116,6 +116,7 @@ libcxx/include/__algorithm/ranges_find.h libcxx/include/__algorithm/ranges_find_if.h libcxx/include/__algorithm/ranges_find_if_not.h +libcxx/include/__algorithm/ranges_find_last_if.h libcxx/include/__algorithm/ranges_for_each.h libcxx/include/__algorithm/ranges_for_each_n.h libcxx/include/__algorithm/ranges_generate.h diff --git a/libcxx/utils/generate_feature_test_macro_components.py b/libcxx/utils/generate_feature_test_macro_components.py --- a/libcxx/utils/generate_feature_test_macro_components.py +++ b/libcxx/utils/generate_feature_test_macro_components.py @@ -315,6 +315,10 @@ "test_suite_guard": "!defined(_LIBCPP_AVAILABILITY_HAS_NO_FILESYSTEM)", "libcxx_guard": "!defined(_LIBCPP_AVAILABILITY_HAS_NO_FILESYSTEM)" }, { + "name": "__cpp_lib_find_last", + "values": { "c++2b": 202207 }, + "headers": ["algorithm"], + }, { "name": "__cpp_lib_format", "values": { # "c++20": 201907 Not implemented P1361R2 Integration of chrono with text formatting