18 Aug, 2014

Eggs.Variant - Part I

Ruminations on the development of Eggs.Variant, a C++11/14 generic, type-safe, discriminated union.

Introduction

A union is a special class type that can hold only one of its non-static data members at a time. It's just big enough to accommodate the largest of its members.

9 [class]/5 A union is a class defined with the class-key union; it holds at most one data member at a time (9.5). [...]

9.5 [class.union]/1 In a union, at most one of the non-static data members can be active at any time, that is, the value of at most one of the non-static data members can be stored in a union at any time. [...] The size of a union is sufficient to contain the largest of its non-static data members. Each non-static data member is allocated as if it were the sole member of a struct. All non-static data members of a union object have the same address.

In C++98, members of a union where restricted to trivial object types. For these types, lifetime begins when appropriate storage is obtained, and ends when the storage is reused or released.

3.8 [basic.life]/1 [...] The lifetime of an object of type T begins when:

  • storage with the proper alignment and size for type T is obtained, and
  • if the object has non-trivial initialization, its initialization is complete.

The lifetime of an object of type T ends when:

  • if T is a class type with a non-trivial destructor (12.4), the destructor call starts, or
  • the storage which the object occupies is reused or released.

This special guarantee allows the active member of a union to be changed by simply assigning to it, effectively reusing the storage —that's at least the spirit, if not the letter, of the standard—.

Furthermore, a union does not know which member —if any— is active, so its special member functions have to be implemented without that information. Since members are restricted to trivial types, the special member functions can be implemented in terms of the underlying bytes, independently of the active member.

9.5 [class.union]/1 [...] An object of a class with a non-trivial constructor (12.1), a non-trivial copy constructor (12.8), a non-trivial destructor (12.4), or a non-trivial copy assignment operator (13.5.3, 12.8) cannot be a member of a union, nor can an array of such objects. [...]

In C++11, this restriction was lifted; members of a union can now be of any object type. Switching between non-trivial members requires explicitly destroying the currently active member, and using placement new to construct the newly active member.

9.5 [class.union]/4 [Note: In general, one must use explicit destructor calls and placement new operators to change the active member of a union. —end note] [Example: Consider an object u of a union type U having non-static data members m of type M and n of type N. If M has a non-trivial destructor and N has a non-trivial constructor (for instance, if they declare or inherit virtual functions), the active member of u can be safely switched from m to n using the destructor and placement new operator as follows:

u.m.~M();
  new (&u.n) N;

—end example]

If a special member function is non-trivial for any of the members, then the union special member function will be implicitly defined as deleted when not user-provided.

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]

9.5 [class.union]/3 [Example: Consider the following union:

union U {
    int i;
    float f;
    std::string s;
  };

Since std::string (21.3) declares non-trivial versions of all of the special member functions, U will have an implicitly deleted default constructor, copy/move constructor, copy/move assignment operator, and destructor. To use U, some or all of these member functions must be user-provided. -end example]

These non-trivial member functions can only be provided —with their usual semantics— by knowing if a member is active, and then forwarding to it. A discriminated union is a union or union-like class that is self-aware, that is, it contains some form of identifier that lets it know which member —if any— is active. A discriminated union can provide all special member functions, trivial or not.

An instance of eggs::variant<Ts...> is a discriminated union with members of object types Ts. It offers a natural interface for switching the active member, and it provides all special member functions with the usual semantics:

eggs::variants<N, M> u; // u has no active members
u = M{}; // u has an active member of type M
u = N{}; // u has an active member of type N, the previous active member was destroyed

// all special member functions are provided
using U = eggs::variants<int, float, std::string>;

Design

The ultimate design goal is to generalize and enhance the discriminated union construct, without compromising its functionality. That is, there should be little or no room for choosing:

struct U {
  union { T0 m0; ...; TN mN; };
  std::size_t which;
} u;

over:

using V = eggs::variant<T0, ..., TN>;
V v;

In particular:

  • The size of V shall match that of the corresponding U. Any active member of v shall be allocated in a region of V suitably aligned for the types T0, ... TN; the use of additional storage, such as dynamic memory, is not permitted.

  • Well defined semantics of u shall be matched or improved by v. Undefined behavior, such as referring to a non-active member of u, shall not be allowed by the interface of v.

  • All special member functions shall be provided by V with the expected semantics.

The interface is largely based on that of std::experimental::optional<T>, as defined by the Library Fundamentals TS. The conceptual model for optional<T> is that of a discriminated union of types nullopt_t and T. The design decisions taken for optional<T> easily translate to variant<Ts...>, whose conceptual model is that of a discriminated union of types nullvariant_t and those in Ts. The semantics of all special member functions and relational operators, as well as the interface for switching the active member —via construction, assignment, or emplacement—, derives from optional<T>.

Access to the active member is based on the design of std::function, which gives back a pointer to the target if queried with the correct target type —as a poor man's dynamic_cast—. Additionally, it is also possible to obtain a void pointer to the active member (if any), which proved useful to simplify the implementation of helper functions.

Finally, helper classes similar to those of std::tuple are provided, as well as index or type based element access —albeit with surprising semantics, closer to those of a runtime-checked cast—.

The reference documentation can be found here.

Implementation

A direct implementation of variant<Ts> would use an underlying relaxed union as storage:

template <typename ...Ts>
union storage {
  nullvariant_t nullvariant;
  Ts... members;
};

However, that's not well formed C++, as parameter packs cannot be expanded in that context —what would the names of the members be, and how would they be referred to—. Instead, a recursive approach is necessary to build the underlying storage:

template <typename ...Ts>
union storage;

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

template <>
union storage<> {
  nullvariant_t nullvariant;
};

Unfortunately, it is not that simple either, given that any non-trivial special member function for a type in Ts will result in the corresponding special member function being deleted for storage. In order to use it, at the very list the default constructor and the destructor would have to be provided, even though a destructor would be unable to do anything useful.

A simpler implementation, one that was used before C++ got relaxed unions, would be to use raw storage suitable for holding any of the types in Tsspoiler alert: this will prove to fall short on some fronts—. The standard even provides a trait to ease the work:

20.10.7.6 [meta.trans.other]

template <std::size_t Len, class... Types>
  struct aligned_union;
  • Condition: At least one type is provided.

  • Comments: The member typedef type shall be a POD type suitable for use as uninitialized storage for any object whose type is listed in Types; its size shall be at least Len. The static member alignment_value shall be an integral constant of type std::size_t whose value is the strictest alignment of all types listed in Types.

It should be noted that this trait was already removed once from the working draft —with the arrival of relaxed unions—, and is now a potential candidate for deprecation. A possible C++14 replacement would be:

template <std::size_t Len, typename ...Types>
struct aligned_union {
  static constexpr std::size_t alignment_value = std::max({alignof(Types)...});
  struct type {
    alignas(alignment_value) unsigned char _[std::max({Len, sizeof(Types)...})];
  };
};

With the help from aligned_union to use as the storage type, a simplified version of variant<Ts> can be implemented as follows:

template <typename ...Ts>
class variant {
  template <typename T> struct _index_of { /*...*/ }; // 0-based index of T in Ts...

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

  variant() noexcept
    : _which{npos}
  {}

  template <typename T>
  variant(T const& v)
    : _which{_index_of<T>::value}
  {
    new (target<T>()) T(v); // Constructs a T in the storage by means of placement new
  }

  /*...*/

  std::size_t which() const noexcept {
    return _which;
  }

  template <typename T>
  T* target() noexcept {
    return _which == _index_of<T>::value ?
      static_cast<T*>(static_cast<void*>(&_storage)) : nullptr;
  }

  template <typename T>
  T const* target() const noexcept {
    return _which == _index_of<T>::value ?
      static_cast<T const*>(static_cast<void const*>(&_storage)) : nullptr;
  }

private:
  std::size_t _which;
  typename std::aligned_union<0, Ts...>::type _storage;
};

The special member functions have to dispatch to the active member (if any). Once again, we cannot simply use switch to accomplish this —albeit if we could it would hardly be simple—, and the immediate replacement would be a recursive implementation:

struct _destructor {
  template <typename T>
  static void call(void* ptr) {
    static_cast<T*>(ptr)->~T();
  }
};

variant<Ts...>::~variant() {
  apply<_destructor, Ts...>(_which, &_storage);
}

template <typename F>
void apply(std::size_t /*which*/, void* /*storage*/) {}

template <typename F, typename T, typename ...Ts>
void apply(std::size_t which, void* storage) {
  if (which == 0) { F::template call<T>(storage); }
  else { apply<F, Ts...>(which - 1, storage); }
}

A flat implementation of apply can be achieved by generating a jump table, similar to what a switch would do, and then jumping to the appropriate entry:

template <typename F, typename ...Ts>
void apply(std::size_t which, void* storage) {
  using fun_ptr = void(*)(void*);
  static constexpr fun_ptr table[] = {&F::template call<Ts>...};

  if (which < sizeof...(Ts)) { table[which](storage); }
}

The flat implementation not only results in faster generated code, but also in faster compilation times for large number of types in Ts —your mileage may vary—.

Trivially Copyable

A trivially copyable type is a type that can be copied by copying its underlying bits —i.e. by means of std::memcpy—.

3.9 [basic.types]/2 For any object (other than a base-class subobject) of trivially copyable type T, whether or not the object holds a valid value of type T, the underlying bytes (1.7) making up the object can be copied into an array of char or unsigned char. If the content of the array of char or unsigned char is copied back into the object, the object shall subsequently hold its original value. [...]

3.9 [basic.types]/3 For any trivially copyable type T, if two pointers to T point to distinct T objects obj1 and obj2, where neither obj1 nor obj2 is a base-class subobject, if the underlying bytes (1.7) making up obj1 are copied into obj2, obj2 shall subsequently hold the same value as obj1. [...]

A union of trivially copyable members is itself trivially copyable, which makes it candidate for more optimizations than a non-trivially copyable type would be. It follows that a variant of trivially copyable types should strive to be trivially copyable too.

9 [class]/6 A trivially copyable class is a class that:

  • has no non-trivial copy constructors (12.8),
  • has no non-trivial move constructors (12.8),
  • has no non-trivial copy assignment operators (13.5.3, 12.8),
  • has no non-trivial move assignment operators (13.5.3, 12.8), and
  • has a trivial destructor (12.4).

    [...]

In order to achieve this, a separate specialization of variant has to be selected when all types in Ts are trivially copyable. The special member functions enumerated above shall not be user provided for that specialization —they should either be implicitly provided or explicitly defaulted on its first declaration—. The implementation will provide implicit definitions for them which will be trivial; copy and move operations will simply copy the underlying bits of the storage as well as the discriminator, the destructor will do nothing.

But there is a catch: a trivially copyable class may not be copyable at all, given that a special member function deleted on its first declaration is trivial. Take, for instance, boost::noncopyable defined as follows:

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

It may come as a surprise that std::is_trivially_copyable yields true for noncopyable. It may be even more surprising that an instance of variant<noncopyable> can be happily copied, since the deleted member functions of noncopyable are not even being used. This is, in fact, a violation of type safety, stemmed from the decision to use untyped raw storage to hold the active member.

Trivially Destructible

Another important category of types is those that are trivially destructible.

12.4 [class.dtor]/5 [...] A destructor is trivial if it is not user-provided and if:

  • the destructor is not virtual,
  • all of the direct base classes of its class have trivial destructors, and
  • for all of the non-static data members of its class that are of class type (or array thereof), each such class has a trivial destructor.

Otherwise, the destructor is non-trivial.

This is particularly important because one of the requirements for a literal type —those whose instances can be used in a constexpr context— is that of being trivially destructible.

3.9 [basic.types]/10 A type is a literal type if it is:

  • [...]
  • a class type (Clause 9) that has all of the following properties:
    • 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.

A union could be a literal type, providing that at least one of its members is a literal type and the rest of them are trivially destructible. It follows that a variant should strive to be a literal type under those conditions too. Yet another specialization of variant has to be selected when all types in Ts are trivially destructible. It is of little benefit however, since amongst the restrictions on constant expressions is that of casting a void pointer to a pointer-to-object:

5.19 [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;
  • [...]

Once again, the decision to use untyped raw storage is a limitation to fully implement a generic discriminated union on par with what a manually implemented one could achieve.

What Lies Ahead

An implementation based in raw storage —while giving a great bang for the buck— does not hold when pushed to the limit. 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.