В смысле, не волнует?!? В эти чудесные январские дни всех нас, конечно, волнует вопрос минимизации исходного кода с сохранением инварианта. И тут начинается веселье: а если вот это выкинуть? Зря… Вот упал у вас компилятор, а программа гигантская — как-то неудобно такое разработчикам слать. — всё ещё падает, и это, и это, и то… Ой, я компилятор на старых исходниках запускал. О, не падает — ладно, оставляем, а если это?
В то же время, автоматизация поиска багов — дело-то житейское: git bisect, llvm-bugpoint, creduce,… В статье я опишу yet another способ решения проблемы упрощения тестового случая, более-менее универсальный по отношению к языку программирования, и покажу некоторые примеры использования.
Да и когда в руках микроскоп, все проблемы кажутся гвоздями. В роли микроскопа — PMD. Универсальное, говорите… Может, оно конечно, уже десять раз реализовано, но разве это остановит матёрого велосипедиста.
Он довольно продвинутый, имеется весьма крутая открытая реализация и вообще. В общем, есть такой язык для написания моделей, описываемых дифференциальными уравнениями — Modelica. В прошлой статье я уже показывал, как добавить поддержку Моделики в статический анализатор PMD (кстати, в процессе review всплыли некоторые мои ошибки) в дополнение к десятку уже имеющихся языковых модулей. Но есть маленькая проблема: иногда в компиляторе возникает Internal compiler error. К сожалению, меня послали — правда, не далеко, в соседний репозиторий: ментейнер сказал, что поддерживать это до скончания века он пока не решается, да и затеряется оно в общей кодовой базе, поэтому вскоре я обнаружил у себя в почтовом ящике приглашение в collaborator'ы свежесозданного pmd/pmd-scm. Вот и сейчас я решил — чего добру пропадать — и прислал proof-of-concept инструмента Source Code Minimizer, переиспользующего имеющиеся языковые модули PMD.
Требуется уменьшить размер исходного кода, сохраняя некоторое его свойство. Во-первых, какова постановка задачи? Конкретнее, хочется, чтобы
- получившийся код был обозримого размера
- он не обязан быть минимально возможным, «доработка напильником» допустима, но она не должна превращаться в мучение
- задача автоматической обфускации не рассматривается
- минимизируемая программа может быть разделена на несколько файлов с исходным кодом
- например, в Java каждый
publicкласс должен быть в отдельном файле с правильным именем и т.д. - хочется, чтобы в итоге каждый файл остался обозримого размера
- например, в Java каждый
- в процессе преобразований должен сохраняться указанный инвариант
Внутреннее устройство
Для начала ещё раз замечу, что идея эта, мягко говоря, не нова. В этом разделе я примерно опишу реализацию. А вот llvm-bugpoint использовать приходилось — впечатляет: сидишь, отлаживаешь свой LLVM Pass, а он — зараза такая — падает на некоторых сишных файлах. И если git bisect я привёл просто в качестве примера «механизма автоматической отладки», то вот на creduce или что-то похожее я натыкался уже довольно давно (правда, не пользовался). А потом, грубо говоря, я просто заменил opt на llvm-bugpoint, и через минуту получил здоровенный «скелет» одной из функций, состоящий из тучи базовых блоков и переходов между ними; всё, кроме ветвлений, было успешно выкинуто. Так вот, можно этот сишный файл скомпилировать в LLVM bitcode, запустить opt на .bc-файле со своим плагином и убедиться, что он падает. В общем, идея не нова. Кстати, как и в моей постановке задачи, после десятка минут ручного упрощения всё свелось к тому, что я некорректно обрабатывал один из видов ветвлений, а всё остальное — просто декорации.
Поскольку предполагалось более-менее универсальное средство, хотелось сделать некий фреймворк, в который бы можно было бы запихнуть реализации, оптимизированные под разные языки. А теперь о реализации. В итоге выделилось две достаточно ортогональных концепции:
- поддерживаемый инвариант
- стратегия минимизации
Инвариант
Также идеи можно почерпнуть из разнообразных фаззеров: AFL, Killerbeez и прочих: Один из вариантов свойства, которое может хотеться сохранить, я уже описал: «компилятор напечатал в консоль некую фразу» («Internal compiler error», например).
- процесс завершился с некоторым кодом возврата (в частности, «падение по сигналу» на Linux)
- процесс выполнялся более T миллисекунд. Тут, увы, может возникнуть нестабильность в связи с плавающей загруженностью системы. Для большей точности можно использовать CPU time, хотя, в идеале пригодятся performance counters
- компилятор может (не)сгенерировать некий выходной файл
- ...
В общем, это достаточно автономный кусок задачи, часто вообще не зависящий от конкретного языка. Часть из них я уже реализовал (код возврата, напечатанная строка), часть — нет, какие-то, возможно, будут специфичны для отдельных языков.
Стратегия минимизации
Где-то нужно выкидывать переменные вместе со случаями использования, где-то — поддерживать одинаковое количество уравнений и неизвестных. На первый взгляд, здесь всё сугубо языкозависимое. Но что-то базовое можно сделать общим для всех: например, лёгким движением руки движок XPath-правил превращается… превращается… — ой, для версии XPath 1. Тем важнее абстрагировать эту часть кода. Извините, маленькая техническая неувязочка — в универсальное средство обрезки синтаксических деревьев на зиму. 0 не превращается. Если инвариант нарушился, функция возвращает управление, если нет — раскручивает стек выкидыванием специального исключения. Вообще, API стратегии минимизации довольно простое: по большому счёту, у стратегии вызывается функция шага (ей передаётся список корневых узлов синтаксических деревьев), которая может через интерфейс операций попросить «а попробуй вот эти ветви выкинуть». Вы, возможно, скажете, что это жутко не эффективно — может быть и так, ЗАТО УДОБНО!! Процесс считается завершённым, если функция шага вернула управление не через исключение. 111, но о чём вообще речь, если предполагается штатно в цикле сотни раз запускать внешний процесс компилятора.
Теория: итог
Одна из них — это обрезка по XPath, являющаяся в каком-то смысле вырожденным случаем, поскольку принудительно записывает результат, даже если он уже не является синтаксически корректным исходником. На данный момент у меня реализовано две стратегии. Вот о ней — чуть подробнее: Вторая уже «честная» итерационная и интерактивная (в том смысле, что она реально взаимодействует с компилятором и проверяет инвариант): она просто пробует выкидывать веточки по порядку по одной в цикле.
- в принципе, проверять инвариант для исходника, который не парсится, для «честной» стратегии смысла мало: даже, если компилятор это и прожуёт, минимизатор должен будет перезагрузить исходник. Поэтому имеет смысл заранее откидывать «битые» файлы: распарсить в своём процессе всяко быстрее, чем запускать целый компилятор
- в общем случае, здесь, наверное, было бы удобно использовать корутины (ну или малость вывернуть наизнанку поток управления), но, поскольку это далеко не самая вычислительно сложная часть работы, на каждом заходе в функцию шага я просто обхожу дерево в глубину, подсчитывая пройденные вершины. Запоминаю же я только счётчик. Так вот, поначалу я подумал, что вершиной больше, вершиной меньше — какая разница, всё равно же эвристика! Оказалось, что ошибка на единицу может менять скорость «сходимости» в разы. В сущности, это логично: выкидывать из класса целые функции по порядку часто будет эффективной стратегией. А вот чуточку перескочить, и каждый раз заходить внутрь функции, в большинстве случаев не имеющей никакого отношения к проблеме, выглядит так себе идеей.
- в принципе, можно в разной степени использовать возможности 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 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-то, может, никогда не видели, зато в совершенстве знают, например, Моделику, и имеют в голове свои продвинутые способы ужимания исходников.
