diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -5,7 +5,7 @@ Search,find,Nikolas Klauser,`D121248 `_,✅ Search,find_if,Nikolas Klauser,`D121248 `_,✅ Search,find_if_not,Nikolas Klauser,`D121248 `_,✅ -Search,find_first_of,Nikolas Klauser,`D126529 `_,Under review +Search,find_first_of,Nikolas Klauser,`D126529 `_,✅ Search,adjacent_find,Nikolas Klauser,`D126610 `_,Under review Search,mismatch,Nikolas Klauser,`D117817 `_,✅ Search,equal,Nikolas Klauser,`D123681 `_,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -79,6 +79,7 @@ __algorithm/ranges_fill.h __algorithm/ranges_fill_n.h __algorithm/ranges_find.h + __algorithm/ranges_find_first_of.h __algorithm/ranges_find_if.h __algorithm/ranges_find_if_not.h __algorithm/ranges_for_each.h diff --git a/libcxx/include/__algorithm/ranges_find_first_of.h b/libcxx/include/__algorithm/ranges_find_first_of.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_first_of.h @@ -0,0 +1,101 @@ +//===----------------------------------------------------------------------===// +// +// 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_FIRST_OF_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_FIRST_OF_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/indirectly_comparable.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 __find_first_of { +struct __fn { + + template + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter1 __find_first_of_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2) { + for (; __first1 != __last1; ++__first1) { + for (auto __j = __first2; __j != __last2; ++__j) { + if (std::invoke(__pred, std::invoke(__proj1, *__first1), std::invoke(__proj2, *__j))) + return __first1; + } + } + return __first1; + } + + template _Sent1, + forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + class _Pred = ranges::equal_to, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter1 operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __find_first_of_impl(std::move(__first1), std::move(__last1), + std::move(__first2), std::move(__last2), + __pred, + __proj1, + __proj2); + } + + template + requires indirectly_comparable, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range1> operator()(_Range1&& __range1, + _Range2&& __range2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __find_first_of_impl(ranges::begin(__range1), ranges::end(__range1), + ranges::begin(__range2), ranges::end(__range2), + __pred, + __proj1, + __proj2); + } + +}; +} // namespace __find_first_of + +inline namespace __cpo { + inline constexpr auto find_first_of = __find_first_of::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_FIRST_OF_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -370,11 +370,26 @@ indirect_strict_weak_order> Comp = ranges::less> constexpr bool binary_search(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 + template, Proj>> Comp = ranges::less> constexpr bool binary_search(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 + template S1, forward_iterator I2, sentinel_for S2, + class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> + requires indirectly_comparable + constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2, + Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + + template + requires indirectly_comparable, iterator_t, Pred, Proj1, Proj2> + constexpr borrowed_iterator_t + ranges::find_first_of(R1&& r1, R2&& r2, + Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 } @@ -1105,6 +1120,7 @@ #include <__algorithm/ranges_fill.h> #include <__algorithm/ranges_fill_n.h> #include <__algorithm/ranges_find.h> +#include <__algorithm/ranges_find_first_of.h> #include <__algorithm/ranges_find_if.h> #include <__algorithm/ranges_find_if_not.h> #include <__algorithm/ranges_for_each.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -311,6 +311,7 @@ module ranges_fill { private header "__algorithm/ranges_fill.h" } module ranges_fill_n { private header "__algorithm/ranges_fill_n.h" } module ranges_find { private header "__algorithm/ranges_find.h" } + 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_for_each { private header "__algorithm/ranges_for_each.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 @@ -112,8 +112,8 @@ //(void)std::ranges::equal_range(a, value, Less(&copies)); assert(copies == 0); //(void)std::ranges::find_end(first, last, first2, mid2, Equal(&copies)); assert(copies == 0); //(void)std::ranges::find_end(a, b, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::find_first_of(first, last, first2, last2, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::find_first_of(a, b, Equal(&copies)); assert(copies == 0); + (void)std::ranges::find_first_of(first, last, first2, last2, Equal(&copies)); assert(copies == 0); + (void)std::ranges::find_first_of(a, b, Equal(&copies)); assert(copies == 0); (void)std::ranges::find_if(first, last, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::find_if(a, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::find_if_not(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 @@ -98,8 +98,8 @@ (void)std::ranges::find(a, value, Proj(&copies)); assert(copies == 0); //(void)std::ranges::find_end(first, last, first2, mid2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); //(void)std::ranges::find_end(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::find_first_of(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::find_first_of(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::find_first_of(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::find_first_of(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); (void)std::ranges::find_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::find_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::find_if_not(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 @@ -116,6 +116,7 @@ #include <__algorithm/ranges_fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill.h'}} #include <__algorithm/ranges_fill_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill_n.h'}} #include <__algorithm/ranges_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find.h'}} +#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_for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each.h'}} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp @@ -0,0 +1,251 @@ +//===----------------------------------------------------------------------===// +// +// 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 S1, forward_iterator I2, sentinel_for S2, +// class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> +// requires indirectly_comparable +// constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2, +// Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); +// template +// requires indirectly_comparable, iterator_t, Pred, Proj1, Proj2> +// constexpr borrowed_iterator_t +// ranges::find_first_of(R1&& r1, R2&& r2, +// Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +template +concept HasFindFirstOfIt = requires(Iter1 iter1, Sent1 sent1, Iter2 iter2, Sent2 sent2) { + std::ranges::find_first_of(iter1, sent1, iter2, sent2); + }; + +static_assert(HasFindFirstOfIt); +static_assert(!HasFindFirstOfIt); +static_assert(!HasFindFirstOfIt); +static_assert(!HasFindFirstOfIt); +static_assert(!HasFindFirstOfIt); +static_assert(!HasFindFirstOfIt); +static_assert(!HasFindFirstOfIt); +static_assert(!HasFindFirstOfIt); +static_assert(!HasFindFirstOfIt); +static_assert(!HasFindFirstOfIt); +static_assert(!HasFindFirstOfIt); // not indirectly_comparable + +template > +concept HasFindFirstOfR = requires(Range1 range1, Range2 range2) { + std::ranges::find_first_of(range1, range2); + }; + +static_assert(HasFindFirstOfR>); +static_assert(!HasFindFirstOfR); +static_assert(!HasFindFirstOfR); +static_assert(!HasFindFirstOfR); +static_assert(!HasFindFirstOfR, ForwardRangeNotDerivedFrom>); +static_assert(!HasFindFirstOfR, ForwardRangeNotIncrementable>); +static_assert(!HasFindFirstOfR, InputRangeNotSentinelSemiregular>); +static_assert(!HasFindFirstOfR, InputRangeNotSentinelEqualityComparableWith>); +static_assert(!HasFindFirstOfR, ForwardRangeNotSentinelSemiregular>); +static_assert(!HasFindFirstOfR, ForwardRangeNotSentinelEqualityComparableWith>); +static_assert(!HasFindFirstOfR, UncheckedRange>); // not indirectly_comparable + +template +struct Data { + std::array input1; + std::array input2; + ptrdiff_t expected; +}; + +template +constexpr void test(Data d) { + { + std::same_as decltype(auto) ret = + std::ranges::find_first_of(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + d.input1.size())), + Iter2(d.input2.data()), Sent2(Iter2(d.input2.data() + d.input2.size()))); + assert(base(ret) == d.input1.data() + d.expected); + } + { + auto range1 = std::ranges::subrange(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + d.input1.size()))); + auto range2 = std::ranges::subrange(Iter2(d.input2.data()), Sent2(Iter2(d.input2.data() + d.input2.size()))); + std::same_as decltype(auto) ret = std::ranges::find_first_of(range1, range2); + assert(base(ret) == d.input1.data() + d.expected); + } +} + +template +constexpr void test_iterators() { + // simple test + test({.input1 = {1, 2, 3, 4}, .input2 = {2, 3}, .expected = 1}); + // other elements from input2 are checked + test({.input1 = {1, 2, 3, 4}, .input2 = {3, 2}, .expected = 1}); + // an empty second range returns last + test({.input1 = {1, 2, 3, 4}, .input2 = {}, .expected = 4}); + // check that an empty first range works + test({.input1 = {}, .input2 = {1}, .expected = 0}); + // check both ranges empty works + test({.input1 = {}, .input2 = {}, .expected = 0}); + // the first element is checked properly + test({.input1 = {5, 4, 3, 2, 1}, .input2 = {1, 5}, .expected = 0}); + // the last element is checked properly + test({.input1 = {5, 4, 3, 2, 1}, .input2 = {1, 6}, .expected = 4}); + // no match, one-past-the-end iterator should be returned + test({.input1 = {1, 3, 5, 7}, .input2 = {0, 2, 4, 6}, .expected = 4}); + // input2 contains a single element + test({.input1 = {1, 3, 5, 7}, .input2 = {1}, .expected = 0}); +} + +template +constexpr void test_iterators1() { + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); +} + +constexpr bool test() { + test_iterators1, sentinel_wrapper>>(); + test_iterators1, sentinel_wrapper>>(); + test_iterators1>(); + test_iterators1>(); + test_iterators1>(); + test_iterators1>(); + test_iterators1(); + + { // check that std::ranges::dangling is returned + [[maybe_unused]] std::same_as decltype(auto) ret = + std::ranges::find_first_of(std::array {1}, std::array {1}); + } + + { // check that the predicate is used + int a[] = {1, 2, 3, 4}; + int b[] = {2}; + { + auto ret = std::ranges::find_first_of(std::begin(a), std::end(a), + std::begin(b), std::end(b), + std::ranges::greater{}); + assert(ret == a + 2); + } + { + auto ret = std::ranges::find_first_of(a, b, std::ranges::greater{}); + assert(ret == a + 2); + } + } + + { // check that the projections are used + int a[] = {1, 2, 3, 4}; + int b[] = {4}; + { + auto ret = std::ranges::find_first_of(std::begin(a), std::end(a), + std::begin(b), std::end(b), {}, + [](int i) { return i / 2; }, + [](int i) { return i - 3; }); + assert(ret == a + 1); + } + { + auto ret = std::ranges::find_first_of(a, b, {}, [](int i) { return i / 2; }, [](int i) { return i - 3; }); + assert(ret == a + 1); + } + } + + { // check that std::invoke is used + struct S1 { + constexpr S1(int i_) : i(i_) {} + constexpr bool compare(int j) const { return j == i; } + constexpr const S1& identity() const { return *this; } + int i; + }; + struct S2 { + constexpr S2(int i_) : i(i_) {} + int i; + }; + + { + S1 a[] = {1, 2, 3, 4}; + S2 b[] = {2, 3}; + auto ret = std::ranges::find_first_of(std::begin(a), std::end(a), + std::begin(b), std::end(b), &S1::compare, &S1::identity, &S2::i); + assert(ret == a + 1); + } + { + S1 a[] = {1, 2, 3, 4}; + S2 b[] = {2, 3}; + auto ret = std::ranges::find_first_of(a, b, &S1::compare, &S1::identity, &S2::i); + assert(ret == a + 1); + } + } + + { // check that the implicit conversion to bool works + StrictComparable a[] = {1, 2, 3, 4}; + StrictComparable b[] = {2, 3}; + { + auto ret = std::ranges::find_first_of(a, std::end(a), b, std::end(b)); + assert(ret == a + 1); + } + { + auto ret = std::ranges::find_first_of(a, b); + assert(ret == a + 1); + } + } + + { // check that the complexity requirements are met + int a[] = {1, 2, 3, 4}; + int b[] = {2, 3}; + { + int predCount = 0; + auto predCounter = [&](int, int) { ++predCount; return false; }; + int proj1Count = 0; + auto proj1Counter = [&](int i) { ++proj1Count; return i; }; + int proj2Count = 0; + auto proj2Counter = [&](int i) { ++proj2Count; return i; }; + auto ret = std::ranges::find_first_of(std::begin(a), std::end(a), + std::begin(b), std::end(b), predCounter, proj1Counter, proj2Counter); + assert(ret == a + 4); + assert(predCount <= 8); + assert(proj1Count <= 8); + assert(proj2Count <= 8); + } + { + int predCount = 0; + auto predCounter = [&](int, int) { ++predCount; return false; }; + int proj1Count = 0; + auto proj1Counter = [&](int i) { ++proj1Count; return i; }; + int proj2Count = 0; + auto proj2Counter = [&](int i) { ++proj2Count; return i; }; + auto ret = std::ranges::find_first_of(a, b, predCounter, proj1Counter, proj2Counter); + assert(ret == a + 4); + assert(predCount == 8); + assert(proj1Count == 8); + assert(proj2Count == 8); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +}