[gcc(refs/users/marxin/heads/if-to-switch-v2)] libstdc++: Fix std::gcd and std::lcm for unsigned integers [PR 92978]

[gcc(refs/users/marxin/heads/if-to-switch-v2)] libstdc++: Fix std::gcd and std::lcm for unsigned integers [PR 92978]

[Martin Liska]

https://gcc.gnu.org/g:82db1a42e9254c9009bbf8ac01366da4d1ab6df5

commit 82db1a42e9254c9009bbf8ac01366da4d1ab6df5
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Aug 28 22:45:24 2020 +0100

    libstdc++: Fix std::gcd and std::lcm for unsigned integers [PR 92978]
    
    This fixes a bug with mixed signed and unsigned types, where converting
    a negative value to the unsigned result type alters the value. The
    solution is to obtain the absolute values of the arguments immediately
    and to perform the actual GCD or LCM algorithm on two arguments of the
    same type.
    
    In order to operate on the most negative number without overflow when
    taking its absolute, use an unsigned type for the result of the abs
    operation. For example, -INT_MIN will overflow, but -(unsigned)INT_MIN
    is (unsigned)INT_MAX+1U which is the correct value.
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/92978
            * include/std/numeric (__abs_integral): Replace with ...
            (__detail::__absu): New function template that returns an
            unsigned type, guaranteeing it can represent the most
            negative signed value.
            (__detail::__gcd, __detail::__lcm): Require arguments to
            be unsigned and therefore already non-negative.
            (gcd, lcm): Convert arguments to absolute value as unsigned
            type before calling __detail::__gcd or __detail::__lcm.
            * include/experimental/numeric (gcd, lcm): Likewise.
            * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust expected
            errors.
            * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
            * testsuite/26_numerics/gcd/92978.cc: New test.
            * testsuite/26_numerics/lcm/92978.cc: New test.
            * testsuite/experimental/numeric/92978.cc: New test.

Diff:
---
 libstdc++-v3/include/experimental/numeric          | 38 ++++++----
 libstdc++-v3/include/std/numeric                   | 83 +++++++++++-----------
 libstdc++-v3/testsuite/26_numerics/gcd/92978.cc    | 40 +++++++++++
 libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc  | 11 ++-
 libstdc++-v3/testsuite/26_numerics/lcm/92978.cc    | 27 +++++++
 libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc  | 11 ++-
 .../testsuite/experimental/numeric/92978.cc        | 48 +++++++++++++
 7 files changed, 190 insertions(+), 68 deletions(-)

diff --git a/libstdc++-v3/include/experimental/numeric b/libstdc++-v3/include/experimental/numeric
index d8a904a7057..4154e535a94 100644
--- a/libstdc++-v3/include/experimental/numeric
+++ b/libstdc++-v3/include/experimental/numeric
@@ -54,15 +54,19 @@ inline namespace fundamentals_v2
   /// Greatest common divisor
   template<typename _Mn, typename _Nn>
     constexpr common_type_t<_Mn, _Nn>
-    gcd(_Mn __m, _Nn __n)
+    gcd(_Mn __m, _Nn __n) noexcept
     {
-      static_assert(is_integral_v<_Mn>, "gcd arguments are integers");
-      static_assert(is_integral_v<_Nn>, "gcd arguments are integers");
-      static_assert(!is_same_v<remove_cv_t<_Mn>, bool>,
-		    "gcd arguments are not bools");
-      static_assert(!is_same_v<remove_cv_t<_Nn>, bool>,
-		    "gcd arguments are not bools");
-      return std::__detail::__gcd(__m, __n);
+      static_assert(is_integral_v<_Mn>,
+	  "std::experimental::gcd arguments must be integers");
+      static_assert(is_integral_v<_Nn>,
+	  "std::experimental::gcd arguments must be integers");
+      static_assert(_Mn(2) != _Mn(1),
+	  "std::experimental::gcd arguments must not be bool");
+      static_assert(_Nn(2) != _Nn(1),
+	  "std::experimental::gcd arguments must not be bool");
+      using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>;
+      return std::__detail::__gcd(std::__detail::__absu<_Up>(__m),
+				  std::__detail::__absu<_Up>(__n));
     }
 
   /// Least common multiple
@@ -70,13 +74,17 @@ inline namespace fundamentals_v2
     constexpr common_type_t<_Mn, _Nn>
     lcm(_Mn __m, _Nn __n)
     {
-      static_assert(is_integral_v<_Mn>, "lcm arguments are integers");
-      static_assert(is_integral_v<_Nn>, "lcm arguments are integers");
-      static_assert(!is_same_v<remove_cv_t<_Mn>, bool>,
-		    "lcm arguments are not bools");
-      static_assert(!is_same_v<remove_cv_t<_Nn>, bool>,
-		    "lcm arguments are not bools");
-      return std::__detail::__lcm(__m, __n);
+      static_assert(is_integral_v<_Mn>,
+	  "std::experimental::lcm arguments must be integers");
+      static_assert(is_integral_v<_Nn>,
+	  "std::experimental::lcm arguments must be integers");
+      static_assert(_Mn(2) != _Mn(1),
+	  "std::experimental::lcm arguments must not be bool");
+      static_assert(_Nn(2) != _Nn(1),
+	  "std::experimental::lcm arguments must not be bool");
+      using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>;
+      return std::__detail::__lcm(std::__detail::__absu<_Up>(__m),
+				  std::__detail::__absu<_Up>(__n));
     }
 } // namespace fundamentals_v2
 } // namespace experimental
diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric
index 57dcac6d215..8f2ed5c6a5e 100644
--- a/libstdc++-v3/include/std/numeric
+++ b/libstdc++-v3/include/std/numeric
@@ -60,6 +60,7 @@
 #include <bits/c++config.h>
 #include <bits/stl_iterator_base_types.h>
 #include <bits/stl_numeric.h>
+#include <ext/numeric_traits.h>
 
 #ifdef _GLIBCXX_PARALLEL
 # include <parallel/numeric>
@@ -82,38 +83,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 namespace __detail
 {
-  // std::abs is not constexpr and doesn't support unsigned integers.
-  template<typename _Tp>
-    constexpr
-    enable_if_t<__and_<is_integral<_Tp>, is_signed<_Tp>>::value, _Tp>
-    __abs_integral(_Tp __val)
-    { return __val < 0 ? -__val : __val; }
-
-  template<typename _Tp>
-    constexpr
-    enable_if_t<__and_<is_integral<_Tp>, is_unsigned<_Tp>>::value, _Tp>
-    __abs_integral(_Tp __val)
-    { return __val; }
+  // std::abs is not constexpr, doesn't support unsigned integers,
+  // and std::abs(std::numeric_limits<T>::min()) is undefined.
+  template<typename _Up, typename _Tp>
+    constexpr _Up
+    __absu(_Tp __val)
+    {
+      static_assert(is_unsigned<_Up>::value, "result type must be unsigned");
+      static_assert(sizeof(_Up) >= sizeof(_Tp),
+	  "result type must be at least as wide as the input type");
+      return __val < 0 ? -(_Up)__val : (_Up)__val;
+    }
 
-  void __abs_integral(bool) = delete;
+  void __absu(bool) = delete;
 
-  template<typename _Mn, typename _Nn>
-    constexpr common_type_t<_Mn, _Nn>
-    __gcd(_Mn __m, _Nn __n)
+  // GCD implementation
+  template<typename _Tp>
+    constexpr _Tp
+    __gcd(_Tp __m, _Tp __n)
     {
-      return __m == 0 ? __detail::__abs_integral(__n)
-	: __n == 0 ? __detail::__abs_integral(__m)
-	: __detail::__gcd(__n, __m % __n);
+      static_assert(is_unsigned<_Tp>::value, "type must be unsigned");
+      return __m == 0 ? __n
+	: __n == 0 ? __m
+	: __detail::__gcd(__n, _Tp(__m % __n));
     }
 
-  /// Least common multiple
-  template<typename _Mn, typename _Nn>
-    constexpr common_type_t<_Mn, _Nn>
-    __lcm(_Mn __m, _Nn __n)
+  // LCM implementation
+  template<typename _Tp>
+    constexpr _Tp
+    __lcm(_Tp __m, _Tp __n)
     {
       return (__m != 0 && __n != 0)
-	? (__detail::__abs_integral(__m) / __detail::__gcd(__m, __n))
-	  * __detail::__abs_integral(__n)
+	? (__m / __detail::__gcd(__m, __n)) * __n
 	: 0;
     }
 } // namespace __detail
@@ -128,29 +129,29 @@ namespace __detail
   /// Greatest common divisor
   template<typename _Mn, typename _Nn>
     constexpr common_type_t<_Mn, _Nn>
-    gcd(_Mn __m, _Nn __n)
+    gcd(_Mn __m, _Nn __n) noexcept
     {
-      static_assert(is_integral_v<_Mn>, "gcd arguments are integers");
-      static_assert(is_integral_v<_Nn>, "gcd arguments are integers");
-      static_assert(!is_same_v<remove_cv_t<_Mn>, bool>,
-		    "gcd arguments are not bools");
-      static_assert(!is_same_v<remove_cv_t<_Nn>, bool>,
-		    "gcd arguments are not bools");
-      return __detail::__gcd(__m, __n);
+      static_assert(is_integral_v<_Mn>, "std::gcd arguments must be integers");
+      static_assert(is_integral_v<_Nn>, "std::gcd arguments must be integers");
+      static_assert(_Mn(2) != _Mn(1), "std::gcd arguments must not be bool");
+      static_assert(_Nn(2) != _Nn(1), "std::gcd arguments must not be bool");
+      using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>;
+      return __detail::__gcd(__detail::__absu<_Up>(__m),
+			     __detail::__absu<_Up>(__n));
     }
 
   /// Least common multiple
   template<typename _Mn, typename _Nn>
     constexpr common_type_t<_Mn, _Nn>
-    lcm(_Mn __m, _Nn __n)
+    lcm(_Mn __m, _Nn __n) noexcept
     {
-      static_assert(is_integral_v<_Mn>, "lcm arguments are integers");
-      static_assert(is_integral_v<_Nn>, "lcm arguments are integers");
-      static_assert(!is_same_v<remove_cv_t<_Mn>, bool>,
-		    "lcm arguments are not bools");
-      static_assert(!is_same_v<remove_cv_t<_Nn>, bool>,
-		    "lcm arguments are not bools");
-      return __detail::__lcm(__m, __n);
+      static_assert(is_integral_v<_Mn>, "std::lcm arguments must be integers");
+      static_assert(is_integral_v<_Nn>, "std::lcm arguments must be integers");
+      static_assert(_Mn(2) == 2, "std::lcm arguments must not be bool");
+      static_assert(_Nn(2) == 2, "std::lcm arguments must not be bool");
+      using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>;
+      return __detail::__lcm(__detail::__absu<_Up>(__m),
+			     __detail::__absu<_Up>(__n));
     }
 
 #endif // C++17
diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/92978.cc b/libstdc++-v3/testsuite/26_numerics/gcd/92978.cc
new file mode 100644
index 00000000000..0ae1d3bb6c4
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/92978.cc
@@ -0,0 +1,40 @@
+// 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-do compile { target c++17 } }
+
+#include <numeric>
+#include <limits.h>
+
+void
+test01()
+{
+  // PR libstdc++/92978
+  static_assert( std::gcd(-120, 10U) == 10 );
+  static_assert( std::gcd(120U, -10) == 10 );
+}
+
+void
+test02()
+{
+  // |INT_MIN| should not be undefined, as long as it fits in the result type.
+  static_assert( std::gcd(INT_MIN, 0LL) == 1LL+INT_MAX );
+  static_assert( std::gcd(0LL, INT_MIN) == 1LL+INT_MAX );
+  static_assert( std::gcd(INT_MIN, 0LL + INT_MIN) == 1LL + INT_MAX );
+  static_assert( std::gcd(INT_MIN, 1LL + INT_MAX) == 1LL + INT_MAX );
+  static_assert( std::gcd(SHRT_MIN, 1U + SHRT_MAX) == 1U + SHRT_MAX );
+}
diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
index fe0dd9a6503..707148a2670 100644
--- a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
@@ -46,9 +46,8 @@ test01()
   std::gcd<const int&, const int&>(0.1, 0.1);   // { dg-error "from here" }
 }
 
-// { dg-error "integers" "" { target *-*-* } 133 }
-// { dg-error "integers" "" { target *-*-* } 134 }
-// { dg-error "not bools" "" { target *-*-* } 135 }
-// { dg-error "not bools" "" { target *-*-* } 137 }
-// { dg-prune-output "deleted function" }
-// { dg-prune-output "invalid operands" }
+// { dg-error "must be integers" "" { target *-*-* } 134 }
+// { dg-error "must be integers" "" { target *-*-* } 135 }
+// { dg-error "must not be bool" "" { target *-*-* } 136 }
+// { dg-error "must not be bool" "" { target *-*-* } 137 }
+// { dg-prune-output "incomplete type .*make_unsigned" }
diff --git a/libstdc++-v3/testsuite/26_numerics/lcm/92978.cc b/libstdc++-v3/testsuite/26_numerics/lcm/92978.cc
new file mode 100644
index 00000000000..0a016c34d43
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/lcm/92978.cc
@@ -0,0 +1,27 @@
+// 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-do compile { target c++17 } }
+
+#include <numeric>
+
+void
+test01()
+{
+  // PR libstdc++/92978
+  static_assert( std::lcm(-42, 21U) == 42U );
+}
diff --git a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
index c9d95d80c12..d4aa6b59da8 100644
--- a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
@@ -46,9 +46,8 @@ test01()
   std::lcm<const int&, const int&>(0.1, 0.1);   // { dg-error "from here" }
 }
 
-// { dg-error "integers" "" { target *-*-* } 147 }
-// { dg-error "integers" "" { target *-*-* } 148 }
-// { dg-error "not bools" "" { target *-*-* } 149 }
-// { dg-error "not bools" "" { target *-*-* } 151 }
-// { dg-prune-output "deleted function" }
-// { dg-prune-output "invalid operands" }
+// { dg-error "must be integers" "" { target *-*-* } 148 }
+// { dg-error "must be integers" "" { target *-*-* } 149 }
+// { dg-error "must not be bool" "" { target *-*-* } 150 }
+// { dg-error "must not be bool" "" { target *-*-* } 151 }
+// { dg-prune-output "incomplete type .*make_unsigned" }
diff --git a/libstdc++-v3/testsuite/experimental/numeric/92978.cc b/libstdc++-v3/testsuite/experimental/numeric/92978.cc
new file mode 100644
index 00000000000..8408fd4d9ce
--- /dev/null
+++ b/libstdc++-v3/testsuite/experimental/numeric/92978.cc
@@ -0,0 +1,48 @@
+// 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-do compile { target c++14 } }
+
+#include <experimental/numeric>
+#include <limits.h>
+
+void
+test01()
+{
+  // PR libstdc++/92978
+  static_assert( std::experimental::gcd(-120, 10U) == 10,
+      "mixed signed/unsigned" );
+  static_assert( std::experimental::gcd(120U, -10) == 10,
+      "mixed signed/unsigned" );
+
+  static_assert( std::lcm(-42, 21U) == 42U );
+}
+
+void
+test02()
+{
+  static_assert( std::experimental::gcd(INT_MIN, 0LL) == 1LL+INT_MAX,
+      "|INT_MIN| should not be undefined as long as it fits in the result" );
+  static_assert( std::experimental::gcd(0LL, INT_MIN) == 1LL+INT_MAX,
+      "|INT_MIN| should not be undefined" );
+  static_assert( std::experimental::gcd(INT_MIN, 0LL + INT_MIN) == 1LL + INT_MAX,
+      "|INT_MIN| should not be undefined" );
+  static_assert( std::experimental::gcd(INT_MIN, 1LL + INT_MAX) == 1LL + INT_MAX,
+      "|INT_MIN| should not be undefined" );
+  static_assert( std::experimental::gcd(SHRT_MIN, 1U + SHRT_MAX) == 1U + SHRT_MAX,
+      "|SHRT_MIN| should not be undefined" );
+}