This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[PATCH] libstdc++: Implement integer-class types as defined in [iterator.concept.winc]
- From: Patrick Palka <ppalka at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Cc: libstdc++ at gcc dot gnu dot org, jwakely at redhat dot com, Patrick Palka <ppalka at redhat dot com>
- Date: Mon, 24 Feb 2020 15:16:23 -0500
- Subject: [PATCH] libstdc++: Implement integer-class types as defined in [iterator.concept.winc]
This implements signed and unsigned integer-class types, whose width is one bit
larger than the widest native signed and unsigned integral type respectively.
In our case this is either __int128 and unsigned __int128, or long long and
unsigned long long.
Internally, the two integer-class types are represented as a largest native
unsigned integral type plus one extra bit. The signed integer-class type is
represented in two's complement form with the extra bit acting as the sign bit.
libstdc++-v3/ChangeLog:
* include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type):
Remove definition, replace with forward declaration of class
__max_diff_type.
(ranges::__detail::__max_size_type): Remove definition, replace with
forward declaration of class __max_size_type.
(__detail::__is_integer_like): Accept __int128 and unsigned __int128.
(__detail::__is_signed_integer_like): Accept __int128.
* include/bits/range_access.h (__detail::__max_size_type): New class.
(__detail::__max_diff_type): New class.
(__detail::__max_size_type::__max_size_type): Define this constructor
out-of-line to break the cycle.
(__detail::__to_unsigned_like): New function.
(numeric_limits<__detail::__max_size_type>): New explicit specialization.
(numeric_limits<__detail::__max_diff_type>): New explicit specialization.
* testsuite/std/ranges/iota/differenc_type.cc: New test.
---
libstdc++-v3/include/bits/iterator_concepts.h | 15 +-
libstdc++-v3/include/bits/range_access.h | 678 +++++++++++++++++-
.../std/ranges/iota/difference_type.cc | 379 ++++++++++
3 files changed, 1064 insertions(+), 8 deletions(-)
create mode 100644 libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc
diff --git a/libstdc++-v3/include/bits/iterator_concepts.h b/libstdc++-v3/include/bits/iterator_concepts.h
index 08e622259b4..6eff0b82feb 100644
--- a/libstdc++-v3/include/bits/iterator_concepts.h
+++ b/libstdc++-v3/include/bits/iterator_concepts.h
@@ -482,20 +482,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
namespace ranges::__detail
{
-#if __SIZEOF_INT128__
- using __max_diff_type = __int128;
- using __max_size_type = unsigned __int128;
-#else
- using __max_diff_type = long long;
- using __max_size_type = unsigned long long;
-#endif
+ class __max_diff_type;
+ class __max_size_type;
template<typename _Tp>
concept __is_integer_like = integral<_Tp>
+#if __SIZEOF_INT128__
+ || same_as<_Tp, __int128> || same_as<_Tp, unsigned __int128>
+#endif
|| same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>;
template<typename _Tp>
concept __is_signed_integer_like = signed_integral<_Tp>
+#if __SIZEOF_INT128__
+ || same_as<_Tp, __int128>
+#endif
|| same_as<_Tp, __max_diff_type>;
} // namespace ranges::__detail
diff --git a/libstdc++-v3/include/bits/range_access.h b/libstdc++-v3/include/bits/range_access.h
index 8b276fd6625..08140b5e77d 100644
--- a/libstdc++-v3/include/bits/range_access.h
+++ b/libstdc++-v3/include/bits/range_access.h
@@ -351,6 +351,628 @@ namespace ranges
namespace __detail
{
+ // An unsigned integer-class type as per [iterator.concept.winc].
+ class __max_size_type
+ {
+ public:
+ __max_size_type() = default;
+
+ template<integral _Tp>
+ constexpr
+ __max_size_type(_Tp __i) noexcept
+ : _M_val(__i), _M_msb(__i < 0)
+ { }
+
+ constexpr explicit
+ __max_size_type(const __max_diff_type& __d) noexcept;
+
+ template<integral _Tp>
+ constexpr explicit operator _Tp() const noexcept
+ { return _M_val; }
+
+ constexpr explicit
+ operator bool() const noexcept
+ { return _M_val != 0 || _M_msb != 0; }
+
+ constexpr __max_size_type
+ operator+() const noexcept
+ { return *this; }
+
+ constexpr __max_size_type
+ operator~() const noexcept
+ { return __max_size_type{~_M_val, !_M_msb}; }
+
+ constexpr __max_size_type
+ operator-() const noexcept
+ { return operator~() + 1; }
+
+ constexpr __max_size_type&
+ operator+=(const __max_size_type& __r) noexcept
+ {
+ const auto __sum = _M_val + __r._M_val;
+ const bool __overflow = (__sum < _M_val);
+ _M_msb = _M_msb ^ __r._M_msb ^ __overflow;
+ _M_val = __sum;
+ return *this;
+ }
+
+ constexpr __max_size_type&
+ operator-=(const __max_size_type& __r) noexcept
+ { return *this += -__r; }
+
+ constexpr __max_size_type&
+ operator*=(__max_size_type __r) noexcept
+ {
+ const bool __lsb = _M_val & 1;
+ const bool __rlsb = __r._M_val & 1;
+
+ constexpr auto __threshold = __rep(1) << (__rep_bits / 2 - 1);
+ if (!_M_msb && !__r._M_msb
+ && _M_val < __threshold && __r._M_val < __threshold) [[likely]]
+ _M_val = _M_val * __r._M_val;
+ else
+ {
+ *this >>= 1;
+ __r >>= 1;
+ _M_val = (2 * _M_val * __r._M_val
+ + _M_val * __rlsb + __r._M_val * __lsb);
+ *this <<= 1;
+ *this += __rlsb * __lsb;
+ }
+
+ return *this;
+ }
+
+ constexpr __max_size_type&
+ operator/=(const __max_size_type& __r) noexcept
+ {
+ __glibcxx_assert(__r != 0);
+
+ if (!_M_msb && !__r._M_msb) [[likely]]
+ _M_val /= __r._M_val;
+ else if (_M_msb && __r._M_msb)
+ {
+ _M_val = (_M_val >= __r._M_val);
+ _M_msb = 0;
+ }
+ else if (!_M_msb && __r._M_msb)
+ _M_val = 0;
+ else if (_M_msb && !__r._M_msb)
+ {
+ const auto __orig = *this;
+ *this >>= 1;
+ _M_val /= __r._M_val;
+ *this <<= 1;
+ if (__orig - *this * __r >= __r)
+ ++_M_val;
+ }
+ return *this;
+ }
+
+ constexpr __max_size_type&
+ operator%=(const __max_size_type& __r) noexcept
+ {
+ if (!_M_msb && !__r._M_msb) [[likely]]
+ _M_val %= __r._M_val;
+ else
+ *this -= (*this / __r) * __r;
+ return *this;
+ }
+
+ constexpr __max_size_type&
+ operator<<=(const __max_size_type& __r) noexcept
+ {
+ __glibcxx_assert(__r < __rep_bits);
+ if (__r == 0)
+ return *this;
+ if (_M_val & (__rep(1) << (__rep_bits - __r._M_val)))
+ _M_msb = 1;
+ else
+ _M_msb = 0;
+ _M_val <<= __r._M_val;
+ return *this;
+ }
+
+ constexpr __max_size_type&
+ operator>>=(const __max_size_type& __r) noexcept
+ {
+ __glibcxx_assert(__r < __rep_bits);
+ if (__r == 0)
+ return *this;
+ _M_val >>= __r._M_val;
+ if (_M_msb) [[unlikely]]
+ {
+ _M_val |= __rep(1) << (__rep_bits - __r._M_val);
+ _M_msb = 0;
+ }
+ return *this;
+ }
+
+ constexpr __max_size_type&
+ operator&=(const __max_size_type& __r) noexcept
+ {
+ _M_val &= __r._M_val;
+ _M_msb &= __r._M_msb;
+ return *this;
+ }
+
+ constexpr __max_size_type&
+ operator|=(const __max_size_type& __r) noexcept
+ {
+ _M_val |= __r._M_val;
+ _M_msb |= __r._M_msb;
+ return *this;
+ }
+
+ constexpr __max_size_type&
+ operator^=(const __max_size_type& __r) noexcept
+ {
+ _M_val ^= __r._M_val;
+ _M_msb ^= __r._M_msb;
+ return *this;
+ }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator+=(_Tp& a, const __max_size_type& b) noexcept
+ { return (a = static_cast<_Tp>(a + b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator-=(_Tp& a, const __max_size_type& b) noexcept
+ { return (a = static_cast<_Tp>(a - b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator*=(_Tp& a, const __max_size_type& b) noexcept
+ { return (a = static_cast<_Tp>(a * b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator/=(_Tp& a, const __max_size_type& b) noexcept
+ { return (a = static_cast<_Tp>(a / b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator%=(_Tp& a, const __max_size_type& b) noexcept
+ { return (a = static_cast<_Tp>(a % b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator&=(_Tp& a, const __max_size_type& b) noexcept
+ { return (a = static_cast<_Tp>(a & b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator|=(_Tp& a, const __max_size_type& b) noexcept
+ { return (a = static_cast<_Tp>(a | b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator^=(_Tp& a, const __max_size_type& b) noexcept
+ { return (a = static_cast<_Tp>(a ^ b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator<<=(_Tp& a, const __max_size_type& b) noexcept
+ { return (a = static_cast<_Tp>(a << b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator>>=(_Tp& a, const __max_size_type& b) noexcept
+ { return (a = static_cast<_Tp>(a >> b)); }
+
+ friend constexpr __max_size_type
+ operator+(__max_size_type __l, const __max_size_type& __r) noexcept
+ {
+ __l += __r;
+ return __l;
+ }
+
+ friend constexpr __max_size_type
+ operator-(__max_size_type __l, const __max_size_type& __r) noexcept
+ {
+ __l -= __r;
+ return __l;
+ }
+
+ friend constexpr __max_size_type
+ operator*(__max_size_type __l, const __max_size_type& __r) noexcept
+ {
+ __l *= __r;
+ return __l;
+ }
+
+ friend constexpr __max_size_type
+ operator/(__max_size_type __l, const __max_size_type& __r) noexcept
+ {
+ __l /= __r;
+ return __l;
+ }
+
+ friend constexpr __max_size_type
+ operator%(__max_size_type __l, const __max_size_type& __r) noexcept
+ {
+ __l %= __r;
+ return __l;
+ }
+
+ friend constexpr __max_size_type
+ operator<<(__max_size_type __l, const __max_size_type& __r) noexcept
+ {
+ __l <<= __r;
+ return __l;
+ }
+
+ friend constexpr __max_size_type
+ operator>>(__max_size_type __l, const __max_size_type& __r) noexcept
+ {
+ __l >>= __r;
+ return __l;
+ }
+
+ friend constexpr __max_size_type
+ operator&(__max_size_type __l, const __max_size_type& __r) noexcept
+ {
+ __l &= __r;
+ return __l;
+ }
+
+ friend constexpr __max_size_type
+ operator|(__max_size_type __l, const __max_size_type& __r) noexcept
+ {
+ __l |= __r;
+ return __l;
+ }
+
+ friend constexpr __max_size_type
+ operator^(__max_size_type __l, const __max_size_type& __r) noexcept
+ {
+ __l ^= __r;
+ return __l;
+ }
+
+ friend constexpr bool
+ operator==(const __max_size_type& __l, const __max_size_type& __r) noexcept
+ { return __l._M_val == __r._M_val && __l._M_msb == __r._M_msb; }
+
+ friend constexpr bool
+ operator!=(const __max_size_type& __l, const __max_size_type& __r) noexcept
+ { return !(__l == __r); }
+
+ friend constexpr bool
+ operator<(const __max_size_type& __l, const __max_size_type& __r) noexcept
+ {
+ if (__l._M_msb == __r._M_msb)
+ return __l._M_val < __r._M_val;
+ else
+ return __r._M_msb;
+ }
+
+ friend constexpr bool
+ operator>(const __max_size_type& __l, const __max_size_type& __r) noexcept
+ { return __r < __l; }
+
+ friend constexpr bool
+ operator<=(const __max_size_type& __l, const __max_size_type& __r) noexcept
+ { return !(__l > __r); }
+
+ friend constexpr bool
+ operator>=(const __max_size_type& __l, const __max_size_type& __r) noexcept
+ { return __r <= __l; }
+
+#ifdef __SIZEOF_INT128__
+ using __rep = unsigned __int128;
+#else
+ using __rep = unsigned long long;
+#endif
+ static constexpr size_t __rep_bits = sizeof(__rep) * __CHAR_BIT__;
+ private:
+ __rep _M_val = 0;
+ unsigned _M_msb:1 = 0;
+
+ constexpr explicit
+ __max_size_type(__rep __val, int __msb) noexcept
+ : _M_val(__val), _M_msb(__msb)
+ { }
+
+ friend __max_diff_type;
+ friend std::numeric_limits<__max_size_type>;
+ friend std::numeric_limits<__max_diff_type>;
+ };
+
+ // A signed integer-class type as per [iterator.concept.winc].
+ class __max_diff_type
+ {
+ public:
+ __max_diff_type() = default;
+
+ template<integral _Tp>
+ constexpr
+ __max_diff_type(_Tp __i) noexcept
+ : _M_rep(__i)
+ { }
+
+ constexpr explicit
+ __max_diff_type(const __max_size_type& __d) noexcept
+ : _M_rep(__d)
+ { }
+
+ template<integral _Tp>
+ constexpr explicit operator _Tp() const noexcept
+ { return static_cast<_Tp>(_M_rep); }
+
+ constexpr explicit
+ operator bool() const noexcept
+ { return _M_rep != 0; }
+
+ constexpr __max_diff_type
+ operator+() const noexcept
+ { return *this; }
+
+ constexpr __max_diff_type
+ operator-() const noexcept
+ { return __max_diff_type(-_M_rep); }
+
+ constexpr __max_diff_type
+ operator~() const noexcept
+ { return __max_diff_type(~_M_rep); }
+
+ constexpr __max_diff_type&
+ operator+=(const __max_diff_type& __r) noexcept
+ {
+ _M_rep += __r._M_rep;
+ return *this;
+ }
+
+ constexpr __max_diff_type&
+ operator-=(const __max_diff_type& __r) noexcept
+ {
+ _M_rep -= __r._M_rep;
+ return *this;
+ }
+
+ constexpr __max_diff_type&
+ operator*=(const __max_diff_type& __r) noexcept
+ {
+ _M_rep *= __r._M_rep;
+ return *this;
+ }
+
+ constexpr __max_diff_type&
+ operator/=(const __max_diff_type& __r) noexcept
+ {
+ __glibcxx_assert (__r != 0);
+ const bool __neg = *this < 0;
+ const bool __rneg = __r < 0;
+ if (!__neg && !__rneg)
+ _M_rep = _M_rep / __r._M_rep;
+ else if (__neg && __rneg)
+ _M_rep = -_M_rep / -__r._M_rep;
+ else
+ _M_rep = -((__neg ? -_M_rep : _M_rep)
+ / (__rneg ? -__r._M_rep : __r._M_rep));
+ return *this ;
+ }
+
+ constexpr __max_diff_type&
+ operator%=(const __max_diff_type& __r) noexcept
+ {
+ __glibcxx_assert (__r != 0);
+ if (*this >= 0 && __r > 0)
+ _M_rep %= __r._M_rep;
+ else
+ *this -= (*this / __r) * __r;
+ return *this;
+ }
+
+ constexpr __max_diff_type&
+ operator<<=(const __max_diff_type& __r) noexcept
+ {
+ _M_rep.operator<<=(__r._M_rep);
+ return *this;
+ }
+
+ constexpr __max_diff_type&
+ operator>>=(const __max_diff_type& __r) noexcept
+ {
+ const auto __msb = _M_rep._M_msb;
+ _M_rep >>= __r._M_rep;
+ _M_rep._M_msb |= __msb;
+ return *this;
+ }
+
+ constexpr __max_diff_type&
+ operator&=(const __max_diff_type& __r) noexcept
+ {
+ _M_rep &= __r._M_rep;
+ return *this;
+ }
+
+ constexpr __max_diff_type&
+ operator|=(const __max_diff_type& __r) noexcept
+ {
+ _M_rep |= __r._M_rep;
+ return *this;
+ }
+
+ constexpr __max_diff_type&
+ operator^=(const __max_diff_type& __r) noexcept
+ {
+ _M_rep ^= __r._M_rep;
+ return *this;
+ }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator+=(_Tp& a, const __max_diff_type& b) noexcept
+ { return (a = static_cast<_Tp>(a + b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator-=(_Tp& a, const __max_diff_type& b) noexcept
+ { return (a = static_cast<_Tp>(a - b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator*=(_Tp& a, const __max_diff_type& b) noexcept
+ { return (a = static_cast<_Tp>(a * b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator/=(_Tp& a, const __max_diff_type& b) noexcept
+ { return (a = static_cast<_Tp>(a / b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator%=(_Tp& a, const __max_diff_type& b) noexcept
+ { return (a = static_cast<_Tp>(a % b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator&=(_Tp& a, const __max_diff_type& b) noexcept
+ { return (a = static_cast<_Tp>(a & b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator|=(_Tp& a, const __max_diff_type& b) noexcept
+ { return (a = static_cast<_Tp>(a | b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator^=(_Tp& a, const __max_diff_type& b) noexcept
+ { return (a = static_cast<_Tp>(a ^ b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator<<=(_Tp& a, const __max_diff_type& b) noexcept
+ { return (a = static_cast<_Tp>(a << b)); }
+
+ template<integral _Tp>
+ friend constexpr _Tp&
+ operator>>=(_Tp& a, const __max_diff_type& b) noexcept
+ { return (a = static_cast<_Tp>(a >> b)); }
+
+ friend constexpr __max_diff_type
+ operator+(__max_diff_type __l, const __max_diff_type& __r) noexcept
+ {
+ __l += __r;
+ return __l;
+ }
+
+ friend constexpr __max_diff_type
+ operator-(__max_diff_type __l, const __max_diff_type& __r) noexcept
+ {
+ __l -= __r;
+ return __l;
+ }
+
+ friend constexpr __max_diff_type
+ operator*(__max_diff_type __l, const __max_diff_type& __r) noexcept
+ {
+ __l *= __r;
+ return __l;
+ }
+
+ friend constexpr __max_diff_type
+ operator/(__max_diff_type __l, const __max_diff_type& __r) noexcept
+ {
+ __l /= __r;
+ return __l;
+ }
+
+ friend constexpr __max_diff_type
+ operator%(__max_diff_type __l, const __max_diff_type& __r) noexcept
+ {
+ __l %= __r;
+ return __l;
+ }
+
+ friend constexpr __max_diff_type
+ operator<<(__max_diff_type __l, const __max_diff_type& __r) noexcept
+ {
+ __l <<= __r;
+ return __l;
+ }
+
+ friend constexpr __max_diff_type
+ operator>>(__max_diff_type __l, const __max_diff_type& __r) noexcept
+ {
+ __l >>= __r;
+ return __l;
+ }
+
+ friend constexpr __max_diff_type
+ operator&(__max_diff_type __l, const __max_diff_type& __r) noexcept
+ {
+ __l &= __r;
+ return __l;
+ }
+
+ friend constexpr __max_diff_type
+ operator|(__max_diff_type __l, const __max_diff_type& __r) noexcept
+ {
+ __l |= __r;
+ return __l;
+ }
+
+ friend constexpr __max_diff_type
+ operator^(__max_diff_type __l, const __max_diff_type& __r) noexcept
+ {
+ __l ^= __r;
+ return __l;
+ }
+
+ friend constexpr bool
+ operator==(const __max_diff_type& __l, const __max_diff_type& __r) noexcept
+ { return __l._M_rep == __r._M_rep; }
+
+ friend constexpr bool
+ operator!=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept
+ { return !(__l == __r); }
+
+ constexpr bool
+ operator<(const __max_diff_type& __r) const noexcept
+ {
+ const auto __lsign = _M_rep._M_msb;
+ const auto __rsign = __r._M_rep._M_msb;
+ if (__lsign ^ __rsign)
+ return __lsign;
+ else
+ return _M_rep < __r._M_rep;
+ }
+
+ friend constexpr bool
+ operator>(const __max_diff_type& __l, const __max_diff_type& __r) noexcept
+ { return __r < __l; }
+
+ friend constexpr bool
+ operator<=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept
+ { return !(__r < __l); }
+
+ friend constexpr bool
+ operator>=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept
+ { return !(__l < __r); }
+
+ private:
+ __max_size_type _M_rep = 0;
+
+ friend class __max_size_type;
+ };
+
+ constexpr
+ __max_size_type::__max_size_type(const __max_diff_type& __d) noexcept
+ : __max_size_type(__d._M_rep)
+ { }
+
+ constexpr __max_size_type
+ __to_unsigned_like(__max_size_type __t) noexcept
+ { return __t; }
+
+ constexpr __max_size_type
+ __to_unsigned_like(__max_diff_type __t) noexcept
+ { return __max_size_type(__t); }
+
template<integral _Tp>
constexpr make_unsigned_t<_Tp>
__to_unsigned_like(_Tp __t) noexcept
@@ -359,13 +981,67 @@ namespace ranges
template<typename _Tp, bool _MaxDiff = same_as<_Tp, __max_diff_type>>
using __make_unsigned_like_t
= conditional_t<_MaxDiff, __max_size_type, make_unsigned_t<_Tp>>;
+ } // namespace __detail
+} // namespace ranges
+
+ template<>
+ struct numeric_limits<ranges::__detail::__max_size_type>
+ {
+ using _Sp = ranges::__detail::__max_size_type;
+ static constexpr bool is_specialized = true;
+ static constexpr bool is_signed = false;
+ static constexpr bool is_integer = true;
+ static constexpr bool is_exact = true;
+ static constexpr int digits = numeric_limits<_Sp::__rep>::digits + 1;
+ static constexpr int digits10 = numeric_limits<_Sp::__rep>::digits10;
+
+ static constexpr _Sp
+ min() noexcept
+ { return 0; }
+
+ static constexpr _Sp
+ max() noexcept
+ { return _Sp(numeric_limits<_Sp::__rep>::max(), 1); }
+
+ static constexpr _Sp
+ lowest() noexcept
+ { return min(); }
+ };
+
+ template<>
+ struct numeric_limits<ranges::__detail::__max_diff_type>
+ {
+ using _Dp = ranges::__detail::__max_diff_type;
+ using _Sp = ranges::__detail::__max_size_type;
+ static constexpr bool is_specialized = true;
+ static constexpr bool is_signed = true;
+ static constexpr bool is_integer = true;
+ static constexpr bool is_exact = true;
+ static constexpr int digits = numeric_limits<_Sp>::digits - 1;
+ static constexpr int digits10 = numeric_limits<_Sp>::digits10;
+
+ static constexpr _Dp
+ min() noexcept
+ { return _Dp(_Sp(0, 1)); }
+
+ static constexpr _Dp
+ max() noexcept
+ { return _Dp(_Sp(numeric_limits<_Sp::__rep>::max(), 0)); }
+
+ static constexpr _Dp
+ lowest() noexcept
+ { return min(); }
+ };
+namespace ranges
+{
+ namespace __detail
+ {
// Part of the constraints of ranges::borrowed_range
template<typename _Tp>
concept __maybe_borrowed_range
= is_lvalue_reference_v<_Tp>
|| enable_borrowed_range<remove_cvref_t<_Tp>>;
-
} // namespace __detail
namespace __cust_access
diff --git a/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc
new file mode 100644
index 00000000000..ef671a4a21b
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc
@@ -0,0 +1,379 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <ranges>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+ using I = unsigned long long;
+ auto imax = std::numeric_limits<I>::max();
+ std::ranges::iota_view<I, I> i(0, imax);
+ auto begin = i.begin();
+ static_assert( std::input_or_output_iterator<decltype(begin)> );
+ auto size = std::ranges::end(i) - std::ranges::begin(i);
+ VERIFY( size > 0 );
+ VERIFY( size == imax );
+}
+
+void
+test02()
+{
+#if __SIZEOF_INT128__
+ using I = unsigned __int128;
+ auto imax = std::numeric_limits<I>::max();
+ std::ranges::iota_view<I, I> i(0, imax);
+ auto begin = i.begin();
+ static_assert( std::input_or_output_iterator<decltype(begin)> );
+ auto size = std::ranges::end(i) - std::ranges::begin(i);
+ VERIFY( size > 0 );
+ VERIFY( size == imax );
+#endif
+}
+
+// The following are correctness tests for the arithmetic operations on
+// __max_size_type and __max_diff_type.
+
+using max_size_t = std::ranges::__detail::__max_size_type;
+using max_diff_t = std::ranges::__detail::__max_diff_type;
+using rep_t = max_size_t::__rep;
+
+static_assert(sizeof(max_size_t) == sizeof(max_diff_t));
+
+static_assert(std::regular<max_size_t>);
+static_assert(std::totally_ordered<max_size_t>);
+
+static_assert(std::regular<max_diff_t>);
+static_assert(std::totally_ordered<max_diff_t>);
+
+void
+test03()
+{
+ static_assert(max_size_t(7) % 3 == 1);
+ static_assert(max_size_t(7) % 4 == 3);
+
+ static_assert(-max_diff_t(1) == max_diff_t(-1));
+ static_assert(max_diff_t(3) % 2 == 1);
+ static_assert(max_diff_t(-3) / 2 == -1);
+ static_assert(max_diff_t(-3) % 2 == -1);
+ static_assert(max_diff_t(3) % -2 == 1);
+ static_assert(max_diff_t(-3) << 1 == -6);
+ static_assert(max_diff_t(-3) >> 1 == -2);
+ static_assert(max_diff_t(3) >> 1 == 1);
+ static_assert(max_diff_t(3) >> 2 == 0);
+
+ static_assert(max_diff_t(-5) / 3 == -1);
+ static_assert(max_diff_t(5) / -3 == -1);
+ static_assert(max_diff_t(-5) / -3 == 1);
+ static_assert(max_diff_t(5) / 3 == 1);
+
+ static_assert(max_diff_t(-6) / 3 == -2);
+ static_assert(max_diff_t(6) / -3 == -2);
+ static_assert(max_diff_t(-6) / -3 == 2);
+ static_assert(max_diff_t(6) / 3 == 2);
+
+ static_assert(~max_size_t(-3) == 2);
+ static_assert(~max_diff_t(-3) == 2);
+
+ static_assert(max_diff_t(1) < max_diff_t(3));
+ static_assert(max_diff_t(-1) < max_diff_t(3));
+ static_assert(max_diff_t(1) > max_diff_t(-3));
+ static_assert(max_diff_t(-1) > max_diff_t(-3));
+
+ constexpr max_size_t mu = std::numeric_limits<rep_t>::max();
+
+ static_assert(max_diff_t(mu)/-1 == -max_diff_t(mu));
+ static_assert(-max_diff_t(mu)/1 == -max_diff_t(mu));
+ static_assert(max_diff_t(mu)>>1 == max_diff_t(mu)/2);
+ static_assert(-max_diff_t(mu+1) == max_diff_t(mu+1));
+ static_assert(-(mu+1) == mu+1);
+ static_assert((mu+1)<<1 == 0);
+ static_assert(max_diff_t(mu+1)<<1 == 0);
+ static_assert(max_diff_t(mu+1)>>1 < 0);
+
+ static_assert(int(max_diff_t(mu+1)) == 0);
+ static_assert(rep_t(max_diff_t(mu+1)) == 0);
+ static_assert(int(max_diff_t(mu)) == -1);
+ static_assert(rep_t(max_diff_t(mu)) == rep_t(-1));
+
+ static_assert(2*mu+1 > 2*mu);
+ static_assert(~(2*mu+1) == 0);
+ static_assert(mu/mu == 1);
+ static_assert(2*mu > mu);
+ static_assert(2*mu-mu == mu);
+ static_assert((2*mu)/mu == 2);
+ static_assert((2*mu+1)/mu == 2);
+ static_assert((2*mu-1)/(mu-1) == 2);
+ static_assert((2*mu-1)/mu == 1);
+ static_assert((2*mu+-1)/mu == 1);
+ static_assert(2*mu-1 < 2*mu);
+ static_assert(2*mu-1 <= 2*mu);
+ static_assert(2*mu+1 > 2*mu);
+ static_assert(2*mu+1 >= 2*mu);
+ static_assert((2*mu)/1 == 2*mu);
+ static_assert(mu/mu-1 == 0);
+ static_assert(mu*0 == 0);
+ static_assert((2*mu-1)*0 == 0);
+ static_assert((2*mu-1)>>1 == mu-1);
+ static_assert(mu+-1+1 == mu);
+ static_assert(mu+1+-1 == mu);
+ static_assert(mu+1);
+ static_assert((2*mu)/2 == mu);
+ static_assert((2*mu)>>1 == mu);
+ static_assert((mu<<1)>>1 == mu);
+ static_assert(1/mu == 0);
+ static_assert(mu/1 == mu);
+ static_assert(((mu+1)|mu) == -1);
+ static_assert((mu+1)+(mu+1) < mu+1);
+
+ constexpr max_size_t ou = 1;
+ constexpr max_diff_t ns = -1;
+
+ static_assert(max_size_t(ns) == -1);
+ static_assert(-max_diff_t(ou) == -1);
+ static_assert(-max_diff_t(-ou) == 1);
+ static_assert(max_size_t(-max_diff_t(-ou)) == 1);
+ static_assert(ns*ns == max_diff_t(ou));
+ static_assert(max_size_t(ns)*max_size_t(ns) == ou);
+ static_assert(-max_diff_t(0) == max_diff_t(0));
+ static_assert(-ou-ou == -2*ou);
+
+ static_assert(int(ns) == -1);
+ static_assert(rep_t(ns) == rep_t(-1));
+
+ static_assert(max_size_t() == 0);
+ static_assert(max_diff_t() == 0);
+
+ auto f = [] (auto a) { a /= a; return a; };
+ static_assert(f(max_size_t(5)) == 1);
+ static_assert(f(max_size_t(-5)) == 1);
+ static_assert(f(max_diff_t(5)) == 1);
+
+ auto g = [] (auto a) { a >>= a; return a; };
+ static_assert(g(max_size_t(5)) == 0);
+ static_assert(g(max_diff_t(5)) == 0);
+
+ auto h = [] (auto a) { a <<= a; return a; };
+ static_assert(h(max_size_t(3)) == 24);
+ static_assert(h(max_diff_t(3)) == 24);
+}
+
+template<bool signed_p, bool shorten_p>
+void
+test04()
+{
+ using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>;
+ using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>;
+ using shorten_type = std::conditional_t<shorten_p, hw_type, max_type>;
+ const int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__;
+ const int limit = 1000;
+ const int log2_limit = 10;
+ static_assert((1 << log2_limit) >= limit);
+ const int min = (signed_p ? -limit : 0);
+ const int max = limit;
+ for (hw_type i = min; i <= max; i++)
+ {
+ bool ok = true;
+ if (signed_p || shorten_p)
+ {
+ ok &= (~i == shorten_type(~max_type(i)));
+ ok &= (-i == shorten_type(-max_type(i)));
+ }
+ for (hw_type j = min; j <= max; j++)
+ {
+ ok &= (i*j == shorten_type(max_type(i)*j));
+ ok &= (i+j == shorten_type(max_type(i)+j));
+ if (j != 0)
+ {
+ ok &= (i/j == shorten_type(max_type(i)/j));
+ ok &= (i%j == shorten_type(max_type(i)%j));
+ }
+ if (signed_p || shorten_p)
+ ok &= (i-j == shorten_type(max_type(i)-j));
+ ok &= ((i&j) == shorten_type(max_type(i)&j));
+ ok &= ((i|j) == shorten_type(max_type(i)|j));
+ ok &= ((i^j) == shorten_type(max_type(i)^j));
+ if (j >= 0 && j < hw_type(hw_type_bit_size)
+ && (shorten_p || j < hw_type(hw_type_bit_size) - log2_limit))
+ {
+ ok &= ((i>>j) == shorten_type(max_type(i)>>j));
+ ok &= ((i<<j) == shorten_type(max_type(i)<<j));
+ }
+ ok &= (i>j) == (max_type(i) > j);
+ ok &= (i<j) == (max_type(i) < j);
+ ok &= (i>=j) == (max_type(i) >= j);
+ ok &= (i<=j) == (max_type(i) <= j);
+ ok &= (i==j) == (max_type(i) == j);
+ ok &= (i!=j) == (max_type(i) != j);
+ if (!ok)
+ {
+ fprintf(stderr,
+ "Inconsistency found: %d %d %lld %lld\n",
+ signed_p, shorten_p, (long long)i, (long long)j) ;
+ VERIFY(0);
+ }
+ }
+ }
+}
+
+template<bool signed_p, bool toggle_base_p>
+void
+test05()
+{
+ using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>;
+ using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>;
+ using base_type = std::conditional_t<toggle_base_p, hw_type, max_type>;
+ constexpr int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__;
+ constexpr int limit = 1000;
+ constexpr int log2_limit = 10;
+ static_assert((1 << log2_limit) >= limit);
+ const int min = (signed_p ? -limit : 0);
+ const int max = limit;
+ for (hw_type i = min; i <= max; i++)
+ {
+ bool ok = true;
+ base_type k;
+ for (hw_type j = min; j <= max; j++)
+ {
+ k = i; k *= j;
+ ok &= (k == (max_type(i)*j));
+ k = i; k += j;
+ ok &= (k == (max_type(i)+j));
+ if (j != 0)
+ {
+ k = i; k /= j;
+ ok &= (k == (max_type(i)/j));
+ k = i; k %= j;
+ ok &= (k == (max_type(i)%j));
+ }
+ if (signed_p)
+ {
+ k = i; k -= j;
+ ok &= (k == (max_type(i)-j));
+ }
+ k = i; k &= j;
+ ok &= (k == (max_type(i)&j));
+ k = i; k |= j;
+ ok &= (k == (max_type(i)|j));
+ k = i; k ^= j;
+ ok &= (k == (max_type(i)^j));
+ if (j >= 0 && j < hw_type(hw_type_bit_size)
+ && (!toggle_base_p || j < hw_type(hw_type_bit_size) - log2_limit))
+ {
+ k = i; k >>= j;
+ ok &= (k == (max_type(i)>>j));
+ k = i; k <<= j;
+ ok &= (k == (max_type(i)<<j));
+ }
+ if (!ok)
+ {
+ fprintf(stderr,
+ "Inconsistency found: %d %d %lld %lld\n",
+ signed_p, toggle_base_p, (long long)i, (long long)j) ;
+ VERIFY(0);
+ }
+ }
+ }
+}
+
+void
+test06()
+{
+ constexpr max_size_t mu = std::numeric_limits<rep_t>::max();
+ const int limit = 1000;
+ for (int i = -limit; i <= limit; i++)
+ {
+ VERIFY( -max_size_t(-i) == i );
+ for (int j = i; j <= limit; j++)
+ {
+ VERIFY( max_size_t(-i) * max_size_t(-j) == i*j );
+ VERIFY( max_size_t(-j) * max_size_t(-i) == j*i );
+ VERIFY( rep_t(((mu+1)+i)*((mu+1)+j)) == rep_t(i*j) );
+ VERIFY( rep_t(((mu+1)+j)*((mu+1)+i)) == rep_t(j*i) );
+ if (i >= 0 && j > 0)
+ {
+ auto r = (mu+i)-((mu+i)/j)*j;
+ VERIFY( r >= 0 && r < j );
+ VERIFY( r == (mu+i)%j );
+ }
+ }
+ }
+}
+
+using std::numeric_limits;
+
+static_assert(numeric_limits<max_size_t>::is_specialized);
+static_assert(!numeric_limits<max_size_t>::is_signed);
+static_assert(numeric_limits<max_size_t>::is_integer);
+static_assert(numeric_limits<max_size_t>::is_exact);
+#if __SIZEOF_INT128__
+static_assert(numeric_limits<max_size_t>::digits == 129);
+static_assert(numeric_limits<max_size_t>::digits10 == 38);
+#else
+static_assert(numeric_limits<max_size_t>::digits == 65);
+static_assert(numeric_limits<max_size_t>::digits == 19);
+#endif
+static_assert(numeric_limits<max_size_t>::min() == 0);
+static_assert(numeric_limits<max_size_t>::max() == max_size_t(-1));
+static_assert(numeric_limits<max_size_t>::lowest()
+ == numeric_limits<max_size_t>::min());
+
+static_assert(numeric_limits<max_diff_t>::is_specialized);
+static_assert(numeric_limits<max_diff_t>::is_signed);
+static_assert(numeric_limits<max_diff_t>::is_integer);
+static_assert(numeric_limits<max_diff_t>::is_exact);
+#if __SIZEOF_INT128__
+static_assert(numeric_limits<max_diff_t>::digits == 128);
+static_assert(numeric_limits<max_diff_t>::digits10 == 38);
+static_assert(numeric_limits<max_diff_t>::min()
+ == -max_diff_t(numeric_limits<unsigned __int128>::max())-1);
+static_assert(numeric_limits<max_diff_t>::max()
+ == numeric_limits<unsigned __int128>::max());
+#else
+static_assert(numeric_limits<max_diff_t>::digits == 64);
+static_assert(numeric_limits<max_diff_t>::digits == 19);
+static_assert(numeric_limits<max_diff_t>::min()
+ == -max_diff_t(numeric_limits<int64_t>::max())-1);
+static_assert(numeric_limits<max_diff_t>::max()
+ == numeric_limits<int64_t>::max());
+#endif
+static_assert(numeric_limits<max_diff_t>::lowest()
+ == numeric_limits<max_diff_t>::min());
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+
+ test04<false,false>();
+ test04<false,true>();
+ test04<true,false>();
+ test04<true,true>();
+
+ test05<false,false>();
+ test05<false,true>();
+ test05<true,false>();
+ test05<true,true>();
+
+ test06();
+}
--
2.25.1.291.ge68e29171c