diff options
author | Arthur O'Dwyer <arthur.j.odwyer@gmail.com> | 2021-07-23 22:05:31 -0400 |
---|---|---|
committer | Arthur O'Dwyer <arthur.j.odwyer@gmail.com> | 2021-07-26 16:41:21 -0400 |
commit | 41b17c444df647ce46609d8efb57a98d35704c63 (patch) | |
tree | 2920b9038d48a3e87b0679006ad4a1edaa044be6 /libcxx | |
parent | 25666a74c5af05ae6b189ad4f7382d351fb8698f (diff) | |
download | llvm-41b17c444df647ce46609d8efb57a98d35704c63.zip llvm-41b17c444df647ce46609d8efb57a98d35704c63.tar.gz llvm-41b17c444df647ce46609d8efb57a98d35704c63.tar.bz2 |
[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
Diffstat (limited to 'libcxx')
-rw-r--r-- | libcxx/include/__iterator/advance.h | 8 | ||||
-rw-r--r-- | libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/iterator_count_sentinel.pass.cpp | 31 |
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; } |