[libc++] Add an assertion in the subrange constructors with a size hint

[ldionne]

Summary

Those constructors are very easy to misuse -- one could easily think that
the size passed to the constructor is the size of the range to exhibit
from the subrange. Instead, it's a size hint and it's UB to get it wrong.
Hence, when it's cheap to compute the real size of the range, it's cheap
to make sure that the user didn't get it wrong.

[• Quuxplusone]

libcxx/include/__ranges/subrange.h

123–125

It is mildly sketchy that you're testing sized_sentinel_for on decltype(__iter) (which is not _Iter) but then invoking ranges::distance on _Iter. What if !sized_sentinel_for<_Sent, _Iter>?

Also, what if !forward_iterator<_Iter>? Then it is invalid to mess with this->__begin_ except at the user's command.

Also, what if !copyable<_Iter>? I don't think that's possible today, but I think there are active proposals for move-only iterators. (But even with those proposals, I bet forward_iterator<_Iter> implies copyable<_Iter>. So that's probably fine.)

I suspect that this is a UB-if-violated "Precondition", not a "Mandates", on purpose, and we should just leave it alone.

[ldionne]

Address review comments

libcxx/include/__ranges/subrange.h

123–125

It is mildly sketchy that you're testing sized_sentinel_for on decltype(__iter) (which is not _Iter) but then invoking ranges::distance on _Iter. What if !sized_sentinel_for<_Sent, _Iter>?

Right, this should be if constexpr (sized_sentinel_for<_Sent, _Iter>) instead. Initially I used ranges::distance(__iter, __sent) so this was correct, but then I noticed we were moving from __iter so I changed to this->__begin_ and forgot to update the if constexpr. Will fix.

Also, what if !forward_iterator<_Iter>? Then it is invalid to mess with this->__begin_ except at the user's command.

Ugh, sure. My thinking was that if you model sized_sentinel_for, clearly you don't expect that evaluating iter - sent is going to do something crazy like invalidate your range. I'm even fine with adding random_access_iterator<_Iter> -- the goal here really is to do our due diligence at catching the UB when it's easy to do that.

I suspect that this is a UB-if-violated "Precondition", not a "Mandates", on purpose, and we should just leave it alone.

I disagree pretty strongly. It's easy to check this precondition, and if the programmer got it wrong, they might have a more serious bug in their program. I think the least we can do is add an assertion to help them catch the issue.

[• Quuxplusone]

libcxx/include/__ranges/subrange.h

123–125

Well, now the if is no longer testing the condition from the Standard wording, so we're drifting away from "checking the precondition" and into "checking a class invariant." I think I agree that what you've got now checks a valid class invariant for this class.
However, for simplicity, how about we do this instead?

if constexpr (sized_sentinel_for<_Sent, _Iter>)
    _LIBCPP_ASSERT((this->__end_ - this->__begin_) == iter_difference_t<_Iter>(this->__size_), "std::ranges::subrange was passed a size hint with the wrong value");

That is, whenever end - begin is well-formed, the size that is passed in must be equal to end - begin.
I put the cast on __size_ just to avoid comparing signed with unsigned. __size_ and __n should be equal at this point.

I think it's reasonable to assume that evaluating end - begin will not invalidate begin, so we no longer need to check for forward_iterator<_Iter>.

[ldionne]

Adjust condition

libcxx/include/__ranges/subrange.h

123–125

Well, now the if is no longer testing the condition from the Standard wording, so we're drifting away from "checking the precondition" and into "checking a class invariant."

Sure, but you're looking at it very pedantically. Concretely, we copy/move __iter and __sent into __begin_ and __end_, so checking that "class invariant" is entirely the same as checking the precondition on the constructor. The only reason why I'm not checking the arguments directly is that we want to move out of __iter.

I like using ranges::distance more than end - begin cause I like the semantic cue it provides, but I agree that if we can remove a dependency on ranges::distance, we should do it. I moved to this->end - this->begin.

Your usage of this->__size_ is not going to work because we don't always store the size. We want to check the precondition even when we end up not storing the size.

I think it's reasonable to assume that evaluating end - begin will not invalidate begin, so we no longer need to check for forward_iterator<_Iter>.

My goal was to make sure the subtraction was O(1), but it turns out that's unnecessary since sized_sentinel_for already mandates that. Technically, I don't see anything that mandates that sent - begin is equality preserving, but I also can't find anything in forward_iterator that would ensure that it must be equality-preserving. So I think we'll have to trust that people are not crazy and define sized_sentinel_for on an iterator such that sent - begin invalidates begin.

[• Quuxplusone]

LGTM at this point. You'll have to fix some IMHO-much-too-fragile tests before this can land.

[ldionne]

Try to fix the CI.

[• Quuxplusone]

libcxx/test/std/ranges/range.utility/range.subrange/types.h

23 ↗

(On Diff #369936)

Huh. #include <ranges> from this header, then?

55 ↗

(On Diff #369936)

Scope creep: It's mildly weird that this type is called SizedSentinelForwardIterator when it doesn't actually involve a sentinel type. (Technically, this iterator type is its own sentinel type; but I call it mildly weird naming nonetheless.) It would be nicer to name it SubtractableForwardIterator.

As we fill out more of the C++20 library, you might also consider adding the sanity-checking static-asserts we couldn't originally do; e.g. on line 91, static_assert(std::sized_sentinel_for<SubtractableForwardIterator, SubtractableForwardIterator>);. This kind of assertion is best-practice in real life, to avoid hard-to-debug delayed error messages; I think it's reasonable to also put such assertions in our test-code helper headers. But scope creep, and also not worth fighting for right now.

[ldionne]

Address review comments and poke CI.

libcxx/test/std/ranges/range.utility/range.subrange/types.h

55 ↗

(On Diff #369936)

I'll add the assertion but won't do the renaming here, it touches too many things for this PR. Feel free to submit a NFC patch with a naming you prefer.

[ldionne]

Fix test that didn't work when the debug mode is enabled.

[ldionne]

The only failure is in the runtimes build, but I just reverted the Clang patch that caused it. Shipping now.

libcxx/include/__ranges/subrange.h

struct _LIBCPP_TEMPLATE_VIS subrange
     constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent)
       requires (!_Base::__store_size)
       : _Base(_VSTD::move(__iter), __sent) {}
 
     _LIBCPP_HIDE_FROM_ABI
     constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent,
                        make_unsigned_t<iter_difference_t<_Iter>> __n)
       requires (_Kind == subrange_kind::sized)
-      : _Base(_VSTD::move(__iter), __sent, __n) { }
+      : _Base(_VSTD::move(__iter), __sent, __n)
+    {
+      if constexpr (sized_sentinel_for<_Sent, decltype(__iter)>)
+        _LIBCPP_ASSERT(ranges::distance(this->__begin_, this->__end_) == __n, "std::ranges::subrange was passed an invalid size hint");
+    }
 
     template<__different_from<subrange> _Range>
       requires borrowed_range<_Range> &&
                __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
                convertible_to<sentinel_t<_Range>, _Sent>
     _LIBCPP_HIDE_FROM_ABI
     constexpr subrange(_Range&& __range)
       requires (!_Base::__store_size)