This is an archive of the discontinued LLVM Phabricator instance.

[libcxx][ranges] Add ranges::take_view.
ClosedPublic

Authored by zoecarver on Jul 21 2021, 4:33 PM.

Details

Reviewers
ldionne
cjdb
Group Reviewers
Restricted Project
Commits
rG0f4b41e03853: [libcxx][ranges] Add ranges::take_view.

Diff Detail

Event Timeline

zoecarver created this revision.Jul 21 2021, 4:33 PM
zoecarver requested review of this revision.Jul 21 2021, 4:33 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 21 2021, 4:33 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
zoecarver updated this revision to Diff 360641.Jul 21 2021, 4:42 PM

Go through https://libcxx.llvm.org/Contributing.html and fix what needs to be fixed.

Added proper "enable_borrowed_range".

zoecarver added inline comments.Jul 21 2021, 4:45 PM
libcxx/include/__iterator/counted_iterator.h
58

Review note: this file and the one below (common_view.h) have/will be updated with the changes shown here in other patches.

libcxx/include/__ranges/take_view.h
54

Chris, before you ask, I did try to factor this out into a static member function, but ran into a couple of issues (first, I had to inline size, second, it didn't work well for move only views).

😉

136

We move __end in the other constructor, why not here too? We don't use it later.

cjdb added inline comments.Jul 21 2021, 5:11 PM
libcxx/include/__ranges/take_view.h
19

Please replace with the specific algorithms you use.

44

Can be const.

54

Now that you've brought it to my attention... ;)

  • why did you need to inline size?
  • why doesn't it work well for move-only views?
111

Hmm... I just realised that if we're going to be using algorithms here, we should definitely be using ranges overloads. You won't be stepping on my turf if you implement the min/max family.

136

If it's passed by value we should be allowed to do so.

160

Oooooh nice, all_t.

ldionne requested changes to this revision.Jul 22 2021, 1:56 PM

I have not looked at the tests yet.

libcxx/include/__ranges/take_view.h
35

[[no_unique_address]]

41

requires default_initializable<_View>, and also _LIBCPP_HIDE_FROM_ABI.

74

using _Difference = range_difference_t<const _View>;? (applies above)

111

It seems conforming to me to use std::min here, no?

127

[[no_unique_address]]

133

_LIBCPP_HIDE_FROM_ABI

136

I say we should move it. I don't see a reason either.

155

You could use __rhs.__end_ here, which would avoid making a copy of the sentinel (base() makes a copy). Same applies above.

This revision now requires changes to proceed.Jul 22 2021, 1:56 PM
zoecarver marked 5 inline comments as done.Jul 22 2021, 1:56 PM
zoecarver added a subscriber: tcanens.
zoecarver added inline comments.
libcxx/include/__ranges/take_view.h
44

__count? I don't really see how that benefits us... it's passed by value...

54

Well, because we really want a static function that we pass __base_ to, otherwise that kind of defeats the purpose of deducing _View vs const _View.

If we're passing __base_ we both lose size and have to move it into the function and then out of the function when we put it back into the member. That seems like an unreasonable cost.

111

I think that's a bit out of scope for my current timeline. Is there an observable difference?

136

Why did the standard do it below and not here, though? Was that just an oversight? CC @tcanens

zoecarver marked 8 inline comments as done.Jul 22 2021, 2:06 PM
zoecarver added inline comments.
libcxx/include/__ranges/take_view.h
155

That really should be inlined. But fair enough. I'm going to make it public so I can do that for lhs too.

zoecarver updated this revision to Diff 360966.Jul 22 2021, 2:11 PM
zoecarver marked an inline comment as done.

Apply review comments.

ldionne accepted this revision.Jul 26 2021, 11:21 AM

LGTM mod comments and passing CI!

libcxx/include/__ranges/take_view.h
54

I think this would work:

template <class _Self>
_LIBCPP_HIDE_FROM_ABI
static constexpr auto __begin(_Self& __self) {
  using _MaybeConstView = _If<is_const_v<_Self>, _View const, _View>;
  if constexpr (sized_range< _MaybeConstView >) {
        if constexpr (random_access_range<_MaybeConstView>) {
          return ranges::begin(__self.__base_);
        } else {
          using _DifferenceT = range_difference_t<_MaybeConstView>;
          auto __size = __self.size();
          return counted_iterator{ranges::begin(__self.__base_), static_cast<_DifferenceT>(__size)};
        }
      } else {
        return counted_iterator{ranges::begin(__self.__base_), __self.__count_};
      }
}

_LIBCPP_HIDE_FROM_ABI
constexpr auto begin() requires (!__simple_view<_View>) {
  return take_view::__begin(*this);
}

// etc...

I'm still not sure whether I like that better than matching the spec 1:1. I'll leave it to you to decide @zoecarver .

77

In all those counted_iterator constructions, the spec uses direct-initialization instead of list-initialization. I don't think this ever matters because there can't be a narrowing conversion from _DifferenceT to the argument of counted_iterator::counted_iterator (both types should always be exactly iter_difference_t<iterator_t<_View>>), but we might as well follow the spec.

155

Depending on what the _View's copy constructor does, it might not be possible to inline it, I think. I would definitely not rely on that, at least.

libcxx/test/std/ranges/range.adaptors/range.take/base.pass.cpp
24

Can you make this more minimal? For example, I think you could provide only begin() const as a member function.

Also, since you're using it in a bunch of places, perhaps you could put it in a types.h helper header in this directory? That would be a simple way to remove some duplication.

libcxx/test/std/ranges/range.adaptors/range.take/begin.pass.cpp
97

Could you add a one-liner to each test to make it very obvious which branch of the if constexpr you're testing? Something as simple as:

// sized_range && random_access
133–143

I'm not sure what coverage this is adding. Consider removing if it doesn't add anything.

libcxx/test/std/ranges/range.adaptors/range.take/ctad.compile.pass.cpp
18

#include <concepts>

46

Alternatively, you could leave at file scope. Whatever you prefer.

libcxx/test/std/ranges/range.adaptors/range.take/ctor.pass.cpp
64

You never actually default-construct an object here. Could you do that? Ideally, you'd then test that base() has been default-initialized, and that the size() is 0 (which you could do best by creating a view that has non-zero size when default-constructed).

libcxx/test/std/ranges/range.adaptors/range.take/end.pass.cpp
97

Same comment as for begin() w.r.t. which if branch we're testing.

libcxx/test/std/ranges/range.adaptors/range.take/size.pass.cpp
113

You want to test this version (N == size-of-the-range) for const too.

118

You want to test this version (N > size-of-the-range) for non-const too.

This revision is now accepted and ready to land.Jul 26 2021, 11:21 AM
zoecarver updated this revision to Diff 361769.Jul 26 2021, 1:13 PM

Apply remaining review comments.

Note: I'm rebasing on main instead of counted_iterator so the CI passes. It's just easier this way.

zoecarver marked 10 inline comments as done and 2 inline comments as done.Jul 26 2021, 1:28 PM
zoecarver updated this revision to Diff 361783.Jul 26 2021, 1:44 PM

Actually push the change with the addressed feedback :P

zoecarver updated this revision to Diff 361838.Jul 26 2021, 3:47 PM

Move Copyable and ContiguousView into the local header. They were conflicting with types that transform_view uses. I'll move them into test_ranges.h in a later commit.

cjdb requested changes to this revision.Jul 26 2021, 6:49 PM

Please add range concept conformance tests before merging.

libcxx/include/__ranges/take_view.h
44

If we start by making everything const and then remove it for only the objects we intend to modify, we're better-documenting our intention. Put another way: we shouldn't need a reason to provide const: we should have a good reason to omit const.

54

@ldionne's got what I had in mind. I like it because it keeps the complex logic in one place and makes sure that any bugs only have one source of manifestation.

111

In general: yes, there is an observable difference. std::min requires that its parameters meet Cpp17LessThanComparable, whereas std::ranges::min requires that its parameters model totally_ordered_with. Since we're comparing integers, I don't think it's going to be an observable difference.

Could you please at least add a FIXME so I remember to clean it up one day?

libcxx/test/support/test_iterators.h
701

Why is this being deleted?

This revision now requires changes to proceed.Jul 26 2021, 6:49 PM
zoecarver marked an inline comment as done.Jul 27 2021, 11:03 AM
zoecarver added inline comments.
libcxx/test/support/test_iterators.h
701

These archetypes are meant to represent the minimum requirements of an iterator. C++20 input iterators are not required to be default constructible, therefore our C++20 input iterator archetype should not be default constructible.

Quuxplusone added inline comments.
libcxx/test/support/test_iterators.h
701

@zoecarver: FWIW, your archetype philosophy makes sense to me; but I wish this change to massively shared test code were done in a separate patch, not bundled in with this counted_iterator feature. (IIUC, all our existing tests are completely apathetic to this change: this change is neither required, nor harmful, to any existing test.)

libcxx/test/support/test_range.h
58

woot! :) but also, please land this as a separate NFC commit (and you can just go ahead and do that).
Bonus points if you clean up the > > on lines 26, 35, 42, 51, and the spelling mistake on line 17, while you're at it.

zoecarver updated this revision to Diff 362212.Jul 27 2021, 3:54 PM
zoecarver marked 4 inline comments as done.

Add a comment with a TODO for the ranges::min.

Reset the changes to test_range.h.

Rebase on main.

zoecarver updated this revision to Diff 362215.Jul 27 2021, 4:07 PM

Add UNSUPPORTED: libcpp-has-no-incomplete-ranges. Rebase. Add range conformance tests.

This revision was not accepted when it landed; it landed in state Needs Review.Jul 28 2021, 12:14 PM
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.