diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -16,6 +16,7 @@ __algorithm/equal.h __algorithm/fill_n.h __algorithm/fill.h + __algorithm/find.h __algorithm/find_end.h __algorithm/find_first_of.h __algorithm/find_if_not.h diff --git a/libcxx/include/__algorithm/find.h b/libcxx/include/__algorithm/find.h --- a/libcxx/include/__algorithm/find.h +++ b/libcxx/include/__algorithm/find.h @@ -11,6 +11,18 @@ #define _LIBCPP___ALGORITHM_FIND_H #include <__config> +#include <__function_like.h> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/operations.h> +#include <__functional/ranges_operations.h> +#include <__functional/reference_wrapper.h> +#include <__functional_base> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header @@ -30,6 +42,37 @@ return __first; } +#if !defined(_LIBCPP_HAS_NO_RANGES) + +namespace ranges { + struct __find_fn final : __function_like { + constexpr explicit __find_fn(__tag __x) noexcept : __function_like(__x) {} + + template _Sp, class _Tp, class _Proj = identity> + requires indirect_binary_predicate, const _Tp*> + _LIBCPP_NODISCARD_EXT constexpr _Ip operator()(_Ip __first, _Sp __last, const _Tp& __value, _Proj __proj = {}) const + { + for (; __first != __last; ++__first) { + if (_VSTD::invoke(__proj, *__first) == __value) { + break; + } + } + return __first; + } + + template + requires indirect_binary_predicate, _Proj>, const _Tp*> + _LIBCPP_NODISCARD_EXT constexpr borrowed_iterator_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Proj __proj = {}) const + { + return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::ref(__proj)); + } + }; + + inline constexpr auto find = __find_fn(__function_like::__tag()); +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + _LIBCPP_END_NAMESPACE_STD _LIBCPP_POP_MACROS diff --git a/libcxx/include/__functional/identity.h b/libcxx/include/__functional/identity.h --- a/libcxx/include/__functional/identity.h +++ b/libcxx/include/__functional/identity.h @@ -30,6 +30,7 @@ using is_transparent = void; }; + #endif // _LIBCPP_STD_VER > 17 _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -236,7 +236,10 @@ module equal_range { header "__algorithm/equal_range.h" } module fill { header "__algorithm/fill.h" } module fill_n { header "__algorithm/fill_n.h" } - module find { header "__algorithm/find.h" } + module find { + header "__algorithm/find.h" + export __function_like + } module find_end { header "__algorithm/find_end.h" } module find_first_of { header "__algorithm/find_first_of.h" } module find_if { header "__algorithm/find_if.h" } diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.pass.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.pass.cpp --- a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.pass.cpp +++ b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.pass.cpp @@ -70,6 +70,9 @@ std::find_if_not(std::begin(arr), std::end(arr), P()); std::find_if(std::begin(arr), std::end(arr), P()); std::find(std::begin(arr), std::end(arr), 1); +#if TEST_STD_VER >= 20 + std::ranges::find(std::begin(arr), std::end(arr), 1); +#endif std::get_temporary_buffer(1); // intentional memory leak. std::includes(std::begin(arr), std::end(arr), std::begin(arr), std::end(arr)); std::includes(std::begin(arr), std::end(arr), std::begin(arr), std::end(arr), diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp --- a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp +++ b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp @@ -116,6 +116,11 @@ // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} std::find(std::begin(arr), std::end(arr), 1); +#if TEST_STD_VER >= 20 + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} + std::ranges::find(std::begin(arr), std::end(arr), 1); +#endif + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} std::get_temporary_buffer(1); diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges::find/ranges_find.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges::find/ranges_find.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges::find/ranges_find.pass.cpp @@ -0,0 +1,153 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// + +// ranges::find + +#include + +#include +#include +#include +#include +#include + +#include "test_macros.h" +#include "test_iterators.h" +#include "test_range.h" + +template +struct projectable { + T x; + T y = x + 1; + + template U> + constexpr bool operator==(projectable const& other) const noexcept { + return x == other.x && y == other.y; + } + + template + requires std::convertible_to + operator projectable() const { return projectable{.x = static_cast(x), .y = static_cast(y)}; } +}; + +template +struct std::common_type, projectable> { using type = projectable>; }; + +template class I> +constexpr bool check_find() +{ + namespace ranges = std::ranges; + + using array_t = std::array, 10>; + auto range = array_t{{{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}}}; + auto subrange = std::ranges::subrange(I(range.begin()), sentinel_wrapper(range.end())); + + { + auto const iterator_result = ranges::find(subrange.begin(), subrange.end(), projectable{6}); + assert(iterator_result.base() == range.begin() + 6); + ASSERT_SAME_TYPE(decltype(iterator_result), I const); + + auto const range_result = ranges::find(subrange, projectable{6}); + assert(range_result.base() == iterator_result.base()); + ASSERT_SAME_TYPE(decltype(range_result), I const); + + ASSERT_SAME_TYPE(decltype(ranges::find(ranges::subrange(range), projectable{6})), + ranges::dangling); + } + { + auto const iterator_result = ranges::find(subrange.begin(), subrange.end(), projectable{3.0}); + assert(iterator_result.base() == range.begin() + 3); + ASSERT_SAME_TYPE(decltype(iterator_result), I const); + + auto const range_result = ranges::find(subrange, projectable{3.0}); + assert(range_result.base() == iterator_result.base()); + ASSERT_SAME_TYPE(decltype(range_result), I const); + + ASSERT_SAME_TYPE(decltype(ranges::find(ranges::subrange(range), projectable{3.0})), + ranges::dangling); + } + { + auto const iterator_result = ranges::find(subrange.begin(), subrange.end(), projectable{3.7}); + assert(iterator_result.base() == range.end()); + ASSERT_SAME_TYPE(decltype(iterator_result), I const); + + auto const range_result = ranges::find(subrange, projectable{3.7}); + assert(range_result.base() == iterator_result.base()); + ASSERT_SAME_TYPE(decltype(iterator_result), I const); + + ASSERT_SAME_TYPE(decltype(ranges::find(ranges::subrange(range), projectable{3.7})), + ranges::dangling); + } + { + auto const iterator_result = ranges::find(subrange.begin(), subrange.end(), 6, &projectable::y); + assert(iterator_result.base() == range.begin() + 5); + ASSERT_SAME_TYPE(decltype(iterator_result), I const); + + auto const range_result = ranges::find(subrange, 6, &projectable::y); + assert(range_result.base() == iterator_result.base()); + ASSERT_SAME_TYPE(decltype(range_result), I const); + + ASSERT_SAME_TYPE(decltype(ranges::find(ranges::subrange(range), 6, &projectable::y)), + ranges::dangling); + } + { + auto const iterator_result = ranges::find(subrange.begin(), subrange.end(), 3.0, &projectable::y); + assert(iterator_result.base() == range.begin() + 2); + ASSERT_SAME_TYPE(decltype(iterator_result), I const); + + auto const range_result = ranges::find(subrange, 3.0, &projectable::y); + assert(range_result.base() == iterator_result.base()); + ASSERT_SAME_TYPE(decltype(range_result), I const); + + ASSERT_SAME_TYPE(decltype(ranges::find(ranges::subrange(range), 3.0, &projectable::y)), + ranges::dangling); + } + { + auto const iterator_result = ranges::find(subrange.begin(), subrange.end(), 3.7, &projectable::y); + assert(iterator_result.base() == range.end()); + ASSERT_SAME_TYPE(decltype(iterator_result), I const); + + auto const range_result = ranges::find(subrange, 3.7, &projectable::y); + assert(range_result.base() == iterator_result.base()); + ASSERT_SAME_TYPE(decltype(range_result), I const); + + ASSERT_SAME_TYPE(decltype(ranges::find(ranges::subrange(range), 3.7, &projectable::y)), + ranges::dangling); + } + + return true; +} + +int main(int, char**) +{ + static_assert(check_find()); + check_find(); + + static_assert(check_find()); + check_find(); + + static_assert(check_find()); + check_find(); + + static_assert(check_find()); + check_find(); + + static_assert(check_find()); + check_find(); + + static_assert(check_find()); + check_find(); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges::find/special_function.compile.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges::find/special_function.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges::find/special_function.compile.pass.cpp @@ -0,0 +1,97 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 +// XFAIL: clang-11 && modules-build +// XFAIL: clang-12 && modules-build + +// ranges::find + +#include + +#include +#include +#include + +#include "test_standard_function.h" + +static_assert(is_function_like()); + +namespace stdr = std::ranges; + +// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent +// name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for +// the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup. +template +constexpr bool unqualified_lookup_works = requires(stdr::subrange r, T const value) { + find(stdr::begin(r), stdr::end(r), value); + find(stdr::begin(r), stdr::end(r), value, &T::first); + find(r, value); + find(r, value, &T::first); +}; + +static_assert(!unqualified_lookup_works>); + +namespace test { +template +struct iterator { + using value_type = std::pair; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + + iterator() = default; + + value_type operator*() const; + iterator& operator++(); + iterator operator++(int); + + bool operator==(iterator const&) const = default; +}; + +template +struct range { + std::pair const* begin() const; + std::pair const* end() const; +}; + +template +void find(iterator, iterator, std::pair const&) { + static_assert(std::same_as); +} + +template +void find(iterator, iterator, int, Proj) { + static_assert(std::same_as); +} + +template +void find(R&&, std::pair const&) { + static_assert(std::same_as); +} + +template +void find(R&&, int, Proj) { + static_assert(std::same_as); +} +} // namespace test + +// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a +// function call ([expr.call]), they inhibit argument-dependent name lookup. +void adl_inhibition() { + using std::ranges::find; + + test::iterator x; + (void)find(x, x, std::pair{10, 20}); + (void)find(x, x, 10, &std::pair::first); + + test::range r; + (void)find(r, std::pair{10, 20}); + (void)find(r, 10, &std::pair::first); +} diff --git a/libcxx/test/support/test_iterators.h b/libcxx/test/support/test_iterators.h --- a/libcxx/test/support/test_iterators.h +++ b/libcxx/test/support/test_iterators.h @@ -861,6 +861,13 @@ difference_type stride_displacement_ = 0; }; +template +concept sentinel_for_base = requires(U const& u) { + u.base(); + requires std::input_or_output_iterator>; + requires std::equality_comparable_with; +}; + template class sentinel_wrapper { public: @@ -871,6 +878,11 @@ return base_ == other; } + template + requires sentinel_for_base + constexpr bool operator==(I2 const& other) const { + return base_ == other.base(); + } private: I base_ = I(); };