Сейчас я работаю над 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 — класс, содержащий набор пар имя-значение. Смысл его в том, что нода которую он ищет должна содержать поле или метод с указанным именем, а значение (или результат) должны совпадать с указанным. Значениями могут быть:

1. другие элементы паттерна (может быть снова Property, например), тогда поиск продолжится уже по ним
2. обычные объекты (строка, число, или любой класс), тогда будет просто проведена проверка на совпадение

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 за вычитку черновика