[libc++] Refactor char_traits

[philnik]

Summary

This allows us to reuse workarounds for compilers that don't provide the builtins or constexpr support.

[philnik]

Rebased

[Mordante]

In general I like the approach, some remarks. I really like to see the CI once it's running again.

libcxx/include/__string/char_traits.h

362

Why is this function and length not changed? Do the builtins not work with them?

libcxx/include/cstring

102

Are these used except in the traits?
I really like to see some private tests for these functions.

[philnik]

libcxx/include/__string/char_traits.h

362

Yes, __builtin_char_memchr only works with char: https://godbolt.org/z/YvzMdzc1x

libcxx/include/cstring

102

Not currently, but I'm working on a patch that uses __constexpr_memcmp to optimize std{,::ranges}::equal().

[philnik]

Add tests

[philnik]

Try to fix CI

[philnik]

Next try

[ldionne]

libcxx/include/__string/char_traits.h

227

I would make this explicit, and I'd use int instead of int_type since int is what memchr takes.

[Mordante]

LGTM modulo some nits.

libcxx/include/__string/char_traits.h

215

This is odd, I did leave a message here, but it's gone :-/

How about removing this test? I tested in godbolt and Clang and GCC for -O0 and -O2 this generated no code.
(If wanted I can recreate the example in godbolt.)

libcxx/test/libcxx/strings/c.strings/constexpr.cwchar.compile.pass.cpp

9 ↗

(On Diff #481278)

[philnik]

• Address comments
• Try to fix CI

libcxx/include/__string/char_traits.h

215

Maybe? I've tried and for me it generates code: https://godbolt.org/z/54v99TMo9. Though it's arguably not worth the extra four instructions and branch prediction slot to optimize for comparing nothing. I mainly kept it because I thought it was UB to call memcmp with null pointers, but I can't find any evidence of that, so removing I'm it.

[philnik]

Next try

[philnik]

Fix static_assert

[philnik]

Remove static_assert again, since it also fires when not actually calling __constexpr_memcmp during constant evaluation

[philnik]

More fixes

[philnik]

Try to fix CI

[haowei]

We are seeing build breakages in Fuchsia's builders after this change was landed and this change is in the blamelist and looks directly related:

[37031/289776](267) CXX kernel.efi_x64/obj/src/lib/llvm-profdata/libllvm-profdata.llvm-profdata.cc.o
FAILED: kernel.efi_x64/obj/src/lib/llvm-profdata/libllvm-profdata.llvm-profdata.cc.o
../../../recipe_cleanup/clangehe1kz7e/bin/clang++ -MD -MF kernel.efi_x64/obj/src/lib/llvm-profdata/libllvm-profdata.llvm-profdata.cc.o.d -o kernel.efi_x64/obj/src/lib/llvm-profdata/libllvm-profdata...
In file included from ../../src/lib/llvm-profdata/llvm-profdata.cc:5:
In file included from ../../src/lib/llvm-profdata/include/lib/llvm-profdata/llvm-profdata.h:11:
In file included from ../../../recipe_cleanup/clangehe1kz7e/include/c++/v1/string_view:220:
../../../recipe_cleanup/clangehe1kz7e/include/c++/v1/__string/char_traits.h:286:17: error: no member named '__constexpr_wmemcmp' in namespace 'std'; did you mean '__constexpr_memcmp'?
    return std::__constexpr_wmemcmp(__s1, __s2, __n);
           ~~~~~^
../../../recipe_cleanup/clangehe1kz7e/include/c++/v1/cstring:119:1: note: '__constexpr_memcmp' declared here
__constexpr_memcmp(const _Tp* __lhs, const _Tp* __rhs, size_t __count) {
^
In file included from ../../src/lib/llvm-profdata/llvm-profdata.cc:5:
In file included from ../../src/lib/llvm-profdata/include/lib/llvm-profdata/llvm-profdata.h:11:
In file included from ../../../recipe_cleanup/clangehe1kz7e/include/c++/v1/string_view:220:
../../../recipe_cleanup/clangehe1kz7e/include/c++/v1/__string/char_traits.h:290:17: error: no member named '__constexpr_wcslen' in namespace 'std'
    return std::__constexpr_wcslen(__s);
           ~~~~~^
../../../recipe_cleanup/clangehe1kz7e/include/c++/v1/__string/char_traits.h:297:17: error: no member named '__constexpr_wmemchr' in namespace 'std'
    return std::__constexpr_wmemchr(__s, __a, __n);
           ~~~~~^
3 errors generated.
clang++: error: failing because '-gen-reproducer' is used
Fuchsia clang version 16.0.0 (https://llvm.googlesource.com/llvm-project fe9e442c57f3b50ec7ad5f01e191745aa3156b4e)
Target: x86_64-unknown-windows-msvc
Thread model: posix
InstalledDir: ../../../recipe_cleanup/clangehe1kz7e/bin
clang++: note: diagnostic msg:
********************

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang++: note: diagnostic msg: clang-crashreports/llvm-profdata-960ad3.cpp
clang++: note: diagnostic msg: clang-crashreports/llvm-profdata-960ad3.sh
clang++: note: diagnostic msg:

********************

Could you take a look?
If it takes a while to fix, could you revert the change first?

[haowei]

Looks like it is Fuchsia's own issue as it overrides libcxx headers in kernel (https://fuchsia.googlesource.com/fuchsia/+/658bbc3cef7f340c058dde67c3d5dd2be4084bdd/zircon/kernel/lib/ktl/include/cwchar). You don't need to take any action. Sorry for the trouble.

[ldionne]

In D139555#3985297, @haowei wrote:

Looks like it is Fuchsia's own issue as it overrides libcxx headers in kernel (https://fuchsia.googlesource.com/fuchsia/+/658bbc3cef7f340c058dde67c3d5dd2be4084bdd/zircon/kernel/lib/ktl/include/cwchar). You don't need to take any action. Sorry for the trouble.

I would check if that workaround is still needed. You should be able to configure the library with LIBCXX_ENABLE_WIDE_CHARACTERS=OFF at CMake time to make sure that the library doesn't rely on this header.

libcxx/include/__string/char_traits.h

#endif
 
     static inline _LIBCPP_CONSTEXPR_SINCE_CXX17
     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
     static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
             {return __c1 == __c2;}
     static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
         {return (unsigned char)__c1 < (unsigned char)__c2;}
 
-    static _LIBCPP_CONSTEXPR_SINCE_CXX17
-    int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
+  static _LIBCPP_CONSTEXPR_SINCE_CXX17 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
+    if (__n == 0)
+      return 0;
+    return std::__constexpr_memcmp(__s1, __s2, __n);
+  }
 
-    static inline size_t _LIBCPP_CONSTEXPR_SINCE_CXX17 length(const char_type* __s)  _NOEXCEPT {
-      // GCC currently does not support __builtin_strlen during constant evaluation.
-      // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70816
-#ifdef _LIBCPP_COMPILER_GCC
-      if (__libcpp_is_constant_evaluated()) {
-        size_t __i = 0;
-        for (; __s[__i] != char_type('\0'); ++__i)
-            ;
-        return __i;
-      }
-#endif
-      return __builtin_strlen(__s);
-    }
+    return std::__constexpr_strlen(__s);
 
-    static _LIBCPP_CONSTEXPR_SINCE_CXX17
-    const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
+  const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
+    if (__n == 0)
+        return nullptr;
+    return std::__constexpr_char_memchr(__s, __a, __n);
+  }
 
     static inline _LIBCPP_CONSTEXPR_SINCE_CXX20
     char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
         return std::__char_traits_move(__s1, __s2, __n);
     }
 
     static inline _LIBCPP_CONSTEXPR_SINCE_CXX20
     char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
     static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
         {return int_type((unsigned char)__c);}
     static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
         {return __c1 == __c2;}
     static inline _LIBCPP_CONSTEXPR int_type  eof() _NOEXCEPT
         {return int_type(EOF);}
 };
 
-inline _LIBCPP_CONSTEXPR_SINCE_CXX17
-int
-char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
-{
-    if (__n == 0)
-        return 0;
-#if __has_feature(cxx_constexpr_string_builtins)
-    return __builtin_memcmp(__s1, __s2, __n);
-#elif _LIBCPP_STD_VER <= 14
-    return _VSTD::memcmp(__s1, __s2, __n);
-#else
-    for (; __n; --__n, ++__s1, ++__s2)
-    {
-        if (lt(*__s1, *__s2))
-            return -1;
-        if (lt(*__s2, *__s1))
-            return 1;
-    }
-    return 0;
-#endif
-}
-
-inline _LIBCPP_CONSTEXPR_SINCE_CXX17
-const char*
-char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
-{
-    if (__n == 0)
-        return nullptr;
-#if __has_feature(cxx_constexpr_string_builtins)
-    return __builtin_char_memchr(__s, to_int_type(__a), __n);
-#elif _LIBCPP_STD_VER <= 14
-    return (const char_type*) _VSTD::memchr(__s, to_int_type(__a), __n);
-#else
-    for (; __n; --__n)
-    {
-        if (eq(*__s, __a))
-            return __s;
-        ++__s;
-    }
-    return nullptr;
-#endif
-}
-
 // char_traits<wchar_t>
 
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 template <>
 struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t>
 {
     using char_type           = wchar_t;
     using int_type            = wint_t;
     using off_type            = streamoff;
     using pos_type            = streampos;
     using state_type          = mbstate_t;
 #if _LIBCPP_STD_VER > 17
     using comparison_category = strong_ordering;
 #endif
 
     static inline _LIBCPP_CONSTEXPR_SINCE_CXX17
     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
     static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
         {return __c1 == __c2;}
     static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
         {return __c1 < __c2;}
 
-    static _LIBCPP_CONSTEXPR_SINCE_CXX17
-    int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
-    static _LIBCPP_CONSTEXPR_SINCE_CXX17
-    size_t length(const char_type* __s) _NOEXCEPT;
-    static _LIBCPP_CONSTEXPR_SINCE_CXX17
-    const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
+  static _LIBCPP_CONSTEXPR_SINCE_CXX17 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
+    if (__n == 0)
+        return 0;
+    return std::__constexpr_wmemcmp(__s1, __s2, __n);
+  }
+
+  static _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t length(const char_type* __s) _NOEXCEPT {
+    return std::__constexpr_wcslen(__s);
+  }
+
+  const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
+    if (__n == 0)
+        return nullptr;
+    return std::__constexpr_wmemchr(__s, __a, __n);
+  }
 
     static inline _LIBCPP_CONSTEXPR_SINCE_CXX20
     char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
         return std::__char_traits_move(__s1, __s2, __n);
     }
 
     static inline _LIBCPP_CONSTEXPR_SINCE_CXX20
     char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
         {return char_type(__c);}
     static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
         {return int_type(__c);}
     static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
         {return __c1 == __c2;}
     static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
         {return int_type(WEOF);}
 };
-
-inline _LIBCPP_CONSTEXPR_SINCE_CXX17
-int
-char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
-{
-    if (__n == 0)
-        return 0;
-#if __has_feature(cxx_constexpr_string_builtins)
-    return __builtin_wmemcmp(__s1, __s2, __n);
-#elif _LIBCPP_STD_VER <= 14
-    return _VSTD::wmemcmp(__s1, __s2, __n);
-#else
-    for (; __n; --__n, ++__s1, ++__s2)
-    {
-        if (lt(*__s1, *__s2))
-            return -1;
-        if (lt(*__s2, *__s1))
-            return 1;
-    }
-    return 0;
-#endif
-}
-
-inline _LIBCPP_CONSTEXPR_SINCE_CXX17
-size_t
-char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT
-{
-#if __has_feature(cxx_constexpr_string_builtins)
-    return __builtin_wcslen(__s);
-#elif _LIBCPP_STD_VER <= 14
-    return _VSTD::wcslen(__s);
-#else
-    size_t __len = 0;
-    for (; !eq(*__s, char_type(0)); ++__s)
-        ++__len;
-    return __len;
-#endif
-}
-
-inline _LIBCPP_CONSTEXPR_SINCE_CXX17
-const wchar_t*
-char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
-{
-    if (__n == 0)
-        return nullptr;
-#if __has_feature(cxx_constexpr_string_builtins)
-    return __builtin_wmemchr(__s, __a, __n);
-#elif _LIBCPP_STD_VER <= 14
-    return _VSTD::wmemchr(__s, __a, __n);
-#else
-    for (; __n; --__n)
-    {
-        if (eq(*__s, __a))
-            return __s;
-        ++__s;
-    }
-    return nullptr;
-#endif
-}
 #endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS
 
 #ifndef _LIBCPP_HAS_NO_CHAR8_T
 
 template <>
 struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t>
 {
     using char_type           = char8_t;
     using int_type            = unsigned int;
     using off_type            = streamoff;
     using pos_type            = u8streampos;
     using state_type          = mbstate_t;
 #if _LIBCPP_STD_VER > 17
     using comparison_category = strong_ordering;
 #endif
 
     static inline constexpr void assign(char_type& __c1, const char_type& __c2) noexcept
         {__c1 = __c2;}
     static inline constexpr bool eq(char_type __c1, char_type __c2) noexcept
         {return __c1 == __c2;}
     static inline constexpr bool lt(char_type __c1, char_type __c2) noexcept
         {return __c1 < __c2;}
 
-    static constexpr
-    int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
+  static _LIBCPP_HIDE_FROM_ABI constexpr int
+  compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
+      return std::__constexpr_memcmp(__s1, __s2, __n);
+  }
 
     static constexpr
     size_t           length(const char_type* __s) _NOEXCEPT;
 
     _LIBCPP_INLINE_VISIBILITY static constexpr
     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 
     static _LIBCPP_CONSTEXPR_SINCE_CXX20
     char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
         return std::__char_traits_move(__s1, __s2, __n);
     }
 
     static _LIBCPP_CONSTEXPR_SINCE_CXX20
     char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {

 char_traits<char8_t>::length(const char_type* __s) _NOEXCEPT
 {
     size_t __len = 0;
     for (; !eq(*__s, char_type(0)); ++__s)
         ++__len;
     return __len;
 }
 
-inline constexpr
-int
-char_traits<char8_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
-{
-#if __has_feature(cxx_constexpr_string_builtins)
-    return __builtin_memcmp(__s1, __s2, __n);
-#else
-    for (; __n; --__n, ++__s1, ++__s2)
-    {
-        if (lt(*__s1, *__s2))
-            return -1;
-        if (lt(*__s2, *__s1))
-            return 1;
-    }
-    return 0;
-#endif
-}
-
 // TODO use '__builtin_char_memchr' if it ever supports char8_t ??
 inline constexpr
 const char8_t*
 char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 {
     for (; __n; --__n)
     {
         if (eq(*__s, __a))

libcxx/include/cstring

 using ::strrchr _LIBCPP_USING_IF_EXISTS;
 using ::strspn _LIBCPP_USING_IF_EXISTS;
 using ::strstr _LIBCPP_USING_IF_EXISTS;
 using ::strtok _LIBCPP_USING_IF_EXISTS;
 using ::memset _LIBCPP_USING_IF_EXISTS;
 using ::strerror _LIBCPP_USING_IF_EXISTS;
 using ::strlen _LIBCPP_USING_IF_EXISTS;
 
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR size_t __constexpr_strlen(const char* __str) {
+  return __builtin_strlen(__str);
+}
+
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int
+__constexpr_memcmp(const void* __lhs, const void* __rhs, size_t __count) {
+  return __builtin_memcmp(__lhs, __rhs, __count);
+}
+
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 const char*
+__constexpr_char_memchr(const char* __str, int __char, size_t __count) {
+#if __has_feature(cxx_constexpr_string_builtins)
+  return __builtin_char_memchr(__str, __char, __count);
+#else
+  if (!__libcpp_is_constant_evaluated())
+    return static_cast<const char*>(std::memchr(__str, __char, __count));
+  for (; __count; --__count) {
+    if (*__str == __char)
+      return __str;
+    ++__str;
+  }
+  return nullptr;
+#endif
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_CSTRING

libcxx/include/cwchar

 using ::getwchar _LIBCPP_USING_IF_EXISTS;
 using ::vwscanf _LIBCPP_USING_IF_EXISTS;
 using ::wscanf _LIBCPP_USING_IF_EXISTS;
 
 using ::putwchar _LIBCPP_USING_IF_EXISTS;
 using ::vwprintf _LIBCPP_USING_IF_EXISTS;
 using ::wprintf _LIBCPP_USING_IF_EXISTS;
 
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 size_t __constexpr_wcslen(const wchar_t* __str) {
+#if __has_builtin(__builtin_wcslen)
+  return __builtin_wcslen(__str);
+#else
+  if (!__libcpp_is_constant_evaluated())
+    return std::wcslen(__str);
+
+  size_t __len = 0;
+  for (; *__str != L'\0'; ++__str)
+    ++__len;
+  return __len;
+#endif
+}
+
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 int
+__constexpr_wmemcmp(const wchar_t* __lhs, const wchar_t* __rhs, size_t __count) {
+#if __has_builtin(__builtin_wmemcmp)
+  return __builtin_wmemcmp(__lhs, __rhs, __count);
+#else
+  if (!__libcpp_is_constant_evaluated())
+    return std::wmemcmp(__lhs, __rhs, __count);
+
+  for (; __count; --__count, ++__lhs, ++__rhs) {
+    if (*__lhs < *__rhs)
+      return -1;
+    if (*__rhs < *__lhs)
+      return 1;
+  }
+  return 0;
+#endif
+}
+
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 const wchar_t*
+__constexpr_wmemchr(const wchar_t* __str, wchar_t __char, size_t __count) {
+#if __has_feature(cxx_constexpr_string_builtins)
+  return __builtin_wmemchr(__str, __char, __count);
+#else
+  if (!__libcpp_is_constant_evaluated())
+    return std::wmemchr(__str, __char, __count);
+
+  for (; __count; --__count) {
+    if (*__str == __char)
+      return __str;
+    ++__str;
+  }
+  return nullptr;
+#endif
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_CWCHAR