[libc++] Rationalize our treatment of contiguous iterators and __unwrap_iter().

[Quuxplusone]

Summary

• Continue exposing contiguous_iterator_tag only in C++20.
• Implement C++20's changes to reverse_iterator, so that it won't be accidentally counted as a contiguous iterator (and test this).
• Implement C++20's changes to move_iterator as well (and test them).
• move_iterator should not be contiguous. This fixes a bug where we optimized std::copy-of-move-iterators in an observable way. Add a regression test for that bugfix.
• Add libcxx tests for __is_cpp17_contiguous_iterator of all relevant standard iterator types (in all modes).
• Expose {reverse,move}_iterator::iterator_concept only in C++20 mode. I initially exposed it in all modes, but now that contiguous_iterator_tag is C++20-only, I think this makes more sense.

I expect this to solve the issue reported by @rnk in D92776. They should just be able to write a conforming contiguous iterator according to https://stackoverflow.com/questions/65712091/in-c20-how-do-i-write-a-contiguous-iterator
libc++ will guarantee that it works (i.e. is optimized in std::copy) in C++20 mode, but will continue not to support user-defined contiguous iterators in C++17.

I would perhaps like to rename __unwrap_iter(x) to something like __unwrap_contiguous_iter(x) or __lower_contiguous_iter(x), to better reflect its purpose; but I didn't want to do that in this patch because it would just add icky diffs at all the call-sites.

[Quuxplusone]

Improve the contiguous_iterators.pass.cpp test, including a test case for exactly what I'd expect Chromium to write in their code to enable contiguous-iterator-ness.

[Quuxplusone]

Tests failed. Let's try this again.

[Quuxplusone]

In the new test, make TCBNTM and TMBNTC copy-constructible, because if they're not, then you can't make an array of them pre-C++17. ("error: copying array element of type 'TMBNTC'...")

[Quuxplusone]

Rebase, and fix my new test's constexprness in C++11 mode.

[ldionne]

I like this - I find it cleaner than a "private contract" with some specific users that they are allowed to overload __unwrap_iter. But I'd like to know why can't we leave that only enabled in C++20 mode. @rnk Would it be acceptable for Chrome to compile with C++20? It seems like an optimization that would justify the work to upgrade?

As a matter of policy, I'm a bit reluctant to say "let's add this as an extension because our very important client Chrome is using it". I don't think it's a great way to make decisions. The only reason why I could see us doing it here is because Chrome previously had a free-pass with __unwrap_iter and we broke them. But my preference would be to avoid adding those extensions pre-C++20. @rnk can you comment?

libcxx/include/algorithm

1642

Can you name this __apply? Or we could use operator(). Either seems closer to conventions than __f.

libcxx/include/iterator

591

Isn't this check made redundant by the following check for __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>?

600

I take it that you're not using just true_type here in case someone specializes iterator_traits<MyFoo*> to have a non random-access iterator_category?

764–765

A test should be added for that.

1216–1219

A test should be added for that.

[rnk]

In D94807#2520226, @ldionne wrote:

I like this - I find it cleaner than a "private contract" with some specific users that they are allowed to overload __unwrap_iter. But I'd like to know why can't we leave that only enabled in C++20 mode. @rnk Would it be acceptable for Chrome to compile with C++20? It seems like an optimization that would justify the work to upgrade?

As a matter of policy, I'm a bit reluctant to say "let's add this as an extension because our very important client Chrome is using it". I don't think it's a great way to make decisions. The only reason why I could see us doing it here is because Chrome previously had a free-pass with __unwrap_iter and we broke them. But my preference would be to avoid adding those extensions pre-C++20. @rnk can you comment?

Chrome hasn't yet migrated to C++17 yet: https://crbug.com/752720 The major blocker is that nacl compilers are still used somewhere, so I'm pretty sure we are not ready to enable C++20.

In the discussion on the bug with the author of these checked iterators, they seemed OK with relying on implementation details, including re-opening the std::__1 namespaces with the necessary macros to make the __unwrap_iter overload work. I think the optimization only has to work with bundled libc++ version. If that is not in use, the optimization is disabled. I think we might be OK without a properly supported way to do this until we make it to C++20. NaCl is supposed to go away in 2021, so at that point we could probably spring forward and use the officially supported mechanism.

[ldionne]

In D94807#2520593, @rnk wrote:

In the discussion on the bug with the author of these checked iterators, they seemed OK with relying on implementation details, including re-opening the std::__1 namespaces with the necessary macros to make the __unwrap_iter overload work. I think the optimization only has to work with bundled libc++ version. If that is not in use, the optimization is disabled. I think we might be OK without a properly supported way to do this until we make it to C++20. NaCl is supposed to go away in 2021, so at that point we could probably spring forward and use the officially supported mechanism.

Okay, so if I'm reading this correctly, we basically don't have anything to do as requested on D92776.

Arthur, some of this stuff landed in C++20, so we can still do it, but in C++20 only. Are you OK with that?

[Quuxplusone]

libcxx/include/algorithm

1642

I definitely object to operator(); I prefer named functions whenever possible. I don't object to __apply; I just picked __f because it was short. (We don't seem to have any instances of either __f or __apply with this connotation in the codebase. We do have quite a few __test, but that name seems inappropriate here because this is a transformation, not a SFINAE test.)

libcxx/include/iterator

444

@ldionne wrote:

Arthur, some of this stuff landed in C++20, so we can still do it, but in C++20 only. Are you OK with that?

Yes, I believe so, unless I run into a problem with that.
The important subtlety here remains, even if we ignore Chromium. The way I've got the code structured now, in both C++03 and C++20,

• The std::copy-to-memmove optimization happens only for iterators where __unwrap_iter(it) returns a native pointer T*.
• __unwrap_iter(it) returns native pointers only for contiguous iterators, i.e., __is_cpp17_contiguous_iterator<It>::value is true and _VSTD::__to_address(it) exists.
• We want the std::copy-to-memmove optimization to happen for vector<int>::iterator i.e. __wrap_iter<int*>.

So even in C++03 mode, where std::contiguous_iterator_tag does not exist, we must ensure that __is_cpp17_contiguous_iterator<int*>::value && __is_cpp17_contiguous_iterator<__wrap_iter<int*>>::value.

I think that's a good state of affairs, and I think I can physically make it happen. But if I come back and say "oops, actually that's physically impossible because...," then I'll ask to revisit this.

591

It's not completely redundant — it rejects user-defined iterator types with iterator_category=input_iterator_tag and iterator_concept=contiguous_iterator_tag. However, I can't point to any such types in the wild, and I didn't write any unit tests for such types, so I agree — I'll remove the redundancy. Let someone put it back if they run into such a case in the wild.

600

As the comment indicated, my intent had been to make sure this specialization didn't accidentally accept types like int(*)(), void*,... which are syntactically _Up* but not actually iterators.
However, writing tests for this revealed that if you try to ask __is_cpp17_contiguous_iterator<void*> it just blows up anyway, because instantiating iterator_traits<void*> is ill-formed.
So as above, I agree — I'll just do true_type here and let someone "fix" the corner case for real, if they ever run into it.

I hadn't realized that __has_iterator_category_convertible_to wasn't SFINAE-friendly. (It barfs on most non-iterator types.)

[ldionne]

libcxx/include/iterator

591

That would be a weird and misleading iterator, wouldn't it?

600

I hadn't realized that __has_iterator_category_convertible_to wasn't SFINAE-friendly. (It barfs on most non-iterator types.)

This is surprising to me. Perhaps we should fix it.

[Quuxplusone]

libcxx/include/iterator

444

@ldionne: It would be almost trivial, if there were a way to expose contiguous_iterator_tag only to the implementation, e.g.

struct __libcpp_contiguous_iterator_tag : random_access_iterator_tag {};
#if _LIBCPP_STD_VER > 17
using contiguous_iterator_tag = __libcpp_contiguous_iterator_tag;
#endif

Is that snippet acceptable? and/or have you got another acceptable idea?
If not, then it's still possible to achieve our goal, but with an increased number of codepaths that differ when #if _LIBCPP_STD_VER > 17.

[Quuxplusone]

Update with the same patch that I rolled into D93661 last week. Still waiting for buildkite to unbork itself and finish a build.

[ldionne]

libcxx/include/iterator

444

Yes, it's acceptable IMO.

[ldionne]

Except for the comment nitpick, this LGTM. Please update and submit. Thanks a lot!

libcxx/include/iterator

587–588

I think the comment at the top of libcxx/test/libcxx/iterators/contiguous_iterators.pass.cpp should come here instead, it helps understanding what's going on.

[Quuxplusone]

Split out the regression test into its own test file.
Hide move_iterator::iterator_concept in C++17-and-earlier. (I had done this for __wrap_iter::iterator_concept and iterator_traits::iterator_concept, but forgotten to do it for move_iterator and reverse_iterator).
Poke buildkite one last time before (I hope) finally landing this patch.

[Quuxplusone]

libcxx/include/iterator

600

Agreed, but not fixed in this patch.