[libc++] Use the __is_trivially_equality_comparable builtin

[philnik]

Generate files

[ldionne]

libcxx/include/__string/constexpr_c_functions.h

41–42

For these two functions, I feel it is useful to clarify that basically since each individual object is trivially lexicographically comparable, we could in theory run memcmp on each object in a loop. But since we have multiple such objects laid out contiguously, we might as well run just one big memcmp on all the bytes. IMO that insight is kind of useful and it would be useful to record in a comment.

And in fact this also clarifies that we could really be taking any contiguous_iterator here and just call std::to_address on it before we do the __builtin_memcmp. Doing that doesn't buy us anything from the caller though so we should probably not try to generalize this.

libcxx/include/__type_traits/is_equality_comparable.h

36–37

This needs to be updated.

46–68

template <class _Tp, class _Up>
struct __libcpp_is_trivially_equality_comparable_impl : false_type {};

template <class _Tp>
struct __libcpp_is_trivially_equality_comparable_impl<_Tp, _Tp>
#if __has_builtin(__is_trivially_equality_comparable)
    : integral_constant<bool, __is_trivially_equality_comparable(_Tp) && __is_equality_comparable<_Tp, _Tp>::value>
#else
    : is_integral<_Tp>
#endif
{};

template <class _Tp>
struct __libcpp_is_trivially_equality_comparable_impl<_Tp*, _Tp*> : true_type {};

template <class _Tp, class _Up>
struct __libcpp_is_trivially_equality_comparable_impl<_Tp*, _Up*> : /* what you have right now */ {};

IMO that is a bit easier to follow, but it's otherwise equivalent.

libcxx/include/__type_traits/is_trivially_lexicographically_comparable.h

28

I would like a comment like we have to __libcpp_is_trivially_equality_comparable explaining formally what this trait tells us (e.g. that a < b is equivalent to a lexicographical comparison on the bytes of the object???).

I think we also need to discuss a couple of issues that we just touched on during live review, such as endianness and signed vs unsigned (which basically means that the value of the object has to be the exact same thing as its representation). So for example int(-1) is less than int(0), but if you compare it with memcmp, it compares the bytes themselves and the bytes for int(-1) are "greater" than the bytes for int(0).

I think we should also discuss what to do with bool. So first, bool < bool is allowed, and it is the case that false < true. It's kinda weird that it's allowed but it is, so whatever. Now false has exactly one possible representation 0x000000000, and IIRC true also has exactly one representation 0x0000001. If that is correct (IOW if it's UB to have true be represented as anything else other than 0x0001), then we are allowed to assume that anything that comes in as a bool has one of these two representations, so we can apply memcmp on it and it'll work just like operator<(bool, bool).

31

As discussed.

[philnik]

• Address comments
• Try to fix CI

[ldionne]

libcxx/include/__string/char_traits.h

215 ↗

(On Diff #519594)

Can we fix the indentation while we're at it?

217 ↗

(On Diff #519594)

We need a comment explaining why we can't use __constexpr_memcmp here, this is pretty subtle. You can say something like "__constexpr_memcmp requires a trivially lexicographically comparable type, but char is not when char is a signed type".

libcxx/include/__string/constexpr_c_functions.h

52

Is there a reason why we can't simply cast to unsigned char here when we do the comparison? That is what __builtin_memcmp does in spirit, and it might resolve a bunch of difficulties.

libcxx/include/__type_traits/is_trivially_lexicographically_comparable.h

27

32

41–44

Nitpick: let's align the comment like

unsigned integer types with sizeof(T) > 1: depending on the endianness [...]
                                           [...]

[ldionne]

LGTM w/ comments and tests.

libcxx/include/__string/constexpr_c_functions.h

41–42

I don't think you have any tests for this.

52

As discussed, we'd have to get rid of the static_assert and we don't want to do that.

[philnik]

Address comments

[philnik]

Try to fix CI

[philnik]

Try to fix CI

libcxx/include/CMakeLists.txt

set(files
   __type_traits/is_trivial.h
   __type_traits/is_trivially_assignable.h
   __type_traits/is_trivially_constructible.h
   __type_traits/is_trivially_copy_assignable.h
   __type_traits/is_trivially_copy_constructible.h
   __type_traits/is_trivially_copyable.h
   __type_traits/is_trivially_default_constructible.h
   __type_traits/is_trivially_destructible.h
+  __type_traits/is_trivially_lexicographically_comparable.h
   __type_traits/is_trivially_move_assignable.h
   __type_traits/is_trivially_move_constructible.h
   __type_traits/is_unbounded_array.h
   __type_traits/is_union.h
   __type_traits/is_unsigned.h
   __type_traits/is_unsigned_integer.h
   __type_traits/is_valid_expansion.h
   __type_traits/is_void.h

libcxx/include/__algorithm/equal.h

template <
     class _Tp,
     class _Up,
     class _BinaryPredicate,
     __enable_if_t<__is_trivial_equality_predicate<_BinaryPredicate, _Tp, _Up>::value && !is_volatile<_Tp>::value &&
                       !is_volatile<_Up>::value && __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value,
                   int> = 0>
 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
 __equal_iter_impl(_Tp* __first1, _Tp* __last1, _Up* __first2, _BinaryPredicate&) {
-  return std::__constexpr_memcmp(__first1, __first2, (__last1 - __first1) * sizeof(_Tp)) == 0;
+  return std::__constexpr_memcmp_equal(__first1, __first2, (__last1 - __first1) * sizeof(_Tp));
 }
 
 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) {
   return std::__equal_iter_impl(
       std::__unwrap_iter(__first1), std::__unwrap_iter(__last1), std::__unwrap_iter(__first2), __pred);
 }
template <class _Tp,
           class _Proj1,
           class _Proj2,
           __enable_if_t<__is_trivial_equality_predicate<_Pred, _Tp, _Up>::value && __is_identity<_Proj1>::value &&
                             __is_identity<_Proj2>::value && !is_volatile<_Tp>::value && !is_volatile<_Up>::value &&
                             __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value,
                         int> = 0>
 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_impl(
     _Tp* __first1, _Tp* __last1, _Up* __first2, _Up*, _Pred&, _Proj1&, _Proj2&) {
-  return std::__constexpr_memcmp(__first1, __first2, (__last1 - __first1) * sizeof(_Tp)) == 0;
+  return std::__constexpr_memcmp_equal(__first1, __first2, (__last1 - __first1) * sizeof(_Tp));
 }
 
 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
 __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
         _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag,
         random_access_iterator_tag) {
   if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))

libcxx/include/__string/constexpr_c_functions.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___STRING_CONSTEXPR_C_FUNCTIONS_H
 #define _LIBCPP___STRING_CONSTEXPR_C_FUNCTIONS_H
 
 #include <__config>
 #include <__type_traits/is_constant_evaluated.h>
 #include <__type_traits/is_equality_comparable.h>
 #include <__type_traits/is_same.h>
+#include <__type_traits/is_trivially_lexicographically_comparable.h>
 #include <cstddef>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 size_t __constexpr_strlen(const char* __str) {
   // GCC currently doesn't support __builtin_strlen for heap-allocated memory 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 (; __str[__i] != '\0'; ++__i)
       ;
     return __i;
   }
 #endif
   return __builtin_strlen(__str);
 }
 
 template <class _Tp, class _Up>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 int
 __constexpr_memcmp(const _Tp* __lhs, const _Up* __rhs, size_t __count) {
-  static_assert(__libcpp_is_trivially_equality_comparable<_Tp, _Up>::value,
-                "_Tp and _Up have to be trivially equality comparable");
+  static_assert(__libcpp_is_trivially_lexicographically_comparable<_Tp, _Up>::value,
+                "_Tp and _Up have to be trivially lexicographically comparable");
 
   if (__libcpp_is_constant_evaluated()) {
 #ifdef _LIBCPP_COMPILER_CLANG_BASED
     if (sizeof(_Tp) == 1 && !is_same<_Tp, bool>::value)
       return __builtin_memcmp(__lhs, __rhs, __count);
 #endif
 
     while (__count != 0) {
       if (*__lhs < *__rhs)
         return -1;
       if (*__rhs < *__lhs)
         return 1;
 
       __count -= sizeof(_Tp);
       ++__lhs;
       ++__rhs;
     }
     return 0;
   } else {
     return __builtin_memcmp(__lhs, __rhs, __count);
   }
 }
 
+template <class _Tp, class _Up>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool
+__constexpr_memcmp_equal(const _Tp* __lhs, const _Up* __rhs, size_t __count) {
+  static_assert(__libcpp_is_trivially_equality_comparable<_Tp, _Up>::value,
+                "_Tp and _Up have to be trivially equality comparable");
+
+  if (__libcpp_is_constant_evaluated()) {
+#ifdef _LIBCPP_COMPILER_CLANG_BASED
+    if (sizeof(_Tp) == 1 && is_integral<_Tp>::value && !is_same<_Tp, bool>::value)
+      return __builtin_memcmp(__lhs, __rhs, __count) == 0;
+#endif
+    while (__count != 0) {
+      if (*__lhs != *__rhs)
+        return false;
+
+      __count -= sizeof(_Tp);
+      ++__lhs;
+      ++__rhs;
+    }
+    return true;
+  } else {
+    return __builtin_memcmp(__lhs, __rhs, __count) == 0;
+  }
+}
+
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 const char*
 __constexpr_char_memchr(const char* __str, int __char, size_t __count) {
 #if __has_builtin(__builtin_char_memchr)
   return __builtin_char_memchr(__str, __char, __count);
 #else
   if (!__libcpp_is_constant_evaluated())
     return static_cast<const char*>(__builtin_memchr(__str, __char, __count));
   for (; __count; --__count) {

libcxx/include/__type_traits/is_equality_comparable.h

 #define _LIBCPP___TYPE_TRAITS_IS_EQUAILITY_COMPARABLE_H
 
 #include <__config>
 #include <__type_traits/integral_constant.h>
 #include <__type_traits/is_integral.h>
 #include <__type_traits/is_same.h>
 #include <__type_traits/is_void.h>
 #include <__type_traits/remove_cv.h>
+#include <__type_traits/remove_cvref.h>
 #include <__type_traits/void_t.h>
 #include <__utility/declval.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Tp, class _Up, class = void>
 struct __is_equality_comparable : false_type {};
 
 template <class _Tp, class _Up>
 struct __is_equality_comparable<_Tp, _Up, __void_t<decltype(std::declval<_Tp>() == std::declval<_Up>())> > : true_type {
 };
 
 // A type is_trivially_equality_comparable if the expression `a == b` is equivalent to `std::memcmp(&a, &b, sizeof(T))`
 // (with `a` and `b` being of type `T`). There is no compiler built-in to check this, so we can only do this for known
 // types. In particular, these are the integral types and raw pointers.
 //
 // The following types are not trivially equality comparable:
 // floating-point types: different bit-patterns can compare equal. (e.g 0.0 and -0.0)
 // enums: The user is allowed to specialize operator== for enums
 // pointers that don't have the same type (ignoring cv-qualifiers): pointers to virtual bases are equality comparable,
 //   but don't have the same bit-pattern. An exception to this is comparing to a void-pointer. There the bit-pattern is
 //   always compared.
 
 template <class _Tp, class _Up>
-struct __libcpp_is_trivially_equality_comparable
-    : integral_constant<bool,
-                        __is_equality_comparable<_Tp, _Up>::value && is_integral<_Tp>::value &&
-                            is_same<__remove_cv_t<_Tp>, __remove_cv_t<_Up> >::value> {};
+struct __libcpp_is_trivially_equality_comparable_impl
+    : integral_constant<bool, is_integral<_Tp>::value && is_same<_Tp, _Up>::value> {};
+
+#if __has_builtin(__is_trivially_equality_comparable)
+
+template <class _Tp>
+struct __libcpp_is_trivially_equality_comparable_impl<_Tp, _Tp>
+    : integral_constant<bool, __is_trivially_equality_comparable(_Tp) && __is_equality_comparable<_Tp, _Tp>::value> {};
+
+#endif // __has_builtin(__is_trivially_equality_comparable)
+
+template <class _Tp>
+struct __libcpp_is_trivially_equality_comparable_impl<_Tp*, _Tp*> : true_type {};
 
 // TODO: Use is_pointer_inverconvertible_base_of
 template <class _Tp, class _Up>
-struct __libcpp_is_trivially_equality_comparable<_Tp*, _Up*>
+struct __libcpp_is_trivially_equality_comparable_impl<_Tp*, _Up*>
     : integral_constant<
           bool,
           __is_equality_comparable<_Tp*, _Up*>::value &&
               (is_same<__remove_cv_t<_Tp>, __remove_cv_t<_Up> >::value || is_void<_Tp>::value || is_void<_Up>::value)> {
 };
 
+template <class _Tp, class _Up>
+using __libcpp_is_trivially_equality_comparable =
+    __libcpp_is_trivially_equality_comparable_impl<__remove_cv_t<_Tp>, __remove_cv_t<_Up> >;
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___TYPE_TRAITS_IS_EQUAILITY_COMPARABLE_H

libcxx/include/__type_traits/is_trivially_lexicographically_comparable.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___TYPE_TRAITS_IS_TRIVIALLY_LEXICOGRAPHICALLY_COMPARABLE_H
+#define _LIBCPP___TYPE_TRAITS_IS_TRIVIALLY_LEXICOGRAPHICALLY_COMPARABLE_H
+
+#include <__config>
+#include <__type_traits/integral_constant.h>
+#include <__type_traits/is_integral.h>
+#include <__type_traits/is_same.h>
+#include <__type_traits/remove_cv.h>
+#include <__type_traits/void_t.h>
+#include <__utility/declval.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Tp, class _Up>
+struct __libcpp_is_trivially_lexicographically_comparable
+    : integral_constant<bool,
+                        is_same<__remove_cv_t<_Tp>, __remove_cv_t<_Up> >::value && sizeof(_Tp) == 1 &&
+                            is_integral<_Tp>::value> {};
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___TYPE_TRAITS_IS_TRIVIALLY_LEXICOGRAPHICALLY_COMPARABLE_H

libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp

friend TEST_CONSTEXPR_CXX20 bool operator==(const AddressCompare& lhs, const AddressCompare& rhs) {
     return &lhs == &rhs;
   }
 
   friend TEST_CONSTEXPR_CXX20 bool operator!=(const AddressCompare& lhs, const AddressCompare& rhs) {
     return &lhs != &rhs;
   }
 };
 
+#if TEST_STD_VER >= 20
+class trivially_equality_comparable {
+public:
+  constexpr trivially_equality_comparable(int i) : i_(i) {}
+  bool operator==(const trivially_equality_comparable&) const = default;
+
+private:
+  int i_;
+};
+
+#endif
+
 TEST_CONSTEXPR_CXX20 bool test() {
   types::for_each(types::cpp17_input_iterator_list<int*>(), TestIter2<int, types::cpp17_input_iterator_list<int*> >());
-  types::for_each(types::cpp17_input_iterator_list<char*>(), TestIter2<char, types::cpp17_input_iterator_list<char*> >());
+  types::for_each(
+      types::cpp17_input_iterator_list<char*>(), TestIter2<char, types::cpp17_input_iterator_list<char*> >());
   types::for_each(types::cpp17_input_iterator_list<AddressCompare*>(),
                   TestIter2<AddressCompare, types::cpp17_input_iterator_list<AddressCompare*> >());
 
   types::for_each(types::integral_types(), TestNarrowingEqualTo());
 
+#if TEST_STD_VER >= 20
+  types::for_each(
+      types::cpp17_input_iterator_list<trivially_equality_comparable*>{},
+      TestIter2<trivially_equality_comparable, types::cpp17_input_iterator_list<trivially_equality_comparable*>>{});
+#endif
+
   return true;
 }
 
 struct Base {};
 struct Derived : virtual Base {};
 
 int main(int, char**) {
   test();
 #if TEST_STD_VER >= 20
   static_assert(test());
 #endif
 
   types::for_each(types::as_pointers<types::cv_qualified_versions<int> >(),
                   TestIter2<int, types::as_pointers<types::cv_qualified_versions<int> > >());
   types::for_each(types::as_pointers<types::cv_qualified_versions<char> >(),
                   TestIter2<char, types::as_pointers<types::cv_qualified_versions<char> > >());
 
   {
     Derived d;
     Derived* a[] = {&d, nullptr};
     Base* b[]    = {&d, nullptr};
 
     assert(std::equal(a, a + 2, b));
 #if TEST_STD_VER >= 14
     assert(std::equal(a, a + 2, b, b + 2));
 #endif
   }
 
   return 0;
 }