This is an archive of the discontinued LLVM Phabricator instance.

[libcxx][ranges] Add contiguous_range.
ClosedPublic

Authored by zoecarver on Jun 14 2021, 1:09 PM.

Details

Reviewers
ldionne
Quuxplusone
cjdb
Group Reviewers
Restricted Project
Commits
rG34503987385b: [libcxx][ranges] Add contiguous_range.

Diff Detail

Event Timeline

zoecarver requested review of this revision.Jun 14 2021, 1:09 PM
zoecarver created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptJun 14 2021, 1:09 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
Quuxplusone requested changes to this revision.Jun 14 2021, 1:23 PM

LGTM % comments.

libcxx/test/std/containers/sequences/deque/range_concept_conformance.compile.pass.cpp
26

deque<T> is not a contiguous range. Add ! here and below.

libcxx/test/std/containers/sequences/vector.bool/range_concept_conformance.compile.pass.cpp
26

vector<bool> is not a contiguous range. Add ! here and below.

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp
15

contiguous_range

43–47

I was initially confused by the name, as this class has no data members... but then I saw: the trick is that X::data() member function has a return type that is different from std::add_pointer_t<ranges::range_reference_t<X>>.
I think it'd be worth replacing this test (or at augmenting it) with both of these:

struct WrongConstness {
    const int *begin() const;
    const int *end() const;
    int *data() const;
};
static_assert(std::ranges::random_access_range<WrongConstness>);
static_assert(!std::ranges::contiguous_range<WrongConstness>);

struct NotPtr {
    contiguous_iterator<const int*> begin() const;
    contiguous_iterator<const int*> end() const;
    contiguous_iterator<const int*> data() const;
};
static_assert(std::ranges::random_access_range<NotPtr>);
static_assert(!std::ranges::contiguous_range<NotPtr>);
libcxx/test/std/ranges/range.req/range.refinements/subsumption.compile.pass.cpp
28

Whitespace: Please indent requires by one level (here and throughout). E.g.

template<...>
  requires ...
bool foo() {
  return ...
}

It'd be nice to remove the [[nodiscard]]s while you're at it.

This revision now requires changes to proceed.Jun 14 2021, 1:23 PM
cjdb added inline comments.Jun 16 2021, 10:08 PM
libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp
43–47

I was initially confused by the name, as this class has no data members... but then I saw: the trick is that X::data() member function has a return type that is different from std::add_pointer_t<ranges::range_reference_t<X>>.

I propose renaming to BadDataMemberFunction.

We should also have a check for when a range can satisfy contiguous_range<R>, but not contiguous_range<R const>.

libcxx/test/std/ranges/range.req/range.refinements/subsumption.compile.pass.cpp
28

@ldionne left it up to me to decide how libc++ formats requires clauses, and I decided that they shouldn't be indented.

ldionne requested changes to this revision.Jun 21 2021, 9:03 AM

Can we also remove the TODO in ref_view::data() in this patch?

libcxx/include/__ranges/concepts.h
1

We're missing a few concepts in the synopsis in <ranges>. I think we're only missing random_access_range and contiguous_range -- can you update that part of the synopsis in this patch?

zoecarver marked 8 inline comments as done.Jun 23 2021, 5:22 PM
zoecarver added inline comments.
libcxx/include/__ranges/concepts.h
1

Hmm, the two I implemented... 🤔

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp
43–47

Thanks for the suggestions. Arthur, I added your first test only (with some modification). The NotPtr test doesn't work because contiguous_iterator has an element_type.

libcxx/test/std/ranges/range.req/range.refinements/subsumption.compile.pass.cpp
28

I'm going to match the existing format of this file. I would support a nfc commit that updated all the requires in this file.

zoecarver updated this revision to Diff 354118.Jun 23 2021, 5:22 PM
zoecarver marked 2 inline comments as done.

Apply review comments.

cjdb added inline comments.Jun 23 2021, 5:41 PM
libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp
43–47

This still isn't complete, because now we're missing a test case for when both contiguous_range<T> and contiguous_range<T const> are true, and one for when only contiguous_range<T const> is true.

libcxx/test/std/ranges/range.req/range.refinements/subsumption.compile.pass.cpp
28

Let's not take any action till Louis and I resolve our discussion.

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp
43–47

Arthur, I added your first test only (with some modification). The NotPtr test doesn't work because contiguous_iterator has an element_type.

Ah. My intent with NotPtr was that contiguous_range<NotPtr> would not be satisfied because NotPtr().data()'s return type is not std::same_as<std::add_pointer_t<ranges::range_reference_t<T>>>. However, I see now that the thing-we're-taking-the-return-type-of in contiguous_range is not NotPtr().data() but instead std::ranges::data(NotPtr()), which actually evaluates to std::to_address(NotPtr().begin()), not NotPtr().data(), in this case.

So then actually maybe it would be worthwhile to add a test like this:

struct WrongObjectness { // https://godbolt.org/z/M7fbvj7fE
    const int *begin() const;
    const int *end() const;
    void *data() const;
};
static_assert(std::ranges::contiguous_range<WrongObjectness>);

which verifies that if data() exists but is completely the wrong return type, then there's no problem at all. (Did I ever mention how overcomplicated Ranges is? :P)

ldionne accepted this revision.Jun 24 2021, 8:22 AM

Please resolve the concerns about testing raised by other reviewers, but apart from that, LGTM.

zoecarver updated this revision to Diff 354271.Jun 24 2021, 8:56 AM

Rebase. Update based on review.

Will be landed when CI is green.

libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp
43–47

when both contiguous_range<T> and contiguous_range<T const> are true,

That's test_range<contiguous_iterator>.

and one for when only contiguous_range<T const> is true.

Added.

43–47

So then actually maybe it would be worthwhile to add a test like this:

I considered adding a test like this. I don't see how it's really different than the const tests (in both cases it fails because the types are not the same). I think it would be hard to write an implementation that said "if this is the same return type with different constness, that's bad, but if it's a totally unrelated types, that's OK."

I suppose it wouldn't hurt to have a case where they both returned const pointers. I'll add a similar test but where the return type is const char *.

zoecarver marked 3 inline comments as done.Jun 24 2021, 8:57 AM
libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp
43–47

Wait, on this latest point I think I'm right and you're confused. My WrongObjectness test above is supposed to pass, not fail, even though the return type of data is not the same as the return type of begin — because it is so different that we wrap around and become a contiguous range again! (Try the godbolt link.)
If my WrongObjectness test did just fail, then it would be boring, I'd agree.

This revision was not accepted when it landed; it landed in state Needs Review.Jun 24 2021, 10:40 AM
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
zoecarver added inline comments.Jun 24 2021, 10:44 AM
libcxx/test/std/ranges/range.req/range.refinements/contiguous_range.compile.pass.cpp
43–47

Oh, interesting. I see (because ranges::data won't pick the data member function). Sorry I didn't see this comment until I landed the patch. I'll make a follow up commit.