_LIBCPP_ABI_BOUNDED_ITERATORS support for std::string and std::vector

[davidben]

There is iterator support for std::string_view and std::span, but not the corresponding containers. It'd be cool to extend it to that.

I don't know why they weren't added there, but I have a guess. Was it because you're allowed to push_back on a std::string or std::vector, up to capacity(), without invalidating iterators? And then I guess std::vector's promise of pointer stability after move means the iterator can't just retain a pointer back to the parent container.

In that case, perhaps the wrapped iterator could be sized based on the capacity, rather than the length? It's a weaker check than is ideal, but at least it means you can't run off the end of the allocation.

[davidben]

Started putting this together for std::vector and noticed:

1. __bounded_iter's converting constructor has never worked. It needs a friend declaration to access the other iterator's internals.
2. There actually isn't a test that push_back() up to a vector's capacity keeps the iterators working!

But the tests will be very different depending on whether #78876 is accepted. Also adding to #78829 would be unfortunate. So I'm thinking I'll wait until #78876 is resolved one way or another.

[davidben]

Oh, another interesting detail is I think the iterators must be __bounded_iter<__wrapped_iter<pointer>>. This is because pointer comes from the allocator and in some of the tests, the allocator's custom pointer type doesn't read as a contiguous iterator, even though it is one.

[davidben]

Things noticed while playing with strings:

• std::string is much stricter about iterator invalidation than std::vector: https://eel.is/c++draft/string.require#4. I suspect this is a remnant of copy-on-write strings.
• However, I think the iterator needs to be each the trailing NUL? At least cppreference claims this. I haven't found the exact spec reference, phrased in terms of iterators.
• test/std/strings/basic.string/string.capacity/resize_and_overwrite.pass.cpp assumes s.begin().base() works. __wrap_iter has a base() method but __bounded_iter does not. Is that method actually guaranteed to exist? libstdc++ and libc++ have it, but MSVC doesn't. I suspect that test should be std::to_address(s.begin()).

As with std::vector, I'll wait for #78876 before finishing this up.

(CC @danakj.)

[davidben]

I think probably the reasonable options for std::string are:

Option 1: Length-bound iterators
Because the standard allows iterator invalidation, bound the iterators by data() + size() + 1, not data() + capacity() + 1. This means the following will not work:

std::string s("abc");
s.reserve(10);
auto it = s.begin();
s.push_back('d');
assert(*(it + 3) == 'd');

But the standard doesn't promise that it works, so breaking is still conformant.

Option 2: Capacity-bound iterators
Although the standard allows iterator invalidation, libc++ does not invalidate iterators today on push_back within capacity. Code may be relying on it, so we could decide to bound the iterators by data() + capacity() + 1 to preserve that behavior in _LIBCPP_ABI_BOUNDED_ITERATORS. Then we're saying that libc++ promises slightly more than the STL does. In that case, I'll add a test like the snippet above, but put it with the other libc++-specific tests.

(Looks like capacity() doesn't include the terminator, so we need to add 1.)

Option 3: Point back to the string
Alternatively, because std::string invalidate iterators after a move (necessary for SSO), the bounded iterators can instead point back to the std::string. Then all this is moot and we can sample the actual current length. However, that means we have to build a new bounded iterator, and also repeat all the work to make sure things optimize well. Since accesses within std::string are non-trivial from SSO, the compiler will need to do a bit of work to optimize it. Any uninlined std::string method will probably tank it.

I'm inclined to do the first one, and switch to the second if it turns out large codebases (Chromium, in my case) have been relying on this property. But also happy to just do the second if that's what folks prefer. The third is a lot more work and perhaps can be something to explore for later.

Edit: Looking at the spec, I'm actually not sure if the terminator is guaranteed to be reachable via iterators. operator[] goes out of its way to not define terminator access in terms of iterators. In fact, it actually can't be fully accessible via iterators because you can't modify it. This might be another place where we have to decide which one to promise. I'm inclined to try without the +1 and see how it goes.

[ldionne]

CC @var-const