Page MenuHomePhabricator

[libcxx][views] Add drop_view.
Changes PlannedPublic

Authored by zoecarver on May 6 2021, 5:41 PM.

Details

Reviewers
cjdb
ldionne
EricWF
Quuxplusone
Group Reviewers
Restricted Project
Summary

The first view in the libc++ ranges library 🚀

Diff Detail

Event Timeline

zoecarver created this revision.May 6 2021, 5:41 PM
zoecarver requested review of this revision.May 6 2021, 5:41 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 6 2021, 5:41 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
zoecarver added inline comments.May 6 2021, 5:42 PM
libcxx/test/std/ranges/range.adaptors/range.drop/range.drop.view.pass.cpp
179

I just had a thought: I should add some tests where views::all comes into play (so make sure we use the deduction guides to automatically create drop_view<subrange> and drop_view<ref_view>). I'll do this tomorrow morning.

cjdb requested changes to this revision.May 6 2021, 7:12 PM

Overall, this is great! Sadly, I can't LGTM till caching is implemented, but I think we'll be good to land this sometime next week :-)

libcxx/include/__iterator/primitives.h
98

If this is temporary, carry on. If there's a genuine concern, please highlight it in D101922.

libcxx/include/__ranges/drop_view.h
34–38

I'd very much appreciate a few simple libcxx tests for this concept. It's so important that I want so much as a light breeze nearby to cause a build failure.

42

Nit 1: please suffix members with an underscore.
Nit 2: please put private stuff at the bottom unless it needs to be seen.

59–61

Let's hold off on merging this with main till ranges::next is available (I'll throw up a patch as soon as D101922 is approved).

You also need to cache the result for forward ranges (see [range.semi.wrap]). This is observable behaviour, so please add a test to ensure the caching happens.

66–68

I'd suggest wrapping this into a static __begin_impl so there's a shared impl. Same with size, but not end.

libcxx/test/std/ranges/range.adaptors/range.drop/range.drop.view.pass.cpp
24

Nit: I'd prefer if this were std::array<int, 8>.

28–67

You have four views that satisfy range<T const>, if I'm not mistaken. Please ensure there's at least one non-const input view, and one non-const forward view too. Also, please check out test/support/test_range.h to see if some of these are already available (I don't think they are), and add some utilities there, as they'll be necessary in other range tests too.

62–64

const-qualified access member functions should probably return const-iterators. Similarly elsewhere.

69

cpp17_ or cpp20_input_iterator

78–80

Please also expand to check const qualification. This is very important!

81–85

These should possibly go into their own ctad.compile.pass.cpp.

111–136

I'd prefer it if these were in functions such as check_begin(). The more intrinsic documentation we have, the less likely comments can go out of date.

117–118

Can we test with some odd numbers and even non-powers of 2 too please?

155–172

We should have const-qualified tests for all these.

This revision now requires changes to proceed.May 6 2021, 7:12 PM
zoecarver updated this revision to Diff 343716.May 7 2021, 10:33 AM
  • Implement caching.
zoecarver updated this revision to Diff 343718.May 7 2021, 10:37 AM
  • Uncomment the static_assert.
cjdb requested changes to this revision.May 7 2021, 11:06 AM
cjdb added inline comments.
libcxx/include/__ranges/drop_view.h
45

Caching should only be available for forward ranges (it's a logic error to cache for input ranges, and also not to spec). Also, please make this [[no_unique_address]].

This revision now requires changes to proceed.May 7 2021, 11:06 AM
zoecarver updated this revision to Diff 343746.May 7 2021, 1:11 PM
  • Move size into a helper function.
ldionne requested changes to this revision.May 7 2021, 1:20 PM

Overall LGTM, left some comments and we just spoke offline too, so you know what else I want. Thanks a lot for working on this, I think this is a huge milestone!!

libcxx/include/__ranges/drop_view.h
36

This should eventually be lifted to a common header because I believe many views are going to depend on this exposition only concept.

48

The combination of = default on this constructor and default member initializers is IMO somewhat misleading. When I see = default, I generally think "oh, the constructor default constructs everything". But this is not the case here.

I think I would instead drop default-member-initializers and explicitly construct the members in the two constructors.

(Yes, I know default member initializers is the way the Standard exposts the class, but they don't have iterator caching).

Edit:

Actually coming back to this, I don't understand why we cache begin(__base) here in the constructor. Shouldn't we only cache it in begin()?

62

I think it would be more natural to use

if (!input_or_output_iterator<iterator_t<_View>>) {
 // cache here
}
65

Is this intended? else {}

If not... there's something funky here if your tests are passing! If so, I would reorganize to avoid this unusual construct.

libcxx/test/std/ranges/range.adaptors/range.drop/range.drop.view.pass.cpp
90

Add a comment // test CTAD

This revision now requires changes to proceed.May 7 2021, 1:20 PM
tcanens added a subscriber: tcanens.May 7 2021, 3:41 PM
tcanens added inline comments.
libcxx/include/__ranges/drop_view.h
45

There's no requirement that ranges::begin on a default-constructed view is even well-defined (see: ref_view).

Additionally, when a drop_view is copied, the cache must be invalidated in the copy.

tcanens added inline comments.May 7 2021, 4:06 PM
libcxx/include/__ranges/drop_view.h
45

...and when a drop_view is moved-from, the cache must be invalidated in the original.

zoecarver updated this revision to Diff 343778.May 7 2021, 4:11 PM
zoecarver marked 4 inline comments as done.

Apply some of the comments.

I still need to:
-> Add a test for move-only input-iterator.
-> Expand the const tests.
-> Add tests for all_t CTAD.

tcanens added inline comments.May 8 2021, 5:01 AM
libcxx/include/__ranges/drop_view.h
57

I'd put __count before __base - see https://lists.isocpp.org/lib/2020/09/17540.php.

cjdb added inline comments.May 8 2021, 12:10 PM
libcxx/include/__ranges/drop_view.h
42

__cache_base is a bit too general a name.

45

@tcanens is this a non-propagating cache?

tcanens added inline comments.May 8 2021, 12:32 PM
libcxx/include/__ranges/drop_view.h
45

Yep. This is the original use case of non-propagating-cache in range-v3.

zoecarver added inline comments.May 10 2021, 9:10 AM
libcxx/include/__ranges/drop_view.h
45

Where in the standard does it say this is a non-propagating cache? Or is that what your paper does?

62

Unfortunately, I just realized that all iterators model input or output iterator, so I think we'll have to stick with forward_range.

cjdb added inline comments.
libcxx/include/__ranges/drop_view.h
45

The standard is very underspecified in what kind of cache is necessary here. I just checked, and range-v3 and cmcstl2 disagree on what kind of cache is necessary: range-v3 uses a non-propagating cache; cmcstl2 switches between a non-propagating cache and a simple cache, depending on whether or not we have a forwarding-range (which I think is now borrowed_range).
I'm inclined to support Tim's opinion here, because it's simpler, and doesn't need to introduce a __cached_position type that's dependent on __non_propagating_cache. Any opinions @CaseyCarter?

tcanens added inline comments.May 10 2021, 9:46 AM
libcxx/include/__ranges/drop_view.h
45

Where in the standard does it say this is a non-propagating cache? Or is that what your paper does?

It falls out of the fact that nothing in the standard allows "take a drop_view, call begin() on it, copy it, and call begin() on the copy" to not work.

zoecarver updated this revision to Diff 344559.May 11 2021, 2:05 PM

Add tests for views::all ctad.

zoecarver planned changes to this revision.May 20 2021, 12:07 PM

I need to update this to use semiregular box.

cjdb requested changes to this revision.Thu, Jun 10, 8:59 AM

Please update according to the recent changes made by P2325.