23 Mar, 2015

Eggs.Variant - Part II (the constexpr experience)

Ruminations on the development of Eggs.Variant, a C++11/14 generic, type-safe, discriminated union. Part I explored a straightforward implementation based on untyped raw storage appropriate to hold any of the variant members. It was noted, however, that such an implementation would never be constexpr-aware. It's time to throw it away and start from scratch in order to properly support constexpr.

Introduction

The goal is to make variant<Ts> a literal type —one that can be used in constant expressions— when all types in Ts are literal types, and to mark as many functions constexpr as possible. A class type is a literal type if it has all of the following properties:

3.9 [basic.types]/10 [...]

  • it has a trivial destructor,
  • it is an aggregate type (8.5.1) or has at least one constexpr constructor or constructor template that is not a copy or move constructor, and
  • all of its non-static data members and base classes are of non-volatile literal types.

The previous implementation uses std::aligned_union yielded POD type as raw storage to hold the active member (if any). It has a trivially destructible specialization for trivially destructible members:

template <bool TriviallyDestructible, typename ...Ts>
struct storage;

template <typename ...Ts>
struct storage<true, Ts...> {
  ~storage() = default; // trivial

  typename std::aligned_union<0, Ts...>::type buffer;
  std::size_t which;
};

template <typename ...Ts>
struct storage<false, Ts...> {
  ~storage() {
    // dispatch to the appropriate destructor
  }

  typename std::aligned_union<0, Ts...>::type buffer;
  std::size_t which;
};

template <typename ...Ts>
class variant { /*...*/ }:

Since it is not an aggregate type, all it is missing to be a literal type is a constexpr constructor:

template <typename ...Ts>
class variant {
  static constexpr bool _trivially_destructible =
      _all_of<std::is_trivially_destructible<Ts>...>::value;

public:
  static constexpr std::size_t npos = std::size_t(-1);

  // `constexpr` constructor that is not a copy or move constructor
  constexpr variant() noexcept
    : _storage{}
  {}

  // trivial if all types in Ts are trivially destructible
  ~variant() = default;

  constexpr std::size_t which() const noexcept { // not quite useful yet
    return _storage.which == 0 ? npos : _storage.which - 1;
  }

  /*...*/

private:
  // literal type if all types in Ts are trivially destructible
  storage<_trivially_destructible, Ts...> _storage;
};

The only possible constexpr constructor is the one that initializes an empty variant; it is enough to make variant a literal type, just not a particularly useful one. The active member is set by constructing it in-place in the raw storage, and it is accessed by casting its pointer to the target type:

// Constructs a T in the storage by means of placement new
new (&_storage.buffer) T(vs);

// Access the newly constructed T
T* member_ptr = static_cast<T*>(static_cast<void*>(&_storage.buffer));

Unfortunately, neither of these fundamental operations are allowed in a constant expression.

5.20 [expr.const]/2 A conditional-expression e is a core constant expression unless the evaluation of e, following the rules of the abstract machine (1.9), would evaluate one of the following expressions:

  • [...]
  • a conversion from type cv void * to a pointer-to-object type;
  • [...]
  • a new-expression;
  • [...]

In order to have any meaningful constexpr support, those operations have to be implemented in terms of operations which are allowed in constant expressions. In Part I, it was concluded that a generalized, type-safe, discriminated union necessarily takes a union as underlying storage if it is to provide as much of the functionality of a union as possible.

Implementation

Storage

The first step consists in using a union for underlying typed storage. A recursive approach is required, as expanding a template parameter pack is not allowed in a member declaration:

template <typename ...Ts>
union storage {};

template <typename T, typename ...Ts>
union storage<T, Ts...> {
  T head;
  storage<Ts...> tail;
};

...and that's when the problems begin. Each special member function of a union that is not user-provided —yes, unions can have functions— is implicitly defined as trivial if the corresponding member function is trivial for all of its members, otherwise is implicitly defined as deleted.

9.5 [class.union]/2 [Note: If any non-static data member of a union has a non-trivial default constructor (12.1), copy constructor (12.8), move constructor (12.8), copy assignment operator (12.8), move assignment operator (12.8), or destructor (12.4), the corresponding member function of the union must be user-provided or it will be implicitly deleted (8.4.3) for the union. —end note]

12.4 [class.dtor]/5 A defaulted destructor for a class X is defined as deleted if:

  • X is a union-like class that has a variant member with a non-trivial destructor,
  • [...]

A deleted destructor is particularly inconvenient, as it precludes common usage of a type. Objects of a type with a deleted destructor cannot have automatic, static nor thread_local storage. If used as a class member, then that class will have a deleted destructor as well, since the class destructor implicitly calls the destructors of all subobjects. What this means is that whenever the storage contains a member type with a non-trivial destructor, it is for all intents and purposes useless.

storage<int, float> s1{42}; // fine, initializes s1.head with 42
storage<int, std::string> s2{}; // error: use of deleted function 'storage::~storage()'
                                //        union member with non-trivial 'std::string::~string()'

It should be noted that s2 has a deleted default constructor too, since std::string::string() is not trivial, however no error is raised because of that. So far storage is an aggregate —implicitly deleted constructors are not user-provided—, and aggregate initialization involves no constructor calls.

8.5.1 [dcl.init.aggr]/1 An aggregate is an array or a class (Clause 9) with no user-provided constructors (12.1), no private or protected non-static data members (Clause 11), no base classes (Clause 10), and no virtual functions (10.3).

8.5.1 [dcl.init.aggr]/16 When a union is initialized with a brace-enclosed initializer, the braces shall only contain an initializer-clause for the first non-static data member of the union. [ Example:

union u { int a; const char* b; };
  u a = { 1 };
  u b = a;
  u c = 1; // error
  u d = { 0, "asdf" }; // error
  u e = { "asdf" }; // error

—end example ]

Trivially Destructible

In order for storage to be usable as intended it has to have a user-provided destructor. However, in order for it to be a literal type it has to have a trivial destructor, and user-provided special member functions are not trivial. What is needed is actually two different storage implementations, one with a trivial destructor for trivially destructible members, another one with a user-provided empty destructor for everything else:

template <bool TriviallyDestructible, typename ...Ts>
union union_ {};

template <typename T, typename ...Ts>
union union_<true, T, Ts...> {
  ~union_() = default; // trivial

  T head;
  union_<true, Ts...> tail;
};

template <typename T, typename ...Ts>
union union_<false, T, Ts...> {
  ~union_() {
     // user-provided, can't possibly know what to do
  }

  T head;
  union_<false, Ts...> tail;
};

This is conceptually wrong, but it is required to avoid the deleted destructor and be able to give others a chance to clean it up. The above definition of union_ is nothing so far but a long-winded way of spelling std::aligned_union. Someone else will be responsible for destroying the active member, someone that actually does know which member is the active one:

template <bool TriviallyDestructible, typename ...Ts>
struct storage;

template <typename ...Ts>
struct storage<true, Ts...> {
  ~storage() = default; // still trivial

  union_<true, Ts...> buffer;
  std::size_t which;
};

template <typename ...Ts>
struct storage<false, Ts...> {
  ~storage() {
    // dispatch to the appropriate destructor
  }

  union_<false, Ts...> buffer;
  std::size_t which;
};

With the union-based storage in place, it is possible to get back to the starting point:

struct empty {};

template <typename ...Ts>
class variant {
  static constexpr bool _trivially_destructible =
      _all_of<std::is_trivially_destructible<Ts>...>::value;

public:
  // `constexpr` constructor that is not a copy or move constructor
  constexpr variant() noexcept
    : _storage{}
  {}

  // trivial if all types in Ts are trivially destructible
  ~variant() = default;

  /*...*/

private:
  // literal type if all types in Ts are trivially destructible
  storage<_trivially_destructible, empty, Ts...> _storage;
};

A Note on Standard-Layout Unions

A special guarantee is made for standard-layout unions —those with standard-layout members—, it's possible to access a subobject of a non-active member when the active member shares all layout-compatible subobjects up to the one being accessed.

9.5 [class.union]/1 [..] [Note: One special guarantee is made in order to simplify the use of unions: If a standard-layout union contains several standard-layout structs that share a common initial sequence (9.2), and if an object of this standard-layout union type contains one of the standard-layout structs, it is permitted to inspect the common initial sequence of any of standard-layout struct members; see 9.2. —end note] [..]

9.2 [class.mem]/16 The common initial sequence of two standard-layout struct (Clause 9) types is the longest sequence of nonstatic data members and bit-fields in declaration order, starting with the first such entity in each of the structs, such that corresponding entities have layout-compatible types and either neither entity is a bit-field or both are bit-fields with the same width. [...]

9.2 [class.mem]/19 In a standard-layout union with an active member (9.5) of struct type T1, it is permitted to read a non-static data member m of another union member of struct type T2 provided m is part of the common initial sequence of T1 and T2. [...]

For these standard-layout unions, it is then possible to stash the discriminator in each member:

template <typename T>
struct indexed {
  std::size_t which;
  T member;
};

template <std::size_t I, typename ...Ts>
union storage {};

template <std::size_t I, typename T, typename ...Ts>
union storage<I, T, Ts...> {
  static_assert(std::is_standard_layout<T>::value, "");

  ~storage() {
    if (head.which == I) // fine, even if head is not active
      head.~indexed();
    else
      tail.~storage();
  }

  indexed<T> head;
  storage<I + 1, Ts...> tail;
};

Constructors

The next step is providing the storage with constructors capable of initializing any one of its members, and constexpr constructors at that:

template <std::size_t I> using index =
    std::integral_constant<std::size_t, I>;

template <typename T, typename ...Ts>
struct union_<true, T, Ts...> {
  template <typename ...Args>
  explicit constexpr union_(index<0>, Args&&... args)
    : head(std::forward<Args>(args)...) {}

  template <std::size_t I, typename ...Args>
  explicit constexpr union_(index<I>, Args&&... args)
    : tail(index<I-1>{}, std::forward<Args>(args)...) {}

  /*...*/
};

template <typename T, typename ...Ts>
struct union_<false, T, Ts...> {
  template <typename ...Args>
  explicit constexpr union_(index<0>, Args&&... args)
    : head(std::forward<Args>(args)...) {}

  template <std::size_t I, typename ...Args>
  explicit constexpr union_(index<I>, Args&&... args)
    : tail(index<I-1>{}, std::forward<Args>(args)...) {}

  /*...*/
};

The use of constexpr for the non-literal version is not a copy-paste induced artifact. Such constructors can be used in constant initialization of non-local variables.

3.6.2 [basic.start.init]/2 Variables with static storage duration (3.7.1) or thread storage duration (3.7.2) shall be zero-initialized (8.5) before any other initialization takes place. A constant initializer for an object o is an expression that is a constant expression, except that it may also invoke constexpr constructors for o and its subobjects even if those objects are of non-literal class types [Note: such a class may have a non-trivial destructor —end note]. Constant initialization is performed:

  • [...]
  • if an object with static or thread storage duration is initialized by a constructor call, and if the initialization full-expression is a constant initializer for the object;
  • [...]

Together, zero-initialization and constant initialization are called static initialization; all other initialization is dynamic initialization.

template <typename ...Ts>
struct storage<true, Ts...> {
  /*...*/

  constexpr storage() noexcept
    : buffer(index<0>{})
    , which(0)
  {}

  template <std::size_t I, typename ...Args>
  explicit constexpr storage(index<I> i, Args&&... args)
    : buffer(i, std::forward<Args>(args)...) {}
    , which(i)
  {}

  /*...*/
};

template <typename ...Ts>
struct storage<false, Ts...> {
  // ditto
};

With this it is now possible to implement constexpr conversion and emplacement constructors, where the type of the source —and hence that of the target— is statically known:

template <typename ...Ts>
class variant {
  template <typename T> using _index_of = index<I>; // 1-based index of T in Ts...

  /*...*/

  template <typename T>
  constexpr variant(T const& v)
    : _storage{_index_of<T>{}, v}
  {}

  /*...*/
};

Trivially Copyable

Copy and move constructors, on the other hand, don't know the type of the source member at compile time. However, when all members of a union are trivially copy/move-constructible the union itself is trivially copy/move-constructible, and such constructors are constexpr. A similar logic applies to copy/move-assignment operators.

12.8 [class.copy]/13 A copy/move constructor that is defaulted and not defined as deleted is implicitly defined [...]. If the implicitly-defined constructor would satisfy the requirements of a constexpr constructor (7.1.5), the implicitly-defined constructor is constexpr.

12.8 [class.copy]/16 The implicitly-defined copy/move constructor for a union X copies the object representation (3.9) of X.

12.8 [class.copy]/26 A copy/move assignment operator for a class X that is defaulted and not defined as deleted is implicitly defined [...]. The implicitly-defined copy/move assignment operator is constexpr if

  • X is a literal type, and
  • the assignment operator selected to copy/move each direct base class subobject is a constexpr function, and
  • for each non-static data member of X that is of class type (or array thereof), the assignment operator selected to copy/move that member is a constexpr function.

12.8 [class.copy]/29 The implicitly-defined copy assignment operator for a union X copies the object representation (3.9) of X.

It follows that a storage of trivially copyable types will be trivially copyable in a constexpr way. The previous implementation has a trivially copyable specialization for trivially copyable members, which the current implementation retains and augments. This specialization will have constexpr copy/move constructors and assignment operators. Furthermore, such specialization can implement emplace as an assignment from a temporary, which is again a constexpr operation:

// Courtesy of Richard Smith
union U {
  int n;
  float f;
  constexpr U(int n) : n(n) {}
  constexpr U(float f) : f(f) {}
};

constexpr int f(bool b) {
  U u(3.0f);
  if (b) u = U(4); // emplacement, sort of...
  return b ? u.n : u.f;
}
static_assert(f(false) == 3);
static_assert(f(true) == 4);

Finally, this specialization's previous implementation used to violate type-safety with trivially copyable but not copyable classes —such apparent oxymoron does in fact exist—:

class noncopyable {
protected:
  constexpr noncopyable() = default;
  noncopyable(noncopyable const&) = delete;
  noncopyable& operator=(noncopyable const&) = delete;
  ~noncopyable() = default;
};

static_assert(std::is_trivially_copyable<noncopyable>::value); // really
variant<noncopyable> v1(noncopyable{}), v2(v1); // fine, no error

With the union based implementation, such operations will be implicitly defined as deleted instead.

12.8 [class.copy]/11 An implicitly-declared copy/move constructor is an inline public member of its class. A defaulted copy/move constructor for a class X is defined as deleted (8.4.3) if X has:

  • [...]
  • a potentially constructed subobject type M (or array thereof) that cannot be copied/moved because overload resolution (13.3), as applied to M’s corresponding constructor, results in an ambiguity or a function that is deleted or inaccessible from the defaulted constructor,
  • [...]
variant<noncopyable> v1(noncopyable{}), v2(v1); // error: use of deleted function

Element Access

The last step is implementing member access without resorting to pointer casts:

template <typename T, typename ...Ts>
struct union_<true, T, Ts...> {
  /*...*/

  constexpr T& get(index<0>) noexcept { return head; }
  constexpr T const& get(index<0>) const noexcept { return head; }

  template <std::size_t I>
  constexpr typename at<I-1, Ts...>::type&
  get(index<I>) noexcept { return tail.get(index<I-1>{}); }

  template <std::size_t I>
  constexpr typename at<I-1, Ts...>::type const&
  get(index<I>) const noexcept { return tail.get(index<I-1>{}); }

  /*...*/
};

template <typename T, typename ...Ts>
struct union_<false, T, Ts...> {
  // ditto
};

template <typename ...Ts>
struct storage<true, Ts...> {
  /*...*/

  template <std::size_t I>
  constexpr typename at<I, Ts...>::type&
  get(index<I> i) noexcept { return buffer.get(i); }

  template <std::size_t I>
  constexpr typename at<I, Ts...>::type const&
  get(index<I> i) const noexcept { return buffer.get(i); }

  /*...*/
};

template <typename ...Ts>
struct storage<false, Ts...> {
  // ditto
};

Some recursion boilerplate later, the last fundamental operation can be made constexpr:

template <typename ...Ts>
class variant {
  /*...*/

  template <typename T>
  constexpr T* target() noexcept {
    return _storage.which == _index_of<T>::value ?
      &_storage.get(_index_of<T>{}) : nullptr;
  }

  template <typename T>
  constexpr T const* target() const noexcept {
    return _storage.which == _index_of<T>::value ?
      &_storage.get(_index_of<T>{}) : nullptr;
  }

  /*...*/
};

The remaining operations build on top of the previous ones; some may need minor twists and tweaks to adapt to the constexpr idiosyncrasy, but otherwise the job is done. A variant<Ts> is a literal type when all types in Ts are literal types, and is as constexpr as std::experimental::optional<T> —more, actually—, on which the design is loosely based.


References:

Constexpr unions - Andrzej Krzemienski