[libcxx][algorithms] adds `std::ranges::find`

[cjdb]

Summary

Implements part of http://wg21.link/P0896.
Implements part of [alg.find].

[zoecarver]

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/ranges_find.pass.cpp

30 ↗

(On Diff #357846)

I would like us to find some consistency with this. As I said before, I don't really care what we actually do. But I'd like to know what I should do and what you should do so we can stop spending time thinking about it. If this patch lands, we'll do three different things for apparently no reason across our test suite.

44 ↗

(On Diff #357846)

Nit: you could probably pull this out of these braces and into the middle ones.

[cjdb]

In D105456#2871478, @zoecarver wrote:

Just a note on the two comments above. I understand how they might come across as pedantic, or too picky, but I think it's important that we get this right. If we develop a good model here, it will mean we have a good model for the dozens of algorithms to come. That's why I think this patch should have a high bar (which is not to say that I wouldn't have made those two comments on any other patch).

Somehow phab got stuck on the old patch so I didn't see the new changes. Sorry for both adding churn and making comments about things that are now resolved.

This LGTM now, but I want to check out your other algorithms patches so I can see how you're testing things over there. I don't have time to do that right now but I figured I'd get this comment in ASAP so you see that I don't actually have a problem with these tests anymore :)

Thanks again for working on this!

It's a bit confusing, but the only other one that you need to check out is D105795 (all the rest are the same as this patch). Please report your feedback to D105791, since that's where the idea for test_algorithm is proposed.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/ranges_find.pass.cpp

30 ↗

(On Diff #357846)

I've defaulted to my original alias because stdr is too easily mistyped or misread as std. I can go and clean the rest up in an NFC.

44 ↗

(On Diff #357846)

Negative: input ranges mean we need to recreate the range each time.

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI (round 2)

[cjdb]

• enables static_asserts that were commented out
• removes GCC 11 from the test suite (due to https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92505)

[cjdb]

rebases to activate CI

[ldionne]

I'll say it upfront, I dislike that we're adding these nodiscard extensions. But we've done it for the non-ranges algorithms, so it's going to be difficult to vouch for not adding the ranges ones.

IMO we should either make them nodiscard unconditionally, or not at all. Adding a knob that very few people will use is not a great bang-for-the-buck.

libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp

10 ↗

(On Diff #359367)

as an

Also, the comment is the same as the one in nodiscard_ranges_extensions.verify.cpp, but they are testing opposite things. This one could say something like:

// Test that entities in <ranges> are not declared [[nodiscard]] as a libc++ extension
// if the user doesn't request it explicitly.

33 ↗

(On Diff #359367)

You can make this test .verify.pass.cpp, and then use // expected-no-diagnostics to make the intent clearer.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/ranges_find.pass.cpp

8 ↗

(On Diff #359367)

Throughout these tests, we never call ranges::find with another type than a complexity_iterator. Sure, we pass it a complexity_iterator wrapping various iterator archetypes, but the actual type passed to ranges::find is still always the complexity_iterator. We need to pass the actual archetypes too in order to really check that ranges::find works with those.

15 ↗

(On Diff #359367)

Can you spell out the prototype(s) you're testing, and make it one per file?

130 ↗

(On Diff #359367)

Can you spell out these types explicitly?

[ldionne]

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/special_function.compile.pass.cpp

31

Is there any way you can avoid doing this?

[cjdb]

In D105456#2884414, @ldionne wrote:

I'll say it upfront, I dislike that we're adding these nodiscard extensions. But we've done it for the non-ranges algorithms, so it's going to be difficult to vouch for not adding the ranges ones.

IMO we should either make them nodiscard unconditionally, or not at all. Adding a knob that very few people will use is not a great bang-for-the-buck.

I think my position is loud and clear on this one ([[nodiscard]], no knob), but I think it warrants its own patch.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/special_function.compile.pass.cpp

31

I need a standard range adaptor that's guaranteed to not be a common_range upon inspection. Till we get iota_view or basic_istream_view (the simplest two), I think not.

[cjdb]

reworks testing

@ldionne ready for another round of reviewing :)

[cjdb]

removes dependency on abandoned patch

[zoecarver]

This is a separate patch, but it would be good to track what algorithms need to be implemented and who's doing that.

Overall this looks good to me. I have a few comments below, though.

libcxx/include/__algorithm/find.h

52

Should we have a test for this requires clause? (Or maybe we do and I missed it.)

54

_LIBCPP_HIDE_FROM_ABI and anything else from https://libcxx.llvm.org/Contributing.html#pre-commit-check-list

73

Can you add a test for something like this:

namespace std { namespace ranges {

struct dummy {
  friend void find() { }
};

}}

Or at least fix the problem that it will uncover.

libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.pass.cpp

1

Do we need to update the docs about this?

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/find_iter_sent_proj.pass.cpp

41

Hmm, this isn't a big thing, but it might be nice to have something like ASSERT_SAME_TYPE(decltype(find), int*) where the second argument is a concrete iterator type.

At least add an ASSERT_SAME_TYPE , please.

45

(Sorry to be a bit pedantic here, but...)

I think it would be simpler to just have an auto here and then assert the type below.

The reason I think this is then two different lines are testing two different things. One line has the test for what type the return type should have, the other line has the test for what value the return type should have. I think it makes it a bit easier to parse quickly, and if there was an error, it would be clearer what the error was.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/special_function.compile.pass.cpp

31

Hopefully you'll have it in a few days: https://reviews.llvm.org/D107096

:)

libcxx/test/support/complexity_invocable.h

49 ↗

(On Diff #363205)

Nit this could be an unsigned type. AFAIU it's never less than zero.

libcxx/test/support/test_range.h

65

This should probably go in test_ranges.h

67

Can we make this a move-only type? Currently I don't see any tests for move only ranges.

[cjdb]

applies most of Zoe's feedback

libcxx/include/__algorithm/find.h

52

Nice catch! See requirements.compile.pass.cpp.

54

Is there a way for us to test this macro's presence/absence?

73

Unlike with CPOs, ranges algorithms don't have a problem here, because find(std::ranges::dummy()) is expressly forbidden.

libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.pass.cpp

1

Technically, no, since the docs don't specify std::find, only find. I wonder if that's disingenuous.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/find_iter_sent_proj.pass.cpp

41

Why? What does this add that's not already present?

45

I don't really understand your rationale here.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/special_function.compile.pass.cpp

31

Done, thanks!

libcxx/test/support/complexity_invocable.h

49 ↗

(On Diff #363205)

Unsigned integers shouldn't be used to represent arithmetic, and they don't play nicely with signed integers (which are bread and butter for iterators).

libcxx/test/support/test_range.h

65

It already is?

67

cpp20_input_iterator is move-only, which should implicitly make subrange<cpp20_input_iterator> move-only.

[• Quuxplusone]

libcxx/include/__algorithm/find.h

73

Well, it's not that find(std::ranges::dummy()) is forbidden; it's just that such a call expression is guaranteed not to find std::ranges::find (because std::ranges::find is not a function*). (*—Okay, in standardese it is a function, but it's a novel kind of function that in all respects behaves exactly like a niebloid variable; for example, it follows the lookup rules for variables, not the rules for functions.)

However, @cjdb, I believe that @zoecarver's main point here is that you forgot the extra inline namespace std::ranges::__cpo that needs to go around every niebloid variable. Without that namespace, you get ill-formedness if anyone (any libc++ maintainer) later tries to add a function by that same name into namespace std::ranges. See https://reviews.llvm.org/D107098#inline-1019805 for previous discussion of the inline namespace __cpo pattern and rationale for using it consistently rather than trying to guess which names we need it on this year. (And notice that once we ship without __cpo, it's technically an ABI break to go adding it. So that's why it's useful to get right on the first go-round.)

[cjdb]

libcxx/include/__algorithm/find.h

73

There appears to be conflation of the terms 'niebloid' and 'customisation point object', which might explain the confusion here. A 'niebloid' is any function that's in namespace std::ranges. Neibloids cannot be found by ADL, and when found by unqualified lookup, inhibit ADL. That we choose to implement them as function objects is a design decision I'm not entirely happy with.

This means that enclosing ranges::find in an inline namespace is incorrect in the niebloid case, because it gives way for a ranges::find function to be found by ADL.

[ldionne]

Comments per live review. Thanks!

Would it be possible to add the algorithms to the status page?

libcxx/include/CMakeLists.txt

19

That entry already exists below.

libcxx/include/__algorithm/find.h

66

Can you please make sure that you test this *at runtime* with a return of ranges::dangling? If it's valid to call it, even though it's kinda stupid to, we should test it.

67

__r -> __range?

libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp

12

Not needed anymore.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/find_iter_sent_proj.pass.cpp

15

For all the overloads that accept a projection, I would really like it if we could test at least one usage of a pointer to member, since that is basically the first (and often the only) use they will get by users. It would be a shame if that didn't work, so I'd like to see that exercised.

44

Assuming you parameterize the other ranges::find on the range instead of the iterator, we should even be able to replace this by ranges::find(I(ranges::begin(input)), I(ranges::end(input)), ...) and get rid of make_archetype_range altogether.

58

You could pass the expected complexity here and avoid calling ranges::ssize.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/ranges_find_range.pass.cpp

43

In this test, we end up only testing ranges::find on a ranges::subrange<whatever>, because that is what make_archetype_range returns. We should also test it on other range archetypes to make sure it works as expected.

66–92

For this overload of ranges::find which takes a range as an input, I think it would make sense to instead parameterize the various tests on the range type instead of the iterator type. That would also solve my comment above regarding this test only checking variants of ranges::subrange. I think something like my suggestion would work.

97

I like that we're testing various positions within the range, but we're always testing the same range. It would be useful to also test an empty range and a one-element range at least, WDYT?

99

Suggestion: Consider using an array that contains something like characters (`'0', '1', ...) to avoid a correspondence between the value in the range and its position.

142–143

Elsewhere in the test suite, we start with the runtime version and then do the static_assert. It's really a nitpick, but it would be good to be consistent since there's otherwise no difference between the two.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/requirements.compile.pass.cpp

13

Can you please add a comment explaining what this test does at a high level?

25–77

I suggest you rewrite this into a single function. That will simplify the test and avoid mistakes such as forgetting to call one of these functions (it seems like check_iterator_requirements is not being called at all right now).

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/special_function.compile.pass.cpp

78

I would suggest this instead:

template <class I, bool AlwaysFalse = false>
void find(...) {
  static_assert(AlwaysFalse);
}

Alternatively, we could have a helper like dependent_false<...> or always_false<T...> and use that.

libcxx/test/support/test_algorithm.h

22–29

I believe counting_invocable would convey what this class does better. I've been a bit confused by the use of complexity ever since I saw this patch. Also, we could move it to counting_predicates.h so it's alongside other similar helpers (and consider renaming that header if you want).

Also, I don't think the (1) and (2) points in the comment are necessary - those are like a justification for adding this type instead of reusing another one, but IMO we don't need that justification.

libcxx/test/support/test_iterators.h

1002–1003

I believe this should instead say that the intention is to measure the number of applications of the predicate, but that this iterator actually achieves that by counting the number of dereferences.

1005

As for complexity_invocable, I'm not a big fan of complexity here. How about counting_iterator?

libcxx/test/support/test_range.h

66

What about using test_input_range?

75

test_output_range?

[ldionne]

Gentle ping!