Анализ AST c помощью паттернов
Сейчас я работаю над senjin/gglsl — библиотекой для программирования шейдеров с помощью Groovy, о которой недавно писал.
Здесь я опишу три подхода к анализу AST (abstract syntax tree), все на примерах под-задач, вытекающих одна из другой и связанных общим контекстом: рекурсивные функции, паттерн Visitor, и паттерн-матчинг.
Паттерн-матчинг реализован на Java и доступен на GitHub.
Рекурсивные функции
90% функционала делается за 1% времени (или типа того)
На первом этапе мне было достаточно просто транслировать код на Groovy в код на glsl. Для этого я использовал простые функции разбора дерева, рекурсивно вызывающие друг-друга. Каждая принимает на вход AST-ноду распарсенного Groovy и возвращает строчку, представляющую из себя транслированный код уже на glsl. Этого вполне достаточно т.к. языки очень похожи, в процессе не нужно накапливать никакой информации, а в каждой ноде локально доступна вся необходимая информация.
Пример функций трансляции бинарного выражения и унарного минуса:
private String translateExpression(BinaryExpression e) {
def opName = e.operation.getText()
if (opName == "[") return translateExpression(e.leftExpression) + "[" + translateExpression(e.rightExpression) + "]"
return "(" + translateExpression(e.leftExpression) + " " + opName + " " + translateExpression(e.rightExpression) + ")"
}
private String translateExpression(UnaryMinusExpression e) {
return "-" + translateExpression(e.expression)
}
Паттерн Visitor
Дьявол прячется в деталях
Вряд ли будет удобно создавать шейдеры если нельзя будет создавать функции. Так что после парочки работающих шейдеров я решил реализовать трансляцию функций. Тут из всех щелей полезли тонкости и детали.
В glsl передача аргументов происходит по значению, а в Groovy по значению мы работаем только с примитивами. Кроме того в glsl с помощью квалификатора out можно передать примитив или вектор обратно, а в Groovy это невозможно. Не помогут и аннотации, т.к. хочется иметь не просто «выглядящий» правильно код, а и запускаемый, и отлаживаемый. Это только пара примеров, на самом деле тонкостей много.
После этапа отчаяния, было принято несколько решений. Например — запретить переписывать непримитивные параметры, запретить возвращать их, если они являются параметрами метода, и т.п.
Приведу код проверки наличия модификации непримитивных параметров с использованием визитёра:
for (Parameter parameter : methodNode.getParameters()) if (!isPrimitive(translateType(parameter.getText()))) {
YList<Boolean> rewritten = al(false);
CodeVisitorSupport detectRewrittenVisitor = new CodeVisitorSupport() {
@Override
public void visitBinaryExpression(BinaryExpression expression) {
if (expression.getOperation().getText().equals("=")) {
Expression left = expression.getLeftExpression();
if (left instanceof VariableExpression) {
if (((VariableExpression) left).getName().equals(parameter.getName())) {
rewritten.set(0, true);
}
}
}
super.visitBinaryExpression(expression);
}
};
detectRewrittenVisitor.visitBlockStatement((BlockStatement) methodNode.getCode());
if (rewritten.get(0)) System.out.println(parameter.getName() + " rewritten!");
}
Код не сложный, но и задача примитивная. И хотя визитёр для таких задач и задумывался — уже здесь кода непозволительно много. Особенно удручают проверки типов дочерних нод и извлечение из них дополнительной информации. Проблема усугубится когда задача станет сложнее — когда нужно, например, проверить наличие в коде чтения поля. При разборе Groovy придётся сначала убедиться что мы находимся в правой ветке присваивания (или ряда других нод), и только ГЛУБЖЕ найти, собственно, ноду, в которой происходит чтение. Т.е. тут — либо придётся вводить в визитёр состояние, либо делать два визитёра, один для поиска ветки «правая часть присваивания», второй — для поиска ноды «чтение поля» где-то в глубине выражений этой ветки.
Паттерн-матчинг
Когда становится легче дышать, а от изменений в ТЗ не болит голова
К сожалению, предыдущие варианты подходят для простых случаев, но заставляют унывать на сложных задачах. Приходится писать много кода для простых понятий, существующий код начинает мешать новому, приходится добавлять различные накопители и промежуточные состояния. А хочется — просто указать кусок AST дерева с переменными, и сказать что нужно делать, если такой найден…
Сказано-сделано! Финальный вариант паттерна для нахождения перезаписи поля в заданной переменной:
Object varWritePattern = stairs(
deeper(G_BODY_ACCESSORS),
p(BinaryExpression.class, "operation", p("text", "="), "leftExpression"),
p(VariableExpression.class, "variable", var("VAR_NAME")));
boolean wasWritten = match(methodNode, varWritePattern).notEmpty();
(НЕ ПАНИКОВАТЬ, чуть дальше я опишу детали, сейчас нужно просто насладиться зрелищем)
Здесь всего одна переменная (var(«VAR_NAME»)), и она указывает на имя переписываемой (в исходном коде) переменной.
Самое интересное тут то, что добавление довольно сложных (для визитёра) условий — выливается в добавление одной строчки на каждое условие! Т.е. поразительный результат — теперь размер кода линейно зависит от сложности ТЗ (тех-задания) и эта сложность не накапливается! Более сложный паттерн:
Object G_FIELD_AS_ARG_PATTERN = stairs(
deeper(G_BODY_ACCESSORS),
p(MethodCallExpression.class,
"getMethod", p("getText", var("METHOD_NAME")),
"getArguments"),
p(ArgumentListExpression.class, "expressions"),
i(),
p(PropertyExpression.class,
"getObjectExpression", p(VariableExpression.class, "variable", var("OBJ_NAME")),
"getProperty", p("value", var("FIELD_NAME"))));
Matcher.match(tree, G_FIELD_AS_ARG_PATTERN)
Здесь вычисляется место в дереве, где происходит передача поля какой-то переменной в качестве аргумента в какую-то функцию. Тут уже есть сразу 3 переменные — имя метода (METHOD_NAME), имя объекта (OBJ_NAME), и имя поля в нём (FIELD_NAME). При желании — легко можно добавить ещё переменных (например, var(«ARG_INDEX») — для получения или связывания номера аргумента). Замечательный факт — в функцию match можно передать предварительно связанные переменные! Тогда не меняя шаблона мы можем находить под-дерево с конкретным именем объекта, или с конкретным индексом, по отдельности или всего сразу. Можно только вообразить сколько нужно было бы вписывать в разные места визитёра чтобы достичь тех-же целей.
Проход за кулисы
Когда магию объясняют, она перестаёт быть магией (но остаётся достаточно развитой технологией)
Паттерн представляет из себя слепок кусочка дерева, которое нужно найти. Матчер берёт этот слепок и ищет в дереве — какой кусочек подошёл бы.
Matcher.match(tree, pattern)
Эта функция возвращает список всех совпадений. Каждая запись — это маппинг переменной к тому элементу дерева, который соответствовал ей во время матчинга. Если в паттерне переменных не было, то записи будут пусты, но по их количеству можно увидеть были ли совпадения и сколько (что тоже может быть целью запроса).
Кроме того, в матчинг можно передать заранее связанные переменные, чтобы ограничить варианты:
boolean wasWritten = match(methodNode, varWritePattern, hm("VAR_NAME", parameterName)).notEmpty();
Здесь мы заранее утверждаем что подойдёт только такое под-дерево, в котором переменная VAR_NAME соответствует некоему parameterName
Надо отметить, что под деревом тут подразумевается не какая-то специфическая структура данных (дерево), а что угодно. Это может быть просто массив с числами или объектами. Или просто один объект любого типа.
Сам паттерн не содержит исчерпывающий 100% совпадающий кусок. В нём указано только то что имеет значение. Кроме того — он состоит не из тех же классов что и дерево, а из специальных. Дальше я приведу примеры таких классов с пояснениями.
new Property("getClass", ReturnStatement.class, "getExpression", var("EXPR"));
Property — класс, содержащий набор пар имя-значение. Смысл его в том, что нода которую он ищет должна содержать поле или метод с указанным именем, а значение (или результат) должны совпадать с указанным. Значениями могут быть:
- другие элементы паттерна (может быть снова Property, например), тогда поиск продолжится уже по ним
- обычные объекты (строка, число, или любой класс), тогда будет просто проведена проверка на совпадение
new Var("VAR_NAME", rest);
Var та самая переменная, которая содержит имя, и продолжение паттерна. В результате именно по этому имени будет содержаться ссылка на соответствующую ноду дерева.
new ByIndex(3, rest);
ByIndex — позволяет матчить List и массивы. Причём сам индекс тоже считается «нодой», так что можно матчить, к примеру, «одинаковые значения в двух массивах находящиеся на одном и том же месте».
new Deeper(G_BODY_ACCESSORS, rest);
Deeper — интересный элемент. Позволяет говорить что «неважно что мы встретим дальше, но в конце-концов найдём...». Он позволяет спускаться по структуре данных на неопределённую изначально глубину. Хороший пример — выражения в языке — не известно сколько уровней BinaryExpression и других ветвлений находится между объявлением метода и конкретным использованием переменной. Так же в нём нужно указать набор мини-паттернов, accessors, с помощью которых он будет прокладывать себе путь.
Я не фанат записей вида new LongJavaClassName(..., поэтому если что-то создаётся больше нескольких раз — я пишу статический метод. Т.о. переписав new Property на p(), new Variable на var(), и т.д., паттерн приобретает вот такой опрятный вид:
Object varWritePattern = deeper(G_BODY_ACCESSORS, p(
"getClass", BinaryExpression.class,
"operation", p("text", "="),
"leftExpression", p(
"getClass", VariableExpression.class,
"variable", var("VAR_NAME"))));
Как видно, здесь декларативно описан шаблон для нахождения присваиваний. Его можно использовать так:
YSet<YMap<String, Object>> match1 = match(node, varWritePattern);
YSet<YMap<String, Object>> match2 = match(node, varWritePattern, hm("VAR_NAME", varName));
В первом случае мы получаем все варианты, а во втором только те, в которых присваивание происходит в переменную с переданным значением varName (связывание переменной).
Избавляемся от ступеней отступов
Когда лестниц в доме больше чем полов
Мне никогда не нравился в Lisp этот стиль, когда всегда нужно открыть ещё одну скобочку (видимо не только мне, потому что в Clojure есть -> и ->>). Гораздо удобнее когда когда я “вызываю метод” у результата предыдущего вызова как в Scala, Xtend, моих YCollections, и много где ещё:
String names = al(new File("/home/user/").listFiles())
.filter(File::isDirectory) //only dirs
.map(File::getName) //get name
.filter(n -> n.startsWith(".")) //only invisible
.sorted() //sorted
.foldLeft("", (r, n) -> r + ", " + n); //to print fine
System.out.println(names);
Для достижения такого же эффекта я добавил функцию “stairs”, которая (по аналогии с “->>” из Clojure) — просто добавляет то, что идёт позже, в поле rest того, что идёт раньше (не так просто, но суть такова). Теперь достаточно сложный паттерн начинает выглядеть вполне приемлемо:
Object G_FIELD_AS_ARG_PATTERN = stairs(
deeper(G_BODY_ACCESSORS),
p(MethodCallExpression.class,
"getMethod", p("getText", var("METHOD_NAME")),
"getArguments"),
p(ArgumentListExpression.class, "expressions"),
i(var("ARG_INDEX")),
p(PropertyExpression.class,
"getObjectExpression", p(VariableExpression.class,
"variable", "OBJ_NAME"),
"getProperty", p("value", var("FIELD_NAME"))));
В таком виде очень удобно читать паттерн — просто сверху вниз, ответвления — направо. Легко можно копи-пастить логику из соседних паттернов.
Тот же пример с комментариями
Object G_FIELD_AS_ARG_PATTERN = stairs(
//на какой-то глубине
deeper(G_BODY_ACCESSORS),
//есть объект такого класса
p(MethodCallExpression.class,
//с такими параметрами
"getMethod", p("getText", var("METHOD_NAME")),
//а метод getArguments возвращает...
"getArguments"),
// такой объект, у которого есть поле expressions, которое...
p(ArgumentListExpression.class, "expressions"),
//является массивом, а по индексу (который мы запомним) находится...
i(var("ARG_INDEX")),
//такой объект
p(PropertyExpression.class,
//с каким-то ответвлением
"getObjectExpression", p(VariableExpression.class,
"variable", var("OBJ_NAME")),
//и с ещё одним
"getProperty", p("value", var("FIELD_NAME"))));
Теперь используем этот паттерн для анализа следующего Groovy кода:
public void foo(Vec3f vecA, Vec3f vecB) {
bar(vecA.x, vecA.y)
bar(vecA.x, vecB.x)
}
Распарсим его:
String src = IO.readFile("src/main/java/yk/senjin/shaders/gshader/analysis/HabraExample.groovy");
//parse kotlin file
Object node = new AstBuilder().buildFromString(CompilePhase.INSTRUCTION_SELECTION, src);
И наконец, сделаем несколько запросов:
//select method "foo"
for (YMap<String, Object> m : match(node, stairs(deeper(G_METHOD_ACCESSORS), var("method"), p(MethodNode.class, "name"), "foo"))) {
//getting methodNode object from select result
Object methodNode = m.get("method");
System.out.println("all variables are free:");
System.out.println(match(methodNode, G_FIELD_AS_ARG_PATTERN).toString("\n"));
System.out.println("fixed OBJ_NAME:");
System.out.println(match(methodNode, G_FIELD_AS_ARG_PATTERN, hm("OBJ_NAME", "vecB")).toString("\n"));
System.out.println("fixed ARG_INDEX:");
System.out.println(match(methodNode, G_FIELD_AS_ARG_PATTERN, hm("ARG_INDEX", 0)).toString("\n"));
}
Вывод в консоли:
all variables are free:
{METHOD_NAME=bar, OBJ_NAME=vecA, FIELD_NAME=x, ARG_INDEX=0}
{METHOD_NAME=bar, OBJ_NAME=vecA, FIELD_NAME=y, ARG_INDEX=1}
{METHOD_NAME=bar, OBJ_NAME=vecB, FIELD_NAME=x, ARG_INDEX=1}
fixed OBJ_NAME:
{OBJ_NAME=vecB, METHOD_NAME=bar, FIELD_NAME=x, ARG_INDEX=1}
fixed ARG_INDEX:
{ARG_INDEX=0, METHOD_NAME=bar, OBJ_NAME=vecA, FIELD_NAME=x}
Другой пример, для совсем простой структуры данных — массива векторов:
Vec3f[] vv = new Vec3f[]{new Vec3f(0, 0, 0), new Vec3f(1, 1, 1)};
System.out.println(match(vv, i(p("x", var("X_VALUE")))));
System.out.println(match(vv, i(var("OBJ_INDEX"), p("x", var("X_VALUE")))));
В консоли появится:
[{X_VALUE=0.0}, {X_VALUE=1.0}]
[{OBJ_INDEX=0, X_VALUE=0.0}, {OBJ_INDEX=1, X_VALUE=1.0}]
Для полноты картины приведу пример аксессоров для Deeper:
public static final YArrayList<Object> G_BODY_ACCESSORS = al(
i(var("access")),
p("methodsList", var("access")),
p(MethodNode.class, "code", var("access")),
p(MethodCallExpression.class, "getReceiver", var("access")),
p(BlockStatement.class, "getStatements", var("access")),
p(ExpressionStatement.class, "expression", var("access")),
p(BinaryExpression.class, "leftExpression", var("access")),
p(BinaryExpression.class, "rightExpression", var("access")),
p(DeclarationExpression.class, "getLeftExpression", var("access")),
p(DeclarationExpression.class, "getRightExpression", var("access")),
p(UnaryMinusExpression.class, "getExpression", var("access")),
p(UnaryPlusExpression.class, "getExpression", var("access")),
p(ReturnStatement.class, "getExpression", var("access")),
p(ConstructorCallExpression.class, "arguments", p("expressions", i(var("access")))),
p(IfStatement.class, "booleanExpression", var("access")),
p(IfStatement.class, "ifBlock", var("access")),
p(IfStatement.class, "elseBlock", var("access"))
Можно сказать что он выполняет роль похожую на ту, которую выполняет интерфейс визитёра, только гораздо проще и гибче. Например строчка i(var(«access»)) — позволяет спускаться в любой список или массив, т.е. не привязана конкретно к данному дереву, а является общей. Т.о. легко задать правила о том, куда можно, а куда нельзя спускаться с помощью Deeper — просто указав соответствующий набор аксессоров.
Интересная идея. Кажется, с помощью паттерн-матчинга можно анализировать не только AST, но и control-flow, для этого нужно соответствующим образом описать аксессоры в Deeper и…
Об оптимизации
Уже пора
Может показаться что подход хорош, но не годится для высоко-нагруженных участков (к примеру, разбора миллионов строк кода). Это верно, но не верно.
Во первых — с паттернами очень легко описать предметную область. А это позволяет разделить задачи — на “реализацию ТЗ”, и на “оптимизацию кода”. Имея на руках отлаженный и покрытый тестами «медленный», простой, правильный вариант — оптимизированный вариант создать гораздо проще и быстрее, чем реализовывать его решая одновременно две задачи — реализации ТЗ и оптимизации. Т.е. тут можно разделить — лёгкость реализации ТЗ и оптимизацию работающего кода.
А это гораздо важнее чем может показаться. У меня были задачи, в которых реализация ТЗ, а ПОТОМ оптимизация может занимать неделю, а реализация ВМЕСТЕ с оптимизацией может занимать месяц. Да, разница может составлять порядок, а на масштабе проекта даже порядки.
Во-вторых, возможности открывает сам факт декларативности в описании предметной области. По декларациям (теоретически) можно сгенерировать оптимизированный код, который хранит весь необходимый стейт в переменных, проходится по дереву один раз выполняя много параллельных задач, и т.п. Т.е. в теории можно сделать генератор оптимизированного, «неприятного» кода. Неприятного — потому что много стейта, много параллельных процессов. Как генератор парсеров.
Просуммирую плюсы
Сам себя не похвалишь — как гугл найдёт?
- декларативность (можно рисовать, можно анализировать, …)
- лёгкий синтаксис
- ненакапливающаяся сложность кода
- вариативная глубина спуска
- отсутствие привязки к конкретному типу данных
- две роли переменных (результат/связывание)
- потенциал для оптимизаций
- лёгкое переиспользование и копи-паст шаблонов
- можно использовать в роли обычного select
- разделение задач
Вики с мавеном github.com/kravchik/jcommon/wiki/pattern-matching
P.S. можно в очередной раз восхититься лиспом, в котором паттерн-матчинг для разбора AST был бы вполне естественным и не стоящим отдельной статьи.
P.P.S. а как разбираете деревья вы? Какие у моего велосипеда промышленные аналоги?
Спасибо kleshney и oshyshko за вычитку черновика
