[libc++] Fix signed overflow inside ranges::advance.

[• Quuxplusone]

Summary

See LWG reflector thread titled 'Question on ranges::advance and "past-the-sentinel iterators"',
from 2021-07-23.
Test case heavily based on one graciously provided by Casey Carter.

[• Quuxplusone]

whoops, didn't commit --amend before diffing

[cjdb]

libcxx/include/__iterator/advance.h

79

Please don't remove noexcept.

156

These explicit conversions shouldn't be necessary: zero is zero for all integer-like types. I also don't think swapping these two lines around is going to benefit anything.

161

Please don't change the type.

164

This else is redundant, please remove it.

172

These explicit conversion-to-bools aren't necessary.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/iterator_count_sentinel.pass.cpp

104

Please match the naming conventions that the file uses.

162

I'd prefer we use std::numeric_limits<Iota::difference_type>::min().

[• Quuxplusone]

Address review comments.

[ldionne]

Thanks for fixing this. LGTM but please check whether @cjdb is happy too.

[cjdb]

In D106735#2904085, @ldionne wrote:

Thanks for fixing this. LGTM but please check whether @cjdb is happy too.

It's almost ready, but I think my comments for the test file were missed.

[• Quuxplusone]

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/iterator_count_sentinel.pass.cpp

104

Got any suggestions? The "naming convention" in this file seems no more than "something long with lots of underscores."

[cjdb]

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/iterator_count_sentinel.pass.cpp

104

I'm fine with just iota, but if you want something "more", perhaps iota_range, or iota_range_regression.

libcxx/include/__iterator/advance.h

 #if !defined(_LIBCPP_HAS_NO_RANGES)
 
 namespace ranges {
 // [range.iter.op.advance]
 struct __advance_fn final : private __function_like {
 private:
   template <class _Tp>
   _LIBCPP_HIDE_FROM_ABI
-  static constexpr _Tp __abs(_Tp __n) noexcept {
-    return __n < 0 ? -__n : __n;
+  static constexpr _Tp __magnitude_geq(_Tp __a, _Tp __b) noexcept {
+    return __a < 0 ? (__a <= __b) : (__a >= __b);
   }
 
   template <class _Ip>
   _LIBCPP_HIDE_FROM_ABI
   static constexpr void __advance_forward(_Ip& __i, iter_difference_t<_Ip> __n) {
     while (__n > 0) {
       --__n;
       ++__i;
public:
   // Preconditions:
   //   * If `n > 0`, [i, bound) denotes a range.
   //   * If `n == 0`, [i, bound) or [bound, i) denotes a range.
   //   * If `n < 0`, [bound, i) denotes a range, `I` models `bidirectional_iterator`, and `I` and `S` model `same_as<I, S>`.
   // Returns: `n - M`, where `M` is the difference between the the ending and starting position.
   template <input_or_output_iterator _Ip, sentinel_for<_Ip> _Sp>
   _LIBCPP_HIDE_FROM_ABI
   constexpr iter_difference_t<_Ip> operator()(_Ip& __i, iter_difference_t<_Ip> __n, _Sp __bound) const {
     _LIBCPP_ASSERT(__n >= 0 || (bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>),
                    "If `n < 0`, then `bidirectional_iterator<I> && same_as<I, S>` must be true.");
     // If `S` and `I` model `sized_sentinel_for<S, I>`:
     if constexpr (sized_sentinel_for<_Sp, _Ip>) {
       // If |n| >= |bound - i|, equivalent to `ranges::advance(i, bound)`.
-      if (const auto __M = __bound - __i; __abs(__n) >= __abs(__M)) {
+      if (const auto __M = __bound - __i; __magnitude_geq(__n, __M)) {
         (*this)(__i, __bound);
         return __n - __M;
       }
 
       // Otherwise, equivalent to `ranges::advance(i, n)`.
       (*this)(__i, __n);
       return 0;
     } else {
       // Otherwise, if `n` is non-negative, while `bool(i != bound)` is true, increments `i` but at
       // most `n` times.
       while (__i != __bound && __n > 0) {
         ++__i;
         --__n;
       }
 
       // Otherwise, while `bool(i != bound)` is true, decrements `i` but at most `-n` times.
       if constexpr (bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>) {
         while (__i != __bound && __n < 0) {
           --__i;

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/iterator_count_sentinel.pass.cpp

 // UNSUPPORTED: gcc-10
 
 // ranges::advance(it, n, sent)
 
 #include <iterator>
 
 #include <array>
 #include <cassert>
+#include <climits>
 
 #include "test_iterators.h"
 
 using range_t = std::array<int, 10>;
 
 class distance_apriori_sentinel {
 public:
   distance_apriori_sentinel() = default;
constexpr void check_backward(std::ptrdiff_t n, expected_t expected, range_t& range) {
   auto current = stride_counting_iterator(It(range.end()));
   Difference const result = std::ranges::advance(current, -n, stride_counting_iterator(It(range.begin())));
   assert(current.base().base() == expected.coordinate);
   assert(result == expected.result);
   assert(current.stride_count() == n + result);
   assert(current.stride_count() == -current.stride_displacement());
 }
 
+struct Iota {
+    using difference_type = int;
+    using value_type = int;
+
+    int x;
+
+    constexpr int operator*() const { return x; }
+    constexpr Iota& operator++() { ++x; return *this; }
+    constexpr Iota operator++(int) { ++x; return Iota{x - 1}; }
+    constexpr bool operator==(const Iota&) const = default;
+
+    constexpr int operator-(const Iota& that) const { return x - that.x; }
+
+    constexpr Iota& operator--() { --x; return *this; }
+    constexpr Iota operator--(int) { --x; return Iota{x + 1}; }
+};
+static_assert(std::bidirectional_iterator<Iota>);
+static_assert(std::sized_sentinel_for<Iota, Iota>);
+
 constexpr bool test() {
   auto range = range_t{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
   check_forward_sized_sentinel<cpp17_input_iterator<range_t::const_iterator> >(1, {range.begin() + 1, 0}, range);
   // cpp20_input_iterator not copyable, so is omitted
   check_forward_sized_sentinel<forward_iterator<range_t::const_iterator> >(3, {range.begin() + 3, 0}, range);
   check_forward_sized_sentinel<bidirectional_iterator<range_t::const_iterator> >(4, {range.begin() + 4, 0}, range);
   check_forward_sized_sentinel<random_access_iterator<range_t::const_iterator> >(5, {range.begin() + 5, 0}, range);
   check_forward_sized_sentinel<contiguous_iterator<range_t::const_iterator> >(6, {range.begin() + 6, 0}, range);
constexpr bool test() {
   // distance == range.size()
   check_forward<forward_iterator<range_t::const_iterator> >(10, {range.end(), 0}, range);
   check_backward<bidirectional_iterator<range_t::const_iterator> >(10, {range.begin(), 0}, range);
 
   // distance > range.size()
   check_forward<forward_iterator<range_t::const_iterator> >(1000, {range.end(), 990}, range);
   check_backward<bidirectional_iterator<range_t::const_iterator> >(1000, {range.begin(), -990}, range);
 
+  // regression-test that INT_MIN doesn't cause any undefined behavior
+  {
+    auto i = Iota{+1};
+    assert(std::ranges::advance(i, INT_MIN, Iota{-2}) == INT_MIN+3);
+    assert(i == Iota{-2});
+    i = Iota{+1};
+    assert(std::ranges::advance(i, -2, Iota{INT_MIN+1}) == 0);
+    assert(i == Iota{-1});
+    i = Iota{+1};
+    assert(std::ranges::advance(i, INT_MIN, Iota{INT_MIN+1}) == 0);
+    assert(i == Iota{INT_MIN+1});
+  }
+
   return true;
 }
 
 int main(int, char**) {
   assert(test());
   static_assert(test());
   return 0;
 }