[libc] Extend optional to support non trivially destructible objects

[mikhail.ramalho]

Summary

This patch moves the storage from inside the libc's optional class to
its own set of class, so we can support non-trivially destructible
objects.

These new classes check if the class is or isn't non trivially
destructible and instantiate the correct base class, i.e., we explicitly
call the destructor if an object is not trivially destructible.

The motivation is to support cpp::optional<UInt<128>> (used by
UInt<T>::div), which is used when a platform does not support native
int128_t types (e.g., riscv32).

The code here is a trimmed-down version of llvm::optional.

[jhuber6]

Surprisingly large amount of changes in optional.cpp considering the old version was also the llvm::optional without the non-trivial OptionalStorage SFINAE.

[michaelrj]

Before I review this patch, I want to confirm that this is the right strategy. If the main goal is to support Uint<> in optional is there a way to do that without a complete replacement of optional?

[mikhail.ramalho]

In D150211#4330579, @michaelrj wrote:

Before I review this patch, I want to confirm that this is the right strategy. If the main goal is to support Uint<> in optional is there a way to do that without a complete replacement of optional?

We need these changes because of
constexpr optional<UInt<Bits>> UInt<T>::div(const UInt<Bits> &other),
used by
constexpr UInt<Bits> UInt<T>::operator/(const UInt<Bits> &other) const.

The optional only seems to be checked here: https://github.com/mikhailramalho/llvm-project/blob/main/libc/test/src/__support/uint_test.cpp#L204, so an alternative would be to remove the optional return from UInt<T>::div, delete this test and maybe abort when we divide by zero.

But I would also argue to keep these changes to optional, the main reason being to avoid copies like the fixed test.

[michaelrj]

I agree that optional supporting UInt is good, my question is whether replacing the existing implementation with a completely new one is the best strategy.

[mikhail.ramalho]

Fixed compilation with clang < 16, where there is no add_lvalue_reference and add_rvalue_reference

[sivachandra]

I am not sure this generalization of cpp::optional is required. Can you give us a simplified use case which is causing problems for you?

[mikhail.ramalho]

This is required because libc's UInt<T> can't be used with libc's optional, when trying to get libc built for riscv32, we get the following errors:

/home/mgadelha/tools/llvm-project/libc/src/__support/UInt.h:347:12: note: non-literal type 'optional<UInt<128U>>' cannot be used in a constant expression
    return remainder;
           ^
/home/mgadelha/tools/llvm-project/libc/src/__support/UInt.h:352:12: note: in call to '&result->div(COUNT)'
    result.div(other);
           ^
/home/mgadelha/tools/llvm-project/libc/test/src/math/CopySignTest.h:37:44: note: in call to '&UIntType(-1)->operator/(COUNT)'
    constexpr UIntType STEP = UIntType(-1) / COUNT;
                                           ^
1 error generated.

[mikhail.ramalho]

ping

[michaelrj]

Ideally we would not like to replace the current optional implementation. Instead we would prefer to modify the current optional so that it supports the features that we need, and only replace it if modification isn't practical. Can you explain why you think that modifying the existing implementation of optional cannot work for your use case?

[mikhail.ramalho]

In D150211#4396897, @michaelrj wrote:

Ideally we would not like to replace the current optional implementation. Instead we would prefer to modify the current optional so that it supports the features that we need, and only replace it if modification isn't practical. Can you explain why you think that modifying the existing implementation of optional cannot work for your use case?

Hey Michael, sorry for taking so long to answer here.

So, although this PR includes several line changes, the overall implementation is not that different from the current optional in libc.

The major differences are:

1. In the storage class:
2. A new base class called OptionalStorageBase<T> for OptionalStorage<T>. Mainly to avoid duplicated code in derived classes.
3. Specialization of OptionalStorage<T> for when T is not trivially destructive, not trivially copy assignable/copy constructible, and not trivially move assignable/move constructible, + some combinations of these properties.

2. In the optional class:
3. A new base class called OptionalBaseImpl<T> for OptionalBase<T> and optional<T>, also mainly to avoid duplicated code in derived classes.
4. A new class OptionalBaseImpl<T> and specialization for when T is not copy constructible, and not move constructible, + some combinations of these properties.
5. Changed the optional<T> class to inherit from OptionalBase<T> and support objects with the properties above.

May I ask you to reconsider this PR as is?

I _think_ I can reduce it to support only the case we need (UInt<T> is not trivially destructible), but when I ported this code from llvm::optional, I decided to support all cases in case we need it for the future.

[michaelrj]

I will think about it, but as a general note we don't really want to add a whole bunch of features we aren't using. That sort of untested and unused code has a tendency to break with newer changes.

[mikhail.ramalho]

In D150211#4554897, @michaelrj wrote:

I will think about it, but as a general note we don't really want to add a whole bunch of features we aren't using. That sort of untested and unused code has a tendency to break with newer changes.

Thanks for considering it, Michael, but I get your point, I'll try to remove the unused pieces from this PR.

[mikhail.ramalho]

Updated PR to support only non trivial destructible objects

[mikhail.ramalho]

Hey Michael, I've managed to reduce the implementation to support only the needed parts.

The implementation of optional in libc now supports non trivial destructive objects and as a bonus a made all the methods constexpr

[mikhail.ramalho]

Rebased

[mikhail.ramalho]

ping

[michaelrj]

I have a bunch of comments, but I think I'm willing to accept the update to optional once review is done. The important part is making it more clear that this patch is focused on modifying OptionalStorage to support destructors.

libc/src/__support/CPP/optional.h

40–65

I think having the internal OptionalStorage struct inside OptionalStorageBase is confusing. Specifically it makes it unclear which functions are part of OptionalStorageBase vs OptionalStorage in a code-review setting where things like colored parentheses aren't available.

41

This struct shouldn't be named the same as the other, completely separate struct that inherits from OptionalStorageBase. It's very confusing to read.

66

you don't need to specify public here, structs are public by default.

75–81

is this actually necessary? The objects that we're wrapping in optional are mostly simple structs or primitives.

101–107

if these are all default, you don't need to specify them.

libc/src/__support/CPP/type_traits.h

63

why is this removed?

198

this is unnecessary. You can just use && and enable_if_t. See span.h for an example of how that works. Same for __not_

libc/src/__support/UInt.h

379 ↗

(On Diff #548225)

this doesn't need to be changed

libc/test/src/__support/CPP/optional_test.cpp

46 ↗

(On Diff #548225)

is the object no longer copied? If so, is that intended behavior?

[mikhail.ramalho]

• addressed comments
• rebased
• updated commit message

libc/src/__support/CPP/optional.h

75–81

It was being used for forwarding the arguments in the new move constructor I've added; by removing it, I'll have to revert the test changes.

libc/src/__support/CPP/type_traits.h

63

It wasn't being used, but I'll add it back.

[michaelrj]

This patch is looking a lot better. I think it should be good to go after dealing with the structs

libc/src/__support/CPP/optional.h

41

Is it possible to condense these structs? It feels a bit overkill to have three structs when there are only two possible variations of the template (trivially destructible and not).

[mikhail.ramalho]

In D150211#4581518, @michaelrj wrote:

This patch is looking a lot better. I think it should be good to go after dealing with the structs

I think that was the minimal way of doing it without duplicating the code
but I can do something like the glibc's optional
it has only two classes for the optional, but there is a lot of duplicated code since the only difference between the two classes is the destructor call. See:
https://github.com/gcc-mirror/gcc/blob/fab08d12b40ad637c5a4ce8e026fb43cd3f0fad1/libstdc%2B%2B-v3/include/experimental/optional#L136
https://github.com/gcc-mirror/gcc/blob/fab08d12b40ad637c5a4ce8e026fb43cd3f0fad1/libstdc%2B%2B-v3/include/experimental/optional#L278
the only difference between these two classes is:
https://github.com/gcc-mirror/gcc/blob/fab08d12b40ad637c5a4ce8e026fb43cd3f0fad1/libstdc%2B%2B-v3/include/experimental/optional#L353

WDYT?

[mikhail.ramalho]

Move OptionalStorage to inside the optional class

[mikhail.ramalho]

I've managed to reduce the implementation even further:

• moved the OptionalStorage to inside the class optional, like it was before, but now the partial specialization for trivially destructible objects is there as well.
• removed all value() methods from OptionalStorage() to reduce duplicated code. Now store_value is accessed directly.
• moved in_use to the class optional. It's a private member there now.

[michaelrj]

LGTM, I really appreciate you sticking with it and getting this patch to its final state. I know it's been a lot of effort, but the result is really something you should be proud of.

[mikhail.ramalho]

In D150211#4586341, @michaelrj wrote:

LGTM, I really appreciate you sticking with it and getting this patch to its final state. I know it's been a lot of effort, but the result is really something you should be proud of.

thanks, Michael

[mikhail.ramalho]

@michaelrj can you take another look at the changes at type_traits.h?

I had to add this code because gcc doesn't have __is_trivially_destructible and here's an explanation of why we can't only use gcc's __has_trivial_destructor (link):

For historical reasons, the name of this compiler builtin is not __is_trivially_destructible(T)
but rather __has_trivial_destructor(T). Furthermore, it turns out that the builtin evaluates to
true even for a class type with a deleted destructor! So we first need to check that the type is
destructible; and then, if it is, we can ask the magic builtin whether that destructor is indeed trivial.

[mikhail.ramalho]

Fix for gcc

[michaelrj]

Given the size, I'd suggest splitting the type_traits.h changes into a separate patch. They look fine and are clearly necessary for the optional change, but are larger than I'd like for one patch.

[mikhail.ramalho]

Moved type_traits changes to a different patch

libc/src/__support/CPP/optional.h

 
 // in_place that can be used in the constructor.
 LIBC_INLINE_VAR constexpr in_place_t in_place{};
 
 // This is very simple implementation of the std::optional class. It makes
 // several assumptions that the underlying type is trivially constructable,
 // copyable, or movable.
 template <typename T> class optional {
-  template <typename U> class OptionalStorage {
+  template <typename U, bool = !is_trivially_destructible<U>::value>
+  struct OptionalStorage {
     union {
       char empty;
       U stored_value;
     };
-    bool in_use;
 
-  public:
-    LIBC_INLINE ~OptionalStorage() { reset(); }
-
-    LIBC_INLINE constexpr OptionalStorage() : empty(), in_use(false) {}
+    LIBC_INLINE ~OptionalStorage() { stored_value.~U(); }
+    LIBC_INLINE constexpr OptionalStorage() : empty() {}
 
     template <typename... Args>
     LIBC_INLINE constexpr explicit OptionalStorage(in_place_t, Args &&...args)
-        : stored_value(forward<Args>(args)...), in_use(true) {}
+        : stored_value(forward<Args>(args)...) {}
+  };
 
-    LIBC_INLINE void reset() {
-      if (in_use)
-        stored_value.~U();
-      in_use = false;
-    }
+  template <typename U> struct OptionalStorage<U, false> {
+    union {
+      char empty;
+      U stored_value;
+    };
 
-    LIBC_INLINE constexpr bool has_value() const { return in_use; }
+    // The only difference is that this class doesn't have a destructor.
+    LIBC_INLINE constexpr OptionalStorage() : empty() {}
 
-    LIBC_INLINE U &value() & { return stored_value; }
-    LIBC_INLINE constexpr U const &value() const & { return stored_value; }
-    LIBC_INLINE U &&value() && { return move(stored_value); }
+    template <typename... Args>
+    LIBC_INLINE constexpr explicit OptionalStorage(in_place_t, Args &&...args)
+        : stored_value(forward<Args>(args)...) {}
   };
 
   OptionalStorage<T> storage;
+  bool in_use = false;
 
 public:
   LIBC_INLINE constexpr optional() = default;
   LIBC_INLINE constexpr optional(nullopt_t) {}
 
-  LIBC_INLINE constexpr optional(const T &t) : storage(in_place, t) {}
+  LIBC_INLINE constexpr optional(const T &t)
+      : storage(in_place, t), in_use(true) {}
   LIBC_INLINE constexpr optional(const optional &) = default;
 
-  LIBC_INLINE constexpr optional(T &&t) : storage(in_place, move(t)) {}
+  LIBC_INLINE constexpr optional(T &&t)
+      : storage(in_place, move(t)), in_use(true) {}
   LIBC_INLINE constexpr optional(optional &&O) = default;
 
   template <typename... ArgTypes>
   LIBC_INLINE constexpr optional(in_place_t, ArgTypes &&...Args)
-      : storage(in_place, forward<ArgTypes>(Args)...) {}
+      : storage(in_place, forward<ArgTypes>(Args)...), in_use(true) {}
 
-  LIBC_INLINE optional &operator=(T &&t) {
+  LIBC_INLINE constexpr optional &operator=(T &&t) {
     storage = move(t);
     return *this;
   }
-  LIBC_INLINE optional &operator=(optional &&) = default;
-
-  LIBC_INLINE static constexpr optional create(const T *t) {
-    return t ? optional(*t) : optional();
-  }
+  LIBC_INLINE constexpr optional &operator=(optional &&) = default;
 
-  LIBC_INLINE optional &operator=(const T &t) {
+  LIBC_INLINE constexpr optional &operator=(const T &t) {
     storage = t;
     return *this;
   }
-  LIBC_INLINE optional &operator=(const optional &) = default;
+  LIBC_INLINE constexpr optional &operator=(const optional &) = default;
 
-  LIBC_INLINE void reset() { storage.reset(); }
+  LIBC_INLINE constexpr void reset() {
+    if (in_use)
+      storage.~OptionalStorage();
+    in_use = false;
+  }
 
-  LIBC_INLINE constexpr const T &value() const & { return storage.value(); }
-  LIBC_INLINE T &value() & { return storage.value(); }
+  LIBC_INLINE constexpr const T &value() const & {
+    return storage.stored_value;
+  }
 
-  LIBC_INLINE constexpr explicit operator bool() const { return has_value(); }
-  LIBC_INLINE constexpr bool has_value() const { return storage.has_value(); }
-  LIBC_INLINE constexpr const T *operator->() const { return &storage.value(); }
-  LIBC_INLINE T *operator->() { return &storage.value(); }
-  LIBC_INLINE constexpr const T &operator*() const & { return value(); }
-  LIBC_INLINE T &operator*() & { return value(); }
+  LIBC_INLINE constexpr T &value() & { return storage.stored_value; }
 
-  template <typename U> LIBC_INLINE constexpr T value_or(U &&value) const & {
-    return has_value() ? value() : forward<U>(value);
+  LIBC_INLINE constexpr explicit operator bool() const { return in_use; }
+  LIBC_INLINE constexpr bool has_value() const { return in_use; }
+  LIBC_INLINE constexpr const T *operator->() const {
+    return &storage.stored_value;
   }
+  LIBC_INLINE constexpr T *operator->() { return &storage.stored_value; }
+  LIBC_INLINE constexpr const T &operator*() const & {
+    return storage.stored_value;
+  }
+  LIBC_INLINE constexpr T &operator*() & { return storage.stored_value; }
 
-  LIBC_INLINE T &&value() && { return move(storage.value()); }
-  LIBC_INLINE T &&operator*() && { return move(storage.value()); }
+  LIBC_INLINE constexpr T &&value() && { return move(storage.stored_value); }
+  LIBC_INLINE constexpr T &&operator*() && {
+    return move(storage.stored_value);
+  }
 };
 
 } // namespace cpp
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_SUPPORT_CPP_OPTIONAL_H

libc/src/__support/CPP/type_traits.h

 //===-- Self contained C++ type traits --------------------------*- C++ -*-===//
 //
 // 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 LLVM_LIBC_SRC_SUPPORT_CPP_TYPETRAITS_H
 #define LLVM_LIBC_SRC_SUPPORT_CPP_TYPETRAITS_H
 
 #include "src/__support/macros/attributes.h"
 
+#include <stddef.h> // For size_t.
+
 namespace __llvm_libc {
 namespace cpp {
 
 template <typename T> struct type_identity {
   using type = T;
 };
 
 template <bool B, typename T> struct enable_if;
 template <typename T> struct enable_if<true, T> : type_identity<T> {};
 template <bool B, typename T = void>
 using enable_if_t = typename enable_if<B, T>::type;
 
 template <typename T, T v> struct integral_constant {
   using value_type = T;
   LIBC_INLINE_VAR static constexpr T value = v;
 };
 using true_type = cpp::integral_constant<bool, true>;
 using false_type = cpp::integral_constant<bool, false>;
 
+template <bool V> using bool_constant = integral_constant<bool, V>;
+
 template <class T>
 struct is_trivially_copyable
     : public integral_constant<bool, __is_trivially_copyable(T)> {};
 
 template <class T, class... Args>
 struct is_trivially_constructible
     : integral_constant<bool, __is_trivially_constructible(T, Args...)> {};
 

 template <typename T> using remove_cv_t = typename remove_cv<T>::type;
 
 template <typename T> struct remove_reference : type_identity<T> {};
 template <typename T> struct remove_reference<T &> : type_identity<T> {};
 template <typename T> struct remove_reference<T &&> : type_identity<T> {};
 template <typename T>
 using remove_reference_t = typename remove_reference<T>::type;
 
 template <typename T> struct add_rvalue_reference : type_identity<T &&> {};
 
 template <typename T> struct remove_cvref {
   using type = remove_cv_t<remove_reference_t<T>>;
 };
 template <typename T> using remove_cvref_t = typename remove_cvref<T>::type;
 
 namespace details {
 template <typename T, typename... Args>

 // Compile time type selection.
 template <bool B, typename T, typename F>
 struct conditional : type_identity<T> {};
 template <typename T, typename F>
 struct conditional<false, T, F> : type_identity<F> {};
 template <bool B, typename T, typename F>
 using conditional_t = typename conditional<B, T, F>::type;
 
 template <typename T>
 struct is_void : is_same<void, typename remove_cv<T>::type> {};
 template <typename T>
 LIBC_INLINE_VAR constexpr bool is_void_v = is_void<T>::value;
 template <class T> T declval();
 
 // Compile time checks on implicit conversions.
 namespace details {
 template <typename...> using void_t = void;
 template <typename T> void convertible_to_helper(T);
 } // namespace details
 
 template <typename F, typename T, typename = void>
 LIBC_INLINE_VAR constexpr bool is_convertible_v = false;
 
 // FIXME: This should use LIBC_INLINE_VAR, but clang buggily complains about
 // this when LIBC_INLINE_VAR uses [[clang::internal_linkage]].
 template <typename F, typename T>
 constexpr bool
     is_convertible_v<F, T,
                      details::void_t<decltype(details::convertible_to_helper<T>(
                          declval<F>()))>> = true;
 
+#if __has_builtin(__is_lvalue_reference) &&                                    \
+    __has_builtin(__is_rvalue_reference) && __has_builtin(__is_reference)
+
+template <typename T>
+struct is_lvalue_reference : bool_constant<__is_lvalue_reference(T)> {};
+template <typename T>
+struct is_rvalue_reference : bool_constant<__is_rvalue_reference(T)> {};
+template <typename T> struct is_reference : bool_constant<__is_reference(T)> {};
+
+#else // __has_builtin(__is_lvalue_reference) && etc...
+
+template <typename T> struct is_lvalue_reference : public false_type {};
+template <typename T> struct is_lvalue_reference<T &> : public true_type {};
+
+template <typename T> struct is_rvalue_reference : public false_type {};
+template <typename T> struct is_rvalue_reference<T &&> : public true_type {};
+
+template <typename T> struct is_reference : public false_type {};
+template <typename T> struct is_reference<T &> : public true_type {};
+template <typename T> struct is_reference<T &&> : public true_type {};
+
+#endif // __has_builtin(__is_lvalue_reference) && etc...
+
+#if __has_builtin(__remove_all_extents)
+template <typename T> using __remove_all_extents_t = __remove_all_extents(T);
+#else
+template <typename T> struct remove_all_extents {
+  typedef T type;
+};
+template <typename T> struct remove_all_extents<T[]> {
+  typedef typename remove_all_extents<T>::type type;
+};
+template <typename T, size_t _Np> struct remove_all_extents<T[_Np]> {
+  typedef typename remove_all_extents<T>::type type;
+};
+
+template <typename T>
+using __remove_all_extents_t = typename remove_all_extents<T>::type;
+#endif // __has_builtin(__remove_all_extents)
+
+#if __has_builtin(__is_function)
+
+template <typename T>
+struct is_function : integral_constant<bool, __is_function(T)> {};
+
+#else
+
+template <typename T>
+struct is_function
+    : public integral_constant<bool, !(is_reference<T>::value ||
+                                       is_const<const T>::value)> {};
+
+#endif // __has_builtin(__is_function)
+
+#if __has_builtin(__is_destructible)
+
+template <typename T>
+struct is_destructible : bool_constant<__is_destructible(T)> {};
+
+#else // __has_builtin(__is_destructible)
+
+//  if it's a reference, return true
+//  if it's a function, return false
+//  if it's   void,     return false
+//  if it's an array of unknown bound, return false
+//  Otherwise, return "declval<T&>().~T()" is well-formed
+//    where T is remove_all_extents<T>::type
+
+template <typename> struct __is_destructible_apply {
+  typedef int type;
+};
+
+template <typename T> struct __is_destructor_wellformed {
+  template <typename T1>
+  static true_type __test(
+      typename __is_destructible_apply<decltype(declval<T1 &>().~T1())>::type);
+
+  template <typename T1> static false_type __test(...);
+
+  static const bool value = decltype(__test<T>(12))::value;
+};
+
+template <typename T, bool> struct __destructible_imp;
+
+template <typename T>
+struct __destructible_imp<T, false>
+    : public integral_constant<
+          bool, __is_destructor_wellformed<__remove_all_extents_t<T>>::value> {
+};
+
+template <typename T> struct __destructible_imp<T, true> : public true_type {};
+
+template <typename T, bool> struct __destructible_false;
+template <typename T>
+struct __destructible_false<T, false>
+    : public __destructible_imp<T, is_reference<T>::value> {};
+template <typename T>
+struct __destructible_false<T, true> : public false_type {};
+
+template <typename T>
+struct is_destructible : public __destructible_false<T, is_function<T>::value> {
+};
+template <typename T> struct is_destructible<T[]> : public false_type {};
+template <> struct is_destructible<void> : public false_type {};
+
+#endif // __has_builtin(__is_destructible)
+
+#if __has_builtin(__is_trivially_destructible)
+
+template <typename T>
+struct is_trivially_destructible
+    : public integral_constant<bool, __is_trivially_destructible(T)> {};
+
+#elif __has_builtin(__has_trivial_destructor)
+
+template <typename T>
+struct is_trivially_destructible
+    : public integral_constant<
+          bool, is_destructible<T>::value &&__has_trivial_destructor(T)> {};
+
+#endif // __has_builtin(__is_trivially_destructible)
+
 } // namespace cpp
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_SUPPORT_CPP_TYPETRAITS_H