Constexpr unions

I assume you are already familiar with constexpr functions. (If not, see a short introduction here.) In this post I wanted to share my experience with using unions in constant expressions. Unions are not very popular due to type-safety hole they open, but they offer some capabilities that I found priceless when working with Fernando Cacciola on std::optional proposal.

Background

Do you know Boost.Optional library? In very short, boost::optional<T> is a ‘compound’ value that can store any value of T plus one additional state that indicates that no value of T is currently stored. It is a nullable T.

One of the features that boost::optional offers is that when you initialize it to store the null state, it does not construct any T at all. It does not even call T’s default constructor — for performance reasons, and also in cases where T is not default-constructible. One way to implement this is to provide some raw memory buffer big enough to store an object of type T and use in-place constructor to initialize it only when necessary:

template <typename T>
class optional
{
  bool initialized_;
  char storage_[ sizeof(T) ];
  // ...
};

This is only to give you an idea of a possible implementation. In practice, it would not work due to alignment reasons; we would have to use std::aligned_storage; or we would have to use a discriminated union — this has been described in detail by Cassio Neri in ACCU Overload #112. The null-state constructor and ‘real-value’ constructor can be implemented as:

optional<T>::optional(none_t)  // null-state tag
{
  initialized_ = false;
  // leave storage_ uninitialized
};

optional<T>::optional(T const& val)
{
  new (storage_) T{val};       // placement new
  initialized_ = true;
};

The definition of the destructor, as you already figured out, is similar to:

optional<T>::~optional()
{
  if (initialized_) {
    static_cast<T*>(storage_) -> T::~T(); 
  }
};

Problem 1

In case of the std::optional, there are other features that are required of the library. One such feature is that std::optional<T> shall be a literal type: a type whose objects can be used as compile-time constants. One constraint that the Standard imposes on literal types is that they should provide a trivial destructor: a destructor that does nothing. As we can see above, optional’s destructor has to do something, so we cannot achieve our goal in general. However, we can achieve our goal for certain Ts that have a trivial destructor themselves. Imagine that T is int: we do not have to call int’s destructor — because it is trivial. Here we also arrive at the practical definition of a trivial destructor: it is a destructor that we can skip (simply not call it) without any harm.

Another requirement for literal types is that they should have at least one constexpr constructor. This constructor(s) will be used to create compile-time constants. However, in order to avoid “compile-time undefined behavior”, the Standard imposes a number of constraints on constexpr constructors and their types to make sure that no data member or base-class sub-object is left uninitialized. Thus, our implementation of optional with appropriately sized array of chars will not work because in “value” constructor the array is not initialized in member-initializer-list. We could fill the array with zeros in the null-state constructor, but this zero-fill is also a run-time cost. We would have a similar problem if we used std::aligned_storage for implementation. We also cannot use a simple discriminated union implementation (as proposed in ACCU Overload #112):

template <typename T>
class optional
{
  bool initialized_;
  union { T storage_ }; // anonymous union
};

Because in order to create an “uninitialized” optional we would have to either leave the anonymous union uninitialized, which is not acceptable in constexpr functions, or default-initialize storage_, but this is counter to our design goal: we wanted to skip T’s default construction.

Problem 2

Another ambitious design goal is the properties of the function that extracts the value contained in the optional object. In boost::optional as well as in the proposed std::optional in order to access the contained value we use operator* (the indirection operator). In order to guarantee the maximum run-time performance, we do not check if the optional object has been initialized to store a meaningful value: we state this requirement as function’s precondition, and blindly access the storage for our T:

explicit optional<T>::operator bool() const // check for being initialized
{
  return initialized_;
};

T const& optional<T>::operator*() const
// precondition: bool(*this)
{
  return *static_cast<T*>(storage_);
}

At the same time, we want to be able to call operator* at compile-time, and in this case, we want the compilation to fail if we are trying to access the value form an uninitialized optional object. We could be tempted to use the method described in my other post on compile-time computations:

constexpr explicit optional<T>::operator bool()
{
  return initialized_;
};

constexpr T const& optional<T>::operator*()
{
  return bool(*this) ? *static_cast<T*>(storage_) : throw uninitialized_optional();
}

This is not acceptable, though. We would achieve the desired compile-time behavior, but we would force a check at run-time which would hit our performance. Is it possible to do the check at compile-time, but skip it at run-time?

Solution

Both these problems are solved by using a union of T and a dummy, empty class:

struct dummy_t{};

template <typename T>
union optional_storage
{
  static_assert( is_trivially_destructible<T>::value, "" );

  dummy_t dummy_;
  T       value_;

  constexpr optional_storage()            // null-state ctor
    : dummy_{} {}

  constexpr optional_storage(T const& v)  // value ctor
    : value_{v} {}

  ~optional_storage() = default;          // trivial dtor
};

There are special rules for using unions in constexpr functions and constructors. We are required to initialize only one member of a union. (Obviously, you cannot initialize more than one, because they occupy the same storage.) This member is called active. In case we want to leave the storage uninitialized, we initialize the dummy member. This meets all the formal requirements of compile-time initialization, but since dummy_t contains no data, its value-initialization costs nothing in run-time.

Second, reading (strictly speaking: triggering lvalue-to-rvalue conversion of) the inactive member of a union is defined as being not a core constant expression, and using it in compile-time computations is a compile-time error. The following example illustrates this:

constexpr optional_storage<int> oi{1}; // ok
constexpr int i = oi.value_;           // ok
static_assert(i == 1, "");             // ok

constexpr optional_storage<int> oj{};  // ok
constexpr int j = oj.value_;           // compile-time error

Class template optional (for trivially destructible Ts) can be implemented as:

template <typename T>
// requires: is_trivially_destructible<T>::value
class optional
{
  bool initialized_;
  optional_storage<T> storage_;

public:
  constexpr optional(none_t) : initialized_{false}, storage_{} {}

  constexpr optional(T const& v) : initialized_{true}, storage_{v} {}

  constexpr T const& operator*() 
  // precondition: bool(*this) 
  {
    return storage_.value_;
  }

  // ...
};

The compile-time error message in operator* is not ideal: it does not mention optional object being uninitialized, but only the usage of inactive union member. However, the primary goal is achieved: we refuse to compile the invalid value access.

You can find the reference implementation of the proposed std::optional here.