[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

124–126

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

124–126

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

124–126

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

124–126

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

28

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

60

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

60

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

 #define _LIBCPP___RANGES_SUBRANGE_H
 
 #include <__concepts/constructible.h>
 #include <__concepts/convertible_to.h>
 #include <__concepts/copyable.h>
 #include <__concepts/derived_from.h>
 #include <__concepts/different_from.h>
 #include <__config>
+#include <__debug>
+#include <__iterator/advance.h>
 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iterator_traits.h>
-#include <__iterator/advance.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
 #include <__ranges/enable_borrowed_range.h>
 #include <__ranges/size.h>
 #include <__ranges/view_interface.h>
 #include <__tuple>
 #include <__utility/move.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, _Iter>)
+        _LIBCPP_ASSERT((this->__end_ - this->__begin_) == static_cast<iter_difference_t<_Iter>>(__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)

libcxx/test/std/ranges/range.utility/range.subrange/primitives.pass.cpp

 // UNSUPPORTED: libcpp-no-concepts
 // UNSUPPORTED: libcpp-has-no-incomplete-ranges
 
 // class std::ranges::subrange;
 
 #include <ranges>
 
 #include <cassert>
-#include "test_macros.h"
 #include "test_iterators.h"
 #include "types.h"
 
 constexpr bool test() {
-  std::ranges::subrange<MoveOnlyForwardIter, int*> a(MoveOnlyForwardIter(globalBuff), globalBuff + 8, 8);
-  assert(a.begin().base == globalBuff);
+  int buff[] = {1, 2, 3, 4, 5};
+
+  {
+    std::ranges::subrange<MoveOnlyForwardIter, int*> a(MoveOnlyForwardIter(buff), buff + 5, 5);
+    assert(a.begin().base == buff);
     assert(!a.empty());
-  assert(a.size() == 8);
+    assert(a.size() == 5);
+  }
 
+  {
     std::ranges::subrange<ForwardIter> b(ForwardIter(nullptr), ForwardIter(nullptr));
     assert(b.empty());
+  }
 
-  std::ranges::subrange<ForwardIter> c{ForwardIter(globalBuff), ForwardIter(globalBuff)};
+  {
+    std::ranges::subrange<ForwardIter> c{ForwardIter(buff), ForwardIter(buff)};
     assert(c.empty());
+  }
 
-  std::ranges::subrange<ForwardIter> d(ForwardIter(globalBuff), ForwardIter(globalBuff + 1));
+  {
+    std::ranges::subrange<ForwardIter> d(ForwardIter(buff), ForwardIter(buff + 1));
     assert(!d.empty());
+  }
 
-  std::ranges::subrange<SizedSentinelForwardIter> e(SizedSentinelForwardIter(globalBuff),
-                                                    SizedSentinelForwardIter(globalBuff + 8), 8);
+  {
+    bool minusWasCalled = false;
+    SizedSentinelForwardIter beg(buff, &minusWasCalled), end(buff + 5, &minusWasCalled);
+    std::ranges::subrange<SizedSentinelForwardIter> e(beg, end, 5);
     assert(!e.empty());
-  assert(e.size() == 8);
 
     // Make sure that operator- is used to calculate size when possible.
-  if (!std::is_constant_evaluated())
-    assert(SizedSentinelForwardIter::minusCount == 1);
+    minusWasCalled = false;
+    assert(e.size() == 5);
+    assert(minusWasCalled);
+  }
 
   return true;
 }
 
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

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

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LIBCXX_TEST_STD_RANGES_RANGE_UTILITY_RANGE_SUBRANGE_TYPES_H
 #define LIBCXX_TEST_STD_RANGES_RANGE_UTILITY_RANGE_SUBRANGE_TYPES_H
 
+#include <cstddef>
+#include <iterator>
+#include <ranges>
+#include <type_traits>
+
 #include "test_macros.h"
 #include "test_iterators.h"
 
 int globalBuff[8];
 
 struct Empty {};
 
 using InputIter = cpp17_input_iterator<int*>;
 using ForwardIter = forward_iterator<int*>;
 using BidirIter = bidirectional_iterator<int*>;
 
 using ForwardSubrange = std::ranges::subrange<ForwardIter, ForwardIter, std::ranges::subrange_kind::unsized>;
 using SizedIntPtrSubrange = std::ranges::subrange<int*, int*, std::ranges::subrange_kind::sized>;
 
 struct MoveOnlyForwardIter {
     typedef std::forward_iterator_tag       iterator_category;
     typedef int                             value_type;
     typedef std::ptrdiff_t                  difference_type;
     typedef int*                            pointer;
     typedef int&                            reference;
struct MoveOnlyForwardIter {
     self& operator++();
     self operator++(int);
     self& operator--();
     self operator--(int);
 
     constexpr operator pointer() const { return base; }
 };
 
 struct SizedSentinelForwardIter {
     typedef std::forward_iterator_tag            iterator_category;
     typedef int                                  value_type;
     typedef std::ptrdiff_t                       difference_type;
     typedef int*                                 pointer;
     typedef int&                                 reference;
     typedef std::make_unsigned_t<std::ptrdiff_t> udifference_type;
     typedef SizedSentinelForwardIter             self;
 
-    int *base;
-
     SizedSentinelForwardIter() = default;
-    constexpr SizedSentinelForwardIter(int *ptr) : base(ptr) { }
+    constexpr explicit SizedSentinelForwardIter(int *ptr, bool *minusWasCalled)
+      : base_(ptr), minusWasCalled_(minusWasCalled)
+    { }
 
-    friend constexpr bool operator==(const self& lhs, const self& rhs) { return lhs.base == rhs.base; }
+    friend constexpr bool operator==(const self& lhs, const self& rhs) { return lhs.base_ == rhs.base_; }
 
     reference operator*() const;
     pointer operator->() const;
     self& operator++();
     self operator++(int);
     self& operator--();
     self operator--(int);
 
-    static int minusCount;
-    friend constexpr difference_type operator-(SizedSentinelForwardIter const&a,
-                                               SizedSentinelForwardIter const&b) {
-      if (!std::is_constant_evaluated())
-        minusCount++;
-      return a.base - b.base;
+    friend constexpr difference_type operator-(SizedSentinelForwardIter const& a,
+                                               SizedSentinelForwardIter const& b) {
+      if (a.minusWasCalled_)
+        *a.minusWasCalled_ = true;
+      if (b.minusWasCalled_)
+        *b.minusWasCalled_ = true;
+      return a.base_ - b.base_;
     }
-};
 
-int SizedSentinelForwardIter::minusCount = 0;
+private:
+    int *base_ = nullptr;
+    bool *minusWasCalled_ = nullptr;
+};
+static_assert(std::sized_sentinel_for<SizedSentinelForwardIter, SizedSentinelForwardIter>);
 
 struct ConvertibleForwardIter {
     typedef std::forward_iterator_tag       iterator_category;
     typedef int                             value_type;
     typedef std::ptrdiff_t                  difference_type;
     typedef int*                            pointer;
     typedef int&                            reference;
     typedef ConvertibleForwardIter          self;