This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Implement ranges::filter_view
ClosedPublic

Authored by ldionne on Sep 1 2021, 1:36 PM.

Details

Reviewers
var-const
Group Reviewers
Restricted Project
Commits
rG2b424f4ea82e: [libc++] Implement ranges::filter_view

Diff Detail

Event Timeline

ldionne created this revision.Sep 1 2021, 1:36 PM
ldionne requested review of this revision.Sep 1 2021, 1:36 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 1 2021, 1:36 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript

Note that this is still missing tests for the iterator and the sentinel, but I wanted to put it up for review to get some initial feedback. I'll finish the tests for iterator and sentinel when I get some more uninterrupted "free time".

ldionne updated this revision to Diff 370134.Sep 1 2021, 6:52 PM

Poke CI overnight

Quuxplusone added inline comments.
libcxx/include/__ranges/filter_view.h
125–126

These conditions smell backwards. Shouldn't it be _Cat satisfies derived_from<foo_tag>, i.e. derived_from<_Cat, foo_tag>?
But actually I would suggest testing the full concept: _If<bidirectional_iterator<_Cat>, bidirectional_iterator_tag, .... Because (sadly) it's perfectly possible in C++20 to have an iterator advertising bidirectional_iterator_tag that itself is only a forward_iterator. The forward_iterator concept does not have any "penalty for overpromising."

Both the bug(?) and the sad scenario could use a test case.

ldionne marked an inline comment as done.Dec 30 2021, 1:08 PM
ldionne added inline comments.
libcxx/include/__ranges/filter_view.h
125–126

Thanks for noticing, the conditions were indeed backwards. I added tests for the iterator in the latest revision and they cover that bug.

But actually I would suggest testing the full concept:

Regarding that, I'm really sticking to http://eel.is/c++draft/range.filter#iterator-3, which uses derived_from explicitly. Actually, while we're talking about that, do you see any way we can ever hit the else part (http://eel.is/c++draft/range.filter#iterator-3.4)? I don't. The iterator *must* be a forward_iterator at least (because View is a forward_range), which means that its iterator_category will be at least forward_iterator_tag. This means that it's always going to at least use line 125, and never go into the else.

ldionne updated this revision to Diff 396712.Dec 30 2021, 1:08 PM
ldionne marked an inline comment as done.

Rebase and finish writing tests. This should be ready for review.

Somewhat but not entirely reviewed.

libcxx/include/__ranges/filter_view.h
125–126

forward_iterator<C> implies derived_from<ITER-CONCEPT(C), forward_iterator_tag>, but (sadly, as usual) that isn't the same thing as derived_from<iterator_traits<C>::iterator_category, forward_iterator_tag>. For example: https://godbolt.org/z/ExzeoEbjv

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/arrow.pass.cpp
38–39 ↗(On Diff #396712)

As always, inheriting from test iterators is bad. :) At least copy one of your TODO comments to here: once contiguous_iterator no longer has operator-> this should go away entirely, right? But then you'll need to re-add a test in this vicinity for an iterator type that does have operator->. Maybe you should preemptively add that test now (it can't hurt) so that you won't forget later and accidentally lose test coverage.

I haven't looked at the wording for this conditional arrow operator, but surely it's important to test what happens when the underlying iterator type is int* (doesn't? have ->) versus Widget* (does? have ->). Or does int* count as having -> because you can say p->~TypedefForInt()?

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/decrement.pass.cpp
116 ↗(On Diff #396712)

Also test<int*>()? Likewise throughout.

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/increment.pass.cpp
88–89 ↗(On Diff #396712)

As a general rule, I'd feel safer with hard-coded expectations like

template <class Iterator, bool IsOnlyInput>
constexpr void test() {
    ~~~
    if constexpr (IsOnlyInput) {
        ~~~
    }
    if constexpr (!IsOnlyInput) {
        ~~~
    }
}
~~~
test<cpp17_input_iterator<int const*>, true>();
test<forward_iterator<int const*>, false>();

than relying on std::ranges::forward_range<minimal_view<Iterator, sentinel_wrapper<Iterator>>> to produce the expected answer. If someone mucks with minimal_view, let's fail noisily.
Also, we're not checking the return value of it++ on line 95; is that because we expect std::same_as<decltype(it++), void> and if so can we assert that?

libcxx/test/std/ranges/range.adaptors/range.filter/sentinel/base.pass.cpp
29–35 ↗(On Diff #396712)

At least the autos on line 29 could be int*s. But I'd write this as

// line 23: rename Iterator to It, and eliminate Sentinel
int a[5] = {};
auto view = FilterView(
    View(It(a), sentinel_wrapper<It>(It(a+5))),
    AlwaysTrue{}
);
37 ↗(On Diff #396712)

std::same_as<FilterSentinel> auto const sent = view.end(); as long as you're checking things?

ldionne updated this revision to Diff 403770.Jan 27 2022, 1:07 PM
ldionne marked 6 inline comments as done.

Address review comments

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/arrow.pass.cpp
38–39 ↗(On Diff #396712)

I refactored this test to remove inheritance and clean it up. It requires D118400 though.

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/increment.pass.cpp
88–89 ↗(On Diff #396712)

We are checking that it++ is the same as void, look on current line 99.

I'll hardcode the expectation.

libcxx/test/std/ranges/range.adaptors/range.filter/sentinel/base.pass.cpp
29–35 ↗(On Diff #396712)

I was going to say this: I'll use int* instead of auto, however I'll keep the rest as-is. This is used consistently throughout the patch, and I'd like to avoid doing it differently in even a single place.

But then I looked and I need to use auto because array's iterators are not portably pointers. And I don't want to get rid of std::array throughout these tests because it makes my life easier (can do .begin() and .end() instead of more complicated alternatives).

37 ↗(On Diff #396712)

I disagree -- that test belongs to the test for filter_view::end(), otherwise we're mucking up the fact that we're only testing .base() here. I did add these assertions to the tests for .end(), they were missing.

libcxx/test/std/ranges/range.adaptors/range.filter/adaptor.pass.cpp
14

Please git grep views::filter and uncomment the existing line you find, too.

libcxx/test/std/ranges/range.adaptors/range.filter/sentinel/base.pass.cpp
29–35 ↗(On Diff #396712)

And I don't want to get rid of std::array throughout these tests because it makes my life easier (can do .begin() and .end() instead of more complicated alternatives).

But a, a+5 is less complicated than a.begin(), a.end()! It just seems like you could get rid of a lot of the cruft here if you wanted.

ldionne updated this revision to Diff 416275.Mar 17 2022, 11:59 AM
ldionne marked 2 inline comments as done.

Address review comments and rebase.

Herald added a project: Restricted Project. · View Herald TranscriptMar 17 2022, 11:59 AM
ldionne added inline comments.Mar 17 2022, 11:59 AM
libcxx/test/std/ranges/range.adaptors/range.filter/sentinel/base.pass.cpp
29–35 ↗(On Diff #396712)

Keeping as-is because I don't want to start hardcoding array sizes around.

ldionne updated this revision to Diff 416276.Mar 17 2022, 12:01 PM

Remove unnecessary // UNSUPPORTED: libcpp-no-concepts markup.

ldionne updated this revision to Diff 416523.Mar 18 2022, 9:22 AM

Fix clang-tidy error. This is nice -- I'm not a huge fan of closing namespace comments for small namespaces, but at least we're forced to do it consistently, which everyone will agree is awesome.

ldionne updated this revision to Diff 416565.Mar 18 2022, 11:17 AM

Fix test failures on GCC.

cjdb removed a subscriber: cjdb.Mar 18 2022, 11:51 AM
ldionne updated this revision to Diff 417055.Mar 21 2022, 12:45 PM

Fix modules issues (hopefully all of them).

ldionne updated this revision to Diff 419835.Apr 1 2022, 12:46 PM

Use _LIBCPP_NO_UNIQUE_ADDRESS

var-const requested changes to this revision.Apr 1 2022, 4:58 PM
var-const added a subscriber: var-const.

Very close to LGTM. Most comments are optional (which includes all nits), but there's just a couple that I think are worth addressing.

libcxx/include/__ranges/filter_view.h
49

Nit: is there a reason to swap the order these are declared in, compared to the Standard? Not that it's an issue, but because of this, the constructor taking both of these parameters looks a little strange because the initialization order is the reverse of the argument order. Also, if there's a reason, I think it should be documented?

libcxx/test/std/ranges/range.adaptors/range.filter/adaptor.pass.cpp
66

Nit/question: why not let the number of elements to be deduced?

libcxx/test/std/ranges/range.adaptors/range.filter/begin.pass.cpp
155

Question: would it be worthwhile to test with a predicate that takes the argument by non-const reference?

libcxx/test/std/ranges/range.adaptors/range.filter/ctad.pass.cpp
28

Very optional: consider turning this comment into a static assertion instead.

libcxx/test/std/ranges/range.adaptors/range.filter/ctor.default.pass.cpp
14

Same comment about potentially testing noexcept as another default constructor test.

libcxx/test/std/ranges/range.adaptors/range.filter/ctor.view_pred.pass.cpp
79

Nit: consider using [[maybe_unused]].

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/compare.pass.cpp
13 ↗(On Diff #419835)

Optional: this seems untested.

35 ↗(On Diff #419835)

Optional: perhaps these type aliases could be moved to types.h as well, along with make_filter_view. They seem to take a significant part of the setup in many of these test files.

73 ↗(On Diff #419835)

Nit: move this right under the definition of FilterIteratorFor (I think it would be easier to read when the definition and the usage are next to each other)?

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/deref.pass.cpp
35 ↗(On Diff #419835)

Very optional: any reason not to get CTAD to deduce the number of arguments? The element type seems obvious enough not to cause any issues.

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/increment.pass.cpp
140 ↗(On Diff #419835)

Looks like this is either a leftover, or some issue that requires a comment.

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/iter_move.pass.cpp
13 ↗(On Diff #419835)

noexcept doesn't seem to be tested.

56 ↗(On Diff #419835)

Same comments as iter_swap.pass.cpp.

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/iter_swap.pass.cpp
14 ↗(On Diff #419835)

I don't see a test for this constraint. If you think it's overkill, feel free to ignore.

36 ↗(On Diff #419835)

Optional: this function is duplicated in many of the test files, I wonder if it should be moved to types.h?

50 ↗(On Diff #419835)

Very optional: consider splitting this into two assertions (to make it easier to see which condition failed if debugging is ever necessary). Applies below as well.

51 ↗(On Diff #419835)

I don't think this test file checks that iter_swap uses ranges::iter_swap (which a user can customize). Do you think it's worthwhile to test for that? Same with iter_move.

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/types.compile.pass.cpp
66 ↗(On Diff #419835)

Hmm, I don't see a test for

3.4 Otherwise, iterator_­category denotes C.

Would it be worthwhile to check with e.g. random_access_iterator_tag?

libcxx/test/std/ranges/range.adaptors/range.filter/sentinel/base.pass.cpp
30 ↗(On Diff #419835)

Ultranit: include <utility> (applies in a few test files).

37 ↗(On Diff #419835)

Nit: should this (and other similar uses) be decltype(auto) in the light of our recent discussion?

libcxx/test/std/ranges/range.adaptors/range.filter/sentinel/compare.pass.cpp
40 ↗(On Diff #419835)

Optional: test the case where result is true as well?

libcxx/test/std/ranges/range.adaptors/range.filter/sentinel/ctor.default.pass.cpp
12 ↗(On Diff #419835)

Optional: would it be worthwhile testing for noexcept-edness?

libcxx/test/std/ranges/range.adaptors/range.filter/sentinel/ctor.parent.pass.cpp
12 ↗(On Diff #419835)

Optional: test that the constructor is explicit?

This revision now requires changes to proceed.Apr 1 2022, 4:58 PM
ldionne updated this revision to Diff 421975.Apr 11 2022, 11:12 AM
ldionne marked 23 inline comments as done.

Address review comments.

libcxx/include/__ranges/filter_view.h
49

I believe this was originally to work around https://wg21.link/LWG3549 where we'd have padding if the base view inherited from view_interface, but that shouldn't be an issue anymore, so I flipped them.

libcxx/test/std/ranges/range.adaptors/range.filter/adaptor.pass.cpp
66

It is probably a remnant of copy-pasting tests for other adaptors. Changed.

libcxx/test/std/ranges/range.adaptors/range.filter/begin.pass.cpp
155

Test added. IMO it's a bit borderline on testing the implementation of ranges::find_if itself, but definitely easy enough to add. I added the same test to iterator::operator++ too since it calls ranges::find_if as well.

libcxx/test/std/ranges/range.adaptors/range.filter/ctor.view_pred.pass.cpp
79

Good point, applied throughout. I don't have the reflex to use it but I should. I guess that makes me old school.

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/compare.pass.cpp
13 ↗(On Diff #419835)

It is tested below with the static_assert(!has_equal<...>);

35 ↗(On Diff #419835)

Unfortunately, those are often slightly different in different test files, so I think this would add complexity instead of simplifying things.

73 ↗(On Diff #419835)

I'll actually remove FilterIteratorFor from this file.

libcxx/test/std/ranges/range.adaptors/range.filter/iterator/iter_swap.pass.cpp
36 ↗(On Diff #419835)

Hmm, you're right about the duplication, however the type of the view is hardcoded here in this test. If I move it to a generic place like types.h, I'd have to hardcode the fact that it returns a filter_view over a minimal_view, and IMO that would make it pretty weird. So yeah, I'm not sure it's worth sharing.

50 ↗(On Diff #419835)

IMO it makes sense to split the checks below because they are actual things that we're testing, however this one is just testing the test, so I think it makes more sense to leave it as terse an unobtrusive as possible.

51 ↗(On Diff #419835)

Added tests by defining my own noexcept/non-noexcept types that override iter_move() (here and in iter_move).

libcxx/test/std/ranges/range.adaptors/range.filter/sentinel/base.pass.cpp
37 ↗(On Diff #419835)

I'm using ASSERT_SAME_TYPE in a bunch of places because of the issues with std::same_as<...> auto, but I used decltype(auto) in the few remaining places.

libcxx/test/std/ranges/range.adaptors/range.filter/sentinel/ctor.parent.pass.cpp
12 ↗(On Diff #419835)

There is one below that checks !std::is_convertible.

var-const accepted this revision.Apr 11 2022, 1:46 PM

Thank you for addressing the feedback! LGTM.

This revision is now accepted and ready to land.Apr 11 2022, 1:46 PM
ldionne updated this revision to Diff 422290.Apr 12 2022, 10:41 AM

Fix GCC CI issues.

This revision was automatically updated to reflect the committed changes.