Page MenuHomePhabricator

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

Authored by philnik on Mar 8 2022, 12:43 PM.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Herald added a project: Restricted Project. · View Herald TranscriptMar 8 2022, 12:43 PM
philnik requested review of this revision.Mar 8 2022, 12:43 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 8 2022, 12:43 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript

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.
Ditto throughout.

(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?)
...Actually, you've already started using auto&& in find_if_not, implying maybe you found a regression test? Please add a similar test for find and find_if.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp
50

Please also test bidirectional_iterator<int*>, int*, and const int*.
Ditto throughout.

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
ldionne requested changes to this revision.Mar 8 2022, 2:11 PM
ldionne added a subscriber: ldionne.
ldionne added inline comments.
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 == ....);
This revision now requires changes to proceed.Mar 8 2022, 2:11 PM
philnik updated this revision to Diff 413961.Mar 8 2022, 3:33 PM
philnik marked 8 inline comments as done.
  • 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.

Quuxplusone added inline comments.Mar 8 2022, 4:03 PM
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.
However, we could do this:

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.
In that case, I'll settle for std::array{1, 2} with no space between the type name and the brace. :)

var-const requested changes to this revision.Mar 8 2022, 10:15 PM
var-const added inline comments.
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):

  • empty range;
  • no element satisfies the predicate;
  • all elements satisfy the predicate (also check that it is the first equivalent element that is returned).
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)

This revision now requires changes to proceed.Mar 8 2022, 10:15 PM

@philnik Thanks a lot for working on this!

philnik updated this revision to Diff 414031.Mar 9 2022, 1:10 AM
philnik marked 10 inline comments as done and an inline comment as not done.
  • 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?

Quuxplusone added inline comments.Mar 9 2022, 8:43 AM
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
https://quuxplusone.github.io/blog/2022/02/02/look-what-they-need/#if-you-see-code-using-std-forwar
(See also Tristan Brindle's response https://tristanbrindle.com/posts/ranges-and-forwarding-references , which is kind of a prequel to that sentence of my post: it explains that Ranges uses constness to signify nothing rather than not-gonna-modify-it-ness, which explains why non-modifying algorithms can't just use const T& and have to use T&& in the first place.)

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...
https://godbolt.org/z/88K1d1PKh
(Notice the non-explicit operator bool here; that's a code smell. So this isn't a real pitfall for users.)
@philnik, I think it would be cute, and perhaps even useful, to add this godbolt as a test case. It does probably somewhat constrain our possible implementation strategies for this overload set.

var-const added inline comments.Mar 9 2022, 11:48 AM
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)

Quuxplusone added inline comments.Mar 9 2022, 3:38 PM
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

+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. :)

philnik updated this revision to Diff 414418.Mar 10 2022, 10:01 AM
philnik marked 5 inline comments as done.
  • Rebased
  • Address comments
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp
34

Thanks, I must have forgotten to copy it.

philnik updated this revision to Diff 414632.Mar 11 2022, 4:02 AM
  • Add version guards
philnik updated this revision to Diff 414680.Mar 11 2022, 9:13 AM
  • Add more SFINAE tests
ldionne accepted this revision as: ldionne.Mar 11 2022, 10:49 AM

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; };
var-const accepted this revision.Mar 11 2022, 2:17 PM

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
41

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.

97

Nit: can you add a closing comment? (// ALMOST_SATISFIES_TYPES_H)

This revision is now accepted and ready to land.Mar 11 2022, 2:17 PM
philnik updated this revision to Diff 414757.Mar 11 2022, 2:44 PM
philnik marked 7 inline comments as done.
  • Rebased
  • Address comments
var-const accepted this revision.Mar 11 2022, 3:06 PM

Thanks for addressing all the feedback! LGTM when the CI is green.

libcxx/test/support/almost_satisfies_types.h
116

Ultranit: s/an/a (here and above).

125

Same note here: I'm not against having this type, but I also think that InputRangeNotSentinelSemiregular is sufficient.

philnik updated this revision to Diff 414762.Mar 11 2022, 3:27 PM
  • Remove lambdas in unevaluated contexts
This revision was automatically updated to reflect the committed changes.
philnik marked an inline comment as done.
tcanens added inline comments.Mar 11 2022, 5:44 PM
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.

(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.
Ditto throughout.

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).

(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?)
...Actually, you've already started using auto&& in find_if_not, implying maybe you found a regression test? Please add a similar test for find and find_if.

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
85

None of these model equality_comparable, so using them with ranges::find is IFNDR.

ldionne added inline comments.Mar 18 2022, 7:51 AM
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.

ldionne added inline comments.Apr 6 2022, 11:22 AM
libcxx/include/__algorithm/ranges_find.h
40

Update: we don't need to change anything, we added tests for this in D122011 and no code changes are necessary.