[libc++] Fix __bitop_unsigned_integer, rename to __is_unsigned_integer, and fix constexprness of std::countr_zero(__uint128_t)

[• Quuxplusone]

Summary

Fixes https://bugs.llvm.org/show_bug.cgi?id=49450

There are only five unsigned integer types, so we should just list them out.
Also provide `__is_signed_integer`, even though the Standard doesn't consume
that trait anywhere yet.

Notice that `concept uniform_random_bit_generator` is specifically specified
to rely on `concept unsigned_integral` and *not* `__is_unsigned_integer`.
Instantiating `std::ranges::sample` with a type `U` satisfying
`uniform_random_bit_generator` where `unsigned_integral<U::result_type>`
and not `__is_unsigned_integer<U::result_type>` is simply IFNDR.

Also vastly improve test coverage for the <bit> manipulation functions, using our modern "test runtime and constexpr-time with the same function" approach.

[• Quuxplusone]

libcxx/include/bit

79–80

Seems like we should add char8_t while we're here, yeah? (It is also integral and unsigned but not an unsigned integer type.) For bonus clarity, we could make a type trait __is_integer_type<_Tp> and then this whole constraint on line 97 would be simply

static_assert(__is_integer_type<_Tp>::value && is_unsigned<_Tp>::value, "__rotl requires an unsigned integer type");

...except that a static_assert is not a "constraint," so we're just totally nonconforming here.
@jwakely, thoughts? I'd volunteer to commandeer if you like.

[jwakely]

libcxx/include/bit

79–80

Yes, that should be there too. Feel free to take this, I only submitted it here because it seemed better to put the patch here than in bugzilla.

[• Quuxplusone]

libcxx/include/bit

79–80

Blech.
@mclow.lists, @ldionne: libc++ currently supports __uint128_t for these functions; do we want to keep supporting it?
libstdc++ does not support it: https://godbolt.org/z/jK9q8z6oT

I'm going to operate on the assumption that we want to keep it (as a non-conforming extension)...

[jwakely]

libcxx/include/bit

79–80

If you want non-conforming extensions then you need to compile with -std=gnu++20 not -std=c++20 and if you do that, libstdc++ does support unsigned __int128 here.

[jwakely]

libcxx/include/bit

79–80

The static assert is not a problem, because you're only looking at the internal __rotl function which doesn't need to be constrained. The public rotl function is constrained correctly, using enable_if.

[• Quuxplusone]

libcxx/include/bit

84

I relaxed the static_assert on the internal functions for the same (bad) intuitive reason that the internal functions are provided in the first place. We never actually use any of these internal functions, but if we did, it might be nice to be able to use them on, I dunno, char or something. I'm highly ambivalent about whether we should be asserting anything at all, or if we do, what it should be. So I'll take suggestions if anyone's got any.

119–125

This is a bugfix: std::countr_zero(__uint128_t(1) << 64) had been trying to evaluate __libcpp_ctz(0uLL) in constexpr context, and that's not allowed. The old tests didn't catch it but the new tests do.

[jwakely]

FWIW

libcxx/include/bit

84

FWIW libstdc++ has similar internal versions of these functions, available from C++14 up, and I didn't constrain them or add assertions. The public functions are responsible for input validation (if needed) and the internal functions assume the caller knows what they're doing.

[• Quuxplusone]

Not sure what happened with https://buildkite.com/llvm-project/libcxx-ci/builds/3210 . Rebase and poke buildkite; let's see if buildkite fixed itself.

[• Quuxplusone]

Okay, what if we don't rearrange the order in which <bit> includes <__debug>?
(I'm preparing another patch to just alphabetize all the includes everywhere.)

[• Quuxplusone]

Well, I don't know what's throwing bad_cast from inside the regex code, so let's just poke buildkite with something totally innocuous for now and see what happens.
https://buildkite.com/llvm-project/libcxx-ci/builds/3225

[• Quuxplusone]

Okay, 92260d7a186425510e96b7036b467a6889d08d97 reverted the thing that was probably breaking all the tests. Let's try buildkite again.

[tschuett]

In D102328#2755987, @Quuxplusone wrote:

Okay, what if we don't rearrange the order in which <bit> includes <__debug>?
(I'm preparing another patch to just alphabetize all the includes everywhere.)

clang-format has

SortIncludes, IncludeCategories, and IncludeBlocks

[Mordante]

LGTM, with a few suggestions.

libcxx/include/type_traits

816 ↗

(On Diff #345131)

How do you feel about using __libcpp_is_signed_integer to match the __libcpp_is_floating_point below?

libcxx/test/std/numerics/bit/bit.pow.two/bit_ceil.pass.cpp

60 ↗

(On Diff #345131)

What about removing this function and add it to the generic test and use it in a if constexpr(std::same_as<T, __uint128_t>) block?
(Obviously still guarded by`#ifndef _LIBCPP_HAS_NO_INT128`)

[• Quuxplusone]

libcxx/include/type_traits

816 ↗

(On Diff #345131)

I wasn't sure what the convention is here. It looks like we can't use e.g. __is_floating_point because that's sometimes a builtin, so we use __libcpp_is_floating_point instead? In this case __is_signed_integer isn't a builtin — well, isn't one today — but yeah, I guess on this second glance I am coming around to naming this entrypoint with a leading __libcpp_. That way, if it ever becomes a builtin, we won't have to change its call-sites.

libcxx/test/std/numerics/bit/bit.pow.two/bit_ceil.pass.cpp

60 ↗

(On Diff #345131)

Part of my thinking here was that these tests could be ported over into libcxx/test/libcxx/ to test std::__bit_ceil and so on, in pre-'17 language modes, so we want to keep avoiding if constexpr.
But clearly I didn't actually do that porting-over; and I did remove the trailing ,"" from all the static_asserts; so I guess it'd be okay to move this into test(). It would make the file a bit shorter. Will do, or at least consider.

[• Quuxplusone]

Take @Mordante's review comments; poke buildbot with some header-alphabetization NFC too.

libcxx/include/bit

 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template<class _Tp>
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _Tp __rotl(_Tp __t, unsigned int __cnt) _NOEXCEPT
 {
     static_assert(is_unsigned<_Tp>::value, "__rotl requires an unsigned integer type");
     const unsigned int __dig = numeric_limits<_Tp>::digits;
     if ((__cnt % __dig) == 0)
         return __t;
     return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig)));
 }
 
 template<class _Tp>
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
if      (sizeof(_Tp) <= sizeof(unsigned int))
         return __libcpp_ctz(static_cast<unsigned int>(__t));
     else if (sizeof(_Tp) <= sizeof(unsigned long))
         return __libcpp_ctz(static_cast<unsigned long>(__t));
     else if (sizeof(_Tp) <= sizeof(unsigned long long))
         return __libcpp_ctz(static_cast<unsigned long long>(__t));
     else
     {
         int __ret = 0;
-        int __iter = 0;
         const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
-        while ((__iter = __libcpp_ctz(static_cast<unsigned long long>(__t))) == __ulldigits)
+        while (static_cast<unsigned long long>(__t) == 0uLL)
         {
-            __ret += __iter;
+            __ret += __ulldigits;
             __t >>= __ulldigits;
         }
-        return __ret + __iter;
+        return __ret + __libcpp_ctz(static_cast<unsigned long long>(__t));
     }
 }
 
 template<class _Tp>
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 int __countl_zero(_Tp __t) _NOEXCEPT
 {
     static_assert(is_unsigned<_Tp>::value, "__countl_zero requires an unsigned integer type");