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,39 @@ 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, const _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, _VSTD::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/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -42,6 +42,15 @@ constexpr InputIterator // constexpr in C++20 find(InputIterator first, InputIterator last, const T& value); +template S, class T, class Proj = identity> + requires indirect_binary_predicate, const T*> + constexpr I ranges::find(I first, S last, const T& value, Proj proj = {}); // since C++20 + +template + requires indirect_binary_predicate, Proj>, const T*> + constexpr borrowed_iterator_t + ranges::find(R&& r, const T& value, Proj proj = {}); // since C++20 + template constexpr InputIterator // constexpr in C++20 find_if(InputIterator first, InputIterator last, Predicate pred); 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 { private header "__algorithm/equal_range.h" } module fill { private header "__algorithm/fill.h" } module fill_n { private header "__algorithm/fill_n.h" } - module find { private header "__algorithm/find.h" } + module find { + private header "__algorithm/find.h" + export __function_like + } module find_end { private header "__algorithm/find_end.h" } module find_first_of { private header "__algorithm/find_first_of.h" } module find_if { private header "__algorithm/find_if.h" } diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.pass.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.pass.cpp rename from libcxx/test/libcxx/diagnostics/nodiscard_extensions.pass.cpp rename to libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.pass.cpp --- a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.pass.cpp +++ b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.pass.cpp @@ -7,20 +7,21 @@ // //===----------------------------------------------------------------------===// -// Test that entities declared [[nodiscard]] as at extension by libc++, are +// Test that entities declared [[nodiscard]] as an extension by libc++, are // only actually declared such when _LIBCPP_ENABLE_NODISCARD is specified. // This test intentionally leaks memory, so it is unsupported under ASAN. // UNSUPPORTED: asan +// expected-no-diagnostics + // AppleClang9 and GCC 5 don't support C++17's implicitly synthesized // deduction guides from existing ctors, needed by default_searcher() below. // UNSUPPORTED: apple-clang-9 // UNSUPPORTED: gcc-5 -// All entities to which libc++ applies [[nodiscard]] as an extension should -// be tested here and in nodiscard_extensions.fail.cpp. They should also -// be listed in `UsingLibcxx.rst` in the documentation for the extension. +// Test that entities in are not declared [[nodiscard]] as a libc++ extension +// if the user doesn't request it explicitly. #include #include // to_integer diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp @@ -0,0 +1,38 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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 + +// Test that entities declared [[nodiscard]] as an extension by libc++, are +// only actually declared such when _LIBCPP_ENABLE_NODISCARD is specified. + +// All entities to which libc++ applies [[nodiscard]] as an extension should +// be tested here and in nodiscard_extensions.pass.cpp. They should also +// be listed in `UsingLibcxx.rst` in the documentation for the extension. + +// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_ENABLE_NODISCARD + +#include +#include + +#include + +int main() +{ + auto arr = std::array{0, 1, 2, 3, 4, 5}; + namespace ranges = std::ranges; + + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} + ranges::find(ranges::begin(arr), ranges::end(arr), 1); + + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} + ranges::find(arr, 1); +} diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.pass.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.pass.cpp @@ -0,0 +1,38 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// Test that entities declared [[nodiscard]] as an extension by libc++, are +// only actually declared such when _LIBCPP_ENABLE_NODISCARD is specified. + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// expected-no-diagnostics + +// Test that entities in are not declared [[nodiscard]] as a libc++ extension +// if the user doesn't request it explicitly. + +#include +#include + +#include + +#include "test_macros.h" + + +int main(int, char**) { + auto arr = std::array{0, 1, 2, 3, 4, 5}; + namespace ranges = std::ranges; + + ranges::find(ranges::begin(arr), ranges::end(arr), 1); + ranges::find(arr, 1); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/find_iter_sent_proj.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/find_iter_sent_proj.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/find_iter_sent_proj.pass.cpp @@ -0,0 +1,146 @@ +//===----------------------------------------------------------------------===// +// +// 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, gcc-11 + +// + +// ranges::find(r, value, proj) + +#include + +#include +#include +#include +#include +#include + +#include "complexity_invocable.h" +#include "test_macros.h" +#include "test_iterators.h" +#include "test_range.h" + +namespace ranges = std::ranges; + +template class I, class R, class T, class Proj> +constexpr void check_find_success(R&& r, + T const value, + Proj proj, + ranges::range_value_t const expected_value, + ranges::iterator_t const expected_position, + std::ptrdiff_t const exact_complexity) +{ + using iterator = I>; + { + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(ranges::begin(input), ranges::end(input), value, proj); + assert(*result == expected_value); + assert(result.base() == expected_position); + } + { + auto input = make_archetype_range(r); + auto complexity_proj = complexity_invocable(proj); + (void)ranges::find(ranges::begin(input), ranges::end(input), value, std::ref(complexity_proj)); + assert(complexity_proj.count() == exact_complexity); + } + } +} + +template class I, ranges::input_range R, class T, class Proj> +constexpr void check_find_fail(R&& r, T const value, Proj proj) +{ + using iterator = I>; + { + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(ranges::begin(input), ranges::end(input), value, proj); + assert(result.base() == ranges::end(r)); + } + { + auto input = make_archetype_range(r); + auto complexity_proj = complexity_invocable(proj); + (void)ranges::find(ranges::begin(input), ranges::end(input), value, std::ref(complexity_proj)); + assert(complexity_proj.count() == ranges::ssize(r)); + } + } +} + +template class I> +constexpr bool check_find() +{ + constexpr auto range = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + auto successor = [](auto const x) { return x + 1; }; + + check_find_success(range, 1, successor, 0, range.begin() + 0, 1); + check_find_success(range, 2, successor, 1, range.begin() + 1, 2); + check_find_success(range, 3, successor, 2, range.begin() + 2, 3); + check_find_success(range, 4, successor, 3, range.begin() + 3, 4); + check_find_success(range, 5, successor, 4, range.begin() + 4, 5); + check_find_success(range, 6, successor, 5, range.begin() + 5, 6); + check_find_success(range, 7, successor, 6, range.begin() + 6, 7); + check_find_success(range, 8, successor, 7, range.begin() + 7, 8); + check_find_success(range, 9, successor, 8, range.begin() + 8, 9); + check_find_success(range, 10, successor, 9, range.begin() + 9, 10); // successor makes this pass + + check_find_success(range, 1.0, successor, 0, range.begin() + 0, 1); + check_find_success(range, 2.0, successor, 1, range.begin() + 1, 2); + check_find_success(range, 3.0, successor, 2, range.begin() + 2, 3); + check_find_success(range, 4.0, successor, 3, range.begin() + 3, 4); + check_find_success(range, 5.0, successor, 4, range.begin() + 4, 5); + check_find_success(range, 6.0, successor, 5, range.begin() + 5, 6); + check_find_success(range, 7.0, successor, 6, range.begin() + 6, 7); + check_find_success(range, 8.0, successor, 7, range.begin() + 7, 8); + check_find_success(range, 9.0, successor, 8, range.begin() + 8, 9); + check_find_success(range, 10.0, successor, 9, range.begin() + 9, 10); // successor makes this pass + + check_find_fail(range, -10, successor); + check_find_fail(range, -1, successor); + check_find_fail(range, 0, successor); // successor makes this one fail + check_find_fail(range, 11, successor); // successor makes this one fail + check_find_fail(range, 363636, successor); + + check_find_fail(range, -1.0, successor); // successor makes this one fail + check_find_fail(range, 0.0, successor); // successor makes this one fail + check_find_fail(range, 1.2, successor); + check_find_fail(range, 2.3, successor); + check_find_fail(range, 3.4, successor); + check_find_fail(range, 4.5, successor); + check_find_fail(range, 5.6, successor); + check_find_fail(range, 6.7, successor); + check_find_fail(range, 7.8, successor); + check_find_fail(range, 8.9, successor); + check_find_fail(range, 11.0, successor); + + 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/ranges_find_iter_sent.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/ranges_find_iter_sent.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/ranges_find_iter_sent.pass.cpp @@ -0,0 +1,139 @@ +//===----------------------------------------------------------------------===// +// +// 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, gcc-11 + +// + +// ranges::find(first, last, value) + +#include + +#include +#include +#include +#include +#include + +#include "complexity_invocable.h" +#include "test_macros.h" +#include "test_iterators.h" +#include "test_range.h" + +namespace ranges = std::ranges; + +template class I, class R, class T> +constexpr void check_find_success(R&& r, + T const value, + ranges::iterator_t const expected_position, + std::ptrdiff_t const exact_complexity) +{ + using iterator = I>; + { + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(ranges::begin(input), ranges::end(input), value); + assert(*result == value); + assert(result.base() == expected_position); + } + { + auto input = make_complexity_range(r); + auto const result = ranges::find(ranges::begin(input), ranges::end(input), value); + assert(result.count() == exact_complexity); + } + } +} + +template class I, ranges::input_range R, class T> +constexpr void check_find_fail(R&& r, T const value) +{ + using iterator = I>; + { + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(ranges::begin(input), ranges::end(input), value); + assert(result.base() == ranges::end(r)); + } + { + auto input = make_complexity_range(r); + auto const result = ranges::find(ranges::begin(input), ranges::end(input), value); + assert(result.count() == ranges::ssize(r)); + } + } +} + +template class I> +constexpr bool check_find() +{ + constexpr auto range = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + check_find_success(range, 0, range.begin() + 0, 1); + check_find_success(range, 1, range.begin() + 1, 2); + check_find_success(range, 2, range.begin() + 2, 3); + check_find_success(range, 3, range.begin() + 3, 4); + check_find_success(range, 4, range.begin() + 4, 5); + check_find_success(range, 5, range.begin() + 5, 6); + check_find_success(range, 6, range.begin() + 6, 7); + check_find_success(range, 7, range.begin() + 7, 8); + check_find_success(range, 8, range.begin() + 8, 9); + check_find_success(range, 9, range.begin() + 9, 10); + + check_find_success(range, 0.0, range.begin() + 0, 1); + check_find_success(range, 1.0, range.begin() + 1, 2); + check_find_success(range, 2.0, range.begin() + 2, 3); + check_find_success(range, 3.0, range.begin() + 3, 4); + check_find_success(range, 4.0, range.begin() + 4, 5); + check_find_success(range, 5.0, range.begin() + 5, 6); + check_find_success(range, 6.0, range.begin() + 6, 7); + check_find_success(range, 7.0, range.begin() + 7, 8); + check_find_success(range, 8.0, range.begin() + 8, 9); + check_find_success(range, 9.0, range.begin() + 9, 10); + + check_find_fail(range, -10); + check_find_fail(range, -1); + check_find_fail(range, 10); + check_find_fail(range, 363636); + + check_find_fail(range, -1.0); + check_find_fail(range, 0.1); + check_find_fail(range, 1.2); + check_find_fail(range, 2.3); + check_find_fail(range, 3.4); + check_find_fail(range, 4.5); + check_find_fail(range, 5.6); + check_find_fail(range, 6.7); + check_find_fail(range, 7.8); + check_find_fail(range, 8.9); + check_find_fail(range, 10.0); + + 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/ranges_find_range.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/ranges_find_range.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/ranges_find_range.pass.cpp @@ -0,0 +1,167 @@ +//===----------------------------------------------------------------------===// +// +// 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, gcc-11 + +// + +// ranges::find(r, value) + +#include + +#include +#include +#include +#include +#include +#include + +#include "complexity_invocable.h" +#include "test_macros.h" +#include "test_iterators.h" +#include "test_range.h" + +namespace ranges = std::ranges; + +template class I, class R, class T> +constexpr void check_find_success(R&& r, + T const value, + ranges::iterator_t const expected_position, + std::ptrdiff_t const exact_complexity) +{ + using iterator = I>; + { + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(input, value); + assert(*result == value); + assert(result.base() == expected_position); + } + { + auto input = make_complexity_range(r); + auto const result = ranges::find(input, value); + assert(result.count() == exact_complexity); + } + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(std::move(input), value); + assert(*result == value); + assert(result.base() == expected_position); + } + { + auto input = make_complexity_range(r); + auto const result = ranges::find(std::move(input), value); + assert(result.count() == exact_complexity); + } + } +} + +template class I, ranges::input_range R, class T> +constexpr void check_find_fail(R&& r, T const value) +{ + using iterator = I>; + { + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(input, value); + assert(result.base() == ranges::end(r)); + } + { + auto input = make_complexity_range(r); + auto const result = ranges::find(input, value); + assert(result.count() == ranges::ssize(r)); + } + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(std::move(input), value); + assert(result.base() == ranges::end(r)); + } + { + auto input = make_complexity_range(r); + auto const result = ranges::find(std::move(input), value); + assert(result.count() == ranges::ssize(r)); + } + } +} + +template class I> +constexpr bool check_find() +{ + constexpr auto range = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + check_find_success(range, 0, range.begin() + 0, 1); + check_find_success(range, 1, range.begin() + 1, 2); + check_find_success(range, 2, range.begin() + 2, 3); + check_find_success(range, 3, range.begin() + 3, 4); + check_find_success(range, 4, range.begin() + 4, 5); + check_find_success(range, 5, range.begin() + 5, 6); + check_find_success(range, 6, range.begin() + 6, 7); + check_find_success(range, 7, range.begin() + 7, 8); + check_find_success(range, 8, range.begin() + 8, 9); + check_find_success(range, 9, range.begin() + 9, 10); + + check_find_success(range, 0.0, range.begin() + 0, 1); + check_find_success(range, 1.0, range.begin() + 1, 2); + check_find_success(range, 2.0, range.begin() + 2, 3); + check_find_success(range, 3.0, range.begin() + 3, 4); + check_find_success(range, 4.0, range.begin() + 4, 5); + check_find_success(range, 5.0, range.begin() + 5, 6); + check_find_success(range, 6.0, range.begin() + 6, 7); + check_find_success(range, 7.0, range.begin() + 7, 8); + check_find_success(range, 8.0, range.begin() + 8, 9); + check_find_success(range, 9.0, range.begin() + 9, 10); + + check_find_fail(range, -10); + check_find_fail(range, -1); + check_find_fail(range, 10); + check_find_fail(range, 363636); + + check_find_fail(range, -1.0); + check_find_fail(range, 0.1); + check_find_fail(range, 1.2); + check_find_fail(range, 2.3); + check_find_fail(range, 3.4); + check_find_fail(range, 4.5); + check_find_fail(range, 5.6); + check_find_fail(range, 6.7); + check_find_fail(range, 7.8); + check_find_fail(range, 8.9); + check_find_fail(range, 10.0); + + 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(); + + ASSERT_SAME_TYPE(decltype(ranges::find(std::vector(10), 6)), + ranges::dangling); + + ASSERT_SAME_TYPE(decltype(ranges::find(std::vector(10), 6, {})), + ranges::dangling); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/ranges_find_range_proj.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/ranges_find_range_proj.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/ranges_find_range_proj.pass.cpp @@ -0,0 +1,176 @@ +//===----------------------------------------------------------------------===// +// +// 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, gcc-11 + +// + +// ranges::find(r, value, proj) + +#include + +#include +#include +#include +#include +#include +#include + +#include "complexity_invocable.h" +#include "test_macros.h" +#include "test_iterators.h" +#include "test_range.h" + +namespace ranges = std::ranges; + +template class I, class R, class T, class Proj> +constexpr void check_find_success(R&& r, + T const value, + Proj proj, + ranges::range_value_t const expected_value, + ranges::iterator_t const expected_position, + std::ptrdiff_t const exact_complexity) +{ + using iterator = I>; + { + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(input, value, proj); + assert(*result == expected_value); + assert(result.base() == expected_position); + } + { + auto input = make_archetype_range(r); + auto complexity_proj = complexity_invocable(proj); + (void)ranges::find(input, value, std::ref(complexity_proj)); + assert(complexity_proj.count() == exact_complexity); + } + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(std::move(input), value, proj); + assert(*result == expected_value); + assert(result.base() == expected_position); + } + { + auto input = make_archetype_range(r); + auto complexity_proj = complexity_invocable(proj); + (void)ranges::find(std::move(input), value, std::ref(complexity_proj)); + assert(complexity_proj.count() == exact_complexity); + } + } +} + +template class I, ranges::input_range R, class T, class Proj> +constexpr void check_find_fail(R&& r, T const value, Proj proj) +{ + using iterator = I>; + { + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(input, value, proj); + assert(result.base() == ranges::end(r)); + } + { + auto input = make_archetype_range(r); + auto complexity_proj = complexity_invocable(proj); + (void)ranges::find(input, value, std::ref(complexity_proj)); + assert(complexity_proj.count() == ranges::ssize(r)); + } + { + auto input = make_archetype_range(r); + std::same_as auto const result = ranges::find(std::move(input), value, proj); + assert(result.base() == ranges::end(r)); + } + { + auto input = make_archetype_range(r); + auto complexity_proj = complexity_invocable(proj); + (void)ranges::find(std::move(input), value, std::ref(complexity_proj)); + assert(complexity_proj.count() == ranges::ssize(r)); + } + } +} + +template class I> +constexpr bool check_find() +{ + constexpr auto range = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + auto successor = [](auto const x) { return x + 1; }; + + check_find_success(range, 1, successor, 0, range.begin() + 0, 1); + check_find_success(range, 2, successor, 1, range.begin() + 1, 2); + check_find_success(range, 3, successor, 2, range.begin() + 2, 3); + check_find_success(range, 4, successor, 3, range.begin() + 3, 4); + check_find_success(range, 5, successor, 4, range.begin() + 4, 5); + check_find_success(range, 6, successor, 5, range.begin() + 5, 6); + check_find_success(range, 7, successor, 6, range.begin() + 6, 7); + check_find_success(range, 8, successor, 7, range.begin() + 7, 8); + check_find_success(range, 9, successor, 8, range.begin() + 8, 9); + check_find_success(range, 10, successor, 9, range.begin() + 9, 10); // successor makes this pass + + check_find_success(range, 1.0, successor, 0, range.begin() + 0, 1); + check_find_success(range, 2.0, successor, 1, range.begin() + 1, 2); + check_find_success(range, 3.0, successor, 2, range.begin() + 2, 3); + check_find_success(range, 4.0, successor, 3, range.begin() + 3, 4); + check_find_success(range, 5.0, successor, 4, range.begin() + 4, 5); + check_find_success(range, 6.0, successor, 5, range.begin() + 5, 6); + check_find_success(range, 7.0, successor, 6, range.begin() + 6, 7); + check_find_success(range, 8.0, successor, 7, range.begin() + 7, 8); + check_find_success(range, 9.0, successor, 8, range.begin() + 8, 9); + check_find_success(range, 10.0, successor, 9, range.begin() + 9, 10); // successor makes this pass + + check_find_fail(range, -10, successor); + check_find_fail(range, -1, successor); + check_find_fail(range, 0, successor); // successor makes this one fail + check_find_fail(range, 11, successor); // successor makes this one fail + check_find_fail(range, 363636, successor); + + check_find_fail(range, -1.0, successor); // successor makes this one fail + check_find_fail(range, 0.0, successor); // successor makes this one fail + check_find_fail(range, 1.2, successor); + check_find_fail(range, 2.3, successor); + check_find_fail(range, 3.4, successor); + check_find_fail(range, 4.5, successor); + check_find_fail(range, 5.6, successor); + check_find_fail(range, 6.7, successor); + check_find_fail(range, 7.8, successor); + check_find_fail(range, 8.9, successor); + check_find_fail(range, 11.0, successor); + + 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(); + + ASSERT_SAME_TYPE(decltype(ranges::find(std::vector(10), 6)), + ranges::dangling); + + ASSERT_SAME_TYPE(decltype(ranges::find(std::vector(10), 6, {})), + ranges::dangling); + + 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,110 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_range.h" +#include "test_standard_function.h" + +static_assert(is_function_like()); + +namespace ranges = std::ranges; + +namespace std::ranges { + // TODO: replace with proper iota_view + template + class iota_view { + struct iterator; + public: + iterator begin(); + default_sentinel_t end() const; + }; +} // namespace 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 no_unqualified_lookup() { + auto identity = ranges::iota_view(); + static_assert(!requires(T value) { find(ranges::begin(identity), ranges::end(identity), value); }); + static_assert(!requires(T value) { find(ranges::begin(identity), ranges::end(identity), value.first, &T::first); }); + static_assert(!requires(T value) { find(identity, value); }); + static_assert(!requires(T value) { find(identity, value.first, &T::first); }); + return true; +}; + +static_assert(no_unqualified_lookup>()); + +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/complexity_invocable.h b/libcxx/test/support/complexity_invocable.h new file mode 100644 --- /dev/null +++ b/libcxx/test/support/complexity_invocable.h @@ -0,0 +1,52 @@ +//===----------------------------------------------------------------------===// +// +// 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 LIBCXX_TEST_SUPPORT_TEST_ALGORITHM_H +#define LIBCXX_TEST_SUPPORT_TEST_ALGORITHM_H + +#include "test_macros.h" + +#if TEST_STD_VER < 20 +#error This file requires -std=c++20 or later. +#endif + +#include +#include +#include +#include + +// `complexity_invocable` is an invocable adaptor that's used to measure the number of calls to a +// predicate or projection. It differs from `unary_counting_predicate` and `binary_counting_predicate` +// in two ways: +// 1. Most importantly, it isn't limited to predicates, and so works with invocables returning +// something other than Boolean values. +// 2. It can store lambdas and works in constexpr contexts. +template +class complexity_invocable { +public: + constexpr complexity_invocable(F f) + : f_(std::move(f)) + {} + + template + requires std::invocable + constexpr decltype(auto) operator()(Args&&... args) noexcept(std::is_nothrow_invocable_v) + { + ++count_; + return std::invoke(f_, std::forward(args)...); + } + + constexpr std::ptrdiff_t count() const + { + return count_; + } +private: + F f_; + std::ptrdiff_t count_ = 0; +}; + +#endif // LIBCXX_TEST_SUPPORT_TEST_ALGORITHM_H 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 @@ -914,6 +914,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: @@ -927,6 +934,11 @@ constexpr const I& base() const& { return base_; } constexpr I base() && { return std::move(base_); } + template + requires sentinel_for_base + constexpr bool operator==(I2 const& other) const { + return base_ == other.base(); + } private: I base_ = I(); }; @@ -987,6 +999,157 @@ friend auto operator<=>(const three_way_contiguous_iterator&, const three_way_contiguous_iterator&) = default; }; +// `complexity_iterator` is an iterator adaptor that's used to measure the number of applications of +// a predicate/projection when there's no predicate to measure (e.g. `ranges::find`). +template +class complexity_iterator { +public: + using value_type = std::iter_value_t; + using difference_type = std::iter_difference_t; + using iterator_concept = iterator_concept_t; + + constexpr complexity_iterator() requires std::default_initializable = default; + + constexpr explicit complexity_iterator(I i) + : base_(std::move(i)) + {} + + [[nodiscard]] constexpr difference_type count() const + { + return dereference_count_; + } + + constexpr decltype(auto) base() const& + { + return base_.base(); + } + + constexpr decltype(auto) base() && + { + return std::move(base_).base(); + } + + constexpr std::iter_reference_t operator*() const + { + ++dereference_count_; + return *base_; + } + + constexpr std::iter_reference_t operator[](difference_type const n) const + requires std::random_access_iterator + { + ++dereference_count_; + return base_[n]; + } + + constexpr complexity_iterator& operator++() + { + ++base_; + return *this; + } + + constexpr void operator++(int) { ++*this; } + + constexpr complexity_iterator operator++(int) + requires std::forward_iterator + { + auto temp = *this; + ++*this; + return temp; + } + + constexpr complexity_iterator& operator--() + requires std::bidirectional_iterator + { + --base_; + return *this; + } + + constexpr complexity_iterator operator--(int) + requires std::bidirectional_iterator + { + auto temp = *this; + --*this; + return temp; + } + + constexpr complexity_iterator& operator+=(difference_type const n) + requires std::random_access_iterator + { + base_ += n; + return *this; + } + + constexpr complexity_iterator& operator-=(difference_type const n) + requires std::random_access_iterator + { + base_ -= n; + return *this; + } + + constexpr friend complexity_iterator operator+(complexity_iterator i, difference_type const n) + requires std::random_access_iterator + { + return i += n; + } + + constexpr friend complexity_iterator operator+(difference_type const n, complexity_iterator i) + requires std::random_access_iterator + { + return i += n; + } + + constexpr friend complexity_iterator operator-(complexity_iterator i, difference_type const n) + requires std::random_access_iterator + { + return i -= n; + } + + constexpr friend difference_type operator-(complexity_iterator const& x, complexity_iterator const& y) + requires std::sized_sentinel_for + { + return x - y; + } + + constexpr bool operator==(complexity_iterator const& other) const requires std::sentinel_for + { + return base_ == other.base_; + } + + template S> + constexpr bool operator==(S const last) const + { + return base_ == last; + } + + constexpr friend bool operator<(complexity_iterator const& x, complexity_iterator const& y) + requires std::random_access_iterator + { + return x.base_ < y.base_; + } + + constexpr friend bool operator>(complexity_iterator const& x, complexity_iterator const& y) + requires std::random_access_iterator + { + return y < x; + } + + constexpr friend bool operator<=(complexity_iterator const& x, complexity_iterator const& y) + requires std::random_access_iterator + { + return !(y < x); + } + + constexpr friend bool operator>=(complexity_iterator const& x, complexity_iterator const& y) + requires std::random_access_iterator + { + return !(x < y); + } +private: + I base_; + mutable difference_type dereference_count_ = 0; +}; + // clang-format on #endif // TEST_STD_VER > 17 && defined(__cpp_lib_concepts) diff --git a/libcxx/test/support/test_range.h b/libcxx/test/support/test_range.h --- a/libcxx/test/support/test_range.h +++ b/libcxx/test/support/test_range.h @@ -61,5 +61,18 @@ sentinel end(); sentinel end() const; }; +template class I, class R> +constexpr auto make_archetype_range(R&& r) +{ + return std::ranges::subrange(I(std::ranges::begin(r)), sentinel_wrapper(std::ranges::end(r))); +} + +template class I, class R> +constexpr auto make_complexity_range(R&& r) +{ + return std::ranges::subrange(complexity_iterator(I(std::ranges::begin(r))), sentinel_wrapper(std::ranges::end(r))); +} + +// clang-format on #endif // LIBCXX_TEST_SUPPORT_TEST_RANGE_H