А суть-то в чём, или Минимизация исходников — проще, чем кажется

В эти чудесные январские дни всех нас, конечно, волнует вопрос минимизации исходного кода с сохранением инварианта. В смысле, не волнует?!? Зря… Вот упал у вас компилятор, а программа гигантская — как-то неудобно такое разработчикам слать. И тут начинается веселье: а если вот это выкинуть? О, не падает — ладно, оставляем, а если это? — всё ещё падает, и это, и это, и то… Ой, я компилятор на старых исходниках запускал.

В то же время, автоматизация поиска багов — дело-то житейское: git bisect, llvm-bugpoint, creduce,… В статье я опишу yet another способ решения проблемы упрощения тестового случая, более-менее универсальный по отношению к языку программирования, и покажу некоторые примеры использования.

Универсальное, говорите… Может, оно конечно, уже десять раз реализовано, но разве это остановит матёрого велосипедиста. Да и когда в руках микроскоп, все проблемы кажутся гвоздями. В роли микроскопа — PMD.

В общем, есть такой язык для написания моделей, описываемых дифференциальными уравнениями — Modelica. Он довольно продвинутый, имеется весьма крутая открытая реализация и вообще. Но есть маленькая проблема: иногда в компиляторе возникает Internal compiler error. В прошлой статье я уже показывал, как добавить поддержку Моделики в статический анализатор PMD (кстати, в процессе review всплыли некоторые мои ошибки) в дополнение к десятку уже имеющихся языковых модулей. Вот и сейчас я решил — чего добру пропадать — и прислал proof-of-concept инструмента Source Code Minimizer, переиспользующего имеющиеся языковые модули PMD. К сожалению, меня послали — правда, не далеко, в соседний репозиторий: ментейнер сказал, что поддерживать это до скончания века он пока не решается, да и затеряется оно в общей кодовой базе, поэтому вскоре я обнаружил у себя в почтовом ящике приглашение в collaborator'ы свежесозданного pmd/pmd-scm.

Во-первых, какова постановка задачи? Требуется уменьшить размер исходного кода, сохраняя некоторое его свойство. Конкретнее, хочется, чтобы

• получившийся код был обозримого размера
  
  • он не обязан быть минимально возможным, «доработка напильником» допустима, но она не должна превращаться в мучение
  • задача автоматической обфускации не рассматривается
• минимизируемая программа может быть разделена на несколько файлов с исходным кодом
  
  • например, в Java каждый public класс должен быть в отдельном файле с правильным именем и т.д.
  • хочется, чтобы в итоге каждый файл остался обозримого размера
• в процессе преобразований должен сохраняться указанный инвариант

Внутреннее устройство

В этом разделе я примерно опишу реализацию. Для начала ещё раз замечу, что идея эта, мягко говоря, не нова. И если git bisect я привёл просто в качестве примера «механизма автоматической отладки», то вот на creduce или что-то похожее я натыкался уже довольно давно (правда, не пользовался). А вот llvm-bugpoint использовать приходилось — впечатляет: сидишь, отлаживаешь свой LLVM Pass, а он — зараза такая — падает на некоторых сишных файлах. Так вот, можно этот сишный файл скомпилировать в LLVM bitcode, запустить opt на .bc-файле со своим плагином и убедиться, что он падает. А потом, грубо говоря, я просто заменил opt на llvm-bugpoint, и через минуту получил здоровенный «скелет» одной из функций, состоящий из тучи базовых блоков и переходов между ними; всё, кроме ветвлений, было успешно выкинуто. Кстати, как и в моей постановке задачи, после десятка минут ручного упрощения всё свелось к тому, что я некорректно обрабатывал один из видов ветвлений, а всё остальное — просто декорации. В общем, идея не нова.

А теперь о реализации. Поскольку предполагалось более-менее универсальное средство, хотелось сделать некий фреймворк, в который бы можно было бы запихнуть реализации, оптимизированные под разные языки. В итоге выделилось две достаточно ортогональных концепции:

• поддерживаемый инвариант
• стратегия минимизации

Инвариант

Один из вариантов свойства, которое может хотеться сохранить, я уже описал: «компилятор напечатал в консоль некую фразу» («Internal compiler error», например). Также идеи можно почерпнуть из разнообразных фаззеров: AFL, Killerbeez и прочих:

• процесс завершился с некоторым кодом возврата (в частности, «падение по сигналу» на Linux)
• процесс выполнялся более T миллисекунд. Тут, увы, может возникнуть нестабильность в связи с плавающей загруженностью системы. Для большей точности можно использовать CPU time, хотя, в идеале пригодятся performance counters
• компилятор может (не)сгенерировать некий выходной файл
• ...

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

Стратегия минимизации

На первый взгляд, здесь всё сугубо языкозависимое. Где-то нужно выкидывать переменные вместе со случаями использования, где-то — поддерживать одинаковое количество уравнений и неизвестных. Тем важнее абстрагировать эту часть кода. Но что-то базовое можно сделать общим для всех: например, лёгким движением руки движок XPath-правил превращается… превращается… — ой, для версии XPath 1.0 не превращается. Извините, маленькая техническая неувязочка — в универсальное средство обрезки синтаксических деревьев на зиму. Вообще, API стратегии минимизации довольно простое: по большому счёту, у стратегии вызывается функция шага (ей передаётся список корневых узлов синтаксических деревьев), которая может через интерфейс операций попросить «а попробуй вот эти ветви выкинуть». Если инвариант нарушился, функция возвращает управление, если нет — раскручивает стек выкидыванием специального исключения, а полученный вариант принимается в качестве следующего приближения. Процесс считается завершённым, если функция шага вернула управление не через исключение. Вы, возможно, скажете, что это жутко не эффективно — может быть и так, ЗАТО УДОБНО!!111, но о чём вообще речь, если предполагается штатно в цикле сотни раз запускать внешний процесс компилятора.

Тут возникает вопрос: как из прореженного AST обратно получить исходник? Конечно, можно для каждого языка попробовать написать специальный код, генерирующий текстовый файл. Но, как известно, программист должен быть ленивым. Так что не пойдёт — это будет уже явно не из серии «подхватили существующие реализации и вперёд». К счастью, в узлах дерева имеется информация о начальных и конечных строке и столбце для этого узла — значит, если языковой модуль корректно указывает эту информацию, можно взять исходный текст и аккуратно вырезать из него куски (отсюда, кстати, и некоторая сложность с обфускацией: для этого недостаточно что-то выкидывать, а нужно заменять: идентификаторы, например). Кстати, в кодовой базе PMD даже обнаружился класс для редактирования файла посредством не пересекающихся операций вырезания текста (а также добавления, но конкретно для этой задачи это не так интересно).

Теория: итог

На данный момент у меня реализовано две стратегии. Одна из них — это обрезка по XPath, являющаяся в каком-то смысле вырожденным случаем, поскольку принудительно записывает результат, даже если он уже не является синтаксически корректным исходником. Вторая уже «честная» итерационная и интерактивная (в том смысле, что она реально взаимодействует с компилятором и проверяет инвариант): она просто пробует выкидывать веточки по порядку по одной в цикле. Вот о ней — чуть подробнее:

• в принципе, проверять инвариант для исходника, который не парсится, для «честной» стратегии смысла мало: даже, если компилятор это и прожуёт, минимизатор должен будет перезагрузить исходник. Поэтому имеет смысл заранее откидывать «битые» файлы: распарсить в своём процессе всяко быстрее, чем запускать целый компилятор
• в общем случае, здесь, наверное, было бы удобно использовать корутины (ну или малость вывернуть наизнанку поток управления), но, поскольку это далеко не самая вычислительно сложная часть работы, на каждом заходе в функцию шага я просто обхожу дерево в глубину, подсчитывая пройденные вершины. Запоминаю же я только счётчик. Так вот, поначалу я подумал, что вершиной больше, вершиной меньше — какая разница, всё равно же эвристика! Оказалось, что ошибка на единицу может менять скорость «сходимости» в разы. В сущности, это логично: выкидывать из класса целые функции по порядку часто будет эффективной стратегией. А вот чуточку перескочить, и каждый раз заходить внутрь функции, в большинстве случаев не имеющей никакого отношения к проблеме, выглядит так себе идеей.
• кстати о корутинах и разворачивании потока управления: с этим были бы некоторые проблемы, поскольку после перезагрузки изменённого текста AST может видоизмениться не совсем очевидным образом (то есть, не только будут откинуты указанные ветви, а где-то пропадут ставшие пустыми узлы, где-то вообще разбор пойдёт по другому пути). Не говоря уже о том, что узлы нового AST не будут идентичны по ссылке старым, а логичное сопоставление по equals — тоже выглядит непростой задачей
• в принципе, можно в разной степени использовать возможности PMD: можно использовать вычисленные типы, зависимости «определение-использование» и т.д. и делать что-то очень умное (но нужно продумать универсальное API). С другой стороны, для описанной стратегии достаточно возможности получить дерево разбора. И тут можно было бы даже прицепить какой-нибудь Kaitai Struct и попытаться потеснить afl-tmin для минимизации бинарных файлов :)

Практика

Для начала, соберём минимизатор:

git clone https://github.com/pmd/pmd-scm.git
cd pmd-scm
./mvnw clean verify
unzip pmd-scm-dist/target/pmd-scm-bin-1.0.0-SNAPSHOT.zip

Теперь нужен какой-нибудь исходник. Давайте, например, возьмём GreedyStrategy.java.

При помощи Rule Designer выясним, как выглядит типичное AST для Java, и запустим

$ ./bin/run.sh scm --language java \
        --input-file ../pmd-scm/src/main/java/net/sourceforge/pmd/scm/strategies/GreedyStrategy.java \
        --output-file GreedyStrategy-min.java \
        --strategy xpath \
        --xpath-expression '//BlockStatement[count(../BlockStatement) > 1]'
Original file(s): 6155 bytes, 1099 nodes.
After initial white-space cleanup: size 4548 bytes (73%), 1099 nodes (100%)
After pass #1: size 1984 bytes (32%), 1099 nodes (100%)
After final white-space cleanup: size 1984 bytes (32%), 325 nodes (29%)
After blank line clean up: size 1767 bytes (28%), 325 nodes (29%)

package net.sourceforge.pmd.scm.strategies;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import net.sourceforge.pmd.lang.ast.Node;
public class GreedyStrategy extends AbstractMinimizationStrategy {
    public static class Configuration extends AbstractConfiguration {
        @Override
        public MinimizationStrategy createStrategy() {
            return new GreedyStrategy(this);
        }
    }
    public static final MinimizationStrategyConfigurationFactory FACTORY = new AbstractFactory("greedy") {
        @Override
        public MinimizationStrategyConfiguration createConfiguration() {
            return new Configuration();
        }
    };
    private GreedyStrategy(Configuration configuration) {
        super(configuration);
    }
    private final Map<Node, HashSet<Node>> directlyDependingNodes = new HashMap<>();
    private final Map<Node, Set<Node>> transitivelyDependingNodes = new HashMap<>();
    private void fetchDirectDependentsFromSubtree(Node node) {
        // process depending nodes
    }
    private Set<Node> indirectlyDependentNodesFor(Node currentNode) {
    }
    private void collectNodesToRemove(Set<Node> result, Node node) {
    }
    private int previousPosition = 0;
    private int positionCountdown;
    private void findNodeToRemove(Node currentNode) throws Exception {
    }
    private void processSingleRoot(Node currentRoot) throws Exception {
        // cannot remove root
        for (int i = 0; i < currentRoot.jjtGetNumChildren(); ++i) {
            findNodeToRemove(currentRoot.jjtGetChild(i));
        }
    }
    @Override
    public void performSinglePass(List<Node> roots) throws Exception {
    }
}

То есть, мы опустошили все функции, непосредственно содержащие больше одного statement. Впрочем удаление комментариев, пустых строк и т.д. у меня не специфицировано — всё-таки это (пока?) в первую очередь инструмент для отладки компиляторов, а не создания красивых описаний интерфейсов.

Давайте теперь рассмотрим что-нибудь поинтереснее: попробуем минимизировать одновременно два файла с обратной связью от компилятора:

orig/TestResource.java:

class TestResource {
    int func() {
        System.err.println("Hello World!");
        return 123;
    }

    void unused() {
        // unused
    }
}

orig/Main.java:

class Main {
    public static void main(String[] args) {
        String str = new TestResource().func();

        return 123;
    }
}

Как вы видите, они не компилируются:

$ javac orig/TestResource.java orig/Main.java
orig/Main.java:3: error: incompatible types: int cannot be converted to String
        String str = new TestResource().func();
                                            ^
orig/Main.java:5: error: incompatible types: unexpected return value
        return 123;
               ^
2 errors

Давайте представим, что с первой ошибкой что-то не то, и попробуем сделать минимальный пример, выдающий

error: incompatible types: int cannot be converted to String

Для этого запустим

$ bin/run.sh scm --language java \
      --input-file orig/TestResource.java orig/Main.java \
      --output-file TestResource.java Main.java \
      --invariant message \
      --printed-message "error: incompatible types: int cannot be converted to String"\
      --command-line "javac TestResource.java Main.java" \
      --strategy greedy
Original file(s): 290 bytes, 77 nodes.
After initial white-space cleanup: size 258 bytes (88%), 77 nodes (100%)
After pass #1: size 255 bytes (87%), 64 nodes (83%)
After pass #2: size 244 bytes (84%), 57 nodes (74%)
After pass #3: size 205 bytes (70%), 51 nodes (66%)
After pass #4: size 192 bytes (66%), 46 nodes (59%)
After pass #5: size 181 bytes (62%), 39 nodes (50%)
After pass #6: size 179 bytes (61%), 39 nodes (50%)
After final white-space cleanup: size 149 bytes (51%), 39 nodes (50%)
After blank line clean up: size 147 bytes (50%), 39 nodes (50%)

В итоге получаем

TestResource.java:

class TestResource {
    int func() {
    }
}

Main.java:

class Main {
    public static void main() {
        String str = new TestResource().func();
    }
}

$ javac TestResource.java Main.java
TestResource.java:3: error: missing return statement
    }
    ^
Main.java:3: error: incompatible types: int cannot be converted to String
        String str = new TestResource().func();
                                            ^
2 errors

Всё, как заказывали!

Итог

Пока что проект находится на достаточно ранней стадии, но уже есть, что продемонстрировать. В дальнейшем есть идеи сделать API для language agnostic указания зависимостей между узлами AST, сделать возможность предоставлять стратегии, специфичные для языка. Ещё было бы неплохо сделать универсальную стратегию, выполняющую скрипт на Groovy/Kotlin/ещё чём-нибудь — всё-таки пользоваться этим будут люди, которые и Java-то, может, никогда не видели, зато в совершенстве знают, например, Моделику, и имеют в голове свои продвинутые способы ужимания исходников.