This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `indirectly_copyable{,_storable}`.
ClosedPublic

Authored by var-const on Jan 27 2022, 9:56 PM.

Details

Summary

Also refactor tests for indirectly_movable{,_storable}.

Diff Detail

Event Timeline

var-const requested review of this revision.Jan 27 2022, 9:56 PM
var-const created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptJan 27 2022, 9:56 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const updated this revision to Diff 403885.Jan 27 2022, 9:58 PM

Add a link to the patch to the status page.

var-const added inline comments.Jan 27 2022, 10:03 PM
libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable.compile.pass.cpp
19–20

It seems to be exactly the same as PointerTo<int>.

52

This line was redundant.

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable_storable.compile.pass.cpp
41

IIUC, the details about conversions are the only interesting things about this class -- it doesn't have to be move-only and doesn't relate to MoveOnly. It seems simpler to create a separate group of classes rather than attach it to the existing MoveOnly.

74–119

While I think I understand the original intention here, specializing basic_common_reference doesn't seem to have any effect on the test (the test passes as is without the specialization and would fail if there is a conversion between ValueType and ReferenceType regardless of the specialization).

Quuxplusone added a subscriber: Quuxplusone.

I have many nits on the tests, but there's nothing terribly awful in there. It's great that you're finishing up these loose ends! Thanks!

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.copy/indirectly_copyable.compile.pass.cpp
22–28

(1) From the placement, I wonder if MoveOnly() = default; was meant to say ~MoveOnly() = default;.
(2) Lines 23 and 25 are superfluous.
(3) We could use "test/support/MoveOnly.h" instead; is it worth it?

73

I'm confused about this one. CopyOnly(CopyOnly&&) = delete;, so how is indirectly_writable<_Out, iter_value_t<_In>&&> satisfied?

81

I recommend replacing line 80 with

static_assert( std::indirectly_copyable<PointerTo<int>, int*>);
static_assert(!std::indirectly_copyable<PointerTo<const int>, const int*>);

for better symmetry with lines 78–79. (If symmetry with those lines wasn't the point, then I don't see the point.)

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.copy/indirectly_copyable.subsumption.compile.pass.cpp
17

This line can be removed AFAICT.

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.copy/indirectly_copyable_storable.compile.pass.cpp
38–42

The second template param is used on line 69 below. For simplicity, I'd rather see template<class T> struct PointerTo here, and a completely separate (non-template) struct ProxyPointer on line 69.
I'm also currently puzzled by the name "proxy pointer" and the comment on lines 67–68: how is this like a proxy? But I think that will become clearer as you simplify. I believe both Foo and FooConvertible can become members of struct ProxyPointer, which will encapsulate them a bit better and perhaps also eliminate the need for the forward declaration of FooConvertible.

74–124

I think these 50 lines are pointless; none of these types are even movable, so of course pointers to them won't be indirectly_copyable.

137–138

Same comment here as above: PointerTo should be a template of one parameter, ProxyPointerBar should be a struct not an alias, and Bar/AssignableToBar should be members of ProxyPointerBar.

141

This should be a member of NotConstructibleFromRefIn.

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable.compile.pass.cpp
24–26

The comment on line 39 is wrong (but also unnecessary).
Line 41 is now redundant with line 37. I think all you really want is to replace lines 35–41 with

static_assert( std::indirectly_movable<int*, int*>);
static_assert(!std::indirectly_movable<int*, const int*>);
static_assert( std::indirectly_movable<const int*, int*>);
static_assert(!std::indirectly_movable<const int*, const int*>);

with no comments necessary at all.

28

You certainly can move from an array (element), so this comment is wrong.
My intuition says that the real hurdle here is that an array type is not an iterator type, so it's not indirectly-anything — it has no iter_value_t. (But then, an optional isn't an iterator either, and I think optionals are indirectly-fooable, so my intuitive explanation may be wrong.)

37–38

FWIW, this test strikes me as redundant. There's nothing special about empty types in this context; changing the distracting name, this is really just testing that struct A {}; is movable. Which of course it is; there's nothing special about class types as opposed to int in this context, either.

But, it might be nice to see ~10 lines of sanity tests for e.g. indirectly_movable<void*, void*>, indirectly_movable<int*, void*>, indirectly_movable<int(), int()>, indirectly_movable<int*, int()>, indirectly_movable<void, void>, indirectly_movable<int*, void>... just to prove they don't explode.

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable_storable.compile.pass.cpp
134

Could you use AssignableFromAnything* here instead of AssignableFromAnythingProxy? I don't see that AssignableFromAnythingProxy's struct-ness matters to this test.
Ditto line 167.

var-const updated this revision to Diff 404210.Jan 28 2022, 6:49 PM
var-const marked 9 inline comments as done.

Address review feedback.

Very useful comments, thanks!

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.copy/indirectly_copyable.compile.pass.cpp
22–28
  1. Hmm, semantically it makes sense to define the default constructor (move/copy constructor inhibit the compiler-generated default constructor), but not the default destructor (which is pretty much always generated).
  1. True -- I guess the original intent was to be more explicit. I don't have a strong preference.
  1. I think so; it also sidesteps issues 1 and 2.
73

indirectly_copyable only requires indirectly_writable<_Out, iter_reference_t<_In>>. Maybe you're thinking of indirectly_copyable_storable, which does require indirectly_writable<_Out, iter_value_t<_In>&&> ?

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.copy/indirectly_copyable_storable.compile.pass.cpp
38–42

Done (it looks like the forward declaration is still necessary, unfortunately).

Regarding the name -- the idea was that it's a pointer that returns a proxy of the type it points to, rather than the type itself (similar to how vector<bool>'s reference type isn't the same as value_type&). So it's more like "a pointer that returns a proxy" rather than "a pointer that itself is a proxy".

74–124

Actually, while none of these types are copyable, DeletedNonconstCopyCtor and DeletedNonconstCopyAssignment _are_ movable. Do you think this is an issue with movable?

141

Done. Whether basic_common_reference is specialized still has no effect on the test.

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable.compile.pass.cpp
24–26

Thanks for catching this! I'd still keep the comment, though -- mostly because it helps me split the tests into logical groups visually.

28

I'm actually not sure about the behavior here.

Intuitively, it would seem to me that:

  • indirectly_movable<int[2], int*> _should_ work due to array-to-pointer decay. After all, just like you said, you can move from an array -- int *ptr, arr[2]; *ptr = std::move(*arr); is certainly valid;
  • in either case, I would expect this to be commutative -- i.e., indirectly_movable<int*, int[2]> and indirectly_movable<int[2], int*> should either both be true or both be false.

My intuition says that the real hurdle here is that an array type is not an iterator type, so it's not indirectly-anything — it has no iter_value_t.

iter_value_t does in fact work on array types -- static_assert(is_same_v<iter_value_t<int[2]>, int>); is successful with both libc++ and libstdc++, at least.

Digging a little into this, it appears that for indirectly_movable<int[2], int*> is false because it is indirectly writable but not indirectly readable. Reducing as much as possible, it boils down to:

template<class In>
concept simplified_indirectly_readable =
  requires(const In i) {
    { *i } -> same_as<iter_reference_t<In>>;
  };

static_assert( simplified_indirectly_readable<int*>);
static_assert(!simplified_indirectly_readable<int[2]>);

(there's also { ranges::iter_move(i) } -> same_as<iter_rvalue_reference_t<In>>; failing for the same reason, so it can be ignored)

The reason this check:

{ *i } -> same_as<iter_reference_t<In>>

works for pointers but fails for arrays comes down to template argument deduction. The const In i argument decays from array to pointer as expected; however:

  • when In is a pointer, the const in the signature "attaches" to the pointer itself, so that it is a const pointer to a non-const object (int* const);
  • when In is an array, the const in the signature "attaches" to the type referred to, so that it's a const array that decays to a non-const pointer to a const object (const int*).

For a quick illustration:

template <class T>
void Foo(const T x) {
  static_assert(is_same_v<decltype(x), const int*>);
}

template <class T>
void Bar(const T x) {
  static_assert(is_same_v<decltype(x), int* const>);
}

void Test() {
  int arr[2];
  Foo<int[2]>(arr);
  
  int* ptr = nullptr;
  Bar<int*>(ptr);
}

(link)

It seems to me that this is pretty subtle and I wonder whether this is intentional -- basically, whether arrays are intentionally not indirectly_readable, or it's just a by-product of the implementation. If arrays are intentionally not_readable, it seems like they should be excluded in a more obvious way.

Let me know what you think (and if you see any errors in my reasoning).

37–38

Agreed on both.

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable_storable.compile.pass.cpp
134

Right -- I got too caught up in renamings and missed that it could just be a pointer. Thanks!

var-const updated this revision to Diff 404218.Jan 28 2022, 7:47 PM

Update all iterator_concept_conformance tests.

Note: I've also updated all the iterator_concept_conformance tests (under the assumption that for iterators, indirectly_copyable{,_storable} always behaves the same as indirectly_movable{,_storable}.

Note: I've also updated all the iterator_concept_conformance tests (under the assumption that for iterators, indirectly_copyable{,_storable} always behaves the same as indirectly_movable{,_storable}.

I have a patch locally (but apparently never got around to submitting it for review) that simply removes all of the "detail" concepts from every iterator_concept_conformance.compile.pass.cpp, leaving only the iterator concepts like forward_iterator and bidirectional_iterator (and only the relevant ones of those, even). I don't object to your expanding those tests, but I certainly wasn't going to ask you to do it.

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable.compile.pass.cpp
37–38

Foo is now unused (right?)

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable_storable.compile.pass.cpp
26–36

In the time it takes to explain that this check is non-exhaustive, you could have made it exhaustive. :)

static_assert( std::indirectly_movable_storable<int*, int*>);
static_assert( std::indirectly_movable_storable<const int*, int *>);
static_assert(!std::indirectly_movable_storable<int*, const int*>);
static_assert(!std::indirectly_movable_storable<const int*, const int *>);
static_assert( std::indirectly_movable_storable<int*, int[2]>);
static_assert(!std::indirectly_movable_storable<int[2], int*>);  // right?
58

Here I think you could just test !std::indirectly_movable_storable<FooConvertible*, Foo*>, couldn't you? You've got the same weird pattern on lines 47-48 as on line 82 below, but even if you change it to Foo operator*() const, I don't see why you need ProxyPointerFoo's value_type to be different from its actual decay_t<decltype(*it)>. This test seems just to be testing that if you have In and Out where *Out = *In isn't well-formed, then indirectly_movable_storable is false.

86

ProxyPointerBar seems like the wrong name for this type. It's basically just a PointerTo<Bar> — you dereference it, you get a reference to an existing Bar object — but it's just got the "wrong" value_type.
To make this more like a proxy iterator (like vector<bool>::iterator, for example), you should declare Bar operator*() const; without the ampersand. If you do that, does the test still pass? Does it still test whatever-is-being-tested-here?
(Strongly consider renaming s/Bar/Reference/ and s/AssignableToBar/ValueType/.)

101–104

Move this definition up to line 92, to eliminate the forward reference.

106–107

Same comment here as on line 82: it's highly unusual to have an iterator type whose operator* returns an X& but whose value type is Y. To make this a proxy iterator, change ReferenceType& to just ReferenceType. (And I'd drop the Type, for consistency with the name of the iterator trait reference.)

124

Let's add above this line

static_assert( std::indirectly_movable_storable<int*, AssignableFromAnything*>);

just to prove it's testing what we think it's testing.

var-const marked an inline comment as not done.Jan 29 2022, 1:33 PM
var-const added inline comments.
libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable.compile.pass.cpp
28

@Quuxplusone Any thoughts on this?

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable.compile.pass.cpp
28

@Quuxplusone Any thoughts on this?

Not particularly. As you say, "when In is a pointer, the const in the signature "attaches" to the pointer itself [...] when In is an array, the const in the signature "attaches" to the type referred to". It would probably be a bit nicer if the requires-expression's parameter list in https://eel.is/c++draft/iterator.concept.readable took const In& instead of const In; but that wouldn't change the outcome.

Anyway, the comment "cannot move from an array" is still wrong. Personally I'd solve the issue by eliminating all these comments; but if you really want keep the comment, I still think "an array is not an iterator" is a reasonable explanation.

var-const marked an inline comment as not done.Feb 1 2022, 1:36 AM

Note: I've also updated all the iterator_concept_conformance tests (under the assumption that for iterators, indirectly_copyable{,_storable} always behaves the same as indirectly_movable{,_storable}.

I have a patch locally (but apparently never got around to submitting it for review) that simply removes all of the "detail" concepts from every iterator_concept_conformance.compile.pass.cpp, leaving only the iterator concepts like forward_iterator and bidirectional_iterator (and only the relevant ones of those, even). I don't object to your expanding those tests, but I certainly wasn't going to ask you to do it.

I see, thanks for the heads-up.

var-const marked 7 inline comments as done.Feb 1 2022, 1:49 AM
var-const added inline comments.
libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable.compile.pass.cpp
28

I mean I'm not sure indirectly_movable<int[2], int*> is actually supposed to be false. I'll start a thread on the LWG reflector.

Anyway, the comment "cannot move from an array" is still wrong. Personally I'd solve the issue by eliminating all these comments; but if you really want keep the comment, I still think "an array is not an iterator" is a reasonable explanation.

My intended meaning was "cannot indirectly-move from an array" (which is true because it's basically saying indirectly_movable<array_type, pointer> == false in natural language). I'm not sure that the problem is that an array is not an iterator -- at least iterator traits do consider it an iterator (due to decay). Removing the comment is tempting but feels like sidestepping the issue. All in all, I'd go with "Arrays are not considered indirectly movable-from".

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable_storable.compile.pass.cpp
26–36

Added these tests (but I still don't consider these exhaustive, exhaustive would be completely copying the tests for indirectly_movable).

124

Thanks!

var-const updated this revision to Diff 404856.Feb 1 2022, 2:32 AM
var-const marked 6 inline comments as done.

Address feedback

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable_storable.compile.pass.cpp
58

(this is a pre-existing test)
I think what's being tested here is that indirectly_movable_storable requires (omitting irrelevant part) indirectly_movable<In, Out> and indirectly_writable<Out, iter_value_t<In>>. indirectly_movable<In, Out, in turn, requires indirectly_writable<Out, iter_rvalue_reference<In>>; in the end, it boils down to:

indirectly_writable<Out, iter_value_t<In>> &&
indirectly_writable<Out, iter_rvalue_reference_t<In>>;

So this test tries to set up the situation where only one of these requirements is true. I don't think !std::indirectly_movable_storable<FooConvertible*, Foo*> covers the same case:

static_assert(!std::indirectly_writable<Foo*, std::iter_rvalue_reference_t<FooConvertible*>>); // False
static_assert( std::indirectly_writable<ProxyPointerFoo, std::iter_rvalue_reference_t<ProxyPointerFoo>>); // True
86

If you do that, does the test still pass?

No -- it's no longer indirectly_writable.

While I see your point about the ProxyPointer name, I think the fact that it has "wrong" value_type is crucial for the class (it's essentially the reason for its existence), and just PointerTo omits that. How about InconsistentIterator? (It's not really a pointer)

Strongly consider renaming s/Bar/Reference/ and s/AssignableToBar/ValueType/

The current names are supposed to convey that Bar is a completely uninteresting class on its own and AssignableToBar is a class that can be assigned to Bar. ValueType and Reference obscure that -- in fact, just looking at them, I'd expect that Reference is an alias for ValueType&. So I'd rather keep the current names.

106–107

I'd prefer to keep as is, at least for this patch (this is preexisting code).

You can fix the Apple-Clang CI failures by rebasing.
(Incidentally, I'm surprised that people don't rebase reflexively when reuploading a diff. I rebase like five times a day even when I'm not uploading. :D)

libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable_storable.compile.pass.cpp
86

The current names are supposed to convey that Bar is a completely uninteresting class on its own and AssignableToBar is a class that can be assigned to Bar.

But those names aren't being used anywhere where that isn't already abundantly obvious (i.e., within 2 lines of the class definition). Contrariwise, the fact that some type is the ValueType of InconsistentIteratorBar, I think, is relevant information. Actually the presence of Bar in the name InconsistentIteratorBar is the thing that stands out right now: what is a Bar? There's no Bar in the global scope, no reason for any user to care about Bar. The only salient thing about Bar is that it's the value type of InconsistentIterator[Bar]... well, except that it's not. Which is why this test is weird. It's not a "proxy iterator", but it's also... well, what is it? If there's no sensible name for it, I'd just as soon name it struct A...

var-const updated this revision to Diff 404965.Feb 1 2022, 9:14 AM

Rebase on main.

var-const updated this revision to Diff 405071.Feb 1 2022, 12:54 PM
var-const marked an inline comment as done.
  • address feedback;
  • exhaustively check all the indirectly_writable requirements of indirectly_copyable_storable.
var-const added inline comments.Feb 1 2022, 12:57 PM
libcxx/test/std/iterators/iterator.requirements/alg.req.ind.move/indirectly_movable_storable.compile.pass.cpp
86

Ok, I decided to check these requirements exhaustively:

template<class _In, class _Out>
concept indirectly_copyable_storable =
  indirectly_writable<_Out, iter_value_t<_In>&> &&
  indirectly_writable<_Out, const iter_value_t<_In>&> &&
  indirectly_writable<_Out, iter_value_t<_In>&&> &&
  indirectly_writable<_Out, const iter_value_t<_In>&&> &&
  ...

This created 4 forms of InconsistentIteratorFoo and led me to rename them just to show the most interesting thing about them, like NoConstRvalueAssignment. Let me know what you think. I also applied your suggestion to use ValueType and ReferenceType as names.

ldionne accepted this revision as: Restricted Project.Feb 2 2022, 11:02 AM
ldionne added a subscriber: ldionne.

Trusting Arthur's review.

This revision is now accepted and ready to land.Feb 2 2022, 11:02 AM