diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -155,6 +155,7 @@ __algorithm/ranges_sort_heap.h __algorithm/ranges_stable_partition.h __algorithm/ranges_stable_sort.h + __algorithm/ranges_starts_with.h __algorithm/ranges_swap_ranges.h __algorithm/ranges_transform.h __algorithm/ranges_unique.h diff --git a/libcxx/include/__algorithm/ranges_starts_with.h b/libcxx/include/__algorithm/ranges_starts_with.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_starts_with.h @@ -0,0 +1,88 @@ +//===----------------------------------------------------------------------===// +// +// 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_STARTS_WITH_H +#define _LIBCPP___ALGORITHM_RANGES_STARTS_WITH_H + +#include "ranges_mismatch.h" +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.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 __starts_with { +struct __fn { + 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_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool operator()( + _Iter1 __first1, + _Sent1 __last1, + _Iter2 __first2, + _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __mismatch::__fn::__go( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + __pred, + __proj1, + __proj2) + .in2 == __last2; + } + + template + requires indirectly_comparable, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool operator()( + _Range1&& __range1, _Range2&& __range2, _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { + return __mismatch::__fn::__go( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + __pred, + __proj1, + __proj2) + .in2 == ranges::end(__range2); + } +}; +} // namespace __starts_with +inline namespace __cpo { +inline constexpr auto starts_with = __starts_with::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER >= 23 + +#endif // _LIBCPP___ALGORITHM_RANGES_STARTS_WITH_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -446,6 +446,18 @@ indirect_unary_predicate, Proj>> Pred> constexpr bool ranges::none_of(R&& r, Pred pred, Proj proj = {}); // 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::starts_with(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++23 + + template + requires indirectly_comparable, iterator_t, Pred, Proj1, Proj2> + constexpr bool ranges::starts_with(R1&& r1, R2&& r2, Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++23 + template S1, random_access_iterator I2, sentinel_for S2, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> @@ -1873,6 +1885,7 @@ #include <__algorithm/ranges_sort_heap.h> #include <__algorithm/ranges_stable_partition.h> #include <__algorithm/ranges_stable_sort.h> +#include <__algorithm/ranges_starts_with.h> #include <__algorithm/ranges_swap_ranges.h> #include <__algorithm/ranges_transform.h> #include <__algorithm/ranges_unique.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 @@ -554,6 +554,7 @@ private header "__algorithm/ranges_stable_sort.h" export functional.__functional.ranges_operations } + module ranges_starts_with { private header "__algorithm/ranges_starts_with.h" } module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.h" export algorithm.__algorithm.in_in_result 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 @@ -215,7 +215,8 @@ if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(&copies)); assert(copies == 0); } if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(&copies)); assert(copies == 0); } #if TEST_STD_VER > 20 - //(void)std::ranges::starts_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0); + (void)std::ranges::starts_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0); + (void)std::ranges::starts_with(a, b, Equal(&copies)); assert(copies == 0); #endif (void)std::ranges::transform(first, last, first2, UnaryTransform(&copies)); assert(copies == 0); (void)std::ranges::transform(a, first2, UnaryTransform(&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 @@ -206,7 +206,8 @@ if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(), Proj(&copies)); assert(copies == 0); } if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(), Proj(&copies)); assert(copies == 0); } #if TEST_STD_VER > 20 - //(void)std::ranges::starts_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::starts_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::starts_with(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); #endif (void)std::ranges::transform(first, last, first2, UnaryTransform(), Proj(&copies)); assert(copies == 0); (void)std::ranges::transform(a, first2, UnaryTransform(), 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 @@ -196,6 +196,7 @@ #include <__algorithm/ranges_sort_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort_heap.h'}} #include <__algorithm/ranges_stable_partition.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_stable_partition.h'}} #include <__algorithm/ranges_stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_stable_sort.h'}} +#include <__algorithm/ranges_starts_with.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_starts_with.h'}} #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}} #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}} #include <__algorithm/ranges_unique.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_unique.h'}} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.starts_with/ranges.starts_with.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.starts_with/ranges.starts_with.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.starts_with/ranges.starts_with.pass.cpp @@ -0,0 +1,255 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 + +// template S1, input_iterator I2, sentinel_for S2, +// class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> +// requires indirectly_comparable +// constexpr bool ranges::starts_with(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::starts_with(R1&& r1, R2&& r2, Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); + +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template +concept HasStartsWithIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { + std::ranges::starts_with(first1, last1, first2, last2); +}; + +static_assert(HasStartsWithIt); +static_assert(HasStartsWithIt); +static_assert(HasStartsWithIt); +static_assert(!HasStartsWithIt); +static_assert(!HasStartsWithIt); // not indirectly comparable +static_assert(!HasStartsWithIt); +static_assert(HasStartsWithIt); +static_assert(HasStartsWithIt); +static_assert(!HasStartsWithIt); +static_assert(!HasStartsWithIt); + +template > +concept HasStartsWithR = requires (Range1 range1, Range2 range2) { + std::ranges::starts_with(range1, range2); +}; + +static_assert(HasStartsWithR>); +static_assert(HasStartsWithR); +static_assert(!HasStartsWithR); +static_assert(!HasStartsWithR); +static_assert(!HasStartsWithR); +static_assert(!HasStartsWithR, UncheckedRange>); // not indirectly comparable +static_assert(HasStartsWithR, ForwardRangeNotDerivedFrom>); +static_assert(HasStartsWithR, ForwardRangeNotIncrementable>); +static_assert(!HasStartsWithR, ForwardRangeNotSentinelSemiregular>); +static_assert(!HasStartsWithR, ForwardRangeNotSentinelEqualityComparableWith>); + +template +constexpr void test_iterators() { + {// simply tests + {int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {1, 2}; + std::same_as decltype(auto) ret = + std::ranges::starts_with(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2))); + assert(ret); + } + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {1, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2))); + std::same_as decltype(auto) ret = std::ranges::starts_with(whole, prefix); + assert(ret); + } + } + + {// prefix doesn't match + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {4, 5, 6}; + std::same_as decltype(auto) ret = + std::ranges::starts_with(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 3))); + assert(!ret); + } + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {4, 5, 6}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + std::same_as decltype(auto) ret = std::ranges::starts_with(whole, prefix); + assert(!ret); + } + } + + {// range and prefix are identical + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {1, 2, 3, 4, 5, 6}; + std::same_as decltype(auto) ret = + std::ranges::starts_with(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 6))); + assert(ret); + } + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {1, 2, 3, 4, 5, 6}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 6))); + std::same_as decltype(auto) ret = std::ranges::starts_with(whole, prefix); + assert(ret); + } + } + + {// prefix is longer than range + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {1, 2, 3, 4, 5, 6, 7, 8}; + std::same_as decltype(auto) ret = + std::ranges::starts_with(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 8))); + assert(!ret); + } + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {1, 2, 3, 4, 5, 6, 7, 8}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8))); + std::same_as decltype(auto) ret = std::ranges::starts_with(whole, prefix); + assert(!ret); + } + } + + {// prefix has zero length + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {}; + std::same_as decltype(auto) ret = + std::ranges::starts_with(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p))); + assert(ret); + } + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p))); + std::same_as decltype(auto) ret = std::ranges::starts_with(whole, prefix); + assert(ret); + } + } + + {// range has zero length + { + int a[] = {}; + int p[] = {1, 2, 3, 4, 5, 6, 7, 8}; + std::same_as decltype(auto) ret = + std::ranges::starts_with(Iter1(a), Sent1(Iter1(a)), Iter2(p), Sent2(Iter2(p + 8))); + assert(!ret); + } + { + int a[] = {}; + int p[] = {1, 2, 3, 4, 5, 6, 7, 8}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); + auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8))); + std::same_as decltype(auto) ret = std::ranges::starts_with(whole, prefix); + assert(!ret); + } + } + + {// check that the predicate is used + { + int a[] = {11, 8, 3, 4, 0, 6}; + int p[] = {1, 12}; + std::same_as decltype(auto) ret = std::ranges::starts_with( + Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2)), [](int l, int r) { return l > r; }); + assert(!ret); + } + { + int a[] = {11, 8, 3, 4, 0, 6}; + int p[] = {1, 12}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2))); + std::same_as decltype(auto) ret = std::ranges::starts_with(whole, prefix, [](int l, int r) { return l > r; }); + assert(!ret); + } + } + + {// check that the projections are used + { + int a[] = {1, 3, 5, 1, 5, 6}; + int p[] = {2, 3, 4}; + std::same_as decltype(auto) ret = std::ranges::starts_with( + Iter1(a), + Sent1(Iter1(a + 6)), + Iter2(p), + Sent2(Iter2(p + 3)), + {}, + [](int i) { return i + 3; }, + [](int i) { return i * 2; }); + assert(ret); + } + { + int a[] = {1, 3, 5, 1, 5, 6}; + int p[] = {2, 3, 4}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + std::same_as decltype(auto) ret = std::ranges::starts_with( + whole, prefix, {}, [](int i) { return i + 3; }, [](int i) { return i * 2; }); + assert(ret); + } + } +} + +constexpr bool test() { + types::for_each(types::forward_iterator_list{}, []() { + types::for_each(types::forward_iterator_list{}, []() { + test_iterators(); + test_iterators, I2, I2>(); + test_iterators>(); + test_iterators, I2, sized_sentinel>(); + }); +}); + + { // check that std::invoke is used + struct S { + int i; + + constexpr S identity() { return *this; } + + constexpr bool compare(const S& s) { return i == s.i; } + }; + { + S a[] = {{1}, {2}, {3}, {4}}; + S p[] = {{1}, {2}}; + auto ret = std::ranges::starts_with(a, a + 4, p, p + 2, &S::compare, &S::identity, &S::identity); + assert(ret); + } + { + S a[] = {{1}, {2}, {3}, {4}}; + S p[] = {{1}, {2}}; + auto ret = std::ranges::starts_with(a, p, &S::compare, &S::identity, &S::identity); + assert(ret); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + return 0; +} diff --git a/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp @@ -74,7 +74,7 @@ test(std::ranges::set_symmetric_difference, in, in2, out2, less, proj1, proj2); test(std::ranges::set_union, in, in2, out, less, proj1, proj2); test(std::ranges::set_union, in, in2, out2, less, proj1, proj2); - //test(std::ranges::starts_with, in, in2, eq, proj1, proj2); + test(std::ranges::starts_with, in, in2, eq, proj1, proj2); //test(std::ranges::ends_with, in, in2, eq, proj1, proj2); return true; 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 @@ -140,7 +140,7 @@ static_assert(test(std::ranges::sort_heap, a)); static_assert(test(std::ranges::stable_partition, a, odd)); static_assert(test(std::ranges::stable_sort, a)); -//static_assert(test(std::ranges::starts_with, a, a)); +static_assert(test(std::ranges::starts_with, a, a)); static_assert(test(std::ranges::swap_ranges, a, a)); static_assert(test(std::ranges::transform, a, a, triple)); static_assert(test(std::ranges::unique, a));