Содержание

Двоичная сериализация данных

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

Общие определения

Для наших целей можно отождествить тип с множеством его (сериализованных) значений, понимаемых как строки (конечные последовательности) 32-битных чисел (передаваемых в формате little-endian).

Итак:

  • Алфавит (A) — в данном случае — множество 32-битных чисел (обычно знаковых, т.е. от -2^31 до 2^31 - 1).
  • Значение — в данном случае то же самое, что строка в алфавите A, т.е. конечная (возможно, пустая) последовательность 32-битных чисел. Множество всех таких последовательностей обозначается A*.
  • Тип — для наших целей то же самое, что и множество допустимых значений данного типа, т.е. некоторое подмножество T в A*, являющееся префикс-кодом (т.е. никакой элемент из Т не может быть префиксом никакого другого). Таким образом, в любой последовательности из A* можно выделить не более одного префикса, принадлежащего T.
  • Значение типа T — любая последовательность (значение), принадлежащая T как подмножеству A*.
  • Совместимые типы — типы T и T', не пересекающиеся как подмножества A*, причем такие, что объединение T и T' является префикс-кодом.
  • Согласованная система типов — конечный или бесконечный набор типов T_1, …, T_n, …, такой, что любые два типа из данного набора совместимы.
  • Тип данных — то же, что и тип в смысле приведенного выше определения.
  • Функциональный тип — тип, описывающий функцию; не является типом в смысле приведенного выше определения. Мы сначала игнорируем существование функциональных типов и описываем только типы данных; однако на самом деле функциональные типы позже будут вложены в некоторое расширение данной системы с помощью т.н. временных комбинаторов.

Комбинаторы, конструкторы, составные типы данных

  • Комбинатор — функция, принимающая аргументы некоторых типов и возвращающая значение некоторого другого типа. Мы обычно рассматриваем комбинаторы, типы аргументов и результата которых являются типами данных (а не функциональными типами).
  • Арность (комбинатора) — неотрицательное целое число, количество аргументов комбинатора.
  • Название комбинатора — идентификатор, начинающийся с маленькой латинской буквы, однозначно идентифицирующий комбинатор.
  • Номер комбинатора или имя комбинатора — 32-битное число (т.е. элемент A), однозначно идентифицирующее комбинатор. Чаще всего является CRC32 от строки с описанием комбинатора без завершающей точки с запятой, с одним пробелом между соседними лексемами. Всегда попадает в диапазон 0x01000000..0xffffff00. Верхние 256 значений зарезервированы для т.н. временных комбинаторов, используемых для передачи функций. Мы часто обозначаем имя комбинатора combinator с помощью одинарных кавычек: ‘*combinator*’.
  • Описание комбинатора — строка вида combinator_name type_arg_1 ... type_arg_N = type_res;, где N - арность комбинатора, type_arg_i — тип i-ого аргумента (вернее, строка с названием комбинатора), type_res — тип значения комбинатора.
  • Конструктор — комбинатор, который не может быть вычислен (редуцирован). Используется для представления составных типов данных. Например, комбинатор int_tree с описанием int_tree IntTree int IntTree = IntTree, наряду с комбинатором empty_tree = IntTree, может быть использован для определения составного типа данных “IntTree”, значениями которого являются бинарные деревья с целыми числами в узлах.
  • Функция (функциональный комбинатор) — комбинатор, который может быть вычислен (редуцирован), при условии, что дано нужное количество аргументов нужного типа. Значение вычисления - некоторое выражение, состоящее только из конструкторов и значений базовых типов.
  • Нормальная форма — выражение, состоящее только из конструкторов и значений базовых типов; то, что обычно является результатом вычисления функции.
  • Название типа — идентификатор, как правило, начинающийся с большой латинской буквы, однозначно идентифицирующий тип.
  • Номер типа или имя типа — 32-битное число, однозначно идентифицирующее тип; обычно является суммой CRC32 описаний конструкторов типа.
  • Описание (составного) типа T — набор описаний всех конструкторов, принимающих значения типа T. Обычно записывается в виде текста, каждая строка которого содержит описание одного конструктора. Например, вот описания типа IntTree:
    int_tree IntTree int IntTree = IntTree;
    empty_tree = IntTree;
  • Полиморфный тип — тип, описание которого содержит параметры (*переменные типов*), заменяющие реальные типы; примерно соответствует шаблонам в C++. Вот описание типа List alpha, где List — это полиморфный тип арности 1 (т.е. зависящий от одного аргумента), alpha — переменная типа, появляющаяся как необязательный параметр конструкторов (в фигурных скобках):
    cons {alpha:Type} alpha (List alpha) = List alpha;
    nil {alpha:Type} = List alpha;
  • Значение (составного) типа T — любая последовательность из A* вида constr_num arg1 ... argN, где constr_num — номер некоторого конструктора C, принимающего значение типа T, arg_i — значение типа T_i, который является типом i-ого аргумента конструктора C. Предположим, например, что комбинатор int_tree имеет номер 17, а комбинатор empty_tree - 239. Тогда значением типа IntTree является, например, 17 17 239 1 239 2 239, которое лучше записывать в виде 'int_tree' 'int_tree' 'empty_tree' 1 'empty_tree' 2 'empty_tree'; с точки зрения языка высокого уровня это int_tree (int_tree (empty_tree) 1 (empty_tree)) 2 (empty_tree) : IntTree.
  • Схема — это совокупность описаний всех (составных) типов данных. Используется для задания некоторой согласованной системы типов.

Одетые и голые типы

  • Одетый тип (boxed type) — тип, любое значение которого начинается с номера конструктора. Поскольку любой конструктор обладает однозначно определенным типом значения, первое число в значении любого одетого типа однозначно определяет его тип. Это гарантирует, что всевозможные одетые типы в совокупности образуют согласованную систему типов. Название одетого типа всегда начинается с большой буквы.
  • Голый тип (bare type) — тип, значения которого не содержащий номера конструктора, который вместо этого подразумевается. Название голого типа совпадает с названием подразумеваемого конструктора (а значит, начинается с маленькой буквы), перед которым может быть дописан знак процента (%). Кроме того, если X — одетый тип, имеющий не более одного конструктора, то %X означает соответствующий голый тип. Значения голого типа совпадают с множеством последовательностей чисел, получающихся откидыванием первого числа (т.е. номера внешнего конструктора) из множества значений соответствующего одетого типа (который является типом результата выбранного конструктора), начинающихся с номера выбранного конструктора. Например, 3 4 является значением голого типа int_couple, определенного с помощью int_couple int int = IntCouple. Соответствующим одетым типом является IntCouple; если номером конструктора int_couple является 404, то 404 3 4 — это значение одетого типа IntCouple, соответствующее значению голого типа int_couple (он же %int_couple и %IntCouple; последняя форма предпочтительнее с концептуальной точки зрения, но длиннее).

С концептуальной точки зрения следовало бы везде использовать только одетые типы. Однако из соображений производительности и компактности приходится использовать голые типы (например, массив из 10000 голых int‘ов занимает 40000 байтов, а из одетых Int’ов - вдвое больше; поэтому при передаче, скажем, большого массива целочисленных идентификаторов выгоднее использовать тип Vector int, а не Vector Int). Кроме того, все базовые типы (int, long, double, string) — голые.

Если одетый тип является полиморфным типовой арности r, то это же верно и для любого голого типа, полученного из него. Иначе говоря, если определить intCouple {alpha:Type} int alpha = IntCouple alpha, то после этого в описаниях комбинаторов (а значит, конструкторов и типов) идентификатор intCouple также является полиморфным голым типом арности 1. Записи intCouple X, %(IntCouple X) и %IntCouple X эквивалентны.

Базовые типы

Базовые типы присутствуют как и в голом (code, long, double, string), так и в одетом (Int, Long, Double, String) вариантах. Названия их конструкторов совпадают с названиями соответствующих голых типов. Псевдоописания выглядят так:

int ? = Int;
        long ? = Long;
        double ? = Double;
        string ? = String;

Соответственно, например, номер конструктора int — это CRC32 от строки "int ? = Int".

Значения голого типа int — это в точности все одноэлементные последовательности, т.е. числа от -2^31 до 2^31-1, которые в данном случае представляют сами себя. Значения типа long — это двухэлементные последовательности, представляющие собой 64-битные числа со знаком (снова little-endian). Значения типа double — это снова двухэлементные последовательности, содержащие 64-битные вещественные числа в стандартном формате double. Наконец, значения типа string выглядят по-разному в зависимости от длины передаваемой строки L. Если L <= 253, то кодируется один байт L, затем L байтов строки, затем от 0 до 3 символов с кодом 0, чтобы общая длина значения делилась на 4, после чего все это интерпретируется как последовательность из int(L/4)+1 32-битных чисел. Если же L>=254, то кодируется байт 254, затем — 3 байта с длиной строки L, затем — L байтов строки, затем - от 0 до 3 нулевых байтов выравнивания.

Псевдотип Object

Псевдотип Object — это “тип”, значениями которого могут быть значения любых одетых типов схемы. Это дает возможность быстро определять типы вроде список чего попало, не используя для этого полиморфные типы. Лучше не злоупотреблять этой возможностью, т.к. она приводит к применению динамической типизации. Тем не менее, структуры данных, привычные по PHP и JSON, довольно сложно представить без применения псевдотипа Object.

Встроенные составные типы: вектора и ассоциативные массивы

Полиморфный псевдотип Vector t — это “тип”, значение которого - последовательность значений любого типа t, одетого или голого.

vector {t:Type} # [ t ] = Vector t;

При сериализации используется всегда используется один и тот же конструктор “vector” (константа 0x1cb5c415 = crc32("vector t:Type # [ t ] = Vector t"), не зависящий от конкретного значения переменной типа t. Значением типа Vector t является номер соответствующего конструктора, за которым следует число N — количество элементов в векторе и далее — N значений типа t. Значение необязательного параметра t не участвует в сериализации, так как он выводится из типа результата (всегда известного до десериализации).

Полиморфные псевдотипы IntHash t и StrHash t представляют собой ассоциативные массивы, отображающие целочисленные или строковые ключи в значения типа t. Фактически являются вектором, содержащим голые пары (int,t) или (string,t):

coupleInt {t:Type} int t = CoupleInt t;
        intHash {t:Type} (vector %(CoupleInt t)) = IntHash t;
        coupleStr {t:Type} string t = CoupleStr t;
        strHash {t:Type} (vector %(CoupleStr t)) = StrHash t;

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

Ключи могут быть отсортированы, а могут идти в каком-то другом порядке (как в PHP-массивах). Для случая ассоциативных массивов с отсортированными ключами используется синоним IntSortedHash или StrSortedHash:

intSortedHash {t:Type} (intHash t) = IntSortedHash t;
        strSortedHash {t:Type} (strHash t) = StrSortedHash t;

Конструкторы полиморфных типов

Номер конструктора полиморфного типа не зависит от того, к каким именно типам применяется полиморфный тип. При его вычислении необязательные параметры (обычно содержащие переменные типа и заключённые в фигурные скобки) делаются обязательными (убираются фигурные скобки) и, кроме того, удаляются все круглые скобки. Таким образом,

vector {t:Type} # [ t ] = Vector t;

соответствует номер конструктора crc32("vector t:Type # [ t ] = Vector t") = 0x1cb5c415. При (де)сериализации конкретные значения необязательной переменной t выводятся из всегда известного типа результата (т.е. сериализуемого или десериализуемого объекта) и никогда не сериализуются явно.

Раньше для каждого полиморфного типа было нужно знать, к каким именно переменным типам он будет применяться. Для этого в описании системы типов использовались строки вида

polymorphic_type_name type_1 ... type_N;

Например,

Vector int;
        Vector string;
        Vector Object;

Сейчас они игнорируются.

См. также полиморфизм в TL.

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

Названия полей

Предположим, нам надо описывать пользователей с помощью троек, состоящих из одного целого числа (идентификатора пользователя) и двух строк (имени и фамилии). Нужная структура данных — это тройка int, string, string, которая может быть объявлена следующим образом:

user int string string = User;

С другой стороны, группа может описываться похожей тройкой, состоящей из идентификатора группы, ее названия и описания:

group int string string = Group;

Для того, чтобы было понятно, чем отличается User от Group, удобно задать для некоторых или для всех полей некоторые названия:

user id:int first_name:string last_name:string = User;
        group id:int title:string description:string = Group;

Если потом понадобится расширить тип User , добавив в него записи с некоторым дополнительным полем, то это можно сделать так:

userv2 id:int unread_messages:int first_name:string last_name:string in_groups:vector int = User;

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

Комментарии