Details
- Reviewers
• Quuxplusone var-const Mordante ldionne - Group Reviewers
Restricted Project - Commits
- rGee0f8c401030: [libc++][ranges] Implement ranges::find{, _if, _if_not}
Diff Detail
- Repository
- rG LLVM Github Monorepo
Unit Tests
Event Timeline
Thanks, LGTM % comments. That was some quick turnaround time!
libcxx/include/__algorithm/ranges_find.h | ||
---|---|---|
40 | (1) https://eel.is/c++draft/algorithms#alg.find-1.4 says __e == __value, which agrees with my prejudices too (thankfully). I believe this is observable by the user. Consider adding a regression test. (2) What you've got now is attractive, but it "flattens" the type of *__first into const auto&, which might unexpectedly const-qualify and/or lvalue-qualify it, which might(?) affect the resolution of operator==. Can you investigate whether this is OK (due to the requirements of indirect_binary_predicate)? You might need to use auto&& here. (@tcanens, thoughts?) | |
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp | ||
50 | Please also test bidirectional_iterator<int*>, int*, and const int*. | |
62 | IIUC, you meant this one to use the range overload. I wonder if this works, or if it's ambiguous... | |
69 | ||
86 | ||
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if.pass.cpp | ||
35 | This isn't a valid predicate; also I don't understand the point of doing c++ here anyway. Are you just trying to make sure the predicate is called non-const? In that case, you could just [](int x) mutable { return x == 2; } — the mutable makes the type not const-callable. | |
69 | ||
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if_not.pass.cpp | ||
69 |
libcxx/docs/Status/RangesAlgorithms.csv | ||
---|---|---|
5–8 | ||
libcxx/include/__algorithm/ranges_find.h | ||
49 | I don't like that we are reaching into __find_if::__fn here. Instead, we should have something like this in find_if.h: template <class _Ip, class _Sp, class _Pred, class _Proj> _LIBCPP_HIDE_FROM_ABI constexpr _Ip __find_if_impl(_Ip __first, _Sp __last, _Pred& __pred, _Proj& __proj) { for (; __first != __last; ++__first) { if (std::invoke(__pred, std::invoke(__proj, *__first))) break; } return __first; } This provides a slightly (but not much) cleaner interface between the two headers, at least. TBH, I would support implementing this as ranges::find_if(ranges::begin(__r), ranges::end(__r), __pred, std::move(__proj)); (and similarly for the iterator/sentinel version), even though I understand this will lead to additional moves over the current approach. In practice, I don't think this is likely to matter, since iterators should be cheap to copy (and hence to move), and same for projections. So, I have a slight preference for implementation simplicity despite it causing additional moves, but if you want to keep it as-is, please use a namespace scope function at least (and add a libc++ specific test for the no-move behavior). | |
libcxx/include/algorithm | ||
48–71 | This looks weirdly formatted -- please try to indent the return types consistently, etc. | |
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp | ||
55–59 | These projection tests are really clever. Something like this would be easier to read: struct Point { int x; int y; }; Point points[] = {....}; auto ret = std::ranges::find(points, points + 4, 3, [](Point const& p) { return p.x; }); assert(ret == ....); |
- Address comments
libcxx/include/__algorithm/ranges_find.h | ||
---|---|---|
49 | @Quuxplusone wants to add the tests in another PR. | |
libcxx/include/algorithm | ||
48–71 | I'm not sure what you are asking for. The return types are all indented the same, and this is copied 1:1 from the standard (excluding the // since C++20). | |
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp | ||
69 | I get why you want to avoid CTAD in template code, but what's wrong with it here? std::array {1, 2} is definitely easier to read than std::array<int, 2> {1, 2} and there is no chance that it deduces the wrong type. |
libcxx/include/algorithm | ||
---|---|---|
48–71 | philnik's code is consistent with the standard's own weird formatting, which we do use in plenty of synopsis comments: template<class T> constexpr R function_name(Args); But immediately above this new stuff, the older stuff seems to be doing more libc++-code-style formatting: template<class T> constexpr R function_name(Args); and immediately below, the really old stuff seems to be doing yet a third thing: template<class T> constexpr R function_name(Args); I personally don't mind the discrepancy, although it would be nice to make everything consistent one way or another. | |
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp | ||
55–59 | I agree it's hard to read, but part of the point of the projection test is to verify that we're calling the projection specifically on *first, never on a copy of *first. So "this projection returns the address of the argument" is important to the test. assert(std::ranges::find(a, a + 4, 3, [](int& i) { return &i - a; }) == a + 3); to avoid passing a, a + 4, a + 3 in close proximity. | |
69 | Just for simplicity... Ah, but I see, I was forgetting that std::array<int>{1, 2} doesn't work, it needs to be std::array<int, 2>{1, 2}, which is indeed another step uglier. |
libcxx/docs/Status/RangesAlgorithms.csv | ||
---|---|---|
5–7 | Ultranit: please use the emoji checkmark, for consistency and better "visibility". | |
libcxx/include/__algorithm/ranges_find.h | ||
49 | Question: does __r need to be forwarded? | |
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp | ||
30 | Similar to other algorithm patches, I think this needs more SFINAE tests. | |
34 | Consider adding the following test cases (in all 3 files):
| |
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if.pass.cpp | ||
128 | This should be find_if, right? (same in find_if_not.pass.cpp) |
- Rebased
- Address comments
libcxx/include/__algorithm/ranges_find.h | ||
---|---|---|
49 | Definitely not the first one, and I also don't think the second one. We still need our range for the iterators to be valid, so conceptually it doesn't make sense to forward them (and makes probably no practical difference). | |
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp | ||
34 | no elements satisfying the predicate is already checked with // check that std::invoke is used and all elements satisfy the predicate should effectively be checked by // count invocations of the projection, since that checks that there are exactly two projections. Or do you want to check for something more that I'm not seeing? |
libcxx/include/__algorithm/ranges_find.h | ||
---|---|---|
40 | As in find_if_not's lambda, you need to std::forward __e here. (Economist's $100 bill — be consistent!) | |
49 | Right, you never forward ranges. The Ranges idiom is "Take by forwarding reference, pass by lvalue." Because Ranges uses rvalueness to signify short lifetime, rather than pilferability; see | |
libcxx/include/__algorithm/ranges_find_if.h | ||
33–41 | (1) @ldionne, I disagree that this should be a standalone free function. Reaching into ranges::__foobar::__fn::__go doesn't strike me as any more confusing than reaching into ranges::__foobar_impl; all it does is add yet another layer of indirection for the gamedevs to complain about. It also implies code churn: as we implement new algorithms in terms of older ones, you're asking us to go back and pull out the old algorithm's guts from the existing __fn::__go into __foobar_impl. (I don't think you're asking for the pulling-out to be done preemptively on every algorithm, are you? It would be ad-hoc?) In short, I fairly strongly recommend putting this back the way it was; but I think @ldionne has the final say, so my job is to convince him. :) (2) If this is kept: please add a blank line after namespace ranges { for readability. (3) In fact, I would even recommend closing and reopening the namespace. My mental model is that we have this one helper in namespace ranges, and then further down in the file we have the essentially unrelated stuff in namespace ranges::__find_if. "Zeroing" in between is good practice IMHO: it makes it easier to see at a glance what namespace we're inside, because you don't have to keep a mental stack of the entire file but only back as far as the last "zero" point. | |
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp | ||
62 | For the record, ranges::find(a, a+3, proj) is not ambiguous, because proj is not equality-comparable-with int. But if you make it equality-comparable... |
libcxx/include/__algorithm/ranges_find.h | ||
---|---|---|
49 | Thanks a lot for the explanation and the links. | |
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp | ||
34 | I think each test case should have a single focus -- it makes it easier to read and better protects against future changes. If someone were to remove a test case that says // No element satisfies the predicate, it should be pretty obvious that test coverage is reduced. On the other hand, if someone were to modify // check that std::invoke is used so that it no longer covers the "no match" case, it's not immediately clear that this case may no longer be checked at all (and reading through every single test case to see if it's covered elsewhere is impractical). | |
34 | (The new tests apply to all 3 algorithms. AFAICT, the new empty range test still needs to be added to find_if.pass.cpp and find_if_not.pass.cpp) |
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp | ||
---|---|---|
34 |
+1. Of course one way around this would be to tag the single test case with both comments. But writing one-for-one test cases produces the side benefit of "more test coverage." E.g. maybe the std::invoke test case should take two lines and test both the "found" and "not found" codepaths; and maybe the not-found test case should also assert that in that situation the predicate is called exactly N times. (Or maybe that's just reintroducing the exact issue var-const objected to. That's fair. :)) Anyway, +1 to "one focus, one comment, one test case" from me. :) |
- Rebased
- Address comments
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp | ||
---|---|---|
34 | Thanks, I must have forgotten to copy it. |
LGTM -- I stand by my comment of using find_if_impl instead of a helper function inside the struct. It's a minor difference but IMO it's important.
Leaving last approval to @var-const, who had requested changes.
libcxx/include/__algorithm/ranges_find.h | ||
---|---|---|
49 | If you want, you should also be able to write auto __pred = [&]<class _Ep>(_Ep&& __e) { return std::forward<_Ep>(__e) == __value; }; |
LGTM (except the sentinel_for check -- sorry, I know it's tedious to add all those checks).
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if_not.pass.cpp | ||
---|---|---|
15 | I think the sentinel_for constraint is still untested (if I'm not seeing it, please let me know). Sorry, I know it's annoying. Just a single pair of types where I satisfies input_iterator but not sentinel_for<I, S> is sufficient. | |
libcxx/test/support/almost_satisfies_types.h | ||
40 ↗ | (On Diff #414680) | Note: I think this type is sufficient for checking the input_iterator requirement -- i.e., a type that is an input_or_output_iterator but not input_iterator is perfect, but whether it satisfies indirectly_readable starts going into the "testing input_iterator" territory. So I'm not against also having InputIteratorNotIndirectlyReadable and InputIteratorNotInputOrOutputIterator, but IMO just InputIteratorNotDerivedFrom is sufficient. |
96 ↗ | (On Diff #414680) | Nit: can you add a closing comment? (// ALMOST_SATISFIES_TYPES_H) |
Thanks for addressing all the feedback! LGTM when the CI is green.
libcxx/test/support/almost_satisfies_types.h | ||
---|---|---|
115 ↗ | (On Diff #414757) | Ultranit: s/an/a (here and above). |
124 ↗ | (On Diff #414757) | Same note here: I'm not against having this type, but I also think that InputRangeNotSentinelSemiregular is sufficient. |
libcxx/include/__algorithm/ranges_find.h | ||
---|---|---|
40 | The only requirement on the result of == is that it is boolean-testable, so these lambdas need to explicitly return bool - boolean-testable only guarantees that the exact expression can be used boolean-ish-ly in situ.
Since ranges::equal_to requires equality_comparable_with, this is not observable (we don't say that it compares this way; we say that it returns something for which the comparison yields true if compared that way).
equality_comparable_with requires implicit expression variations, so turning into const& should be fine. | |
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp | ||
86 | None of these model equality_comparable, so using them with ranges::find is IFNDR. |
libcxx/include/__algorithm/ranges_find.h | ||
---|---|---|
40 | @philnik We need to address the -> bool in the lambda. You should add a test: operator== returns something that can be converted to bool, but that can't be moved or copied. With the current implementation, it should fail cause you're returning it from the lambda. If you switch to -> bool, there would be an implicit conversion to bool and it should work. |
Ultranit: please use the emoji checkmark, for consistency and better "visibility".