https://github.com/ZijunZhaoCCK updated https://github.com/llvm/llvm-project/pull/65148:
>From 02e9afd761228f401df4d9f8dfaaca44ffae0c6e Mon Sep 17 00:00:00 2001 From: zijunzhao <zijunz...@google.com> Date: Thu, 31 Aug 2023 20:08:32 +0000 Subject: [PATCH] [libc++] Implement ranges::contains Differential Revision: https://reviews.llvm.org/D159232 --- libcxx/include/CMakeLists.txt | 1 + libcxx/include/__algorithm/ranges_contains.h | 60 ++++++ libcxx/include/algorithm | 9 + ...obust_against_copying_projections.pass.cpp | 4 + .../alg.contains/ranges.contains.pass.cpp | 190 ++++++++++++++++++ .../niebloid.compile.pass.cpp | 1 + 6 files changed, 265 insertions(+) create mode 100644 libcxx/include/__algorithm/ranges_contains.h create mode 100644 libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains.pass.cpp diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index 77a7269121ec142..024aa8959fb7200 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.h __algorithm/ranges_copy.h __algorithm/ranges_copy_backward.h __algorithm/ranges_copy_if.h diff --git a/libcxx/include/__algorithm/ranges_contains.h b/libcxx/include/__algorithm/ranges_contains.h new file mode 100644 index 000000000000000..647b7ea34be3421 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_contains.h @@ -0,0 +1,60 @@ +//===----------------------------------------------------------------------===// +// +// 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_H +#define _LIBCPP___ALGORITHM_RANGES_CONTAINS_H + +#include <__algorithm/in_in_result.h> +#include <__algorithm/ranges_find.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__functional/reference_wrapper.h> +#include <__iterator/concepts.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 { +struct __fn { + template <input_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type*> + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool + operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) const { + return ranges::find(std::move(__first), std::move(__last), __value, std::ref(__proj)) != __last; + } + + template <input_range _Range, class _Type, class _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*> + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool + operator()(_Range&& __range, const _Type& __value, _Proj __proj = {}) const { + return ranges::find(ranges::begin(__range), ranges::end(__range), __value, std::ref(__proj)) != ranges::end(__range); + } +}; +} // namespace __contains +inline namespace __cpo { +inline constexpr auto contains = __contains::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER >= 23 + +#endif // _LIBCPP___ALGORITHM_RANGES_CONTAINS_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 76e0d22bf73ef85..003bf132b38b4d8 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -226,6 +226,14 @@ namespace ranges { template<class I1, class I2> using copy_backward_result = in_out_result<I1, I2>; // since C++20 + 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 + template<input_iterator I, sentinel_for<I> S, weakly_incrementable O> requires indirectly_copyable<I, O> constexpr ranges::copy_result<I, O> ranges::copy(I first, S last, O result); // since C++20 @@ -1827,6 +1835,7 @@ template <class BidirectionalIterator, class Compare> #include <__algorithm/ranges_any_of.h> #include <__algorithm/ranges_binary_search.h> #include <__algorithm/ranges_clamp.h> +#include <__algorithm/ranges_contains.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 111b0ff655f5342..e50f4ef2ed719c7 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 @@ -80,6 +80,10 @@ constexpr bool all_the_algorithms() (void)std::ranges::binary_search(first, last, value, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::binary_search(a, value, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::clamp(T(), T(), T(), Less(), Proj(&copies)); assert(copies == 0); +#if TEST_STD_VER >= 23 + (void)std::ranges::contains(first, last, value, Proj(&copies)); assert(copies == 0); + (void)std::ranges::contains(a, value, 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); (void)std::ranges::count_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains.pass.cpp new file mode 100644 index 000000000000000..8e67e971c2f040b --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains.pass.cpp @@ -0,0 +1,190 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// 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 Iter, class Sent = Iter> +concept HasContainsIt = requires(Iter iter, Sent sent) { std::ranges::contains(iter, sent, *iter); }; + +static_assert(HasContainsIt<int*>); +static_assert(!HasContainsIt<NotEqualityComparable*>); +static_assert(!HasContainsIt<InputIteratorNotDerivedFrom>); +static_assert(!HasContainsIt<InputIteratorNotIndirectlyReadable>); +static_assert(!HasContainsIt<InputIteratorNotInputOrOutputIterator>); +static_assert(!HasContainsIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>); +static_assert(!HasContainsIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>); + +static_assert(!HasContainsIt<int*, int>); +static_assert(!HasContainsIt<int, int*>); + +template <class Range, class ValT> +concept HasContainsR = requires(Range range) { std::ranges::contains(range, ValT{}); }; + +static_assert(HasContainsR<std::array<int, 1>, int>); +static_assert(!HasContainsR<int, int>); +static_assert(!HasContainsR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>); +static_assert(!HasContainsR<InputRangeNotDerivedFrom, int>); +static_assert(!HasContainsR<InputRangeNotIndirectlyReadable, int>); +static_assert(!HasContainsR<InputRangeNotInputOrOutputIterator, int>); +static_assert(!HasContainsR<InputRangeNotSentinelSemiregular, int>); +static_assert(!HasContainsR<InputRangeNotSentinelEqualityComparableWith, int>); + +static std::vector<int> comparable_data; + +// clang-format off +template <class Iter, class Sent = Iter> +constexpr void test_iterators() { + using ValueT = std::iter_value_t<Iter>; + { // simple tests + { + ValueT a[] = {1, 2, 3, 4, 5, 6}; + std::same_as<bool> auto ret = + std::ranges::contains(Iter(a), Sent(Iter(a + 6)), 3); + assert(ret); + } + { + ValueT a[] = {1, 2, 3, 4, 5, 6}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); + std::same_as<bool> decltype(auto) ret = + std::ranges::contains(range, 3); + assert(ret); + } + } + + { // check that an empty range works + { + ValueT a[] = {}; + auto ret = std::ranges::contains(Iter(a), Sent(Iter(a)), 1); + assert(!ret); + } + { + ValueT a[] = {}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a))); + auto ret = std::ranges::contains(range, 1); + assert(!ret); + } + } + + { // check that no match + { + ValueT a[] = {13, 1, 21, 4, 5}; + auto ret = std::ranges::contains(Iter(a), Sent(Iter(a + 5)), 10); + assert(!ret); + } + { + ValueT a[] = {13, 1, 21, 4, 5}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5))); + auto ret = std::ranges::contains(range, 10); + assert(!ret); + } + } + + if (!std::is_constant_evaluated()) + comparable_data.clear(); +} +template <class ElementT> +class TriviallyComparable { + ElementT el_; + +public: + TEST_CONSTEXPR TriviallyComparable(ElementT el) : el_(el) {} + bool operator==(const TriviallyComparable&) const = default; +}; + +template <class IndexT> +class Comparable { + IndexT index_; + +public: + Comparable(IndexT i) + : index_([&]() { + IndexT size = static_cast<IndexT>(comparable_data.size()); + comparable_data.push_back(i); + return size; + }()) {} + + bool operator==(const Comparable& other) const { + return comparable_data[other.index_] == comparable_data[index_]; + } + + friend bool operator==(const Comparable& lhs, long long rhs) { return comparable_data[lhs.index_] == rhs; } +}; + +constexpr bool test() { + types::for_each(types::type_list<char, wchar_t, int, long, + TriviallyComparable<char>, TriviallyComparable<wchar_t>>{}, + []<class T> { + types::for_each(types::cpp20_input_iterator_list<T*>{}, + []<class Iter> { + if constexpr (std::forward_iterator<Iter>) + test_iterators<Iter>(); + test_iterators<Iter, sentinel_wrapper<Iter>>(); + test_iterators<Iter, sized_sentinel<Iter>>(); + }); + }); + + { + // count invocations of the projection + { + int a[] = {1, 9, 0, 13, 25}; + int projection_count = 0; + auto ret = std::ranges::contains(a, a + 5, 0, + [&](int i) { ++projection_count; return i; }); + assert(ret); + assert(projection_count == 3); + } + { + int a[] ={1, 9, 0, 13, 25}; + int projection_count = 0; + auto range = std::ranges::subrange(a, a + 5); + auto ret = std::ranges::contains(range, 0, [&](int i) { ++projection_count; return i; }); + assert(ret); + assert(projection_count == 3); + } + } + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + types::for_each(types::type_list<Comparable<char>, Comparable<wchar_t>>{}, + []<class T> { + types::for_each(types::cpp20_input_iterator_list<T*>{}, + []<class Iter> { + if constexpr (std::forward_iterator<Iter>) + test_iterators<Iter>(); + test_iterators<Iter, sentinel_wrapper<Iter>>(); + test_iterators<Iter, sized_sentinel<Iter>>(); + }); + }); + + return 0; +} 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 9e00a57ba80c631..8884941fee32345 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 @@ -65,6 +65,7 @@ static_assert(test(std::ranges::all_of, a, odd)); static_assert(test(std::ranges::any_of, a, odd)); static_assert(test(std::ranges::binary_search, a, 42)); static_assert(test(std::ranges::clamp, 42, 42, 42)); +static_assert(test(std::ranges::contains, a, 42)); static_assert(test(std::ranges::copy, a, a)); static_assert(test(std::ranges::copy_backward, a, a)); static_assert(test(std::ranges::copy_if, a, a, odd)); _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
