Page MenuHomePhabricator

[libc++][ranges] Implement ranges::min_element
ClosedPublic

Authored by philnik on Jan 11 2022, 7:40 AM.

Details

Summary

Implement ranges::min_element

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
miscco added a subscriber: miscco.Jan 11 2022, 8:05 AM
miscco added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min_element.pass.cpp
120

Is there a reason the tests are disabled?

philnik marked an inline comment as done.Jan 11 2022, 11:52 PM
philnik added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min_element.pass.cpp
120

Just forgot to re-enable it. Thanks for noting.

philnik updated this revision to Diff 399227.Jan 11 2022, 11:52 PM
philnik marked an inline comment as done.
  • Guard with HAS_NO_RANGES and enable constepxr test
philnik updated this revision to Diff 400295.Jan 15 2022, 9:01 AM
  • Rebased
  • Fix CI
Quuxplusone requested changes to this revision.Jan 16 2022, 11:44 AM
Quuxplusone added inline comments.
libcxx/include/__algorithm/ranges_min_element.h
50

This makes copies of __comp and __proj. At the very least we should std::move them; but I think we should also give serious consideration to just taking them by forwarding reference to begin with.

Speaking of how scary it is to mess with overload sets... what's the mandated behavior for a call like std::ranges::min_element(42) — does it need to SFINAE away quietly? If so, we should have a test for that.

libcxx/include/algorithm
29

Nit: lowercase since C++20 to match line 23 (and generally)

libcxx/include/module.modulemap
288

Typo here. I'll update lint_modulemap.sh.py. :)

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min_element.pass.cpp
31

I see zero reason for this test to use randomness. We just need to check that it works when the first element is the min; when the last element is the min; when some middle element is the min; when there's a tie for min; when the range's size is 1; when the range's size is 0; when the range's value type is immobile (i.e. we shouldn't ever be copying/moving elements).
And then check for SFINAE when the thing isn't a range; when the range's value type isn't <-comparable; when it is <-comparable but not totally_ordered.
I would also expect to see the word std::ranges::dangling used at least once in this test file.

This revision now requires changes to proceed.Jan 16 2022, 11:44 AM
philnik updated this revision to Diff 400651.Jan 17 2022, 2:50 PM
philnik marked 4 inline comments as done.
  • Address comments
philnik updated this revision to Diff 400663.Jan 17 2022, 4:05 PM
  • Add forward include
philnik updated this revision to Diff 400670.Jan 17 2022, 4:30 PM
  • Fix forward
philnik updated this revision to Diff 404268.Jan 29 2022, 7:47 AM
  • Rebased
  • Put implementation into other function
  • Move Immobile declaration out of function
Quuxplusone requested changes to this revision.Jan 29 2022, 11:48 AM

The code looks great at this point! Significant comments on the test.

libcxx/include/__algorithm/ranges_min_element.h
35

Remove blank line.

44

bool(...) is unnecessary here, because the invoke_result_t of a predicate is guaranteed to be boolean-testable. If someone thinks the cast looks nice for some reason, I won't complain too much; but IMHO you should eliminate the cast as unnecessary.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min_element.pass.cpp
33–34

Please either name this concept HasMinElement, or just use
static_assert(!std::is_invocable_v<decltype(std::ranges::min_element), int&>);
etc. without defining a named concept at all. I have a slight preference for the latter.
(Also, surely T i should be T t or perhaps R& r. Notice that you only ever pass lvalues here; that's one reason it would be clearer to use is_invocable_v instead of the named concept.)

71

Moot style point: Stylistically I prefer (x , ...) over (x, ...) for the same reason I prefer (x + ...) over (x+ ...).
However, this strikes me as vastly too "clever". I think the ultimate reason for this is line 131, which should just be 4 lines. My same comments from the mismatch review apply here: let's keep these tests as simple as possible, so we can tell what's going wrong when one fails without a lot of metaprogramming-debugging; and also so that we can be sure our tests are actually testing what we intend, and not being nerfed by some accidental bug in the metaprogramming.

95–101

See, this is a great test, because it's simple enough that I think I see what it's doing. ;)
Nits: indentation on line 95; prefer () over {} on line 97. But FWIW, I'd just write

{
  int a[] = {2, 3, 1, 3, 2};
  int *ret = std::ranges::min_element(a, std::greater());
  assert(ret == a + 1);
}
{
  const int a[] = {2, 3, 1, 3, 2};
  const int *ret = std::ranges::min_element(a, std::less());
  assert(ret == a + 2);
}

or something like that. I don't think we need sentinel_wrapper or subrange (or std::ranges::greater) if the goal is to test the comparator codepath specifically.

107

Nice example of a call where the answer would be different if the predicate weren't there!
I'd like to see one additional test where the projected type is not the same type as the range's value_type, e.g.

int a[] = {2, 1, 3};
int *ret = std::ranges::min_element(a, std::less<int*>(), [](int& i) { return &i; });
assert(ret == a);
128

Moot: , 0 is kind of a weird corner case; I'd make this , 10 or , 42.
But also, we need to test this behavior outside an unevaluated expression. I suggest

constexpr void test_dangling()
{
  int a[] = {2, 1, 3};
  int compares = 0;
  int projections = 0;
  auto comparator = [&](int a, int b) { compares += 1; return a < b; };
  auto projection = [&](int a) { projections += 1; return a; };
  std::same_as<std::ranges::dangling> auto r =
    std::ranges::min_element(r, comparator, projection);
  assert(compares == 2);
  assert(projections == 4);
}
This revision now requires changes to proceed.Jan 29 2022, 11:48 AM
philnik updated this revision to Diff 405930.Feb 4 2022, 5:16 AM
philnik marked 5 inline comments as done.
  • Address comments
philnik marked an inline comment as done.Feb 4 2022, 5:16 AM
philnik added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min_element.pass.cpp
71

The reason was that I didn't want to run test_range multiple times, and having a single fold expression doesn't strike me as very much meta-programming.
I prefer (x, ...) for the same reason I write fun(a, b) and not fun(a , b).

95–101

Why do you want to test std::less? It's tested literally every where else.

Quuxplusone requested changes to this revision.Feb 4 2022, 9:16 AM

Let's fix that variadic test function. It's cheap and easy to fix.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min_element.pass.cpp
71

I prefer (x, ...) for the same reason I write fun(a, b) and not fun(a , b).

I would have said the same thing! ;) I write fun(a, b) and {1, 2} and so on because each of those commas represents the comma separator. But when I use the comma operator, at least in a fold-expression context where the reader might casually mistake it for the comma separator, I'll call out that unusual usage by formatting it like an operator.

75
95–101

Well, in general TDD terms, testing two different comparators "proves" that the implementation isn't just "if there's a comparator object then reverse all the comparisons" or something. But I don't mind just testing std::greater.
(I'd still prefer std::greater() over std::ranges::greater{}, purely for style: it's shorter and causes fewer dependencies. But whatever.)
No further action required here.

107

Here please use std::less<int*>() with the specific type int*, because I want to verify that the comparator doesn't need to be callable with the original element type — we want it to be callable (and called) only with the projected type.

128

You can remove line 128 (the static_assert) now, which will allow you to remove #include <array> (and eliminate the weirdness of std::array<T, 0>).

150–153
This revision now requires changes to proceed.Feb 4 2022, 9:16 AM
philnik marked 7 inline comments as done.
philnik added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min_element.pass.cpp
128

I'm still using std::array in line 140.

philnik updated this revision to Diff 406088.Feb 4 2022, 1:04 PM
philnik marked an inline comment as done.
  • Address comments
Quuxplusone added inline comments.Feb 4 2022, 1:28 PM
libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min_element.pass.cpp
72

I would like to see us test some ranges that are not std::array. Given the implementation, I guess it's not likely that anything could go wrong; but still, you could get vastly more mileage out of this test by making it something like

template<class It>
constexpr void test_one_case(std::initializer_list<int> a, int expected_idx) {
  int *first = a.begin();
  int *last = a.end();
  {
    std::same_as<It> auto it = std::ranges::min_element(It(first), It(last));
    assert(base(it) == first + expected_idx);
  }
  {
    using Sent = std::sentinel_wrapper<It>;
    std::same_as<It> auto it = std::ranges::min_element(It(first), Sent(It(last)));
    assert(base(it) == first + expected_idx);
  }
  {
    auto r = std::ranges::subrange(It(first), It(last));
    std::same_as<It> auto it = std::ranges::min_element(r);
    assert(base(it) == first + expected_idx);
  }
  {
    using Sent = std::sentinel_wrapper<It>;
    auto r = std::ranges::subrange(It(first), Sent(It(last)));
    std::same_as<It> auto it = std::ranges::min_element(r);
    assert(base(it) == first + expected_idx);
  }
}

template<class It>
constexpr void test_cases()
  test_one_case<It>({}, 0);
  test_one_case<It>({1}, 0);
  test_one_case<It>({1, 2, 1}, 0);
  test_one_case<It>({2, 1, 3}, 1);
  test_one_case<It>({3, 2, 1}, 2);
}

~~~
  test_cases<forward_iterator<int*>>();
  test_cases<bidirectional_iterator<int*>>();
  [etc.]
75

Throughout: s/Iters/Iter/ (or even It).
Lines 76-81: Is the first template parameter always just the length of the initializer-list?

philnik updated this revision to Diff 406107.Feb 4 2022, 2:28 PM
philnik marked 2 inline comments as done.
  • Address comments
Mordante accepted this revision as: Mordante.Feb 10 2022, 9:11 AM

LGTM modulo one suggestion.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min_element.pass.cpp
108

For reviewing it would be nice to also validate the value assert(*ret == x); in all these tests.

philnik updated this revision to Diff 407578.Feb 10 2022, 9:33 AM
philnik marked an inline comment as done.

Thanks for the review @Mordante!

  • Address comment
Quuxplusone accepted this revision.Feb 10 2022, 10:59 AM

LGTM assuming all comments have been addressed. Please make sure that you transfer all relevant improvements over to D117523, and vice versa if there are any comments on D117523 over to here.

This revision is now accepted and ready to land.Feb 10 2022, 10:59 AM
philnik updated this revision to Diff 407705.Feb 10 2022, 3:28 PM
  • Rebased
  • Fix CI
philnik updated this revision to Diff 407837.Feb 11 2022, 4:12 AM
  • Use _LIBCPP_HAS_NO_CONCEPTS
This revision was landed with ongoing or failed builds.Feb 11 2022, 8:20 AM
This revision was automatically updated to reflect the committed changes.