diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -91,6 +91,7 @@ __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 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_contains.h @@ -0,0 +1,69 @@ +//===----------------------------------------------------------------------===// +// +// 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_starts_with.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.h> +#include <__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 + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool + __compare_single_element(_Iter __first, _Sent __last, const _Type& __value, _Proj& __proj = {}) const { + auto __pred = [&](auto&& __e) { return std::forward(__e) == __value; }; + for (; __first != __last; ++__first) { + if (std::invoke(std::move(__pred), std::invoke(std::move(__proj), *__first))) + return true; + } + return false; + } + + template _Sent, class _Type, class _Proj = identity> + requires indirect_binary_predicate, const _Type*> + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool + operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) const { + return __compare_single_element(std::move(__first), std::move(__last), __value, __proj); + } + + template + requires indirect_binary_predicate, _Proj>, const _Type*> + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool + operator()(_Range&& __range, const _Type& __value, _Proj __proj = {}) const { + return __compare_single_element(ranges::begin(__range), ranges::end(__range), __value, __proj); + } +}; +} // 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 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -226,6 +226,14 @@ template using copy_backward_result = in_out_result; // since C++20 + template S, class T, class Proj = identity> + requires indirect_binary_predicate, const T*> + constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {}); // since C++23 + + template + requires indirect_binary_predicate, Proj>, const T*> + constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {}); // since C++23 + template S, weakly_incrementable O> requires indirectly_copyable constexpr ranges::copy_result ranges::copy(I first, S last, O result); // since C++20 @@ -1812,6 +1820,7 @@ #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/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -356,6 +356,7 @@ private header "__algorithm/ranges_clamp.h" export functional.__functional.ranges_operations } + module ranges_contains { private header "__algorithm/ranges_contains.h" } module ranges_copy { private header "__algorithm/ranges_copy.h" export algorithm.__algorithm.in_out_result diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -80,6 +80,10 @@ (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 > 20 + (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/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -128,6 +128,7 @@ #include <__algorithm/ranges_any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_any_of.h'}} #include <__algorithm/ranges_binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_binary_search.h'}} #include <__algorithm/ranges_clamp.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_clamp.h'}} +#include <__algorithm/ranges_contains.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_contains.h'}} #include <__algorithm/ranges_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy.h'}} #include <__algorithm/ranges_copy_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_backward.h'}} #include <__algorithm/ranges_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_if.h'}} 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 --- /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 +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 +// template S, class T, class Proj = identity> +// requires indirect_binary_predicate, const T*> +// constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {}); // since C++23 + +// template +// requires indirect_binary_predicate, Proj>, const T*> +// constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {}); // since C++23 + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +struct NotEqualityComparable {}; + +template +concept HasContainsIt = requires(Iter iter, Sent sent) { std::ranges::contains(iter, sent, *iter); }; + +static_assert(HasContainsIt); +static_assert(!HasContainsIt); +static_assert(!HasContainsIt); +static_assert(!HasContainsIt); +static_assert(!HasContainsIt); +static_assert(!HasContainsIt, SentinelForNotSemiregular>); +static_assert(!HasContainsIt, InputRangeNotSentinelEqualityComparableWith>); + +static_assert(!HasContainsIt); +static_assert(!HasContainsIt); + +template +concept HasContainsR = requires(Range range) { std::ranges::contains(range, ValT{}); }; + +static_assert(HasContainsR, int>); +static_assert(!HasContainsR); +static_assert(!HasContainsR, NotEqualityComparable>); +static_assert(!HasContainsR); +static_assert(!HasContainsR); +static_assert(!HasContainsR); +static_assert(!HasContainsR); +static_assert(!HasContainsR); + +static std::vector comparable_data; + +// clang-format off +template +constexpr void test_iterators() { + using ValueT = std::iter_value_t; + { // simple tests + { + ValueT a[] = {1, 2, 3, 4, 5, 6}; + std::same_as 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 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 TriviallyComparable { + ElementT el_; + +public: + TEST_CONSTEXPR TriviallyComparable(ElementT el) : el_(el) {} + bool operator==(const TriviallyComparable&) const = default; +}; + +template +class Comparable { + IndexT index_; + +public: + Comparable(IndexT i) + : index_([&]() { + IndexT size = static_cast(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, TriviallyComparable>{}, + [] { + types::for_each(types::cpp20_input_iterator_list{}, + [] { + if constexpr (std::forward_iterator) + test_iterators(); + test_iterators>(); + test_iterators>(); + }); + }); + + { + // 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>{}, + [] { + types::for_each(types::cpp20_input_iterator_list{}, + [] { + if constexpr (std::forward_iterator) + test_iterators(); + test_iterators>(); + test_iterators>(); + }); + }); + + 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 --- 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::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));