[libc++][ranges][NFC] Consolidate range algorithm checks for returning `dangling`.

[var-const]

Summary

Also simplify the robust test files for non-boolean predicates and
omitting std::invoke.

[var-const]

libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp

39

I somehow missed this in the initial implementation -- variadics make things so much simpler.

[huixie90]

libcxx/include/__algorithm/ranges_remove_if.h

23 ↗

(On Diff #444557)

question. why do we need to include this header. borrowed_subrange_t is defined in subrange.h. can we consider dangling is a detail in borrowed_subrange_t?

libcxx/test/std/algorithms/ranges_robust_against_dangling.compile.pass.cpp

34 ↗

(On Diff #444557)

this is not an issue for the test because the test doesn't actually run the code. but this is undefined behaviour.
the data_ pointer points to the temporary copy std::array arr and will be dangling immediately after the constructor returns

This makes me think that we should probably actually run the code?

35 ↗

(On Diff #444557)

is this one used apart from called by the other constructor?

53 ↗

(On Diff #444557)

a possible additional to the test is dangling_both

53 ↗

(On Diff #444557)

perhaps it is outside the scope of this test, but for the existing tests in set operations, for those tests that are testing that the second argument is dangling, it also verifies the first argument is a normal iterator which points to the correct place. (but it might be over-testing)

155 ↗

(On Diff #444557)

you can enable this test if you rebase the main. also I think this one also needs to test the 2nd case

[philnik]

I think we should run the dangling tests and check their outputs. In theory we could optimize on an algorithms returning ranges::dangling. For some algorithms this would work perfectly, but for others there are side-effects where the current tests would catch the problem while this test doesn't. The nonbool and invoke changes LGTM.

[var-const]

Address feedback, rebase.

[var-const]

In D129741#3651996, @philnik wrote:

I think we should run the dangling tests and check their outputs. In theory we could optimize on an algorithms returning ranges::dangling. For some algorithms this would work perfectly, but for others there are side-effects where the current tests would catch the problem while this test doesn't. The nonbool and invoke changes LGTM.

Made this a runtime test and added a TODO to check the non-dangling iterators. I'm not removing any existing tests yet, so this patch is strictly improving coverage even without checking the results (and I won't remove existing checks without adding an equivalent check here). Quite a few existing tests either don't check for dangling at all or just check the return type.

I'm not convinced this check is worthwhile, by the way -- I can't think of a case where an algorithm would produce incorrect output in presence of dangling but work correctly otherwise. But if these checks could be made very brief, I can add them (or won't object if someone else does).

libcxx/include/__algorithm/ranges_remove_if.h

23 ↗

(On Diff #444557)

I simply forgot that borrowed_subrange_t isn't defined in dangling.h. Thanks for catching this!

libcxx/test/std/algorithms/ranges_robust_against_dangling.compile.pass.cpp

53 ↗

(On Diff #444557)

Re. dangling_both -- I thought about it and it seemed a little overkill, but since you mentioned it, I decided to add it anyway.

[huixie90]

libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp

46–47

I still prefer

decltype(auto) result = func(R(in), std::forward<Args>(args)...);
static_assert(std::same_as<decltype(result), ExpectedT>);

or

[[maybe_unused]] std::same_as<ExpectedT> decltype(auto) result = func(R(in), std::forward<Args>(args)...);

This way the tests actually run the algorithms instead of just checking the return type.

[var-const]

Address feedback and rebase.

[var-const]

libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp

46–47

Good point, done.

[var-const]

The Windows CI failure looks like a fluke.

[ldionne]

LGTM w/ comments. I think @philnik's comments have been addressed.

libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp

0

I think this should be a .pass.cpp.

libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp

0

I think this should be a .pass.cpp.

[var-const]

Address feedback.

[var-const]

Rebase on main.

[var-const]

Rebase on main.

libcxx/include/__algorithm/ranges_for_each_n.h

 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/projected.h>
 #include <__ranges/concepts.h>
-#include <__ranges/dangling.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 

libcxx/include/__algorithm/ranges_generate_n.h

 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
-#include <__ranges/dangling.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)

libcxx/include/__algorithm/ranges_includes.h

 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
-#include <__ranges/dangling.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)

libcxx/include/__algorithm/ranges_is_heap.h

 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
-#include <__ranges/dangling.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)

libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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-has-no-incomplete-ranges
+
+// <algorithm>
+//
+// Range algorithms should return `std::ranges::dangling` when given a dangling range.
+
+#include <algorithm>
+
+#include <array>
+#include <concepts>
+#include <iterator>
+#include <ranges>
+#include <random>
+
+#include "test_iterators.h"
+
+struct NonBorrowedRange {
+  using Iter = int*;
+  using Sent = sentinel_wrapper<Iter>;
+
+  int* data_;
+  size_t size_;
+
+  template <size_t N>
+  constexpr explicit NonBorrowedRange(std::array<int, N>& arr) : data_{arr.data()}, size_{arr.size()} {}
+
+  constexpr Iter begin() const { return data_; };
+  constexpr Sent end() const { return Sent{data_ + size_}; };
+};
+
+using R = NonBorrowedRange;
+
+// (dangling_in, ...)
+template <class ExpectedT = std::ranges::dangling, class Func, std::ranges::range Input, class ...Args>
+constexpr void dangling_1st(Func&& func, Input& in, Args&& ...args) {
+  decltype(auto) result = func(R(in), std::forward<Args>(args)...);
+  static_assert(std::same_as<decltype(result), ExpectedT>);
+}
+
+// (in, dangling_in, ...)
+template <class ExpectedT = std::ranges::dangling, class Func, std::ranges::range Input, class ...Args>
+constexpr void dangling_2nd(Func&& func, Input& in1, Input& in2, Args&& ...args) {
+  decltype(auto) result = func(in1, R(in2), std::forward<Args>(args)...);
+  static_assert(std::same_as<decltype(result), ExpectedT>);
+}
+
+// (dangling_in1, dangling_in2, ...)
+template <class ExpectedT = std::ranges::dangling, class Func, std::ranges::range Input, class ...Args>
+constexpr void dangling_both(Func&& func, Input& in1, Input& in2, Args&& ...args) {
+  decltype(auto) result = func(R(in1), R(in2), std::forward<Args>(args)...);
+  static_assert(std::same_as<decltype(result), ExpectedT>);
+}
+
+// TODO: also check the iterator values for algorithms that return `*_result` types.
+constexpr bool test_all() {
+  using std::ranges::dangling;
+
+  using std::ranges::binary_transform_result;
+  using std::ranges::copy_result;
+  //using std::ranges::copy_backward_result;
+  using std::ranges::copy_if_result;
+  using std::ranges::for_each_result;
+  using std::ranges::merge_result;
+  using std::ranges::minmax_result;
+  using std::ranges::mismatch_result;
+  using std::ranges::move_result;
+  //using std::ranges::move_backward_result;
+  //using std::ranges::partial_sort_copy_result;
+  //using std::ranges::partition_copy_result;
+  //using std::ranges::remove_copy_result;
+  //using std::ranges::remove_copy_if_result;
+  using std::ranges::reverse_copy_result;
+  using std::ranges::rotate_copy_result;
+  using std::ranges::set_difference_result;
+  using std::ranges::set_intersection_result;
+  using std::ranges::set_symmetric_difference_result;
+  using std::ranges::set_union_result;
+  using std::ranges::swap_ranges_result;
+  using std::ranges::unary_transform_result;
+  //using std::ranges::unique_copy_result;
+
+  auto unary_pred = [](int i) { return i > 0; };
+  auto binary_pred = [](int i, int j) { return i < j; };
+  //auto gen = [] { return 42; };
+  //std::mt19937 rand_gen;
+
+  std::array in = {1, 2, 3};
+  std::array in2 = {4, 5, 6};
+
+  auto mid = in.begin() + 1;
+
+  std::array output = {7, 8, 9, 10, 11, 12};
+  auto out = output.begin();
+  //auto out2 = output.begin() + 1;
+
+  int x = 2;
+  size_t count = 1;
+
+  dangling_1st(std::ranges::find, in, x);
+  dangling_1st(std::ranges::find_if, in, unary_pred);
+  dangling_1st(std::ranges::find_if_not, in, unary_pred);
+  dangling_1st(std::ranges::find_first_of, in, in2);
+  dangling_1st(std::ranges::adjacent_find, in);
+  dangling_1st<mismatch_result<dangling, int*>>(std::ranges::mismatch, in, in2);
+  dangling_2nd<mismatch_result<int*, dangling>>(std::ranges::mismatch, in, in2);
+  dangling_both<mismatch_result<dangling, dangling>>(std::ranges::mismatch, in, in2);
+  //dangling_1st(std::ranges::partition_point, in, unary_pred);
+  dangling_1st(std::ranges::lower_bound, in, x);
+  dangling_1st(std::ranges::upper_bound, in, x);
+  //dangling_1st(std::ranges::equal_range, in, x);
+  dangling_1st(std::ranges::min_element, in);
+  dangling_1st(std::ranges::max_element, in);
+  dangling_1st<minmax_result<dangling>>(std::ranges::minmax_element, in);
+  dangling_1st(std::ranges::search, in, in2);
+  dangling_1st(std::ranges::search_n, in, count, x);
+  dangling_1st(std::ranges::find_end, in, in2);
+  dangling_1st(std::ranges::is_sorted_until, in);
+  //dangling_1st(std::ranges::is_heap_until, in);
+  dangling_1st<for_each_result<dangling, decltype(unary_pred)>>(std::ranges::for_each, in, unary_pred);
+  dangling_1st<copy_result<dangling, int*>>(std::ranges::copy, in, out);
+  // TODO: uncomment `copy_backward` once https://reviews.llvm.org/D128864 lands.
+  //dangling_1st<copy_backward_result<dangling, int*>>(std::ranges::copy_backward, in, out);
+  dangling_1st<copy_if_result<dangling, int*>>(std::ranges::copy_if, in, out, unary_pred);
+  dangling_1st<move_result<dangling, int*>>(std::ranges::move, in, out);
+  // TODO: uncomment `move_backward` once https://reviews.llvm.org/D128864 lands.
+  //dangling_1st<move_backward_result<dangling, int*>>(std::ranges::move_backward, in, out);
+  dangling_1st(std::ranges::fill, in, x);
+  { // transform
+    std::array out_transform = {false, true, true};
+    dangling_1st<unary_transform_result<dangling, bool*>>(std::ranges::transform, in, out_transform.begin(), unary_pred);
+    dangling_1st<binary_transform_result<dangling, int*, bool*>>(
+        std::ranges::transform, in, in2, out_transform.begin(), binary_pred);
+    dangling_2nd<binary_transform_result<int*, dangling, bool*>>(
+        std::ranges::transform, in, in2, out_transform.begin(), binary_pred);
+    dangling_both<binary_transform_result<dangling, dangling, bool*>>(
+        std::ranges::transform, in, in2, out_transform.begin(), binary_pred);
+  }
+  //dangling_1st(std::ranges::generate, in, gen);
+  //dangling_1st<remove_copy_result<dangling, int*>>(std::ranges::remove_copy, in, out, x);
+  //dangling_1st<remove_copy_if_result<dangling, int*>>(std::ranges::remove_copy_if, in, out, unary_pred);
+  dangling_1st(std::ranges::replace, in, x, x);
+  dangling_1st(std::ranges::replace_if, in, std::identity{}, x);
+  //dangling_1st(std::ranges::replace_copy, in, out, x, x);
+  //dangling_1st(std::ranges::replace_copy_if, in, out, x, x);
+  dangling_1st<swap_ranges_result<dangling, int*>>(std::ranges::swap_ranges, in, in2);
+  dangling_2nd<swap_ranges_result<int*, dangling>>(std::ranges::swap_ranges, in, in2);
+  dangling_both<swap_ranges_result<dangling, dangling>>(std::ranges::swap_ranges, in, in2);
+  dangling_1st<reverse_copy_result<dangling, int*>>(std::ranges::reverse_copy, in, out);
+  dangling_1st<rotate_copy_result<dangling, int*>>(std::ranges::rotate_copy, in, mid, out);
+  //dangling_1st<unique_copy_result<dangling, int*>>(std::ranges::unique_copy, in, out);
+  //dangling_1st<partition_copy_result<dangling, int*, int*>>std::ranges::partition_copy(in, out, out2, unary_pred);
+  //dangling_1st<partial_sort_copy_result<dangling, int*>>(std::ranges::partial_sort_copy, in, in2);
+  //dangling_2nd<partial_sort_copy_result<int*, dangling>>(std::ranges::partial_sort_copy, in, in2);
+  //dangling_both<partial_sort_copy_result<dangling, dangling>>(std::ranges::partial_sort_copy, in, in2);
+  dangling_1st<merge_result<dangling, int*, int*>>(std::ranges::merge, in, in2, out);
+  dangling_2nd<merge_result<int*, dangling, int*>>(std::ranges::merge, in, in2, out);
+  dangling_both<merge_result<dangling, dangling, int*>>(std::ranges::merge, in, in2, out);
+  dangling_1st<set_difference_result<dangling, int*>>(std::ranges::set_difference, in, in2, out);
+  dangling_1st<set_intersection_result<dangling, int*, int*>>(std::ranges::set_intersection, in, in2, out);
+  dangling_2nd<set_intersection_result<int*, dangling, int*>>(std::ranges::set_intersection, in, in2, out);
+  dangling_both<set_intersection_result<dangling, dangling, int*>>(std::ranges::set_intersection, in, in2, out);
+  dangling_1st<set_symmetric_difference_result<dangling, int*, int*>>(
+      std::ranges::set_symmetric_difference, in, in2, out);
+  dangling_2nd<set_symmetric_difference_result<int*, dangling, int*>>(
+      std::ranges::set_symmetric_difference, in, in2, out);
+  dangling_both<set_symmetric_difference_result<dangling, dangling, int*>>(
+      std::ranges::set_symmetric_difference, in, in2, out);
+  dangling_1st<set_union_result<dangling, int*, int*>>(std::ranges::set_union, in, in2, out);
+  dangling_2nd<set_union_result<int*, dangling, int*>>(std::ranges::set_union, in, in2, out);
+  dangling_both<set_union_result<dangling, dangling, int*>>(std::ranges::set_union, in, in2, out);
+  dangling_1st(std::ranges::remove, in, x);
+  dangling_1st(std::ranges::remove_if, in, unary_pred);
+  dangling_1st(std::ranges::reverse, in);
+  //dangling_1st(std::ranges::rotate, in, mid);
+  //dangling_1st(std::ranges::shuffle, in, rand_gen);
+  //dangling_1st(std::ranges::unique, in);
+  //dangling_1st(std::ranges::partition, in, binary_pred);
+  //if (!std::is_constant_evaluated())
+  //  dangling_1st(std::ranges::stable_partition, in, binary_pred);
+  dangling_1st(std::ranges::sort, in);
+  //if (!std::is_constant_evaluated())
+  //  dangling_1st(std::ranges::stable_sort, in);
+  //dangling_1st(std::ranges::partial_sort, in, mid);
+  dangling_1st(std::ranges::nth_element, in, mid);
+  //if (!std::is_constant_evaluated())
+  //  dangling_1st(std::ranges::inplace_merge, in, mid);
+  dangling_1st(std::ranges::make_heap, in);
+  dangling_1st(std::ranges::push_heap, in);
+  dangling_1st(std::ranges::pop_heap, in);
+  dangling_1st(std::ranges::sort_heap, in);
+  //dangling_1st(std::ranges::prev_permutation, in);
+  //dangling_1st(std::ranges::next_permutation, in);
+
+  return true;
+}
+
+int main(int, char**) {
+  test_all();
+  static_assert(test_all());
+
+  return 0;
+}

libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-// 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-has-no-incomplete-ranges
-
-// <algorithm>
-//
-// Range algorithms that take predicates should support predicates that return a non-boolean value as long as the
-// returned type is implicitly convertible to bool.
-
-#include <algorithm>
-
-#include <array>
-#include <concepts>
-#include <initializer_list>
-#include <iterator>
-#include <ranges>
-
-#include "boolean_testable.h"
-
-auto unary_pred = [](int i) { return BooleanTestable(i > 0); };
-static_assert(!std::same_as<decltype(unary_pred(1)), bool>);
-static_assert(std::convertible_to<decltype(unary_pred(1)), bool>);
-
-auto binary_pred = [](int i, int j) { return BooleanTestable(i < j); };
-static_assert(!std::same_as<decltype(binary_pred(1, 2)), bool>);
-static_assert(std::convertible_to<decltype(binary_pred(1, 2)), bool>);
-
-// There are only a few typical signatures shared by most algorithms -- this set of helpers invokes both the
-// (iterator, sentinel, ...) and the (range, ...) overloads of the given niebloid.
-
-// (in, pred)
-template <class Func, std::ranges::range Input, class Pred>
-void in_pred(Func&& func, Input& in, Pred& pred) {
-  func(in.begin(), in.end(), pred);
-  func(in, pred);
-}
-
-// (in, val, pred)
-template <class Func, std::ranges::range Input, class T, class Pred>
-void in_val_pred(Func&& func, Input& in, T& value, Pred& pred) {
-  func(in.begin(), in.end(), value, pred);
-  func(in, value, pred);
-}
-
-// (in, out, pred)
-template <class Func, std::ranges::range Input, std::weakly_incrementable Output, class Pred>
-void in_out_pred(Func&& func, Input& in, Output& out, Pred& pred) {
-  func(in.begin(), in.end(), out, pred);
-  func(in, out, pred);
-}
-
-// (in1, in2, pred)
-template <class Func, std::ranges::range Input, class Pred>
-void in2_pred(Func&& func, Input& in1, Input& in2, Pred& pred) {
-  func(in1.begin(), in1.end(), in2.begin(), in2.end(), pred);
-  func(in1, in2, pred);
-}
-
-// (in1, in2, out, pred)
-template <class Func, std::ranges::range Input, std::weakly_incrementable Output, class Pred>
-void in2_out_pred(Func&& func, Input& in1, Input& in2, Output& out, Pred& pred) {
-  func(in1.begin(), in1.end(), in2.begin(), in2.end(), out, pred);
-  func(in1, in2, out, pred);
-}
-
-// (in, mid, pred)
-template <class Func, std::ranges::range Input, class Pred>
-void in_mid_pred(Func&& func, Input& in, std::ranges::iterator_t<Input>& mid, Pred& pred) {
-  func(in.begin(), mid, in.end(), pred);
-  func(in, mid, pred);
-}
-
-void test_all() {
-  std::array in = {1, 2, 3};
-  std::array in2 = {4, 5, 6};
-  auto mid = in.begin() + 1;
-
-  std::array output = {4, 5, 6};
-  auto out = output.begin();
-  //auto out2 = output.begin() + 1;
-
-  int x = 2;
-  int count = 1;
-
-  in_pred(std::ranges::any_of, in, unary_pred);
-  in_pred(std::ranges::all_of, in, unary_pred);
-  in_pred(std::ranges::none_of, in, unary_pred);
-  in_pred(std::ranges::find_if, in, unary_pred);
-  in_pred(std::ranges::find_if_not, in, unary_pred);
-  in2_pred(std::ranges::find_first_of, in, in2, binary_pred);
-  in_pred(std::ranges::adjacent_find, in, binary_pred);
-  in2_pred(std::ranges::mismatch, in, in2, binary_pred);
-  in2_pred(std::ranges::equal, in, in2, binary_pred);
-  in2_pred(std::ranges::lexicographical_compare, in, in2, binary_pred);
-  //in_pred(std::ranges::partition_point, unary_pred);
-  in_val_pred(std::ranges::lower_bound, in, x, binary_pred);
-  in_val_pred(std::ranges::upper_bound, in, x, binary_pred);
-  //in_val_pred(std::ranges::equal_range, in, x, binary_pred);
-  in_val_pred(std::ranges::binary_search, in, x, binary_pred);
-
-  // min
-  std::ranges::min(1, 2, binary_pred);
-  std::ranges::min(std::initializer_list<int>{1, 2}, binary_pred);
-  std::ranges::min(in, binary_pred);
-  // max
-  std::ranges::max(1, 2, binary_pred);
-  std::ranges::max(std::initializer_list<int>{1, 2}, binary_pred);
-  std::ranges::max(in, binary_pred);
-  // minmax
-  std::ranges::minmax(1, 2, binary_pred);
-  std::ranges::minmax(std::initializer_list<int>{1, 2}, binary_pred);
-  std::ranges::minmax(in, binary_pred);
-
-  in_pred(std::ranges::min_element, in, binary_pred);
-  in_pred(std::ranges::max_element, in, binary_pred);
-  in_pred(std::ranges::minmax_element, in, binary_pred);
-  in_pred(std::ranges::count_if, in, unary_pred);
-  //in2_pred(std::ranges::search, in, in2, binary_pred);
-  std::ranges::search_n(in.begin(), in.end(), count, x, binary_pred);
-  std::ranges::search_n(in, count, x, binary_pred);
-  in2_pred(std::ranges::find_end, in, in2, binary_pred);
-  in_pred(std::ranges::is_partitioned, in, unary_pred);
-  in_pred(std::ranges::is_sorted, in, binary_pred);
-  in_pred(std::ranges::is_sorted_until, in, binary_pred);
-  //in2_pred(std::ranges::includes, in, in2, binary_pred);
-  //in_pred(std::ranges::is_heap, in, binary_pred);
-  //in_pred(std::ranges::is_heap_until, in, binary_pred);
-  //std::ranges::clamp(2, 1, 3, binary_pred);
-  //in2_pred(std::ranges::is_permutation, in, in2, binary_pred);
-  in_out_pred(std::ranges::copy_if, in, out, unary_pred);
-  //in_out_pred(std::ranges::remove_copy_if, in, out, unary_pred);
-
-  // replace_if
-  //std::ranges::replace_if(in.begin(), in.end(), unary_pred, x);
-  //std::ranges::replace_if(in, unary_pred, x);
-  // replace_copy_if
-  //std::ranges::replace_copy_if(in.begin(), in.end(), out, unary_pred, x);
-  //std::ranges::replace_copy_if(in, out, unary_pred, x);
-
-  //in_out_pred(std::ranges::unique_copy, in, out, binary_pred);
-  // partition_copy
-  //std::ranges::partition_copy(in.begin(), in.end(), out, out2, unary_pred);
-  //std::ranges::partition_copy(in, out, out2, unary_pred);
-  //in2_pred(std::ranges::partial_sort_copy, in, in2, binary_pred);
-  in2_out_pred(std::ranges::merge, in, in2, out, binary_pred);
-  in2_out_pred(std::ranges::set_difference, in, in2, out, binary_pred);
-  in2_out_pred(std::ranges::set_intersection, in, in2, out, binary_pred);
-  in2_out_pred(std::ranges::set_symmetric_difference, in, in2, out, binary_pred);
-  in2_out_pred(std::ranges::set_union, in, in2, out, binary_pred);
-  in_pred(std::ranges::remove_if, in, unary_pred);
-  //in_pred(std::ranges::unique, in, binary_pred);
-  //in_pred(std::ranges::partition, in, binary_pred);
-  //in_pred(std::ranges::stable_partition, in, binary_pred);
-  in_pred(std::ranges::sort, in, binary_pred);
-  in_pred(std::ranges::stable_sort, in, binary_pred);
-  //in_mid_pred(std::ranges::partial_sort, in, mid, binary_pred);
-  in_mid_pred(std::ranges::nth_element, in, mid, binary_pred);
-  //in_mid_pred(std::ranges::inplace_merge, in, mid, binary_pred);
-  in_pred(std::ranges::make_heap, in, binary_pred);
-  in_pred(std::ranges::push_heap, in, binary_pred);
-  in_pred(std::ranges::pop_heap, in, binary_pred);
-  in_pred(std::ranges::sort_heap, in, binary_pred);
-  //in_pred(std::ranges::prev_permutation, in, binary_pred);
-  //in_pred(std::ranges::next_permutation, in, binary_pred);
-}

libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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-has-no-incomplete-ranges
+
+// <algorithm>
+//
+// Range algorithms that take predicates should support predicates that return a non-boolean value as long as the
+// returned type is implicitly convertible to bool.
+
+#include <algorithm>
+
+#include <array>
+#include <concepts>
+#include <initializer_list>
+#include <iterator>
+#include <ranges>
+
+#include "boolean_testable.h"
+
+auto unary_pred = [](int i) { return BooleanTestable(i > 0); };
+static_assert(!std::same_as<decltype(unary_pred(1)), bool>);
+static_assert(std::convertible_to<decltype(unary_pred(1)), bool>);
+
+auto binary_pred = [](int i, int j) { return BooleanTestable(i < j); };
+static_assert(!std::same_as<decltype(binary_pred(1, 2)), bool>);
+static_assert(std::convertible_to<decltype(binary_pred(1, 2)), bool>);
+
+// Invokes both the (iterator, sentinel, ...) and the (range, ...) overloads of the given niebloid.
+
+// (in, ...)
+template <class Func, std::ranges::range Input, class ...Args>
+constexpr void test(Func&& func, Input& in, Args&& ...args) {
+  func(in.begin(), in.end(), std::forward<Args>(args)...);
+  func(in, std::forward<Args>(args)...);
+}
+
+// (in1, in2, ...)
+template <class Func, std::ranges::range Input, class ...Args>
+constexpr void test(Func&& func, Input& in1, Input& in2, Args&& ...args) {
+  func(in1.begin(), in1.end(), in2.begin(), in2.end(), std::forward<Args>(args)...);
+  func(in1, in2, std::forward<Args>(args)...);
+}
+
+// (in, mid, ...)
+template <class Func, std::ranges::range Input, class ...Args>
+constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input> mid, Args&& ...args) {
+  func(in.begin(), mid, in.end(), std::forward<Args>(args)...);
+  func(in, mid, std::forward<Args>(args)...);
+}
+
+constexpr bool test_all() {
+  std::array in = {1, 2, 3};
+  std::array in2 = {4, 5, 6};
+  auto mid = in.begin() + 1;
+
+  std::array output = {7, 8, 9, 10, 11, 12};
+  auto out = output.begin();
+  //auto out2 = output.begin() + 1;
+
+  int x = 2;
+  int count = 1;
+
+  test(std::ranges::any_of, in, unary_pred);
+  test(std::ranges::all_of, in, unary_pred);
+  test(std::ranges::none_of, in, unary_pred);
+  test(std::ranges::find_if, in, unary_pred);
+  test(std::ranges::find_if_not, in, unary_pred);
+  test(std::ranges::find_first_of, in, in2, binary_pred);
+  test(std::ranges::adjacent_find, in, binary_pred);
+  test(std::ranges::mismatch, in, in2, binary_pred);
+  test(std::ranges::equal, in, in2, binary_pred);
+  test(std::ranges::lexicographical_compare, in, in2, binary_pred);
+  //test(std::ranges::partition_point, unary_pred);
+  test(std::ranges::lower_bound, in, x, binary_pred);
+  test(std::ranges::upper_bound, in, x, binary_pred);
+  //test(std::ranges::equal_range, in, x, binary_pred);
+  test(std::ranges::binary_search, in, x, binary_pred);
+
+  // min
+  std::ranges::min(1, 2, binary_pred);
+  std::ranges::min(std::initializer_list<int>{1, 2}, binary_pred);
+  std::ranges::min(in, binary_pred);
+  // max
+  std::ranges::max(1, 2, binary_pred);
+  std::ranges::max(std::initializer_list<int>{1, 2}, binary_pred);
+  std::ranges::max(in, binary_pred);
+  // minmax
+  std::ranges::minmax(1, 2, binary_pred);
+  std::ranges::minmax(std::initializer_list<int>{1, 2}, binary_pred);
+  std::ranges::minmax(in, binary_pred);
+
+  test(std::ranges::min_element, in, binary_pred);
+  test(std::ranges::max_element, in, binary_pred);
+  test(std::ranges::minmax_element, in, binary_pred);
+  test(std::ranges::count_if, in, unary_pred);
+  test(std::ranges::search, in, in2, binary_pred);
+  test(std::ranges::search_n, in, count, x, binary_pred);
+  test(std::ranges::find_end, in, in2, binary_pred);
+  test(std::ranges::is_partitioned, in, unary_pred);
+  test(std::ranges::is_sorted, in, binary_pred);
+  test(std::ranges::is_sorted_until, in, binary_pred);
+  //test(std::ranges::includes, in, in2, binary_pred);
+  //test(std::ranges::is_heap, in, binary_pred);
+  //test(std::ranges::is_heap_until, in, binary_pred);
+  //std::ranges::clamp(2, 1, 3, binary_pred);
+  //test(std::ranges::is_permutation, in, in2, binary_pred);
+  test(std::ranges::copy_if, in, out, unary_pred);
+  //test(std::ranges::remove_copy_if, in, out, unary_pred);
+  //test(std::ranges::replace_if, in, unary_pred, x);
+  //test(std::ranges::replace_copy_if, in, out, unary_pred, x);
+  //test(std::ranges::unique_copy, in, out, binary_pred);
+  //test(std::ranges::partition_copy, in, out, out2, unary_pred);
+  //test(std::ranges::partial_sort_copy, in, in2, binary_pred);
+  test(std::ranges::merge, in, in2, out, binary_pred);
+  test(std::ranges::set_difference, in, in2, out, binary_pred);
+  test(std::ranges::set_intersection, in, in2, out, binary_pred);
+  test(std::ranges::set_symmetric_difference, in, in2, out, binary_pred);
+  test(std::ranges::set_union, in, in2, out, binary_pred);
+  test(std::ranges::remove_if, in, unary_pred);
+  //test(std::ranges::unique, in, binary_pred);
+  //test(std::ranges::partition, in, binary_pred);
+  //test(std::ranges::stable_partition, in, binary_pred);
+  test(std::ranges::sort, in, binary_pred);
+  if (!std::is_constant_evaluated())
+    test(std::ranges::stable_sort, in, binary_pred);
+  //test_mid(std::ranges::partial_sort, in, mid, binary_pred);
+  test_mid(std::ranges::nth_element, in, mid, binary_pred);
+  //test_mid(std::ranges::inplace_merge, in, mid, binary_pred);
+  test(std::ranges::make_heap, in, binary_pred);
+  test(std::ranges::push_heap, in, binary_pred);
+  test(std::ranges::pop_heap, in, binary_pred);
+  test(std::ranges::sort_heap, in, binary_pred);
+  //test(std::ranges::prev_permutation, in, binary_pred);
+  //test(std::ranges::next_permutation, in, binary_pred);
+
+  return true;
+}
+
+int main(int, char**) {
+  test_all();
+  static_assert(test_all());
+
+  return 0;
+}

libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-// 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-has-no-incomplete-ranges
-
-// <algorithm>
-//
-// Range algorithms should use `std::invoke` to call the given projection(s) (and predicates, where applicable).
-
-#include <algorithm>
-
-#include <array>
-#include <concepts>
-#include <initializer_list>
-#include <iterator>
-#include <ranges>
-
-struct Foo {
-  int val;
-  constexpr bool unary_pred() const { return val > 0; }
-  constexpr bool binary_pred(const Foo& rhs) const { return val < rhs.val; }
-  constexpr auto operator<=>(const Foo&) const = default;
-};
-
-struct Bar {
-  Foo val;
-  Bar create() const { return Bar(); }
-};
-
-// There are only a few typical signatures shared by most algorithms -- this set of helpers invokes both the
-// (iterator, sentinel, ...) and the (range, ...) overloads of the given niebloid.
-
-// (in, val)
-template <class Func, std::ranges::range Input, class T, class Proj>
-void in_val(Func&& func, Input& in, const T& val, Proj&& proj) {
-  func(in.begin(), in.end(), val, proj);
-  func(in, val, proj);
-}
-
-// (in, pred)
-template <class Func, std::ranges::range Input, class Pred, class Proj>
-void in_pred(Func&& func, Input& in, Pred&& pred, Proj&& proj) {
-  func(in.begin(), in.end(), pred, proj);
-  func(in, pred, proj);
-}
-
-// (in, val, pred)
-template <class Func, std::ranges::range Input, class T, class Pred, class Proj>
-void in_val_pred(Func&& func, Input& in, const T& val, Pred&& pred, Proj&& proj) {
-  func(in.begin(), in.end(), val, pred, proj);
-  func(in, val, pred, proj);
-}
-
-// (in1, in2, pred) -- two projections.
-template <class Func, std::ranges::range Input, class Pred, class Proj1, class Proj2>
-void in2_pred(Func&& func, Input& in1, Input& in2, Pred&& pred, Proj1&& proj1, Proj2&& proj2) {
-  func(in1.begin(), in1.end(), in2.begin(), in2.end(), pred, proj1, proj2);
-  func(in1, in2, pred, proj1, proj2);
-}
-
-// (in, out, pred)
-template <class Func, std::ranges::range Input, std::weakly_incrementable Output, class Pred, class Proj>
-void in_out_pred(Func&& func, Input& in, Output out, Pred&& pred, Proj&& proj) {
-  func(in.begin(), in.end(), out, pred, proj);
-  func(in, out, pred, proj);
-}
-
-// (in, mid, pred)
-template <class Func, std::ranges::range Input, std::input_iterator Iter, class Pred, class Proj>
-void in_mid_pred(Func&& func, Input& in, Iter mid, Pred&& pred, Proj&& proj) {
-  func(in.begin(), mid, in.end(), pred, proj);
-  func(in, mid, pred, proj);
-}
-
-// (in1, in2, out, pred) -- two projections.
-template <class Func, std::ranges::range Input, std::weakly_incrementable Output, class Pred, class Proj1, class Proj2>
-void in2_out_pred(Func&& func, Input& in1, Input& in2, Output out, Pred&& pred, Proj1&& proj1, Proj2&& proj2) {
-  func(in1.begin(), in1.end(), in2.begin(), in2.end(), out, pred, proj1, proj2);
-  func(in1, in2, out, pred, proj1, proj2);
-}
-
-void test_all() {
-  std::array in = {Bar{Foo{1}}, Bar{Foo{2}}, Bar{Foo{3}}};
-  std::array in2 = {Bar{Foo{4}}, Bar{Foo{5}}, Bar{Foo{6}}};
-  auto mid = in.begin() + 1;
-
-  std::array output = {Bar{Foo{4}}, Bar{Foo{5}}, Bar{Foo{6}}};
-  auto out = output.begin();
-  //auto out2 = output.begin() + 1;
-
-  Bar a{Foo{1}};
-  Bar b{Foo{2}};
-  //Bar c{Foo{3}};
-
-  Foo x{2};
-  size_t count = 1;
-
-  in_pred(std::ranges::any_of, in, &Foo::unary_pred, &Bar::val);
-  in_pred(std::ranges::all_of, in, &Foo::unary_pred, &Bar::val);
-  in_pred(std::ranges::none_of, in, &Foo::unary_pred, &Bar::val);
-  in_val(std::ranges::find, in, x, &Bar::val);
-  in_pred(std::ranges::find_if, in, &Foo::unary_pred, &Bar::val);
-  in_pred(std::ranges::find_if_not, in, &Foo::unary_pred, &Bar::val);
-  in2_pred(std::ranges::find_first_of, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
-  in_pred(std::ranges::adjacent_find, in, &Foo::binary_pred, &Bar::val);
-  in2_pred(std::ranges::mismatch, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
-  in2_pred(std::ranges::equal, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
-  in2_pred(std::ranges::lexicographical_compare, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
-  //in_pred(std::ranges::partition_point, in, &Foo::unary_pred, &Bar::val);
-  in_val_pred(std::ranges::lower_bound, in, x, &Foo::binary_pred, &Bar::val);
-  in_val_pred(std::ranges::upper_bound, in, x, &Foo::binary_pred, &Bar::val);
-  //in_val_pred(std::ranges::equal_range, in, x, &Foo::binary_pred, &Bar::val);
-  in_val_pred(std::ranges::binary_search, in, x, &Foo::binary_pred, &Bar::val);
-
-  // min
-  std::ranges::min(a, b, &Foo::binary_pred, &Bar::val);
-  std::ranges::min(std::initializer_list<Bar>{a, b}, &Foo::binary_pred, &Bar::val);
-  std::ranges::min(in, &Foo::binary_pred, &Bar::val);
-  // max
-  std::ranges::max(a, b, &Foo::binary_pred, &Bar::val);
-  std::ranges::max(std::initializer_list<Bar>{a, b}, &Foo::binary_pred, &Bar::val);
-  std::ranges::max(in, &Foo::binary_pred, &Bar::val);
-  // minmax
-  std::ranges::minmax(a, b, &Foo::binary_pred, &Bar::val);
-  std::ranges::minmax(std::initializer_list<Bar>{a, b}, &Foo::binary_pred, &Bar::val);
-  std::ranges::minmax(in, &Foo::binary_pred, &Bar::val);
-
-  in_pred(std::ranges::min_element, in, &Foo::binary_pred, &Bar::val);
-  in_pred(std::ranges::max_element, in, &Foo::binary_pred, &Bar::val);
-  in_pred(std::ranges::minmax_element, in, &Foo::binary_pred, &Bar::val);
-  in_val(std::ranges::count, in, x, &Bar::val);
-  in_pred(std::ranges::count_if, in, &Foo::unary_pred, &Bar::val);
-  in2_pred(std::ranges::search, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
-  // search_n
-  std::ranges::search_n(in.begin(), in.end(), count, x, &Foo::binary_pred, &Bar::val);
-  std::ranges::search_n(in, count, x, &Foo::binary_pred, &Bar::val);
-  in2_pred(std::ranges::find_end, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
-  in_pred(std::ranges::is_partitioned, in, &Foo::unary_pred, &Bar::val);
-  in_pred(std::ranges::is_sorted, in, &Foo::binary_pred, &Bar::val);
-  in_pred(std::ranges::is_sorted_until, in, &Foo::binary_pred, &Bar::val);
-  //in2_pred(std::ranges::includes, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
-  //in_pred(std::ranges::is_heap, in, &Foo::binary_pred, &Bar::val);
-  //in_pred(std::ranges::is_heap_until, in, &Foo::binary_pred, &Bar::val);
-  //std::ranges::clamp(b, a, c, &Foo::binary_pred);
-  //in2_pred(std::ranges::is_permutation, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
-  in_pred(std::ranges::for_each, in, &Foo::unary_pred, &Bar::val);
-  std::ranges::for_each_n(in.begin(), count, &Foo::unary_pred, &Bar::val);
-  // `copy`, `copy_n` and `copy_backward` have neither a projection nor a predicate.
-  in_out_pred(std::ranges::copy_if, in, out, &Foo::unary_pred, &Bar::val);
-  // `move` and `move_backward` have neither a projection nor a predicate.
-  // `fill` and `fill_n` have neither a projection nor a predicate.
-  {
-    std::array out_transform = {false, true, true};
-    in_out_pred(std::ranges::transform, in, out_transform.begin(), &Foo::unary_pred, &Bar::val);
-  }
-  // generate
-  //std::ranges::generate(in.begin(), in.end(), &Bar::create);
-  //std::ranges::generate(in, &Bar::create);
-  // generate_n
-  //std::ranges::generate(in.begin(), count, &Bar::create);
-  // remove_copy
-  //std::ranges::remove_copy(in.begin(), in.end(), out, x, &Bar::val);
-  //std::ranges::remove_copy(in, out, x, &Bar::val);
-  //in_out_pred(std::ranges::remove_copy_if, in, out, &Foo::unary_pred, &Bar::val);
-  // `replace*` algorithms only use the projection to compare the elements, not to write them.
-  // replace
-  std::ranges::replace(in.begin(), in.end(), x, a, &Bar::val);
-  std::ranges::replace(in, x, a, &Bar::val);
-  // replace_if
-  std::ranges::replace_if(in.begin(), in.end(), &Foo::unary_pred, a, &Bar::val);
-  std::ranges::replace_if(in, &Foo::unary_pred, a, &Bar::val);
-  // replace_copy
-  //std::ranges::replace_copy(in.begin(), in.end(), out, x, a, &Bar::val);
-  //std::ranges::replace_copy(in, out, x, a, &Bar::val);
-  // replace_copy_if
-  //std::ranges::replace_copy_if(in.begin(), in.end(), out, pred, a, &Bar::val);
-  //std::ranges::replace_copy_if(in, out, pred, a, &Bar::val);
-  // `swap_ranges` has neither a projection nor a predicate.
-  // `reverse_copy` has neither a projection nor a predicate.
-  // `rotate_copy` has neither a projection nor a predicate.
-  // `sample` has no requirement that the given generator be invoked via `std::invoke`.
-  //in_out_pred(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val);
-  // partition_copy
-  //std::ranges::partition_copy(in.begin(), in.end(), out, out2, &Foo::unary_pred, &Bar::val);
-  //std::ranges::partition_copy(in, out, out2, &Foo::unary_pred, &Bar::val);
-  //in2_pred(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val);
-  in2_out_pred(std::ranges::merge, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
-  in2_out_pred(std::ranges::set_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
-  in2_out_pred(std::ranges::set_intersection, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
-  in2_out_pred(std::ranges::set_symmetric_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
-  in2_out_pred(std::ranges::set_union, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
-  in_val(std::ranges::remove, in, x, &Bar::val);
-  in_pred(std::ranges::remove_if, in, &Foo::unary_pred, &Bar::val);
-  // `reverse` has neither a projection nor a predicate.
-  // `rotate` has neither a projection nor a predicate.
-  // `shuffle` has neither a projection nor a predicate.
-  //in_pred(std::ranges::unique, in, &Foo::binary_pred, &Bar::val);
-  //in_pred(std::ranges::partition, in, &Foo::binary_pred, &Bar::val);
-  //in_pred(std::ranges::stable_partition, in, &Foo::binary_pred, &Bar::val);
-  in_pred(std::ranges::sort, in, &Foo::binary_pred, &Bar::val);
-  in_pred(std::ranges::stable_sort, in, &Foo::binary_pred, &Bar::val);
-  //in_mid_pred(std::ranges::partial_sort, in, mid, binary_pred);
-  in_mid_pred(std::ranges::nth_element, in, mid, &Foo::binary_pred, &Bar::val);
-  //in_mid_pred(std::ranges::inplace_merge, in, mid, binary_pred);
-  in_pred(std::ranges::make_heap, in, &Foo::binary_pred, &Bar::val);
-  in_pred(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val);
-  in_pred(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val);
-  in_pred(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val);
-  //in_pred(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val);
-  //in_pred(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val);
-}

libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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-has-no-incomplete-ranges
+
+// <algorithm>
+//
+// Range algorithms should use `std::invoke` to call the given projection(s) (and predicates, where applicable).
+
+#include <algorithm>
+
+#include <array>
+#include <concepts>
+#include <initializer_list>
+#include <iterator>
+#include <ranges>
+
+struct Foo {
+  int val;
+  constexpr bool unary_pred() const { return val > 0; }
+  constexpr bool binary_pred(const Foo& rhs) const { return val < rhs.val; }
+  constexpr auto operator<=>(const Foo&) const = default;
+};
+
+struct Bar {
+  Foo val;
+  Bar create() const { return Bar(); }
+};
+
+// Invokes both the (iterator, sentinel, ...) and the (range, ...) overloads of the given niebloid.
+
+// (in, ...)
+template <class Func, std::ranges::range Input, class ...Args>
+constexpr void test(Func&& func, Input& in, Args&& ...args) {
+  func(in.begin(), in.end(), std::forward<Args>(args)...);
+  func(in, std::forward<Args>(args)...);
+}
+
+// (in1, in2, ...)
+template <class Func, std::ranges::range Input, class ...Args>
+constexpr void test(Func&& func, Input& in1, Input& in2, Args&& ...args) {
+  func(in1.begin(), in1.end(), in2.begin(), in2.end(), std::forward<Args>(args)...);
+  func(in1, in2, std::forward<Args>(args)...);
+}
+
+// (in, mid, ...)
+template <class Func, std::ranges::range Input, class ...Args>
+constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input> mid, Args&& ...args) {
+  func(in.begin(), mid, in.end(), std::forward<Args>(args)...);
+  func(in, mid, std::forward<Args>(args)...);
+}
+
+constexpr bool test_all() {
+  std::array in = {Bar{Foo{1}}, Bar{Foo{2}}, Bar{Foo{3}}};
+  std::array in2 = {Bar{Foo{4}}, Bar{Foo{5}}, Bar{Foo{6}}};
+  auto mid = in.begin() + 1;
+
+  std::array output = {Bar{Foo{7}}, Bar{Foo{8}}, Bar{Foo{9}}, Bar{Foo{10}}, Bar{Foo{11}}, Bar{Foo{12}}};
+  auto out = output.begin();
+  //auto out2 = output.begin() + 1;
+
+  Bar a{Foo{1}};
+  Bar b{Foo{2}};
+  //Bar c{Foo{3}};
+
+  Foo x{2};
+  size_t count = 1;
+
+  test(std::ranges::any_of, in, &Foo::unary_pred, &Bar::val);
+  test(std::ranges::all_of, in, &Foo::unary_pred, &Bar::val);
+  test(std::ranges::none_of, in, &Foo::unary_pred, &Bar::val);
+  test(std::ranges::find, in, x, &Bar::val);
+  test(std::ranges::find_if, in, &Foo::unary_pred, &Bar::val);
+  test(std::ranges::find_if_not, in, &Foo::unary_pred, &Bar::val);
+  test(std::ranges::find_first_of, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::adjacent_find, in, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::mismatch, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::equal, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::lexicographical_compare, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
+  //test(std::ranges::partition_point, in, &Foo::unary_pred, &Bar::val);
+  test(std::ranges::lower_bound, in, x, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::upper_bound, in, x, &Foo::binary_pred, &Bar::val);
+  //test(std::ranges::equal_range, in, x, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::binary_search, in, x, &Foo::binary_pred, &Bar::val);
+
+  // min
+  std::ranges::min(a, b, &Foo::binary_pred, &Bar::val);
+  std::ranges::min(std::initializer_list<Bar>{a, b}, &Foo::binary_pred, &Bar::val);
+  std::ranges::min(in, &Foo::binary_pred, &Bar::val);
+  // max
+  std::ranges::max(a, b, &Foo::binary_pred, &Bar::val);
+  std::ranges::max(std::initializer_list<Bar>{a, b}, &Foo::binary_pred, &Bar::val);
+  std::ranges::max(in, &Foo::binary_pred, &Bar::val);
+  // minmax
+  std::ranges::minmax(a, b, &Foo::binary_pred, &Bar::val);
+  std::ranges::minmax(std::initializer_list<Bar>{a, b}, &Foo::binary_pred, &Bar::val);
+  std::ranges::minmax(in, &Foo::binary_pred, &Bar::val);
+
+  test(std::ranges::min_element, in, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::max_element, in, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::minmax_element, in, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::count, in, x, &Bar::val);
+  test(std::ranges::count_if, in, &Foo::unary_pred, &Bar::val);
+  test(std::ranges::search, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::search_n, in, count, x, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::find_end, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::is_partitioned, in, &Foo::unary_pred, &Bar::val);
+  test(std::ranges::is_sorted, in, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::is_sorted_until, in, &Foo::binary_pred, &Bar::val);
+  //test(std::ranges::includes, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
+  //test(std::ranges::is_heap, in, &Foo::binary_pred, &Bar::val);
+  //test(std::ranges::is_heap_until, in, &Foo::binary_pred, &Bar::val);
+  //std::ranges::clamp(b, a, c, &Foo::binary_pred);
+  //test(std::ranges::is_permutation, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::for_each, in, &Foo::unary_pred, &Bar::val);
+  std::ranges::for_each_n(in.begin(), count, &Foo::unary_pred, &Bar::val);
+  // `copy`, `copy_n` and `copy_backward` have neither a projection nor a predicate.
+  test(std::ranges::copy_if, in, out, &Foo::unary_pred, &Bar::val);
+  // `move` and `move_backward` have neither a projection nor a predicate.
+  // `fill` and `fill_n` have neither a projection nor a predicate.
+  {
+    std::array out_transform = {false, true, true};
+    test(std::ranges::transform, in, out_transform.begin(), &Foo::unary_pred, &Bar::val);
+  }
+  //test(std::ranges::generate, in, &Bar::create);
+  //std::ranges::generate_n(in.begin(), count, &Bar::create);
+  //test(std::ranges::remove_copy, in, out, x, &Bar::val);
+  //test(std::ranges::remove_copy_if, in, out, &Foo::unary_pred, &Bar::val);
+  // `replace*` algorithms only use the projection to compare the elements, not to write them.
+  test(std::ranges::replace, in, x, a, &Bar::val);
+  test(std::ranges::replace_if, in, &Foo::unary_pred, a, &Bar::val);
+  //test(std::ranges::replace_copy, in, out, x, a, &Bar::val);
+  //test(std::ranges::replace_copy_if, in, out, pred, a, &Bar::val);
+  // `swap_ranges` has neither a projection nor a predicate.
+  // `reverse_copy` has neither a projection nor a predicate.
+  // `rotate_copy` has neither a projection nor a predicate.
+  // `sample` has no requirement that the given generator be invoked via `std::invoke`.
+  //test(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val);
+  //test(std::ranges::partition_copy, in, out, out2, &Foo::unary_pred, &Bar::val);
+  //test(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::merge, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::set_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::set_intersection, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::set_symmetric_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::set_union, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::remove, in, x, &Bar::val);
+  test(std::ranges::remove_if, in, &Foo::unary_pred, &Bar::val);
+  // `reverse` has neither a projection nor a predicate.
+  // `rotate` has neither a projection nor a predicate.
+  // `shuffle` has neither a projection nor a predicate.
+  //test(std::ranges::unique, in, &Foo::binary_pred, &Bar::val);
+  //test(std::ranges::partition, in, &Foo::binary_pred, &Bar::val);
+  //test(std::ranges::stable_partition, in, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::sort, in, &Foo::binary_pred, &Bar::val);
+  if (!std::is_constant_evaluated())
+    test(std::ranges::stable_sort, in, &Foo::binary_pred, &Bar::val);
+  //test_mid(std::ranges::partial_sort, in, mid, binary_pred);
+  test_mid(std::ranges::nth_element, in, mid, &Foo::binary_pred, &Bar::val);
+  //test_mid(std::ranges::inplace_merge, in, mid, binary_pred);
+  test(std::ranges::make_heap, in, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val);
+  //test(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val);
+  //test(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val);
+
+  return true;
+}
+
+int main(int, char**) {
+  test_all();
+  static_assert(test_all());
+
+  return 0;
+}

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp

 #include <initializer_list>
 #include <iterator>
 #include <memory>
 #include <random>
 #include <ranges>
 
 #include "test_iterators.h"
 
+// (in, ...)
 template <class Func, std::ranges::range Input, class ...Args>
 constexpr void test(Func&& func, Input& in, Args&& ...args) {
   func(in.begin(), in.end(), std::forward<Args>(args)...);
   func(in, std::forward<Args>(args)...);
 }
 
+// (in1, in2, ...)
 template <class Func, std::ranges::range Range1, std::ranges::range Range2, class ...Args>
 constexpr void test(Func&& func, Range1& r1, Range2& r2, Args&& ...args) {
   func(r1.begin(), r1.end(), r2.begin(), r2.end(), std::forward<Args>(args)...);
   func(r1, r2, std::forward<Args>(args)...);
 }
 
+// (in, mid, ...)
 template <class Func, std::ranges::range Input, class ...Args>
 constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input> mid, Args&& ...args) {
   func(in.begin(), mid, in.end(), std::forward<Args>(args)...);
   func(in, mid, std::forward<Args>(args)...);
 }
 
 constexpr bool test_all() {
   std::array input = {1, 2, 3};
constexpr bool test_all() {
   //test(std::ranges::replace_copy, in, out, x, x);
   //test(std::ranges::replace_copy_if, in, out, unary_pred, x);
   //test(std::ranges::swap_ranges, in, in2);
   test(std::ranges::reverse_copy, in, out);
   test_mid(std::ranges::rotate_copy, in, mid, out);
   //test(std::ranges::sample, in, out, count, rand_gen);
   //test(std::ranges::unique_copy, in, out);
   //test(std::ranges::partition_copy, in, out, out2, unary_pred);
-  //test_mid(std::ranges::partial_sort_copy, in, in2);
+  //test(std::ranges::partial_sort_copy, in, in2);
   test(std::ranges::merge, in, in2, out);
   test(std::ranges::set_difference, in, in2, out);
   test(std::ranges::set_intersection, in, in2, out);
   test(std::ranges::set_symmetric_difference, in, in2, out);
   test(std::ranges::set_union, in, in2, out);
   test(std::ranges::remove, in, x);
   test(std::ranges::remove_if, in, unary_pred);
   test(std::ranges::reverse, in);