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

[cjdb]

Summary

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

[miscco]

libcxx/include/__algorithm/find.h

42

I find it a bad idea to pessimize the classic algorithm

Usually the algorithms are simple enough that code duplication is not an issue

55

Would it make sense to simply do using __function_like :.__function_like;

61

plain std:: qualifier should be _VSTD::

68

plain ranges:: qualifier should be something else

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

55 ↗

(On Diff #356601)

I have trouble discerning what the individual tests actually test.

I would suggest to pull in the auto subrange = std::ranges::subrange(I<array_t::iterator>(range.begin()), sentinel_wrapper(range.end())); into each clause and give it a descriptive name like

auto find_without_projection = std::ranges::subrange(I<array_t::iterator>(range.begin()), sentinel_wrapper(range.end()));`

That way one can directly read what the test is testing

[miscco]

libcxx/include/__algorithm/find.h

66

also proj needs to be ugly __proj?

[cjdb]

responds to @miscco's feedback

[cjdb]

libcxx/include/__algorithm/find.h

42

I'm not fond of this either, but it was requested of me. ATTN @ldionne.

55

No, we already decided against this in ranges::advance.

68

It's been this way for the entirety of ranges.

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

55 ↗

(On Diff #356601)

Yes to better names, but I don't see how moving the subrange anywhere will improve readability.

[tcanens]

libcxx/include/__functional/identity.h

36

This is nonconforming.

[tcanens]

libcxx/include/__algorithm/find.h

45

If all real projections are already passed by reference_wrapper then there's no need to use __invoke.

[cjdb]

libcxx/include/__functional/identity.h

36

Why?

[tcanens]

libcxx/include/__functional/identity.h

36

struct std::identity is required to work and doesn't if it is a _typedef-name_.

Also, the injected-class-name is different and as a public member that is observable.

[ldionne]

libcxx/include/__algorithm/find.h

42

So the general idea is to avoid duplicating non trivial algorithmic logic, especially when we have optimizations in place. That's always been my goal, and that's why I originally requested that we try sharing the implementations.

Seeing this patch, I think we can agree it will have to be decided on a case-by-case basis. It's difficult to argue for sharing this simple for-loop given the added complexity.

@cjdb For something simple like this, I think it's fine to reimplement.

libcxx/include/module.modulemap

241

What happens if you don't do this?

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

55 ↗

(On Diff #356601)

Sorry for the churn, but I strongly think that using "better names" makes things harder to read. Instead of trying to use descriptive names that are longer but that eventually fail to be descriptive because identifiers can't be plain english, use a simple and consistent name like it, but add a comment in plain english that explains what this test case is about. For example, I don't find different_value_result especially telling, and I don't think it's possible to explain the test case properly in the number of characters that keeps a variable name reasonable.

libcxx/test/support/test_iterators.h

881–885

Why do we need to add this? This is only a convenience, right? If so, let's remove it and use x.base() == y.base() in the tests. We must keep our archetypes minimal.

[cjdb]

responds to @ldionne's feedback

[cjdb]

libcxx/include/module.modulemap

241

The __function_like properties aren't exported. It's not clear to me if this is intentional or a bug.

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

55 ↗

(On Diff #356601)

I'm grateful.

libcxx/test/support/test_iterators.h

881–885

It's a requirement for alg(cpp20_input_iterator(first), sentinel(last)). Without it, that will fail because cpp20_input_iterator has the minimal input_iterator interface.

[• Quuxplusone]

libcxx/include/module.modulemap

241

+1 please don't export things here; and please do format this module as a one-liner like all the others.

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

73–75 ↗

(On Diff #357366)

This interleaving will become unwieldy very quickly as you add C++20-specific algorithms.
I recommend creating a new function, test_ranges_algorithms(). It will be small to start with, but it will eventually look very similar to this one. You might even go ahead and make that function a complete copy of this one, and just comment out the lines that don't work yet. Comment them in as they are implemented.
Compare line 182 below (bit_cast). I'm basically asking for that approach.

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

119–122 ↗

(On Diff #357366)

Ditto here. I recommend a new function test_ranges_algorithms.
However, I also would like to make my own NFC cleanup so that nodiscard_extensions.{pass,verify}.cpp can be meaningfully diffed against each other; so until that happens, I don't care so much about what happens in this file.

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

65–66 ↗

(On Diff #357366)

This seems incorrect. subrange is a borrowed range, so there shouldn't be any dangling here.
(Testing both lvalues and rvalues is important, though, exactly because the Ranges library messes with return types like this based on value category.)

55 ↗

(On Diff #356601)

+100 that iterator_result should be spelled it.
range_result should be spelled r.
range should probably be spelled input, for clarity. Alternatively, remove the dependency on std::array — make it a plain old array, and name it a, just like in all existing algorithms tests.

It's unclear to me what the difference is between projectable<int> and projectable<double>. Let's replace double with int throughout. Having done that, let's make Projectable into a non-template. Having done that, let's make check_find() take a template type parameter class It, not a template template parameter: e.g. check_find<contiguous_iterator<Projectable>>();.

It's also not clear to me how Projectable differs meaningfully from int. Projectable is providing a lot of implicit conversions every which way; aren't those just re-implementing things that int already would have had? I think it would make more sense to define a type _`Projection`_ and then test some calls like

template<class T>
struct Mod10 {
    constexpr int operator()(const T& x) const { return x % 10; }
};
template<class It>
constexpr bool check_find() {
    int a[] = {21, 22, 23, 24, 25, 23};
    It first = It(a);
    It last = It(a+5);
    auto r = std::ranges::subrange(first, last);
    {
        It it = std::ranges::find(r, 23);
        assert(base(it) == a+2);
        it = std::ranges::find(r, 3);
        assert(base(it) == a+5);
        it = std::ranges::find(r, 3, Mod10<int>());
        assert(base(it) == a+2);
        it = std::ranges::find(r, 6, Mod10<int>());
        assert(base(it) == a+5);
    }
    // repeat with `r` replaced by `a`, by `first, last`, possibly by `std::move(r)`, possibly etc.
    // possibly repeat with `int` replaced by `MoveOnly`
}

This will be much easier to see what's going on.

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

27 ↗

(On Diff #357366)

Please avoid namespace aliases whenever possible. In this case I think it's pretty easy to avoid.

40 ↗

(On Diff #357366)

De Morgan's Laws are unhappy here. You wrote !(x works AND y works AND z works), but what you meant to test was !(x works) AND !(y works) AND !(z works). You'll need to turn the concept on line 33 into a disjunction of four constraints. Alternatively:

void test_unqualified_lookup() {
    using T = std::pair<int, int>;
    T value;
    T a[5];
    auto r = std::ranges::subrange(a, a+5);
    static_assert(!requires { find(a, a+5, value); });
    static_assert(!requires { find(a, a+5, value, &T::first); });
    static_assert(!requires { find(r, value); });
    static_assert(!requires { find(r, value, &T::first); });
}

Notice that your iterator-pair find arguments don't include anything out of std::ranges, so it's totally expected that they fail to find std::ranges::find via ADL. (The fact that the iterator arguments were returned from a call to std::ranges::begin(a) doesn't matter at all. ADL cares only about the types of the arguments, and in this case they're plain old pointers to std::pairs.)
Also, won't ADL happily find std::find? I think the main thing you were testing in the old code was that std::find had no two-argument overload, so find(r, value) was ill-formed.

libcxx/test/support/test_iterators.h

881–885

Even better: use base(x) == base(y) in the tests, because test_iterators.h provides base() as a free function, so that we can also test against raw pointer types like int*.

[zoecarver]

Generally this looks good to me. I have a few small comments, nothing too major. Looking forward to shipping this!

libcxx/include/__algorithm/find.h

68

The std:: qualifier should be _VSTD.

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

74 ↗

(On Diff #357366)

Nit: maybe use ranges here? (I.e., std::ranges::begin.)

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

50 ↗

(On Diff #357366)

I like this. But other don't. Let's go for consistency and use std::ranges everywhere.

(The reason not to use this, which is fair, is that we can't change it at any point. We can do a simple find and replace to go from std::ranges -> ranges or stdr or whatever, but we can't go from ranges:: to std::ranges.)

61 ↗

(On Diff #357366)

I think it would reduce complexity, and increase clarity in what is actually being tested if tests that had Proj = identity didn't use the projectable type.

69 ↗

(On Diff #357366)

This is testing that the conversion operator is invoked? I'm not sure you need to test that, but if you want to, I'd use a specific "convertible_to_int" type or something (or even just a "convertible<T>" type).

93 ↗

(On Diff #357366)

Where's the case where the first argument is a range and the last argument is a projection?

libcxx/test/support/test_iterators.h

883

Thanks for fixing this type :)

I probably should have done this when I needed a similar use case rather than just writing my own sentinel.

[cjdb]

• fixes build failures
• fixes unqualified lookup test
• replaces std with _VSTD
• replaces projectable with int

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

50 ↗

(On Diff #357366)

I'm not sure that's a strong enough argument, since the alias improves readability. A counterargument to the reason you've provided is that we can use a regex to find all aliases.

61 ↗

(On Diff #357366)

I'm not sure I understand what you're asking for here. Could you please rephrase?

69 ↗

(On Diff #357366)

Strictly speaking, this case could be omitted, but it's documenting that int == double can return true (which I think is important in light of the test below).

93 ↗

(On Diff #357366)

Right below.

55 ↗

(On Diff #356601)

+100 that iterator_result should be spelled it.
range_result should be spelled r.
range should probably be spelled input, for clarity. Alternatively, remove the dependency on std::array — make it a plain old array, and name it a, just like in all existing algorithms tests.

Your opinion has been noted.

It's unclear to me what the difference is between projectable<int> and projectable<double>. Let's replace double with int throughout. Having done that, let's make Projectable into a non-template. Having done that, let's make check_find() take a template type parameter class It, not a template template parameter: e.g. check_find<contiguous_iterator<Projectable>>();.

Considering that find(range_of_ints, some_double) is permitted by the interface, we need to be testing that.

The rest has been applied in some fashion.

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

27 ↗

(On Diff #357366)

Your opinion has been noted.

[cjdb]

• fixes input iterator issue
• adds complexity_iterator
• makes test more readable

[zoecarver]

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

61 ↗

(On Diff #357366)

Here you're not testing anything "special". You don't need a type that's convertible. You don't need a type that's projectable.

By using the projectable type here, you seem to indicate that it's needed for the test. Given that its name is projectable, readers might think that you're testing a projection. But you're not. I think you should just write this test as follows:

using array_t = std::array<int, 10>;
auto range = array_t{...};
auto subrange = std::ranges::subrange(I<array_t::iterator>(range.begin()), sentinel_wrapper(range.end()));
auto const range_result = ranges::find(subrange, 6);

No need for any extra complexity.

This makes it even more clear later that when you use the projectable type, you're testing that the projections work, specifically.

69 ↗

(On Diff #357366)

If you want to keep it, let's test this without the projectable type. (You can either use int and double directly, or you could use a convertible<T> type as I suggested above, either is OK with me.)

It's not clear that a type named projectable is convertible. And it's not clear in the implementation of the type why it's important that there's a conversion operator.

Here it could be much more clear what's being tested, simply by not using the projectable type. That would also make this test simpler.

[zoecarver]

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

[zoecarver]

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!

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

148

Remnants of a fun debug session?

[zoecarver]

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

31

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.

45

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

31

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.

45

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

11

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.

34

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

9

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.

16

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

131

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 ↗

(On Diff #363205)

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

40 ↗

(On Diff #363205)

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.

44 ↗

(On Diff #363205)

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

(On Diff #363205)

This should probably go in test_ranges.h

67 ↗

(On Diff #363205)

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 ↗

(On Diff #363205)

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

40 ↗

(On Diff #363205)

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

44 ↗

(On Diff #363205)

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 ↗

(On Diff #363205)

It already is?

67 ↗

(On Diff #363205)

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

13

Not needed anymore.

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

15 ↗

(On Diff #366528)

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 ↗

(On Diff #366528)

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 ↗

(On Diff #366528)

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 ↗

(On Diff #366528)

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 ↗

(On Diff #366528)

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 ↗

(On Diff #366528)

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 ↗

(On Diff #366528)

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 ↗

(On Diff #366528)

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 ↗

(On Diff #366528)

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

25–77 ↗

(On Diff #366528)

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

79

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 ↗

(On Diff #366528)

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

946–947

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.

949

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

libcxx/test/support/test_range.h

66 ↗

(On Diff #366528)

What about using test_input_range?

75 ↗

(On Diff #366528)

test_output_range?

[ldionne]

Gentle ping!

libcxx/include/CMakeLists.txt

set(files
   __algorithm/copy_n.h
   __algorithm/copy.h
   __algorithm/count_if.h
   __algorithm/count.h
   __algorithm/equal_range.h
   __algorithm/equal.h
   __algorithm/fill_n.h
   __algorithm/fill.h
+  __algorithm/find.h
   __algorithm/find_end.h
   __algorithm/find_first_of.h
   __algorithm/find_if_not.h
   __algorithm/find_if.h
   __algorithm/find.h
   __algorithm/for_each_n.h
   __algorithm/for_each.h
   __algorithm/generate_n.h

libcxx/include/__algorithm/find.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_FIND_H
 #define _LIBCPP___ALGORITHM_FIND_H
 
 #include <__config>
+#include <__function_like.h>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/operations.h>
+#include <__functional/ranges_operations.h>
+#include <__functional/reference_wrapper.h>
+#include <__functional_base>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _InputIterator, class _Tp>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator
 find(_InputIterator __first, _InputIterator __last, const _Tp& __value_) {
   for (; __first != __last; ++__first)
     if (*__first == __value_)
       break;
   return __first;
 }
 
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace ranges {
+  struct __find_fn final : __function_like {
+    constexpr explicit __find_fn(__tag __x) noexcept : __function_like(__x) {}
+
+    template<input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, class _Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<_Ip, _Proj>, const _Tp*>
+    _LIBCPP_NODISCARD_EXT constexpr
+    _Ip operator()(_Ip __first, const _Sp __last, const _Tp& __value, _Proj __proj = {}) const
+    {
+      for (; __first != __last; ++__first) {
+        if (_VSTD::invoke(__proj, *__first) == __value) {
+          break;
+        }
+      }
+      return __first;
+    }
+
+    template<input_range _Rp, class _Tp, class _Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Rp>, _Proj>, const _Tp*>
+    _LIBCPP_NODISCARD_EXT constexpr
+    borrowed_iterator_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Proj __proj = {}) const
+    {
+      return (*this)(ranges::begin(__r), ranges::end(__r), __value, _VSTD::ref(__proj));
+    }
+  };
+
+  inline constexpr auto find = __find_fn(__function_like::__tag());
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_FIND_H

libcxx/include/__functional/identity.h

struct identity {
     template<class _Tp>
     _LIBCPP_NODISCARD_EXT constexpr _Tp&& operator()(_Tp&& __t) const noexcept
     {
         return _VSTD::forward<_Tp>(__t);
     }
 
     using is_transparent = void;
 };
+
 #endif // _LIBCPP_STD_VER > 17
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___FUNCTIONAL_IDENTITY_H

libcxx/include/algorithm

 template<class InputIterator, class Size, class Function>
     constexpr InputIterator     // constexpr in C++20
     for_each_n(InputIterator first, Size n, Function f); // C++17
 
 template <class InputIterator, class T>
     constexpr InputIterator     // constexpr in C++20
     find(InputIterator first, InputIterator last, const T& value);
 
+template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
+  requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+  constexpr I ranges::find(I first, S last, const T& value, Proj proj = {}); // since C++20
+
+template<input_range R, class T, class Proj = identity>
+  requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+  constexpr borrowed_iterator_t<R>
+    ranges::find(R&& r, const T& value, Proj proj = {}); // since C++20
+
 template <class InputIterator, class Predicate>
     constexpr InputIterator     // constexpr in C++20
     find_if(InputIterator first, InputIterator last, Predicate pred);
 
 template<class InputIterator, class Predicate>
     constexpr InputIterator     // constexpr in C++20
     find_if_not(InputIterator first, InputIterator last, Predicate pred);
 

libcxx/include/module.modulemap

module __algorithm {
       module copy_if                  { header "__algorithm/copy_if.h" }
       module copy_n                   { header "__algorithm/copy_n.h" }
       module count                    { header "__algorithm/count.h" }
       module count_if                 { header "__algorithm/count_if.h" }
       module equal                    { header "__algorithm/equal.h" }
       module equal_range              { header "__algorithm/equal_range.h" }
       module fill                     { header "__algorithm/fill.h" }
       module fill_n                   { header "__algorithm/fill_n.h" }
-      module find                     { header "__algorithm/find.h" }
+      module find {
+        header "__algorithm/find.h"
+        export __function_like
+      }
       module find_end                 { header "__algorithm/find_end.h" }
       module find_first_of            { header "__algorithm/find_first_of.h" }
       module find_if                  { header "__algorithm/find_if.h" }
       module find_if_not              { header "__algorithm/find_if_not.h" }
       module for_each                 { header "__algorithm/for_each.h" }
       module for_each_n               { header "__algorithm/for_each_n.h" }
       module generate                 { header "__algorithm/generate.h" }
       module generate_n               { header "__algorithm/generate_n.h" }

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

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// Test that entities declared [[nodiscard]] as at extension by libc++, are
+// only actually declared such when _LIBCPP_ENABLE_NODISCARD is specified.
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// All entities to which libc++ applies [[nodiscard]] as an extension should
+// be tested here and in nodiscard_extensions.fail.cpp. They should also
+// be listed in `UsingLibcxx.rst` in the documentation for the extension.
+
+#include <algorithm>
+#include <ranges>
+
+#include <array>
+
+#include "test_macros.h"
+
+
+int main(int, char**) {
+  auto arr = std::array{0, 1, 2, 3, 4, 5};
+  namespace ranges = std::ranges;
+
+  ranges::find(ranges::begin(arr), ranges::end(arr), 1);
+  ranges::find(arr, 1);
+
+  return 0;
+}

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

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// Test that entities declared [[nodiscard]] as an extension by libc++, are
+// only actually declared such when _LIBCPP_ENABLE_NODISCARD is specified.
+
+// All entities to which libc++ applies [[nodiscard]] as an extension should
+// be tested here and in nodiscard_extensions.pass.cpp. They should also
+// be listed in `UsingLibcxx.rst` in the documentation for the extension.
+
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_ENABLE_NODISCARD
+
+#include <algorithm>
+#include <ranges>
+
+#include <array>
+
+int main()
+{
+  auto arr = std::array{0, 1, 2, 3, 4, 5};
+  namespace ranges = std::ranges;
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::find(ranges::begin(arr), ranges::end(arr), 1);
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::find(arr, 1);
+}

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

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10, gcc-11
+
+// <algorithm>
+
+// ranges::find
+
+#include <algorithm>
+
+#include <array>
+#include <cassert>
+#include <concepts>
+#include <ranges>
+#include <utility>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "test_range.h"
+
+namespace ranges = std::ranges;
+
+template<template<class...> class I>
+constexpr bool check_find()
+{
+
+  auto const range = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+  auto successor = [](auto const x) { return x + 1; };
+
+  {
+    constexpr auto value = 6;
+    constexpr auto expected_complexity = 7;
+    auto const expected_result = range.begin() + 6;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input.begin(), input.end(), value);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input, value);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+  }
+  {
+    constexpr auto value = 3.0;
+    constexpr auto expected_complexity = 4;
+    auto const expected_result = range.begin() + 3;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input.begin(), input.end(), value);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input, value);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+  }
+  {
+    constexpr auto value = 3.7;
+    constexpr auto expected_complexity = ranges::ssize(range);
+    auto const expected_result = range.begin() + expected_complexity;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input.begin(), input.end(), value);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input, value);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+  }
+  {
+    constexpr auto value = 6;
+    constexpr auto expected_complexity = 6;
+    auto const expected_result = range.begin() + 5;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input.begin(), input.end(), value, successor);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input, value, successor);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+  }
+  {
+    constexpr auto value = 3.0;
+    constexpr auto expected_complexity = 3;
+    auto const expected_result = range.begin() + 2;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input.begin(), input.end(), value, successor);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input, value, successor);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+  }
+  {
+    constexpr auto value = 3.7;
+    constexpr auto expected_complexity = ranges::ssize(range);
+    auto const expected_result = range.begin() + expected_complexity;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input.begin(), input.end(), value, successor);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find(input, value, successor);
+      assert(result.base().base() == expected_result);
+      assert(result.count() == expected_complexity);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**)
+{
+  static_assert(check_find<cpp17_input_iterator>());
+  check_find<cpp17_input_iterator>();
+
+  static_assert(check_find<cpp20_input_iterator>());
+  check_find<cpp20_input_iterator>();
+
+  static_assert(check_find<forward_iterator>());
+  check_find<forward_iterator>();
+
+  static_assert(check_find<bidirectional_iterator>());
+  check_find<bidirectional_iterator>();
+
+  static_assert(check_find<random_access_iterator>());
+  check_find<random_access_iterator>();
+
+  static_assert(check_find<contiguous_iterator>());
+  check_find<contiguous_iterator>();
+
+  ASSERT_SAME_TYPE(decltype(ranges::find(std::vector<int>(10), 6)),
+                   ranges::dangling);
+
+  ASSERT_SAME_TYPE(decltype(ranges::find(std::vector<int>(10), 6, {})),
+                   ranges::dangling);
+
+  return 0;
+}

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

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// ranges::find
+
+#include <algorithm>
+
+#include <array>
+#include <iterator>
+#include <ranges>
+#include <utility>
+
+#include "test_range.h"
+#include "test_standard_function.h"
+
+static_assert(is_function_like<decltype(std::ranges::find)>());
+
+namespace ranges = std::ranges;
+
+namespace std::ranges {
+  template<class T>
+  class basic_istream_view {
+    struct iterator;
+  public:
+    iterator begin();
+    default_sentinel_t end() const;
+  };
+} // namespace std::ranges
+
+// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent
+// name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for
+// the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup.
+template <class T>
+constexpr bool no_unqualified_lookup() {
+  auto identity = ranges::basic_istream_view<T>();
+  static_assert(!requires(T value) { find(ranges::begin(identity), ranges::end(identity), value); });
+  static_assert(!requires(T value) { find(ranges::begin(identity), ranges::end(identity), value.first, &T::first); });
+  static_assert(!requires(T value) { find(identity, value); });
+  static_assert(!requires(T value) { find(identity, value.first, &T::first); });
+  return true;
+};
+
+static_assert(no_unqualified_lookup<std::pair<int, int>>());
+
+namespace test {
+template <class>
+struct iterator {
+  using value_type = std::pair<int, int>;
+  using difference_type = std::ptrdiff_t;
+  using iterator_category = std::forward_iterator_tag;
+
+  iterator() = default;
+
+  value_type operator*() const;
+  iterator& operator++();
+  iterator operator++(int);
+
+  bool operator==(iterator const&) const = default;
+};
+
+template<class>
+struct range {
+  std::pair<int, int> const* begin() const;
+  std::pair<int, int> const* end() const;
+};
+
+template <class I>
+void find(iterator<I>, iterator<I>, std::pair<int, int> const&) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I, class Proj>
+void find(iterator<I>, iterator<I>, int, Proj) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class R>
+void find(R&&, std::pair<int, int> const&) {
+  static_assert(std::same_as<R, R*>);
+}
+
+template <class R, class Proj>
+void find(R&&, int, Proj) {
+  static_assert(std::same_as<R, R*>);
+}
+} // namespace test
+
+// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a
+// function call ([expr.call]), they inhibit argument-dependent name lookup.
+void adl_inhibition() {
+  using std::ranges::find;
+
+  test::iterator<int*> x;
+  (void)find(x, x, std::pair{10, 20});
+  (void)find(x, x, 10, &std::pair<int, int>::first);
+
+  test::range<int*> r;
+  (void)find(r, std::pair{10, 20});
+  (void)find(r, 10, &std::pair<int, int>::first);
+}

libcxx/test/support/test_iterators.h

public:
   }
 
 private:
   I base_;
   difference_type stride_count_ = 0;
   difference_type stride_displacement_ = 0;
 };
 
+template<class T, class U>
+concept sentinel_for_base = requires(U const& u) {
+  u.base();
+  requires std::input_or_output_iterator<std::remove_cvref_t<decltype(u.base())>>;
+  requires std::equality_comparable_with<T, decltype(u.base())>;
+};
+
 template <std::input_or_output_iterator I>
 class sentinel_wrapper {
 public:
   sentinel_wrapper() = default;
   constexpr explicit sentinel_wrapper(I base) : base_(std::move(base)) {}
 
   constexpr bool operator==(I const& other) const requires std::equality_comparable<I> {
     return base_ == other;
   }
 
+  template<std::input_or_output_iterator I2>
+  requires sentinel_for_base<I, I2>
+  constexpr bool operator==(I2 const& other) const {
+    return base_ == other.base();
+  }
 private:
   I base_ = I();
 };
 
 template <class It>
 class three_way_contiguous_iterator
 {
     static_assert(std::is_pointer_v<It>, "Things probably break in this case");
public:
     friend TEST_CONSTEXPR_CXX14
     difference_type operator-(const three_way_contiguous_iterator& x, const three_way_contiguous_iterator& y) {
         return x.base() - y.base();
     }
 
     friend auto operator<=>(const three_way_contiguous_iterator&, const three_way_contiguous_iterator&) = default;
 };
 
 template<std::input_iterator I>
 class complexity_iterator {
 public:
   using value_type = std::iter_value_t<I>;
   using difference_type = std::iter_difference_t<I>;
   using iterator_concept = iterator_concept_t<I>;
 
   constexpr complexity_iterator() requires std::default_initializable<I> = default;
 
   constexpr explicit complexity_iterator(I i)
   : base_(std::move(i))
   {}