Пишем сериализатор для сетевой игры на C++1116.06.2016 01:03

e5e30668003f4348a50a52e174b0c5db.pngНаписать этот пост меня вдохновила замечательная статья в блоге Gaffer on Games «Reading and Writing Packets» и неуёмная тяга автоматизировать всё и вся (особенно написание кода на C++!).

Начнём с постановки задачи. Мы пишем сетевую игру (и сразу MMORPG, конечно же!), и независимо от архитектуры у нас возникает необходимость постоянно посылать и получать данные по сети. У нас, скорее всего, возникнет необходимость посылать несколько разных типов пакетов (действия игроков, обновления игрового мира, просто-напросто аутентификация, в конце концов!), и для каждого у нас должна быть функция чтения и функция записи. Казалось бы, не вопрос сесть и написать спокойно эти две функции и не нервничать, однако у нас сразу же возникает ряд проблем.

  • Выбор формата. Если бы мы писали простенькую игру на JavaScript, нас бы устроил JSON или любой его самописный родственник. Но мы пишем серьёзную многопользовательскую игру, требовательную к трафику; мы не можем позволить себе отправлять ~16 байт на float вместо четырёх. Значит, нам нужен «сырой» двоичный формат. Однако, двоичные данные усложняют отладку; было бы здорово, если бы мы могли менять формат в любой момент, не переписывая целиком все наши функции чтения/записи.
  • Проблемы безопасности. Первое правило сетевой игры: не доверяй данным, присланным клиентом! Функция чтения должна уметь оборваться в любой момент и вернуть false, если что-то пошло не так. При этом использовать исключения считается неважной идеей, поскольку они слишком медленные. Мамкин хакер пусть и не сломает ваш сервер, но вполне может ощутимо замедлить его беспрерывными эксепшнами. Но вручную писать код, состоящий из if’ов и return’ов, неприятно и неэстетично.
  • Повторяющийся код. Функции чтения и записи похожи, да не совсем. Необходимость изменить структуру пакета приводит к необходимости поменять две функции, что рано или поздно приведёт к тому, что вы забудете поменять одну из них или поменяете их по-разному, что приведёт к трудно отлавливаемым багам. Как справедливо замечает Gaffer on Games, it is really bloody annoying to maintain separate read and write functions.


Всех интересующихся тем, как Бендер выполнил своё обещание и при этом решил обозначенные проблемы, прошу под кат.

Потоки чтения и записи


Начнём с начальных предположений. Мы хотим уметь писать и читать текстовый и бинарный формат; пусть текстовый формат будет читаться и писаться из/в стандартные потоки STL (std::basic_istream и std::basic_ostream, соответственно). Для бинарного формата у нас будет свой класс BitStream, поддерживающий аналогичный потокам STL интерфейс (как минимум операторы << и >>, метод rdstate(), возвращающий 0 при отсутствии ошибок чтения/записи и не 0 в остальных случаях, и способность кушать манипуляторы); так же было бы здорово, если бы он умел писать и читать данные длины, не кратной восьми битам.

Возможный интерфейс класса BitStream 
using byte = uint8_t;

class BitStream {
    byte* bdata;
    size_t position;
    size_t length, allocated;
    int mode;  // 0 = read, other = write
    int state; // 0 = OK
    void reallocate(size_t);
public:
    static const int MODE_READ  = 0; // здесь, конечно же, нужен модный
    static const int MODE_WRITE = 1; // enum class, но пока забьём
    inline int get_mode(void) const noexcept { return mode; }
    BitStream(void); // для записи
    BitStream(void*, size_t); // для чтения
    ~BitStream(void);
    int rdstate(void) const;
    // записать младшие how_much бит:
    void write_bits(size_t how_much, uint64_t bits);
    // прочитать how_much бит в младшие биты результата:
    uint64_t read_bits(size_t how_much);
    void* data(void);
    BitStream& operator<<(BitStream&(*func)(BitStream&)); // вкусные
    BitStream& operator>>(BitStream&(*func)(BitStream&)); // манипуляторы
};

template
typename std::enable_if::value, BitStream&>::type
operator<<(BitStream& out, const Int& arg); // записать 8*sizeof(Int) бит в поток

template
typename std::enable_if::value, BitStream&>::type
operator>>(BitStream& in, Int& arg); // прочитать 8*sizeof(Int) бит из потока

Зачем здесь enable_if и как он работает?
std::enable_if проверяет условие condition и, если оно выполнено (т.е. не равно нулю), определяет тип std::enable_if<...>::type, равный указанному пользователем типу T или (по умолчанию) void. Если условие не выполнено, обращение к std::enable_if<...>::type выдаёт undefined; такая ошибка помешает скомпилироваться нашему шаблону, но не помешает скомпилироваться программе, поскольку substitution failure is not an error (SFINAE) — ошибка при подстановке аргументов в шаблон не является ошибкой компиляции. Программа успешно скомпилируется, если где-то определена другая реализация operator<< с подходящей сигнатурой, или скажет, что подходящей для вызова функции просто нет (умный компилятор, возможно, уточнит, что он пытался, но у него случилось SFINAE).


Интерфейс сериализатора


Понятно, что теперь нам нужны базовые «кирпичики» сериализатора: функции или объекты, умеющие сериализовывать и парсить целые числа или числа с плавающей точкой. Однако, мы (конечно же!) хотим расширяемости, т.е. чтобы программист мог написать «кирпичик» для сериализации любого своего типа данных и использовать его в нашем сериализаторе. Как такой кирпичик должен выглядеть? Я предлагаю простейший формат: 

struct IntegerField {
    template
    static void serialize(OutputStream& out, int t) {
        out << t; // просто скормить сериализуемый объект в поток!
    } // эту функцию тоже можно заставить возвращать bool, но пока забьём

    template
    static bool deserialize(InputStream& in, int& t) {
        in >> t;  // просто вытащить считываемый объект из потока!
        return !in.rdstate(); // вернуть true, если при чтении не произошло ошибок
    }
};


Просто класс с двумя статическими методами и, возможно, неограниченным числом их перегрузок. (Так, вместо одного шаблонного метода допускается написать несколько: один для std::basic_ostream, один для BitStream, неограниченное количество для любых других стримов на вкус программиста.)

Например, для сериализации и парсинга динамического массива элементов интерфейс может выглядеть так: 

template
struct ArrayField {
    template
    static void serialize(OutputStream& out, size_t n, const T* data);

    template
    static void serialize(OutputStream& out, const std::vector& data);

    template
    static bool deserialize(InputStream& in, size_t& n, T*& data);
    
    template
    static bool deserialize(InputStream& in, std::vector& data);
};


Вспомогательные шаблоны can_serialize и can_deserialize


Далее нам потребуется возможность проверять, может ли такое-то поле запускать сериализацию/парсинг с такими-то аргументами. Здесь мы приходим к более подробному обсуждению variadic tempates и SFINAE.

Начнём с кода: 

template
struct TypeList { // просто вспомогательный класс, статический «список типов»
    static const size_t length = sizeof...(Types);
};

template class can_serialize;
template
class can_serialize>
{
    template 
    static char func(decltype(U::serialize(std::declval()...))*);

    template 
    static long func(...);

  public:
    static const int value = ( sizeof(func(0)) == sizeof(char) );
};


Что это? Это структура, на этапе компиляции определяющая по заданному классу F и списку типов L = TypeList, можно ли вызвать функцию F::serialize с аргументами этих типов. Например, 

can_serialize >::value

равно 1, как и 

can_serialize >::value

(потому что char& прекрасно конвертируется в int), однако, 

can_serialize >::value

равно 0, так как в IntegerField не предусмотрено метода serialize, принимающего на вход только поток вывода.

Как это работает? Более тонкий вопрос, давайте разберёмся.

ba0ff63db38d4256b46d0452d5a75ac9.pngНачнём с класса TypeList. Здесь мы используем обещанные Бендером variadic templates, то есть шаблоны с переменным количеством аргументов. Шаблон класса TypeList принимает произвольное количество аргументов-типов, которые помещаются в parameter pack под именем Types. (О том, как использовать parameter packs, я писал подробнее в предыдущей статье.) Наш класс TypeList не делает ничего полезного, но вообще с parameter pack на руках мы можем сделать довольно многое. Например, конструкция

std::declval()...

для parameter pack длины 4, содержащего типы T1, T2, T3, T4, раскроется при компиляции в

std::declval(), std::declval(), std::declval(), std::declval()


Далее. У нас есть шаблон can_serialize, принимающий класс F и список типов L, и частичная специализация, дающая нам доступ к самим типам в списке. (Если запросить can_serialize, где L не является списком типов, компилятор пожалуется на неопределённый шаблон (undefined template), и поделом.) В этой частичной специализации и просходит вся магия.

В её коде есть вызов func(0) внутри sizeof. Компилятор вынужден будет определить, какая из перегрузок функции func вызывается, чтобы вычислить размер возвращаемого в байтах, но он не станет пытаться скомпилировать её, и поэтому нас не ждёт ошибок типа «что-то я реализации вашей функции не нахожу» (равно как и ошибок «в теле функции какая-то лажа с типами», если бы это тело было). Сперва он попытается использовать первое определение func, весьма замысловатого вида: 

template 
static char func( decltype( U::serialize( std::declval()... ) )* );


Конструкция decltype выдаёт тип выражения в скобках; например, decltype(10) есть то же самое, что int. Но, как и sizeof, она не компилирует его; это позволяет работать фокусу с std::declval. std::declval — это функция, делающая вид, что возвращает rvalue-ссылку требуемого типа; она делает выражение U::serialize( std::declval()... ) имеющим смысл и мимикрирующим под настоящий вызов U::serialize, даже если у половины аргументов нет конструктора по умолчанию и мы не можем написать просто U::serialize( Ts()... ) (не говоря уже о том, что эта функция может требовать lvalue-ссылки! кстати, в этом случае declval выдаст lvalue-ссылку, потому что по правилам C++ T& && равно T&). Реализации она, конечно, не имеет; написать в обычном коде 

int a = std::declval();

 — плохая идея.

f2bd8175914d4d90a8eb5c4b41bb3ca5.pngТак вот. Если вызов внутри decltype невозможен (нет функции с такой сигнатурой или её подстановка вызывает ошибку по каким-либо причинам) — компилятор считает, что случилась ошибка подстановки шаблона (substitution failure), которая, как известно, is not an error (SFINAE). И он спокойно идёт дальше, пытаясь использовать следующее определение func, в котором никаких проблем уже не предвидится. Однако, другая функция возвращает результат другого размера, что легко можно отловить с помощью sizeof.

В качестве пищи для самостоятельного размышления приведу также код шаблона can_deserialize, который специально чуть-чуть сложнее: он не только проверяет, можно ли вызвать F::deserialize с заданными типами аргументов, но и убеждается, что тип результата равен bool.

template class can_deserialize;
template
class can_deserialize>
{
    template  static char func(
        typename std::enable_if<
            std::is_same()...)), bool>::value
        >::type*
    );
    template  static long func(...);
  public:
    using type = can_deserialize;
    static const int value = ( sizeof(func(0)) == sizeof(char) );
};


Собираем пакеты из кирпичиков


Наконец, время заняться содержательной частью сериализатора. Вкратце, мы хотим получить шаблонный класс Schema, который бы предоставлял функции serialize и deserialize, собранные из «кирпичиков»: 

using MyPacket = Schema>;
MyPacket::serialize(std::cout, 10, 15, 0.3, 0, nullptr);
int da, db;
float fc;
std::vector my_vector;
bool success = MyPacket::deserialize(std::cin, da, db, fc, my_vector);


Начнём с простого — объявления шаблонного класса (с переменным числом аргументов, ня!) и конца рекурсии.

template
struct Schema;

template<>
struct Schema<> {
    template
    static void serialize(OutputStream&) {
        // ничего не надо делать!
    }
    template
    static bool deserialize(InputStream&) {
        return true; // нет работы -- нет ошибок!
    }
};


Но как должен выглядеть код функции serialize в схеме с ненулевым числом полей? Заранее вычислить типы, принимаемые функциями serialize всех данных полей, и сконкатенировать их мы не можем: это потребовало бы ещё не включенных в стандарт invocation type traits. Остаётся лишь сделать функцию с переменным числом аргументов и отправлять столько из них в каждое поле, сколько то может съесть — тут-то нам и пригодится рождённая в муках can_serialize.

Для такой рекурсии по числу аргументов нам потребуется вспомогательный класс (основной класс Schema будет заниматься рекурсией по числу полей). Определим его, не скупясь на аргументы: 

template<
    typename F,   // текущее поле, serialize которого мы пытаемся вызвать
    typename NextSerializer, // куда потом отправить «лишние» аргументы
    typename OS,  // тип потока вывода
    typename TL,  // типы аргументов, с которыми пытаемся вызвать F::serialize
    bool can_serialize // можно ли вызвать с такими типами
> struct SchemaSerializer;


Тогда частичная специализация Schema, окончательно реализующая рекурсию по числу полей, примет вид

template
struct Schema {
    template<
        typename OutputStream, // любой поток вывода
        typename... Types      // сколько угодно каких угодно аргументов
    > static void serialize(OutputStream& out, Types&&... args) {
        // просто вызываем serialize вспомогательного класса:
        SchemaSerializer<
            F,                  // текущее поле
            Schema,  // рекурсия по числу полей
            OutputStream&,      // тип потока вывода
            TypeList, // типы всех имеющихся аргументов
            can_serialize>::value // !!!
        >::serialize(out, std::forward(args)...);
    }

    // . . . (здесь должна быть аналогичная deserialize)
    
};


Теперь напишем рекурсию для SchemaSerializer. Начнём с простого — с конца: 

template
struct SchemaSerializer, false> {
    // мы дошли до самого низа рекурсии, но ничего не получилось.
    // без аргументов (кроме потока вывода) вызвать F::serialize
    // тоже не получается. что поделать, просто не объвляем здесь
    // ничего -- пользователь где-то накосячил, компилятор выдаст
    // ему no such function serialize(...) и будет прав.
};

template
struct SchemaSerializer, true> {
    // мы дошли до самого низа рекурсии и -- о чудо! -- F::serialize
    // можно вызвать вообще без аргументов! (не считая потока вывода)
    template // оставшиеся аргументы
    static void serialize(OS& out, TailArgs&&... targs) {
        F::serialize(out); // ну вызываем без аргументов, чо
        // (здесь можно отправить в out какой-нибудь разделитель)
        // рекурсия по числу полей понеслась дальше:
        NextSerializer::serialize(out, std::forward(targs)...);
    }
};


7f4c82c06c8b4e3081c115605b923f8b.pngЗдесь мы подошли ко второму концепту, обещанному Бендером — perfect forwarding. Нам пришли лишние аргументы (возможно, и ноль аргументов, но скорее всего нет), и мы хотим отправить их дальше, в NextSerializer::serialize. В случае шаблонов это проблема, известная как perfect forwarding problem.

Perfect forwarding


Допустим, вы хотите написать враппер вокруг шаблонной функции f, принимающей один аргумент. Например, 

template
void better_f(T arg) {
    std::cout << "I'm so much better..." << std::endl;
    f(arg);
}

Выглядит неплохо, однако, незамедлительно ломается, если f принимает на вход lvalue-ссылку T&, а не просто T: исходная функция f получит на вход ссылку на временный объект, поскольку тип Т будет вычислен (deducted) как тип без ссылки. Решение просто: 

template
void better_f(T& arg) {
    std::cout << "I'm so much better..." << std::endl;
    f(arg);
}

И опять-таки незамедлительно ломается, если f принимает аргумент по значению: в исходную функцию можно было посылать литералы и прочие rvalues, а в новую — нет.
Придётся написать оба варианта, чтобы компилятор мог выбрать и полная совместимость присутствовала в обоих случаях: 

template
void better_f(T& arg) {
    std::cout << "I'm so much better..." << std::endl;
    f(arg);
}

template
void better_f(const T& arg) {
    std::cout << "I'm so much better..." << std::endl;
    f(arg);
}

И весь этот цирк для одной функции с одним аргументом. С ростом числа аргументов число необходимых перегрузок для полноценного враппера будет расти экспоненциально.

Для борьбы с этим C++11 вводит rvalue reference и новые правила вычисления типов. Теперь можно написать просто

template
void better_f(T&& arg) {
    std::cout << "I'm so much better..." << std::endl;
    // ? . .
}

Модификатор && в контексте вычисления типов имеет особый смысл (хотя его легко спутать с обычной rvalue-ссылкой). Если функции будет передана lvalue-ссылка на объект типа type, тип T теперь будет угадан как type&; если же будет передано rvalue типа type, тип T будет угадан как type&&. Последнее, что осталось сделать для чистого perfect forwarding без лишних копирований аргументов по умолчанию — это использовать std::forward: 

template
void better_f(T&& arg) {
    std::cout << "I'm so much better..." << std::endl;
    f(std::forward(arg));
}

std::forward не трогает обычные ссылки и превращает объекты, переданные по значению, в rvalue-ссылки; таким образом, после первого же враппера дальше по цепочке врапперов (если такая есть) пойдет rvalue-ссылка вместо непосредственно объекта, избавляя от лишних копирований.

Продолжаем сериализатор


Итак, конструкция

NextSerializer::serialize(out, std::forward(targs)...);

осуществляет perfect forwarding, отправляя все «лишние» аргументы в неизменном виде дальше по цепочке сериализаторов.

Продолжим писать рекурсию для SchemaSerializer. Шаг рекурсии для can_serialize = false: 

template
struct SchemaSerializer, false>:
    // с такими аргументами вызвать F::serialize не получается --
    // попробуем взять их поменьше; если получится, мы унаследуем
    // работающую функцию serialize
    public SchemaSerializer>::Result, // все аргументы, кроме последнего
        can_serialize>::Result>::value // !!!
    > {
    // в самом классе делать нечего ¯\_(ツ)_/¯
};
Реализация вспомогательного класса Head, отрезающего от списка типов последний элемент 
template struct Head;
// нам потребуется ещё один вспомогательный класс...
template struct Concatenate;
// зато его имя говорит само за себя!
template<>
struct Concatenate<> {
    using Result = EmptyList;
};
template
struct Concatenate> {
    using Result = TypeList;
};
template
struct Concatenate, TypeList> {
    using Result = TypeList;
};
template
struct Concatenate, Ts...> {
    using Result = typename Concatenate<
        TypeList,
        typename Concatenate::Result
    >::Result;
};
// к сожалению, в С++ нельзя написать
// template
// struct Head>, так что
// приходится идти менее красивым путём
template
struct Head> {
    using Result = typename Concatenate, typename Head>::Result>::Result;
};
template
struct Head> {
    using Result = TypeList;
};
template
struct Head> {
    using Result = TypeList<>;
};
template<>
struct Head> {
    using Result = TypeList<>;
};


Шаг рекурсии для can_serialize = true: 

template
struct SchemaSerializer, true> {
    template // оставшиеся аргументы
    static void serialize(OS& out, Types... args, TailTypes&&... targs) {
        F::serialize(out, std::forward(args)...);
        // (здесь можно отправить в out какой-нибудь разделитель)
        // рекурсия по числу полей понеслась дальше:
        NextSerializer::serialize(out, std::forward(targs)...);
    }
};


fcf2da0046ed4e12bb0ddc069703e323.gifИииии… это всё! На этом наш сериализатор (в самых общих чертах) готов, и простейший код

using MyPacket = Schema<
    IntegerField,
    IntegerField,
    CharField
>;
MyPacket::serialize(std::cout, 777, 6666, 'a');

успешно выводит

7776666a

Но осталась маленькая деталь…

Вложенность


Раз наши схемы имеют такой же интерфейс, как и простые поля, почему бы не сделать схему из схем? 

using MyBigPacket = Schema;
MyBigPacket::serialize(std::cout, 11, 22, 'a', 33, 44, 55, 'b');

Компилируем ииии… получаем no matching function for call to 'serialize'. В чём же дело?

Дело в том, что Schema::serialize съедает все аргументы, что ей даны. Внешняя схема видит, что Schema::serialize можно вызвать со всеми подкинутыми аргументами, ну и вызывает. Компилятор компилирует и видит, что последние четыре аргумента остаются не у дел (candidate function template not viable: requires 1 argument, but 5 were provided), ну и сообщает об ошибке.

Преимущество SFINAE выползло здесь как недостаток. Компилятор не компилирует функцию прежде чем определить, можно её вызвать с заданными аргументами или нет; он лишь смотрит на её тип. Чтобы устранить это нежелательное поведение, мы должны заставить Schema::serialize быть невалидного типа, если ей переданы неподходящие аргументы.

Делать это будем сразу для Schema и SchemaSerializer — так проще. Предположим, что для Schema это уже сделано, и него функция serialize имеет невалидный тип при невалидных аргументах. Модифицируем некоторые специализации нашего класса SchemaSerializer: 

template
struct SchemaSerializer, true> {
    template
    static auto serialize(OS& out, TailArgs&&... targs)
        -> decltype(NextSerializer::serialize(out, std::forward(targs)...))
    {
        F::serialize(out);
        NextSerializer::serialize(out, std::forward(targs)...);
    }
};

template
struct SchemaSerializer, true> {
    template
    static auto serialize(OS& out, Types... args, TailTypes&&... targs)
        -> decltype(NextSerializer::serialize(out, std::forward(targs)...))
    {
        F::serialize(out, std::forward(args)...);
        NextSerializer::serialize(out, std::forward(targs)...);
    }
};


Что произошло? Во-первых, мы использовали новый синтаксис. Начиная с С++11, эквивалентны следующие способы задания типа результата функции: 

type func(...) { ... }
auto func(...) -> type { .. }


Зачем это нужно? В ряде случаев так удобнее. Например, мы смогли добиться желаемого, не используя снова фокус с std::declval.

А чего мы, собственно, добились? А вот чего: если рекурсия ломается и NextSerialize::serialize нельзя вызвать с предоставленными аргументами, вызов NextSerialize::serialize(out, std::forward(targs)...) по нашему предположению вызовет ошибку подстановки. Тип возвращаемого значения (а значит, и тип всей функции) вычислить будет невозможно; таким образом и вызов нашего SchemaSerializer::serialize вызовет ошибку подстановки. Ошибка будет подниматься, пока не поднимется на самый верх и не скажет пользователю, что вызвать Schema::serialize с такими-то аргументами нельзя, на этапе определения типа функции. Остаётся аналогично модифицировать специализацию Schema: 

template
struct Schema {
    // шаблонный using (снова привет, С++11!)
    template
    using Serializer = SchemaSerializer<
        F,                  // текущее поле
        Schema,  // рекурсия по числу полей
        OutputStream&,      // тип потока вывода
        TypeList, // типы всех имеющихся аргументов
        can_serialize>::value // !!!
    >;

    template<
        typename OS,      // любой поток вывода
        typename... Types // сколько угодно каких угодно аргументов
    > static auto serialize(OS& out, Types&&... args)
        -> decltype(Serializer::serialize(out, std::forward(args)...) )
    {
        Serializer::serialize(out, std::forward(args)...);
    }

    // . . .

};


Отлично! Теперь чуть менее простой код

using MyPacket = Schema<
        IntegerField,
        IntegerField,
        CharField
    >;
using MyBigPacket = Schema<
    MyPacket,
    IntegerField,
    MyPacket
>;
MyBigPacket::serialize(std::cout, 11, 22, 'a', 33, 44, 55, 'b');


2325e17b3ce54244a6c79ed72d146e52.jpgкомпилируется и радостно печатает 

1122a334455b

(главным образом потому, что у нас так и не дошли руки добавить разделитель; для тестов с std::cout можно просто впихнуть пробел, но вы же понимаете, что для абстрактного потока вывода нужно более абстрактное решение…).

Мы сделали это!

Заключение


C++ проделал большой путь, и стандарт C++11 был особенно большим шагом. Мы планомерно использовали почти все его нововведения, чтобы реализовать чистый и красивый сериализатор, чего только не поддерживающий. Он терпит произвольное число аргументов для каждого поля, терпит произвольное количество шаблонных и нешаблонных перегрузок функции serialize в каждом поле; он терпит в качестве полей другие сериализаторы; главное, на мой взгляд — он не убивает приведение типов, аккуратно донося все аргументы до их адресатов. Легко сообразить, как написать вспомогательный класс SchemaDeserializer, реализующий функцию deserialize — я опустил это за тривиальностью. Немного погружения в тему — и с помощью манипуляторов можно написать универсальные сложные поля (форматированный вывод, поле с проверкой диапазона, поле с фиксированной шириной в битах для сжатия в двоичном формате и т.д.), легко расширяемые на новые реализации потоков ввода/вывода.

Об ошибках и неточностях непременно пишите в комментарии или (лучше) в личку. Возможно, статья сможет освободиться от них и даже стать приличным учебным материалом! Спасибо за внимание.

© Habrahabr.ru