This is an archive of the discontinued LLVM Phabricator instance.

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

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

Details

Reviewers
ldionne
zoecarver
Mordante
Quuxplusone
Group Reviewers
Restricted Project
Summary

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

Diff Detail

Event Timeline

cjdb created this revision.Jul 5 2021, 10:30 PM
cjdb requested review of this revision.Jul 5 2021, 10:30 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 5 2021, 10:30 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
miscco added a subscriber: miscco.Jul 6 2021, 5:50 AM
miscco added inline comments.
libcxx/include/__algorithm/find.h
37

I find it a bad idea to pessimize the classic algorithm

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

57

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

63

plain std:: qualifier should be _VSTD::

70

plain ranges:: qualifier should be something else

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

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 added inline comments.Jul 6 2021, 5:55 AM
libcxx/include/__algorithm/find.h
68

also proj needs to be ugly __proj?

cjdb updated this revision to Diff 356745.Jul 6 2021, 8:49 AM
cjdb marked 4 inline comments as done.

responds to @miscco's feedback

cjdb added inline comments.Jul 6 2021, 8:50 AM
libcxx/include/__algorithm/find.h
37

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

57

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

70

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

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

tcanens added a subscriber: tcanens.Jul 7 2021, 8:44 PM
tcanens added inline comments.
libcxx/include/__functional/identity.h
34

This is nonconforming.

tcanens added inline comments.Jul 7 2021, 8:51 PM
libcxx/include/__algorithm/find.h
40

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

cjdb added inline comments.Jul 8 2021, 9:17 AM
libcxx/include/__functional/identity.h
34

Why?

tcanens added inline comments.Jul 8 2021, 9:51 AM
libcxx/include/__functional/identity.h
34

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 requested changes to this revision.Jul 8 2021, 1:57 PM
ldionne added inline comments.
libcxx/include/__algorithm/find.h
37

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 ↗(On Diff #356745)

What happens if you don't do this?

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

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
880–884

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.

This revision now requires changes to proceed.Jul 8 2021, 1:57 PM
cjdb updated this revision to Diff 357366.Jul 8 2021, 2:55 PM
cjdb marked an inline comment as done.

responds to @ldionne's feedback

cjdb marked 7 inline comments as done.Jul 8 2021, 2:56 PM
cjdb added inline comments.
libcxx/include/module.modulemap
241 ↗(On Diff #356745)

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

I'm grateful.

libcxx/test/support/test_iterators.h
880–884

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 requested changes to this revision.Jul 8 2021, 3:30 PM
Quuxplusone added a subscriber: Quuxplusone.
Quuxplusone added inline comments.
libcxx/include/module.modulemap
241 ↗(On Diff #356745)

+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
55

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

66–67

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

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

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

41

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
880–884

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

This revision now requires changes to proceed.Jul 8 2021, 3:30 PM

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
70

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
51

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

62

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.

70

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

94

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

libcxx/test/support/test_iterators.h
882

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 updated this revision to Diff 357685.Jul 9 2021, 6:58 PM
cjdb marked 14 inline comments as done.
  • 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
51

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.

55

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

62

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

70

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

94

Right below.

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

Your opinion has been noted.

cjdb updated this revision to Diff 357846.Jul 12 2021, 12:01 AM
cjdb edited the summary of this revision. (Show Details)
  • fixes input iterator issue
  • adds complexity_iterator
  • makes test more readable
zoecarver added inline comments.Jul 12 2021, 9:27 AM
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges::find/ranges_find.pass.cpp
62

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.

70

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.

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

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
147 ↗(On Diff #357846)

Remnants of a fun debug session?

zoecarver added inline comments.Jul 12 2021, 9:50 AM
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 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.

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

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?

This revision now requires changes to proceed.Jul 16 2021, 1:49 PM
ldionne added inline comments.Jul 22 2021, 2:21 PM
libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/special_function.compile.pass.cpp
30 ↗(On Diff #359367)

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.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find/special_function.compile.pass.cpp
30 ↗(On Diff #359367)

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.

libcxx/include/__algorithm/find.h
54

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

56

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

75

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
30 ↗(On Diff #359367)

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

libcxx/include/__algorithm/find.h
54

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

56

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

75

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
30 ↗(On Diff #359367)

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.

libcxx/include/__algorithm/find.h
75

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 added inline comments.Aug 15 2021, 8:38 PM
libcxx/include/__algorithm/find.h
75

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?

libcxx/include/CMakeLists.txt
19

That entry already exists below.

libcxx/include/__algorithm/find.h
68

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.

69

__r -> __range?

libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp
12 ↗(On Diff #366528)

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
78 ↗(On Diff #366528)

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
889–890

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.

892

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?

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.