[libc++] Use bounded iterators in std::span when the debug mode is enabled

[ldionne]

Summary

Previously, we'd use raw pointers when the debug mode was enabled,
which means we wouldn't get out-of-range checking with std::span's
iterators.

This patch introduces a new class called __bounded_iter which can
be used to wrap iterators and make them carry around bounds-related
information. This allows iterators to assert when they are dereferenced
outside of their bounds.

As a fly-by change, this commit removes the _LIBCPP_ABI_SPAN_POINTER_ITERATORS
knob. Indeed, not using a raw pointer as the iterator type is useful to
avoid users depending on properties of raw pointers in their code.

This is an alternative to D127401.

[ldionne]

This approach has the benefit that we don't need to modify the container (std::span) at all, unlike with the usual __wrap_iter and __debug_insert_c() methods. It doesn't use a global locking mechanism and the internal debug "database". As a result, std::span can stay trivially copyable and trivially destructible, which could be important for the correctness of user programs.

On the downside, we also can't track any potential changes to the size of the container. Once an iterator is obtained, the bounds it considers will never change, even if the underlying container could potentially change its bounds. This is not a major issue for std::span, however it could potentially be an issue for other containers.

[philnik]

libcxx/include/span

233

What do you think about introducing a constexpr bool _InDebugMode and make this using iterator = _If<_InDebugMode, __bounded_iter<pointer>, __wrap_iter<pointer>>? With that it would also be possible to use if constexpr (_InDebugMode) and void func() requires _InDebugMode. This only works for C++11, C++17 and C++20 code respectively, but is a lot nicer to read IMO.

391–395

For example this could change to

if constexpr (_InDebugMode) {
    return iterator(data(), data(), data() + size());
} else {
    return iterator(this, data());
}

libcxx/test/libcxx/containers/views/views.span/span.elem/assert.back.pass.cpp

29

Maybe array.data() or std::data(array)?

[philnik]

This approach has the benefit that we don't need to modify the container (std::span) at all, unlike with the usual __wrap_iter and __debug_insert_c() methods. It doesn't use a global locking mechanism and the internal debug "database". As a result, std::span can stay trivially copyable and trivially destructible, which could be important for the correctness of user programs.

I wouldn't call std::span a container.

On the downside, we also can't track any potential changes to the size of the container. Once an iterator is obtained, the bounds it considers will never change, even if the underlying container could potentially change its bounds. This is not a major issue for std::span, however it could potentially be an issue for other containers.

I think this approach is good for views like std::span and std::string_view and fixed-size containers like std::array which are normally (conditionally) trivially copyable. I don't think there is any resizable container which is trivially destructible or copyable, so there it isn't a huge problem that we have to add and remove them from the database. I don't see any problem with having two ways to do two related but still quite different things.

[jkorous]

libcxx/include/span

237

This gets rbegin() and rend() covered as well, right? Shall we add some tests to make the guarantee explicit?

[Mordante]

Thanks for working on this, I like the general direction!

I think we should add more tests to validate whether the bound iterator's operations work as expected. Also in language modes other than C++20.

libcxx/include/__iterator/bounded_iter.h

67

Why not adding move construction and assignment?

86

How about including <span> ?

I don't feel adding all options here is the cleanest approach. But I expect this list to remain very short so I don't object.

144

Same for the other places.

192

Copy paste == and in the next operators.

201

Can we make all these operators only available before C++20 and add operator<=> for C++20 and later.

211

libcxx/test/libcxx/containers/views/views.span/debug.iterator-indexing.pass.cpp

14

c++03 is already unsupported at line 8.

27

libcxx/test/libcxx/containers/views/views.span/span.elem/assert.back.pass.cpp

18

Please have a look at the other tests too.

[ldionne]

Add tests for __bounded_iter itself. Address most review comments. Use clang-format.

[ldionne]

In D127418#3570877, @philnik wrote:

This approach has the benefit that we don't need to modify the container (std::span) at all, unlike with the usual __wrap_iter and __debug_insert_c() methods. It doesn't use a global locking mechanism and the internal debug "database". As a result, std::span can stay trivially copyable and trivially destructible, which could be important for the correctness of user programs.

I wouldn't call std::span a container.

Yeah, I'm being sloppy in my choice of terms here, indeed.

In D127418#3578865, @Mordante wrote:

I think we should add more tests to validate whether the bound iterator's operations work as expected. Also in language modes other than C++20.

Agreed, and done!

libcxx/include/__iterator/bounded_iter.h

86

We can't include <span> because it includes this header! That being said, I changed this to a free function that creates these __bounded_iters instead, since it allows me to test them.

144

I don't think we've decided on an official east-const vs west-const policy, so I'll leave as-is. It's consistent within the file and tests.

192

Ooooh, thanks. I added tests, too.

201

I'm really not sure it's worth the added complexity. Am I missing a benefit this would provide, like efficiency or something else? If not, given that we *have* to define the operators to support older C++ Standards anyway, it seems to me that supporting <=> would only add additional complexity.

211

Will leave as-is. I intended to put them on the same line since the comment then applies to both begin and end, which is what I wanted.

libcxx/include/span

233

I am ambivalent about this. I don't think it's a bad idea, but I'm not sure there is much of an actual benefit beyond being more "modern". I'll give it a shot and report on what I think.

237

Yes, it covers it. Added tests.

libcxx/test/libcxx/containers/views/views.span/span.elem/assert.back.pass.cpp

18

Yeah, thanks, I fixed all of them.

[Mordante]

LGTM after the CI passes. I leave the final approval to @philnik since he also had some comments.

libcxx/include/__iterator/bounded_iter.h

86

Thanks! I even wonder whether the previous dependencies would work for modules.

201

Mainly for consistency with other containers and iterators. I don't know whether there are places in the Standard that would mandate this. (I haven't spend much time reading the spaceship wording.) But I don't see it as a blocker.

libcxx/test/libcxx/iterators/bounded_iter/types.compile.pass.cpp

40

I really like this set of __bounded_iter tests!

[ldionne]

Fix modules test.

[ldionne]

Fix CI failures. I had to remove uses of std::array in bounded_iter's tests because of constexpr requirements.

[ldionne]

Implement to_address.

[ldionne]

Fix CI in C++03 and C++11.

[ldionne]

Rebase onto main.