Перейти к основному содержимому

Типы TL-B

warning

Эта страница переведена сообществом на русский язык, но нуждается в улучшениях. Если вы хотите принять участие в переводе свяжитесь с @alexgton.

продвинутый уровень

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

В этом разделе анализируются сложные и нетрадиционные структуры типизированного языка двоичных данных (TL-B). Для начала мы рекомендуем сначала прочитать эту документацию, чтобы лучше ознакомиться с темой.

tlb structure

Either​

left$0 {X:Type} {Y:Type} value:X = Either X Y;
right$1 {X:Type} {Y:Type} value:Y = Either X Y;

Тип Either используется, когда возможен один из двух результирующих типов. В этом случае выбор типа зависит от показанного префиксного бита. Если префиксный бит равен 0, сериализуется левый тип, а если используется префиксный бит 1, сериализуется правый.

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

Maybe​

nothing$0 {X:Type} = Maybe X;
just$1 {X:Type} value:X = Maybe X;

Тип Maybe используется в сочетании с необязательными значениями. В этих случаях, если первый бит равен 0, само значение не сериализуется (и фактически пропускается), а если значение равно 1, оно сериализуется.

Both​

pair$_ {X:Type} {Y:Type} first:X second:Y = Both X Y;

Вариант типа Both используется только в сочетании с обычными парами, при этом оба типа сериализуются один за другим без условий.

Unary​

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

Unary представляет два основных варианта:

unary_zero$0 = Unary ~0;
unary_succ$1 {n:#} x:(Unary ~n) = Unary ~(n + 1);

Унарная сериализация​

Как правило, использовать вариант unary_zero довольно просто: если первый бит равен 0, то результатом всей унарной десериализации будет 0.

При этом вариант unary_succ более сложен, поскольку он загружается рекурсивно и имеет значение ~(n + 1). Это означает, что он последовательно вызывает себя, пока не достигнет unary_zero. Другими словами, желаемое значение будет равно количеству единиц в строке.

Например, давайте проанализируем сериализацию битовой строки 110.

Цепочка вызовов будет следующей:

unary_succ$1 -> unary_succ$1 -> unary_zero$0

Как только мы достигнем unary_zero, значение возвращается в конец сериализованной битовой строки аналогично рекурсивному вызову функции.

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

0 -> ~(0 + 1) -> ~(1 + 1) -> 2, это означает, что мы сериализовали 110 в Unary 2.

Унарная десериализация​

Предположим, у нас есть тип Foo:

foo$_  u:(Unary 2) = Foo;

Согласно вышесказанному, Foo будет десериализован в:



foo u:(unary_succ x:(unary_succ x:(unnary_zero)))

Hashmap​

Комплексный тип Hashmap используется для хранения словаря из кода смарт-контракта FunC (dict).

Следующие структуры TL-B используются для сериализации Hashmap с фиксированной длиной ключа:

hm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel ~l n)
          {n = (~m) + l} node:(HashmapNode m X) = Hashmap n X;

hmn_leaf#_ {X:Type} value:X = HashmapNode 0 X;
hmn_fork#_ {n:#} {X:Type} left:^(Hashmap n X)
           right:^(Hashmap n X) = HashmapNode (n + 1) X;

hml_short$0 {m:#} {n:#} len:(Unary ~n) {n <= m} s:(n * Bit) = HmLabel ~n m;
hml_long$10 {m:#} n:(#<= m) s:(n * Bit) = HmLabel ~n m;
hml_same$11 {m:#} v:Bit n:(#<= m) = HmLabel ~n m;

unary_zero$0 = Unary ~0;
unary_succ$1 {n:#} x:(Unary ~n) = Unary ~(n + 1);

hme_empty$0 {n:#} {X:Type} = HashmapE n X;
hme_root$1 {n:#} {X:Type} root:^(Hashmap n X) = HashmapE n X;

Это означает, что корневая структура использует HashmapE и одно из двух ее состояний: включая hme_empty или hme_root.

Пример разбора Hashmap​

В качестве примера рассмотрим следующую ячейку, заданную в двоичной форме.

1[1] -> {
  2[00] -> {
    7[1001000] -> {
      25[1010000010000001100001001],
      25[1010000010000000001101111]
    },
    28[1011100000000000001100001001]
  }
}

Эта ячейка использует тип структуры HashmapE и обладает 8-битным размером ключа, а ее значения используют числовой фреймворк uint16 (HashmapE 8 uint16). HashmapE использует 3 различных типа ключей:

1 = 777
17 = 111
128 = 777

Чтобы проанализировать этот Hashmap, нам нужно заранее знать, какой тип структуры использовать, hme_empty или hme_root. Это определяется путем определения правильного префикса. Вариант hme empty использует один бит 0 (hme_empty$0), а hme root использует один бит 1 (hme_root$1). После считывания первого бита определяется, что он равен единице (1[1]), то есть это вариант hme_root.

Теперь давайте заполним переменные структуры известными значениями, при этом начальный результат будет следующим: hme_root$1 {n:#} {X:Type} root:^(Hashmap 8 uint16) = HashmapE 8 uint16;

Здесь префикс из одного бита уже считан, но внутри {} обозначены условия, которые не нужно считывать. Условие {n:#} означает, что n — это любое число uint32, тогда как {X:Type} означает, что X может использовать любой тип.

Следующая часть, которую нужно прочитать, — это root:^(Hashmap 8 uint16), тогда как символ ^ обозначает ссылку, которую необходимо загрузить.

2[00] -> {
    7[1001000] -> {
      25[1010000010000001100001001],
      25[1010000010000000001101111]
    },
    28[1011100000000000001100001001]
  }

Инициирование анализа ветвей​

Согласно нашей схеме, это правильная структура Hashmap 8 uint16. Далее мы заполняем ее известными значениями и получаем результат:

hm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel ~l 8)
          {8 = (~m) + l} node:(HashmapNode m uint16) = Hashmap 8 uint16;

Как показано выше, теперь появились условные переменные {l:#} и {m:#}, но значения обеих переменных нам неизвестны. Также после прочтения соответствующей label становится ясно, что n участвует в уравнении {n = (~m) + l}, в этом случае мы вычисляем l и m, знак сообщает нам результирующее значение ~.

Чтобы определить значение l, мы должны загрузить последовательность label:(HmLabel ~l uint16). Как показано ниже, HmLabel имеет 3 основных структурных варианта:

hml_short$0 {m:#} {n:#} len:(Unary ~n) {n <= m} s:(n * Bit) = HmLabel ~n m;
hml_long$10 {m:#} n:(#<= m) s:(n * Bit) = HmLabel ~n m;
hml_same$11 {m:#} v:Bit n:(#<= m) = HmLabel ~n m;

Каждый вариант определяется соответствующим префиксом. В настоящее время наша корневая ячейка состоит из 2 нулевых битов, что отображается как: (2[00]). Поэтому единственным логическим вариантом является hml_short$0, который использует префикс, начинающийся с 0.

Заполните hml_short известными значениями:

hml_short$0 {m:#} {n:#} len:(Unary ~n) {n <= 8} s:(n * Bit) = HmLabel ~n 8

В этом случае мы не знаем значение n, но поскольку оно содержит символ ~, его можно вычислить. Для этого мы загружаем len:(Unary ~n), подробнее об Unary здесь.

В этом случае мы начали с 2[00], но после определения типа HmLabel только один из двух битов все еще существует.

Поэтому мы загружаем его и видим, что его значение равно 0, что означает, что он явно использует вариацию unary_zero$0. Это означает, что значение n с использованием вариации HmLabel равно нулю.

Далее необходимо завершить последовательность вариаций hml_short, используя вычисленное значение n:

hml_short$0 {m:#} {n:#} len:0 {n <= 8} s:(0 * Bit) = HmLabel 0 8

Оказывается, у нас есть пустой HmLabel, обозначенный как, s = 0, поэтому загружать нечего.

Далее мы дополняем нашу структуру вычисленным значением l следующим образом:

hm_edge#_ {n:#} {X:Type} {l:0} {m:#} label:(HmLabel 0 8)
          {8 = (~m) + 0} node:(HashmapNode m uint16) = Hashmap 8 uint16;

Теперь, когда мы вычислили значение l, мы также можем вычислить m, используя уравнение n = (~m) + 0, т. е. m = n - 0, m = n = 8.

После определения всех неизвестных значений теперь можно загрузить node:(HashmapNode 8 uint16).

Что касается HashmapNode, у нас есть варианты:

hmn_leaf#_ {X:Type} value:X = HashmapNode 0 X;
hmn_fork#_ {n:#} {X:Type} left:^(Hashmap n X)
           right:^(Hashmap n X) = HashmapNode (n + 1) X;

В этом случае мы определяем вариант не с помощью префикса, а с помощью параметра. Это означает, что если n = 0, то правильным конечным результатом будет либо hmn_leaf, либо hmn_fork. В этом примере результат равен n = 8 (вариация hmn_fork). Мы используем вариацию hmn_fork и заполняем известные значения:

hmn_fork#_ {n:#} {X:uint16} left:^(Hashmap n uint16)
           right:^(Hashmap n uint16) = HashmapNode (n + 1) uint16;

После ввода известных значений мы должны вычислить HashmapNode (n + 1) uint16. Это означает, что полученное значение n должно быть равно нашему параметру, т. е. 8. Чтобы вычислить локальное значение n, нам нужно вычислить его с помощью следующей формулы: n = (n_local + 1) -> n_local = (n - 1) -> n_local = (8 - 1) -> n_local = 7.

hmn_fork#_ {n:#} {X:uint16} left:^(Hashmap 7 uint16)
           right:^(Hashmap 7 uint16) = HashmapNode (7 + 1) uint16;

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

Анализ загруженных значений Hashmap​

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

Конечным результатом снова становится hm_edge, и следующим шагом будет заполнение последовательности правильными известными значениями следующим образом:

hm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel ~l 7)
          {7 = (~m) + l} node:(HashmapNode m uint16) = Hashmap 7 uint16;

Далее ответ HmLabel загружается с использованием вариации HmLabel, поскольку префикс равен 10.

hml_long$10 {m:#} n:(#<= m) s:(n * Bit) = HmLabel ~n m;

Теперь давайте заполним последовательность:

hml_long$10 {m:#} n:(#<= 7) s:(n * Bit) = HmLabel ~n 7;

Новая конструкция - n:(#<= 7), ясно обозначает размерное значение, которое соответствует числу 7, которое на самом деле является log2 от числа + 1. Но для простоты мы могли бы посчитать количество бит, необходимых для записи числа 7. Соответственно, число 7 в двоичной форме равно 111; поэтому требуется 3 бита, что означает значение для n = 3.

hml_long$10 {m:#} n:(## 3) s:(n * Bit) = HmLabel ~n 7;

Далее мы загружаем n в последовательность с конечным результатом 111, который, как мы отметили выше = 7 по совпадению. Затем мы загружаем s в последовательность, 7 бит - 0000000. Помните, s является частью ключа.

Далее мы возвращаемся к началу последовательности и заполняем полученное l:

hm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel 7 7)
          {7 = (~m) + 7} node:(HashmapNode m uint16) = Hashmap 7 uint16;

Затем мы вычисляем значение m, m = 7 - 7, поэтому значение m = 0. Поскольку значение m = 0, структура идеально подходит для использования с HashmapNode:

hmn_leaf#_ {X:Type} value:X = HashmapNode 0 X;

Далее мы подставляем наш тип uint16 и загружаем значение. Оставшиеся 16 бит 0000001100001001 в десятичной форме составляют 777, следовательно, наше значение.

Теперь давайте восстановим ключ, мы должны объединить упорядоченный список всех частей ключа, которые были вычислены ранее. Каждая из двух связанных частей ключа объединяется одним битом на основе того, какие ветви типа используются. Для правой ветви добавляется бит "1", а для левой ветви добавляется бит "0". Если выше существует полная HmLabel, то ее биты добавляются к ключу.

В этом случае конкретно из HmLabel 0000000 берутся 7 бит, а перед последовательностью нулей добавляется бит "1", поскольку значение было получено из правой ветви. Конечный результат составляет 8 бит в общей сложности или 10000000, что означает, что значение ключа равно 128.

Другие типы Hashmap​

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

HashmapAugE​

ahm_edge#_ {n:#} {X:Type} {Y:Type} {l:#} {m:#}
  label:(HmLabel ~l n) {n = (~m) + l}
  node:(HashmapAugNode m X Y) = HashmapAug n X Y;

ahmn_leaf#_ {X:Type} {Y:Type} extra:Y value:X = HashmapAugNode 0 X Y;

ahmn_fork#_ {n:#} {X:Type} {Y:Type} left:^(HashmapAug n X Y)
  right:^(HashmapAug n X Y) extra:Y = HashmapAugNode (n + 1) X Y;

ahme_empty$0 {n:#} {X:Type} {Y:Type} extra:Y
          = HashmapAugE n X Y;

ahme_root$1 {n:#} {X:Type} {Y:Type} root:^(HashmapAug n X Y)
  extra:Y = HashmapAugE n X Y;

Главное отличие между HashmapAugE и обычным Hashmap заключается в наличии поля extra:Y в каждом узле (а не только в листьях со значениями).

PfxHashmap​

phm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel ~l n)
           {n = (~m) + l} node:(PfxHashmapNode m X)
           = PfxHashmap n X;

phmn_leaf$0 {n:#} {X:Type} value:X = PfxHashmapNode n X;
phmn_fork$1 {n:#} {X:Type} left:^(PfxHashmap n X)
            right:^(PfxHashmap n X) = PfxHashmapNode (n + 1) X;

phme_empty$0 {n:#} {X:Type} = PfxHashmapE n X;
phme_root$1 {n:#} {X:Type} root:^(PfxHashmap n X)
            = PfxHashmapE n X;

Главное отличие между PfxHashmap и обычным Hashmap заключается в его способности хранить ключи разной длины из-за наличия узлов phmn_leaf$0 и phmn_fork$1.

VarHashmap​

vhm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel ~l n)
           {n = (~m) + l} node:(VarHashmapNode m X)
           = VarHashmap n X;
vhmn_leaf$00 {n:#} {X:Type} value:X = VarHashmapNode n X;
vhmn_fork$01 {n:#} {X:Type} left:^(VarHashmap n X)
             right:^(VarHashmap n X) value:(Maybe X)
             = VarHashmapNode (n + 1) X;
vhmn_cont$1 {n:#} {X:Type} branch:Bit child:^(VarHashmap n X)
            value:X = VarHashmapNode (n + 1) X;

// nothing$0 {X:Type} = Maybe X;
// just$1 {X:Type} value:X = Maybe X;

vhme_empty$0 {n:#} {X:Type} = VarHashmapE n X;
vhme_root$1 {n:#} {X:Type} root:^(VarHashmap n X)
            = VarHashmapE n X;

Главное отличие VarHashmap от обычного Hashmap заключается в его способности хранить ключи разной длины из-за наличия узлов vhmn_leaf$00 и ​​vhmn_fork$01. Кроме того, VarHashmap может формировать общий префикс значения (дочернюю карту) за счет vhmn_cont$1.

BinTree​

bta_leaf$0 {X:Type} {Y:Type} extra:Y leaf:X = BinTreeAug X Y;
bta_fork$1 {X:Type} {Y:Type} left:^(BinTreeAug X Y)
           right:^(BinTreeAug X Y) extra:Y = BinTreeAug X Y;

Механизм генерации ключей двоичного дерева работает аналогично стандартизированной структуре Hashmap, но не использует метки и включает только префиксы ветвей.

Адреса​

Адреса TON формируются с помощью механизма хеширования sha256 с использованием структуры TL-B StateInit. Это означает, что адрес можно вычислить до развертывания сетевого контракта.

Сериализация​

Стандартные адреса, такие как EQBL2_3lMiyywU17g-or8N7v9hDmPCpttzBPE2isF2GTzpK4, используют URI base64 для кодирования байтов. Обычно они имеют длину 36 байтов, последние 2 из которых представляют собой контрольную сумму crc16, рассчитанную с помощью таблицы XMODEM, в то время как первый байт представляет флаг, а второй представляет рабочую цепочку. 32 байта в середине представляют собой данные самого адреса (также называемые AccountID), часто представленные в схемах, таких как int256.

Пример декодирования

Ссылки​

Вот ссылка на оригинальную статью Олега Баранова.