Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

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

Authored by cjdb on Jul 5 2021, 10:30 PM.


Group Reviewers
Restricted Project

Implements part of
Implements part of [alg.find].

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
zoecarver added inline comments.Jul 12 2021, 9:50 AM
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 added a comment.Jul 12 2021, 10:00 AM

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.

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 updated this revision to Diff 358114.Jul 12 2021, 5:55 PM
cjdb edited the summary of this revision. (Show Details)

rebases to activate CI

cjdb updated this revision to Diff 358115.Jul 12 2021, 5:58 PM

rebases to activate CI (round 2)

cjdb updated this revision to Diff 358148.Jul 12 2021, 10:06 PM
cjdb updated this revision to Diff 359367.Jul 16 2021, 9:54 AM

rebases to activate CI

ldionne requested changes to this revision.Jul 16 2021, 1:49 PM

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.

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.

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?

This revision now requires changes to proceed.Jul 16 2021, 1:49 PM
ldionne added inline comments.Jul 22 2021, 2:21 PM

Is there any way you can avoid doing this?

cjdb marked 2 inline comments as done.Jul 22 2021, 2:54 PM

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.


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 updated this revision to Diff 363148.Jul 30 2021, 10:47 AM

reworks testing

@ldionne ready for another round of reviewing :)

cjdb updated this revision to Diff 363205.Jul 30 2021, 2:39 PM
cjdb edited the summary of this revision. (Show Details)

removes dependency on abandoned patch

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.


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


_LIBCPP_HIDE_FROM_ABI and anything else from


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.


Do we need to update the docs about this?


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.


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


Hopefully you'll have it in a few days:


49 ↗(On Diff #363205)

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


This should probably go in test_ranges.h


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

cjdb updated this revision to Diff 366528.Aug 15 2021, 3:44 PM
cjdb marked 6 inline comments as done.

applies most of Zoe's feedback


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


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


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


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


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


I don't really understand your rationale here.


Done, thanks!

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


It already is?


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


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 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 added inline comments.Aug 15 2021, 8:38 PM

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 requested changes to this revision.Aug 17 2021, 2:59 PM

Comments per live review. Thanks!

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


That entry already exists below.


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.


__r -> __range?


Not needed anymore.


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.


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.


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


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.


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.


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?


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.


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.


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


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


I would suggest this instead:

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

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


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.


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.


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


What about using test_input_range?



This revision now requires changes to proceed.Aug 17 2021, 2:59 PM

Gentle ping!

cjdb abandoned this revision.Jan 18 2022, 11:53 AM
cjdb marked 12 inline comments as done.