Хабрахабр

[Из песочницы] Анализ языка VKScript: JavaScript, ты ли это?

Семантика этого языка кардинально отличается от семантики JavaScript. VKScript — это не JavaScript. заключение. См.

По сути, VKScript — это аналог GraphQL, используемого в Facebook для тех же целей. VKScript — скриптовый язык программирования, похожий на JavaScript, который используется в методе execute API ВКонтакте, который дает клиентам возможность загружать ровно ту информацию, которая им нужна.

Сравнение GraphQL и VKScript:

Описание VKScript со страницы метода в документации VK API (единственная официальная документация по языку):

Поддерживаются:

  • арифметические операции
  • логические операции
  • создание массивов и списков ([X,Y])
  • parseInt и parseDouble
  • конкатенация (+)
  • конструкция if
  • фильтр массива по параметру (@.)
  • вызовы методов API, параметр length
  • циклы, используя оператор while
  • методы Javascript: slice, push, pop, shift, unshift, splice, substr, split
  • оператор delete
  • присваивания элементам маcсива, например: row.user.action = «test»;
  • поиск в массиве или строке — indexOf, например: «123».indexOf(2) = 1, [1, 2, 3].indexOf(3) = 2. Возвращает -1, если элемент не найден.

В данный момент не поддерживается создание функций.

Но так ли это? В приведенной документации указано, что «планируется совместимость с ECMAScript». Попробуем разобраться, как этот язык работает изнутри.

  1. Виртуальная машина VKScript
  2. Семантика объектов VKScript
  3. Заключение

Правильно — отправлять запросы к публичному endpoint'у и анализировать ответы. Как вообще можно анализировать программу при отсутствии локальной копии? Попробуем, например, выполнить такой код:

while(1);

Это говорит о том, что в реализации языка присутствует лимит на количество произведенных действий. Мы получаем ошибку Runtime error occurred during code invocation: Too many operations. Попробуем установить точное значение лимита:

var i = 0;
while(i < 1000) i = i + 1;

  • Runtime error occurred during code invocation: Too many operations.

var i = 0;
while(i < 1000) i = i + 1;

  • — код успешно выполнился.

Но, в то же время, понятно, что такой цикл, скорее всего, не является «унитарной» операцией. Таким образом, лимит на количество операций — порядка 1000 «холостых» циклов. Попробуем найти операцию, которая не разделяется компилятором на несколько более мелких.

Однако после добавления к коду с i < 999 50 символов ;, превышения лимита не происходит. Самым очевидным кандидатом на роль такой операции является так называемый empty statement (;). Это означает, что либо empty statement выбрасывается компилятором и не тратит операции, либо одна итерация цикла занимает больше 50 операций (что, скорее всего, не так).

Попробуем добавить несколько таких выражений в наш код: Следующее, что приходит в голову после ; — вычисление какого-нибудь простого выражения (например, так: 1;).

var i = 0;
while(i < 999) i = i + 1;
1; // так еще работает
1; // при добавлении этой строки получаем ошибку "Too many operations"

Это подтверждает гипотезу о том, что empty statement не тратит инструкций. Таким образом, 2 операции 1; тратят больше операций, чем 50 операция ;.

Несложно заметить, что на каждую итерацию приходится 5 дополнительных 1;, следовательно, одна итерация цикла тратит в 5 раз больше операций, чем одна операция 1;. Попробуем уменьшать количество итераций цикла и добавлять дополнительные 1;.

Например, добавление унарного оператора ~ не требует вычисления дополнительных выражений, а сама операция выполняется на процессоре. Но нет ли еще более простой операции? Логично предположить, что добавление в выражение этой операции увеличивает общее количество операций на 1.

Добавим в наш код этот оператор:

var i = 0;
while(i < 999) i = i + 1;
~1;

Следовательно, 1; действительно не является унитарным оператором. И да, один такой оператор мы добавить можем, а еще одно выражение 1; — уже нет.

Одна итерация оказалась эквивалентна 10 унитарным операциям ~, следовательно, выражение 1; тратит 2 операции. Аналогично оператору 1;, будем уменьшать количество итераций цикла и добавлять операторы ~.

Будем считать, что лимит составляет точно 10000 операций. Заметим, что лимит составляет примерно 1000 итераций, то есть примерно 10000 единичных операций.

Измерение количества операций в коде

Для этого нужно добавить этот код после цикла и добавлять/удалять итерации, операторы ~ или всю последнюю строку целиком, пока ошибка Too many operations не исчезнет. Заметим, что теперь мы можем измерять количество операций в любом коде.

Некоторые результаты измерений:

Определение типа виртуальной машины

Есть два более-менее правдоподобных варианта: Для начала нужно понять, по какому принципу работает интерпретатор VKScript.

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

Рассмотрим выражения (true? Несложно понять, что в VKScript используется второй вариант. 1:1); (4 операции). 1:1); (5 операций) и (false? Аналогичный эффект наблюдается в if/else с разным условием. В случае с последовательным выполнением инструкций дополнительная операция объясняется переходом, который «обходит» неверный вариант, а в случае с рекурсивным обходом AST оба варианта для интерпретатора равноценны.

Создание новой переменной обходится всего в 1 операцию, а присвоение в существующую — в 3? Также стоит обратить внимание на пару i = 1; (3 операции) и var j = 1; (1 операция). То, что создание переменной обходится в 1 операцию (и то, это, скорее всего, операция загрузки константы), говорит о двух вещах:

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

Использованием стека также объясняется то, что выражение var j = 1; выполняется быстрее, чем выражение 1;: последнее выражение тратит дополнительную инструкцию на то, чтобы убрать со стека вычисленное значение.

Определение точного значения лимита

Заметим, что цикл var j=0;while(j < 1)j=j+1; (15 операций) — это уменьшенная копия цикла, который использовался для измерений:

Лимит составляет 9998 инструкций? Стоп, что? Мы явно что-то упускаем...

Это легко объясняется: компилятор добавляет в конце кода неявный return null;, и при добавлении своего return'а он не выполняется. Заметим, что код return 1; выполняется, согласно измерениям, за 0 инструкций. Считая, что лимит равен 10000, делаем вывод, что операция return null; занимает 2 инструкции (вероятно, это что-то вроде push null; return;).

Вложенные блоки кода

Проведем еще несколько измерений:

Обратим внимание на следующие факты:

  • При добавлении переменной в блок тратится одна дополнительная операция.
  • При «объявлении переменной заново» второе объявление отрабатывает как обычное присваивание.
  • Но при этом переменная внутри блока снаружи не видна (см. последний пример).

Соответственно, когда локальных переменных нет, удалять ничего не нужно. Несложно понять, что лишняя операция тратится на удаление со стека локальных переменных, объявленных в блоке.

Можно заметить, что создание строки и пустого массива/объекта занимает 2 операции, так же как и загрузка числа. Проанализируем полученные результаты. Это говорит о том, что непосредственно создание объекта происходит за одну операцию. При создании непустого массива или объекта добавляются операции, потраченные на загрузку элементов массива/объекта. При этом на загрузку названий свойств время не тратится, следовательно, их загрузка является частью операции создания объекта.

А вот последние три примера выглядят интересно. С вызовом метода API все тоже весьма банально — загрузка единицы, собственно вызов метода, pop результата (можно заметить, что название метода обрабатывается как единое целое, а не как взятие свойств).

  • "".substr(0, 0); — загрузка строки, загрузка нуля, загрузка нуля, pop результата. На вызов метода почему-то приходится 2 инструкции (почему — см. далее).
  • var j={};j.x=1; — создание объекта, загрузка объекта, загрузка единицы, pop единицы после присваивания. Опять-таки, на присваивание приходится 2 инструкции.
  • var j={x:1};delete j.x; — загрузка единицы, создание объекта, загрузка объекта, удаление. На операцию удаления приходится 3 инструкции.

Числа

Проведем простой тест: Вернемся к исходному вопросу: VKScript — это подмножество JavaScript или другой язык?

return 1000000000 + 2000000000;

{"response": -1294967296};

Также несложно убедиться, что деление на 0 приводит к ошибке, а не возвращает Infinity. Как мы видим, целочисленное сложение приводит к переполнению, несмотря на то, что в JavaScript нет целых чисел как таковых.

Объекты

return {};

{"response": []}

Мы возвращаем объект и получаем массив? Стоп, что? В языке VKScript массивы и объекты представлены одним типом, в частности, пустой объект и пустой массив это одно и тоже. Да, так и есть. При этом свойство length у объекта работает и возвращает количество свойств.

Интересно посмотреть, как поведут себя методы списка, если вызвать их на объекте?

return {a:1, b:2, c:3}.pop();

3

Поменяем порядок свойств: Метод pop возвращает последнее объявленное свойство, что, впрочем, логично.

return {b:1, c:2, a:3}.pop();

3

Попробуем использовать числовые свойства: Видимо, объекты в VKScript запоминают порядок присвоения свойств.

return {'2':1,'1':2,'0':3}.pop();

3

Теперь посмотрим, как работает push:

var a = {'2':'a','1':'b','x':'c'};
a.push('d');
return a;

{"1": "b", "2": "a", "3": "d", "x": "c"};

«Дыры» при этом не заполняются. Как видим, метод push сортирует численные ключи и добавляет новое значение после последнего численного ключа.

Теперь попробуем объединить два этих метода:

var a = {'2':'a','1':'b','x':'c'};
a.push(a.pop());
return a;

{"1": "b", "2": "a", "3": "c", "x": "c"};

Однако, если мы разнесем push и pop в разные строки, баг пропадет. Как мы видим, элемент не удалился из массива. We need to go deeper!

Хранение объектов

var x = {};
var y = x;
x.y = 'z';
return y;

{"response": []}

Теперь понятно странное поведение строки a.push(a.pop()); — видимо, старое значение массива сохранилось на стеке, откуда потом и было взято. Как выяснилось, объекты в VKScript хранятся по значению, в отличие от JavaScript.

Видимо, «лишняя» инструкция при вызове метода предназначена именно для записи изменений обратно в объект. Однако как тогда данные сохраняются в объект, если метод его изменяет?

Методы массивов

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть