https://github.com/ZijunZhaoCCK updated https://github.com/llvm/llvm-project/pull/66963
>From 647f5fe641b30c874bab770fced9fcec9b601161 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Wed, 13 Sep 2023 14:26:01 -0700 Subject: [PATCH 01/15] [libc++] Implement ranges::contains_subrange --- libcxx/include/CMakeLists.txt | 1 + .../__algorithm/ranges_contains_subrange.h | 145 +++++++++ libcxx/include/algorithm | 14 + ...obust_against_copying_projections.pass.cpp | 2 + .../ranges.contains_subrange.pass.cpp | 293 ++++++++++++++++++ .../niebloid.compile.pass.cpp | 1 + 6 files changed, 456 insertions(+) create mode 100644 libcxx/include/__algorithm/ranges_contains_subrange.h create mode 100644 libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index 0fe3ab44d2466e..dd3ff541fbc7ba 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -110,6 +110,7 @@ set(files __algorithm/ranges_binary_search.h __algorithm/ranges_clamp.h __algorithm/ranges_contains.h + __algorithm/ranges_contains_subrange.h __algorithm/ranges_copy.h __algorithm/ranges_copy_backward.h __algorithm/ranges_copy_if.h diff --git a/libcxx/include/__algorithm/ranges_contains_subrange.h b/libcxx/include/__algorithm/ranges_contains_subrange.h new file mode 100644 index 00000000000000..16de6c29cb2a1a --- /dev/null +++ b/libcxx/include/__algorithm/ranges_contains_subrange.h @@ -0,0 +1,145 @@ +//===----------------------------------------------------------------------===// +// +// 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_CONTAINS_SUBRANGE_H +#define _LIBCPP___ALGORITHM_RANGES_CONTAINS_SUBRANGE_H + +#include <__algorithm/ranges_starts_with.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__functional/reference_wrapper.h> +#include <__iterator/concepts.h> +#include <__iterator/distance.h> +#include <__iterator/indirectly_comparable.h> +#include <__iterator/projected.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 >= 23 + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __contains_subrange { +struct __fn { + template <input_iterator _Iter1, + sentinel_for<_Iter1> _Sent1, + input_iterator _Iter2, + sentinel_for<_Iter2> _Sent2, + class _Pred, + class _Proj1, + class _Proj2, + class _Offset> + static _LIBCPP_HIDE_FROM_ABI constexpr bool __contains_subrange_fn_impl( + _Iter1 __first1, + _Sent1 __last1, + _Iter2 __first2, + _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + _Offset __offset) { + if (__offset < 0) + return false; + else { + for (; __offset >= 0; __offset--, __first1++) { + auto result = ranges::starts_with( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::ref(__pred), + std::ref(__proj1), + std::ref(__proj2)); + if (result) + return true; + } + return false; + } + } + + template <input_iterator _Iter1, + sentinel_for<_Iter1> _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 { + auto __n1 = ranges::distance(__first1, __last1); + auto __n2 = ranges::distance(__first2, __last2); + auto __offset = __n1 - __n2; + + return __contains_subrange_fn_impl( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + __pred, + __proj1, + __proj2, + std::move(__offset)); + } + + template <input_range _Range1, + input_range _Range2, + class _Pred = ranges::equal_to, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_comparable<iterator_t<_Range1>, 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 { + auto __n1 = 0; + auto __n2 = 0; + + if constexpr (sized_range<_Range1> && sized_range<_Range2>) { + __n1 = ranges::size(__range1); + __n2 = ranges::size(__range2); + } else { + __n1 = ranges::distance(ranges::begin(__range1), ranges::end(__range1)); + __n2 = ranges::distance(ranges::begin(__range2), ranges::end(__range2)); + } + + auto __offset = __n1 - __n2; + return __contains_subrange_fn_impl( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + __pred, + __proj1, + __proj2, + __offset); + } +}; +} // namespace __contains_subrange + +inline namespace __cpo { +inline constexpr auto contains_subrange = __contains_subrange::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER >= 23 + +#endif // _LIBCPP___ALGORITHM_RANGES_CONTAINS_SUBRANGE_H \ No newline at end of file diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 1176602a2b6951..7c490ef40ac5f8 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -217,6 +217,19 @@ namespace ranges { constexpr ranges::minmax_element_result<borrowed_iterator_t<R>> minmax_element(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, + sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, + class Proj2 = identity> + requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> + constexpr bool ranges::contains_subrange(I1 first1, S1 last1, I2 first2, + S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++23 + + template<forward_range R1, forward_range R2, + class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> + requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> + constexpr bool ranges::contains_subrange(R1&& r1, R2&& r2, Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++23 + template<class I, class O> using copy_result = in_out_result<I, O>; // since C++20 @@ -1875,6 +1888,7 @@ template <class BidirectionalIterator, class Compare> #include <__algorithm/ranges_binary_search.h> #include <__algorithm/ranges_clamp.h> #include <__algorithm/ranges_contains.h> +#include <__algorithm/ranges_contains_subrange.h> #include <__algorithm/ranges_copy.h> #include <__algorithm/ranges_copy_backward.h> #include <__algorithm/ranges_copy_if.h> 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 index e96a57f4005e04..cc031867b908a3 100644 --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -86,6 +86,8 @@ constexpr bool all_the_algorithms() assert(copies == 0); (void)std::ranges::contains(a, value, Proj(&copies)); assert(copies == 0); + (void)std::ranges::contains_subrange(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::contains_subrange(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); #endif (void)std::ranges::count(first, last, value, Proj(&copies)); assert(copies == 0); (void)std::ranges::count(a, value, Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp new file mode 100644 index 00000000000000..fd4d858b255db7 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp @@ -0,0 +1,293 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// <algorithm> + +// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 +// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000 + +// template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity> +// requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> +// constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {}); // since C++23 + +// template<input_range R, class T, class Proj = identity> +// requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> +// constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {}); // since C++23 + +#include <algorithm> +#include <array> +#include <cassert> +#include <ranges> +#include <vector> + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +struct NotEqualityComparable {}; + +template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2> +concept HasContainsSubrangeSubrangeIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { + std::ranges::contains_subrange(first1, last1, first2, last2); +}; + +static_assert(HasContainsSubrangeSubrangeIt<int*>); +static_assert(!HasContainsSubrangeSubrangeIt<NotEqualityComparable*>); +static_assert(!HasContainsSubrangeSubrangeIt<InputIteratorNotDerivedFrom>); +static_assert(!HasContainsSubrangeSubrangeIt<InputIteratorNotIndirectlyReadable>); +static_assert(!HasContainsSubrangeSubrangeIt<InputIteratorNotInputOrOutputIterator>); +static_assert(!HasContainsSubrangeSubrangeIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>); +static_assert(!HasContainsSubrangeSubrangeIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>); +static_assert(!HasContainsSubrangeSubrangeIt<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>); + +static_assert(!HasContainsSubrangeSubrangeIt<int*, int>); +static_assert(!HasContainsSubrangeSubrangeIt<int, int*>); +static_assert(HasContainsSubrangeSubrangeIt<int*, int*>); + +template <class Range1, class Range2 = UncheckedRange<int*>> +concept HasContainsSubrangeR = requires(Range1&& range1, Range2&& range2) { + std::ranges::contains_subrange(std::forward<Range1>(range1), std::forward<Range2>(range2)); }; + +static_assert(HasContainsSubrangeR<UncheckedRange<int*>>); +static_assert(HasContainsSubrangeR<ForwardRangeNotDerivedFrom>); +static_assert(!HasContainsSubrangeR<ForwardIteratorNotIncrementable>); +static_assert(!HasContainsSubrangeR<ForwardRangeNotSentinelSemiregular>); +static_assert(!HasContainsSubrangeR<ForwardRangeNotSentinelEqualityComparableWith>); +static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable +static_assert(HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>); +static_assert(HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotIncrementable>); +static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>); +static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>); + +static std::vector<int> comparable_data; + +template <class Iter1, class Sent1 = Iter1, class Iter2, class Sent2 = Iter2> +constexpr void test_iterators() { + { // simple tests + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4, 5}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + { + [[maybe_unused]] std::same_as<bool> decltype(auto) ret = + std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(ret); + } + { + [[maybe_unused]] std::same_as<bool> decltype(auto) ret = + std::ranges::contains_subrange(whole, subrange); + assert(ret); + } + } + + { // no match + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(!ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(!ret); + } + } + + { // range consists of just one element + int a[] = {3}; + int p[] = {3, 4, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 1))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(!ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(!ret); + } + } + + { // subrange consists of just one element + int a[] = {23, 1, 20, 3, 54, 2}; + int p[] = {3}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(ret); + } + } + + { // range has zero length + int a[] = {}; + int p[] = {3, 4, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(!ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(!ret); + } + } + + { // subrange has zero length + int a[] = {3, 4, 2}; + int p[] = {}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(ret); + } + } + + { // range and subrange are identical + int a[] = {3, 4, 11, 32, 54, 2}; + int p[] = {3, 4, 11, 32, 54, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 6))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(ret); + } + } + + { // subrange is longer than range + int a[] = {3, 4, 2}; + int p[] = {23, 3, 4, 2, 11, 32, 54, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(!ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(!ret); + } + } + + { // subrange is subsequence + int a[] = {23, 1, 0, 54, 2}; + int p[] = {1, 0, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(!ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(!ret); + } + } + + { // repeated subrange + int a[] = {23, 1, 0, 2, 54, 1, 0, 2, 23, 33}; + int p[] = {1, 0, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 10))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(ret); + } + } + + { // check that the predicate is used + int a[] = {23, 81, 61, 0, 42, 25, 1, 2, 1, 29, 2}; + int p[] = {-1, -2, -1}; + auto pred = [](int l, int r) { return l * -1 == r; }; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 11))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end(), pred); + assert(ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange, pred); + assert(ret); + } + } + + { // check that the projections are used + int a[] = {1, 3, 15, 1, 2, 1, 8}; + int p[] = {2, 1, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 7))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end(), {}, + [](int i) { return i - 3; }, + [](int i) { return i * -1; }); + assert(ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange, {}, + [](int i) { return i - 3; }, + [](int i) { return i * -1; }); + assert(ret); + } + } + + { // check the nodiscard extension + // use #pragma around to suppress error: ignoring return value of function + // declared with 'nodiscard' attribute [-Werror,-Wunused-result] + #pragma clang diagnostic push + #pragma clang diagnostic ignored "-Wunused-result" + int a[] = {1, 9, 0, 13, 25}; + int p[] = {1, 9, 0}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + std::ranges::contains_subrange(whole, subrange); + #pragma clang diagnostic pop + } +} + +constexpr bool test() { + types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter2>() { + types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter1>() { + if constexpr (std::forward_iterator<Iter1> && std::forward_iterator<Iter2>) + test_iterators<Iter1, Iter1, Iter2, Iter2>(); + if constexpr (std::forward_iterator<Iter2>) + test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, Iter2>(); + if constexpr (std::forward_iterator<Iter1>) + test_iterators<Iter1, Iter1, Iter2, sized_sentinel<Iter2>>(); + test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, sized_sentinel<Iter2>>(); + }); + }); + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} \ No newline at end of file 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 index 494e9fd19c3545..9506ca1c768bd7 100644 --- 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 @@ -67,6 +67,7 @@ static_assert(test(std::ranges::binary_search, a, 42)); static_assert(test(std::ranges::clamp, 42, 42, 42)); #if TEST_STD_VER >= 23 static_assert(test(std::ranges::contains, a, 42)); +static_assert(test(std::ranges::contains_subrange, a, a)); #endif static_assert(test(std::ranges::copy, a, a)); static_assert(test(std::ranges::copy_backward, a, a)); >From 5a1d555e0cdf070ee415e9c1b1e8c928d79e4d71 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Wed, 20 Sep 2023 18:41:04 -0700 Subject: [PATCH 02/15] format --- libcxx/include/__algorithm/ranges_contains_subrange.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libcxx/include/__algorithm/ranges_contains_subrange.h b/libcxx/include/__algorithm/ranges_contains_subrange.h index 16de6c29cb2a1a..f8e885d3259be6 100644 --- a/libcxx/include/__algorithm/ranges_contains_subrange.h +++ b/libcxx/include/__algorithm/ranges_contains_subrange.h @@ -129,7 +129,7 @@ struct __fn { __proj1, __proj2, __offset); - } + } }; } // namespace __contains_subrange >From 7cb4d06f6c801a52e239f5f2a780001f73c25e30 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Thu, 21 Sep 2023 11:06:02 -0700 Subject: [PATCH 03/15] Add a newline --- libcxx/include/__algorithm/ranges_contains_subrange.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libcxx/include/__algorithm/ranges_contains_subrange.h b/libcxx/include/__algorithm/ranges_contains_subrange.h index f8e885d3259be6..8fdd460c8d6f34 100644 --- a/libcxx/include/__algorithm/ranges_contains_subrange.h +++ b/libcxx/include/__algorithm/ranges_contains_subrange.h @@ -142,4 +142,4 @@ _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP_STD_VER >= 23 -#endif // _LIBCPP___ALGORITHM_RANGES_CONTAINS_SUBRANGE_H \ No newline at end of file +#endif // _LIBCPP___ALGORITHM_RANGES_CONTAINS_SUBRANGE_H >From aee12dd713093aad9f8b1e7b8281f50235047982 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Tue, 26 Sep 2023 16:56:38 -0700 Subject: [PATCH 04/15] 1. call distance(r) directly 2. replace auto with int to avoid potential errors --- .../__algorithm/ranges_contains_subrange.h | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) diff --git a/libcxx/include/__algorithm/ranges_contains_subrange.h b/libcxx/include/__algorithm/ranges_contains_subrange.h index 8fdd460c8d6f34..6dd8324c5dfa69 100644 --- a/libcxx/include/__algorithm/ranges_contains_subrange.h +++ b/libcxx/include/__algorithm/ranges_contains_subrange.h @@ -40,7 +40,7 @@ struct __fn { class _Pred, class _Proj1, class _Proj2, - class _Offset> + class _Offset = int> static _LIBCPP_HIDE_FROM_ABI constexpr bool __contains_subrange_fn_impl( _Iter1 __first1, _Sent1 __last1, @@ -85,9 +85,9 @@ struct __fn { _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { - auto __n1 = ranges::distance(__first1, __last1); - auto __n2 = ranges::distance(__first2, __last2); - auto __offset = __n1 - __n2; + int __n1 = ranges::distance(__first1, __last1); + int __n2 = ranges::distance(__first2, __last2); + int __offset = __n1 - __n2; return __contains_subrange_fn_impl( std::move(__first1), @@ -108,18 +108,18 @@ struct __fn { requires indirectly_comparable<iterator_t<_Range1>, 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 { - auto __n1 = 0; - auto __n2 = 0; + int __n1 = 0; + int __n2 = 0; if constexpr (sized_range<_Range1> && sized_range<_Range2>) { __n1 = ranges::size(__range1); __n2 = ranges::size(__range2); } else { - __n1 = ranges::distance(ranges::begin(__range1), ranges::end(__range1)); - __n2 = ranges::distance(ranges::begin(__range2), ranges::end(__range2)); + __n1 = ranges::distance(__range1); + __n2 = ranges::distance(__range2); } - auto __offset = __n1 - __n2; + int __offset = __n1 - __n2; return __contains_subrange_fn_impl( ranges::begin(__range1), ranges::end(__range1), >From b2c57a20557fd7d7af15eafc0a11ba6bd4c3a333 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Sun, 1 Oct 2023 22:41:08 -0700 Subject: [PATCH 05/15] Reformat --- .../ranges.contains_subrange.pass.cpp | 115 +++++++++--------- 1 file changed, 59 insertions(+), 56 deletions(-) diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp index fd4d858b255db7..172c30ad8b979c 100644 --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp @@ -51,7 +51,7 @@ static_assert(HasContainsSubrangeSubrangeIt<int*, int*>); template <class Range1, class Range2 = UncheckedRange<int*>> concept HasContainsSubrangeR = requires(Range1&& range1, Range2&& range2) { - std::ranges::contains_subrange(std::forward<Range1>(range1), std::forward<Range2>(range2)); }; + std::ranges::contains_subrange(std::forward<Range1>(range1), std::forward<Range2>(range2)); }; static_assert(HasContainsSubrangeR<UncheckedRange<int*>>); static_assert(HasContainsSubrangeR<ForwardRangeNotDerivedFrom>); @@ -69,26 +69,25 @@ static std::vector<int> comparable_data; template <class Iter1, class Sent1 = Iter1, class Iter2, class Sent2 = Iter2> constexpr void test_iterators() { { // simple tests - int a[] = {1, 2, 3, 4, 5, 6}; - int p[] = {3, 4, 5}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4, 5}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); { [[maybe_unused]] std::same_as<bool> decltype(auto) ret = - std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); assert(ret); } { - [[maybe_unused]] std::same_as<bool> decltype(auto) ret = - std::ranges::contains_subrange(whole, subrange); + [[maybe_unused]] std::same_as<bool> decltype(auto) ret = std::ranges::contains_subrange(whole, subrange); assert(ret); } } { // no match - int a[] = {1, 2, 3, 4, 5, 6}; - int p[] = {3, 4, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); @@ -101,9 +100,9 @@ constexpr void test_iterators() { } { // range consists of just one element - int a[] = {3}; - int p[] = {3, 4, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 1))); + int a[] = {3}; + int p[] = {3, 4, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 1))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); @@ -116,9 +115,9 @@ constexpr void test_iterators() { } { // subrange consists of just one element - int a[] = {23, 1, 20, 3, 54, 2}; - int p[] = {3}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + int a[] = {23, 1, 20, 3, 54, 2}; + int p[] = {3}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); @@ -131,9 +130,9 @@ constexpr void test_iterators() { } { // range has zero length - int a[] = {}; - int p[] = {3, 4, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); + int a[] = {}; + int p[] = {3, 4, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); @@ -146,9 +145,9 @@ constexpr void test_iterators() { } { // subrange has zero length - int a[] = {3, 4, 2}; - int p[] = {}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + int a[] = {3, 4, 2}; + int p[] = {}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); @@ -161,9 +160,9 @@ constexpr void test_iterators() { } { // range and subrange are identical - int a[] = {3, 4, 11, 32, 54, 2}; - int p[] = {3, 4, 11, 32, 54, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + int a[] = {3, 4, 11, 32, 54, 2}; + int p[] = {3, 4, 11, 32, 54, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 6))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); @@ -176,9 +175,9 @@ constexpr void test_iterators() { } { // subrange is longer than range - int a[] = {3, 4, 2}; - int p[] = {23, 3, 4, 2, 11, 32, 54, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + int a[] = {3, 4, 2}; + int p[] = {23, 3, 4, 2, 11, 32, 54, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); @@ -191,9 +190,9 @@ constexpr void test_iterators() { } { // subrange is subsequence - int a[] = {23, 1, 0, 54, 2}; - int p[] = {1, 0, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + int a[] = {23, 1, 0, 54, 2}; + int p[] = {1, 0, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); @@ -206,9 +205,9 @@ constexpr void test_iterators() { } { // repeated subrange - int a[] = {23, 1, 0, 2, 54, 1, 0, 2, 23, 33}; - int p[] = {1, 0, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 10))); + int a[] = {23, 1, 0, 2, 54, 1, 0, 2, 23, 33}; + int p[] = {1, 0, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 10))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); @@ -221,10 +220,10 @@ constexpr void test_iterators() { } { // check that the predicate is used - int a[] = {23, 81, 61, 0, 42, 25, 1, 2, 1, 29, 2}; - int p[] = {-1, -2, -1}; - auto pred = [](int l, int r) { return l * -1 == r; }; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 11))); + int a[] = {23, 81, 61, 0, 42, 25, 1, 2, 1, 29, 2}; + int p[] = {-1, -2, -1}; + auto pred = [](int l, int r) { return l * -1 == r; }; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 11))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end(), pred); @@ -237,40 +236,44 @@ constexpr void test_iterators() { } { // check that the projections are used - int a[] = {1, 3, 15, 1, 2, 1, 8}; - int p[] = {2, 1, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 7))); + int a[] = {1, 3, 15, 1, 2, 1, 8}; + int p[] = {2, 1, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 7))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); { - bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end(), {}, - [](int i) { return i - 3; }, - [](int i) { return i * -1; }); + bool ret = std::ranges::contains_subrange( + whole.begin(), + whole.end(), + subrange.begin(), + subrange.end(), + {}, + [](int i) { return i - 3; }, + [](int i) { return i * -1; }); assert(ret); } { - bool ret = std::ranges::contains_subrange(whole, subrange, {}, - [](int i) { return i - 3; }, - [](int i) { return i * -1; }); + bool ret = std::ranges::contains_subrange( + whole, subrange, {}, [](int i) { return i - 3; }, [](int i) { return i * -1; }); assert(ret); } } { // check the nodiscard extension - // use #pragma around to suppress error: ignoring return value of function - // declared with 'nodiscard' attribute [-Werror,-Wunused-result] - #pragma clang diagnostic push - #pragma clang diagnostic ignored "-Wunused-result" - int a[] = {1, 9, 0, 13, 25}; - int p[] = {1, 9, 0}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); +// use #pragma around to suppress error: ignoring return value of function +// declared with 'nodiscard' attribute [-Werror,-Wunused-result] +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wunused-result" + int a[] = {1, 9, 0, 13, 25}; + int p[] = {1, 9, 0}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); std::ranges::contains_subrange(whole, subrange); - #pragma clang diagnostic pop +#pragma clang diagnostic pop } } constexpr bool test() { - types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter2>() { + types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter2>() { types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter1>() { if constexpr (std::forward_iterator<Iter1> && std::forward_iterator<Iter2>) test_iterators<Iter1, Iter1, Iter2, Iter2>(); >From ae96c2f72baaddc9dd121cd645b15b45a44c23a6 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Mon, 2 Oct 2023 17:45:39 -0700 Subject: [PATCH 06/15] Correct input type and call ranges::search() --- .../__algorithm/ranges_contains_subrange.h | 40 ++++++------ .../ranges.contains_subrange.pass.cpp | 65 ++++++++++--------- 2 files changed, 56 insertions(+), 49 deletions(-) diff --git a/libcxx/include/__algorithm/ranges_contains_subrange.h b/libcxx/include/__algorithm/ranges_contains_subrange.h index 6dd8324c5dfa69..d4fcb8c08a24aa 100644 --- a/libcxx/include/__algorithm/ranges_contains_subrange.h +++ b/libcxx/include/__algorithm/ranges_contains_subrange.h @@ -9,7 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_CONTAINS_SUBRANGE_H #define _LIBCPP___ALGORITHM_RANGES_CONTAINS_SUBRANGE_H -#include <__algorithm/ranges_starts_with.h> +#include <__algorithm/ranges_search.h> #include <__config> #include <__functional/identity.h> #include <__functional/ranges_operations.h> @@ -33,9 +33,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD namespace ranges { namespace __contains_subrange { struct __fn { - template <input_iterator _Iter1, + template <forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, - input_iterator _Iter2, + forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, class _Pred, class _Proj1, @@ -53,25 +53,21 @@ struct __fn { if (__offset < 0) return false; else { - for (; __offset >= 0; __offset--, __first1++) { - auto result = ranges::starts_with( - std::move(__first1), - std::move(__last1), - std::move(__first2), - std::move(__last2), - std::ref(__pred), - std::ref(__proj1), - std::ref(__proj2)); - if (result) - return true; - } - return false; + auto result = ranges::search( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::ref(__pred), + std::ref(__proj1), + std::ref(__proj2)); + return result.empty() == false; } } - template <input_iterator _Iter1, + template <forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, - input_iterator _Iter2, + forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, class _Pred = ranges::equal_to, class _Proj1 = identity, @@ -87,6 +83,8 @@ struct __fn { _Proj2 __proj2 = {}) const { int __n1 = ranges::distance(__first1, __last1); int __n2 = ranges::distance(__first2, __last2); + if (__n2 == 0) + return true; int __offset = __n1 - __n2; return __contains_subrange_fn_impl( @@ -100,8 +98,8 @@ struct __fn { std::move(__offset)); } - template <input_range _Range1, - input_range _Range2, + template <forward_range _Range1, + forward_range _Range2, class _Pred = ranges::equal_to, class _Proj1 = identity, class _Proj2 = identity> @@ -119,6 +117,8 @@ struct __fn { __n2 = ranges::distance(__range2); } + if (__n2 == 0) + return true; int __offset = __n1 - __n2; return __contains_subrange_fn_impl( ranges::begin(__range1), diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp index 172c30ad8b979c..0b7a2359b2b666 100644 --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp @@ -32,40 +32,36 @@ struct NotEqualityComparable {}; template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2> -concept HasContainsSubrangeSubrangeIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { +concept HasContainsSubrangeIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { std::ranges::contains_subrange(first1, last1, first2, last2); }; -static_assert(HasContainsSubrangeSubrangeIt<int*>); -static_assert(!HasContainsSubrangeSubrangeIt<NotEqualityComparable*>); -static_assert(!HasContainsSubrangeSubrangeIt<InputIteratorNotDerivedFrom>); -static_assert(!HasContainsSubrangeSubrangeIt<InputIteratorNotIndirectlyReadable>); -static_assert(!HasContainsSubrangeSubrangeIt<InputIteratorNotInputOrOutputIterator>); -static_assert(!HasContainsSubrangeSubrangeIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>); -static_assert(!HasContainsSubrangeSubrangeIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>); -static_assert(!HasContainsSubrangeSubrangeIt<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>); - -static_assert(!HasContainsSubrangeSubrangeIt<int*, int>); -static_assert(!HasContainsSubrangeSubrangeIt<int, int*>); -static_assert(HasContainsSubrangeSubrangeIt<int*, int*>); +static_assert(HasContainsSubrangeIt<int*>); +static_assert(!HasContainsSubrangeIt<ForwardIteratorNotDerivedFrom>); +static_assert(!HasContainsSubrangeIt<ForwardIteratorNotIncrementable>); +static_assert(!HasContainsSubrangeIt<int*, SentinelForNotSemiregular>); +static_assert(!HasContainsSubrangeIt<int*, int*, int**>); // not indirectly comparable +static_assert(!HasContainsSubrangeIt<int*, SentinelForNotWeaklyEqualityComparableWith>); +static_assert(!HasContainsSubrangeIt<int*, int*, ForwardIteratorNotDerivedFrom>); +static_assert(!HasContainsSubrangeIt<int*, int*, ForwardIteratorNotIncrementable>); +static_assert(!HasContainsSubrangeIt<int*, int*, int*, SentinelForNotSemiregular>); +static_assert(!HasContainsSubrangeIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>); template <class Range1, class Range2 = UncheckedRange<int*>> concept HasContainsSubrangeR = requires(Range1&& range1, Range2&& range2) { std::ranges::contains_subrange(std::forward<Range1>(range1), std::forward<Range2>(range2)); }; static_assert(HasContainsSubrangeR<UncheckedRange<int*>>); -static_assert(HasContainsSubrangeR<ForwardRangeNotDerivedFrom>); +static_assert(!HasContainsSubrangeR<ForwardRangeNotDerivedFrom>); static_assert(!HasContainsSubrangeR<ForwardIteratorNotIncrementable>); static_assert(!HasContainsSubrangeR<ForwardRangeNotSentinelSemiregular>); static_assert(!HasContainsSubrangeR<ForwardRangeNotSentinelEqualityComparableWith>); static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable -static_assert(HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>); -static_assert(HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotIncrementable>); +static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>); +static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotIncrementable>); static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>); static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>); -static std::vector<int> comparable_data; - template <class Iter1, class Sent1 = Iter1, class Iter2, class Sent2 = Iter2> constexpr void test_iterators() { { // simple tests @@ -272,18 +268,29 @@ constexpr void test_iterators() { } } +template <class Iter1, class Sent1 = Iter1> +constexpr void test_iterators2() { + test_iterators<Iter1, Sent1, forward_iterator<int*>>(); + test_iterators<Iter1, Sent1, forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>(); + test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>(); + test_iterators<Iter1, Sent1, bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>(); + test_iterators<Iter1, Sent1, random_access_iterator<int*>>(); + test_iterators<Iter1, Sent1, random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>(); + test_iterators<Iter1, Sent1, contiguous_iterator<int*>>(); + test_iterators<Iter1, Sent1, contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>(); + test_iterators<Iter1, Sent1, int*>(); +} + constexpr bool test() { - types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter2>() { - types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter1>() { - if constexpr (std::forward_iterator<Iter1> && std::forward_iterator<Iter2>) - test_iterators<Iter1, Iter1, Iter2, Iter2>(); - if constexpr (std::forward_iterator<Iter2>) - test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, Iter2>(); - if constexpr (std::forward_iterator<Iter1>) - test_iterators<Iter1, Iter1, Iter2, sized_sentinel<Iter2>>(); - test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, sized_sentinel<Iter2>>(); - }); - }); + test_iterators2<forward_iterator<int*>>(); + test_iterators2<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>(); + test_iterators2<bidirectional_iterator<int*>>(); + test_iterators2<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>(); + test_iterators2<random_access_iterator<int*>>(); + test_iterators2<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>(); + test_iterators2<contiguous_iterator<int*>>(); + test_iterators2<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>(); + test_iterators2<int*>(); return true; } >From 11384e6c94e5e297050dd1b4beace6e628caebb2 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Wed, 3 Jan 2024 19:00:40 -0800 Subject: [PATCH 07/15] 1. update function 2. add nondiscard tests --- libcxx/include/__algorithm/ranges_contains_subrange.h | 2 +- .../diagnostics/ranges.nodiscard_extensions.compile.pass.cpp | 2 ++ .../libcxx/diagnostics/ranges.nodiscard_extensions.verify.cpp | 4 ++++ 3 files changed, 7 insertions(+), 1 deletion(-) diff --git a/libcxx/include/__algorithm/ranges_contains_subrange.h b/libcxx/include/__algorithm/ranges_contains_subrange.h index d4fcb8c08a24aa..23c5ea767de114 100644 --- a/libcxx/include/__algorithm/ranges_contains_subrange.h +++ b/libcxx/include/__algorithm/ranges_contains_subrange.h @@ -61,7 +61,7 @@ struct __fn { std::ref(__pred), std::ref(__proj1), std::ref(__proj2)); - return result.empty() == false; + return !result.empty(); } } diff --git a/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.compile.pass.cpp b/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.compile.pass.cpp index 7e2d64b8c9b618..790260d209a95d 100644 --- a/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.compile.pass.cpp +++ b/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.compile.pass.cpp @@ -28,6 +28,8 @@ void test() { std::ranges::binary_search(range, 1); std::ranges::binary_search(iter, iter, 1); std::ranges::clamp(1, 2, 3); + std::ranges::contains_subrange(range, range); + std::ranges::contains_subrange(iter, iter, iter, iter); std::ranges::count_if(range, pred); std::ranges::count_if(iter, iter, pred); std::ranges::count(range, 1); diff --git a/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.verify.cpp b/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.verify.cpp index f0a0e4889a7603..c41461fff516fa 100644 --- a/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.verify.cpp +++ b/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.verify.cpp @@ -91,6 +91,10 @@ void test() { std::ranges::upper_bound(iter, iter, 1); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}} #if TEST_STD_VER >= 23 + std::ranges::contains_subrange(range, range); + // expected-warning@-1 {{ignoring return value of function declared with 'nodiscard' attribute}} + std::ranges::contains_subrange(iter, iter, iter, iter); + // expected-warning@-1 {{ignoring return value of function declared with 'nodiscard' attribute}} std::ranges::fold_left(range, 0, std::plus()); // expected-warning@-1{{ignoring return value of function declared with 'nodiscard' attribute}} std::ranges::fold_left(iter, iter, 0, std::plus()); >From 2973c85802f8d265a943f024bfca16d64dc8f240 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Thu, 4 Jan 2024 18:39:42 -0800 Subject: [PATCH 08/15] update code --- libcxx/include/algorithm | 16 +-- .../ranges.contains_subrange.pass.cpp | 105 ++++++++---------- 2 files changed, 55 insertions(+), 66 deletions(-) diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 7c490ef40ac5f8..70e30bc87e8128 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -217,18 +217,18 @@ namespace ranges { constexpr ranges::minmax_element_result<borrowed_iterator_t<R>> minmax_element(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 - template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, - sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, - class Proj2 = identity> + template<forward_iterator I1, sentinel_for<I1> S1, + forward_iterator I2, sentinel_for<I2> S2, + class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> - constexpr bool ranges::contains_subrange(I1 first1, S1 last1, I2 first2, - S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++23 + constexpr bool contains_subrange(I1 first1, S1 last1, I2 first2, S2 last2, + Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++23 template<forward_range R1, forward_range R2, - class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> + class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> - constexpr bool ranges::contains_subrange(R1&& r1, R2&& r2, Pred pred = {}, - Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++23 + constexpr bool contains_subrange(R1&& r1, R2&& r2, Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++23 template<class I, class O> using copy_result = in_out_result<I, O>; // since C++20 diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp index 0b7a2359b2b666..89701c1c2487dd 100644 --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp @@ -11,22 +11,25 @@ // UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 // ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000 -// template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity> -// requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> -// constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {}); // since C++23 +// template<forward_iterator I1, sentinel_for<I1> S1, +// forward_iterator I2, sentinel_for<I2> S2, class Proj = identity> +// requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> +// constexpr bool ranges::contains_subrange(I1 first1, S1 last1, I2 first2, S2 last2, +// Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++23 -// template<input_range R, class T, class Proj = identity> -// requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> -// constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {}); // since C++23 +// template<forward_range R1, forward_range R2, +// class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> +// requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> +// constexpr bool ranges::contains_subrange(R1&& r1, R2&& r2, Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++23 #include <algorithm> -#include <array> #include <cassert> +#include <concepts> #include <ranges> -#include <vector> +#include <utility> #include "almost_satisfies_types.h" -#include "boolean_testable.h" #include "test_iterators.h" struct NotEqualityComparable {}; @@ -67,15 +70,15 @@ constexpr void test_iterators() { { // simple tests int a[] = {1, 2, 3, 4, 5, 6}; int p[] = {3, 4, 5}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); { - [[maybe_unused]] std::same_as<bool> decltype(auto) ret = + std::same_as<bool> decltype(auto) ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); assert(ret); } { - [[maybe_unused]] std::same_as<bool> decltype(auto) ret = std::ranges::contains_subrange(whole, subrange); + std::same_as<bool> decltype(auto) ret = std::ranges::contains_subrange(whole, subrange); assert(ret); } } @@ -83,8 +86,8 @@ constexpr void test_iterators() { { // no match int a[] = {1, 2, 3, 4, 5, 6}; int p[] = {3, 4, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); assert(!ret); @@ -98,8 +101,8 @@ constexpr void test_iterators() { { // range consists of just one element int a[] = {3}; int p[] = {3, 4, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 1))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); assert(!ret); @@ -113,8 +116,8 @@ constexpr void test_iterators() { { // subrange consists of just one element int a[] = {23, 1, 20, 3, 54, 2}; int p[] = {3}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); assert(ret); @@ -129,7 +132,7 @@ constexpr void test_iterators() { int a[] = {}; int p[] = {3, 4, 2}; auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); assert(!ret); @@ -143,7 +146,7 @@ constexpr void test_iterators() { { // subrange has zero length int a[] = {3, 4, 2}; int p[] = {}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); @@ -158,8 +161,8 @@ constexpr void test_iterators() { { // range and subrange are identical int a[] = {3, 4, 11, 32, 54, 2}; int p[] = {3, 4, 11, 32, 54, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 6))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); assert(ret); @@ -173,8 +176,8 @@ constexpr void test_iterators() { { // subrange is longer than range int a[] = {3, 4, 2}; int p[] = {23, 3, 4, 2, 11, 32, 54, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); assert(!ret); @@ -188,8 +191,8 @@ constexpr void test_iterators() { { // subrange is subsequence int a[] = {23, 1, 0, 54, 2}; int p[] = {1, 0, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); assert(!ret); @@ -203,8 +206,8 @@ constexpr void test_iterators() { { // repeated subrange int a[] = {23, 1, 0, 2, 54, 1, 0, 2, 23, 33}; int p[] = {1, 0, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 10))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); assert(ret); @@ -219,8 +222,8 @@ constexpr void test_iterators() { int a[] = {23, 81, 61, 0, 42, 25, 1, 2, 1, 29, 2}; int p[] = {-1, -2, -1}; auto pred = [](int l, int r) { return l * -1 == r; }; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 11))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); { bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end(), pred); assert(ret); @@ -234,8 +237,8 @@ constexpr void test_iterators() { { // check that the projections are used int a[] = {1, 3, 15, 1, 2, 1, 8}; int p[] = {2, 1, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 7))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); { bool ret = std::ranges::contains_subrange( whole.begin(), @@ -261,36 +264,22 @@ constexpr void test_iterators() { #pragma clang diagnostic ignored "-Wunused-result" int a[] = {1, 9, 0, 13, 25}; int p[] = {1, 9, 0}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); std::ranges::contains_subrange(whole, subrange); #pragma clang diagnostic pop } } -template <class Iter1, class Sent1 = Iter1> -constexpr void test_iterators2() { - test_iterators<Iter1, Sent1, forward_iterator<int*>>(); - test_iterators<Iter1, Sent1, forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>(); - test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>(); - test_iterators<Iter1, Sent1, bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>(); - test_iterators<Iter1, Sent1, random_access_iterator<int*>>(); - test_iterators<Iter1, Sent1, random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>(); - test_iterators<Iter1, Sent1, contiguous_iterator<int*>>(); - test_iterators<Iter1, Sent1, contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>(); - test_iterators<Iter1, Sent1, int*>(); -} - constexpr bool test() { - test_iterators2<forward_iterator<int*>>(); - test_iterators2<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>(); - test_iterators2<bidirectional_iterator<int*>>(); - test_iterators2<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>(); - test_iterators2<random_access_iterator<int*>>(); - test_iterators2<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>(); - test_iterators2<contiguous_iterator<int*>>(); - test_iterators2<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>(); - test_iterators2<int*>(); + types::for_each(types::forward_iterator_list<int*>{}, []<class Iter1> { + types::for_each(types::forward_iterator_list<int*>{}, []<class Iter2> { + test_iterators<Iter1, Iter1, Iter2, Iter2>(); + test_iterators<Iter1, Iter1, Iter2, sized_sentinel<Iter2>>(); + test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, Iter2>(); + test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, sized_sentinel<Iter2>>(); + }); + }); return true; } @@ -300,4 +289,4 @@ int main(int, char**) { static_assert(test()); return 0; -} \ No newline at end of file +} >From b0f9bac17a5a200c77aa7d5207b4c0b252c92bdf Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Thu, 4 Jan 2024 18:39:42 -0800 Subject: [PATCH 09/15] update code --- libcxx/docs/Status/RangesAlgorithms.csv | 6 +- .../__algorithm/ranges_contains_subrange.h | 83 ++++--------------- libcxx/modules/std/algorithm.inc | 2 - 3 files changed, 17 insertions(+), 74 deletions(-) diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv index 2fe530bf75fd94..419bf58d683217 100644 --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -3,13 +3,13 @@ C++20,all C++20 algorithms,N/A,N/A,✅ C++23,`find_last <https://wg21.link/P1223R5>`_,Unassigned,No patch yet,Not started C++23,`find_last_if <https://wg21.link/P1223R5>`_,Unassigned,No patch yet,Not started C++23,`find_last_if_not <https://wg21.link/P1223R5>`_,Unassigned,No patch yet,Not started -C++23,`starts_with <https://wg21.link/P1659R3>`_,Zijun Zhao,`D150735 <https://llvm.org/D150735>`_,✅ -C++23,`ends_with <https://wg21.link/P1659R3>`_,Zijun Zhao,No patch yet,In Progress +C++23,`starts_with <https://wg21.link/P1659R3>`_,Zijun Zhao,`D150735 <https://llvm.org/D150735>`_,Complete +C++23,`ends_with <https://wg21.link/P1659R3>`_,Zijun Zhao,N/A,Complete C++23,`shift_left <https://wg21.link/p2440r1>`_,Unassigned,No patch yet,Not started C++23,`shift_right <https://wg21.link/p2440r1>`_,Unassigned,No patch yet,Not started C++23,`iota (algorithm) <https://wg21.link/p2440r1>`_,Unassigned,No patch yet,Not started C++23,`fold <https://wg21.link/p2322r5>`_,Unassigned,No patch yet,Not started -C++23,`contains <https://wg21.link/p2302r2>`_,Zijun Zhao,No patch yet,In Progress +C++23,`contains <https://wg21.link/p2302r2>`_,Zijun Zhao,N/A,Complete C++23,`fold_left_with_iter <https://wg21.link/p2322r6>`_,Christopher Di Bella,N/A,Complete C++23,`fold_left <https://wg21.link/p2322r6>`_,Christopher Di Bella,N/A,Complete C++23,`fold_left_first_with_iter <https://wg21.link/p2322r6>`_,Christopher Di Bella,N/A,In progress diff --git a/libcxx/include/__algorithm/ranges_contains_subrange.h b/libcxx/include/__algorithm/ranges_contains_subrange.h index 23c5ea767de114..beb4d84f232bab 100644 --- a/libcxx/include/__algorithm/ranges_contains_subrange.h +++ b/libcxx/include/__algorithm/ranges_contains_subrange.h @@ -33,38 +33,6 @@ _LIBCPP_BEGIN_NAMESPACE_STD namespace ranges { namespace __contains_subrange { struct __fn { - template <forward_iterator _Iter1, - sentinel_for<_Iter1> _Sent1, - forward_iterator _Iter2, - sentinel_for<_Iter2> _Sent2, - class _Pred, - class _Proj1, - class _Proj2, - class _Offset = int> - static _LIBCPP_HIDE_FROM_ABI constexpr bool __contains_subrange_fn_impl( - _Iter1 __first1, - _Sent1 __last1, - _Iter2 __first2, - _Sent2 __last2, - _Pred& __pred, - _Proj1& __proj1, - _Proj2& __proj2, - _Offset __offset) { - if (__offset < 0) - return false; - else { - auto result = ranges::search( - std::move(__first1), - std::move(__last1), - std::move(__first2), - std::move(__last2), - std::ref(__pred), - std::ref(__proj1), - std::ref(__proj2)); - return !result.empty(); - } - } - template <forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, forward_iterator _Iter2, @@ -73,29 +41,19 @@ struct __fn { class _Proj1 = identity, class _Proj2 = identity> requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> - _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool operator()( + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool static operator()( _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, _Proj1 __proj1 = {}, - _Proj2 __proj2 = {}) const { - int __n1 = ranges::distance(__first1, __last1); - int __n2 = ranges::distance(__first2, __last2); - if (__n2 == 0) - return true; - int __offset = __n1 - __n2; + _Proj2 __proj2 = {}) { + auto __n2 = ranges::distance(__first2, __last2); + if (__n2 == 0) return true; - return __contains_subrange_fn_impl( - std::move(__first1), - std::move(__last1), - std::move(__first2), - std::move(__last2), - __pred, - __proj1, - __proj2, - std::move(__offset)); + auto ret = ranges::search(std::move(__first1), __last1, std::move(__first2), __last2, __pred, std::ref(__proj1), std::ref(__proj2)); + return ret.empty() == false; } template <forward_range _Range1, @@ -104,31 +62,18 @@ struct __fn { class _Proj1 = identity, class _Proj2 = identity> requires indirectly_comparable<iterator_t<_Range1>, 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 { - int __n1 = 0; - int __n2 = 0; - - if constexpr (sized_range<_Range1> && sized_range<_Range2>) { - __n1 = ranges::size(__range1); + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool static operator()( + _Range1&& __range1, _Range2&& __range2, _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) { + auto __n2 = 0; + if constexpr (sized_range<_Range2>) { __n2 = ranges::size(__range2); } else { - __n1 = ranges::distance(__range1); - __n2 = ranges::distance(__range2); + __n2 = std::distance(cbegin(__range2), cend(__range2)); } + if (__n2 == 0) return true; - if (__n2 == 0) - return true; - int __offset = __n1 - __n2; - return __contains_subrange_fn_impl( - ranges::begin(__range1), - ranges::end(__range1), - ranges::begin(__range2), - ranges::end(__range2), - __pred, - __proj1, - __proj2, - __offset); + auto ret = ranges::search(__range1, __range2, __pred, std::ref(__proj1), std::ref(__proj2)); + return ret.empty() == false; } }; } // namespace __contains_subrange diff --git a/libcxx/modules/std/algorithm.inc b/libcxx/modules/std/algorithm.inc index 75e8a3af78dea2..e7796bfa26af81 100644 --- a/libcxx/modules/std/algorithm.inc +++ b/libcxx/modules/std/algorithm.inc @@ -46,9 +46,7 @@ export namespace std { // [alg.contains], contains namespace ranges { using std::ranges::contains; -#if 0 using std::ranges::contains_subrange; -#endif } // namespace ranges #endif // _LIBCPP_STD_VER >= 23 >From 72d92de43d24b8b32bc50267fd2b473cc2340c2f Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Thu, 4 Jan 2024 18:39:42 -0800 Subject: [PATCH 10/15] update code --- .../ranges.contains_subrange.pass.cpp | 43 +++++++++++++------ 1 file changed, 30 insertions(+), 13 deletions(-) diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp index 89701c1c2487dd..98527901bfe800 100644 --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp @@ -188,6 +188,36 @@ constexpr void test_iterators() { } } + { // subrange is the prefix + int a[] = {3, 43, 5, 100, 433, 278, 6457, 900}; + int p[] = {3, 43, 5}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(ret); + } + } + + { // subrange is the suffix + int a[] = {3, 43, 5, 7, 68, 100, 433, 900}; + int p[] = {100, 433, 900}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(ret); + } + } + { // subrange is subsequence int a[] = {23, 1, 0, 54, 2}; int p[] = {1, 0, 2}; @@ -256,19 +286,6 @@ constexpr void test_iterators() { assert(ret); } } - - { // check the nodiscard extension -// use #pragma around to suppress error: ignoring return value of function -// declared with 'nodiscard' attribute [-Werror,-Wunused-result] -#pragma clang diagnostic push -#pragma clang diagnostic ignored "-Wunused-result" - int a[] = {1, 9, 0, 13, 25}; - int p[] = {1, 9, 0}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); - std::ranges::contains_subrange(whole, subrange); -#pragma clang diagnostic pop - } } constexpr bool test() { >From 65dd43c95f578adf42da750da48e22ebca3ddce0 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Thu, 4 Jan 2024 18:39:42 -0800 Subject: [PATCH 11/15] 1. Call ranges::search() in ranges::contains_subrange() 2. add several test cases: like when both range and subrange are empty 3. reformat 4. nit to fix --- .../ranges.contains_subrange.pass.cpp | 35 ++++++++++++++----- 1 file changed, 26 insertions(+), 9 deletions(-) diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp index 98527901bfe800..cdfd40e8ca8398 100644 --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp @@ -67,7 +67,7 @@ static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotSentine template <class Iter1, class Sent1 = Iter1, class Iter2, class Sent2 = Iter2> constexpr void test_iterators() { - { // simple tests + { // simple tests int a[] = {1, 2, 3, 4, 5, 6}; int p[] = {3, 4, 5}; auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); @@ -158,6 +158,21 @@ constexpr void test_iterators() { } } + { // range and subrange both have zero length + int a[] = {}; + int p[] = {}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(p))); + { + bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end()); + assert(ret); + } + { + bool ret = std::ranges::contains_subrange(whole, subrange); + assert(ret); + } + } + { // range and subrange are identical int a[] = {3, 4, 11, 32, 54, 2}; int p[] = {3, 4, 11, 32, 54, 2}; @@ -218,7 +233,7 @@ constexpr void test_iterators() { } } - { // subrange is subsequence + { // subrange is a subsequence int a[] = {23, 1, 0, 54, 2}; int p[] = {1, 0, 2}; auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); @@ -265,10 +280,12 @@ constexpr void test_iterators() { } { // check that the projections are used - int a[] = {1, 3, 15, 1, 2, 1, 8}; - int p[] = {2, 1, 2}; - auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); - auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); + int a[] = {1, 3, 15, 1, 2, 1, 8}; + int p[] = {2, 1, 2}; + auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a)))); + auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p)))); + auto proj1 = [](int i) { return i - 3; }; + auto proj2 = [](int i) { return i * -1; }; { bool ret = std::ranges::contains_subrange( whole.begin(), @@ -276,13 +293,13 @@ constexpr void test_iterators() { subrange.begin(), subrange.end(), {}, - [](int i) { return i - 3; }, - [](int i) { return i * -1; }); + proj1, + proj2); assert(ret); } { bool ret = std::ranges::contains_subrange( - whole, subrange, {}, [](int i) { return i - 3; }, [](int i) { return i * -1; }); + whole, subrange, {}, proj1, proj2); assert(ret); } } >From cf639d1d7555aa8447d6572e14d9256dae9b6d03 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Thu, 4 Jan 2024 18:39:42 -0800 Subject: [PATCH 12/15] 1. Call ranges::search() in ranges::contains_subrange() 2. add several test cases: like when both range and subrange are empty 3. reformat 4. nit to fix 5. add ranges::contains_subrange() in module.modulemap.in --- libcxx/include/module.modulemap.in | 1 + 1 file changed, 1 insertion(+) diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in index d10670d4faaffc..dc8534d9b1745b 100644 --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -787,6 +787,7 @@ module std_private_algorithm_ranges_clamp [system export std_private_functional_ranges_operations } module std_private_algorithm_ranges_contains [system] { header "__algorithm/ranges_contains.h" } +module std_private_algorithm_ranges_contains_subrange [system] { header "__algorithm/ranges_contains_subrange.h" } module std_private_algorithm_ranges_copy [system] { header "__algorithm/ranges_copy.h" export std_private_algorithm_in_out_result >From a5ecb2bf64a780cd3e748699214758d40ec09508 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Thu, 4 Jan 2024 18:39:42 -0800 Subject: [PATCH 13/15] 1. Call ranges::search() in ranges::contains_subrange() 2. add several test cases: like when both range and subrange are empty 3. reformat 4. nit to fix 5. add ranges::contains_subrange() in module.modulemap.in --- .../include/__algorithm/ranges_contains_subrange.h | 12 +++++++----- ...ges_robust_against_copying_projections.pass.cpp | 6 ++++-- .../alg.contains/ranges.contains_subrange.pass.cpp | 14 ++++---------- 3 files changed, 15 insertions(+), 17 deletions(-) diff --git a/libcxx/include/__algorithm/ranges_contains_subrange.h b/libcxx/include/__algorithm/ranges_contains_subrange.h index beb4d84f232bab..fd229b6524f0a5 100644 --- a/libcxx/include/__algorithm/ranges_contains_subrange.h +++ b/libcxx/include/__algorithm/ranges_contains_subrange.h @@ -52,8 +52,9 @@ struct __fn { auto __n2 = ranges::distance(__first2, __last2); if (__n2 == 0) return true; - auto ret = ranges::search(std::move(__first1), __last1, std::move(__first2), __last2, __pred, std::ref(__proj1), std::ref(__proj2)); - return ret.empty() == false; + auto __ret = ranges::search( + std::move(__first1), __last1, std::move(__first2), __last2, __pred, std::ref(__proj1), std::ref(__proj2)); + return __ret.empty() == false; } template <forward_range _Range1, @@ -70,10 +71,11 @@ struct __fn { } else { __n2 = std::distance(cbegin(__range2), cend(__range2)); } - if (__n2 == 0) return true; + if (__n2 == 0) + return true; - auto ret = ranges::search(__range1, __range2, __pred, std::ref(__proj1), std::ref(__proj2)); - return ret.empty() == false; + auto __ret = ranges::search(__range1, __range2, __pred, std::ref(__proj1), std::ref(__proj2)); + return __ret.empty() == false; } }; } // namespace __contains_subrange 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 index cc031867b908a3..71823d9afc1a4b 100644 --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -86,8 +86,10 @@ constexpr bool all_the_algorithms() assert(copies == 0); (void)std::ranges::contains(a, value, Proj(&copies)); assert(copies == 0); - (void)std::ranges::contains_subrange(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); - (void)std::ranges::contains_subrange(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::contains_subrange(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); + assert(copies == 0); + (void)std::ranges::contains_subrange(a, b, Equal(), Proj(&copies), Proj(&copies)); + assert(copies == 0); #endif (void)std::ranges::count(first, last, value, Proj(&copies)); assert(copies == 0); (void)std::ranges::count(a, value, Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp index cdfd40e8ca8398..d48ee9e4e7e02e 100644 --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp @@ -52,7 +52,8 @@ static_assert(!HasContainsSubrangeIt<int*, int*, int*, SentinelForNotWeaklyEqual template <class Range1, class Range2 = UncheckedRange<int*>> concept HasContainsSubrangeR = requires(Range1&& range1, Range2&& range2) { - std::ranges::contains_subrange(std::forward<Range1>(range1), std::forward<Range2>(range2)); }; + std::ranges::contains_subrange(std::forward<Range1>(range1), std::forward<Range2>(range2)); +}; static_assert(HasContainsSubrangeR<UncheckedRange<int*>>); static_assert(!HasContainsSubrangeR<ForwardRangeNotDerivedFrom>); @@ -288,18 +289,11 @@ constexpr void test_iterators() { auto proj2 = [](int i) { return i * -1; }; { bool ret = std::ranges::contains_subrange( - whole.begin(), - whole.end(), - subrange.begin(), - subrange.end(), - {}, - proj1, - proj2); + whole.begin(), whole.end(), subrange.begin(), subrange.end(), {}, proj1, proj2); assert(ret); } { - bool ret = std::ranges::contains_subrange( - whole, subrange, {}, proj1, proj2); + bool ret = std::ranges::contains_subrange(whole, subrange, {}, proj1, proj2); assert(ret); } } >From 9d64b6766b7bf3efff9e0b407648026b0a6b68f9 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Thu, 4 Jan 2024 18:39:42 -0800 Subject: [PATCH 14/15] 1. Call ranges::search() in ranges::contains_subrange() 2. add several test cases: like when both range and subrange are empty 3. reformat 4. nit to fix 5. add ranges::contains_subrange() in module.modulemap.in --- libcxx/include/__algorithm/ranges_contains_subrange.h | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) diff --git a/libcxx/include/__algorithm/ranges_contains_subrange.h b/libcxx/include/__algorithm/ranges_contains_subrange.h index fd229b6524f0a5..91e582acc85a13 100644 --- a/libcxx/include/__algorithm/ranges_contains_subrange.h +++ b/libcxx/include/__algorithm/ranges_contains_subrange.h @@ -50,7 +50,8 @@ struct __fn { _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) { auto __n2 = ranges::distance(__first2, __last2); - if (__n2 == 0) return true; + if (__n2 == 0) + return true; auto __ret = ranges::search( std::move(__first1), __last1, std::move(__first2), __last2, __pred, std::ref(__proj1), std::ref(__proj2)); @@ -63,15 +64,15 @@ struct __fn { class _Proj1 = identity, class _Proj2 = identity> requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> - _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool static operator()( - _Range1&& __range1, _Range2&& __range2, _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) { + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool static + operator()(_Range1&& __range1, _Range2&& __range2, _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) { auto __n2 = 0; if constexpr (sized_range<_Range2>) { __n2 = ranges::size(__range2); } else { __n2 = std::distance(cbegin(__range2), cend(__range2)); } - if (__n2 == 0) + if (__n2 == 0) return true; auto __ret = ranges::search(__range1, __range2, __pred, std::ref(__proj1), std::ref(__proj2)); >From d13b6e1abac30f1245077be50ecde58a0dc26ae2 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Thu, 4 Jan 2024 18:39:42 -0800 Subject: [PATCH 15/15] 1. Call ranges::search() in ranges::contains_subrange() 2. add several test cases: like when both range and subrange are empty 3. reformat 4. nit to fix 5. add ranges::contains_subrange() in module.modulemap.in --- libcxx/include/__algorithm/ranges_contains_subrange.h | 1 + 1 file changed, 1 insertion(+) diff --git a/libcxx/include/__algorithm/ranges_contains_subrange.h b/libcxx/include/__algorithm/ranges_contains_subrange.h index 91e582acc85a13..db01b605b20daf 100644 --- a/libcxx/include/__algorithm/ranges_contains_subrange.h +++ b/libcxx/include/__algorithm/ranges_contains_subrange.h @@ -20,6 +20,7 @@ #include <__iterator/projected.h> #include <__ranges/access.h> #include <__ranges/concepts.h> +#include <__ranges/subrange.h> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
