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_forward_like`` ``202207L`` ------------------------------------------------- ----------------- ``__cpp_lib_invoke_r`` ``202106L`` 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|","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, 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,79 @@ +//===----------------------------------------------------------------------===// +// +// 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,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 __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,36 @@ 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 +1839,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 @@ -397,6 +398,7 @@ # define __cpp_lib_constexpr_memory 202202L # define __cpp_lib_constexpr_typeinfo 202106L # define __cpp_lib_expected 202202L +# define __cpp_lib_find_last 202207L # define __cpp_lib_forward_like 202207L # define __cpp_lib_invoke_r 202106L # define __cpp_lib_is_scoped_enum 202011L 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(); + 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,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(); + 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,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(); + static_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", diff --git a/polly/lib/External/isl/imath/Makefile b/polly/lib/External/isl/imath/Makefile deleted file mode 100644 --- a/polly/lib/External/isl/imath/Makefile +++ /dev/null @@ -1,131 +0,0 @@ -## -## Name: Makefile -## Purpose: Makefile for imath library and associated tools -## Author: M. J. Fromberger -## -## Copyright (C) 2002-2008 Michael J. Fromberger, All Rights Reserved. -## -## Permission is hereby granted, free of charge, to any person obtaining a copy -## of this software and associated documentation files (the "Software"), to -## deal in the Software without restriction, including without limitation the -## rights to use, copy, modify, merge, publish, distribute, sublicense, and/or -## sell copies of the Software, and to permit persons to whom the Software is -## furnished to do so, subject to the following conditions: -## -## The above copyright notice and this permission notice shall be included in -## all copies or substantial portions of the Software. -## -## THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -## IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -## FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -## AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -## LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING -## FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS -## IN THE SOFTWARE. -## - -# --- begin configuration section --- - -## Generic settings for systems with GCC (default) -## To build with debugging, add DEBUG=Y on the "make" command line. -ifeq ($(origin CC),default) -CC=gcc -endif -CFLAGS+=-pedantic -Wall -Werror -Wextra -Wno-unused-parameter \ - -I. -std=c99 $(DFLAGS$(DEBUG)) -CSFLAGS=$(CFLAGS) -fPIC -#LIBS= - -# These are needed to build the GMP compatibility tests. -export CC CFLAGS - -DFLAGS=-O3 -funroll-loops -finline-functions -DFLAGSN=$(DFLAGS) -DFLAGSY=-g -DDEBUG=1 - -# --- end of configuration section --- - -TARGETS=bintest bug-swap imtest imtimer rtest -HDRS=imath.h imrat.h iprime.h imdrover.h rsamath.h gmp_compat.h -SRCS=$(HDRS:.h=.c) $(TARGETS:=.c) -OBJS=$(SRCS:.c=.o) -OTHER=LICENSE ChangeLog Makefile doc.md doc.md.in \ - tools/findthreshold.py tools/mkdoc.py .dockerignore -VPATH += examples tests -EXAMPLES=basecvt findprime imcalc input pi randprime rounding rsakey - -.PHONY: all test clean distclean -.SUFFIXES: .so .md - -.c.o: - $(CC) $(CFLAGS) -c $< - -.c.so: - $(CC) $(CSFLAGS) -o $@ -c $< - -all: objs examples test - -objs: $(OBJS) - -check: test gmp-compat-test - @ echo "Completed running imath and gmp-compat unit tests" - -test: imtest pi bug-swap doc.md - @ echo "" - @ echo "Running tests, you should not see any 'FAILED' lines here." - @ echo "If you do, please see doc.txt for how to report a bug." - @ echo "" - (cd tests && ./test.sh) - -gmp-compat-test: libimath.so - @ echo "Running gmp-compat unit tests" - @ echo "Printing progress after every 100,000 tests" - make -C tests/gmp-compat-test TESTS="-p 100000 random.tests" - -docker-test: - if which docker ; \ - then \ - docker run --rm -it \ - "$(shell docker build -f tests/linux/Dockerfile -q .)" ; \ - fi - -$(EXAMPLES):%: imath.o imrat.o iprime.o %.o - $(CC) $(CFLAGS) -o $@ $^ $(LIBS) - -$(TARGETS):%: imath.o %.o - $(CC) $(CFLAGS) -o $@ $^ $(LIBS) - -examples: $(EXAMPLES) - -libimath.so: imath.so imrat.so gmp_compat.so - $(CC) $(CFLAGS) -shared -o $@ $^ - -imtest: imtest.o imath.o imrat.o imdrover.o iprime.o - -rtest: rtest.o imath.o rsamath.o - -# Requires clang-format: https://clang.llvm.org/docs/ClangFormat.html -format-c: - @ echo "Formatting C source files and headers ..." - find . -type f -name '*.h' -o -name '*.c' -print0 | \ - xargs -0 clang-format --style=Google -i - -# Requires yapf: pip install yapf -format-py: - @ echo "Formatting Python source files ..." - find . -type f -name '*.py' -print0 | \ - xargs -0 yapf --style=pep8 -i - -# Format source files. -format: format-c format-py - -# Generate documentation from header comments. -# This rule depends on the header files to ensure the docs get updated when the -# headers change. -doc.md: doc.md.in imath.h imrat.h tools/mkdoc.py - tools/mkdoc.py $< $@ - -clean distclean: - rm -f *.o *.so *.pyc *~ core gmon.out tests/*~ tests/gmon.out examples/*~ - make -C tests/gmp-compat-test clean - rm -f $(TARGETS) $(EXAMPLES) diff --git a/polly/lib/External/isl/imath/tests/gmp-compat-test/Makefile b/polly/lib/External/isl/imath/tests/gmp-compat-test/Makefile deleted file mode 100644 --- a/polly/lib/External/isl/imath/tests/gmp-compat-test/Makefile +++ /dev/null @@ -1,27 +0,0 @@ -CFLAGS+=-fPIC -I$(IMATH_DIR) -IMATH_DIR=../.. - -runtest: imath_test.so gmp_test.so wrappers.py random.tests - ./runtest $(TESTS) - -gmp_test.c: gmp_custom_test.c genctest.py gmpapi.py - ./genctest.py gmp > $@ - -imath_test.c: imath_custom_test.c genctest.py gmpapi.py - ./genctest.py imath > $@ - -gmp_test.so: gmp_test.o - $(CC) $(CFLAGS) -shared -o $@ $^ -lgmp - -imath_test.so: imath_test.o - $(CC) $(CFLAGS) -shared -L$(IMATH_DIR) -o $@ $^ -limath - -wrappers.py: genpytest.py gmpapi.py - ./genpytest.py > $@ - -random.tests: gendata.py - ./gendata.py > $@ - -clean: - rm -f a.out *.so *.o gmp_test.c imath_test.c wrappers.py *.pyc - rm -rf __pycache__