# 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]/2Aconditional-expression`e`

is acore constant expressionunless 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]/5A 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]/1Anaggregateis 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]/16When a union is initialized with a brace-enclosed initializer, the braces shall only contain aninitializer-clausefor 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* `union`

s —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]/16Thecommon initial sequenceof 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]/19In 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]/2Variables 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 initializationis 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 isdynamic 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]/13A copy/move constructor that is defaulted and not defined as deleted isimplicitly 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]/16The implicitly-defined copy/move constructor for a union`X`

copies the object representation (3.9) of`X`

.

12.8 [class.copy]/26A copy/move assignment operator for a class`X`

that is defaulted and not defined as deleted isimplicitly 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]/29The 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]/11An 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: