[libc] Trivial implementation of std::optional

[jeffbailey]

Summary

This class has only the minimum functionality in it to provide what the
TZ variable parsing needs. In particular, the standard makes guarantees
about how trivial the destructors are, throws an expception if it's used
incorrectly, etc. There are also missing features.

Tested:
Trivial testsuite added, and use in development.

[jeffbailey]

Hi! I'm not expecting that this is in final shape, but I wanted to ask for an initial set of feedback from you. The test suite certainly needs expanding, but I'd love to get your initial thoughts on this approach, etc.

Thanks!

[tschuett]

Do you need the union and the Placeholder? In reset you reset the StoredValue. This implies something about T.

I would add asserts to catch misbehaviour.

The LLVM optional uses a union for storage.

libc/src/__support/CPP/Optional.h

27

The private is redundant or for documentation.

[jeffbailey]

In D129920#3657048, @tschuett wrote:

Do you need the union and the Placeholder? In reset you reset the StoredValue. This implies something about T.

I think I need the union because I don't want to construct the object if I'm not using it as in this case:

std::optional<std::string> foo() {
  return std::nullopt;
}

Does a union still have that property if it only has a single member? Or is there a different approach?

I would add asserts to catch misbehaviour.

Will do. It's almost tempting to also implement std::variant and use that since we'll probably want it later anyway.

The LLVM optional uses a union for storage.

Right. They're using the same approach that I am with:

union
{
    char __null_state_;
    value_type __val_;
};

I've just used the words Placeholder and StoredValue. They're using __engaged where I'm using InUse.

[tschuett]

If the LLVM optional uses a union, then it is probably a good idea.

I guess you are more interested in trivially copyable types.

[jeffbailey]

In D129920#3657405, @tschuett wrote:

If the LLVM optional uses a union, then it is probably a good idea.

I guess you are more interested in trivially copyable types.

It solves our current use, anyway. =) I could add the && versions if folks think they'll get used soon (or that this will be confusing to not have them for now). For this I was focused on what's needed for our case of implementing the TZ variable parsing (we use this for int, struct, and a string_view).

Thanks!

[gchatelet]

You'd also need to adjust the Bazel config.

libc/src/__support/CPP/Optional.h

16

According to our current style guide that would be NulloptT.
Note that I would be in favor of using the STL names whenever we're re-implementing them but that would be a separate discussion.

Do you want to limit it to POD types? Or to primitive types?

22–25

I would list the requirements for T here, AFAICT:

• default constructible
• copy constructible
• copy assignable
• destructible

48

You can drop noexpect here and below, exceptions are disabled throughout llvm-libc

[jeffbailey]

Updating with some review comments addressed, but not the asserts or the
testsuite, etc. Posting this in case you want this committed to unblock
https://reviews.llvm.org/D129918 and the fix-ups to come in a subsequent
change.

[jeffbailey]

On review, saw two other review comments that I could address easily.

[jeffbailey]

In D129920#3659436, @gchatelet wrote:

You'd also need to adjust the Bazel config.

Done.

[sivachandra]

In D129920#3664742, @jeffbailey wrote:

Updating with some review comments addressed, but not the asserts or the
testsuite, etc.

I think, starting with a simple implementation like this is OK. IMO, we do not have to mimic std::optional - IIUC, we want something similar for our convenience but not exactly equal. So, this is LGTM after expanding the testsuite. Please wait for Guillaume though.

libc/src/__support/CPP/Optional.h

22–25

I think Guilllaume is just asking you to list them for now. IIUC, except for the default constructible requirement, they are already enforced?

[gchatelet]

Please add the requirements on T for Optional as documentation and then this is good to go.

libc/src/__support/CPP/Optional.h

22–25

Yes exactly it's just to document the expectations and indeed "default constructible" might not be required (because of the union)
Ideally this would be checked upfront in the class body with some static_asserts and CPP traits. The aim here is to make the failing requirements obvious.

[jeffbailey]

It's late enough that I'm going to wait until morning to commit this, in case
Guillaume or others want to take a look at the test suite and comments.

Otherwise I already have an LGTM and will commit in the morning.

[jeffbailey]

libc/src/__support/CPP/Optional.h

22–25

I'm not sure where to put static_asserts in here. I think if it's not copy constructable/assignable or not destructable, compilation will simply fail right now. I couldn't think of what static_asserts to put in beyond this.

Feedback is always welcome, thanks!

[zero9178]

libc/src/__support/CPP/Optional.h

45

This copy constructor causes undefined behaviour in the case that t is not does not have a value. Shouldn't this be conditionally copying t.value() into StoredValue depending on whether t.has_value()?

(I am an outsider to the libc part of LLVM, but I am guessing you'll probably also want a copy assignment operator acting similarily)

[jeffbailey]

libc/src/__support/CPP/Optional.h

45

Oh bugger. This probably explains why everyone does the storage as a sub object.

Happily, I also found an implementation in llvm/include/llvm/ADT/optional.h that's a bit simpler than the one in libcxx, so I'll go with that. Gimme another day.

[gchatelet]

libc/src/__support/CPP/Optional.h

22–25

I would have put the static_assert in the body of the class so it fails right before it's used in any method.
That said I'm not sure we have the type traits handy (since we have to reimplement most of them).
I don't want to block the patch any longer here. We can do it as a follow up.

45

Yes absolutely. And because of the union you'll have to initialize either Placeholder or StoredValue, so I think the code has to move into the body of the copy constructor.

And yes, if you have the copy ctor, you also want the copy assignment operator.

Thx for noticing @zero9178 .

[jeffbailey]

Added two tests to test code review comment that noticed that an unset
optional would become set on assignment. Then fixed the code for
that situation by factoring our storage into a consistent object.

Since the decision to use the C++ casing, changed Optional,
Nullopt and NulloptT to optional, nullopt, and nullopt_t for this
upload.

[jeffbailey]

Oops, I noticed that I didn't have clang-format installed. This
diff fixes one formatting error.

[jeffbailey]

libc/src/__support/CPP/Optional.h

22–25

I'd like to do this as a follow-up. I wrestled with type_traits here for a bunch of the last week and we don't have the ones that we need and I don't understand them well enough to implement them. (And I'd like to unblock two patches that want to use this)

45

I think this is done now and covered with a test.

The Kingdom Valley is a community of people who want to make a difference in their lives and in the world. They believe that through living an authentic life and creating a strong family and a strong community, they can achieve a better future for themselves and for those around them. The community has been growing steadily since its inception in 1998. It now has over 2000 members, with new members joining every day.

[jeffbailey]

I think this closes out the comments. I'll leave this another day before submitting. Thanks all!

libc/src/__support/CPP/Optional.h

16

Per the separate discussion, keeping as nullopt_t

I'll add more constraints to this once we have more type traits in place.

22–25

Doing as a follow-up per this comment.

45

This code rewritten.

libc/src/__support/CPP/CMakeLists.txt

 
 add_header_library(
   string_view
   HDRS
     StringView.h
 )
 
 add_header_library(
+  optional
+  HDRS
+    Optional.h
+)
+
+add_header_library(
   type_traits
   HDRS
     TypeTraits.h
   DEPENDS
     .uint
 )
 
 add_header_library(

libc/src/__support/CPP/Optional.h

+//===-- Standalone implementation std::optional -----------------*- 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_OPTIONAL_H
+#define LLVM_LIBC_SRC_SUPPORT_CPP_OPTIONAL_H
+
+namespace __llvm_libc {
+namespace cpp {
+
+// Trivial nullopt_t struct.
+struct nullopt_t {};
+
+// nullopt that can be used and returned
+inline constexpr nullopt_t nullopt;
+
+// This is very simple implementation of the std::optional class.  There are a
+// number of guarantees in the standard that are not made here.
+//
+// This class will be extended as needed in future.
+//
+// T currently needs to be a scalar or an object with the following properties:
+//  - copy constructible
+//  - copy assignable
+//  - destructible
+template <class T> class optional {
+
+  template <class E> class OptionalStorage {
+  public:
+    union {
+      E StoredValue;
+      char Placeholder;
+    };
+    bool InUse = false;
+
+    OptionalStorage() : Placeholder(0), InUse(false) {}
+    OptionalStorage(const E &t) : StoredValue(t), InUse(true) {}
+    ~OptionalStorage() {
+    if (InUse)
+      StoredValue.~E();
+    }
+
+    void reset() {
+      if (InUse)
+        StoredValue.~E();
+      InUse = false;
+    }
+  };
+
+OptionalStorage<T> Storage;
+
+public:
+  optional() {}
+  optional(nullopt_t) {}
+  optional(const T &t) : Storage(t) {}
+
+  T value() const { return Storage.StoredValue; }
+
+  bool has_value() const { return Storage.InUse; }
+
+  void reset() {
+    Storage.reset();
+  }
+
+  constexpr explicit operator bool() const { return Storage.InUse; }
+
+  constexpr optional &operator=(nullopt_t) {
+    reset();
+    return *this;
+  }
+
+  constexpr T &operator*() & { return Storage.StoredValue; }
+
+  constexpr const T &operator*() const & { return Storage.StoredValue; }
+};
+} // namespace cpp
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_SUPPORT_CPP_OPTIONAL_H

libc/test/src/__support/CPP/CMakeLists.txt

add_libc_unittest(
   blockstore_test
   SUITE
     libc_cpp_utils_unittests
   SRCS
     blockstore_test.cpp
   DEPENDS
     libc.src.__support.CPP.blockstore
 )
+
+add_libc_unittest(
+  optional_test
+  SUITE
+    libc_cpp_utils_unittests
+  SRCS
+    optional_test.cpp
+  DEPENDS
+  libc.src.__support.CPP.optional
+
+)

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

+//===-- Unittests for Optional --------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/__support/CPP/Optional.h"
+#include "utils/UnitTest/Test.h"
+
+using __llvm_libc::cpp::nullopt;
+using __llvm_libc::cpp::optional;
+
+// This has clase has two properties for testing:
+// 1) No default constructor
+// 2) A non-trivial destructor with an observable side-effect
+class Contrived {
+  int *_a;
+
+public:
+  Contrived(int *a) : _a(a) {}
+  ~Contrived() { (*_a)++; }
+};
+
+TEST(LlvmLibcOptionalTest, Tests) {
+  optional<int> Trivial1(12);
+  ASSERT_TRUE(Trivial1.has_value());
+  ASSERT_EQ(Trivial1.value(), 12);
+  ASSERT_EQ(*Trivial1, 12);
+  Trivial1.reset();
+  ASSERT_FALSE(Trivial1.has_value());
+
+  optional<int> Trivial2(12);
+  ASSERT_TRUE(Trivial2.has_value());
+  Trivial2 = nullopt;
+  ASSERT_FALSE(Trivial2.has_value());
+
+  // For this test case, the destructor increments the pointed-to value.
+  int holding = 1;
+  optional<Contrived> Complicated(&holding);
+  // Destructor was run once as part of copying the object.
+  ASSERT_EQ(holding, 2);
+  // Destructor was run a second time as part of destruction.
+  Complicated.reset();
+  ASSERT_EQ(holding, 3);
+  // Destructor was not run a third time as the object is already destroyed.
+  Complicated.reset();
+  ASSERT_EQ(holding, 3);
+
+  // Test that assigning an optional to another works when set
+  optional<int> Trivial3(12);
+  optional<int> Trivial4 = Trivial3;
+  ASSERT_TRUE(Trivial4.has_value());
+  ASSERT_EQ(Trivial4.value(), 12);
+
+  // Test that assigning an option to another works when unset
+  optional<int> Trivial5;
+  ASSERT_FALSE(Trivial5.has_value());
+  optional<int> Trivial6 = Trivial5;
+  ASSERT_FALSE(Trivial6.has_value());
+}

utils/bazel/llvm-project-overlay/libc/BUILD.bazel

 
 cc_library(
     name = "__support_cpp_limits",
     hdrs = ["src/__support/CPP/Limits.h"],
     deps = [":libc_root", "__support_cpp_uint"],
 )
 
 cc_library(
+    name = "__support_cpp_optional",
+    hdrs = ["src/__support/CPP/Optional.h"],
+    deps = [":libc_root"],
+)
+
+cc_library(
     name = "__support_cpp_string_view",
     hdrs = ["src/__support/CPP/StringView.h"],
     deps = [":libc_root"],
 )
 
 cc_library(
     name = "__support_cpp_uint",
     hdrs = [