В интерпретируемых языках программирования (или в языках, которые включают возможность компиляции в 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. Если интересно, посмотреть запись урока можно на странице курса по ссылке.
