В интерпретируемых языках программирования (или в языках, которые включают возможность компиляции в runtime) есть возможность вычисления значения выражения, полученного из внешнего источника (например, для построения графика функции, введенной пользователем) с подстановкой актуальных значений переменных. Но JVM изначально ориентирована на компиляцию перед выполнением и механизма, аналогичного eval, в JVM нет (кроме, конечно, возможности использования Nashorn и eval в JavaScript-коде). В этой статье мы рассмотрим пример динамической генерации байт-кода из математического выражения.
Любое математическое выражение может быть преобразовано в последовательность операций над стеком, для этого начнем с простых преобразований математических операций без учета приоритета. Для простоты будем использовать только целочисленные операции (но доработка для использования float/double-значений не будет очень сложной и нужно будет только заменить тип операнда, например заменить IADD на FADD или DADD).
Например, операция 10+20 может быть записана в виде последовательности операций байт-кода — положить константу 10 в стек, положить константу 20 в стек, выполнить сложение, вернуть значение со стека как результат метода. Для генерации через ASM фрагмент может выглядеть следующим образом:
var newMethod = writer.visitMethod(ACC_PUBLIC, "eval", "()I", null, null); newMethod.visitLdcInsn(10); newMethod.visitLdcInsn(20); newMethod.visitInsn(IADD); newMethod.visitInsn(IRETURN); newMethod.visitMaxs(2, 1); //стек из двух значений, локальных переменных тоже 2 + this newMethod.visitEnd();В общем виде можно использовать обратную польскую нотацию и преобразовывать ее в последовательность операций со стеком, например 10 + 20 + 30 можно преобразовать в одну операцию (+ 10 20 30), однако в JVM арифметические операции сложения, умножения, вычитания, деления и остатка от деления являются бинарными, поэтому потребуется дополнительное преобразование в (+ (+ 20 30) 10). Создадим абстракцию для хранения таких операций:
enum OperationType { ADD, SUB, MUL, DIV, } class Operation { OperationType type; Object operand1; Object operand2; Operation(OperationType type, Object operand1, Object operand2) { this.type = type; this.operand1 = operand1; this.operand2 = operand2; } }Теперь выполним преобразование в стековую машину, последовательность операций может быть такой:
var newMethod = writer.visitMethod(ACC_PUBLIC, "sum", "()I", null, null); newMethod.visitLdcInsn(30); //операция 2 newMethod.visitLdcInsn(10); newMethod.visitLdcInsn(20); newMethod.visitInsn(IADD); //операция 1 newMethod.visitInsn(IADD); newMethod.visitInsn(IRETURN); newMethod.visitMaxs(3, 1); //стек из двух значений, локальных переменных тоже 2 + this newMethod.visitEnd();Будем использовать рекурсивную трансляцию описаний бинарных операций в байт-код, для упрощения выделим отдельный класс для генерации конструктора и генерации байт-кода для бинарной математической операции:
class OperationBuilder { OperationBuilder(ClassWriter writer) { this.writer = writer; } ClassWriter writer; void createConstructor(String className) { //создаем public class Calculator extends java.lang.Object writer.visit(V11, ACC_PUBLIC + ACC_SUPER, className, null, "java/lang/Object", null); //создаем конструктор без аргументов var newConstructor = writer.visitMethod(ACC_PUBLIC, "<init>", "()V", null, null); newConstructor.visitVarInsn(ALOAD, 0); //вызываем конструктор родительского класса (не интерфейс, поэтому false последний аргумент) //()V - сигнатура метода без аргументов и с типом результата void (V) newConstructor.visitMethodInsn(INVOKESPECIAL, "java/lang/Object", "<init>", "()V", false); newConstructor.visitInsn(RETURN); //определяем размер стека и локальных переменных newConstructor.visitMaxs(1, 1); //завершаем создание конструктора newConstructor.visitEnd(); } void createMethod(String methodName, Operation root) { var newMethod = writer.visitMethod(ACC_PUBLIC, methodName, "()I", null, null); applyOperation(newMethod, root); newMethod.visitInsn(IRETURN); newMethod.visitMaxs(3, 1); //стек из двух значений, локальных переменных тоже 2 + this newMethod.visitEnd(); } void saveToClassFile(String className) throws IOException { var classFile = writer.toByteArray(); var stream = new FileOutputStream("build/classes/java/main/"+className+".class"); stream.write(classFile); stream.close(); } void applyOperation(MethodVisitor methodVisitor, Operation operation) { if (operation.operand1.getClass()==Operation.class) { applyOperation(methodVisitor, (Operation)operation.operand1); } else { methodVisitor.visitLdcInsn(operation.operand1); } if (operation.operand2.getClass()==Operation.class) { applyOperation(methodVisitor, (Operation)operation.operand2); } else { methodVisitor.visitLdcInsn(operation.operand2); } switch (operation.type) { case ADD -> methodVisitor.visitInsn(IADD); case SUB -> methodVisitor.visitInsn(ISUB); case MUL -> methodVisitor.visitInsn(IMUL); case DIV -> methodVisitor.visitInsn(IDIV); } } } Теперь сделаем преобразование математического выражения, для правильного вычисления операций с одним приоритетом будем использовать последовательное выполнение бинарных операций, например 10+20+30 преобразуется в последовательность добавления значения констант в стек с последующим сложением. Но для генерации из математического выражения нужно будет также предусмотреть приоритеты операций и сначала подготовим наше выражение и добавим дополнительные скобки вокруг операций с более высоким приоритетом.
Для решения этой задачи будем добавлять рекурсивно дополнительные скобки вокруг выражений, приоритет которых выше, чем приоритет ранее обнаруженных операций. Например, 10+20*30-40 будет преобразован в 10+(20*30)-40. Это позволит выполнять операции над стеком без учета приоритета, при этом выражения в скобках будут выполняться как отдельный набор операций, который возвращает результат в стек. При обнаружении скобок приоритет сбрасывается и значение в скобках рассматривается как отдельная подстрока:
public ElementResult expandBrackets(String current, int index, int priority) { StringBuilder builder = new StringBuilder(); while (index<current.length()) { //завершили выражение - возвращаем подстроку и позицию после скобки if (current.charAt(index)==')') { return new ElementResult(builder.toString(), index+1); } //начало подвыражения в скобках if (current.charAt(index)=='(') { var result = expandBrackets(current, index+1, 1); index = result.position; builder.append(result.result); continue; } //начало последнего обнаруженного числа int lastPosition = index; //пропускаем число while (index<current.length() && current.charAt(index) >= '0' && current.charAt(index) <= '9') index++; //определяем приоритет следующей операции int myPriority = priority; if (index < current.length()) { char op = current.charAt(index); if (op == '+' || op == '-') myPriority = 1; if (op == '*' || op == '/') myPriority = 2; } if (myPriority > priority) { //если больше - оборачиваем в скобки (возможно в несколько пар, если разница приоритетов >1) ElementResult subitem = expandBrackets(current, lastPosition, myPriority); index = subitem.position; String result = subitem.result; for (int i = priority; i < myPriority; i++) result = "(" + result + ")"; builder.append(result); } else if (myPriority < priority) { //если меньше - просто добавляем число и выходим (продолжаем в предыдущих скобках) builder.append(current.substring(lastPosition, index)); return new ElementResult(builder.toString(), index); } else { //иначе добавляем к линейной последовательности операторов builder.append(current.substring(lastPosition, index)); if (index<current.length() && current.charAt(index)!=')') { builder.append(current.charAt(index)); } else { return new ElementResult(builder.toString(), index); } index++; } } return new ElementResult(builder.toString(), index); }Теперь полученную строку будем использовать для генерации последовательности команд размещения констант в стек и выполнения вычислений над стеком:
void createMethod(String methodName, String math) { var newMethod = writer.visitMethod(ACC_PUBLIC, methodName, "()I", null, null); applyMethod(newMethod, math, 0); newMethod.visitInsn(IRETURN); newMethod.visitMaxs(10, 1); //стек из группы значений, локальных переменных тоже 2 + this newMethod.visitEnd(); } OperationType getType(char symbol) { OperationType ot = null; switch (symbol) { case '+' -> ot = ADD; case '-' -> ot = SUB; case '*' -> ot = MUL; case '/' -> ot = OperationType.DIV; } return ot; } void putOperationIfNeeded(MethodVisitor methodVisitor, OperationType operation) { if (operation!=null) { System.out.println("Push operation " + operation.name()); switch (operation) { case ADD -> methodVisitor.visitInsn(IADD); case SUB -> methodVisitor.visitInsn(ISUB); case MUL -> methodVisitor.visitInsn(IMUL); case DIV -> methodVisitor.visitInsn(IDIV); } } } int applyMethod(MethodVisitor visitor, String math, int currentIndex) { OperationType lastOperation = null; while (currentIndex<math.length()) { if (math.charAt(currentIndex)==')') { //скобки закончились - завершаем операции над стеком и возвращаем следующую позицию putOperationIfNeeded(visitor, lastOperation); return currentIndex+1; } if (math.charAt(currentIndex) == '(') { //скобки собираем как отдельное значение в стеке currentIndex = applyMethod(visitor, math, currentIndex + 1); putOperationIfNeeded(visitor, lastOperation); lastOperation=null; continue; } //сохраняем операцию для применения к следующему значению var type = getType(math.charAt(currentIndex)); if (type!=null) { lastOperation = type; currentIndex++; continue; } //извлекаем значение числового операнда StringBuilder number = new StringBuilder(); while (currentIndex < math.length() && math.charAt(currentIndex) >= '0' && math.charAt(currentIndex) <= '9') { number.append(math.charAt(currentIndex)); currentIndex++; } System.out.println("Push constant "+number); visitor.visitLdcInsn(Integer.parseInt(number.toString())); //применяем операцию над стеком (если необходимо) putOperationIfNeeded(visitor, lastOperation); //и готовимся к следующей операции lastOperation = null; } return currentIndex; } Для корректного создания метода также необходимо предусмотреть вычисление глубины стека (передается в visitMaxs), для этого будем сохранять текущее значение глубины и увеличивать его на единицу при сохранении константы (или в дальнейшем добавим переменные) или уменьшать на два при выполнении бинарной операции (извлекается два значения, размещает один результат):
int maxDepth = 0; int depth = 0; void changeDepth(int delta) { depth+=delta; if (depth>maxDepth) { maxDepth = depth; } }Для тестирования нужно будет создать объекта класса OperationBuilder, сгенерировать конструктор, метод eval и сохранить это в .class-файл:
public static void main(String[] args) throws IOException, ClassNotFoundException, NoSuchMethodException, InvocationTargetException, IllegalAccessException, InstantiationException { String className = "Calculator2"; var writer = new ClassWriter(0); var builder = new OperationBuilder(writer); var result = builder.expandBrackets("20*(3+2)-(2+5)", 0, 1); System.out.println("Brackets expansion result is "+result.result); builder.createConstructor(className); builder.createMethod("eval", result.result); builder.saveToClassFile(className); var calculator = Class.forName(className); var calculatorInstance = calculator.getDeclaredConstructor().newInstance(); var method = calculator.getMethod("eval"); var eval = method.invoke(calculatorInstance); System.out.print(eval); }После того, как мы создали интерпретатор константных значений, мы можем добавить поддержку переменных. Здесь есть несколько вариантов решения, но мы ограничимся добавлением аргументов к функции в соответствии с обнаруженными ссылками на переменные, для этого мы должны будем изменить сигнатуру функции (добавить необходимое количество букв I для передачи целочисленных аргументов), использовать ее при обнаружении функции в getMethod("eval", Integer.class)и вместо подстановки значения константы использовать обращение к локальной переменной из фрейма метода со смещением, который совпадает с обнаруженной буквой названия переменной. Полный текст eval с поддержкой переменных представлен в https://github.com/dzolotov/bytecode (ветка eval).
Материал подготовлен в преддверии старта онлайн-курса «Java Developer. Professional».
Недавно в рамках курса прошел открытый урок, посвященный разбору протокола HTTP. На уроке рассмотрели, что он из себя представляет, а для закрепления материала написали простейшие HTTP клиент и сервер на java.io. Если интересно, посмотреть запись урока можно на странице курса по ссылке.
ссылка на оригинал статьи https://habr.com/ru/articles/730160/
Добавить комментарий