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

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

Differential Revision: https://reviews.llvm.org/D106735

2 files changed, 35 insertions, 4 deletions

diff --git a/libcxx/include/__iterator/advance.h b/libcxx/include/__iterator/advance.h
index b0a9b68..674a304 100644
--- a/libcxx/include/__iterator/advance.h
+++ b/libcxx/include/__iterator/advance.h
@@ -76,8 +76,8 @@ 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) {
+    return __a < 0 ? (__a <= __b) : (__a >= __b);
   }
 
   template <class _Ip>
@@ -153,12 +153,12 @@ public:
   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>),
+    _LIBCPP_ASSERT((bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>) || (__n >= 0),
                    "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 (auto __M = __bound - __i; __magnitude_geq(__n, __M)) {
         (*this)(__i, __bound);
         return __n - __M;
       }
diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/iterator_count_sentinel.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/iterator_count_sentinel.pass.cpp
index b8e4372..8a0fb5d 100644
--- a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/iterator_count_sentinel.pass.cpp
+++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/iterator_count_sentinel.pass.cpp
@@ -16,6 +16,7 @@
 
 #include <array>
 #include <cassert>
+#include <climits>
 
 #include "test_iterators.h"
 
@@ -100,6 +101,23 @@ constexpr void check_backward(std::ptrdiff_t n, expected_t expected, range_t& ra
   assert(current.stride_count() == -current.stride_displacement());
 }
 
+struct iota_iterator {
+    using difference_type = int;
+    using value_type = int;
+
+    constexpr int operator*() const { return x; }
+    constexpr iota_iterator& operator++() { ++x; return *this; }
+    constexpr iota_iterator operator++(int) { ++x; return iota_iterator{x - 1}; }
+    constexpr bool operator==(const iota_iterator&) const = default;
+    constexpr int operator-(const iota_iterator& that) const { return x - that.x; }
+    constexpr iota_iterator& operator--() { --x; return *this; }
+    constexpr iota_iterator operator--(int) { --x; return iota_iterator{x + 1}; }
+
+    int x;
+};
+static_assert(std::bidirectional_iterator<iota_iterator>);
+static_assert(std::sized_sentinel_for<iota_iterator, iota_iterator>);
+
 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);
@@ -136,6 +154,19 @@ constexpr bool test() {
   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_iterator{+1};
+    assert(std::ranges::advance(i, INT_MIN, iota_iterator{-2}) == INT_MIN+3);
+    assert(i == iota_iterator{-2});
+    i = iota_iterator{+1};
+    assert(std::ranges::advance(i, -2, iota_iterator{INT_MIN+1}) == 0);
+    assert(i == iota_iterator{-1});
+    i = iota_iterator{+1};
+    assert(std::ranges::advance(i, INT_MIN, iota_iterator{INT_MIN+1}) == 0);
+    assert(i == iota_iterator{INT_MIN+1});
+  }
+
   return true;
 }