diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -66,6 +66,7 @@ __algorithm/pop_heap.h __algorithm/prev_permutation.h __algorithm/push_heap.h + __algorithm/ranges_adjacent_find.h __algorithm/ranges_all_of.h __algorithm/ranges_any_of.h __algorithm/ranges_binary_search.h diff --git a/libcxx/include/__algorithm/ranges_adjacent_find.h b/libcxx/include/__algorithm/ranges_adjacent_find.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_adjacent_find.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_ADJACENT_FIND_H +#define _LIBCPP___ALGORITHM_RANGES_ADJACENT_FIND_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __adjacent_find { +struct __fn { + + template + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __adjacent_find_impl(_Iter __first, _Sent __last, _Pred& __pred, _Proj& __proj) { + if (__first == __last) + return __first; + + auto __i = __first; + while (++__i != __last) { + if (std::invoke(__pred, std::invoke(__proj, *__first), std::invoke(__proj, *__i))) + return __first; + __first = __i; + } + return __i; + } + + template _Sent, + class _Proj = identity, + indirect_binary_predicate, projected<_Iter, _Proj>> _Pred = ranges::equal_to> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, _Pred __pred = {}, _Proj __proj = {}) const { + return __adjacent_find_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template , _Proj>, + projected, _Proj>> _Pred = ranges::equal_to> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __range, _Pred __pred = {}, _Proj __proj = {}) const { + return __adjacent_find_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj); + } +}; +} // namespace __adjacent_find + +inline namespace __cpo { + inline constexpr auto adjacent_find = __adjacent_find::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_ADJACENT_FIND_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -391,6 +391,16 @@ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + template S, class Proj = identity, + indirect_binary_predicate, + projected> Pred = ranges::equal_to> + constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {}); // since C+20 + + template, Proj>, + projected, Proj>> Pred = ranges::equal_to> + constexpr borrowed_iterator_t ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {}); // since C++20 + } constexpr bool // constexpr in C++20 @@ -1107,6 +1117,7 @@ #include <__algorithm/pop_heap.h> #include <__algorithm/prev_permutation.h> #include <__algorithm/push_heap.h> +#include <__algorithm/ranges_adjacent_find.h> #include <__algorithm/ranges_all_of.h> #include <__algorithm/ranges_any_of.h> #include <__algorithm/ranges_binary_search.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -298,6 +298,7 @@ module pop_heap { private header "__algorithm/pop_heap.h" } module prev_permutation { private header "__algorithm/prev_permutation.h" } module push_heap { private header "__algorithm/push_heap.h" } + module ranges_adjacent_find { private header "__algorithm/ranges_adjacent_find.h" } module ranges_all_of { private header "__algorithm/ranges_all_of.h" } module ranges_any_of { private header "__algorithm/ranges_any_of.h" } module ranges_binary_search { private header "__algorithm/ranges_binary_search.h" } diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -90,8 +90,8 @@ int count = 1; int copies = 0; - //(void)std::ranges::adjacent_find(first, last, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::adjacent_find(a, Equal(&copies)); assert(copies == 0); + (void)std::ranges::adjacent_find(first, last, Equal(&copies)); assert(copies == 0); + (void)std::ranges::adjacent_find(a, Equal(&copies)); assert(copies == 0); (void)std::ranges::all_of(first, last, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::all_of(a, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::any_of(first, last, UnaryTrue(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -72,8 +72,8 @@ int count = 1; int copies = 0; - //(void)std::ranges::adjacent_find(first, last, Equal(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::adjacent_find(a, Equal(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::adjacent_find(first, last, Equal(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::adjacent_find(a, Equal(), Proj(&copies)); assert(copies == 0); (void)std::ranges::all_of(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::all_of(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::any_of(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); 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 @@ -103,6 +103,7 @@ #include <__algorithm/pop_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pop_heap.h'}} #include <__algorithm/prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/prev_permutation.h'}} #include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}} +#include <__algorithm/ranges_adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_adjacent_find.h'}} #include <__algorithm/ranges_all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_all_of.h'}} #include <__algorithm/ranges_any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_any_of.h'}} #include <__algorithm/ranges_binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_binary_search.h'}} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.adjacent.find/ranges.adjacent_find.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.adjacent.find/ranges.adjacent_find.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.adjacent.find/ranges.adjacent_find.pass.cpp @@ -0,0 +1,197 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S, class Proj = identity, +// indirect_binary_predicate, +// projected> Pred = ranges::equal_to> +// constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {}); +// template, Proj>, +// projected, Proj>> Pred = ranges::equal_to> +// constexpr borrowed_iterator_t ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {}); + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +template +concept HasAdjacentFindIt = requires (Iter iter, Sent sent) { std::ranges::adjacent_find(iter, sent); }; + +struct NotComparable {}; + +static_assert(HasAdjacentFindIt); +static_assert(!HasAdjacentFindIt); +static_assert(!HasAdjacentFindIt); +static_assert(!HasAdjacentFindIt); +static_assert(!HasAdjacentFindIt); +static_assert(!HasAdjacentFindIt); + +template +concept HasAdjacentFindR = requires (Range range) { std::ranges::adjacent_find(range); }; + +static_assert(HasAdjacentFindR>); +static_assert(!HasAdjacentFindR); +static_assert(!HasAdjacentFindR); +static_assert(!HasAdjacentFindR); +static_assert(!HasAdjacentFindR); +static_assert(!HasAdjacentFindR>); + +template +struct Data { + std::array input; + int expected; +}; + +template +constexpr void test(Data d) { + { + std::same_as decltype(auto) ret = + std::ranges::adjacent_find(Iter(d.input.data()), Sent(Iter(d.input.data() + d.input.size()))); + assert(base(ret) == d.input.data() + d.expected); + } + { + auto range = std::ranges::subrange(Iter(d.input.data()), Sent(Iter(d.input.data() + d.input.size()))); + std::same_as decltype(auto) ret = std::ranges::adjacent_find(range); + assert(base(ret) == d.input.data() + d.expected); + } +} + +template +constexpr void test_iterators() { + // simple test + test({.input = {1, 2, 2, 4}, .expected = 1}); + // last is returned with no match + test({.input = {1, 2, 3, 4}, .expected = 4}); + // first elements match + test({.input = {1, 1, 3, 4}, .expected = 0}); + // the first match is returned + test({.input = {1, 1, 3, 4, 4, 4, 4}, .expected = 0}); + // two element range works + test({.input = {3, 3}, .expected = 0}); + // single element range works + test({.input = {1}, .expected = 1}); + // empty range works + test({.input = {}, .expected = 0}); +} + +constexpr bool test() { + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); + test_iterators(); + + { // check that ranges::dangling is returned + [[maybe_unused]] std::same_as decltype(auto) ret = + std::ranges::adjacent_find(std::array{1, 2, 3, 4}); + } + + { // check that the complexity requirements are met with no match + { + int predicateCount = 0; + auto pred = [&](int, int) { ++predicateCount; return false; }; + auto projectionCount = 0; + auto proj = [&](int i) { ++projectionCount; return i; }; + int a[] = {1, 2, 3, 4, 5}; + auto ret = std::ranges::adjacent_find(a, a + 5, pred, proj); + assert(ret == a + 5); + assert(predicateCount == 4); + assert(projectionCount == 8); + } + { + int predicateCount = 0; + auto pred = [&](int, int) { ++predicateCount; return false; }; + auto projectionCount = 0; + auto proj = [&](int i) { ++projectionCount; return i; }; + int a[] = {1, 2, 3, 4, 5}; + auto ret = std::ranges::adjacent_find(a, pred, proj); + assert(ret == a + 5); + assert(predicateCount == 4); + assert(projectionCount == 8); + } + } + + { // check that the complexity requirements are met with a match + { + int predicateCount = 0; + auto pred = [&](int i, int j) { ++predicateCount; return i == j; }; + auto projectionCount = 0; + auto proj = [&](int i) { ++projectionCount; return i; }; + int a[] = {1, 2, 4, 4, 5}; + auto ret = std::ranges::adjacent_find(a, a + 5, pred, proj); + assert(ret == a + 2); + assert(predicateCount == 3); + assert(projectionCount == 6); + } + { + int predicateCount = 0; + auto pred = [&](int i, int j) { ++predicateCount; return i == j; }; + auto projectionCount = 0; + auto proj = [&](int i) { ++projectionCount; return i; }; + int a[] = {1, 2, 4, 4, 5}; + auto ret = std::ranges::adjacent_find(a, pred, proj); + assert(ret == a + 2); + assert(predicateCount == 3); + assert(projectionCount == 6); + } + } + + { // check that std::invoke is used + struct S { + constexpr S(int i_) : i(i_) {} + constexpr bool compare(const S& j) const { return j.i == i; } + constexpr const S& identity() const { return *this; } + int i; + }; + { + S a[] = {1, 2, 3, 4}; + auto ret = std::ranges::adjacent_find(std::begin(a), std::end(a), &S::compare, &S::identity); + assert(ret == a + 4); + } + { + S a[] = {1, 2, 3, 4}; + auto ret = std::ranges::adjacent_find(a, &S::compare, &S::identity); + assert(ret == a + 4); + } + } + + { // check that the implicit conversion to bool works + { + int a[] = {1, 2, 2, 4}; + auto ret = std::ranges::adjacent_find(a, a + 4, [](int i, int j) { return BooleanTestable{i == j}; }); + assert(ret == a + 1); + } + { + int a[] = {1, 2, 2, 4}; + auto ret = std::ranges::adjacent_find(a, [](int i, int j) { return BooleanTestable{i == j}; }); + assert(ret == a + 1); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -60,7 +60,7 @@ // [algorithm.syn] -//static_assert(test(std::ranges::adjacent_find, a)); +static_assert(test(std::ranges::adjacent_find, a)); static_assert(test(std::ranges::all_of, a, odd)); static_assert(test(std::ranges::any_of, a, odd)); static_assert(test(std::ranges::binary_search, a, 42));