18 Oct, 2015

Rant: On the std::experimental::variant to come

Variant has been a hot topic in the C++ lands ever since one has been proposed for inclusion into the standard library. It's a controversial topic, the term is loaded. Variant means different things to different target audiences, ranging all the way from a very low level problematic smart union to a very high level problematic type theory concept. Reaching a compromise that services both ends well is bound to be challenging...

The Problem

One thing is clear, a plain union won't cut it. With no knowledge of which member is active, it is devoid of any semantic meaning. Even while C++11 relaxed unions to take non-trivial object types as members, they are still nothing but typed raw storage —oxymoronic as that might sound—, unable to provide even the most fundamental functionality —a destructor—:

union U1 {
  int i;
  std::string s;

  U1(int v) : i(v) {}
  U1(std::string const& v) : s(v) {}
} u1("hello"); // error: not destructible, ~U1 is implicitly deleted

union U2 {
  int i;
  std::string s;

  U2(int v) : i(v) {}
  U2(std::string const& v) : s(v) {}
  ~U2() { /* what now? */ }
} u2("world"); // ok: ~U2 happily leaks std::string

That's just scratching the surface, destructibility is required for objects with automatic storage duration, as well as to not leak objects with dynamic storage duration. The plot thickens when copy and move operations are added to the picture, and it spirals out of control when considering perfect forwarding, constexpr, noexcept, and all the things we are used to love.

Standard Layout Unions and the Common Initial Sequence of Standard Layout Structs

Those that really want to provide a meaningful destructor can take advantage of the common initial sequence special rule for unions:

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. [...]

union U3 {
  struct M0 {
    std::size_t which;
    int i;

    M0(int v) : which(0), i(v) {}
    ~M0() = default;
  } m0;

  struct M1 {
    std::size_t which;
    // std::string is not guaranted to be standard-layout
    std::aligned_storage_t<sizeof(std::string), alignof(std::string)> s;

    M1(std::string const& v) : which(1) {
      ::new (static_cast<void*>(&s)) std::string(v);
    }
    ~M1() {
      auto s_ptr = static_cast<std::string*>(static_cast<void*>(&s));
      s_ptr->~basic_string(); // it is not called "string"
    }
  } m1;

  U3(int v) : m0(v) {}
  U3(std::string const& v) : m1(v) {}
  ~U3() {
    switch (m0.which) { // inspect common-initial-sequence
      case 0: m0.~M0(); break;
      case 1: m1.~M1(); break;
    }
  }
};
static_assert(std::is_standard_layout<U3>::value, "it better be");

With the only purpose of simplifying usage of unions, the common initial sequence guarantee does not look all that compelling when compared to a —pure— raw storage approach:

struct U4 {
  std::size_t which;
  std::aligned_union_t<0, int, std::string> storage;

  U4(int v) : which(0) {
    ::new (static_cast<void*>(&storage)) int(v);
  }
  U4(std::string const& v) : which(1) {
    ::new (static_cast<void*>(&storage)) std::string(v);
  }
  ~U4() {
    switch (which) {
      case 0: break; // int is trivially destructible
      case 1: {
        auto s_ptr = static_cast<std::string*>(static_cast<void*>(&storage));
        s_ptr->~basic_string(); // it is not called "string"
        break;
      }
    }
  }
};

It looks as if C++ never happened for union...

Shades of Variant

The terms discriminated union and sum type are arbitrarily chosen to respectively represent the lowest level and highest level shades of variant.

Discriminated Union

A discriminated union is the minimal incremental step beyond a plain union, it bundles the union together with the active member discriminator necessary for any meaningful use. Just like a union, it has a (possibly empty) sequence of members of object type; unlike a union, it has an intrinsic discriminator that keeps track of which member is active (if any). As such, it can implicitly provide definitions for special member functions while retaining the benefits of a union, as well as most of its downsides.

This is what Eggs.Variant models, which predates the standard proposal and all its debate, or else it would have been called Eggs.DiscriminatedUnion.

The main motivation for delving into a union is to reduce storage for objects with non-overlapping lifetimes:

9.5 [class.union]/1 [...] 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.

At most one member can be stored in a union —discriminated or plain— at any time. In a non-trivial world, switching the active member consist of explicitly destroying the currently active member (if any), 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]

In-between these operations the union is an empty state, and were the construction of the new member to fail —exit via an exception— the union would be left with no active member. This is not problematic for a union, which models at most one; even a trivial union would be empty when default-initialized. This is but a consequence of fiddling with storage at such low level.

A discriminated union needs just enough extra space to store the discriminator. Here the common initial sequence guarantee proves actually useful, as it allows for a more space-efficient storage —if only it were constexpr friendly as P0120R0 proposes—.

A note on a core language discriminated union

While a library solution would likely use indices to represent members, a core language solution could use names instead like unions do. It could further provide full constexpr semantics where a library solution simply can't, and at a much lesser cost:

discriminated-union U5 {
  int i;
  std::string s;
}; // there, done, packed with all the goodies

Unfortunately, a core language solution would not be helpful when implementing variant. Whatever that chooses to model, it will be variadic, and —in lack of syntax to expand template parameter packs in member declarations— it will have to resort to a recursive definition:

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

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

Each storage node along the chain would store it's own discriminator, they have to as each is its own separate type and can be operated on independently of the rest.

Sum Type

On the other end of the specter sits the sum type, dual of type theory's product type, which holds a value from any one of its set of member types. It would be naturally implementable on top of a discriminated union, which should be unsurprising given that it is designed specifically to address this need.

Type theory has it easy however, it does not have to concern itself with the sort of beasts that lurk the C++ lands (copies, memory allocation, exceptions, etc). A sum type cannot be empty, it models exactly one of, which is a situation that can arise in C++ when using overlapped storage. A discriminated union may not be such a sure choice after all, some sort of double storage might be needed so that the lifetime of the active member can be extended just up to the point the newly active member's lifetime has started.

The never-empty guarantee is deemed so important that Boost.Variant is willing to resort to dynamic memory allocation in order to provide it —and dedicates the entirety of its design overview section to it—. It implements the "temporary heap backup" technique:

  • Copy-construct the content of the left-hand side to the heap; call the pointer to this data backup.
  • Destroy the content of the left-hand side.
  • Copy-construct the content of the right-hand side in the (now-empty) storage of the left-hand side.
  • In the event of failure, copy backup to the left-hand side storage.
  • In the event of success, deallocate the data pointed to by backup.

Under the hood, it is implemented using a sort of discriminated_union<Ts..., value_ptr<Ts>...>. However, it provides an opt-out for when dynamic memory allocation is deemed unacceptable:

If any bounded type is nothrow default-constructible (as indicated by boost::has_nothrow_constructor), the library guarantees variant will use only single storage and in-place construction for every bounded type in the variant. Note, however, that in the event of assignment failure, an unspecified nothrow default-constructible bounded type will be default-constructed in the left-hand side operand so as to preserve the never-empty guarantee.

That is, it is willing to sacrifice the strong exception guarantee but not the never-empty guarantee, without incurring dynamic memory allocation. If further provides a boost::blank type that meets these conditions, so that when it is added as a first member of a boost::variant it effectively introduces an empty state.

The compromise reached by the Lenexa few —resulting in N4542— bans dynamic memory allocation as well as any other form of double storage, forcing the possibility of an empty variant into existence. However, instead of making this state a visible "empty state", it makes it an "invalid state" instead: a transient valid state in which the invariants of the class do not hold. This too turned out to be controversial, resulting in a fork into P0087: a type-safe union without undefined behavior, and P0088: a type-safe union that is rarely invalid.

Yet another proposal, P0110 —which continuing the trend would be "a type-safe union that rarely needs double buffering"—, investigates the possible ways of implementing the strong exception guarantee for assignment, while reducing the use of double (embedded) buffering to a bare minimum. It should be noted that this is from the point of view of a variant only, when the active members on both sides of the assignment have the same type regular assignment is done, and thus the exception safety is determined by the operands.

But there's more down this line, P0080: Discriminated Union with Value Semantics, P0093: Simply a Strong Variant, P0094: Simply a Basic Variant, P0095: The Case for a Language Based Variant, as well as a few other satellite papers. The dust, it appears, is far from settling...

A note on type ordering

Given that the order in which the elements are listed in a set is irrelevant, it would be desirable from a purity point of view for sum-type(int, std::string) and sum-type(std::string, int) to be interchangeable. Unfortunately there is no compile-time relation that would allow the construction of an ordered set of types —there is only a run-time one—.

template <typename>
class basic_variant;

template <typename ...Ts>
class basic_variant<meta::set<Ts...>> { /*...*/ };

template <typename ...Ts>
using variant = basic_variant<meta::order<meta::set<Ts...>>>;

static_assert(std::is_same<
      variant<int, std::string>, 
      variant<std::string, int>
    >::value, "if only!");

This is not a showstopper —types with different names should not be expected to be the same—, but might nevertheless be worth considering compile-time type ordering in the future.

Rounding up

The committee faces a challenging decision: a safe vocabulary type to phase out unnecessary low level usage of unions is sorely needed, and the obvious model for such a high level feature would be exactly one of, which does not exactly come for free. Efficiency is paramount in these lands —we care—; could a high level type sum be performant enough to satisfy the low level discriminated union use cases? Or will entangling these two ends of the spectrum turn out to be a disservice to both camps?

What std::experimental::variant will be remains to be seen...