tech.ru.md

Оператор template

Синтаксис

template(match) body

где

• match это произвольное выражение
• body либо одиночный statement, либо блок { ... }

Семантика

Программа на XJST содержит произвольный JavaScript код (определения и инициализация глобальных переменных, функций и т.п.), а также некоторое количество шаблонов (операторов template). В результате компиляции получается функция, семантика которой состоит в том, что шаблоны перебираются начиная от нижнего вверх, и выполняется тело первого шаблона, чей match оказался истинным. Иными словами, шаблоны расположенные ниже имеют больший приоритет. Несмотря на простоту этого определения, оптимизированный код, генерируемый компилятором, намного сложнее, чем просто последовательность else if-ов.

Компиляция

Предварительная обработка

Хотя формально по синтаксису match в операторе template может быть произвольным выражением, перед компиляцией все match-и приводятся к каноническому виду

p1 === c1 && p2 === c2 && ...

где pN произвольные выражения, а cN константы. Для этого все выражения e, не соответствующие каноническому виду, заменяются на !e === false. Важно отметить, что значение undefined не является константой (это неопределенная переменная).

Ниже мы будем называть pN предикатным выражением, а равенство pN === cN элементарным предикатом. Так в каноническом виде match каждого шаблона состоит из одного или более элементарных предикатов.

После приведения match-ей к каноническому виду компилятор просматривает все шаблоны и собирается множество всех используемых в них различных предикатных выражений pN, и для каждого из них запоминается множество различных cN, с которыми оно сравнивается хотя бы в одном элементарном предикате. Выражения считаются одинаковыми, если после JavaScript парсера и последующей сериализации получаются равные строки. Другими словами никакого специального анализа выражений не производится, например, a+b и b+a считаются разными выражениями. Но по крайней мере игнорируются различия в пробельных символах, лишних скобках, разница между x['a'] и x.a и т.п.

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

Построение полного дерева программы

После предварительного анализа шаблонов запускается основной рекурсивный алгоритм. Состояние этого алгоритма содержит

• какой шаблон сейчас обрабатывается, и какой элементарный предикат в нем
• кеш значений предикатных выражений

Алгоритм стартует с нижнего шаблона, первого элементарного предиката в нем, и с пустым кешом. Шаг алгоритма состоит в следующем:

• Мы берем предикатное выражение pN текущего элементарного предиката, и ищем его в кеше.
  • Если нашли, то смотрим, совпадает ли значение в кеше с константой cN в нашем элементарном предикате.
    • Если совпадает, то рекурсивно переходим к обработке следующего элементарного предиката в том же шаблоне. Если это последний элементарный предикат в шаблоне, но генерируем в результирующую программу тело этого шаблона.
    • Если не совпадает, то рекурсивно переходим к обработке первого элементарного предиката следующего шаблона.
  • Если в кеше нет значения для нашего предикатного выражения, то мы генерируем в результирующую программу switch с ветками case для всех возможных для этого pN значений констант cN, и веткой default. На каждой из этих веток алгоритм рекурсивно вызывается для того же самого шаблона и элементарного предиката в нем, но при этом в кеш записывается то значение для pN которое было на обрабатываемой case ветке, либо undefined для ветки default.

После того как эта рекурсия завершится, мы получим дерево.

• В узлах этого дерева находятся операторы switch(pN) для различных предикатных выражений pN встреченных в шаблонах.
• Ветками дерева являются операторы default и case cN для различных cN.
• На листьях дерева находятся тела шаблонов.

Построенное дерево представляет собой функцию (apply), выполняющую однократную операцию матчинга, то есть выбора шаблона, подходящего для данного контекста. Она не содержит зацикливаний, только несколько разветвлений с последующим выполнением тела найденного шаблона. Но при этом, как правило в теле многих шаблонов будет рекурсивный вызов функции apply (а, возможно, и не один) с каким-то измененным контекстом. Для эффективного управления контекстом см. оператор local.

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

Поиск общих поддеревьев

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

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

Сериализация в JavaScript

Посколько в языке JavaScript нет оператора goto, выписать на нем программу, заданную в виде графа, пусть даже ациклического, довольно непросто. Но на самом деле возможно. Основная идея состоит в использовании оператора break lN, где lN метка некоторого блока. В сущности любой переход "вниз" можно осуществить с помощью оператора break, если подходящим образом задать отмеченный меткой блок. Переходы "вверх" можно производить через оператор continue lN, но для сериализации ациклического графа нам это не понадобится.

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

Каждой точке слияния мы сопоставим блок с меткой. В самом начале генерируемой программы откроем все эти блоки в порядке, обратном номерам точек слияния. Дальше начнем выписывать программу начиная от корня дерева, встречающиеся операторы switch, case, dafault, тела шаблонов. Каждый раз когда будем натыкаться на точку слияния, не будем рекурсивно обрабатывать то что ниже неё, а вместо этого сгенерируем оператор *break lN соответствующий номеру этой точки. Когда этот обход закончится, мы закроем самый внутренний блок, соответствующий точке слияния с номером 1. И под ним тем же самым способом сгенерируем часть программы, стартуя уже не от корня дерева, а от первой точки слияния. И так далее, пока все блоки не будут закрыты, и все точки слияния обработаны.

Идеи на будущее

• Специализация функции apply. То есть чтобы при рекурсивных вызовах управление переходило не в общую функцию, а в специализированную версию. Для начала надо сделать apply новым ключевым словом, чтобы оптимизатор видел рекурсивные вызовы.
  • Специализация по результатам профилирования. Основная идея: удалять ветки, в которые при тестовых прогонах ни разу не зашли, и мониторить что в будущем в них тоже не захотят зайти.
  • "Честная" специализация. Метаинтерпретировать тела шаблонов и доносить информацию внутрь вызовов apply. Для начала простейшие частные случаи типа local(pN = cN) apply; и подобное.
• Разрешить из тела шаблона делать "continue", то есть продолжать перебирать шаблоны, даже если один match уже найден.
• Идея, смежная с предыдущей: вложенные шаблоны.
• Поддержка == в канонической форме match-ей. Сейчас x == 5 компилируется в if(x == 5), а можно в switch(Number(x)) { case 5: ... }.
• Удобный синтаксис для генерации текста (html-я в частности) из шаблонов. + медленно, push громоздко, и то и другое не достаточно наглядно.
• Поддержка || в виде нескольких шаблонов с одинаковым телом.
• Раскрытие скобок с || и &&.
• Поддержка !.

Оператор local

Оператор local позволяет временно изменить значения некоторых переменных или полей объектов. Его следует использовать вместо создании копии контекста и её редактирования, потому что аллокация нового контекста (хеша) и его копирование это довольно дорогая операция и может существенно повлиять на производительность. Также оператором local можно локализовать глобальные переменные, подполя контекста любой вложенности и т.п.

Синтаксис

local(v1 = x1, v2 = x2, ...) body

где

• vN - любое lvalue, то есть переменная, либо поле объекта
• xN - произвольные выражения
• body - либо одиночный statement, либо блок { ... }

Семантика

var x = 2,
    y = { a : 'b' },
    z = [0, 1, 2, 3];
function Y() { return y }
function a() { return 'a' }
local(x = 3, Y()[a()] = {}, y['b'] = 42, z[x] = 4) {
    x; // 3
    y['a']; // Object
    y['b']; // 42
    ++y['b']; //43
    z[2]; // 2
    z[3]; // 4
    ++x; // 4
}
z[3]; // 3
x; // 5
y['a']; // 'b'
y['b']; // undefined

'b' in y; // true!

Некоторые неочевидные моменты

• В левой части присваивания как сам объект так и поле могут вычисляться динамическ, как Y()[a()] в примере.
• Присваивания производятся слева направо (а откатываются справа налево). То есть z[x] это z[3], а не z[2].
• При откатывании используется то значение ключа (и тот объект) которые были на момент присваивания. То есть, несмотря на оператор ++x, будет восстановлено именно значение z[3], а не z[4].
• На данный момент мы не отличаем отсутствие ключа от undefined значения по этому ключу. Поэтому после откатывания ключ в объекте всегда остается. См. 'b' in y в примере.
• На данный момент мы не поддерживаем исключения. То есть если при работе тела произойдет исключение, то значения vN не будут восстановлены.

Компиляция

При компиляции конструкции local вначале генерируются операторы, запоминающие предыдущие значения переменных и полей vN, далее выполняются присваивания новых значений xN, дальше вставляется собственно тело body и в конце добавляются операторы, восстанавливающие исходные значение vN. Имеется три различных вида vN, которые обрабатываются по-разному.

• Просто переменная, то есть vN имеет вид v. В таком случае заводится одна вспомогательная переменная, в которую сохраняется исходное значение переменной v.
• Константное поле объекта, то есть vN имеет вид e[c] (или e.c), где c это константа. При этом само выражение e может быть сколь угодно сложным, вызов функции, например. В таком случае при компиляции заводится две вспомогательные переменные, одна сохраняет значение самого объекта e, вторая значение его поля c.
• Неконстантное поле объекта, то есть vN имеет вид e[k], где и e и k выражения произвольной сложности. В таком случае компилятор заводит три вспомогательные переменные, две такие же как в предыдущем пункте, плюс еще одну для хранения значения k.

Идеи на будущее

• При компиляции стоит отдельно выделить случай, когда e это this, потому что this не может измениться за время работы тела, и поэтому его значение сохранять необязательно.
• Надо померять, насколько страдает производительность, если запоминать был ли такой ключ в объекте или нет, и если не было, то вместо присваивания undefined вызывать delete. Если производительность деградирует несильно (1%?) то стоит добавить такую логику в компилятор.
• Попробовать try/finally чтобы поддержать исключения. Опять же следует замерять эффект на производительности.