Концепты: упрощаем реализацию классов STD Utility19.09.2019 18:34

Появляющиеся в C++20 концепты — давно и широко обсуждаемая тема. Несмотря на избыток материала, накопившегося за годы (в т.ч. выступления экспертов мирового уровня), среди прикладных программистов (не засыпающих ежедневно в обнимку со стандартом) все еще остается неразбериха, что же такое С++20-концепты и так ли они нам нужны, если есть проверенный годами enable_if. Частично виной тому то, как концепты эволюционировали за ~15 лет (Concepts Full + Concept Map → Concepts Lite), а частично то, что концепты получились непохожими на аналогичные средства в других языках (Java/С# generic bounds, Rust traits, …).

Под катом — видео и расшифровка доклада Андрея Давыдова из команды ReSharper C++ с конференции C++ Russia 2019. Андрей сделал краткий обзор concept-related нововведений C++20, после чего рассмотрел реализацию некоторых классов и функций STL, сравнивая C++17 и С++20-решения. Далее повествование — от его лица.

Поговорим о концептах. Это довольно сложная и обширная тема, так что, готовясь к докладу, я был в некотором затруднении. Я решил обратиться к опыту одного из лучших спикеров C++ комьюнити Андрея Александреску.

В ноябре 2018 года, выступая на открытии Meeting C++, Андрей спросил аудиторию о том, что будет следующей большой фичей C++:

• концепты,
• метаклассы,
• или интроспекция?

Давайте и мы начнём с этого вопроса. Считаете ли вы, что следующей большой фичей в C++ будут концепты?

По мнению Александреску, концепты — это скучно. Вот этой скучной вещью я и предлагаю вам заняться. Тем более, что я всё равно не смогу так же интересно и зажигательно рассказать про метаклассы, как Герб Саттер, или про интроспекцию, как Александреску.

Что мы имеем в виду, когда говорим о концептах в C++20? Эта фича обсуждалась как минимум с 2003 года, и она за это время успела сильно эволюционировать. Давайте разберёмся, какие новые concept related-фичи появились в C++20.

Новая сущность под названием «концепты» определяется ключевым словом concept. Это предикат на шаблонных параметрах. Выглядит это примерно так:

template  concept NoThrowDefaultConstructible = noexept(T{});

template 
concept Assignable = std::is_assignable_v

Я не просто так использовал фразу «на шаблонных параметрах», а не «на типах», потому что концепты можно определять и на нетиповых шаблонных параметрах. Если вам совсем делать нечего, можно определить концепт для числа:

template concept Even = I % 2 == 0;

Но гораздо больше смысла в том чтобы смешивать типовые и нетиповые шаблонные параметры. Назовём тип маленьким, если его size и alignment не превышает заданных ограничений:

template
concept Small = sizeof(T) <= MaxSize && alignof(T) <= MaxAlign;

Наверное, пока неочевидно, почему нам нужно городить в языке новую сущность, и почему концепт — это не просто constexpr bool переменная.

// почему `concept` нельзя определить таким образом?
#define concept constexpr bool

Чтобы разобраться, давайте посмотрим, как используются концепты.

Во-первых, так же, как и constexpr bool переменные, их можно использовать везде, где вам в compile-time нужно булевское выражение. Например, внутри static_assert или внутри noexcept
спецификаций:

// bool expression evaluated in compile-time
static_assert(Assignable);

template
void test() noexcept(NothrowDefaultConstructible) {
  T t;
  ...
}

Во-вторых, концепты можно использовать вместо ключевых слов typename или class при определении шаблонных параметров. Определим простой класс optional, который будет просто хранить пару из булевского флажка initializedи значения. Естественно, такой optional применим только для тривиальных типов. Поэтому мы тут пишем Trivial и при попытке проинстанцировать от чего-то нетривиального, например, от std::string, у нас будет ошибка компиляции:

// вместо type-parameter-key (class, typename)
template
class simple_optional {
  T value;
  bool initialized = false;
  ...
};

Концепты можно применять частично. К примеру, реализуем свой класс any со small buffer оптимизацией. Определим структуру SB (small buffer) с фиксированным Size и Alignment, будем хранить union из SB и указателя в куче. И теперь, если в конструктор приходит маленький тип, то мы можем просто разместить его в SB. Чтобы определить, что тип маленький, мы пишем, что он удовлетворяет концепту Small. Концепт Small принимал 3 шаблонных параметра: два мы определили, и у нас как бы получилась функция от одного шаблонного параметра:

// Частичное применение
class any {
  struct SB {
    static constexpr size_t Size = ...;
    static constexpr size_t Alignment = ...;

    aligned_storage_t storage;
  };
  union {
    SB sb;
    void* handle;
  };
  template T>
  any(T const & t) : sb(...) ...
};

Есть и более краткая запись. Мы пишем имя шаблонного параметра, возможно, с какими-то аргументами, перед auto. Предыдущий пример переписывается таким образом:

// Terse syntax (ограничение на auto)
class any {
  struct SB {
    static constexpr size_t Size = ...;
    static constexpr size_t Alignment = ...;

    aligned_storage_t storage;
  };
  union {
    SB sb;
    void* handle;
  };
  any(Small auto const & t) : sb(...) ...
};

Наверное, в любом месте, где мы пишем auto, теперь можно писать перед ним имя концепта.

Определим функцию get_handle, которая возвращает для объекта некоторый handle.
Будем считать, что маленькие объекты сами для себя являются handle, а для больших — указатель на них является handle. Поскольку у нас две ветки if constexpr обозначают выражения разных типов, то нам удобно не указывать тип этой функции явно, а попросить компилятор его вывести. Но, написав там просто auto, мы потеряем информацию о том, что обозначаемое значение маленькое, оно не превышает указатель:

//Terse syntax (ограничение на auto)
template
concept LEPtr = Small;

template
auto get_handle(T& object) {
  if constexpr (LEPtr)
    return object;
  else
    return &object;
}

В C++20 можно будет перед ним написать, что это не просто auto, это ограниченное auto:

// Terse syntax (ограничение на auto)
template
concept LEPtr = Small;

template
LEPtr auto get_handle(T &object) {
    if constexpr (LEPtr)
        return object;
    else
        return &object;
}

Requires expression — это целое семейство expression’ов, все они имеют тип bool и вычисляются в compile-time. Их используют для проверки утверждений о выражениях и типах. Requires expression очень удобно применять для определения концептов.

Пример с Constructible. Те, кто были на моём предыдущем докладе, уже его видели:

template
concept Constructible = requires(Args... args) { T{args...} };

И пример с Comparable. Скажем, что тип T является Comparable, если два объекта типа T можно сравнить с помощью оператора «меньше» и результат конвертируется в bool. Эта стрелочка и тип после неё означают, что тип expression конвертируется в bool, а не то, что он равен bool:

template
concept Comparable = requires(T const & a, T const & b) {
  {a < b} -> bool;
};

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

У нас есть уже концепт Comparable, давайте определим концепты для итераторов. Скажем, RandomAccessIterator — это BidirectionalIterator и ещё какие-то свойства. Имея это, определим концепт Sortable. Range называется Sortable, если его итератор RandomAccessи его элементы можно сравнивать. И теперь мы можем написать функцию sort, которая принимает не абы что, а Sortable Range:

// concepts, полный пример в С++20

template
concept RandomAccessIterator = BidirectionalIterator && ...;

template
concept Sortable = RandomAccessIterator> && Comparable>;

template
void sort(Range &) {...}

Теперь, если мы попробуем вызвать эту функцию от чего-то, не удовлетворяющего концепту Sortable, мы получим от компилятора хорошую, SFINAE-friendly ошибку с понятным сообщением. Попробуем проинстанцировать std::list'ом или вектором элементов, которые не умеют сравниваться:

//concepts, полный пример в С++20, тесты

struct X {};
void test() {
  vector vi; sort(vi); // OK
  list  li; sort(li); // Fail, list::iterator is not random access
  vector< X > vx; sort(vx); // Fail, X is not Comparable
}

Вы уже видели подобный пример использования концептов или что-то очень похожее? Я такое видел несколько раз. Честно скажу, меня это совсем не убеждало. Нужно ли нам городить в языке столько новых сущностей, если можно получить это в C++17?

//concepts, полный пример в  С++17

#define concept constexpr bool

template
concept Comparable = is_convertible_v<
  decltype(declval() < declval()), bool
  >;

template
concept RandomAccessIterator = BidirectionalIterator && ...;

template
concept Sortable = RandomAccessIterator> && Comparable>;

template>>
void sort(Range &) { ... }

Ключевое слово concept я ввёл макросом, а Comparable переписывается таким образом. Он стал немножко уродливее, и это намекает нам, что requires expression действительно полезная и удобная вещь. Вот мы определили концепт Sortable и с помощью enable_if указали, что функция sort принимает Sortable Range.

Можно подумать, что такой способ сильно проигрывает по сообщениям об ошибках компиляции, но, на самом деле, это вопрос качества реализации компилятора. Скажем, в Clang на эту тему подсуетились и специально захачили, что если при подстановке enable_if у вас первый аргумент
вычисляется false, то они презентуют эту ошибку так, что такой вот requirement не был удовлетворён.

Пример выше как будто бы написан через концепты. У меня есть гипотеза: этот пример неубедительный, потому что он не использует главную фичу концептов — requires clause.

Requires clause — это такая штука, которая вешается на почти любую шаблонную декларацию или на нешаблонную функцию. Синтаксически это выглядит как ключевое слово requires, а дальше некоторое булевское выражение. Это нужно для того, чтобы отфильтровывать template specialization или overloading candidate, то есть работает так же как SFINAE, только сделанный правильно, а не хаками:

// requires-clause

template concept Sortable
  = RandomAccessIterator> && Comparable>;

template
void sort(Range &) { ... }

Где в нашем примере с сортировкой, мы можем использовать requires clause? Вместо краткого синтаксиса применения концептов напишем так:

template concept Sortable
  = RandomAccessIterator> && Comparable>;

template requires Sortable
void sort(Range &) { ... }

Кажется, что код стал только хуже, и его стало больше. Но теперь мы можем избавиться от концепта Sortable. C моей точки зрения, это улучшение, поскольку сам по себе концепт Sortable тавтологичный: мы называем Sortable всё, что можно передать в функцию sort. Физического смысла это не имеет. Перепишем код таким образом:

//template concept Sortable
//    = RandomAccessIterator> && Comparable>;

template requires
  RandomAccessIterator> && Comparable>;
void sort(Range &) { ... }

Список concept-related нововведений в C++20 выглядит так. Пункты в этом списке отсортированы по возрастанию полезности фичи с моей субъективной точки зрения:

• Новая сущность concept. Без сущности concept, мне кажется, можно было бы обойтись, наделив constexpr bool переменные дополнительной семантикой.
• Специальный синтаксис для применения концептов. Конечно, он приятен, но это всего лишь синтаксис. Если бы программисты на C++ боялись плохого синтаксиса, они бы давно уже вымерли от страха.
• Requires expression — это действительно клёвая штука, и она полезна не только для определения концептов.
• Requires clause — это самая большая ценность концептов, она позволяет забыть о SFINAE и прочих легендарных ужасах шаблонов C++.

Прежде чем мы перейдём к обсуждению requires clause, пара слов о requires expression.

Во-первых, их можно применять не только для определения концептов. С незапамятных времен на майкрософтовском компиляторе есть расширение __if_exists-__if_not_exists. Оно позволяет в compile-time проверять существование имени и в зависимости от этого включать или выключать компиляцию блока кода. А в кодовой базе, с которой я работал несколько лет назад, было примерно такое. Есть функция f(), она принимает точку шаблонного типа и берёт от этой точки высоту. Она может инстанцироваться трёхмерной или двухмерной точкой. Для трёхмерной мы считаем высотой координату z, для двухмерной мы обращаемся к специальному сенсору поверхности. Это выглядит вот таким образом:

struct Point2 { float x, y; };
struct Point3 { float x, y, z; };

template
void f(Point const & p) {
  float h;
  __if_exists(Point::z) {
    h = p.z;
  }
  __if_not_exists(Point::z) {
    h = sensor.get_height(p);
  }
}

В C++20 мы можем это переписать без использования расширений компилятора, стандартным кодом. Как мне кажется, стало не хуже:

struct Point2 { float x, y; };
struct Point3 { float x, y, z; };

template
void f(Point const & p) {
  float h;
  if constexpr(requires { Point::z; })
    h = p.z;
  else
    h = sensor.get_height(p);
}

Второй момент — это то, что надо быть бдительным с синтаксисом requires expression.
Они довольно мощные, и эта мощь достигается тем, что вводится много новых синтаксических конструкций. В них можно запутаться, по крайней мере, поначалу.

Давайте определим концепт Sizable, который проверяет, что у контейнера есть константный метод size, возвращающий size_t. Мы, естественно, ожидаем, что vector является Sizable, однако этот static_assert заваливается. Понимаете, из-за чего у нас ошибка? Почему этот код не компилируется?

template
concept Sizable = requires(Container const & c) {
  c.size() -> size_t;
};
static_assert(Sizable>); // Fail

Давайте я покажу код, который компилируется. Такой класс X удовлетворяет концепту Sizable. Теперь понимаете, в чём у нас проблема?

struct X {
  struct Inner {
    int size_t;
  };
  Inner* size() const;
};
static_assert(Sizable); // OK

Давайте я исправлю подсветку кода. Слева код раскрашен так, как мне бы хотелось. А на самом деле, он должен быть раскрашен так, как справа:

Видите, поменялся цвет size_t, стоящего после стрелочки? Я хотел, чтобы это был тип, но это просто поле, к которому мы обращаемся. Всё, что у нас в requires expression — это одно большое выражение, и мы проверяем его корректность. Для типа X — да, это корректное выражение, для vector — нет. Чтобы достичь того, что мы хотели, нужно взять выражение в фигурные скобки:

template
concept Sizable = requires(Container const & c) {
  {c.size()} -> size_t;
};
static_assert(Sizable>); // OK

struct X {
  struct Inner {
    int size_t;
  };
  Inner* size() const;
};
static_assert(Sizable); // Fail

Но это просто забавный пример. В общем-то, просто нужно проявлять аккуратность.

Реализация класса pair

Дальше я буду демонстрировать какие-то фрагменты STL, которые можно реализовать в C++17, но довольно громоздко.
А затем мы посмотрим, как в C++20 мы можем улучшить имплементацию.

Давайте начнём с класса pair.
Это очень старый класс, он есть ещё в C++98.
Он не содержит какой-то сложной логики, так что
хотелось бы, чтобы его определение выглядело примерно таким образом.
Оно, с моей точки зрения, должно примерно на этом и закончиться:

template struct pair {
  F f; S s;
  ...
};

Но, согласно cppreference, у pair одних только конструкторов 8 штук.
А если посмотреть в настоящую реализацию, допустим, в майкрософтовскую STL, то будет целых 15 конструкторов класса pair. Мы не будем смотреть на всю эту мощь и ограничимся конструктором по умолчанию.

Казалось бы, в нём-то что сложного? Для начала поймём, зачем он нужен. Мы хотим, чтобы если один из аргументов класса pair был тривиального типа, допустим, int, то после конструирования класса pair он был инициализирован нулём, а не оставался неинициализированным. Для этого мы хотим написать такой конструктор, который вызовет value-инициализацию для полей f (first) и s (second).

template struct pair {
  F f; S s;

  pair()
    : f()
    , s()
  {}
};

К сожалению, если мы попробуем проинстанцировать pair от чего-то, что не имеет конструктора по умолчанию, допустим, от такого класса А, мы сразу же получим ошибку компиляции. Желаемое поведение — это чтобы при попытке сконструировать pair по умолчанию была бы ошибка компиляции, но если мы явно передаём значения f и s, то всё бы работало:

struct A {
  A(int);
};

pair a2;     // must fail
pair a1; { 1, 2 };    // must be OK

Для этого нужно сделать конструктор по умолчанию шаблонным и ограничить его по SFINAE.
Первая идея, которая приходит в голову, — давайте напишем так, что этот конструктор разрешён, только если f и s — is_default_constructable:

template struct pair {
  F f; S s;

  template, // not dependent
      is_default_constructible
    >>>
  pair() : f(), s() {}
};

template struct pair {
  F f; S s;

  template,
      is_default_constructible
    >>>
  pair() : f(), s() {}
};

struct B { explicit B(); };

pair p = {};

template struct pair {
  F f; S s;

  template,
      is_default_constructible,
      is_implicity_default_constructible,
      is_implicity_default_constructible
    >>>
  pair() : f(), s() {}

  template<...> explicit pair() : f(), s() {}
};

template true_type test(T, int);
template false_type test(int, ...);

template
using is_implicity_default_constructible = decltype(test({}, 0));

template<..., typename = enable_if_t,
    is_default_constructible,
    is_implicity_default_constructible,
    is_implicity_default_constructible
  >>>
...
pair p = {};
...
candidate template ignored: requirement 'conjunction_v<
  is_default_constructible,
  is_default_constructible,
  is_implicity_default_constructible,
  is_implicity_default_constructible
>' was not satisfied [with T=int, U=B]

template<...,
    typename = enable_if_t::value>>,
    typename = enable_if_t::value>>,
    typename = enable_if_t::value>>,
    typename = enable_if_t::value>>
  >
...

pair p = {};

// candidate template ignored: requirement 'is_implicity_default_constructible::value' was not satisfied
with...

template struct pair {
    F f; S s;

    pair() requires DefaultConstructible
            && DefaultConstructible
            && ImplicitlyDefaultConstructible
            && ImplicitlyDefaultConstructible
        : f(), s() {}

    explicit pair() ...      
};

template concept ImplicitlyDefaultConstructible =
    requires { [] (T) {} ({}); };

template struct pair {
  F f; S s;

  explicit(!ImplicityDefaultConstructible ||
           !ImplicityDefaultConstructible)
  pair() requires DefaultConstructible
               && DefaultConstructible
    : f(), s() {}
};

enum Option {
  None,
  Some(t)
}

class Optional {
  final T value;

  Optional()  {this.value = null; }
  Optional(T value)  {this.value = value; }
}

template class optional {
  bool initialized;
  aligned_storage_t storage;

    ...

  ...
  T       & get()       & { return reinterpret_cast(storage); }
  T const & get() const & { return reinterpret_cast(storage); }
  T      && get()      && { return move(get()); }

  optional() noexcept : initialized(false) {}
  optional(T const & value) noexcept(NothrowCopyConstructible)
    : initialized(true) {
    new (&storage) T(value);
  }
  ~optional() : noexcept(NothrowDestructible) { if (initialized) get().~T(); }
};

template class optional {
  bool initialized;
  aligned_storage_t storage;
  ...

  optional(optional const & other) noexcept(NothrowCopyConstructible)
    : initialized(other.initialized) {
    if (initialized) new (&storage) T(other.get());
  }

  optional& operator =(optional && other) noexcept(...) {...}
};

optional& operator =(optional && other) noexcept(...) {
  if (initialized) {
    if (other.initialized) {
      get() = move(other.get());
    } else {
      initialized = false; other.initilized = true;
      new(&other.storage) T(move(get()));
      get().~T();
    }
  } else if (other.initialized) {
    initialized = true; other.initialized = false;
    new(&storage) T(move(get()));
    other.get().~T();
  }
  return *this;
}

optional& operator =(optional && other)
    noexcept(NothrowAssignable &&
             NothrowMoveConstructible &&
             NothrowDestructible) {
  if (initialized) {
    if (other.initialized) {
      get() = move(other.get());
    } else {
      initialized = false; other.initialized = true;
      new (&other.storage) T(move(get()));
      get().~T();
    }
  }
  ...
}

template class optional {
  ...
  optional(optional const &)  noexcept(NothrowCopyConstructible);
  optional(optional &&)       noexcept(NothrowMoveConstructible);
  optional& operator =(optional const &)  noexcept(...);
  optional& operator =(optional &&)       noexcept(...);
};

template class optional>; // compilation error

template struct deleted_copy_construct : Base {
  deleted_copy_construct(deleted_copy_construct const &)                = delete;
  deleted_copy_construct(deleted_copy_construct &&)                     = default;
  deleted_copy_construct& operator =(deleted_copy_construct const &)    = default;
  deleted_copy_construct& operator =(deleted_copy_construct &&)         = default;
};

template struct copy_construct : Base {
  copy_construct(copy_construct const & other)
      noexcept(noexcept(Base::construct(other))) {
    Base::construct(other);
  }
  copy_construct(copy_construct &&)                     = default;
  copy_construct& operator =(copy_construct const &)    = default;
  copy_construct& operator =(copy_construct &&)         = default;
};

template
using select_copy_construct = conditional_t
  copy_construct
  deleted_copy_construct
>;

template class optional_base {
  ...
  void construct(optional_base const & other) noexcept(NothrowCopyConstructible) {
    if ((initialized = other.initialized)) new (&storage) t(other.get());
  }
};

template class optional : select_copy_construct> {
  ...
};

template
using select_move_construct = select_copy_construct,
    move_construct
  >
>;

template
using select_copy_assign = select_move_construct && CopyConstructible,
    copy_assign
    delete_copy_assign
  >
>;

template
using select_move_assign = select_copy_assign;

template class optional_base {
  ...
  void construct(optional_base const&)  noexcept(NothrowCopyConstructible);
  void construct(optional_base &&)      noexcept(NothrowMoveConstructible);
  optional_base& assign(optional_base &&)       noexcept(...);
  optional_base& assign(optional_base const &)  noexcept(...);
};

template class optional : select_move_assign> {
  ...
};

optional>
  : deleted_copy_construct<...>
    : move_construct<...>
      : deleted_copy_assign<...>
        : move_assign<...>
          : optional_base>

template
class optional : select_move_assign> {...};

static_assert(TriviallyCopyable>);

static_assert(TriviallyCopyConstructible>);
static_assert(TriviallyMoveConstructible>);
static_assert(TriviallyCopyAssignable   >);
static_assert(TriviallyMoveAssignable   >);
static_assert(TriviallyDestructible     >);

template
using select_copy_construct = conditional_t,
  copy_construct
  deleted_copy_construct
>;

template
using select_copy_construct = conditional_t,
  conditional_t,
    Base,
    copy_construct
  >,
  deleted_copy_construct
>;

template
using select_destruct = conditional_t,
    Base,
    destruct
  >
>;

optional>
  : deleted_copy_construct<...>
    : move_construct<...>
      : deleted_copy_assign<...>
        : move_assign<...>
          : destruct>>
            : optional_base>