This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by ldionne on Jun 9 2022, 11:04 AM.

Details

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.

Diff Detail

Event Timeline

ldionne created this revision.Jun 9 2022, 11:04 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 9 2022, 11:04 AM
ldionne requested review of this revision.Jun 9 2022, 11:04 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 9 2022, 11:04 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript

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 added inline comments.
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)?

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 added inline comments.
libcxx/include/span
237

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

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 updated this revision to Diff 437713.Jun 16 2022, 2:45 PM
ldionne marked 10 inline comments as done.

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

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.

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 accepted this revision as: Mordante.Jun 17 2022, 9:56 AM

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 updated this revision to Diff 438031.Jun 17 2022, 1:41 PM

Fix modules test.

ldionne updated this revision to Diff 438726.Jun 21 2022, 8:51 AM

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

ldionne updated this revision to Diff 439482.Jun 23 2022, 11:32 AM

Implement to_address.

ldionne updated this revision to Diff 439517.Jun 23 2022, 1:30 PM

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

ldionne updated this revision to Diff 439518.Jun 23 2022, 1:30 PM

Rebase onto main.

ldionne accepted this revision as: Restricted Project.Jun 27 2022, 5:34 AM
This revision is now accepted and ready to land.Jun 27 2022, 5:34 AM
libcxx/test/std/containers/views/views.span/span.sub/last.verify.cpp