diff options
author | Christopher Di Bella <cjdb@google.com> | 2023-12-19 21:57:50 -0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-12-19 21:57:50 -0800 |
commit | 3903438860b6eebf53a912c672560e1e55311220 (patch) | |
tree | 0ba9bb1c3e189e73a5f65eafcbed0205355480c3 | |
parent | 037c220702802ea8f26c359c30b69a1c8d33ef0d (diff) | |
download | llvm-3903438860b6eebf53a912c672560e1e55311220.zip llvm-3903438860b6eebf53a912c672560e1e55311220.tar.gz llvm-3903438860b6eebf53a912c672560e1e55311220.tar.bz2 |
[libcxx] adds ranges::fold_left_with_iter and ranges::fold_left (#75259)
Notable things in this commit:
* refactors `__indirect_binary_left_foldable`, making it slightly
different (but equivalent) to _`indirect-binary-left-foldable`_, which
improves readability (a [patch to the Working Paper][patch] was made)
* omits `__cpo` namespace, since it is not required for implementing
niebloids (a cleanup should happen in 2024)
* puts tests ensuring invocable robustness and dangling correctness
inside the correctness testing to ensure that the algorithms' results
are still correct
[patch]: https://github.com/cplusplus/draft/pull/6734
18 files changed, 1062 insertions, 32 deletions
diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv index 17c8953..2fe530b 100644 --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -10,3 +10,9 @@ C++23,`shift_right <https://wg21.link/p2440r1>`_,Unassigned,No patch yet,Not sta C++23,`iota (algorithm) <https://wg21.link/p2440r1>`_,Unassigned,No patch yet,Not started C++23,`fold <https://wg21.link/p2322r5>`_,Unassigned,No patch yet,Not started C++23,`contains <https://wg21.link/p2302r2>`_,Zijun Zhao,No patch yet,In Progress +C++23,`fold_left_with_iter <https://wg21.link/p2322r6>`_,Christopher Di Bella,N/A,Complete +C++23,`fold_left <https://wg21.link/p2322r6>`_,Christopher Di Bella,N/A,Complete +C++23,`fold_left_first_with_iter <https://wg21.link/p2322r6>`_,Christopher Di Bella,N/A,In progress +C++23,`fold_left_first <https://wg21.link/p2322r6>`_,Christopher Di Bella,N/A,In progress +C++23,`fold_right <https://wg21.link/p2322r6>`_,Christopher Di Bella,N/A,In progress +C++23,`fold_right_last <https://wg21.link/p2322r6>`_,Christopher Di Bella,N/A,In progress diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index f1e5a24..746d581 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -23,6 +23,7 @@ set(files __algorithm/find_if.h __algorithm/find_if_not.h __algorithm/find_segment_if.h + __algorithm/fold.h __algorithm/for_each.h __algorithm/for_each_n.h __algorithm/for_each_segment.h diff --git a/libcxx/include/__algorithm/fold.h b/libcxx/include/__algorithm/fold.h new file mode 100644 index 0000000..88e6814 --- /dev/null +++ b/libcxx/include/__algorithm/fold.h @@ -0,0 +1,125 @@ +// -*- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_FOLD_H +#define _LIBCPP___ALGORITHM_FOLD_H + +#include <__concepts/assignable.h> +#include <__concepts/convertible_to.h> +#include <__concepts/invocable.h> +#include <__concepts/movable.h> +#include <__config> +#include <__functional/invoke.h> +#include <__functional/reference_wrapper.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__type_traits/decay.h> +#include <__type_traits/invoke.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 23 + +namespace ranges { +template <class _Ip, class _Tp> +struct in_value_result { + _LIBCPP_NO_UNIQUE_ADDRESS _Ip in; + _LIBCPP_NO_UNIQUE_ADDRESS _Tp value; + + template <class _I2, class _T2> + requires convertible_to<const _Ip&, _I2> && convertible_to<const _Tp&, _T2> + _LIBCPP_HIDE_FROM_ABI constexpr operator in_value_result<_I2, _T2>() const& { + return {in, value}; + } + + template <class _I2, class _T2> + requires convertible_to<_Ip, _I2> && convertible_to<_Tp, _T2> + _LIBCPP_HIDE_FROM_ABI constexpr operator in_value_result<_I2, _T2>() && { + return {std::move(in), std::move(value)}; + } +}; + +template <class _Ip, class _Tp> +using fold_left_with_iter_result = in_value_result<_Ip, _Tp>; + +template <class _Fp, class _Tp, class _Ip, class _Rp, class _Up = decay_t<_Rp>> +concept __indirectly_binary_left_foldable_impl = + convertible_to<_Rp, _Up> && // + movable<_Tp> && // + movable<_Up> && // + convertible_to<_Tp, _Up> && // + invocable<_Fp&, _Up, iter_reference_t<_Ip>> && // + assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Ip>>>; + +template <class _Fp, class _Tp, class _Ip> +concept __indirectly_binary_left_foldable = + copy_constructible<_Fp> && // + invocable<_Fp&, _Tp, iter_reference_t<_Ip>> && // + __indirectly_binary_left_foldable_impl<_Fp, _Tp, _Ip, invoke_result_t<_Fp&, _Tp, iter_reference_t<_Ip>>>; + +struct __fold_left_with_iter { + template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, __indirectly_binary_left_foldable<_Tp, _Ip> _Fp> + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI static constexpr auto + operator()(_Ip __first, _Sp __last, _Tp __init, _Fp __f) { + using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Ip>>>; + + if (__first == __last) { + return fold_left_with_iter_result<_Ip, _Up>{std::move(__first), _Up(std::move(__init))}; + } + + _Up __result = std::invoke(__f, std::move(__init), *__first); + for (++__first; __first != __last; ++__first) { + __result = std::invoke(__f, std::move(__result), *__first); + } + + return fold_left_with_iter_result<_Ip, _Up>{std::move(__first), std::move(__result)}; + } + + template <input_range _Rp, class _Tp, __indirectly_binary_left_foldable<_Tp, iterator_t<_Rp>> _Fp> + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Rp&& __r, _Tp __init, _Fp __f) { + auto __result = operator()(ranges::begin(__r), ranges::end(__r), std::move(__init), std::ref(__f)); + + using _Up = decay_t<invoke_result_t<_Fp&, _Tp, range_reference_t<_Rp>>>; + return fold_left_with_iter_result<borrowed_iterator_t<_Rp>, _Up>{std::move(__result.in), std::move(__result.value)}; + } +}; + +inline constexpr auto fold_left_with_iter = __fold_left_with_iter(); + +struct __fold_left { + template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, __indirectly_binary_left_foldable<_Tp, _Ip> _Fp> + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI static constexpr auto + operator()(_Ip __first, _Sp __last, _Tp __init, _Fp __f) { + return fold_left_with_iter(std::move(__first), std::move(__last), std::move(__init), std::ref(__f)).value; + } + + template <input_range _Rp, class _Tp, __indirectly_binary_left_foldable<_Tp, iterator_t<_Rp>> _Fp> + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Rp&& __r, _Tp __init, _Fp __f) { + return fold_left_with_iter(ranges::begin(__r), ranges::end(__r), std::move(__init), std::ref(__f)).value; + } +}; + +inline constexpr auto fold_left = __fold_left(); +} // namespace ranges + +#endif // _LIBCPP_STD_VER >= 23 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_FOLD_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 62dbec4..1176602 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -42,6 +42,9 @@ namespace ranges { template <class I> struct in_found_result; // since C++20 + template <class I, class T> + struct in_value_result; // since C++23 + template<forward_iterator I, sentinel_for<I> S, class Proj = identity, indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> // since C++20 constexpr I min_element(I first, S last, Comp comp = {}, Proj proj = {}); @@ -881,6 +884,23 @@ namespace ranges { ranges::search_n(R&& r, range_difference_t<R> count, const T& value, Pred pred = {}, Proj proj = {}); // since C++20 + template<input_iterator I, sentinel_for<I> S, class T, + indirectly-binary-left-foldable<T, I> F> + constexpr auto ranges::fold_left(I first, S last, T init, F f); // since C++23 + + template<input_range R, class T, indirectly-binary-left-foldable<T, iterator_t<R>> F> + constexpr auto fold_left(R&& r, T init, F f); // since C++23 + + template<class I, class T> + using fold_left_with_iter_result = in_value_result<I, T>; // since C++23 + + template<input_iterator I, sentinel_for<I> S, class T, + indirectly-binary-left-foldable<T, I> F> + constexpr see below fold_left_with_iter(I first, S last, T init, F f); // since C++23 + + template<input_range R, class T, indirectly-binary-left-foldable<T, iterator_t<R>> F> + constexpr see below fold_left_with_iter(R&& r, T init, F f); // since C++23 + template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> @@ -1786,6 +1806,7 @@ template <class BidirectionalIterator, class Compare> #include <__algorithm/find_first_of.h> #include <__algorithm/find_if.h> #include <__algorithm/find_if_not.h> +#include <__algorithm/fold.h> #include <__algorithm/for_each.h> #include <__algorithm/for_each_n.h> #include <__algorithm/generate.h> diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in index 49d5e52..a37e962 100644 --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -666,6 +666,7 @@ module std_private_algorithm_find_first_of [system module std_private_algorithm_find_if [system] { header "__algorithm/find_if.h" } module std_private_algorithm_find_if_not [system] { header "__algorithm/find_if_not.h" } module std_private_algorithm_find_segment_if [system] { header "__algorithm/find_segment_if.h" } +module std_private_algorithm_fold [system] { header "__algorithm/fold.h" } module std_private_algorithm_for_each [system] { header "__algorithm/for_each.h" } module std_private_algorithm_for_each_n [system] { header "__algorithm/for_each_n.h" } module std_private_algorithm_for_each_segment [system] { header "__algorithm/for_each_segment.h" } diff --git a/libcxx/modules/std/algorithm.inc b/libcxx/modules/std/algorithm.inc index 246b55c..f6b35ef 100644 --- a/libcxx/modules/std/algorithm.inc +++ b/libcxx/modules/std/algorithm.inc @@ -16,7 +16,7 @@ export namespace std { using std::ranges::in_in_result; using std::ranges::in_out_out_result; using std::ranges::in_out_result; - // using std::ranges::in_value_result; + using std::ranges::in_value_result; using std::ranges::min_max_result; // using std::ranges::out_value_result; } // namespace ranges @@ -157,15 +157,15 @@ export namespace std { // [alg.ends.with], ends with using std::ranges::ends_with; -# if 0 // [alg.fold], fold using std::ranges::fold_left; + using std::ranges::fold_left_with_iter; + using std::ranges::fold_left_with_iter_result; +# if 0 using std::ranges::fold_left_first; using std::ranges::fold_right; using std::ranges::fold_right_last; using std::ranges::fold_left_with_iter; - using std::ranges::fold_left_with_iter_result; - using std::ranges::fold_left_with_iter; using std::ranges::fold_left_first_with_iter; using std::ranges::fold_left_first_with_iter; # endif diff --git a/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.verify.cpp b/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.verify.cpp index d11dcfc..f0a0e48 100644 --- a/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.verify.cpp +++ b/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.verify.cpp @@ -12,6 +12,8 @@ #include <algorithm> +#include "test_macros.h" + void test() { int range[1]; int* iter = range; @@ -87,4 +89,15 @@ void test() { std::ranges::unique(iter, iter); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}} std::ranges::upper_bound(range, 1); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}} std::ranges::upper_bound(iter, iter, 1); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}} + +#if TEST_STD_VER >= 23 + std::ranges::fold_left(range, 0, std::plus()); + // expected-warning@-1{{ignoring return value of function declared with 'nodiscard' attribute}} + std::ranges::fold_left(iter, iter, 0, std::plus()); + // expected-warning@-1{{ignoring return value of function declared with 'nodiscard' attribute}} + std::ranges::fold_left_with_iter(range, 0, std::plus()); + // expected-warning@-1{{ignoring return value of function declared with 'nodiscard' attribute}} + std::ranges::fold_left_with_iter(iter, iter, 0, std::plus()); + // expected-warning@-1{{ignoring return value of function declared with 'nodiscard' attribute}} +#endif } diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.fold/left_folds.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.fold/left_folds.pass.cpp new file mode 100644 index 0000000..cf089b2 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.fold/left_folds.pass.cpp @@ -0,0 +1,320 @@ +//===----------------------------------------------------------------------===// +// +// 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, +// indirectly-binary-left-foldable<T, I> F> +// constexpr see below ranges::fold_left_with_iter(I first, S last, T init, F f); +// +// template<input_range R, class T, indirectly-binary-left-foldable<T, iterator_t<R>> F> +// constexpr see below ranges::fold_left_with_iter(R&& r, T init, F f); + +// template<input_iterator I, sentinel_for<I> S, class T, +// indirectly-binary-left-foldable<T, I> F> +// constexpr see below ranges::fold_left(I first, S last, T init, F f); +// +// template<input_range R, class T, indirectly-binary-left-foldable<T, iterator_t<R>> F> +// constexpr see below ranges::fold_left(R&& r, T init, F f); + +#include <algorithm> +#include <cassert> +#include <concepts> +#include <deque> +#include <forward_list> +#include <functional> +#include <iterator> +#include <list> +#include <ranges> +#include <string_view> +#include <string> +#include <vector> + +#include "test_macros.h" +#include "test_range.h" +#include "invocable_with_telemetry.h" +#include "maths.h" + +#if !defined(TEST_HAS_NO_LOCALIZATION) +# include <sstream> +#endif + +using std::ranges::fold_left; +using std::ranges::fold_left_with_iter; + +template <class Result, class Range, class T> +concept is_in_value_result = + std::same_as<Result, std::ranges::fold_left_with_iter_result<std::ranges::iterator_t<Range>, T>>; + +template <class Result, class T> +concept is_dangling_with = std::same_as<Result, std::ranges::fold_left_with_iter_result<std::ranges::dangling, T>>; + +struct Long { + int value; + + constexpr Long(int const x) : value(x) {} + + constexpr Long plus(int const x) const { return Long{value + x}; } + + friend constexpr bool operator==(Long const& x, Long const& y) = default; +}; + +template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected> + requires std::copyable<R> +constexpr void check_iterator(R& r, T const& init, F f, Expected const& expected) { + { + is_in_value_result<R, Expected> decltype(auto) result = fold_left_with_iter(r.begin(), r.end(), init, f); + assert(result.in == r.end()); + assert(result.value == expected); + } + { + auto telemetry = invocable_telemetry(); + auto f2 = invocable_with_telemetry(f, telemetry); + is_in_value_result<R, Expected> decltype(auto) result = fold_left_with_iter(r.begin(), r.end(), init, f2); + assert(result.in == r.end()); + assert(result.value == expected); + assert(telemetry.invocations == std::ranges::distance(r)); + assert(telemetry.moves == 0); + assert(telemetry.copies == 1); + } + + { + std::same_as<Expected> decltype(auto) result = fold_left(r.begin(), r.end(), init, f); + assert(result == expected); + } + { + auto telemetry = invocable_telemetry(); + auto f2 = invocable_with_telemetry(f, telemetry); + std::same_as<Expected> decltype(auto) result = fold_left(r.begin(), r.end(), init, f2); + assert(result == expected); + assert(telemetry.invocations == std::ranges::distance(r)); + assert(telemetry.moves == 0); + assert(telemetry.copies == 1); + } +} + +template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected> + requires std::copyable<R> +constexpr void check_lvalue_range(R& r, T const& init, F f, Expected const& expected) { + { + is_in_value_result<R, Expected> decltype(auto) result = fold_left_with_iter(r, init, f); + assert(result.in == r.end()); + assert(result.value == expected); + } + { + auto telemetry = invocable_telemetry(); + auto f2 = invocable_with_telemetry(f, telemetry); + std::same_as<Expected> decltype(auto) result = fold_left(r, init, f2); + assert(result == expected); + assert(telemetry.invocations == std::ranges::distance(r)); + assert(telemetry.moves == 0); + assert(telemetry.copies == 1); + } + + { + std::same_as<Expected> decltype(auto) result = fold_left(r, init, f); + assert(result == expected); + } + { + auto telemetry = invocable_telemetry(); + auto f2 = invocable_with_telemetry(f, telemetry); + std::same_as<Expected> decltype(auto) result = fold_left(r, init, f2); + assert(result == expected); + assert(telemetry.invocations == std::ranges::distance(r)); + assert(telemetry.moves == 0); + assert(telemetry.copies == 1); + } +} + +template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected> + requires std::copyable<R> +constexpr void check_rvalue_range(R& r, T const& init, F f, Expected const& expected) { + { + auto r2 = r; + is_dangling_with<Expected> decltype(auto) result = fold_left_with_iter(std::move(r2), init, f); + assert(result.value == expected); + } + { + auto telemetry = invocable_telemetry(); + auto f2 = invocable_with_telemetry(f, telemetry); + auto r2 = r; + is_dangling_with<Expected> decltype(auto) result = fold_left_with_iter(std::move(r2), init, f2); + assert(result.value == expected); + assert(telemetry.invocations == std::ranges::distance(r)); + assert(telemetry.moves == 0); + assert(telemetry.copies == 1); + } + + { + auto r2 = r; + std::same_as<Expected> decltype(auto) result = fold_left(std::move(r2), init, f); + assert(result == expected); + } + { + auto telemetry = invocable_telemetry(); + auto f2 = invocable_with_telemetry(f, telemetry); + auto r2 = r; + std::same_as<Expected> decltype(auto) result = fold_left(std::move(r2), init, f2); + assert(result == expected); + assert(telemetry.invocations == std::ranges::distance(r)); + assert(telemetry.moves == 0); + assert(telemetry.copies == 1); + } +} + +template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected> + requires std::copyable<R> +constexpr void check(R r, T const& init, F f, Expected const& expected) { + check_iterator(r, init, f, expected); + check_lvalue_range(r, init, f, expected); + check_rvalue_range(r, init, f, expected); +} + +constexpr void empty_range_test_case() { + auto const data = std::vector<int>{}; + check(data, 100, std::plus(), 100); + check(data, -100, std::multiplies(), -100); + + check(data | std::views::take_while([](auto) { return false; }), 1.23, std::plus(), 1.23); + check(data, Long(52), &Long::plus, Long(52)); +} + +constexpr void common_range_test_case() { + auto const data = std::vector<int>{1, 2, 3, 4}; + check(data, 0, std::plus(), triangular_sum(data)); + check(data, 1, std::multiplies(), factorial(data.back())); + + auto multiply_with_prev = [n = 1](auto const x, auto const y) mutable { + auto const result = x * y * n; + n = y; + return static_cast<std::size_t>(result); + }; + check(data, 1, multiply_with_prev, factorial(data.size()) * factorial(data.size() - 1)); + + auto fib = [n = 1](auto x, auto) mutable { + auto old_x = x; + x += n; + n = old_x; + return x; + }; + check(data, 0, fib, fibonacci(data.back())); + + check(data, Long(0), &Long::plus, Long(triangular_sum(data))); +} + +constexpr void non_common_range_test_case() { + auto parse = [](std::string_view const s) { + return s == "zero" ? 0.0 + : s == "one" ? 1.0 + : s == "two" ? 2.0 + : s == "three" ? 3.0 + : s == "four" ? 4.0 + : s == "five" ? 5.0 + : s == "six" ? 6.0 + : s == "seven" ? 7.0 + : s == "eight" ? 8.0 + : s == "nine" ? 9.0 + : (assert(false), 10.0); // the number here is arbitrary + }; + + { + auto data = std::vector<std::string>{"five", "three", "two", "six", "one", "four"}; + auto range = data | std::views::transform(parse); + check(range, 0, std::plus(), triangular_sum(range)); + } + + { + auto data = std::string("five three two six one four"); + auto to_string_view = [](auto&& r) { + auto const n = std::ranges::distance(r); + return std::string_view(&*r.begin(), n); + }; + auto range = + std::views::lazy_split(data, ' ') | std::views::transform(to_string_view) | std::views::transform(parse); + check(range, 0, std::plus(), triangular_sum(range)); + } +} + +constexpr bool test_case() { + empty_range_test_case(); + common_range_test_case(); + non_common_range_test_case(); + return true; +} + +// Most containers aren't constexpr +void runtime_only_test_case() { +#if !defined(TEST_HAS_NO_LOCALIZATION) + { // istream_view is a genuine input range and needs specific handling. + constexpr auto raw_data = "Shells Orange Syrup Baratie Cocoyashi Loguetown"; + constexpr auto expected = "WindmillShellsOrangeSyrupBaratieCocoyashiLoguetown"; + auto const init = std::string("Windmill"); + + { + auto input = std::istringstream(raw_data); + auto data = std::views::istream<std::string>(input); + is_in_value_result<std::ranges::basic_istream_view<std::string, char>, std::string> decltype(auto) result = + fold_left_with_iter(data.begin(), data.end(), init, std::plus()); + + assert(result.in == data.end()); + assert(result.value == expected); + } + { + auto input = std::istringstream(raw_data); + auto data = std::views::istream<std::string>(input); + is_in_value_result<std::ranges::basic_istream_view<std::string, char>, std::string> decltype(auto) result = + fold_left_with_iter(data, init, std::plus()); + assert(result.in == data.end()); + assert(result.value == expected); + } + { + auto input = std::istringstream(raw_data); + auto data = std::views::istream<std::string>(input); + assert(fold_left(data.begin(), data.end(), init, std::plus()) == expected); + } + { + auto input = std::istringstream(raw_data); + auto data = std::views::istream<std::string>(input); + assert(fold_left(data, init, std::plus()) == expected); + } + } +#endif + { + auto const data = std::forward_list<int>{1, 3, 5, 7, 9}; + auto const n = std::ranges::distance(data); + auto const expected = static_cast<float>(n * n); // sum of n consecutive odd numbers = n^2 + check(data, 0.0f, std::plus(), expected); + } + + { + auto const data = std::list<int>{2, 4, 6, 8, 10, 12}; + auto const expected = triangular_sum(data); + check(data, 0, std::plus<long>(), static_cast<long>(expected)); + } + + { + auto const data = std::deque<double>{-1.1, -2.2, -3.3, -4.4, -5.5, -6.6}; + auto plus = [](int const x, double const y) { return x + y; }; + auto const expected = -21.6; // int( 0.0) + -1.1 = 0 + -1.1 = -1.1 + // int(- 1.1) + -2.2 = - 1 + -2.2 = -3.2 + // int(- 3.2) + -3.3 = - 3 + -3.3 = -6.3 + // int(- 6.3) + -4.4 = - 6 + -4.4 = -10.4 + // int(-10.4) + -5.5 = -10 + -5.5 = -15.5 + // int(-15.5) + -6.6 = -15 + -6.6 = -21.6. + check(data, 0.0, plus, expected); + } +} + +int main(int, char**) { + test_case(); + static_assert(test_case()); + runtime_only_test_case(); + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.fold/requirements.compile.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.fold/requirements.compile.pass.cpp new file mode 100644 index 0000000..cad96d4 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.fold/requirements.compile.pass.cpp @@ -0,0 +1,259 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// Checks that `std::ranges::fold_left_with_iter`'s requirements reject parameters that don't meet +// the overloads' constraints. + +#include <algorithm> +#include <concepts> +#include <cstddef> +#include <functional> +#include <iterator> +#include <ranges> + +#include "test_iterators.h" + +// FIXME(cjdb): deduplicate +struct bad_iterator_category { + using value_type = int; + using difference_type = std::ptrdiff_t; + using iterator_category = void; + + value_type operator*() const; + + bad_iterator_category& operator++(); + void operator++(int); +}; + +// Covers indirectly_readable<I> too +template <std::input_or_output_iterator T> + requires(!std::input_iterator<T>) +void requires_input_iterator() { + struct bad_range { + T begin(); + std::unreachable_sentinel_t end(); + }; + + static_assert(!requires(bad_range r) { + std::ranges::fold_left_with_iter(r.begin(), r.end(), std::unreachable_sentinel, 0, std::plus()); + }); + static_assert(!requires(bad_range r) { std::ranges::fold_left_with_iter(r, 0, std::plus()); }); + + static_assert(!requires(bad_range r) { + std::ranges::fold_left(r.begin(), r.end(), std::unreachable_sentinel, 0, std::plus()); + }); + + static_assert(!requires(bad_range r) { std::ranges::fold_left(r, 0, std::plus()); }); +} + +template <std::equality_comparable S> + requires(!std::sentinel_for<int*, S>) +void requires_sentinel() { + static_assert(!requires(S first, S last) { std::ranges::fold_left_with_iter(first, last, 0, std::plus()); }); + static_assert(!requires(S first, S last) { std::ranges::fold_left(first, last, 0, std::plus()); }); +} + +struct non_copy_constructible_callable { + non_copy_constructible_callable(non_copy_constructible_callable&&) = default; + non_copy_constructible_callable(non_copy_constructible_callable const&) = delete; + + int operator()(int, int) const; +}; + +template <class F> + requires(!std::copy_constructible<F>) +void requires_copy_constructible_F() { + static_assert(!requires(std::ranges::subrange<int*, int*> r, F f) { + std::ranges::fold_left_with_iter(r.begin(), r.end(), 0, std::move(f)); + }); + static_assert(!requires(std::ranges::subrange<int*, int*> r, F f) { + std::ranges::fold_left_with_iter(r, 0, std::move(f)); + }); + + static_assert(!requires(std::ranges::subrange<int*, int*> r, F f) { + std::ranges::fold_left(r.begin(), r.end(), 0, std::move(f)); + }); + static_assert(!requires(std::ranges::subrange<int*, int*> r, F f) { std::ranges::fold_left(r, 0, std::move(f)); }); +} + +struct not_invocable_with_lvalue_rhs { + int operator()(int, int&&); +}; + +template <class F> + requires(!std::invocable<F&, int, std::iter_reference_t<int*>>) +void requires_raw_invocable() { + static_assert(!requires(std::ranges::subrange<int*, int*> r, F f) { + std::ranges::fold_left_with_iter(r.begin(), r.end(), 0, f); + }); + static_assert(!requires(std::ranges::subrange<int*, int*> r, F f) { std::ranges::fold_left_with_iter(r, 0, f); }); + + static_assert(!requires(std::ranges::subrange<int*, int*> r, F f) { + std::ranges::fold_left(r.begin(), r.end(), 0, f); + }); + static_assert(!requires(std::ranges::subrange<int*, int*> r, F f) { std::ranges::fold_left(r, 0, f); }); +} + +struct S {}; + +struct non_decayable_result { + S volatile& operator()(S, S) const; +}; + +template <std::invocable<S, std::iter_reference_t<S*>> F> + requires(!std::convertible_to<std::invoke_result_t<F&, S, std::iter_reference_t<S*>>, + std::decay_t<std::invoke_result_t<F&, S, std::iter_reference_t<S*>>>>) +void requires_decaying_invoke_result() { + static_assert(!requires(std::ranges::subrange<S*, S*> r, S init, F f) { + std::ranges::fold_left_with_iter(r.begin(), r.end(), init, f); + }); + static_assert(!requires(std::ranges::subrange<S*, S*> r, S init, F f) { + std::ranges::fold_left_with_iter(r, init, f); + }); + + static_assert(!requires(std::ranges::subrange<S*, S*> r, S init, F f) { + std::ranges::fold_left(r.begin(), r.end(), init, f); + }); + static_assert(!requires(std::ranges::subrange<S*, S*> r, S init, F f) { std::ranges::fold_left(r, init, f); }); +} + +struct non_movable { + non_movable(int); + non_movable(non_movable&&) = delete; + + int apply(non_movable const&) const; +}; + +template <class T> + requires(!std::movable<T>) +void requires_movable_init() { + static_assert(!requires(std::ranges::subrange<T*, T*> r, T init) { + std::ranges::fold_left_with_iter(r.begin(), r.end(), init, &T::apply); + }); + static_assert(!requires(std::ranges::subrange<T*, T*> r, T init) { + std::ranges::fold_left_with_iter(r, init, &T::apply); + }); + static_assert(!requires(std::ranges::subrange<T*, T*> r, T init) { + std::ranges::fold_left(r.begin(), r.end(), init, &T::apply); + }); + static_assert(!requires(std::ranges::subrange<T*, T*> r, T init) { std::ranges::fold_left(r, init, &T::apply); }); +} + +struct result_not_movable_after_decay { + result_not_movable_after_decay(int); + result_not_movable_after_decay(result_not_movable_after_decay&&) = delete; + result_not_movable_after_decay(result_not_movable_after_decay const&); + + friend result_not_movable_after_decay const& operator+(int, result_not_movable_after_decay const&); + friend result_not_movable_after_decay const& operator+(result_not_movable_after_decay const&, int); + friend result_not_movable_after_decay const& + operator+(result_not_movable_after_decay const&, result_not_movable_after_decay const&); +}; + +template <class T> + requires(!std::movable<T>) +void requires_movable_decayed() { + static_assert(!requires(std::ranges::subrange<T*, T*> r) { + std::ranges::fold_left_with_iter(r.begin(), r.end(), 0, std::plus()); + }); + static_assert(!requires(std::ranges::subrange<T*, T*> r) { std::ranges::fold_left_with_iter(r, 0, std::plus()); }); + + static_assert(!requires(std::ranges::subrange<T*, T*> r) { + std::ranges::fold_left(r.begin(), r.end(), 0, T::apply); + }); + static_assert(!requires(std::ranges::subrange<T*, T*> r) { std::ranges::fold_left(r, 0, std::plus()); }); +} + +struct not_convertible_to_int { + friend int operator+(not_convertible_to_int, not_convertible_to_int); + friend int operator+(not_convertible_to_int, int); + friend int operator+(int, not_convertible_to_int); +}; + +template <class T> + requires(!std::convertible_to<T, int>) +void requires_init_is_convertible_to_decayed() { + static_assert(!requires(std::ranges::subrange<int*, int*> r, T init) { + std::ranges::fold_left_with_iter(r.begin(), r.end(), init, std::plus()); + }); + static_assert(!requires(std::ranges::subrange<int*, int*> r, T init) { + std::ranges::fold_left_with_iter(r, init, std::plus()); + }); + + static_assert(!requires(std::ranges::subrange<int*, int*> r, T init) { + std::ranges::fold_left(r.begin(), r.end(), init, std::plus()); + }); + static_assert(!requires(std::ranges::subrange<int*, int*> r, T init) { + std::ranges::fold_left(r, init, std::plus()); + }); +} + +struct not_invocable_with_decayed { + not_invocable_with_decayed(int); + friend not_invocable_with_decayed& operator+(int, not_invocable_with_decayed&); + friend not_invocable_with_decayed& operator+(not_invocable_with_decayed&, int); + friend not_invocable_with_decayed& operator+(not_invocable_with_decayed volatile&, not_invocable_with_decayed&); +}; + +template <class T> + requires(!std::invocable<std::plus<>&, T, T&>) +void requires_invocable_with_decayed() { + static_assert(!requires(std::ranges::subrange<T*, T*> r, int init) { + std::ranges::fold_left_with_iter(r.begin(), r.end(), init, std::plus()); + }); + static_assert(!requires(std::ranges::subrange<T*, T*> r, int init) { + std::ranges::fold_left_with_iter(r, init, std::plus()); + }); + + static_assert(!requires(std::ranges::subrange<T*, T*> r, int init) { + std::ranges::fold_left(r.begin(), r.end(), init, std::plus()); + }); + static_assert(!requires(std::ranges::subrange<T*, T*> r, int init) { std::ranges::fold_left(r, init, std::plus()); }); +} + +struct not_assignable_to_decayed { + not_assignable_to_decayed(); + not_assignable_to_decayed(not_assignable_to_decayed&); + not_assignable_to_decayed(not_assignable_to_decayed const&); + not_assignable_to_decayed(not_assignable_to_decayed volatile&); + not_assignable_to_decayed(not_assignable_to_decayed const volatile&); + friend not_assignable_to_decayed volatile& operator+(not_assignable_to_decayed, not_assignable_to_decayed); +}; + +template <class T> + requires(!std::assignable_from<T&, T volatile&>) +void requires_assignable_from_invoke_result() { + static_assert(!requires(std::ranges::subrange<T*, T*> r, T init) { + std::ranges::fold_left_with_iter(r.begin(), r.end(), init, std::plus()); + }); + static_assert(!requires(std::ranges::subrange<T*, T*> r, T init) { + std::ranges::fold_left_with_iter(r, init, std::plus()); + }); + + static_assert(!requires(std::ranges::subrange<T*, T*> r, T init) { + std::ranges::fold_left(r.begin(), r.end(), init, std::plus()); + }); + static_assert(!requires(std::ranges::subrange<T*, T*> r, T init) { std::ranges::fold_left(r, init, std::plus()); }); +} + +void test() { + requires_input_iterator<bad_iterator_category>(); + requires_sentinel<cpp17_input_iterator<int*>>(); + requires_copy_constructible_F<non_copy_constructible_callable>(); + requires_raw_invocable<not_invocable_with_lvalue_rhs>(); + requires_decaying_invoke_result<non_decayable_result>(); + requires_movable_init<non_movable>(); + requires_movable_decayed<result_not_movable_after_decay>(); + requires_init_is_convertible_to_decayed<not_convertible_to_int>(); + requires_invocable_with_decayed<not_invocable_with_decayed>(); + requires_assignable_from_invoke_result<not_assignable_to_decayed>(); +} diff --git a/libcxx/test/std/algorithms/algorithms.results/in_value_result.pass.cpp b/libcxx/test/std/algorithms/algorithms.results/in_value_result.pass.cpp new file mode 100644 index 0000000..f4023b8 --- /dev/null +++ b/libcxx/test/std/algorithms/algorithms.results/in_value_result.pass.cpp @@ -0,0 +1,104 @@ +//===----------------------------------------------------------------------===// +// +// 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 <class I, class T> +// struct in_value_result; + +#include <algorithm> +#include <cassert> +#include <type_traits> +#include <utility> + +#include "MoveOnly.h" + +struct A { + explicit A(int); +}; +// no implicit conversion +static_assert(!std::is_constructible_v<std::ranges::in_value_result<A, A>, std::ranges::in_value_result<int, int>>); + +struct B { + B(int); +}; +// implicit conversion +static_assert(std::is_constructible_v<std::ranges::in_value_result<B, B>, std::ranges::in_value_result<int, int>>); +static_assert(std::is_constructible_v<std::ranges::in_value_result<B, B>, std::ranges::in_value_result<int, int>&>); +static_assert( + std::is_constructible_v<std::ranges::in_value_result<B, B>, const std::ranges::in_value_result<int, int>>); +static_assert( + std::is_constructible_v<std::ranges::in_value_result<B, B>, const std::ranges::in_value_result<int, int>&>); + +struct C { + C(int&); +}; +static_assert(!std::is_constructible_v<std::ranges::in_value_result<C, C>, std::ranges::in_value_result<int, int>&>); + +// has to be convertible via const& +static_assert(std::is_convertible_v<std::ranges::in_value_result<int, int>&, std::ranges::in_value_result<long, long>>); +static_assert( + std::is_convertible_v<const std::ranges::in_value_result<int, int>&, std::ranges::in_value_result<long, long>>); +static_assert( + std::is_convertible_v<std::ranges::in_value_result<int, int>&&, std::ranges::in_value_result<long, long>>); +static_assert( + std::is_convertible_v<const std::ranges::in_value_result<int, int>&&, std::ranges::in_value_result<long, long>>); + +// should be move constructible +static_assert(std::is_move_constructible_v<std::ranges::in_value_result<MoveOnly, int>>); +static_assert(std::is_move_constructible_v<std::ranges::in_value_result<int, MoveOnly>>); + +// should not copy constructible with move-only type +static_assert(!std::is_copy_constructible_v<std::ranges::in_value_result<MoveOnly, int>>); +static_assert(!std::is_copy_constructible_v<std::ranges::in_value_result<int, MoveOnly>>); + +struct NotConvertible {}; +// conversions should not work if there is no conversion +static_assert( + !std::is_convertible_v<std::ranges::in_value_result<NotConvertible, int>, std::ranges::in_value_result<int, int>>); +static_assert( + !std::is_convertible_v<std::ranges::in_value_result<int, NotConvertible>, std::ranges::in_value_result<int, int>>); + +template <class T> +struct ConvertibleFrom { + constexpr ConvertibleFrom(T c) : content{c} {} + T content; +}; + +constexpr bool test() { + { + std::ranges::in_value_result<int, double> res{10, 0.}; + assert(res.in == 10); + assert(res.value == 0.); + std::ranges::in_value_result<ConvertibleFrom<int>, ConvertibleFrom<double>> res2 = res; + assert(res2.in.content == 10); + assert(res2.value.content == 0.); + } + { + std::ranges::in_value_result<MoveOnly, int> res{MoveOnly{}, 2}; + assert(res.in.get() == 1); + assert(res.value == 2); + auto res2 = static_cast<std::ranges::in_value_result<MoveOnly, int>>(std::move(res)); + assert(res.in.get() == 0); + assert(res2.in.get() == 1); + assert(res2.value == 2); + } + { + auto [in, value] = std::ranges::in_value_result<int, int>{1, 2}; + assert(in == 1); + assert(value == 2); + } + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp b/libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp index 8e0a819..34dbd64 100644 --- a/libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp +++ b/libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp @@ -53,6 +53,14 @@ static_assert(sizeof(std::ranges::in_out_out_result<Empty, Empty, char>) == 2); static_assert(sizeof(std::ranges::in_out_out_result<int, Empty, Empty2>) == sizeof(int)); static_assert(sizeof(std::ranges::in_out_out_result<Empty, Empty, Empty>) == 3); +#if TEST_STD_VER >= 23 + +static_assert(sizeof(std::ranges::in_value_result<Empty, int>) == sizeof(int)); +static_assert(sizeof(std::ranges::in_value_result<int, Empty>) == sizeof(int)); +static_assert(sizeof(std::ranges::in_value_result<Empty, Empty2>) == sizeof(Empty2)); + +#endif // TEST_STD_VER + // In min_max_result both elements have the same type, so they can't have the same address. // So the only way to test that [[no_unique_address]] is used is to have it in another struct struct MinMaxNoUniqueAddress { diff --git a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp index a72c3a3..6940b23 100644 --- a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp @@ -16,6 +16,8 @@ #include <memory> #include <type_traits> +#include "test_macros.h" + using namespace std::ranges; static_assert(std::is_same_v<in_fun_result<int, long>, for_each_result<int, long>>); @@ -59,4 +61,10 @@ static_assert(std::is_same_v<min_max_result<int>, minmax_element_result<int>>); static_assert(std::is_same_v<in_found_result<int>, next_permutation_result<int>>); static_assert(std::is_same_v<in_found_result<int>, prev_permutation_result<int>>); +#if TEST_STD_VER >= 23 + +static_assert(std::is_same_v<in_value_result<int, long>, fold_left_with_iter_result<int, long>>); + // static_assert(std::is_same_v<out_value_result<int>, iota_result<int>>); + +#endif // TEST_STD_VER diff --git a/libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp b/libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp index 217c68f..0c72c70 100644 --- a/libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp +++ b/libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp @@ -81,6 +81,7 @@ struct not_indirectly_readable { }; static_assert(!std::indirectly_readable<not_indirectly_readable> && !std::input_iterator<not_indirectly_readable>); +// FIXME(cjdb): deduplicate struct bad_iterator_category { using value_type = int; using difference_type = std::ptrdiff_t; 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 fa005d1..494e9fd 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 @@ -86,6 +86,10 @@ static_assert(test(std::ranges::find_end, a, a)); static_assert(test(std::ranges::find_first_of, a, a)); static_assert(test(std::ranges::find_if, a, odd)); static_assert(test(std::ranges::find_if_not, a, odd)); +#if TEST_STD_VER >= 23 +static_assert(test(std::ranges::fold_left, a, 0, std::plus())); +static_assert(test(std::ranges::fold_left_with_iter, a, 0, std::plus())); +#endif static_assert(test(std::ranges::for_each, a, odd)); static_assert(test(std::ranges::for_each_n, a, 10, odd)); static_assert(test(std::ranges::generate, a, gen)); diff --git a/libcxx/test/std/ranges/range.adaptors/range.all/range.ref.view/borrowing.compile.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.all/range.ref.view/borrowing.compile.pass.cpp index 4405742..2887ef1 100644 --- a/libcxx/test/std/ranges/range.adaptors/range.all/range.ref.view/borrowing.compile.pass.cpp +++ b/libcxx/test/std/ranges/range.adaptors/range.all/range.ref.view/borrowing.compile.pass.cpp @@ -15,6 +15,6 @@ #include "test_range.h" -static_assert(std::ranges::borrowed_range<std::ranges::ref_view<BorrowedRange>>); +static_assert(std::ranges::borrowed_range<std::ranges::ref_view<BorrowedRange<>>>); static_assert(std::ranges::borrowed_range<std::ranges::ref_view<BorrowedView>>); static_assert(std::ranges::borrowed_range<std::ranges::ref_view<NonBorrowedView>>); diff --git a/libcxx/test/support/invocable_with_telemetry.h b/libcxx/test/support/invocable_with_telemetry.h new file mode 100644 index 0000000..612bbec --- /dev/null +++ b/libcxx/test/support/invocable_with_telemetry.h @@ -0,0 +1,89 @@ +//===----------------------------------------------------------------------===// +// +// 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 TEST_SUPPORT_INVOCABLE_WITH_TELEMETRY_H +#define TEST_SUPPORT_INVOCABLE_WITH_TELEMETRY_H + +#include <cassert> +#include <concepts> +#include <functional> +#include <utility> + +#if TEST_STD_VER < 20 +# error invocable_with_telemetry requires C++20 +#else +struct invocable_telemetry { + int invocations; + int moves; + int copies; +}; + +template <class F> +class invocable_with_telemetry { +public: + constexpr invocable_with_telemetry(F f, invocable_telemetry& telemetry) : f_(f), telemetry_(&telemetry) {} + + constexpr invocable_with_telemetry(invocable_with_telemetry&& other) + requires std::move_constructible<F> + : f_(std::move(other.f_)), + telemetry_(assert(other.telemetry_ != nullptr), std::exchange(other.telemetry_, nullptr)) { + ++telemetry_->moves; + } + + constexpr invocable_with_telemetry(invocable_with_telemetry const& other) + requires std::copy_constructible<F> + : f_(other.f_), telemetry_((assert(other.telemetry_ != nullptr), other.telemetry_)) { + ++telemetry_->copies; + } + + constexpr invocable_with_telemetry& operator=(invocable_with_telemetry&& other) + requires std::movable<F> + { + // Not using move-and-swap idiom to ensure that copies and moves remain accurate. + assert(&other != this); + assert(other.telemetry_ != nullptr); + + f_ = std::move(other.f_); + telemetry_ = std::exchange(other.telemetry_, nullptr); + + ++telemetry_->moves; + return *this; + } + + constexpr invocable_with_telemetry& operator=(invocable_with_telemetry const& other) + requires std::copyable<F> + { + // Not using copy-and-swap idiom to ensure that copies and moves remain accurate. + assert(&other != this); + assert(other.telemetry_ != nullptr); + + f_ = other.f_; + telemetry_ = other.telemetry_; + + ++telemetry_->copies; + return *this; + } + + template <class... Args> + requires std::invocable<F&, Args...> + constexpr decltype(auto) operator()(Args&&... args) noexcept(std::is_nothrow_invocable_v<F&, Args...>) { + assert(telemetry_); + ++telemetry_->invocations; + return std::invoke(f_, std::forward<Args>(args)...); + } + +private: + F f_ = F(); + invocable_telemetry* telemetry_ = nullptr; +}; + +template <class F> +invocable_with_telemetry(F f, int& invocations, int& moves, int& copies) -> invocable_with_telemetry<F>; + +#endif // TEST_STD_VER < 20 +#endif // TEST_SUPPORT_INVOCABLE_WITH_TELEMETRY_H diff --git a/libcxx/test/support/maths.h b/libcxx/test/support/maths.h new file mode 100644 index 0000000..11c507b --- /dev/null +++ b/libcxx/test/support/maths.h @@ -0,0 +1,68 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// Implementations of well-known functions in mathematics that are useful for +// testing algorithms. + +#ifndef LIBCXX_TEST_MATHS_H +#define LIBCXX_TEST_MATHS_H + +#include <algorithm> +#include <cassert> +#include <concepts> +#include <ranges> +#include <vector> + +template <std::ranges::forward_range R> +constexpr std::ranges::range_value_t<R> triangular_sum(R& input) { + assert(not std::ranges::empty(input)); + auto [min, max] = std::ranges::minmax_element(input); + return static_cast<std::ranges::range_value_t<R>>( + (static_cast<double>(std::ranges::distance(input)) / 2) * (*min + *max)); +} + +template <std::integral I> +constexpr I factorial(I const n) { + assert(n >= 0); + auto result = I(1); + for (auto i = I(1); i <= n; ++i) { + result *= i; + } + + return result; +} +static_assert(factorial(0) == 1); +static_assert(factorial(1) == 1); +static_assert(factorial(2) == 2); +static_assert(factorial(3) == 6); +static_assert(factorial(4) == 24); +static_assert(factorial(5) == 120); + +template <std::integral I> +constexpr I fibonacci(I const n) { + assert(n >= 0); + + auto result = I(0); + auto prev = I(1); + for (auto i = I(0); i < n; ++i) { + result += std::exchange(prev, result); + } + return result; +} +static_assert(fibonacci(0) == 0); +static_assert(fibonacci(1) == 1); +static_assert(fibonacci(2) == 1); +static_assert(fibonacci(3) == 2); +static_assert(fibonacci(4) == 3); +static_assert(fibonacci(5) == 5); +static_assert(fibonacci(6) == 8); +static_assert(fibonacci(7) == 13); +static_assert(fibonacci(8) == 21); +static_assert(fibonacci(9) == 34); + +#endif // LIBCXX_TEST_MATHS_H diff --git a/libcxx/test/support/test_range.h b/libcxx/test/support/test_range.h index eea8ce1..3f03b4d 100644 --- a/libcxx/test/support/test_range.h +++ b/libcxx/test/support/test_range.h @@ -15,62 +15,64 @@ #include "test_iterators.h" #if TEST_STD_VER < 17 -#error "test/support/test_range.h" can only be included in builds supporting ranges +# error "test/support/test_range.h" can only be included in builds supporting ranges #endif struct sentinel { bool operator==(std::input_or_output_iterator auto const&) const; }; -template <template <class...> class I> -requires std::input_or_output_iterator<I<int*> > +template <template <class...> class I, class T = int> + requires std::input_or_output_iterator<I<T*> > struct test_range { - I<int*> begin(); - I<int const*> begin() const; + I<T*> begin(); + I<T const*> begin() const; sentinel end(); sentinel end() const; }; -template <template <class...> class I> -requires std::input_or_output_iterator<I<int*> > +template <template <class...> class I, class T = int> + requires std::input_or_output_iterator<I<T*> > struct test_non_const_range { - I<int*> begin(); + I<T*> begin(); sentinel end(); }; -template <template <class...> class I> -requires std::input_or_output_iterator<I<int*> > +template <template <class...> class I, class T = int> + requires std::input_or_output_iterator<I<T*> > struct test_common_range { - I<int*> begin(); - I<int const*> begin() const; - I<int*> end(); - I<int const*> end() const; + I<T*> begin(); + I<T const*> begin() const; + I<T*> end(); + I<T const*> end() const; }; -template <template <class...> class I> -requires std::input_or_output_iterator<I<int*> > +template <template <class...> class I, class T = int> + requires std::input_or_output_iterator<I<T*> > struct test_non_const_common_range { - I<int*> begin(); - I<int*> end(); + I<T*> begin(); + I<T*> end(); }; -template <template <class...> class I> -requires std::input_or_output_iterator<I<int*> > +template <template <class...> class I, class T = int> + requires std::input_or_output_iterator<I<T*> > struct test_view : std::ranges::view_base { - I<int*> begin(); - I<int const*> begin() const; + I<T*> begin(); + I<T const*> begin() const; sentinel end(); sentinel end() const; }; +template <class T = int> struct BorrowedRange { - int *begin() const; - int *end() const; + T* begin() const; + T* end() const; BorrowedRange(BorrowedRange&&) = delete; }; -template<> inline constexpr bool std::ranges::enable_borrowed_range<BorrowedRange> = true; -static_assert(!std::ranges::view<BorrowedRange>); -static_assert(std::ranges::borrowed_range<BorrowedRange>); +template <class T> +inline constexpr bool std::ranges::enable_borrowed_range<BorrowedRange<T>> = true; +static_assert(!std::ranges::view<BorrowedRange<>>); +static_assert(std::ranges::borrowed_range<BorrowedRange<>>); using BorrowedView = std::ranges::empty_view<int>; static_assert(std::ranges::view<BorrowedView>); |