C++
Designing and refactoring
November 2014 30

Eggs.Variant — Часть I

Original author: K-ballo
Translation
На публикацию этого перевода меня сподвиг комментарий пользователя @encyclopedist к недавней статье «Фабричный метод без размещения в динамической памяти». Статья меня заинтересовала, но беглое гугление не выявило перевода. «Непорядок.» — подумал я — «Такая интересная статья по С++ и не переведена на русский язык. Надо бы исправить.»

Оглавление
  1. Введение
  2. Проектирование
  3. Реализация

  4. О чём ещё не сказано


Размышления о разработке Eggs.Variant — обобщённом типобезопасном размеченном объединении на C++11/14.

Введение


Объединение — это специальный тип класса, который в один момент времени может хранить только один из своих нестатических членов. Он занимает столько места, сколько требуется для размещения наибольшего из его членов.
9 [class]/5 Объединение — это класс, определяемый с ключевым словом union; одновременно он может хранить только один из своих членов (9.5). [...]
9.5 [class.union]/1 В объединении активным может быть только один из нестатических членов, то есть, в данный момент времени в объединении может храниться значение только одного из его нестатических членов. [...] Размер объединения достаточен для вмещения самого большого из его нестатических членов. Каждый нестатический член размещается в памяти так, словно он является единственным членом структуры. Все нестатические члены объекта объединения имеют одинаковый адрес.

Оригинал
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.





В C++98 члены объединения ограничены тривиальными типами объектов. Для таких типов время их жизни начинается при получении хранилища и заканчивается при его переиспользовании или освобождении.
3.8 [basic.life]/1 [...] Время жизни объекта типа T начинается, когда:
  • получено хранилище с подходящим к типу T выравниванием и размером и
  • инициализация объекта, если она нетривиальна, завершена.

Время жизни объекта типа T заканчивается, когда:
  • в том случае, если T является типом класса с нетривиальным деструктором (12.4), начинается вызов деструктора, или
  • хранилище, которое занимает объект, было переиспользовано или освобождено.


Оригинал
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.



Эта специальная гарантия позволяет менять активный член объединения просто присваивая объединению новое значение, позволяя эффективно переиспользовать хранилище — что хорошо согласуется если не с буквой, то с духом стандарта.
Кроме того, объединение не знает, какой его член — если он есть — активен, так что его специальные функции-члены должны реализовываться без знания этой информации. Поскольку члены объединения ограничены тривиальными типами, специальные функции-члены могут быть реализованы в терминах лежащих в основе объединения байтов, не зависящих от активного члена.
9.5 [class.union]/1 [...] Объект класса с нетривиальным конструктором (12.1), нетривиальным конструктором копирования (12.8), нетривиальным деструктором (12.4) или нетривиальным копирующим оператором присваивания (13.5.3, 12.8) не может быть членом объединения, либо элементом массива, лежащем в объединении. [...]

Оригинал
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. [...]


В C++11 это ограничение было отменено; члены объединения теперь могут быть любого типа. Переключение между нетривиальными членами требует явного разрушения текущего активного члена и использования размещающего оператора new для конструирования нового активного члена.
9.5 [class.union]/4 [Примечание: в общем случае необходимо использовать один явный вызов деструктора и один явный вызов размещающего оператора new для изменения активного члена перечисления. —конец примечания] [Пример: Рассмотрим объект u, имеющий тип перечисления U с нестатическими членами m типа M и n типа N. Если M имеет нетривиальный деструктор, а N имеет нетривиальный конструктор (к примеру, если в них объявлены или они наследуют виртуальные функции), активный член u может быть безопасно изменён с m на n при помощи следующего использования деструктора и размещающего оператора new:
u.m.~M();
new (&u.n) N;

—конец примера]

Оригинал
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]


Если специальная функция-член любого из членов объединения является нетривиальной, то специальная функция-член самого объединения будет неявно определяться как удалённая, если только её не предоставил сам пользователь.
9.5 [class.union]/2 [Примечание: если любой нестатический член объединения имеет нетривиальный конструктор по умолчанию (12.1), конструктор копирования (12.8), конструктор перемещения (12.8), копирующий оператор присванивания (12.8), перемещающий оператор присваивания (12.8) или деструктор (12.4), соответствующая функция-член объединения должна быть предоставлена пользователем, или она будет неявно удалена (8.4.3) из объединения. —конец примечания]
9.5 [class.union]/3 [Пример: рассмотрим следующее объединение:
union U {
  int i;
  float f;
  std::string s;
};

Поскольку тип std::string (21.3) объявляет нетривиальные версии всех специальных функций-членов, у типа U будут неявно удалены конструктор по умолчанию, конструкторы копирования/перемещения, копирующий/перемещающий операторы присваивания и деструктор. Для использования типа U некоторые из этих функций-членов должны быть предоставлены пользователем. —конец примера]

Оригинал
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]


Эти нетривиальные функции-члены могут быть предоставлены — с соблюдением их обычной семантики — только если будет известен активный член перечисления, чтобы его можно было передать дальше. Размеченное объединение — это объединение или класс, подобный объединению, которое обладает знанием о себе, то есть, оно содержит некоторый идентификатор, который позволяет узнать, какой член — если он есть — сейчас активен. Размеченное объединение может предоставлять все специальные функции-члены независимо от их тривиальности.
Экземпляр класса eggs::variant<Ts...> является размеченным объединением объектов с типами Ts. Он обеспечивает естественный интерфейс для переключения активного члена и предоставляет все специальные функции-члены с их обычной семантикой:
eggs::variants<N, M> u; // u не имеет активного члена
u = M{}; // теперь активный член u имеет тип M
u = N{}; // теперь активный член u имеет тип N, предыдущий активный член был разрушен

// предоставляются все специальные функции-члены
using U = eggs::variants<int, float, std::string>;


Проектирование


Конечной целью проектирования является обобщение и улучшение конструкции размеченного объединения без ущерба для его функциональности. То есть, у него не должно быть специального члена для выбора текущего активного члена объединения, либо он должен занимать совсем немного места:
struct U {
  union { T0 m0; ...; TN mN; };
  std::size_t which;
} u;

заменяется этим:
using V = eggs::variant<T0, ..., TN>;
V v;

В частности:
  • Размер типа V должен совпадать с размером соответствующего типа U. Любой активный член v должен размещаться в области V, соответствующим образом выровненной для типов T0, ... TN; использование дополнительного хранилища, например, динамической памяти, не допускается.
  • Семантика v должна соответствовать или улучшать чётко определённую семантику u. Интерфейсом v не должно позволяться неопределённое поведение, например, ссылка на неактивный член u.
  • Типом V должны предоставляться все специальные функции-члены с их ожидаемой семантикой.

В основном интерфейс основывается на std::experimental::optional<T>, как он определён в Технической спецификации основной библиотеки. Концептуальная модель optional<T> состоит из размеченного объединения типов nullopt_t и T. Проектные решения, принятые для optional<T>, легко перенести на variant<Ts...>, чья концептуальная модель состоит из размеченного объединения типов nullvariant_t и тех, что скрыты за Ts. Семантика всех специальных функций-членов и связанных операторов, а также интерфейс для переключения активного члена — через конструирование, присваивание или размещение — заимствуется от optional<T>.
Доступ к активному члену выполняется в стиле std::function, которая возвращает указатель на цель, если она запрашивается с корректным типом цели — что-то вроде dynamic_cast для бедных. Кроме того, он также позволяет получить пустой указатель на активный член (если он есть), что оказалось очень полезным для упрощения реализации вспомогательных функций.
Наконец, предоставляются вспомогательные классы, подобные std::tuple, а также доступ к элементам по индексу или по типу — хотя и с неочевидной семантикой, более близкой к семантике приведения типов во время выполнения.
Справочная документация может быть найдена здесь.

Реализация


Прямая реализация variant<Ts> в качестве хранилища использовала бы нижележащее расслабленное объединение:
template <typename ...Ts>
union storage {
  nullvariant_t nullvariant;
  Ts... members;
};

Однако, вышеприведённый код не является правильным с точки зрения синтаксиса C++, поскольку набор параметров шаблона не может быть раскрыт в этом контексте — он должен содержать имена членов, чтобы на них можно было ссылаться. Вместо этого для построения нижележащего хранилища следует применить рекурсивный подход:
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;
};

К сожалению, это не так просто, учитывая то, что любая нетривиальная специальная функция-член для типа из Ts в результате удалит соответствующую специальную функцию-член из хранилища. Чтобы эту реализацию можно было использовать, для получившегося списка должны быть реализованы как минимум конструктор по умолчанию и деструктор, хотя деструктор и не сможет сделать ничего полезного.
Простейшая реализация, которая использовалась до того, как в C++ появились расслабленные объединения, использовала бы голое хранилище, пригодное для хранения любого из типов в Ts — внимание, спойлер: в некоторых случаях оно не подойдёт. Стандарт даже предоставляет специальное свойство для облегчения нашей работы:
20.10.7.6 [meta.trans.other]
template <std::size_t Len, class... Types>
  struct aligned_union;

  • Условие: Должен быть предоставлен как минимум один тип.
  • Комментарии: typedef на тип члена должен быть POD-типом, применимым для использования в качестве неинициализированного хранилища для любого объекта, чей тип перечислен в списке Types; его размер должен быть не менее Len. Статический член alignment_value должен быть целочисленной константой типа std::size_t, чьё значение определяет строжайшее выравнивание для всех типов, перечисленных в списке Types.


Оригинал
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.



Следует заметить, что это свойство уже удалено из рабочего черновика — вместе с приходом расслабленных объединений — и сейчас является потенциальным кандидатом на устаревание. Возможной заменой в C++14 может быть:
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)...})];
  };
};

С использованием aligned_union в качестве типа для хранилища, упрощённая версия variant<Ts> может быть реализована следующим образом:
template <typename ...Ts>
class variant {
  template <typename T> struct _index_of { /*...*/ }; // индекс T в Ts..., начинающийся с 0

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); // Конструирует тип T в хранилище при помощи
                            // размещающего оператора 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;
};

Специальные функции-члены должны перенаправляться в активный член (если таковой имеется). И снова, мы не можем просто использовать инструкцию switch для достижения этой цели — хотя, если бы мы могли это делать, вряд ли всё значительно упростилось бы — и непосредственное замещение имело бы рекурсивную реализацию:
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); }
}

Нерекурсивная реализация метода apply может быть построена при помощи таблицы переходов, подобно тому, как это делает инструкция switch, с последующим переходом на подходящую запись:
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); }
}

Нерекурсивная реализация не только даёт более быстрый сгенерированный код, но также значительно ускоряет компиляцию с случае большого числа типов в списке Ts — в вашем случае оценка может меняться.

Тривиально копируемые типы


Тривиально копируемый тип — это такой тип, который может быть скопирован путём копирования составляющих его битов — то есть, с помощью std::memcpy.
3.9 [basic.types]/2 Для любого объекта (кроме подобъектов базового класса) тривиально копируемого типа T, содержат ли они или нет допустимые значения типа T, составляющие его байты (1.7) можно скопировать в массив char или unsigned char. Если содержимое массива char или unsigned char скопировать обратно в объект, в результате объект должен получить своё первоначальное значение. [...]
3.9 [basic.types]/3 Для любого тривиально копируемого типа T, если два указателя на T указывают на различные объекты obj1 и obj2 типа T, где либо obj1, либо obj2 являются подобъектами базового класса и составляющие obj1 байты (1.7) копируются в obj2, в результате obj2 должен содержать тоже самое значение, что и obj1. [...]

Оригинал
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. [...]


Объединение тривиально копируемых членов само является тривиально копируемым, что записывает его в кандидаты для дополнительной оптимизации, которую нельзя провести для нетривиально копируемого типа. Отсюда следует, что variant с тривиально копируемыми типами также должен стремиться быть тривиально копируемым.
9 [class]/6 Тривиально копируемый класс — это класс, который:
  • не имеет нетривиальных конструкторов копирования (12.8),
  • не имеет нетривиальных конструкторов перемещения (12.8),
  • не имеет нетривиальных копирующих операторов присваивания (13.5.3, 12.8),
  • не имеет нетривиальных перемещающих операторов присваивания (13.5.3, 12.8) и
  • имеет тривиальный деструктор (12.4).

[...]

Оригинал
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).

[...]


Для достижения этой цели должна быть выбрана отдельная специализация variant, если все типы в Ts являются тривиально копируемыми. Специальные функции-члены, перечисленные выше, не должны предоставляться пользователем для этой специализации — они должны либо предоставляться неявно, либо явно быть указанными при их первом определении, как генерируемые по умолчанию. Реализация предоставит для них неявные определения, которые будут тривиальными; операторы копирования и перемещения будут просто копировать содержащие их биты хранилища вместе с дискриминатором, деструктор же ничего не будет делать.
Но здесь есть одна загвоздка: тривиально копируемый класс может быть вообще некопируемым, хотя специальная функция-член, удалённая при его первом определении, является тривиальной. Взглянем, к примеру, на то, как определён класс boost::noncopyable:
class noncopyable {
protected:
  constexpr noncopyable() = default;
  noncopyable(noncopyable const&) = delete;
  noncopyable& operator=(noncopyable const&) = delete;
  ~noncopyable() = default;
};

Может стать сюрпризом то, что std::is_trivially_copyable выводит true для класса noncopyable. Ещё большим сюрпризом может стать то, что экземпляр variant<noncopyable> может быть успешно скопирован, поскольку удалённые функции-члены noncopyable вообще не используются. Это, по сути, нарушение безопасности типов вытекает из решения использовать нетипизированное голое хранилище для хранения активного члена.

Тривиально разрушаемые типы


Другой важной категорией типов являются тривиально разрушаемые типы.
12.4 [class.dtor]/5 [...] Деструктор является тривиальным, если он не предоставлен пользователем и если:
  • он не является виртуальным,
  • все непосредственные базовые классы даного класса имеют тривиальные деструкторы и
  • для всех нестатических членов данного класса, имеющих своим типом класс (или массив классов), каждый такой класс имеет тривиальный деструктор.

В противном случае деструктор является нетривиальным.

Оригинал
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.


Это особенно важно, поскольку одним из требований к литеральному типу — чьи экземпляры могут быть использованы в контексте constexpr-выражения — является его тривиальная разрушаемость.
3.9 [basic.types]/10 Тип является литеральным типом, если он является:
  • [...]
  • типом класса (пункт 9), обладающим всеми следующими свойствами:
    • он имеет тривиальный деструктор,
    • он является составным типом (8.5.1) или имеет как минимум один constexpr-конструктор или шаблонный конструктор, который не является конструктором копирования или перемещения и
    • все его нестатические члены и базовые классы являются неизменными литеральными типами.



Оригинал
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.




Объединение может быть литеральным типом, при условии, что как минимум один из его членов является литеральным типом, а остальные члены являются тривиально разрушаемыми. Отсюда следует, что variant при этих условиях также должен стремиться быть литеральным типом. Ещё одна специализация variant должна выбираться, если все типы в Ts являются тривиально разрушаемыми. Однако, она не столь полезна, поскольку среди ограничений на константные выражения присутствует ограничение на приведение указателя на void к указателю на объект:
5.19 [expr.const]/2 Условное выражение e является ядром константного выражения только если вычисление e, следующее правилам абстрактной машины (1.9), не вычислится в одно из следующих выражений:
  • [...]
  • преобразование из типа cv void* к типу указателя на объект;
  • [...]


Оригинал
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;
  • [...]



И вновь, решение использовать нетипизированное сырое хранилище ограничивает полноту реализации обобщённого размеченного объединения тем же уровнем, который можно достичь, реализовав его вручную.

О чём ещё не сказано


Реализация на основе сырого хранилища — хотя она и оправдывает свою цену — не выдерживает критики, стоит выйти за привычные рамки. Хранилищем значений в обобщённом типобезопасном размеченном объединении обязательно должно быть обычное объединение, а иначе не получится задействовать всю его функциональность.

+16
7.8k 69
Comments 13
Top of the day