[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
philnik777 wrote: > Please make sure you add a description to your PR. This is what usually goes > into the git log and we want those entries to be as descriptive and helpful > for folks who read the git logs, thank you. Do you have any specific suggestions what should be in the message? The libc++ "I implement something" patches are most of the time quite straight-forward, since you can look at the standard and know what's going on. It's also the best source, since it's the authoritative document here, and is also what anybody who cares to actually look at the patch should check against for correctness. https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
shafik wrote: Please make sure you add a description to your PR. This is what usually goes into the git log and we want those entries to be as descriptive and helpful for folks who read the git logs, thank you. https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
https://github.com/ZijunZhaoCCK converted_to_draft https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
https://github.com/ZijunZhaoCCK updated https://github.com/llvm/llvm-project/pull/66963 >From 5a2c930770cf548c5e3f3451e76b48cb067e6762 Mon Sep 17 00:00:00 2001 From: Zijun Zhao Date: Wed, 13 Sep 2023 14:26:01 -0700 Subject: [PATCH 1/5] [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 | 4 + .../ranges.contains_subrange.pass.cpp | 293 ++ .../niebloid.compile.pass.cpp | 3 + 6 files changed, 460 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 2ec755236dbaee2..b096259f85f6ac8 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -104,6 +104,7 @@ set(files __algorithm/ranges_any_of.h __algorithm/ranges_binary_search.h __algorithm/ranges_clamp.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 000..16de6c29cb2a1a4 --- /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 _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 _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 +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 { +auto __n1 = 0; +auto __n2 = 0; + +if
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
https://github.com/huixie90 requested changes to this pull request. https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
@@ -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 _Sent1, +input_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 { + 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 _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 { +int __n1 = ranges::distance(__first1, __last1); +int __n2 = ranges::distance(__first2, __last2); +int __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 https://eel.is/c++draft/alg.contains https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
@@ -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 _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; +} huixie90 wrote: `contains_subrange` only worked for `forward_iterator`, which is the same as `ranges::search`. Why do you test it with an `input_iterator`? It will fail as expected. https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
@@ -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 _Sent1, +input_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 { + 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 _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 { +int __n1 = ranges::distance(__first1, __last1); +int __n2 = ranges::distance(__first2, __last2); +int __offset = __n1 - __n2; huixie90 wrote: This still does not work. `iter_difference_t` could be any integer class type, which is not guaranteed to be explicitly convertible to `int`. Even it does, you don't want to do it, because this might be a narrowing conversion and you just get into undefined behaviour if actual distance is larger than the max of `int` https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
@@ -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 _Sent1, +input_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 { + 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 _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 { +int __n1 = ranges::distance(__first1, __last1); +int __n2 = ranges::distance(__first2, __last2); +int __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 +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 { +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(__range1); + __n2 = ranges::distance(__range2); +} huixie90 wrote: as in the other comments. `int` won't work here https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
@@ -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 _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; +} ZijunZhaoCCK wrote: Yes. Initially, I didn't aware that I can use `ranges::search`. Then I tried to replace `ranges::starts_with` with `ranges::search` and I got > constraints not satisfied for class template 'subrange' [with _Iter = > cpp20_input_iterator, _Sent = cpp20_input_iterator, _Kind = > std::ranges::subrange_kind::unsized] error in the test file. I tried to test with forward iterator. It works well. https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
github-actions[bot] wrote: :warning: C/C++ code formatter, clang-format found issues in your code. :warning: You can test this locally with the following command: ``bash git-clang-format --diff 2f2319cf2406d9830a331cbf015881c55ae78806 5f33fa63e76b5d0c066773113447749c3428aa99 -- libcxx/include/__algorithm/ranges_contains_subrange.h libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp `` View the diff from clang-format here. ``diff 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 fd4d858b255d..e9c300e5bb20 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,8 @@ static_assert(HasContainsSubrangeSubrangeIt); template > concept HasContainsSubrangeR = requires(Range1&& range1, Range2&& range2) { -std::ranges::contains_subrange(std::forward(range1), std::forward(range2)); }; + std::ranges::contains_subrange(std::forward(range1), std::forward(range2)); +}; static_assert(HasContainsSubrangeR>); static_assert(HasContainsSubrangeR); @@ -68,27 +69,26 @@ static std::vector comparable_data; template 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))); + { // 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 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 decltype(auto) ret = -std::ranges::contains_subrange(whole, subrange); + [[maybe_unused]] std::same_as 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 +101,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 +116,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 +131,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 +146,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))); {
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
https://github.com/ZijunZhaoCCK resolved https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
https://github.com/ZijunZhaoCCK resolved https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
https://github.com/huixie90 edited https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
@@ -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 _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; +} huixie90 wrote: is there a reason why you did not define in terms of `ranges::search` as in the standard? https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
https://github.com/huixie90 edited https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
@@ -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 _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 _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 +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 { +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)); +} + huixie90 wrote: `ranges::distance(r)` does exactly this https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
@@ -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 _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 _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 +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 { +auto __n1 = 0; +auto __n2 = 0; huixie90 wrote: `__n1` and `__n2` are `int`s, and later you assigned to `iter_difference_t`. This could be a hard error because integer class is not guaranteed to be "explicitly" convertible to `int` https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
https://github.com/ZijunZhaoCCK ready_for_review https://github.com/llvm/llvm-project/pull/66963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
https://github.com/ZijunZhaoCCK updated https://github.com/llvm/llvm-project/pull/66963 >From 5a2c930770cf548c5e3f3451e76b48cb067e6762 Mon Sep 17 00:00:00 2001 From: Zijun Zhao Date: Wed, 13 Sep 2023 14:26:01 -0700 Subject: [PATCH 1/2] [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 | 4 + .../ranges.contains_subrange.pass.cpp | 293 ++ .../niebloid.compile.pass.cpp | 3 + 6 files changed, 460 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 2ec755236dbaee2..b096259f85f6ac8 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -104,6 +104,7 @@ set(files __algorithm/ranges_any_of.h __algorithm/ranges_binary_search.h __algorithm/ranges_clamp.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 000..16de6c29cb2a1a4 --- /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 _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 _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 +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 { +auto __n1 = 0; +auto __n2 = 0; + +if
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
https://github.com/ZijunZhaoCCK updated https://github.com/llvm/llvm-project/pull/66963 >From 5a2c930770cf548c5e3f3451e76b48cb067e6762 Mon Sep 17 00:00:00 2001 From: Zijun Zhao Date: Wed, 13 Sep 2023 14:26:01 -0700 Subject: [PATCH] [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 | 4 + .../ranges.contains_subrange.pass.cpp | 293 ++ .../niebloid.compile.pass.cpp | 3 + 6 files changed, 460 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 2ec755236dbaee2..b096259f85f6ac8 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -104,6 +104,7 @@ set(files __algorithm/ranges_any_of.h __algorithm/ranges_binary_search.h __algorithm/ranges_clamp.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 000..16de6c29cb2a1a4 --- /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 _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 _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 +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 { +auto __n1 = 0; +auto __n2 = 0; + +if
[clang] [libc++] Implement ranges::contains_subrange (PR #66963)
https://github.com/ZijunZhaoCCK updated https://github.com/llvm/llvm-project/pull/66963 >From 5a2c930770cf548c5e3f3451e76b48cb067e6762 Mon Sep 17 00:00:00 2001 From: Zijun Zhao Date: Wed, 13 Sep 2023 14:26:01 -0700 Subject: [PATCH] [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 | 4 + .../ranges.contains_subrange.pass.cpp | 293 ++ .../niebloid.compile.pass.cpp | 3 + 6 files changed, 460 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 2ec755236dbaee2..b096259f85f6ac8 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -104,6 +104,7 @@ set(files __algorithm/ranges_any_of.h __algorithm/ranges_binary_search.h __algorithm/ranges_clamp.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 000..16de6c29cb2a1a4 --- /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 _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 _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 +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 { +auto __n1 = 0; +auto __n2 = 0; + +if