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 @@ -8,7 +8,7 @@ Search,find_first_of,Not assigned,n/a,Not started Search,adjacent_find,Not assigned,n/a,Not started Search,mismatch,Nikolas Klauser,`D117817 `_,✅ -Search,equal,Not assigned,n/a,Not started +Search,equal,Nikolas Klauser,n/a,✅ Search,lexicographical_compare,Not assigned,n/a,Not started Search,partition_point,Christopher Di Bella,`D105794 `_,Under review Search,lower_bound,Christopher Di Bella,`D105795 `_,Under review diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -72,6 +72,7 @@ __algorithm/ranges_copy_n.h __algorithm/ranges_count.h __algorithm/ranges_count_if.h + __algorithm/ranges_equal.h __algorithm/ranges_fill.h __algorithm/ranges_fill_n.h __algorithm/ranges_find.h diff --git a/libcxx/include/__algorithm/ranges_equal.h b/libcxx/include/__algorithm/ranges_equal.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_equal.h @@ -0,0 +1,115 @@ +//===----------------------------------------------------------------------===// +// +// 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_EQUAL_H +#define _LIBCPP___ALGORITHM_RANGES_EQUAL_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/distance.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.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 __equal { +struct __fn { +private: + template + _LIBCPP_HIDE_FROM_ABI constexpr static + bool __equal_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2) { + while (__first1 != __last1 && __first2 != __last2) { + if (!std::invoke(__pred, std::invoke(__proj1, *__first1), std::invoke(__proj2, *__first2))) + return false; + ++__first1; + ++__first2; + } + return __first1 == __last1 && __first2 == __last2; + } + +public: + + template _Sent1, + input_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 + bool operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + if constexpr (sized_sentinel_for<_Sent1, _Iter1> && sized_sentinel_for<_Sent2, _Iter2>) { + if (__last1 - __first1 != __last2 - __first2) + return false; + } + return __equal_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 + bool operator()(_Range1&& __range1, + _Range2&& __range2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + if constexpr (sized_range<_Range1> && sized_range<_Range2>) { + if (ranges::distance(__range1) != ranges::distance(__range2)) + return false; + } + return __equal_impl(ranges::begin(__range1), ranges::end(__range1), + ranges::begin(__range2), ranges::end(__range2), + __pred, + __proj1, + __proj2); + return false; + } +}; +} // namespace __equal + +inline namespace __cpo { + inline constexpr auto equal = __equal::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_EQUAL_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -291,6 +291,20 @@ template O> constexpr O ranges::fill_n(O first, iter_difference_t n, const T& value); // since C++20 + + template S1, input_iterator I2, sentinel_for S2, + class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> + requires indirectly_comparable + constexpr bool ranges::equal(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 bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + } constexpr bool // constexpr in C++20 @@ -1013,6 +1027,7 @@ #include <__algorithm/ranges_copy_n.h> #include <__algorithm/ranges_count.h> #include <__algorithm/ranges_count_if.h> +#include <__algorithm/ranges_equal.h> #include <__algorithm/ranges_fill.h> #include <__algorithm/ranges_fill_n.h> #include <__algorithm/ranges_find.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -304,6 +304,7 @@ module ranges_copy_n { private header "__algorithm/ranges_copy_n.h" } module ranges_count { private header "__algorithm/ranges_count.h" } module ranges_count_if { private header "__algorithm/ranges_count_if.h" } + module ranges_equal { private header "__algorithm/ranges_equal.h" } 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" } 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 @@ -106,8 +106,8 @@ #if TEST_STD_VER > 20 //(void)std::ranges::ends_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0); #endif - //(void)std::ranges::equal(first, last, first2, last2, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::equal(a, b, Equal(&copies)); assert(copies == 0); + (void)std::ranges::equal(first, last, first2, last2, Equal(&copies)); assert(copies == 0); + (void)std::ranges::equal(a, b, Equal(&copies)); assert(copies == 0); //(void)std::ranges::equal_range(first, last, value, Less(&copies)); assert(copies == 0); //(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); 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 @@ -90,8 +90,8 @@ #if TEST_STD_VER > 20 //(void)std::ranges::ends_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); #endif - //(void)std::ranges::equal(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::equal(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::equal(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::equal(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); //(void)std::ranges::equal_range(first, last, value, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::equal_range(a, value, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::find(first, last, value, 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 @@ -109,6 +109,7 @@ #include <__algorithm/ranges_copy_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_n.h'}} #include <__algorithm/ranges_count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}} #include <__algorithm/ranges_count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}} +#include <__algorithm/ranges_equal.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_equal.h'}} #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'}} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp @@ -0,0 +1,375 @@ +//===----------------------------------------------------------------------===// +// +// 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, input_iterator I2, sentinel_for S2, +// class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> +// requires indirectly_comparable +// constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2, +// Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); +// template +// requires indirectly_comparable, iterator_t, Pred, Proj1, Proj2> +// constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template , + class Iter2 = Iter1, class Sent2 = sentinel_wrapper> +concept HasEqualIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { + std::ranges::equal(first1, last1, first2, last2); +}; + +static_assert(HasEqualIt); +static_assert(!HasEqualIt); +static_assert(!HasEqualIt); +static_assert(!HasEqualIt); +static_assert(!HasEqualIt); +static_assert(!HasEqualIt); +static_assert(!HasEqualIt); +static_assert(!HasEqualIt); +static_assert(!HasEqualIt); +static_assert(!HasEqualIt); +static_assert(!HasEqualIt); +static_assert(!HasEqualIt); + +template +concept HasEqualR = requires (Range1 range1, Range2 range2) { + std::ranges::equal(range1, range2); +}; + +static_assert(HasEqualR, UncheckedRange>); +static_assert(!HasEqualR>); +static_assert(!HasEqualR>); +static_assert(!HasEqualR>); +static_assert(!HasEqualR>); +static_assert(!HasEqualR>); +static_assert(!HasEqualR, InputRangeNotDerivedFrom>); +static_assert(!HasEqualR, InputRangeNotIndirectlyReadable>); +static_assert(!HasEqualR, InputRangeNotInputOrOutputIterator>); +static_assert(!HasEqualR, InputRangeNotSentinelSemiregular>); +static_assert(!HasEqualR, InputRangeNotSentinelEqualityComparableWith>); +static_assert(!HasEqualR, UncheckedRange>); + +template +constexpr void test_iterators() { + { // simple test + { + int a[] = {1, 2, 3, 4}; + int b[] = {1, 2, 3, 4}; + std::same_as decltype(auto) ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), + Iter2(b), Sent2(Iter2(b + 4))); + assert(ret); + } + { + int a[] = {1, 2, 3, 4}; + int b[] = {1, 2, 3, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); + auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); + std::same_as decltype(auto) ret = std::ranges::equal(range1, range2); + assert(ret); + } + } + + { // check that the predicate is used (return true) + { + int a[] = {1, 2, 3, 4}; + int b[] = {2, 3, 4, 5}; + auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)), + [](int l, int r) { return l != r; }); + assert(ret); + } + { + int a[] = {1, 2, 3, 4}; + int b[] = {2, 3, 4, 5}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); + auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); + auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; }); + assert(ret); + } + } + + { // check that the predicate is used (return false) + { + int a[] = {1, 2, 3, 4}; + int b[] = {2, 3, 3, 5}; + auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)), + [](int l, int r) { return l != r; }); + assert(!ret); + } + { + int a[] = {1, 2, 3, 4}; + int b[] = {2, 3, 3, 5}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); + auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); + auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; }); + assert(!ret); + } + } + + { // check that the projections are used + { + int a[] = {1, 2, 3, 4, 5}; + int b[] = {6, 10, 14, 18, 22}; + auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), + Iter2(b), Sent2(Iter2(b + 5)), + {}, + [](int i) { return i * 4; }, + [](int i) { return i - 2; }); + assert(ret); + } + { + int a[] = {1, 2, 3, 4, 5}; + int b[] = {6, 10, 14, 18, 22}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5))); + auto ret = std::ranges::equal(range1, + range2, + {}, + [](int i) { return i * 4; }, + [](int i) { return i - 2; }); + assert(ret); + } + } + + { // check that different sized ranges work + { + int a[] = {4, 3, 2, 1}; + int b[] = {4, 3, 2, 1, 5, 6, 7}; + auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 7))); + assert(!ret); + } + { + int a[] = {4, 3, 2, 1}; + int b[] = {4, 3, 2, 1, 5, 6, 7}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); + auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 7))); + auto ret = std::ranges::equal(range1, range2); + assert(!ret); + } + } + + { // check that two ranges with the same size but different values are different + { + int a[] = {4, 6, 34, 76, 5}; + int b[] = {4, 6, 34, 67, 5}; + auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), Iter2(b), Sent2(Iter2(b + 5))); + assert(!ret); + } + { + int a[] = {4, 6, 34, 76, 5}; + int b[] = {4, 6, 34, 67, 5}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5))); + auto ret = std::ranges::equal(range1, range2); + assert(!ret); + } + } + + { // check that two empty ranges work + { + int a[] = {}; + int b[] = {}; + auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b))); + assert(ret); + } + { + int a[] = {}; + int b[] = {}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); + auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b))); + auto ret = std::ranges::equal(range1, range2); + assert(ret); + } + } + + { // check that it works with the first range empty + { + int a[] = {}; + int b[] = {1, 2}; + auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b + 2))); + assert(!ret); + } + { + int a[] = {}; + int b[] = {1, 2}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); + auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 2))); + auto ret = std::ranges::equal(range1, range2); + assert(!ret); + } + } + + { // check that it works with the second range empty + { + int a[] = {1, 2}; + int b[] = {}; + auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 2)), Iter2(b), Sent2(Iter2(b))); + assert(!ret); + } + { + int a[] = {1, 2}; + int b[] = {}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 2))); + auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b))); + auto ret = std::ranges::equal(range1, range2); + assert(!ret); + } + } +} + +template +constexpr void test_iterators2() { + test_iterators, sentinel_wrapper>>(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); + test_iterators(); +} + +constexpr bool test() { + test_iterators2, sentinel_wrapper>>(); + test_iterators2, sentinel_wrapper>>(); + test_iterators2>(); + test_iterators2>(); + test_iterators2>(); + test_iterators2>(); + test_iterators2(); + test_iterators2(); + + { // check that std::invoke is used + struct S { + constexpr S(int i_) : i(i_) {} + constexpr bool equal(int o) { return i == o; } + constexpr S& identity() { return *this; } + int i; + }; + { + S a[] = {7, 8, 9}; + S b[] = {7, 8, 9}; + auto ret = std::ranges::equal(a, a + 3, b, b + 3, &S::equal, &S::identity, &S::i); + assert(ret); + } + { + S a[] = {7, 8, 9}; + S b[] = {7, 8, 9}; + auto ret = std::ranges::equal(a, b, &S::equal, &S::identity, &S::i); + assert(ret); + } + } + + { // check that the complexity requirements are met + { // different size + { + int a[] = {1, 2, 3}; + int b[] = {1, 2, 3, 4}; + int predCount = 0; + int projCount = 0; + auto pred = [&](int l, int r) { ++predCount; return l == r; }; + auto proj = [&](int i) { ++projCount; return i; }; + auto ret = std::ranges::equal(a, a + 3, b, b + 4, pred, proj, proj); + assert(!ret); + assert(predCount == 0); + assert(projCount == 0); + } + { + int a[] = {1, 2, 3}; + int b[] = {1, 2, 3, 4}; + int predCount = 0; + int projCount = 0; + auto pred = [&](int l, int r) { ++predCount; return l == r; }; + auto proj = [&](int i) { ++projCount; return i; }; + auto ret = std::ranges::equal(a, b, pred, proj, proj); + assert(!ret); + assert(predCount == 0); + assert(projCount == 0); + } + } + + { // not a sized sentinel + { + int a[] = {1, 2, 3}; + int b[] = {1, 2, 3, 4}; + int predCount = 0; + int projCount = 0; + auto pred = [&](int l, int r) { ++predCount; return l == r; }; + auto proj = [&](int i) { ++projCount; return i; }; + auto ret = std::ranges::equal(a, sentinel_wrapper(a + 3), b, sentinel_wrapper(b + 4), pred, proj, proj); + assert(!ret); + assert(predCount <= 4); + assert(projCount <= 7); + } + { + int a[] = {1, 2, 3}; + int b[] = {1, 2, 3, 4}; + int predCount = 0; + int projCount = 0; + auto pred = [&](int l, int r) { ++predCount; return l == r; }; + auto proj = [&](int i) { ++projCount; return i; }; + auto range1 = std::ranges::subrange(a, sentinel_wrapper(a + 3)); + auto range2 = std::ranges::subrange(b, sentinel_wrapper(b + 4)); + auto ret = std::ranges::equal(range1, range2, pred, proj, proj); + assert(!ret); + assert(predCount <= 4); + assert(projCount <= 7); + } + } + + { // same size + { + int a[] = {1, 2, 3}; + int b[] = {1, 2, 3}; + int predCount = 0; + int projCount = 0; + auto pred = [&](int l, int r) { ++predCount; return l == r; }; + auto proj = [&](int i) { ++projCount; return i; }; + auto ret = std::ranges::equal(a, a + 3, b, b + 3, pred, proj, proj); + assert(ret); + assert(predCount == 3); + assert(projCount == 6); + } + { + int a[] = {1, 2, 3}; + int b[] = {1, 2, 3}; + int predCount = 0; + int projCount = 0; + auto pred = [&](int l, int r) { ++predCount; return l == r; }; + auto proj = [&](int i) { ++projCount; return i; }; + auto ret = std::ranges::equal(a, b, pred, proj, proj); + assert(ret); + assert(predCount == 3); + assert(projCount == 6); + } + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +}