From e6c76f0d3327bf00c96f5a63961c1d5ab77512db Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Wed, 19 Aug 2020 09:12:55 -0400 Subject: [PATCH] libstdc++: integer-class types as per [iterator.concept.winc] This implements signed and unsigned integer-class types, whose width is one bit larger than the widest supported 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 supported 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/Makefile.am (bits_headers): Add new header . * include/Makefile.in: Regenerate. * include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type): Remove definition, replace with forward declaration of class __max_diff_type. (__detail::__max_size_type): Remove definition, replace with forward declaration of class __max_size_type. (__detail::__is_unsigned_int128, __is_signed_int128) (__is_int128): New concepts. (__detail::__is_integer_like): Accept __int128 and unsigned __int128. (__detail::__is_signed_integer_like): Accept __int128. * include/bits/max_size_type.h: New header. * include/bits/range_access.h: Include . (__detail::__to_unsigned_like): Two new overloads. * testsuite/std/ranges/iota/difference_type.cc: New test. * testsuite/std/ranges/iota/max_size_type.cc: New test. --- libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/iterator_concepts.h | 24 +- libstdc++-v3/include/bits/max_size_type.h | 753 ++++++++++++++++++ libstdc++-v3/include/bits/range_access.h | 11 + .../std/ranges/iota/difference_type.cc | 57 ++ .../std/ranges/iota/max_size_type.cc | 376 +++++++++ 7 files changed, 1219 insertions(+), 4 deletions(-) create mode 100644 libstdc++-v3/include/bits/max_size_type.h create mode 100644 libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc create mode 100644 libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index e131ce04f8c..1dff3862e35 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -143,6 +143,7 @@ bits_headers = \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index c0b71e13a32..16371015071 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -489,6 +489,7 @@ bits_headers = \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/bits/iterator_concepts.h b/libstdc++-v3/include/bits/iterator_concepts.h index aad6c2dcd91..5033f2bddc3 100644 --- a/libstdc++-v3/include/bits/iterator_concepts.h +++ b/libstdc++-v3/include/bits/iterator_concepts.h @@ -511,12 +511,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace ranges::__detail { + class __max_diff_type; + class __max_size_type; + + template + concept __is_signed_int128 #if __SIZEOF_INT128__ - using __max_diff_type = __int128; - using __max_size_type = unsigned __int128; + = same_as<_Tp, __int128>; #else - using __max_diff_type = long long; - using __max_size_type = unsigned long long; + = false; +#endif + + template + concept __is_unsigned_int128 +#if __SIZEOF_INT128__ + = same_as<_Tp, unsigned __int128>; +#else + = false; #endif template @@ -525,12 +536,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template concept __integral_nonbool = integral<_Tp> && !__cv_bool<_Tp>; + template + concept __is_int128 = __is_signed_int128<_Tp> || __is_unsigned_int128<_Tp>; + template concept __is_integer_like = __integral_nonbool<_Tp> + || __is_int128<_Tp> || same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>; template concept __is_signed_integer_like = signed_integral<_Tp> + || __is_signed_int128<_Tp> || same_as<_Tp, __max_diff_type>; } // namespace ranges::__detail diff --git a/libstdc++-v3/include/bits/max_size_type.h b/libstdc++-v3/include/bits/max_size_type.h new file mode 100644 index 00000000000..8e616626c80 --- /dev/null +++ b/libstdc++-v3/include/bits/max_size_type.h @@ -0,0 +1,753 @@ +// -*- C++ -*- + +// Copyright (C) 2019-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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file bits/max_size_type.h. + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{iterator} + */ + +#ifndef _GLIBCXX_MAX_SIZE_TYPE_H +#define _GLIBCXX_MAX_SIZE_TYPE_H 1 + +#pragma GCC system_header + +#if __cplusplus > 201703L && __cpp_lib_concepts +#include +#include + +// This header implements unsigned and signed integer-class types (as per +// [iterator.concept.winc]) that are one bit wider than the widest supported +// integer type. +// +// The set of integer types we consider includes __int128 and unsigned __int128 +// (when they exist), even though they are really integer types only in GNU +// mode. This is to obtain a consistent ABI for these integer-class types +// across strict mode and GNU mode. + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + +template + struct numeric_limits; + +namespace ranges +{ + namespace __detail + { + class __max_size_type + { + public: + __max_size_type() = default; + + template requires integral<_Tp> || __is_int128<_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 requires integral<_Tp> || __is_int128<_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 + { + constexpr __max_size_type __threshold + = __rep(1) << (_S_rep_bits / 2 - 1); + if (_M_val < __threshold && __r < __threshold) + // When both operands are below this threshold then the + // multiplication can be safely computed in the base precision. + _M_val = _M_val * __r._M_val; + else + { + // Otherwise, perform the multiplication in four steps, by + // decomposing the LHS and the RHS into 2*x+a and 2*y+b, + // respectively, and computing 4*x*y + 2*x*b + 2*y*a + a*b. + const bool __lsb = _M_val & 1; + const bool __rlsb = __r._M_val & 1; + *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) + { + // The non-trivial case: the dividend has its MSB set and the + // divisor doesn't. In this case we compute ((LHS/2)/RHS)*2 + // in the base precision. This quantity is either the true + // quotient or one less than the true quotient. + 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 <= _S_rep_bits); + if (__r != 0) + { + _M_msb = (_M_val >> (_S_rep_bits - __r._M_val)) & 1; + + if (__r._M_val == _S_rep_bits) [[unlikely]] + _M_val = 0; + else + _M_val <<= __r._M_val; + } + return *this; + } + + constexpr __max_size_type& + operator>>=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r <= _S_rep_bits); + if (__r != 0) + { + if (__r._M_val == _S_rep_bits) [[unlikely]] + _M_val = 0; + else + _M_val >>= __r._M_val; + + if (_M_msb) [[unlikely]] + { + _M_val |= __rep(1) << (_S_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 requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator+=(_Tp& __a, const __max_size_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a + __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator-=(_Tp& __a, const __max_size_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a - __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator*=(_Tp& __a, const __max_size_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a * __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator/=(_Tp& __a, const __max_size_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a / __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator%=(_Tp& __a, const __max_size_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a % __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator&=(_Tp& __a, const __max_size_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a & __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator|=(_Tp& __a, const __max_size_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a | __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator^=(_Tp& __a, const __max_size_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a ^ __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator<<=(_Tp& __a, const __max_size_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a << __b)); } + + template requires integral<_Tp> || __is_int128<_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; } + +#if __SIZEOF_INT128__ + using __rep = unsigned __int128; +#else + using __rep = unsigned long long; +#endif + static constexpr size_t _S_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>; + }; + + class __max_diff_type + { + public: + __max_diff_type() = default; + + template requires integral<_Tp> || __is_int128<_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 requires integral<_Tp> || __is_int128<_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 if (__neg && !__rneg) + _M_rep = -(-_M_rep / __r._M_rep); + else + _M_rep = -(_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 + { + // Arithmetic right shift. + 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 requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator+=(_Tp& __a, const __max_diff_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a + __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator-=(_Tp& __a, const __max_diff_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a - __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator*=(_Tp& __a, const __max_diff_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a * __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator/=(_Tp& __a, const __max_diff_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a / __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator%=(_Tp& __a, const __max_diff_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a % __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator&=(_Tp& __a, const __max_diff_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a & __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator|=(_Tp& __a, const __max_diff_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a | __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator^=(_Tp& __a, const __max_diff_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a ^ __b)); } + + template requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator<<=(_Tp& __a, const __max_diff_type& __b) noexcept + { return (__a = static_cast<_Tp>(__a << __b)); } + + template requires integral<_Tp> || __is_int128<_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) + { } + + } // namespace __detail +} // namespace ranges + + template<> + struct numeric_limits + { + 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; +#if __SIZEOF_INT128__ + static_assert(same_as<_Sp::__rep, unsigned __int128>); + static constexpr int digits = 129; +#else + static_assert(same_as<_Sp::__rep, unsigned long long>); + static constexpr int digits + = __gnu_cxx::__int_traits::__digits + 1; +#endif + static constexpr int digits10 + = static_cast(digits * numbers::ln2 / numbers::ln10); + + static constexpr _Sp + min() noexcept + { return 0; } + + static constexpr _Sp + max() noexcept + { return _Sp(static_cast<_Sp::__rep>(-1), 1); } + + static constexpr _Sp + lowest() noexcept + { return min(); } + }; + + template<> + struct numeric_limits + { + 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 + = static_cast(digits * numbers::ln2 / numbers::ln10); + + static constexpr _Dp + min() noexcept + { return _Dp(_Sp(0, 1)); } + + static constexpr _Dp + max() noexcept + { return _Dp(_Sp(static_cast<_Sp::__rep>(-1), 0)); } + + static constexpr _Dp + lowest() noexcept + { return min(); } + }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif // C++20 && library concepts +#endif // _GLIBCXX_MAX_SIZE_TYPE_H diff --git a/libstdc++-v3/include/bits/range_access.h b/libstdc++-v3/include/bits/range_access.h index 3919183c5b4..3eb1f2fd272 100644 --- a/libstdc++-v3/include/bits/range_access.h +++ b/libstdc++-v3/include/bits/range_access.h @@ -36,6 +36,9 @@ #include #include #include +#if __cplusplus > 201703L +#include +#endif namespace std _GLIBCXX_VISIBILITY(default) { @@ -352,6 +355,14 @@ namespace ranges namespace __detail { + 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 constexpr make_unsigned_t<_Tp> __to_unsigned_like(_Tp __t) noexcept 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..6eb1a1676f7 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc @@ -0,0 +1,57 @@ +// 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 +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include + +void +test01() +{ + using I = unsigned long long; + auto imax = std::numeric_limits::max(); + std::ranges::iota_view i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +} + +void +test02() +{ +#if !defined(__STRICT_ANSI__) && __SIZEOF_INT128__ + using I = unsigned __int128; + auto imax = std::numeric_limits::max(); + std::ranges::iota_view i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +#endif +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc b/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc new file mode 100644 index 00000000000..cb9444074fc --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc @@ -0,0 +1,376 @@ +// 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 +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include +#include + +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); +static_assert(std::totally_ordered); + +static_assert(std::regular); +static_assert(std::totally_ordered); + +// We can't use numeric_limits::max() here because __int128 is an +// integral type only in GNU mode. +constexpr max_size_t mu = max_size_t(~rep_t(0)); +constexpr max_size_t ou = 1; +constexpr max_diff_t ns = -1; + +void +test01() +{ + 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)); + + 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); + + 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 +void +test02() +{ + using hw_type = std::conditional_t; + using max_type = std::conditional_t; + using shorten_type = std::conditional_t; + 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) == (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 +void +test03() +{ + using hw_type = std::conditional_t; + using max_type = std::conditional_t; + using base_type = std::conditional_t; + 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)<= 0 && j > 0) + { + auto r = (mu+i)-((mu+i)/j)*j; + VERIFY( r >= 0 && r < j ); + VERIFY( r == (mu+i)%j ); + } + } + } +} + +void +test05() +{ +#if __SIZEOF_INT128__ + max_size_t x = 0; + x = static_cast<__int128>(0); + x = static_cast(0); + + max_diff_t y = 0; + y = static_cast<__int128>(0);; + y = static_cast(0); +#endif +} + +using std::numeric_limits; + +static_assert(numeric_limits::is_specialized); +static_assert(!numeric_limits::is_signed); +static_assert(numeric_limits::is_integer); +static_assert(numeric_limits::is_exact); +// We can't unconditionally use numeric_limits here because __int128 is an +// integral type only in GNU mode. +#if __SIZEOF_INT128__ +static_assert(numeric_limits::digits == 129); +static_assert(numeric_limits::digits10 == 38); +static_assert(numeric_limits::max() + == 2*max_size_t(~rep_t(0)) + 1); +#else +static_assert(numeric_limits::digits + == numeric_limits::digits + 1); +static_assert(numeric_limits::digits10 + == numeric_limits::digits10); +static_assert(numeric_limits::max() + == 2*max_size_t(numeric_limits::max())+1); +#endif +static_assert(numeric_limits::min() == 0); +static_assert(numeric_limits::max() + == max_size_t(-1)); +static_assert((numeric_limits::max() + >> (numeric_limits::digits-1)) == 1); +static_assert(numeric_limits::lowest() + == numeric_limits::min()); + +static_assert(numeric_limits::is_specialized); +static_assert(numeric_limits::is_signed); +static_assert(numeric_limits::is_integer); +static_assert(numeric_limits::is_exact); +static_assert(numeric_limits::digits + == numeric_limits::digits - 1); +static_assert(numeric_limits::digits10 + == numeric_limits::digits10); +// We can't unconditionally use numeric_limits here because __int128 is an +// integral type only in GNU mode. +#if __SIZEOF_INT128__ +static_assert(numeric_limits::min() == -max_diff_t(~rep_t(0))-1); +static_assert(numeric_limits::max() == ~rep_t(0)); +#else +static_assert(numeric_limits::min() + == -max_diff_t(numeric_limits::max())-1); +static_assert(numeric_limits::max() + == numeric_limits::max()); +#endif +static_assert(numeric_limits::lowest() + == numeric_limits::min()); +static_assert(max_diff_t(max_size_t(1) + << (numeric_limits::digits-1)) + == numeric_limits::min()); + +int +main() +{ + test01(); + + test02(); + test02(); + test02(); + test02(); + + test03(); + test03(); + test03(); + test03(); + + test04(); + test05(); +} -- 2.30.2