Eggs.Variant — Часть I

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

Оглавление

1. Введение
2. Проектирование
3. Реализация
   • Тривиально копируемые типы
   • Тривиально разрушаемые типы

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

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

Введение

Объединение — это специальный тип класса, который в один момент времени может хранить только один из своих нестатических членов. Он занимает столько места, сколько надо, чтобы вместить наибольший из его членов.

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

В C++98 члены объединения ограничены тривиальными типами объектов. Для этих типов их время жизни начинается при получении хранилища и заканчивается при его переиспользовании или освобождении.

3.8 [basic.life]/1 [...] Время жизни объекта типа T начинается, когда:

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

Время жизни объекта типа T заканчивается, когда:

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

Эта специальная гарантия позволяет менять активный член объединения просто присвоив объединению новое значение, эффективно переиспользуя хранилище — что хорошо согласуется если не с буквой, то с духом стандарта.
Кроме того, объединение не знает, какой его член — если они есть — активен, так что его специальные функции-члены должны реализовываться без знания этой информации. Поскольку члены ограничены тривиальными типами, специальные функции-члены могут быть реализованы в терминах лежащих в основе объединения байтов не зависящих от активного члена.

9.5 [class.union]/1 [...] Объект класса с нетривиальным конструктором (12.1), нетривиальным конструктором копирования (12.8), нетривиальным деструктором (12.4) или нетривиальным копирующим оператором присваивания (13.5.3, 12.8) не может быть членом объединения, либо элементом массива в объединении. [...]

В 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]/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 некоторые из этих функций-членов должны быть предоставлены пользователем. —конец примера]

Эти нетривиальные функции-члены могут быть предоставлены — с соблюдением их обычной семантики — только если будет знание о том, какой член перечисления активен, чтобы его можно было передать дальше. Размеченное объединение — это объединение или класс, подобный объединению, которое обладает знанием о себе, то есть, оно содержит некоторый идентификатор, который позволяет узнать, какой член — если он есть — сейчас активен. Размеченное объединение может предоставлять все специальные функции-члены, неважно, тривиальные они или нет.
Экземпляр класса 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; использование дополнительного хранилища, например, динамической памяти, не допускается.
• Чётко определённая семантика u должна соответствовать или быть улучшенной v. Неопределённое поведение, например, ссылка на неактивный член u, не должно позволяться интерфейсом v.
• Типом 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.

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

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

9 [class]/6 Тривиально копируемый класс — это класс, который:

• не имеет нетривильных конструкторов копирования (12.8),
• не имеет нетривильных конструкторов перемещения (12.8),
• не имеет нетривильных копирующих операторов присваивания (13.5.3, 12.8),
• не имеет нетривильных перемещающих операторов присваивания (13.5.3, 12.8) и
• имеет тривильный деструктор (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 [...] Деструктор является тривиальным, если он не предоставлен пользователем и если:

• деструктор не является виртуальным,
• все непосредственные базовые классы даного класса имеют тривиальные деструкторы и
• для всех нестатических членов данного класса, которые имеют тип класса (или тип массива классов), каждый такой класс имеет тривиальный деструктор.

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

Это особенно важно, поскольку одним из требований к литеральному типу — чьи экземпляры могут быть использованы в контексте constexpr-выражения — является их тривиальная разрушаемость.

3.9 [basic.types]/10 Тип является литеральным типом, если он является:

• [...]
• типом класса (пункт 9), обладающим всеми следующими свойствами:
  • он имеет тривиальный деструктор,
  • он является составным типом (8.5.1) или имеет как минимум один constexpr-конструктор или шаблонный конструктор, который не является конструктором копирования или перемещения и
  • все его нестатические члены и базовые классы являются неизменными литеральными типами.

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

5.19 [expr.const]/2 Условное выражение e является ядром константного выражения только если вычисление e, следующее правилам абстрактной машины (1.9), не вычислится в одно из следующих выражений:

• [...]
• преобразование из типа cv void* к типу указателя на объект;
• [...]

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

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

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

Автор: Mingun

Источник