[libc++][ranges][NFC] Consolidate some repetitive range algorithm tests:

[var-const]

Summary

• checking that the algorithm supports predicates returning a non-boolean type that's implicitly convertible to bool;
• checking that predicates and/or projections are invoked using std::invoke.

[var-const]

Add comment.

[philnik]

All in all I think it's a good idea. I don't really see a way to fuck it up other than with malicious intent if it compiles. You'd have to do something like if (!is_same_v<decltype(pred()), bool>) { /*do stuff*/ }). If you do bool b = pred() or if (pred()) it would be implicitly converted to bool. if you do auto x = pred(); auto y = x; if (x) {} it would error at compile-time. IIUC even if you'd use invoke_r<bool, ...>(pred) it should get implicitly converted.

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

20

Nit: Add a newline between <> and "" includes

78

I don't think a TODO makes a lot of sense here. We are quite good at adding the tests as we go by now I think.

170–174

Maybe just make it a .compile.pass.cpp? It's not like we learn anything from running them. They probably work properly if they compile.

[var-const]

Add tests for omitting std::invoke.

[var-const]

My plan is to omit these tests from the remaining unimplemented range algorithms going forward, but leave the existing tests be for now (I'll clean them up later once we're done with the initial implementation of the algorithms).

The primary motivation for this patch is to reduce the amount of drudgery when implementing a new algorithm. I also think that having these closely related tests consolidated together makes them more readable.

A potential downside is that we're no longer testing that the algorithms behave correctly. However, I think these checks were redundant -- the probability of an algorithm compiling but producing incorrect results when given e.g. a non-bool predicate seems to be essentially zero.

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

39 ↗

(On Diff #443544)

Originally I tried to have a single overloaded function for each kind of invocation, but I found that there is too much complexity when trying to distinguish between different invocations that have the same number of arguments (especially the unconstrained arguments like predicates, projections and values). Additionally, I think that cataloguing all the different algorithm signatures has some value.

108 ↗

(On Diff #443544)

I avoided creating helper functions here because their main benefit is taking care of both the (iterator, sentinel) and (range) overloads which doesn't apply here.

125 ↗

(On Diff #443544)

In general, I avoided creating a helper function unless there were at least 3 uses of it within the file.

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

159 ↗

(On Diff #443544)

I'm reusing the name "predicate" here even though it's arguably a little hacky.

[var-const]

Fix the CI.

[philnik]

LGTM % nits.

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

174–178 ↗

(On Diff #443743)

The main shouldn't be required anymore. Also applies to the invoke test.

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

1 ↗

(On Diff #443743)

Please update the PR title.

201 ↗

(On Diff #443743)

I would just omit the algorithms for which the test doesn't apply, like we do in the other robust_against_x tests.

[var-const]

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

201 ↗

(On Diff #443743)

Hmm, I'm inclined to leave these in. It makes it easier to verify that no algorithm has been accidentally omitted.

[var-const]

Address feedback

[philnik]

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

201 ↗

(On Diff #443743)

Do it as you see fit. I don't have any strong opinions here. I mostly wanted to note that this deviates from the other tests.

[huixie90]

It seems that the "ranges_robust_against_copying_xxx" tests are in "test/libcxx/algorithms" and these "ranges_robust_against_" tests are in "test/std/algorithms".
Is there a reason for using different directories?

[var-const]

In D129414#3647373, @huixie90 wrote:

It seems that the "ranges_robust_against_copying_xxx" tests are in "test/libcxx/algorithms" and these "ranges_robust_against_" tests are in "test/std/algorithms".
Is there a reason for using different directories?

Tests under the std directory should pass on any valid standard library implementation, while tests under libcxx are libc++-specific. It's not mandated that we don't copy comparators or projections (AFAIK, GCC does), it's just a self-imposed optimization (see https://reviews.llvm.org/D114136 for more context). OTOH, the behavior in these tests I believe is mandated by the standard, so it should go under std.

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 "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>);
+
+// (in, pred)
+template <class Func, std::ranges::range Input, class Pred>
+void test(Func&& func, Input& in, Pred& pred) {
+  func(in.begin(), in.end(), pred);
+  func(in, pred);
+}
+
+// (in1, in2, pred)
+template <class Func, std::ranges::range Input, class Pred>
+void test(Func&& func, Input& in1, Input& in2, Pred& pred) {
+  func(in1.begin(), in1.end(), in2.begin(), in2.end(), pred);
+  func(in1, in2, pred);
+}
+
+// (in, out, pred)
+template <class Func, std::ranges::range Input, std::weakly_incrementable Output, class Pred>
+void test(Func&& func, Input& in, Output& out, Pred& pred) {
+  func(in.begin(), in.end(), out, pred);
+  func(in, out, pred);
+}
+
+// (in, mid, pred)
+// To avoid ambiguity with the `(in, out, pred)` overload, this function has a different name.
+template <class Func, std::ranges::range Input, class Pred>
+void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input>& mid, Pred& pred) {
+  func(in.begin(), mid, in.end(), pred);
+  func(in, mid, pred);
+}
+
+// (in1, in2, out, pred)
+template <class Func, std::ranges::range Input, std::weakly_incrementable Output, class Pred>
+void test(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, out1, out2, pred)
+template <class Func, std::ranges::range Input, std::weakly_incrementable Output, class Pred>
+void test(Func&& func, Input& in, Output& out1, Output& out2, Pred& pred) {
+  func(in.begin(), in.end(), out1, out2, pred);
+  func(in, out1, out2, pred);
+}
+
+// (in, val, pred)
+template <class Func, std::ranges::range Input, class T, class Pred>
+void test(Func&& func, Input& in, T& value, Pred& pred) {
+  func(in.begin(), in.end(), value, pred);
+  func(in, value, pred);
+}
+
+void test_all() {
+  // TODO(ranges): uncomment test cases as range algorithms are implemented.
+
+  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;
+
+  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, 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);
+
+  // 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);
+
+  //test(std::ranges::unique_copy, in, out, unary_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);
+  //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);
+}
+
+int main(int, char**) {
+  test_all();
+
+  return 0;
+}