Page MenuHomePhabricator

[libc++][ranges] Implement [special.mem.concepts].
ClosedPublic

Authored by var-const on Nov 29 2021, 5:30 PM.

Details

Summary

Implement the exposition-only concepts specified in
[special.mem.concepts]. These are all thin wrappers over other
concepts.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
libcxx/include/__memory/ranges_uninitialized_algorithms.h
33 ↗(On Diff #390531)

I recommend deleting this comment line.

libcxx/test/std/algorithms/specialized.algorithms/special.mem.concepts/special.mem.concepts.compile.pass.cpp
1 ↗(On Diff #390531)

Since this file tests non-standard (exposition-only, double-underscored) facilities, it should go in libcxx/test/libcxx/ instead of libcxx/test/std/.

38–42 ↗(On Diff #390531)

I believe this should be more like https://godbolt.org/z/PTce8axh5 :

bool is_nothrow_input_iterator(std::ranges::__nothrow_input_iterator auto) { return true; }
bool is_nothrow_input_iterator(std::input_iterator auto) { return false; }

int main() {
    assert(!is_nothrow_input_iterator(InputIt{}));
    assert(is_nothrow_input_iterator(NothrowInputIt{}));
}

Also please take the NothrowInputIt and InputIt from that godbolt; they're pretty minimal.

49–52 ↗(On Diff #390531)

For this one, I think it would be reasonable to test that __nothrow_sentinel_for subsumes sentinel_for, and vice versa. However, that might also be overkill. Untested code:

bool ntsf_subsumes_sf(__nothrow_sentinel_for<char*> auto) requires true { return true; }
bool ntsf_subsumes_sf(sentinel_for<char*> auto);

bool sf_subsumes_ntsf(sentinel_for<char*> auto) requires true { return true; }
bool sf_subsumes_ntsf(__nothrow_sentinel_for<char*> auto);

assert(ntsf_subsumes_sf("foo"));
assert(sf_subsumes_ntsf("foo"));
libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp
110–116 ↗(On Diff #390531)

Feel free to delete lines 110–116, and remove all the blank lines in this class body. That'll help shorten things up, without metaprogramming.
Ditto lines 89–97 and 69–77 and 50–58.

libcxx/test/support/test_iterators.h
629–661 ↗(On Diff #390531)

I strongly, strongly recommend not doing this. We need the test code to remain simple, so that when a test fails we can tell quickly why it failed (and whether it's a library bug, as opposed to a bug somewhere deep in someone's test-code metaprogramming).

Moot: you've also got some bogus default arguments on lines 645 and 651.

This revision now requires changes to proceed.Nov 29 2021, 6:00 PM

I only did a quick review since the review is already flagged for more work to be done.

libcxx/test/std/algorithms/specialized.algorithms/special.mem.concepts/special.mem.concepts.compile.pass.cpp
13 ↗(On Diff #390533)

In general we use one test per concept / function overload. Can you split this test?

Please split out the test-metaprogramming-refactoring stuff into a separate PR, or abandon it.

I suggest we split it into a separate review, but I'd like us to have that discussion -- I like the composition-of-archetypes approach and IMO it does make several things much easier to understand. It could also lead to greatly reduced duplication in the test suite.

libcxx/include/__memory/ranges_uninitialized_algorithms.h
33 ↗(On Diff #390531)

So this comment actually comes from a discussion Costa and I had where we were wondering what this is_lvalue_reference_v<iter_reference_t<_Ip>> && same_as<remove_cvref_t<iter_reference_t<_Ip>>, iter_value_t<_Ip>> business was. We came to the common understanding that they were trying to prevent proxy iterators.

Does that make sense to you? If so, I think the comment is useful cause it was not entirely obvious to us at first.

libcxx/test/support/test_iterators.h
629–661 ↗(On Diff #390531)

When Costa showed me this, I actually quite liked it. I thought it was a nice and straightforward way to build archetypes while expressing what they represent concisely, which we have sometimes struggled to do. FWIW, I would probably have suggested writing archetypes that way from the start if I had thought about it.

var-const updated this revision to Diff 390827.Nov 30 2021, 2:49 PM
var-const marked 2 inline comments as done.

Address feedback.

libcxx/include/__memory/ranges_uninitialized_algorithms.h
28 ↗(On Diff #390531)

Right, I should have written a comment about this. The intention is for this file to contain algorithms described in [specialized.algorithms](http://eel.is/c++draft/specialized.algorithms). The concepts are exposition-only and specific to these algorithms, which is why I didn't want to create a dedicated file for them. Please let me know if you would still prefer to move them to __memory/concepts.h or __memory/special_mem_concepts.h.

33 ↗(On Diff #390531)

What's the rationale for deleting this comment? If you feel it is incorrect or incomplete, I'd rather improve wording than delete it altogether. It took me some time to figure out the meaning of the additional constraints which I hoped this comment could save for somebody else.

libcxx/test/std/algorithms/specialized.algorithms/special.mem.concepts/special.mem.concepts.compile.pass.cpp
13 ↗(On Diff #390533)

Done. It does lead to some duplication, though.

1 ↗(On Diff #390531)

Done, thanks!

38–42 ↗(On Diff #390531)

What's the advantage of using these functions? They add a layer of abstraction and, AFAICT, make this a runtime test rather than a compile-time test. Also, why define a custom InputIt when test_iterators.h already contains suitable classes?

49–52 ↗(On Diff #390531)

Honestly, it seems to me like it's a little overkill. The Standard specifies nothrow-sentinel-for to be essentially an alias for sentinel_for, and it doesn't really make sense to implement it any other way.

libcxx/test/support/test_iterators.h
629–661 ↗(On Diff #390531)

I removed this change from the patch. I'll create a separate patch just for this refactoring and we can continue the discussion there.

My primary motivation was to be able to write code that is reasonably close to the way I would describe the problem in natural language. For example, I want to make sure that a move-only, incrementable, dereferenceable class satisfies the input iterator concept -- this is reflected quite closely through a definition like struct InputIterator : MoveOnly, Incremental<InputIterator>, Readable {.

var-const marked an inline comment as done.Nov 30 2021, 2:50 PM
var-const added inline comments.
libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp
110–116 ↗(On Diff #390531)

Done.

var-const edited the summary of this revision. (Show Details)Nov 30 2021, 3:45 PM

LGTM mod three extremely nitty style nits — and ideally renaming to __memory/concepts.h, unless @ldionne disagrees, in which case OK.

IIUC your changes to input_iterator.compile.pass.cpp are now entirely NFC-cleanup and can be committed separately from the functional part. (No additional Phab review needed AFAIC; I'd say just land it in its own commit.)

libcxx/include/__memory/ranges_uninitialized_algorithms.h
28 ↗(On Diff #390531)

Ah, the picture is becoming clearer. Right now std::uninitialized_default_construct is defined in <__memory/uninitialized_algorithms.h>. You're planning to define the new std::ranges::uninitialized_default_construct in <__memory/ranges_uninitialized_algorithms.h> ?

And likewise e.g. std::ranges::copy will be defined in <__algorithm/ranges_copy.h>, and so on?

If that's the direction @ldionne prefers, then I'm also okay with it. (Like a year ago, I recall its being unclear whether we were going to make ranges::copy live alongside copy, etc., and I don't know that a decision was ever made, really. I think the outlined direction makes sense; its only downside is that it will lead to a ton of files named __algorithm/ranges_*.h.)

That said, I'm still weakly in favor of renaming this file to __memory/concepts.h. If one day we split up __memory/ranges_uninitialized_algorithms.h into __memory/ranges_uninitialized_copy.h, __memory/ranges_uninitialized_default_construct.h, etc. (which I estimate as fairly likely), it'll be easier if we have the shared __memory/concepts.h part already split out.

33 ↗(On Diff #390531)

Mainly the comment line is just confusing because it's so terse: we could rewrite it to __nothrow_input_iterator accepts input iterators that aren't proxy iterators, but I'm not sure that's literally true.

I can certainly design something that I'd call a "proxy iterator" that happens to return T& from its operator* — like, maybe it's like istream_iterator and stashes the referred-to thingie inside itself.
In fact, __nothrow_input_iterator<std::istream_iterator<int>> == true today, right?

I would say that this restriction comes from the fact that we're going to be calling std::addressof(*it), so *it needs to be an lvalue: prvalues and xvalues can't be passed to addressof.
But the most immediate rationale is simply "because we copy-pasted this line directly from the Standard." I don't think we need to insert our own speculations. Maybe turn it into a commit-message comment? :)

libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_iterator.compile.pass.cpp
21

Naming nit: ForwardProxyIterator (or perhaps ProxyForwardIterator but I like that worse).
Ditto throughout.

26–28

Another trivial nit here: I'd delete blank line 26 and swap the order of lines 25 and 27.

libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_range.compile.pass.cpp
21

...and this is why test_range sucks. ;) But OK for now. I have a long-self-assigned TODO to clean up some of this stuff.

ldionne requested changes to this revision.Dec 1 2021, 8:00 AM
ldionne added a subscriber: tcanens.

Mostly LGTM but I do have a few questions.

libcxx/include/__memory/ranges_uninitialized_algorithms.h
28 ↗(On Diff #390531)

I don't think we'll want to put ranges::copy in the same header as std::copy, because those have different sets of dependencies (namely ranges::copy needs concepts, while std::copy doesn't).

Regarding putting this in __memory/concepts.h so that it's already split out if we end up with separate headers for the various uninitialized memory algorithms, I'm neutral. I don't know whether we'll end up with separate headers for those, so I think it's reasonable to either do it right away or to wait until it's needed. I'm fine with either, the cost is minimal.

33 ↗(On Diff #390531)

FWIW my impression is that those requirements were there so that we know there aren't other potentially throwing operations when one does iter_reference_t<Iterator> ref = *it, since that would kind of circumvent the whole point of the concept describing an iterator that doesn't throw. If for example initializing iter_reference_t<Iterator> did throw, then you'd end up with a potentially throwing statement in a place where the user probably never expected one, since the concept is __nothrow_input_iterator. So my understanding was that when they spec'd it out, they said "let's prevent any subtlety from happening by requiring that these __nothrow_iput_iterators return lvalue references, nothing fancier.

If the rationale is really just the syntactical requirement of doing std::addressof(*it), then honestly this concept is incredibly mis-named.

@tcanens Do you know why the following requirements are added to the concept:

is_lvalue_reference_v<iter_reference_t<_Ip>> &&
same_as<remove_cvref_t<iter_reference_t<_Ip>>, iter_value_t<_Ip>>

Whatever the answer is, I think it would be useful to record that in a comment, given the discussion we're having right now.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp
26 ↗(On Diff #390827)

Why are we removing those here?

This revision now requires changes to proceed.Dec 1 2021, 8:00 AM
Quuxplusone added inline comments.Dec 1 2021, 8:10 AM
libcxx/test/std/algorithms/specialized.algorithms/special.mem.concepts/special.mem.concepts.compile.pass.cpp
38–42 ↗(On Diff #390531)

Overloading like this is the pattern for testing subsumption relationships. The Standard says that If you have an overload set where one overload is constrained on __nothrow_input_iterator and another is constrained only on input_iterator, they won't be ambiguous overloads. So in general, when a subsumption relationship is mandated, we ought to have a test following this pattern somewhere.

However, in writing this comment, I realized that the Stupid C++ Trick I was thinking this enabled, isn't even legal. I was thinking that a sufficiently evil user could write https://godbolt.org/z/E4WT434xa

struct NotDC {
    NotDC(int) {}
    void uninitialized_default_construct(std::ranges::forward_range auto&& r) {}
};
int main() {
    NotDC a[3] = {1, 2, 3};
    using std::ranges::uninitialized_default_construct;
    uninitialized_default_construct(a);
}

But in fact subsumption is completely irrelevant to that code. It won't work because std::ranges::uninitialized_default_construct is a niebloid and so there is no overload set here at all. Conclusion: the subsumption relationship is mandated, but I no longer think that any user could possibly observe it, so we probably don't need to test it.

Quuxplusone added inline comments.Dec 1 2021, 8:12 AM
libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp
26 ↗(On Diff #390827)

This file had much more refactoring in the first revision, and then I said "let's split out all the controversial refactoring into a new PR." This is just what was left over. IMO this file should be landed in its own separate commit, and that could be done right now today AFAIC.

jloser added a subscriber: jloser.Dec 1 2021, 8:25 AM
jloser added inline comments.
libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_sentinel_for.compile.pass.cpp
22

Is this include needed? Same with "test_range.h", etc.

ldionne added inline comments.Dec 1 2021, 8:25 AM
libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp
26 ↗(On Diff #390827)

I think it would make sense to split this in a separate diff and explain why we're removing those. It's probably a one liner to explain it, but I'd like it on record.

cjdb requested changes to this revision.Dec 1 2021, 8:32 AM
cjdb added a subscriber: cjdb.

Very close to LGTM, thanks for working on this! I'd like to see the concepts in a descriptively named file before continuing.

libcxx/include/__memory/ranges_uninitialized_algorithms.h
1 ↗(On Diff #390827)

Would you mind renaming this file to uninitialized_algo_concepts.h or similar please?

libcxx/include/module.modulemap
647–648

As a general thing, I didn't bother to align the closing braces when making the initial header splits, and don't care for this change. It's very brittle on the LHS, and I don't want to duplicate said brittleness.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp
26 ↗(On Diff #390827)

Agreed. Please keep commits small and relevant.

tcanens added inline comments.Dec 1 2021, 8:41 AM
libcxx/include/__memory/ranges_uninitialized_algorithms.h
33 ↗(On Diff #390531)

This is for constructing into where it points to (or for the input version in particular, used only for destroy(_n), destroying what it points to). I don't see how we can implement it if it's not a real reference.

ldionne accepted this revision.Dec 1 2021, 8:51 AM

LGTM with

  • an updated comment in __nothrow_input_iterator
  • the removals in libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp moved to another NFC patch
  • the header renamed to __memory/concepts.h
libcxx/include/__memory/ranges_uninitialized_algorithms.h
33 ↗(On Diff #390531)

Ok, that makes sense, and admittedly I had lost the original purpose of these concepts when I formulated my hypothesis about non-throwing oprations. But then the concept is incredibly badly named. This has way more to it than not throwing exceptions. I suggest we change the comment to:

// This is used to ensure that uninitialized algorithms can construct an object
// at the address pointed-to by the iterator, which requires an lvalue.
is_lvalue_reference_v<iter_reference_t<_Ip>> &&
same_as<remove_cvref_t<iter_reference_t<_Ip>>, iter_value_t<_Ip>>;

At least that makes it clear this is unrelated to throwing exceptions.

1 ↗(On Diff #390827)

Let's try to avoid forking the header naming discussion happening below! Given your comment, I guess it makes sense to take the suggestion below and rename it to __memory/concepts.h -- that should satisfy everyone.

libcxx/include/__memory/ranges_uninitialized_algorithms.h
33 ↗(On Diff #390531)

I like that wording but let's keep it out of the middle of the expression, please.

// This concept ensures that uninitialized algorithms can construct an object
// at the address pointed-to by the iterator, which requires an lvalue.
template <class _Ip>
concept __nothrow_input_iterator =
    input_iterator<_Ip> &&
    is_lvalue_reference_v<iter_reference_t<_Ip>> &&
    same_as<remove_cvref_t<iter_reference_t<_Ip>>, iter_value_t<_Ip>>;

[or simply // at addressof(*it), but if that reopens a whole discussion, nvm :)]

var-const updated this revision to Diff 391143.Dec 1 2021, 2:47 PM
var-const marked an inline comment as done.
var-const edited the summary of this revision. (Show Details)

Address feedback (rename the new file to __memory/concepts.h, improve the
comment on __nothrow_input_iterator, revert the unrelated refactoring in an
input_iterator test, various minor fixes.)

var-const marked 12 inline comments as done.Dec 1 2021, 2:53 PM
var-const added inline comments.
libcxx/include/__memory/ranges_uninitialized_algorithms.h
33 ↗(On Diff #390531)

Done. @tcanens Thanks for the explanation!

1 ↗(On Diff #390827)

Renamed to concepts.h.

libcxx/include/module.modulemap
647–648

Done. I'm also not a fan of these kinds of formatting -- I originally did it just for consistency with the existing code.

libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_iterator.compile.pass.cpp
26–28

In this case, I'd prefer to keep it as-is. I deliberately separated operator* because it's the only function of interest in this class.

libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_sentinel_for.compile.pass.cpp
22

Thanks for spotting. I cleaned up other test files but missed this one.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.input/input_iterator.compile.pass.cpp
26 ↗(On Diff #390827)

Reverted

var-const marked 4 inline comments as done.Dec 1 2021, 2:53 PM
var-const updated this revision to Diff 391144.Dec 1 2021, 2:56 PM

Run libcxx-generate-files.

var-const updated this revision to Diff 391146.Dec 1 2021, 2:58 PM

Formatting

ldionne accepted this revision.Dec 2 2021, 7:04 AM

LGTM as is once CI is passing. You're likely missing an include, the modular build is complaining. Also, you could rebase onto main, where we don't build in 32 bit mode anymore.

jloser added inline comments.Dec 2 2021, 9:07 AM
libcxx/test/std/algorithms/specialized.algorithms/special.mem.concepts/special.mem.concepts.compile.pass.cpp
49–52 ↗(On Diff #390531)

I like the general idea of testing subsumption for concepts, including these. Overkill for most user concepts in codebases, but for standard library implementors, I think it's reasonable. WDYT, @ldionne @cjdb?

ldionne added inline comments.Dec 2 2021, 11:29 AM
libcxx/test/std/algorithms/specialized.algorithms/special.mem.concepts/special.mem.concepts.compile.pass.cpp
49–52 ↗(On Diff #390531)

We did some of this at some point, but as concepts become larger and more complex, it ends up being incredibly complicated to do that. You basically end up copy-pasting exactly the sub-expressions that are used in the implementation to make sure that the concept subsumes these sub-expressions. I'm not convinced that it provides that much bang for our buck, except in simple cases (e.g. it's obvious that forward_iterator should subsume input_iterator, and that should be checked).

49–52 ↗(On Diff #390531)

So yeah, writing that, I guess it makes sense to check that nothrow_forward_iterator subsumes nothrow_input_iterator.

var-const added inline comments.Dec 2 2021, 1:05 PM
libcxx/test/std/algorithms/specialized.algorithms/special.mem.concepts/special.mem.concepts.compile.pass.cpp
49–52 ↗(On Diff #390531)

I'd prefer to merge this patch as-is and add subsumption tests in a follow-up.

var-const updated this revision to Diff 391441.Dec 2 2021, 1:06 PM

Rebase on main.

var-const updated this revision to Diff 391475.Dec 2 2021, 3:10 PM

Fix includes.

var-const updated this revision to Diff 391502.Dec 2 2021, 5:01 PM

Another missing header.

This revision was not accepted when it landed; it landed in state Needs Review.Dec 2 2021, 5:58 PM
This revision was automatically updated to reflect the committed changes.