This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Implement ranges::equal
ClosedPublic

Authored by philnik on Apr 13 2022, 6:54 AM.

Details

Reviewers
ldionne
Mordante
var-const
Group Reviewers
Restricted Project
Commits
rG569d6630204d: [libc++] Implement ranges::equal

Diff Detail

Event Timeline

philnik created this revision.Apr 13 2022, 6:54 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 13 2022, 6:54 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Apr 13 2022, 6:54 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 13 2022, 6:54 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript

In general looks good, but some minor issues.

libcxx/include/__algorithm/ranges_equal.h
94

Interesting that the standard uses distance instead of size.

libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp
90

Please add tests with the same size, but different values.

107

Here too I like to see a test which returns false for a search.

197

This misses the tests when the input isn't a size_sentinel_for or a sized_range.

Mordante added inline comments.Apr 23 2022, 10:06 AM
libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp
2

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp should also be updated.

philnik updated this revision to Diff 424785.Apr 24 2022, 8:32 AM
philnik marked 4 inline comments as done.
  • Address comments
libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp
197

I don't think there is anything interesting about them. IIUC in theory an implementation could still not call the projections or predicates if it magically knows that it's iterating over two arrays of different sizes.

Mordante added inline comments.Apr 26 2022, 8:30 AM
libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp
197

I think the interesting part is that we now have an untested code path. Not that I expect errors, but it would be good to add a test.

var-const requested changes to this revision.Apr 27 2022, 7:37 PM
var-const added inline comments.
libcxx/include/__algorithm/ranges_equal.h
94

Same question -- what's the reason to use size as opposed to distance (which would be closer to the Standard)?

libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp
76

Optional: a helper function would allow making the call sites quite a bit shorter:

assert(test({1, 2, 3, 4}, {1, 2, 3, 4});
assert(test({1, 2, 3, 4}, {2, 3, 4, 5}, [](int l, int r) { return l != r; });
...
// Comments can help distinguish parameters:
assert(test(/*a=*/ {1, 2, 3, 4}, /*b=*/ {2, 3, 4, 5}, /*pred=*/ [](int l, int r) { return l != r; });
186

Please also test when a) both ranges are empty and b) only one of the ranges is empty.

257

Nit: please add a blank line after this line.

This revision now requires changes to proceed.Apr 27 2022, 7:37 PM
philnik updated this revision to Diff 426001.Apr 29 2022, 2:31 AM
philnik marked 5 inline comments as done.
  • Address comments

@philnik I see you've addressed a few comments but not sure if this is ready for another round of review. Please ping me (here or on Discord if you prefer) when you'd like me to take another look. Thanks!

philnik updated this revision to Diff 427595.May 6 2022, 4:00 AM
  • Try to fix CI

@var-const This should be ready for another round.

philnik added inline comments.May 24 2022, 4:00 AM
libcxx/include/__algorithm/ranges_equal.h
94

ranges::distance just forwards to ranges::size if it's a sized_range, so I don't see any reason for the additional indirection. If you'd rather have it spelled ranges::distance I can change it though.

var-const accepted this revision.May 24 2022, 1:23 PM

LGTM. There's just one blocking comment that should be a very straightforward fix and one completely optional suggestion, so I don't think this needs another round of review (unless something unexpected happens, of course). Thanks!

libcxx/include/__algorithm/ranges_equal.h
94

I'd prefer to use ranges::distance just to be a little more consistent with the standard. That way, somebody reading the code could trivially verify that this part is correct, without looking up or recalling the details of how distance and size are defined. I don't think the extra indirection would cause any noticeable issues.

libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp
76

Note: it's totally fine to ignore an optional suggestion, but in that case, please write a short comment to make it clear that you deliberately decided to not implement or postpone it. It would just make it more obvious to me whether you decided to not go with the suggestion or simply didn't get to this comment yet. Thanks!

This revision is now accepted and ready to land.May 24 2022, 1:23 PM
philnik updated this revision to Diff 431903.May 25 2022, 1:17 AM
philnik marked an inline comment as done.
  • Address comments
philnik added inline comments.May 25 2022, 1:28 AM
libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp
76

I've done that in a few of the newly written code and I think it's nice. I might refactor the already-written tests later.

philnik updated this revision to Diff 431914.May 25 2022, 2:10 AM
  • Fix the modules build
This revision was automatically updated to reflect the committed changes.