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 01/21] [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 77a7269121ec14..024aa8959fb720 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 00000000000000..647b7ea34be342 --- /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 76e0d22bf73ef8..003bf132b38b4d 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 111b0ff655f534..e50f4ef2ed719c 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 00000000000000..8e67e971c2f040 --- /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 9e00a57ba80c63..8884941fee3234 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)); >From 80c08f6f2f86ae650ef0cbbc5d4a5f5ce39e0916 Mon Sep 17 00:00:00 2001 From: zijunzhao <zijunz...@google.com> Date: Thu, 31 Aug 2023 20:08:32 +0000 Subject: [PATCH 02/21] [libc++] Implement ranges::contains Differential Revision: https://reviews.llvm.org/D159232 --- libcxx/include/__algorithm/ranges_contains.h | 1 + .../alg.nonmodifying/alg.contains/ranges.contains.pass.cpp | 4 +++- 2 files changed, 4 insertions(+), 1 deletion(-) diff --git a/libcxx/include/__algorithm/ranges_contains.h b/libcxx/include/__algorithm/ranges_contains.h index 647b7ea34be342..018d362900e394 100644 --- a/libcxx/include/__algorithm/ranges_contains.h +++ b/libcxx/include/__algorithm/ranges_contains.h @@ -48,6 +48,7 @@ struct __fn { } }; } // namespace __contains + inline namespace __cpo { inline constexpr auto contains = __contains::__fn{}; } // namespace __cpo 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 index 8e67e971c2f040..a0c4acb08f5c92 100644 --- 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 @@ -9,6 +9,7 @@ // <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 @@ -108,6 +109,7 @@ constexpr void test_iterators() { if (!std::is_constant_evaluated()) comparable_data.clear(); } + template <class ElementT> class TriviallyComparable { ElementT el_; @@ -160,7 +162,7 @@ constexpr bool test() { assert(projection_count == 3); } { - int a[] ={1, 9, 0, 13, 25}; + 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; }); >From 34d8e29a0c9c6bd11d8d0ba1433015d8d22f0c4a Mon Sep 17 00:00:00 2001 From: zijunzhao <zijunz...@google.com> Date: Thu, 31 Aug 2023 20:08:32 +0000 Subject: [PATCH 03/21] [libc++] Implement ranges::contains Differential Revision: https://reviews.llvm.org/D159232 --- .../alg.contains/ranges.contains.pass.cpp | 92 +++++++++++++------ 1 file changed, 65 insertions(+), 27 deletions(-) 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 index a0c4acb08f5c92..b4c879bbc8ee26 100644 --- 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 @@ -40,15 +40,17 @@ 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<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>); static_assert(!HasContainsIt<int*, int>); 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{}); }; +concept HasContainsR = requires(Range&& range) { std::ranges::contains(std::forward<Range>(range), ValT{}); }; -static_assert(HasContainsR<std::array<int, 1>, int>); static_assert(!HasContainsR<int, int>); +static_assert(HasContainsR<std::array<int, 1>, int>); static_assert(!HasContainsR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>); static_assert(!HasContainsR<InputRangeNotDerivedFrom, int>); static_assert(!HasContainsR<InputRangeNotIndirectlyReadable, int>); @@ -63,45 +65,81 @@ 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}; + auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); { - ValueT a[] = {1, 2, 3, 4, 5, 6}; - std::same_as<bool> auto ret = - std::ranges::contains(Iter(a), Sent(Iter(a + 6)), 3); + [[maybe_unused]] std::same_as<bool> decltype(auto) ret = + std::ranges::contains(whole.begin(), whole.end(), 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); + [[maybe_unused]] std::same_as<bool> decltype(auto) ret = + std::ranges::contains(whole, 3); + assert(ret); + } + } + + { // check that a range with a single element works + ValueT a[] = {32}; + auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 1))); + { + bool ret = std::ranges::contains(whole.begin(), whole.end(), 32); + assert(ret); + } + { + bool ret = std::ranges::contains(whole, 32); assert(ret); } } { // check that an empty range works + ValueT a[] = {}; + auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a))); { - ValueT a[] = {}; - auto ret = std::ranges::contains(Iter(a), Sent(Iter(a)), 1); + bool ret = std::ranges::contains(whole.begin(), whole.end(), 1); assert(!ret); } { - ValueT a[] = {}; - auto range = std::ranges::subrange(Iter(a), Sent(Iter(a))); - auto ret = std::ranges::contains(range, 1); + bool ret = std::ranges::contains(whole, 1); assert(!ret); } } - { // check that no match + { // check that the first element matches + ValueT a[] = {32, 3, 2, 1, 0, 23, 21, 9, 40, 100}; + auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 10))); + { + bool ret = std::ranges::contains(whole.begin(), whole.end(), 32); + assert(ret); + } + { + bool ret = std::ranges::contains(whole, 32); + assert(ret); + } + } + + { // check that the last element matches + ValueT a[] = {3, 22, 1, 43, 99, 0, 56, 100, 32}; + auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 9))); + { + bool ret = std::ranges::contains(whole.begin(), whole.end(), 32); + assert(ret); + } + { + bool ret = std::ranges::contains(whole, 32); + assert(ret); + } + } + + { // no match + ValueT a[] = {13, 1, 21, 4, 5}; + auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 5))); { - ValueT a[] = {13, 1, 21, 4, 5}; - auto ret = std::ranges::contains(Iter(a), Sent(Iter(a + 5)), 10); + bool ret = std::ranges::contains(whole.begin(), whole.end(), 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); + bool ret = std::ranges::contains(whole, 10); assert(!ret); } } @@ -115,7 +153,7 @@ class TriviallyComparable { ElementT el_; public: - TEST_CONSTEXPR TriviallyComparable(ElementT el) : el_(el) {} + constexpr TriviallyComparable(ElementT el) : el_(el) {} bool operator==(const TriviallyComparable&) const = default; }; @@ -152,20 +190,20 @@ constexpr bool test() { }); { + int a[] = {1, 9, 0, 13, 25}; + int projection_count = 0; // 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, + projection_count = 0; + bool 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; + projection_count = 0; auto range = std::ranges::subrange(a, a + 5); - auto ret = std::ranges::contains(range, 0, [&](int i) { ++projection_count; return i; }); + bool ret = std::ranges::contains(range, 0, [&](int i) { ++projection_count; return i; }); assert(ret); assert(projection_count == 3); } >From 9db49ddab25affcd7c05d0c825ec2788dd53e5b5 Mon Sep 17 00:00:00 2001 From: zijunzhao <zijunz...@google.com> Date: Thu, 31 Aug 2023 20:08:32 +0000 Subject: [PATCH 04/21] [libc++] Implement ranges::contains Differential Revision: https://reviews.llvm.org/D159232 --- .../alg.nonmodifying/alg.contains/ranges.contains.pass.cpp | 1 - 1 file changed, 1 deletion(-) 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 index b4c879bbc8ee26..29a686a1ae8eed 100644 --- 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 @@ -194,7 +194,6 @@ constexpr bool test() { int projection_count = 0; // count invocations of the projection { - projection_count = 0; bool ret = std::ranges::contains(a, a + 5, 0, [&](int i) { ++projection_count; return i; }); assert(ret); >From 54bccdd7677000ae6d90bc0fc9790d9c2c69602b Mon Sep 17 00:00:00 2001 From: zijunzhao <zijunz...@google.com> Date: Thu, 31 Aug 2023 20:08:32 +0000 Subject: [PATCH 05/21] [libc++] Implement ranges::contains Differential Revision: https://reviews.llvm.org/D159232 --- .../alg.contains/ranges.contains.pass.cpp | 23 +++++++++++++++++++ 1 file changed, 23 insertions(+) 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 index 29a686a1ae8eed..eb6567c786342a 100644 --- 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 @@ -144,6 +144,29 @@ constexpr void test_iterators() { } } + { // check that the projections are used + int a[] = {1, 9, 0, 13, 25}; + { + bool ret = std::ranges::contains(a, a + 5, -13, [&](int i) { return i * -1; }); + assert(ret); + } + { + auto range = std::ranges::subrange(a, a + 5); + bool ret = std::ranges::contains(range, -13, [&](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}; + std::ranges::contains(a, a + 5, -13, [&](int i) { return i * -1; }); + #pragma clang diagnostic pop + } + if (!std::is_constant_evaluated()) comparable_data.clear(); } >From 826bd982d734c23fbe95d79cb446b5bb50341f34 Mon Sep 17 00:00:00 2001 From: zijunzhao <zijunz...@google.com> Date: Thu, 31 Aug 2023 20:08:32 +0000 Subject: [PATCH 06/21] [libc++] Implement ranges::contains Differential Revision: https://reviews.llvm.org/D159232 --- .../alg.nonmodifying/alg.contains/ranges.contains.pass.cpp | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) 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 index eb6567c786342a..9e079b7dc42723 100644 --- 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 @@ -162,8 +162,9 @@ constexpr void test_iterators() { // declared with 'nodiscard' attribute [-Werror,-Wunused-result] #pragma clang diagnostic push #pragma clang diagnostic ignored "-Wunused-result" - int a[] = {1, 9, 0, 13, 25}; - std::ranges::contains(a, a + 5, -13, [&](int i) { return i * -1; }); + ValueT a[] = {1, 9, 0, 13, 25}; + auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 5))); + std::ranges::contains(whole.begin(), whole.end(), 12); #pragma clang diagnostic pop } >From 32cf818aa8a74e7d2c8e30892e463a09a5dca4d6 Mon Sep 17 00:00:00 2001 From: zijunzhao <zijunz...@google.com> Date: Thu, 31 Aug 2023 20:08:32 +0000 Subject: [PATCH 07/21] [libc++] Implement ranges::contains Differential Revision: https://reviews.llvm.org/D159232 --- .../alg.nonmodifying/alg.contains/ranges.contains.pass.cpp | 1 - 1 file changed, 1 deletion(-) 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 index 9e079b7dc42723..f91641b4a6de49 100644 --- 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 @@ -60,7 +60,6 @@ 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>; >From 4420189228af33f2fc23af1c4e2c70740f640bca Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Mon, 11 Sep 2023 17:35:39 -0700 Subject: [PATCH 08/21] update the tests and make it more elegant --- .../alg.nonmodifying/alg.contains/ranges.contains.pass.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) 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 index f91641b4a6de49..e9465c58f87890 100644 --- 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 @@ -50,8 +50,8 @@ template <class Range, class ValT> concept HasContainsR = requires(Range&& range) { std::ranges::contains(std::forward<Range>(range), ValT{}); }; static_assert(!HasContainsR<int, int>); -static_assert(HasContainsR<std::array<int, 1>, int>); -static_assert(!HasContainsR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>); +static_assert(HasContainsR<int[1], int>); +static_assert(!HasContainsR<NotEqualityComparable[1], NotEqualityComparable>); static_assert(!HasContainsR<InputRangeNotDerivedFrom, int>); static_assert(!HasContainsR<InputRangeNotIndirectlyReadable, int>); static_assert(!HasContainsR<InputRangeNotInputOrOutputIterator, int>); >From 7481a66f70ab6c969142d17cff54dbd69ab4a7a2 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Tue, 12 Sep 2023 14:32:38 -0700 Subject: [PATCH 10/21] update test types --- .../alg.nonmodifying/alg.contains/ranges.contains.pass.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) 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 index e9465c58f87890..30bb399bd6dec9 100644 --- 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 @@ -200,7 +200,7 @@ class Comparable { }; constexpr bool test() { - types::for_each(types::type_list<char, wchar_t, int, long, + types::for_each(types::type_list<char, short, int, long, long long, TriviallyComparable<char>, TriviallyComparable<wchar_t>>{}, []<class T> { types::for_each(types::cpp20_input_iterator_list<T*>{}, >From f37aa1df5fcbf084da184640bc247e7ffbbd5ee9 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Wed, 13 Sep 2023 14:45:11 -0700 Subject: [PATCH 11/21] simplify code --- .../alg.nonmodifying/alg.contains/ranges.contains.pass.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) 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 index 30bb399bd6dec9..77e90a528e37dd 100644 --- 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 @@ -163,7 +163,7 @@ constexpr void test_iterators() { #pragma clang diagnostic ignored "-Wunused-result" ValueT a[] = {1, 9, 0, 13, 25}; auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 5))); - std::ranges::contains(whole.begin(), whole.end(), 12); + std::ranges::contains(whole, 12); #pragma clang diagnostic pop } >From e21911a96cd488a20e1830327b7d198bb5bf8506 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Tue, 3 Oct 2023 17:12:02 -0700 Subject: [PATCH 12/21] nits fixed --- libcxx/include/__algorithm/ranges_contains.h | 4 ++-- .../alg.contains/ranges.contains.pass.cpp | 8 ++++---- 2 files changed, 6 insertions(+), 6 deletions(-) diff --git a/libcxx/include/__algorithm/ranges_contains.h b/libcxx/include/__algorithm/ranges_contains.h index 018d362900e394..08d5305477889b 100644 --- a/libcxx/include/__algorithm/ranges_contains.h +++ b/libcxx/include/__algorithm/ranges_contains.h @@ -9,7 +9,6 @@ #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> @@ -44,7 +43,8 @@ struct __fn { 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); + return ranges::find(ranges::begin(__range), ranges::end(__range), __value, + std::ref(__proj)) != ranges::end(__range); } }; } // namespace __contains 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 index 77e90a528e37dd..66b2732590b5ea 100644 --- 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 @@ -203,7 +203,7 @@ constexpr bool test() { types::for_each(types::type_list<char, short, int, long, long long, TriviallyComparable<char>, TriviallyComparable<wchar_t>>{}, []<class T> { - types::for_each(types::cpp20_input_iterator_list<T*>{}, + types::for_each(types::cpp20_input_iterator_list<T*>{}, []<class Iter> { if constexpr (std::forward_iterator<Iter>) test_iterators<Iter>(); @@ -212,10 +212,9 @@ constexpr bool test() { }); }); - { + { // count invocations of the projection int a[] = {1, 9, 0, 13, 25}; int projection_count = 0; - // count invocations of the projection { bool ret = std::ranges::contains(a, a + 5, 0, [&](int i) { ++projection_count; return i; }); @@ -230,6 +229,7 @@ constexpr bool test() { assert(projection_count == 3); } } + return true; } @@ -239,7 +239,7 @@ int main(int, char**) { types::for_each(types::type_list<Comparable<char>, Comparable<wchar_t>>{}, []<class T> { - types::for_each(types::cpp20_input_iterator_list<T*>{}, + types::for_each(types::cpp20_input_iterator_list<T*>{}, []<class Iter> { if constexpr (std::forward_iterator<Iter>) test_iterators<Iter>(); >From fdff1a4c64ca2f403cae67565c4780bc5dbbb424 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Thu, 12 Oct 2023 18:15:29 -0700 Subject: [PATCH 13/21] 1. remove Comparable and TriviallyComparable 2. remove wchar_t test 3. some nits --- .../alg.contains/ranges.contains.pass.cpp | 71 ++----------------- 1 file changed, 6 insertions(+), 65 deletions(-) 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 index 66b2732590b5ea..b98f1c86b75546 100644 --- 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 @@ -19,7 +19,6 @@ // constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {}); // since C++23 #include <algorithm> -#include <array> #include <cassert> #include <ranges> #include <vector> @@ -34,6 +33,7 @@ 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<int*, int*>); static_assert(!HasContainsIt<NotEqualityComparable*>); static_assert(!HasContainsIt<InputIteratorNotDerivedFrom>); static_assert(!HasContainsIt<InputIteratorNotIndirectlyReadable>); @@ -44,7 +44,6 @@ static_assert(!HasContainsIt<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_ static_assert(!HasContainsIt<int*, int>); static_assert(!HasContainsIt<int, int*>); -static_assert(HasContainsIt<int*, int*>); template <class Range, class ValT> concept HasContainsR = requires(Range&& range) { std::ranges::contains(std::forward<Range>(range), ValT{}); }; @@ -58,8 +57,6 @@ static_assert(!HasContainsR<InputRangeNotInputOrOutputIterator, int>); static_assert(!HasContainsR<InputRangeNotSentinelSemiregular, int>); static_assert(!HasContainsR<InputRangeNotSentinelEqualityComparableWith, int>); -static std::vector<int> comparable_data; - template <class Iter, class Sent = Iter> constexpr void test_iterators() { using ValueT = std::iter_value_t<Iter>; @@ -67,13 +64,12 @@ constexpr void test_iterators() { ValueT a[] = {1, 2, 3, 4, 5, 6}; auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); { - [[maybe_unused]] std::same_as<bool> decltype(auto) ret = + std::same_as<bool> decltype(auto) ret = std::ranges::contains(whole.begin(), whole.end(), 3); assert(ret); } { - [[maybe_unused]] std::same_as<bool> decltype(auto) ret = - std::ranges::contains(whole, 3); + std::same_as<bool> decltype(auto) ret = std::ranges::contains(whole, 3); assert(ret); } } @@ -155,53 +151,10 @@ 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" - ValueT a[] = {1, 9, 0, 13, 25}; - auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 5))); - std::ranges::contains(whole, 12); - #pragma clang diagnostic pop - } - - if (!std::is_constant_evaluated()) - comparable_data.clear(); } -template <class ElementT> -class TriviallyComparable { - ElementT el_; - -public: - 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, short, int, long, long long, - TriviallyComparable<char>, TriviallyComparable<wchar_t>>{}, + types::for_each(types::type_list<char, short, int, long, long long>{}, []<class T> { types::for_each(types::cpp20_input_iterator_list<T*>{}, []<class Iter> { @@ -220,11 +173,10 @@ constexpr bool test() { [&](int i) { ++projection_count; return i; }); assert(ret); assert(projection_count == 3); + projection_count = 0; } { - projection_count = 0; - auto range = std::ranges::subrange(a, a + 5); - bool ret = std::ranges::contains(range, 0, [&](int i) { ++projection_count; return i; }); + bool ret = std::ranges::contains(a, 0, [&](int i) { ++projection_count; return i; }); assert(ret); assert(projection_count == 3); } @@ -237,16 +189,5 @@ 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; } >From 51672ee44126e637c8f98331ec999d7e8ad22294 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Fri, 13 Oct 2023 07:28:48 -0700 Subject: [PATCH 15/21] reformat --- libcxx/include/__algorithm/ranges_contains.h | 4 +- .../alg.contains/ranges.contains.pass.cpp | 40 ++++++++++--------- 2 files changed, 24 insertions(+), 20 deletions(-) diff --git a/libcxx/include/__algorithm/ranges_contains.h b/libcxx/include/__algorithm/ranges_contains.h index 08d5305477889b..f0047960a6f774 100644 --- a/libcxx/include/__algorithm/ranges_contains.h +++ b/libcxx/include/__algorithm/ranges_contains.h @@ -43,8 +43,8 @@ struct __fn { 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); + return ranges::find(ranges::begin(__range), ranges::end(__range), __value, std::ref(__proj)) != + ranges::end(__range); } }; } // namespace __contains 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 index b98f1c86b75546..64a88e46f2c2fc 100644 --- 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 @@ -60,12 +60,11 @@ static_assert(!HasContainsR<InputRangeNotSentinelEqualityComparableWith, int>); template <class Iter, class Sent = Iter> constexpr void test_iterators() { using ValueT = std::iter_value_t<Iter>; - { // simple tests + { // simple tests ValueT a[] = {1, 2, 3, 4, 5, 6}; auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); { - std::same_as<bool> decltype(auto) ret = - std::ranges::contains(whole.begin(), whole.end(), 3); + std::same_as<bool> decltype(auto) ret = std::ranges::contains(whole.begin(), whole.end(), 3); assert(ret); } { @@ -147,36 +146,41 @@ constexpr void test_iterators() { } { auto range = std::ranges::subrange(a, a + 5); - bool ret = std::ranges::contains(range, -13, [&](int i) { return i * -1; }); + bool ret = std::ranges::contains(range, -13, [&](int i) { return i * -1; }); assert(ret); } } } constexpr bool test() { - types::for_each(types::type_list<char, short, int, long, long long>{}, - []<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>>(); - }); - }); + types::for_each( + types::type_list<char, short, int, long, long long>{}, + []<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 a[] = {1, 9, 0, 13, 25}; int projection_count = 0; { - bool ret = std::ranges::contains(a, a + 5, 0, - [&](int i) { ++projection_count; return i; }); + bool ret = std::ranges::contains(a, a + 5, 0, [&](int i) { + ++projection_count; + return i; + }); assert(ret); assert(projection_count == 3); projection_count = 0; } { - bool ret = std::ranges::contains(a, 0, [&](int i) { ++projection_count; return i; }); + bool ret = std::ranges::contains(a, 0, [&](int i) { + ++projection_count; + return i; + }); assert(ret); assert(projection_count == 3); } >From adc8c392c35adad58ecc13694f2f5337ea927c33 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Tue, 17 Oct 2023 12:09:52 -0700 Subject: [PATCH 16/21] 1. add robust tests 2. add nodiscard_extensions tests --- libcxx/docs/UsingLibcxx.rst | 1 + .../libcxx/diagnostics/nodiscard_extensions.compile.pass.cpp | 3 +++ .../test/libcxx/diagnostics/nodiscard_extensions.verify.cpp | 5 +++++ .../ranges_robust_against_omitting_invoke.pass.cpp | 1 + .../ranges_robust_against_proxy_iterators.pass.cpp | 1 + 5 files changed, 11 insertions(+) diff --git a/libcxx/docs/UsingLibcxx.rst b/libcxx/docs/UsingLibcxx.rst index 4d7d70e1d7901d..04324d0893309c 100644 --- a/libcxx/docs/UsingLibcxx.rst +++ b/libcxx/docs/UsingLibcxx.rst @@ -451,6 +451,7 @@ which no dialect declares as such (See the second form described above). * ``ranges::any_of`` * ``ranges::binary_search`` * ``ranges::clamp`` +* ``ranges::contains`` * ``ranges::count_if`` * ``ranges::count`` * ``ranges::equal_range`` diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.compile.pass.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.compile.pass.cpp index e9fab0c75a98e9..641fcd9233bc2e 100644 --- a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.compile.pass.cpp +++ b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.compile.pass.cpp @@ -45,6 +45,9 @@ void test_algorithms() { #if TEST_STD_VER >= 17 std::clamp(2, 1, 3); std::clamp(2, 3, 1, std::greater<int>()); +#endif +#if TEST_STD_VER >= 23 + std::ranges::contains(arr, arr + 1, 1); #endif std::count_if(std::begin(arr), std::end(arr), P()); std::count(std::begin(arr), std::end(arr), 1); diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp index d7a26d99e52233..1e3f537f01ed6e 100644 --- a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp +++ b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp @@ -60,6 +60,11 @@ void test_algorithms() { std::clamp(2, 1, 3, std::greater<int>()); #endif +#if TEST_STD_VER >= 23 + // expected-warning@+1 {{ignoring return value of function declared with 'nodiscard' attribute}} + std::ranges::contains(arr, arr + 1, 1); +#endif + // expected-warning@+1 {{ignoring return value of function declared with 'nodiscard' attribute}} std::count_if(std::begin(arr), std::end(arr), P()); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp index d17dce00e0b1ae..85fe6fbe10ef59 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp @@ -75,6 +75,7 @@ constexpr bool test_all() { test(std::ranges::any_of, in, &Foo::unary_pred, &Bar::val); test(std::ranges::all_of, in, &Foo::unary_pred, &Bar::val); #if TEST_STD_VER >= 23 + test(std::ranges::contains, in, x, &Bar::val); test(std::ranges::ends_with, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); #endif test(std::ranges::none_of, in, &Foo::unary_pred, &Bar::val); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp index 5c8aa0153a63c3..139f1999bc9dca 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -75,6 +75,7 @@ constexpr void run_tests() { test(std::ranges::any_of, in, unary_pred); test(std::ranges::all_of, in, unary_pred); #if TEST_STD_VER >= 23 + test(std::ranges::contains, in, x); test(std::ranges::ends_with, in, in2); #endif test(std::ranges::none_of, in, unary_pred); >From decac9ba83afbafa3ddf1372433f8839643b3c32 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Tue, 31 Oct 2023 16:35:56 -0700 Subject: [PATCH 17/21] Add benchmark tests --- libcxx/benchmarks/CMakeLists.txt | 1 + .../algorithms/ranges_contains.bench.cpp | 79 +++++++++++++++++++ 2 files changed, 80 insertions(+) create mode 100644 libcxx/benchmarks/algorithms/ranges_contains.bench.cpp diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt index 7591f34d938bf8..3a9e15f51a8bc0 100644 --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -184,6 +184,7 @@ set(BENCHMARK_TESTS algorithms/pop_heap.bench.cpp algorithms/pstl.stable_sort.bench.cpp algorithms/push_heap.bench.cpp + algorithms/ranges_contains.bench.cpp algorithms/ranges_ends_with.bench.cpp algorithms/ranges_make_heap.bench.cpp algorithms/ranges_make_heap_then_sort_heap.bench.cpp diff --git a/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp b/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp new file mode 100644 index 00000000000000..a2f4cc82d9c818 --- /dev/null +++ b/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include <algorithm> +#include <benchmark/benchmark.h> +#include <iterator> + +#include "test_iterators.h" +#include <vector> + +static std::vector<char> comparable_data; + +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; } +}; + +static void bm_contains(benchmark::State& state) { + std::vector<char> a(state.range(), 'a'); + + for (auto _ : state) { + benchmark::DoNotOptimize(a); + + benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'a')); + } +} +BENCHMARK(bm_contains)->RangeMultiplier(16)->Range(16, 16 << 20); + +static void bm_contains_with_trivially_comparable(benchmark::State& state) { + std::vector<TriviallyComparable<char>> a(state.range(), 'a'); + + for (auto _ : state) { + benchmark::DoNotOptimize(a); + + benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'a')); + } +} +BENCHMARK(bm_contains_with_trivially_comparable)->RangeMultiplier(16)->Range(16, 16 << 20); + +static void bm_contains_with_comparable(benchmark::State& state) { + std::vector<Comparable<char>> a(state.range(), 'a'); + + for (auto _ : state) { + benchmark::DoNotOptimize(a); + + benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'a')); + } +} +BENCHMARK(bm_contains_with_comparable)->RangeMultiplier(16)->Range(16, 16 << 20); + +BENCHMARK_MAIN(); \ No newline at end of file >From eb4ca7970cce2683b9141a70ad9ca86b7e5c3a0f Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Wed, 6 Dec 2023 11:42:17 -0800 Subject: [PATCH 18/21] Improve benchmark tests. --- libcxx/benchmarks/algorithms/ranges_contains.bench.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp b/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp index a2f4cc82d9c818..8fb20c0374b100 100644 --- a/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp +++ b/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp @@ -49,7 +49,7 @@ static void bm_contains(benchmark::State& state) { for (auto _ : state) { benchmark::DoNotOptimize(a); - benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'a')); + benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'B')); } } BENCHMARK(bm_contains)->RangeMultiplier(16)->Range(16, 16 << 20); @@ -60,7 +60,7 @@ static void bm_contains_with_trivially_comparable(benchmark::State& state) { for (auto _ : state) { benchmark::DoNotOptimize(a); - benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'a')); + benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'B')); } } BENCHMARK(bm_contains_with_trivially_comparable)->RangeMultiplier(16)->Range(16, 16 << 20); @@ -71,7 +71,7 @@ static void bm_contains_with_comparable(benchmark::State& state) { for (auto _ : state) { benchmark::DoNotOptimize(a); - benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'a')); + benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'B')); } } BENCHMARK(bm_contains_with_comparable)->RangeMultiplier(16)->Range(16, 16 << 20); >From 221cd0a91d61e2ac7d19bf27d657b378af967767 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Mon, 11 Dec 2023 23:15:54 -0800 Subject: [PATCH 19/21] Update benchmark tests and identity.h --- .../algorithms/ranges_contains.bench.cpp | 52 ++++--------------- libcxx/include/__functional/identity.h | 9 ++++ .../alg.contains/ranges.contains.pass.cpp | 15 +++--- 3 files changed, 27 insertions(+), 49 deletions(-) diff --git a/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp b/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp index 8fb20c0374b100..c11ec89de27eca 100644 --- a/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp +++ b/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp @@ -13,37 +13,7 @@ #include "test_iterators.h" #include <vector> -static std::vector<char> comparable_data; - -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; } -}; - -static void bm_contains(benchmark::State& state) { +static void bm_contains_char(benchmark::State& state) { std::vector<char> a(state.range(), 'a'); for (auto _ : state) { @@ -52,28 +22,28 @@ static void bm_contains(benchmark::State& state) { benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'B')); } } -BENCHMARK(bm_contains)->RangeMultiplier(16)->Range(16, 16 << 20); +BENCHMARK(bm_contains_char)->RangeMultiplier(16)->Range(16, 16 << 20); -static void bm_contains_with_trivially_comparable(benchmark::State& state) { - std::vector<TriviallyComparable<char>> a(state.range(), 'a'); +static void bm_contains_int(benchmark::State& state) { + std::vector<int> a(state.range(), 1); for (auto _ : state) { benchmark::DoNotOptimize(a); - benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'B')); + benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 2)); } } -BENCHMARK(bm_contains_with_trivially_comparable)->RangeMultiplier(16)->Range(16, 16 << 20); +BENCHMARK(bm_contains_int)->RangeMultiplier(16)->Range(16, 16 << 20); -static void bm_contains_with_comparable(benchmark::State& state) { - std::vector<Comparable<char>> a(state.range(), 'a'); +static void bm_contains_bool(benchmark::State& state) { + std::vector<bool> a(state.range(), true); for (auto _ : state) { benchmark::DoNotOptimize(a); - benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), 'B')); + benchmark::DoNotOptimize(std::ranges::contains(a.begin(), a.end(), false)); } } -BENCHMARK(bm_contains_with_comparable)->RangeMultiplier(16)->Range(16, 16 << 20); +BENCHMARK(bm_contains_bool)->RangeMultiplier(16)->Range(16, 16 << 20); -BENCHMARK_MAIN(); \ No newline at end of file +BENCHMARK_MAIN(); diff --git a/libcxx/include/__functional/identity.h b/libcxx/include/__functional/identity.h index ee92c4130e716b..4223fc9bf55506 100644 --- a/libcxx/include/__functional/identity.h +++ b/libcxx/include/__functional/identity.h @@ -11,6 +11,7 @@ #define _LIBCPP___FUNCTIONAL_IDENTITY_H #include <__config> +#include <__functional/reference_wrapper.h> #include <__type_traits/integral_constant.h> #include <__utility/forward.h> @@ -34,6 +35,10 @@ struct __identity { template <> struct __is_identity<__identity> : true_type {}; +template <> +struct __is_identity<reference_wrapper<__identity>> : true_type {}; +template <> +struct __is_identity<reference_wrapper<const __identity>> : true_type {}; #if _LIBCPP_STD_VER >= 20 @@ -49,6 +54,10 @@ struct identity { template <> struct __is_identity<identity> : true_type {}; +template <> +struct __is_identity<reference_wrapper<identity>> : true_type {}; +template <> +struct __is_identity<reference_wrapper<const identity>> : true_type {}; #endif // _LIBCPP_STD_VER >= 20 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 index 64a88e46f2c2fc..0c82b43c28ef99 100644 --- 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 @@ -154,15 +154,14 @@ constexpr void test_iterators() { constexpr bool test() { types::for_each( - types::type_list<char, short, int, long, long long>{}, - []<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>>(); - }); + types::type_list<char, short, int, long, long long>{}, []<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}; >From 853024539c80f2083490c5ed757434945c1429ca Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Tue, 12 Dec 2023 16:25:32 -0800 Subject: [PATCH 20/21] reformat --- libcxx/benchmarks/algorithms/ranges_contains.bench.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp b/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp index c11ec89de27eca..f36ebff9009585 100644 --- a/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp +++ b/libcxx/benchmarks/algorithms/ranges_contains.bench.cpp @@ -9,9 +9,9 @@ #include <algorithm> #include <benchmark/benchmark.h> #include <iterator> +#include <vector> #include "test_iterators.h" -#include <vector> static void bm_contains_char(benchmark::State& state) { std::vector<char> a(state.range(), 'a'); >From 529985622fed52dca3149220981732f61b91ce85 Mon Sep 17 00:00:00 2001 From: Zijun Zhao <zijunz...@google.com> Date: Tue, 12 Dec 2023 16:52:59 -0800 Subject: [PATCH 21/21] reformat test --- .../alg.contains/ranges.contains.pass.cpp | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-) 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 index 0c82b43c28ef99..b606eb410dd277 100644 --- 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 @@ -153,15 +153,14 @@ constexpr void test_iterators() { } constexpr bool test() { - types::for_each( - types::type_list<char, short, int, long, long long>{}, []<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>>(); - }); + types::for_each(types::type_list<char, short, int, long, long long>{}, []<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}; _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
