[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 ↗

(On Diff #548225)

why is this removed?

198 ↗

(On Diff #548225)

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 ↗

(On Diff #548225)

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