From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugzilla@gcc.gnu.org>
Received: by sourceware.org (Postfix, from userid 48)
 id 9E282385C301; Sat,  4 Jun 2022 01:08:55 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9E282385C301
From: "goswin-v-b at web dot de" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/105844] New: std::lcm(50000, 49999) is UB but
 accepted in a constexpr due to cast to unsigned
Date: Sat, 04 Jun 2022 01:08:55 +0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: 12.1.0
X-Bugzilla-Keywords: 
X-Bugzilla-Severity: normal
X-Bugzilla-Who: goswin-v-b at web dot de
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status
 bug_severity priority component assigned_to reporter target_milestone
Message-ID: <bug-105844-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-BeenThere: gcc-bugs@gcc.gnu.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Gcc-bugs mailing list <gcc-bugs.gcc.gnu.org>
List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=unsubscribe>
List-Archive: <https://gcc.gnu.org/pipermail/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-request@gcc.gnu.org?subject=help>
List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=subscribe>
X-List-Received-Date: Sat, 04 Jun 2022 01:08:55 -0000

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D105844

            Bug ID: 105844
           Summary: std::lcm(50000, 49999) is UB but accepted in a
                    constexpr due to cast to unsigned
           Product: gcc
           Version: 12.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: goswin-v-b at web dot de
  Target Milestone: ---

Running "gcc-12.1 -std=3Dc++20 -O2 -W -Wall" on

    #include <numeric>
    constinit int t =3D std::lcm(50000, 49999);

produces

    t:
        .long   -1795017296

The standard says:

> The behavior is undefined if |m|, |n|, or the least common multiple of |m|
> and |n| is not representable as a value of type std::common_type_t<M, N>.=
=20

Which is the case here, the lvm overflows and is undefined. The negative nu=
mber
produced is not correct and the compile should fail.

The problem is the __absu function in <numeric> casting the arguments to an
unsigned type:

  // 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) >=3D sizeof(_Tp),
          "result type must be at least as wide as the input type");
      return __val < 0 ? -(_Up)__val : (_Up)__val;
    }

  /// Least common multiple
  template<typename _Mn, typename _Nn>
    constexpr common_type_t<_Mn, _Nn>
    lcm(_Mn __m, _Nn __n) noexcept
    {
      static_assert(is_integral_v<_Mn>, "std::lcm arguments must be integer=
s");
      static_assert(is_integral_v<_Nn>, "std::lcm arguments must be integer=
s");
      static_assert(_Mn(2) =3D=3D 2, "std::lcm arguments must not be bool");
      static_assert(_Nn(2) =3D=3D 2, "std::lcm arguments must not be bool");
      using _Up =3D make_unsigned_t<common_type_t<_Mn, _Nn>>;
      return __detail::__lcm(__detail::__absu<_Up>(__m),
                             __detail::__absu<_Up>(__n));
    }

__lvm is called with unsigned arguments which do not overflow for the given
numbers. And any unsigned overflow would not be undefined behavior. The res=
ult
of __lcm is then converted back to the signed type, which is not UB.

I suggest the following changes:

  // LCM implementation
  template<typename _Tp>
    constexpr _Tp
    __lcm(_Tp __m, _Tp __n)
    {
      static_assert(__m =3D=3D 0 || __n =3D=3D 0 || __m / __detail::__gcd(_=
_m, __n) <=3D
std::numeric_limits<_Tp>::max() / __n, "std::lcm not representable in commo=
nt
type");
      return (__m !=3D 0 && __n !=3D 0)
        ? (__m / __detail::__gcd(__m, __n)) * __n
        : 0;
    }


  /// Least common multiple
  template<typename _Mn, typename _Nn>
    constexpr common_type_t<_Mn, _Nn>
    lcm(_Mn __m, _Nn __n) noexcept
    {
      static_assert(is_integral_v<_Mn>, "std::lcm arguments must be integer=
s");
      static_assert(is_integral_v<_Nn>, "std::lcm arguments must be integer=
s");
      static_assert(_Mn(2) =3D=3D 2, "std::lcm arguments must not be bool");
      static_assert(_Nn(2) =3D=3D 2, "std::lcm arguments must not be bool");
      using _Cp =3D common_type_t<_Mn, _Nn>;
      using _Up =3D make_unsigned_t<common_type_t<_Mn, _Nn>>;
      _Up t =3D __detail::__lcm(__detail::__absu<_Up>(__m),
                              __detail::__absu<_Up>(__n));
      static_assert(t <=3D (_Up)std::numeric_limits<_Cp>::max(), "std::lcm =
not
representable in commont type");
      return t;
    }=