This is an archive of the discontinued LLVM Phabricator instance.

[libcxx] patch for implementing ranges::find_last
Needs RevisionPublic

Authored by phyBrackets on Oct 21 2022, 9:18 PM.

Details

Reviewers
philnik
ldionne
huixie90
bollu
var-const
Group Reviewers
Restricted Project
Summary

Diff Detail

Event Timeline

phyBrackets created this revision.Oct 21 2022, 9:18 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 21 2022, 9:18 PM
phyBrackets requested review of this revision.Oct 21 2022, 9:18 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 21 2022, 9:18 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
huixie90 requested changes to this revision.Oct 22 2022, 12:08 PM
huixie90 added a subscriber: huixie90.
huixie90 added inline comments.
libcxx/include/__algorithm/ranges_find_last.h
1

Please add tests for all the algorithms' behaviour and constraints.
You can take a look at this to get an idea about how we test algorithms
https://reviews.llvm.org/D130404

29

is the paper C++23? If so, should it be

#if _LIBCPP_STD_VER >= 23

same applies to other files in the patch

39

question. can we use static operator() now?

libcxx/include/__algorithm/ranges_find_last_if.h
36

There are several issues.

  1. In general __last is a sentinel (as supposed to be an iterator). The only thing you can do about it is to compare with an iterator. so you cannot use operator-- for a sentinel.
  2. The algorithm's requirement is forward_iterator (instead of bidirectional_iterator). operator-- does not exist for forward_iteartor. You will probably need to dispatch to different implementations depending on whether it is common_range, bidirectional_range, sized_sentinel_for/sized_range
This revision now requires changes to proceed.Oct 22 2022, 12:08 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 8 2023, 9:31 PM
fsb4000 added a subscriber: fsb4000.Mar 9 2023, 1:18 AM
fsb4000 added inline comments.
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last_if_not.pass.cpp
216 ↗(On Diff #503617)

Should be static_assert?

fsb4000 added inline comments.Mar 9 2023, 1:19 AM
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last_if.pass.cpp
230 ↗(On Diff #503617)

static_assert

fsb4000 added inline comments.Mar 9 2023, 1:19 AM
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last.pass.cpp
245 ↗(On Diff #503617)

static_assert

fsb4000 added inline comments.Mar 9 2023, 1:21 AM
libcxx/docs/Status/Cxx2bPapers.csv
58 ↗(On Diff #503617)

instead of

"","|ranges|"

should be

"17.0","|ranges|"

phyBrackets marked 4 inline comments as done.

Thanks for your patch. I only want over it lightly. I will do an full review after the current open issues are addressed.

libcxx/include/__algorithm/ranges_find_last.h
29

@phyBrackets can you mark items as done when they are done? That makes reviewing these changes a lot easier.

39

Why would that not be possible, I've seen this used in other ranges patches too.

56

Please run clang-format on new files, I'm quite sure this indention is off.

libcxx/include/__algorithm/ranges_find_last_if.h
39

Please don't use auto everywhere, this just makes things harder to read.
Please make sure all names are __uglified, for example result too,

libcxx/include/__algorithm/ranges_find_last_if_not.h
43

naming is hard, but let's try to use something better than just a number.
How about __not_pred since this is basically the inverse of the predicate given.

Another option is just not giving this predicate a name and write it in the return statement on the next line.

libcxx/include/algorithm
129

This indention is off.

131

Please align all these since entries.

libcxx/include/module.modulemap.in
365 ↗(On Diff #506629)

Please fix the alignment of the {.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last.pass.cpp
81 ↗(On Diff #506629)

Here you should use std::same_as<return type> auto method. For example have a look at
libcxx/test/std/ranges/range.adaptors/range.common.view/begin.pass.cpp

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last_if.pass.cpp
105 ↗(On Diff #506629)

Please use clang-format on these tests, this looks wrong.

libcxx/utils/data/ignore_format.txt
119 ↗(On Diff #506629)

The ignore list is there since we don't want to reformat our entire code base and have merge conflicts for existing patches. New files should always be formatted.

llvm/utils/gn/secondary/libcxx/include/BUILD.gn
170 ↗(On Diff #506629)

Typically we don't update the bazel files, there is a post-commit bot that does that.

phyBrackets marked 2 inline comments as done.
phyBrackets marked 8 inline comments as done.
phyBrackets marked an inline comment as done.
var-const requested changes to this revision.Jun 2 2023, 7:12 PM
var-const added a subscriber: var-const.

So sorry it took me so long to get to this review!

libcxx/include/__algorithm/ranges_find_last.h
16

Is this used?

17

Is this used?

38–39

This formatting looks really weird, is it produced by clang-format? (If so, feel free to disable it for these lines by adding a // clang-format off comment, then reenable with // clang-format on)

39

Can you also add _LIBCPP_NODISCARD_EXT to all the new algorithms? We want to mark these as [[nodiscard]] since they have no side effects and are only used to produce a value, but since they aren't marked as such in the Standard, we have to do it as an extension. Please also update the test/libcxx/diagnostics/ranges.nodiscard_extensions.verify.cpp test file.

41

Question: what's the case where forward would make a difference? Do we have a test for that?

62

>= 23.

libcxx/include/__algorithm/ranges_find_last_if.h
39

Normally we simply increment __first, no need to create a separate variable.

39–47

Recreating the whole __result each time seems a little wasteful, consider:

_Ip __result = __last;
while (__first != __last) {
  if (std::invoke(__pred, std::invoke(__proj, * __first))) {
    __result = __first;
  }
  ++__first;
}
return {__result, __last};
45

For a bidirectional common range, it seems more efficient to iterate from the end -- then you can return as soon as you find an element satisfying the predicate. For a bidirectional non-common range, it might still be more efficient to create an iterator from the sentinel and go from the end (though this is debatable).

55

Missing _LIBCPP_HIDE_FROM_ABI.

58

Please add a newline after this line.

63

Missing _LIBCPP_HIDE_FROM_ABI.

77

>= 23.

libcxx/include/__algorithm/ranges_find_last_if_not.h
16

iterator_operations.h might be unnecessary.

43

Do we have a test that fails if we remove this forward?

43

Very optional: __negate_pred or __negated_pred?

52

To avoid duplicating this logic, consider instead delegating to the iterator version of find_last_if_not.

65

>= 23

libcxx/include/algorithm
129

Nit: please fix indentation here.

131

Nit: can these comments (// since C++23) be aligned?

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last.pass.cpp
81 ↗(On Diff #506629)

Looks not done?

145 ↗(On Diff #516117)

This test should also apply to the iterator version of the algorithm, right? (applies to the other two test files as well)

164 ↗(On Diff #516117)

Wrong indentation.

175 ↗(On Diff #516117)

Do the other two files need an equivalent test?

215 ↗(On Diff #516117)

Does this have to be constexpr?

230 ↗(On Diff #516117)

The other files use BooleanComparable, can this be made consistent?

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last_if.pass.cpp
9 ↗(On Diff #516117)

Note: most comments in this file apply to the other two test files as well.

35 ↗(On Diff #516117)

s/HasFindIfIt/HasFindLastIfIt/, same for the range version below.

53 ↗(On Diff #516117)

Please also add a case where HasFindLastIfPred is true (to test the test, so to speak).

71 ↗(On Diff #516117)

Can we add a few more test cases?

  • empty range;
  • 1-element range;
  • no element satisfies the predicate;
  • all elements satisfy the predicate;
  • the element being searched is the first one;
  • the element being searched is the last one.
73 ↗(On Diff #516117)

This formatting is incorrect, continuations should be indented.

73 ↗(On Diff #516117)

Why is it mutable?

78 ↗(On Diff #516117)

Please reuse the input between the iterator version and the range version, it cuts down boilerplate and makes it easier to verify that the two test cases are equivalent.

87 ↗(On Diff #516117)

It's better if the tests for these very similar algorithms are as uniform as possible. The find_last_if_not test file calls this helper NonConstComparableLvalue while the find_last test file has both NonConstComparableLValue and NonConstComparableRValue . Can this be consistent?

88 ↗(On Diff #516117)

Are all 4 overloads necessary? If so, please add a short comment to explain why.

95 ↗(On Diff #516117)

Consider using types::for_each to cut down on the boilerplate a little.

97 ↗(On Diff #516117)

Can these types be ordered from most to least restrictive? (or vice versa)

102 ↗(On Diff #516117)

Can you rephrase the called with the iterator directly bit? It reads as if the projection receives an iterator as an argument, which isn't the case. I think something like called with the reference to the element the iterator is pointing to would be more technically correct (though this can definitely be improved).

106 ↗(On Diff #516117)

Please make the projection a named variable and reuse it between the iterator version and the range version.

107–108 ↗(On Diff #516117)

Optional: consider adding blank lines between scopes (throughout). I find code easier to read when it's split into logical blocks, and different scopes offer a very straightforward point for splitting.

121 ↗(On Diff #516117)

How about s/other/index/?

130 ↗(On Diff #516117)

(throughout) You can reuse these helper types between the iterator version and the range version to reduce boilerplate.

143 ↗(On Diff #516117)

Nit: s/end + 1/past-the-end/.

143 ↗(On Diff #516117)

I would move this test to test_iterators.

158 ↗(On Diff #516117)

Nit: I'd use decltype(auto). In this case the difference isn't really relevant, but IMO it's better to just always use decltype(auto) which catches the exact return type and never have to think about it.

182 ↗(On Diff #516117)

Please see if the types from test/support/counting_{projection,predicates}.h can be used here.

208 ↗(On Diff #516117)

Can you please elaborate a little on this comment? I'm not sure how it relates to the test (which seems to check whether a predicate that takes arguments by a non-const reference works with the algorithm).

221 ↗(On Diff #516117)

Please move this test case to test_iterators.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_last_if_not.pass.cpp
73 ↗(On Diff #516117)

Can we use a simpler predicate? These tests should check the most basic logic and be as easy to read as possible.

118 ↗(On Diff #516117)

Last element?

254 ↗(On Diff #516117)

Please also update test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp and the *robust* test files where applicable (searching for ranges::find_if among the *robust* test files should give a good idea of which ones to update).

This revision now requires changes to proceed.Jun 2 2023, 7:12 PM

@phyBrackets Do you have any plans to keep working on this?

Probably yes , I was just a bit busy with gsoc project and nowdays i am a bit sick! I will get over this patch as soon as possible.