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