This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement ranges::count{, _if}
ClosedPublic

Authored by philnik on Mar 12 2022, 7:27 AM.

Details

Diff Detail

Event Timeline

philnik created this revision.Mar 12 2022, 7:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 12 2022, 7:27 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Mar 12 2022, 7:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 12 2022, 7:27 AM
Herald added a reviewer: Restricted Project. · View Herald TranscriptMar 12 2022, 7:27 AM
philnik updated this revision to Diff 414839.Mar 12 2022, 7:43 AM
  • Update documentation

In general looks good, but several minor issues.

libcxx/include/__algorithm/ranges_count.h
39

This differs from the wording invoke(proj, *i) == value for the overloads with a parameter proj but no parameter pred;
Does your code generate the same assembly as the wording in the Standard or does it generate extra overhead?

libcxx/include/algorithm
90

This is already in the namespace ranges and matches the other functions.
(The same for the other new functions.)

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp
35

HasFindIt smells like a copy-paste, please update the name.

85

To avoid duplication this line could be placed in its parent block.

138
libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp
49

Another copy-paste.

69

Why the mutable? I see it used at multiple places.

127

This comment is wrong.

169
philnik updated this revision to Diff 415829.Mar 16 2022, 7:44 AM
philnik marked 6 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_count.h
39

What exactly do you think differs between my implementation and the standard? (https://godbolt.org/z/GvGvT7fxT) At least my ranges::count and std::count produce for this example the exact same assembly at -O1.

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp
85

Arthur asked me to duplicate it in other tests to have the definition near the usage.

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp
69

I think that's a leftover from some iteration of this test.

127

What's wrong with the comment? It checks that 0 is returned when there is no match?

Mordante accepted this revision as: Mordante.Mar 16 2022, 9:41 AM

It looks like the CI failures aren't related to this change. LGTM, modulo one small issue.

libcxx/include/__algorithm/ranges_count.h
39

The indirection using the lambda is the difference. For -O0, the version with the lambda generates a lot more code for this version. Starting at -O1 both versions generate the same output.
But I don't feel too strongly about slightly worse codegen at -O0.

libcxx/include/__algorithm/ranges_count_if.h
28

Sorry I missed this in the previous review, but _LIBCPP_HAS_NO_CONCEPTS is no longer required.

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp
85

For these small tests I would prefer to avoid duplication. However since Arthur asked you to do it this way, let's keep it as-is.

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp
127

Sorry I misread, please ignore my previous remark.

philnik updated this revision to Diff 415888.Mar 16 2022, 10:04 AM
philnik marked 4 inline comments as done.
  • Address comments
ldionne requested changes to this revision.Mar 18 2022, 8:11 AM
ldionne added a subscriber: tcanens.

Looks pretty good, with some comments especially about exhaustiveness in the tests.

libcxx/include/__algorithm/ranges_count.h
39

@tcanens 's comment on ranges::find probably applies here too -- this should be -> bool IIUC (please add test, too).

Also, we should use auto&& __e.

libcxx/include/__algorithm/ranges_count_if.h
33

FWIW, I'm not a huge fan of extremely terse names like this. I'd find _Iterator and _Sentinel clearer. This is non-blocking, but that would be easier to read, and it's not like we gain anything by using fewer characters. This applies throughout the patch.

35
libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp
60–70

Here, you should test with a 0-sized range and 1-sized range too. And for each range size (when that makes sense), you can vary the position of the element you're finding. Right now, you're always finding the last element in the range -- that's not exhaustive enough. You can also check for an element which is not in the range.

Then, you can remove a couple of tests below that are only run on int[], like the one that says // check that 0 is returned with no match.

This comment applies to the other algorithms patches I haven't looked at yet -- we need to be more exhaustive when checking algorithms, especially since it's so easy to do.

This revision now requires changes to proceed.Mar 18 2022, 8:11 AM
philnik updated this revision to Diff 416957.Mar 21 2022, 8:21 AM
philnik marked 2 inline comments as done.
  • Address comments
libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp
60–70

I'm not sure what you are asking for. Do you want that the result changes for every iterator type? Or just have more invocations for each of them?

var-const requested changes to this revision.Mar 23 2022, 3:34 PM
var-const added inline comments.
libcxx/include/__algorithm/ranges_count_if.h
39

Question: in the Standard, there's an explicit cast to bool, but I presume it doesn't matter because the return type is implicitly converted to bool by virtue of being used in an if expression, right?

50

Question: hmm, there are no constraints on iter/range_difference_t (in the Standard), but the implementation has to make certain assumptions about the type. I wonder if it would be a good idea to have a constraint on that as well (unless this constraint comes from somewhere implicitly). What do you think?

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp
45

I think there are a couple more SFINAE cases to test:

  • projected<I, P> is invalid;
  • iter/range_difference_t is invalid.
60

Nit: can you please add a comment to this test case as well, even something as simple as "Normal case" or similar? It just makes skimming through the file easier.

64

Can you add:

  • a test case where ret > 1 to make sure the algorithm counts equivalent elements properly?
  • a test case where all the elements are equal to the given element?
78

Question: why not use a.begin() and a.end()?

90

Nit: s/elment/element/.

121

Consider adding a test to ensure that a non-copyable (perhaps even non-movable) _Type works.

168

Can you also check that the return type is exactly iter/range_difference_t for a type that has some custom-defined difference type?

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp
2

(A few comments from the other test file apply here as well)

66

Hmm, quite a few test cases that are in ranges.count.pass.cpp seem to be missing here?

180

Can you also check that a predicate a) that takes its argument by lvalue; b) that has non-const operator() works?

This revision now requires changes to proceed.Mar 23 2022, 3:34 PM
philnik updated this revision to Diff 418499.Mar 27 2022, 11:45 PM
philnik marked 13 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_count_if.h
39

Yes. ifs can use explicit conversions without the type being explicitly cast to bool. (https://godbolt.org/z/xr8nEb6xG)

50

There are constraints through input_iterator -> input_or_output_iterator -> weakly_incrementable. Specifically __signed_integer_like.

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp
45

{iter, range}_difference_t is never invalid if input_{iterator, range} is valid. With projected i guess you meant indirect_binary_predicate? There I don't think I can do much more than NotEqualityComparable.

78

a.begin() and a.end() aren't portably int*, but they have to be int* for the casts to work.

var-const requested changes to this revision.Apr 1 2022, 10:22 PM
var-const added inline comments.
libcxx/include/__algorithm/ranges_count_if.h
50

Ah, thanks for explaining.

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp
245

Nit: s/auto/decltype(auto)/ (here and below).

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp
152

This should be count_if, not count.

This revision now requires changes to proceed.Apr 1 2022, 10:22 PM
philnik updated this revision to Diff 419956.Apr 2 2022, 1:03 AM
philnik marked an inline comment as done.
  • Address comments
libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp
245

I think we should stick with auto and only use decltype(auto) if we want to check that a reference is returned.

var-const accepted this revision.Apr 4 2022, 12:45 PM
var-const added inline comments.
libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp
245

I think that

std::same_as<Foo> auto x = Bar();

and

static_assert(std::same_as<decltype(Bar()), Foo>);

should be exactly equivalent as far as checking the return type is concerned. If Bar() were to return const Foo&, the second check would catch that but not the first. Yes, it is highly unlikely that count could return a reference; however, I think it's easier to use an approach that is always guaranteed to work rather than deciding on a case-by-case basis.

ldionne accepted this revision.Apr 6 2022, 11:24 AM

LGTM with my and Costa's comments. Thanks!

libcxx/include/__algorithm/ranges_count.h
39

My comment about -> bool can be ignored since this code is correct as-is. However, can we add tests like we did in D122011?

libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_count_if.module.verify.cpp
2

Please rebase onto main with the new way we generate those tests.

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp
60–70

I think you can disregard this comment. I am not sure what I had in mind anymore, but I seem to have written it thinking that we were testing ranges::find, which is obviously not the case. I looked at the tests again and I don't think we are missing relevant coverage.

205–213

We usually say "NonMovable" instead of "Immobile". If you change it, it applies to the other test as well. Non-blocking, but it would be more idiomatic IMO.

This revision is now accepted and ready to land.Apr 6 2022, 11:24 AM
philnik updated this revision to Diff 421154.Apr 7 2022, 4:02 AM
philnik marked 6 inline comments as done.
  • Address comments
This revision was automatically updated to reflect the committed changes.