alexander-shustanov 21 янв 2020 в 12:48

DIY Корутины. Часть 1. Ленивые генераторы

18 мин

11K

Блог компании HaulmontJava*Параллельное программирование*Программирование*

В мире JVM про корутины знают в большей степени благодаря языку Kotlin и Project Loom. Хорошего описания принципа работы котлиновских корутин я не видел, а код библиотеки kotlin-coroutines совершенно не понятен неподготовленному человеку. По моему опыту, большинство людей знает о корутинах только то, что это "облегченные потоки", и что в котлине они работают через умную генерацию байткода. Таким был и я до недавнего времени. И мне пришла в голову идея, что раз корутины могут быть реализованы в байткоде, то почему бы не реализовать их в java. Из этой идеи, впоследствии, появилась небольшая и достаточно простая библиотека, в устройстве которой, я надеюсь, может разобраться практически любой разработчик. Подробности под катом.

Исходный код

Проект я назвал Microutines, что получилось из слов Micro и Coroutines.

Весь код доступен на github. Изначально я хотел построить повествование в соответствии с развитием моего собственного понимания темы, рассказать о моих неправильных решениях и идеях, о развитии api, но тогда код в статье очень сильно бы отличался от кода с github (что в любом случае неизбежно, статью я пишу один раз, а на гитхаб комичу время от времени). Поэтому я в большей степени буду описывать конечный вариант библиотеки, и если некоторые части api не очень понятны с первого взгляда, то, скорее всего, они нужны для решения проблем, которые мы будем рассматривать в следующих статьях.

Disclaimer

Это своего рода учебный проект. Я буду рад, если кто-то из читателей склонирует его, чтобы поиграться или даже закинет пулл реквест. Но использовать его в продакшне не стоит. Лучший способ глубоко разобраться в какой-нибудь технологии — реализовать ее самому, в чем и заключается единственная цель этого проекта.

А еще я не гарантирую точность используемых терминов. Возможно какие-то из них я где-то услышал, неправильно запомнил, а какие-то вообще придумал сам и забыл.

Что такое корутины

Как я уже заметил, про корутины часто говорят, что это "облегченные потоки". Это не совсем верное определение. Верного определения я правда тоже давать не буду, но попробую описать, какие они, корутины. Называть корутины потоками будет не совсем корректно. Корутина это меньшая чем поток единица планирования, а поток, в свою очередь, меньшая чем процесс единица планирования (scheduling). Планированием процессов и потоков занимается операционная система. Планированием корутин занимается… мы сами займемся их планированием. Корутины работают поверх обычных потоков, и их главная фишка в том, что они не блокируют поток, когда ждут выполнения какой-то другой задачи, а освобождают его для другой корутины. Такой подход называется кооперативной многозадачностью. Корутина может работать сначала в одном потоке, потом в другом. Поток для корутины выступает в роли ресурса, и миллион корутин может работать на одном единственном потоке. Вы могли видеть такую картинку:

Задачи contribs 1 и contribs 2 выполняют какие-то запросы и на время ожидания ответов не блокируют поток, а приостанавливают свою работу и продолжают её уже после получения ответов. Мы можем написать такой код с помощью колбеков, скажете вы. Так и есть, но суть корутин в том, что мы пишем код без колбеков, мы пишем обычный последовательный код, который выполняется асинхронно.

Генераторы

Разработку начнем от простого к сложному. Первая вещь, которую мы сделаем, будет ленивая генерация коллекции, реализуемая в некоторых языках с помощью ключевого слова yield. Генераторы тут не случайно, как мы увидим дальше, и генераторы и корутины могут быть реализованы с помощью одного и того же механизма.

Рассмотрим пример на python, просто потому что генераторы там есть из коробки.

def generator():
    k = 10
    yield k
    k += 10
    yield k
    k += 10
    yield k

for i in generator():
    print(i)

Цикл разворачивается в нечто такое (может не совсем так, но нам важен принцип):

gen = generator()
while True:
    try:
        i = next(gen)
        print(i)
    except StopIteration:
        break

Вызов generator() создаст особый итератор, который называется генератор. При первом вызове next(gen) выполняется код от начала функции generator до первого yield, и в переменную i запишется значение локальной переменной k из genertator(). Каждый следующий вызов next продолжит исполнение функции с инструкции, стоящей сразу за предыдущим yield и так далее. При этом между вызовами next сохраняются значения всех локальных переменных внутри generator.

Вот примерно тоже самое, но на языке Kotlin.

val seq = sequence {
    var i = 10 
    yield(i)
    i += 10
    yield(i)
    i += 10
    yield(i)
}

for (i in seq) {
    println(i)
}

На Java ленивую генерацию мы могли бы сделать как-то так:

Iterable<Integer> seq = DummySequence.first(() -> {
    final int i = 10;
    return DummySequence.next(i, () -> {
            final int i1 = i + 10;
            return DummySequence.next(i1, () -> DummySequence.end(i1 + 10));
    });
});

for(int i: seq) {
    System.out.println(i);
}

Реализация DummySequence

import org.junit.Assert;
import org.junit.Test;

import java.util.Iterator;
import java.util.List;
import java.util.function.Supplier;
import java.util.stream.Collectors;
import java.util.stream.StreamSupport;

public class DummySequenceTest {

    @Test
    public void dummySequenceTest() {
        DummySequence<Integer> sequence = DummySequence.first(() -> {
            final int i = 10;
            return DummySequence.next(10, () -> {
                final int i1 = i + 10;
                return DummySequence.next(i1, () -> DummySequence.end(i1 + 10));
            });
        });

        List<Integer> list = StreamSupport.stream(sequence.spliterator(), false)
                .collect(Collectors.toList());

        Assert.assertEquals(10, ((int) list.get(0)));
        Assert.assertEquals(20, ((int) list.get(1)));
        Assert.assertEquals(30, ((int) list.get(2)));
    }

    private static class DummySequence<T> implements Iterable<T>, Iterator<T> {
        private Step<T> step;

        public DummySequence(Step<T> step) {
            this.step = step;
        }

        @Override
        public Iterator<T> iterator() {
            return this;
        }

        @Override
        public boolean hasNext() {
            if (step instanceof EndStep)
                return false;
            step = step.nextStep();
            return true;
        }

        @Override
        public T next() {
            return step.getValue();
        }

        public static <T> DummySequence<T> first(Supplier<Step<T>> next) {
            return new DummySequence<>(new FirstStep<T>(next));
        }

        public static <T> Step<T> next(T value, Supplier<Step<T>> next) {
            return new IntermediateStep<>(value, next);
        }

        public static <T> Step<T> end(T value) {
            return new EndStep<>(value);
        }
    }

    private interface Step<T> {
        T getValue();

        Step<T> nextStep();
    }

    public static class FirstStep<T> implements Step<T> {
        Supplier<Step<T>> nextStep;

        public FirstStep(Supplier<Step<T>> next) {
            this.nextStep = next;
        }

        @Override
        public T getValue() {
            throw new IllegalStateException();
        }

        @Override
        public Step<T> nextStep() {
            return nextStep.get();
        }
    }

    public static class IntermediateStep<T> implements Step<T> {
        T value;
        Supplier<Step<T>> nextStep;

        public IntermediateStep(T value, Supplier<Step<T>> nextStep) {
            this.value = value;
            this.nextStep = nextStep;
        }

        @Override
        public T getValue() {
            return value;
        }

        @Override
        public Step<T> nextStep() {
            return nextStep.get();
        }
    }

    public static class EndStep<T> implements Step<T> {
        T value;

        public EndStep(T value) {
            this.value = value;
        }

        @Override
        public T getValue() {
            return value;
        }

        @Override
        public Step<T> nextStep() {
            throw new IllegalStateException();
        }
    }
}

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

Sequence<Integer> sequence = new Sequence<Integer>(() -> {
    int i = 10; 
    yield(i);
    i += 10;
    yield(i);
    i += 10;
    yield(i);
});

Функция, переданная в конструктор Sequence, должна идти от yield к yield только при необходимости, значения локальных переменных должны сохраняться между вызовами sequence.next(). Вот это сохранение стека и номера последней выполненной инструкции называется вытеснение (yield так и переводится на русский) или приостановка.

Континуации

Штука, которая умеет вытесняться, называется Continuation. На русский continuation переводится как 'продолжение', но я буду называть ее континуацией. В Википедия про континуации написано:

Продолжение (англ. continuation) представляет состояние программы в определённый момент, которое может быть сохранено и использовано для перехода в это состояние. Продолжения содержат всю информацию, чтобы продолжить выполнения программы с определённой точки.

Предположим, что у нас уже каким-то волшебным способом реализован механизм континуаций, который представлен следующим интерфейсом. Метод run умеет останавливать свой выполнение. Каждый следующий вызов возобновляет выполнение с последнего yield. Можем думать о континуации как о Runnable, который умеет выполняться по частям.

interface Continuation<T> {
    void run(SequenceScope<T> scope);
}

Континуацию мы будем использовать так:

Sequence<Integer> sequence = new Sequence<>(new Continuation<>() {
    void run(SequenceScope<Integer> scope) {
        int i = 1;
        System.out.println("Continuation start");
        scope.yield(i++);
        System.out.println("Continuation resume");
        scope.yield(i++);
        System.out.println("Continuation resume");
        scope.yield(i++);
        System.out.println("Continuation end");
    }       
});     

for(Integer i: sequence) {
    System.out.println("Next element :" + i);
}

И мы ожидаем получить такой вывод:

Output

Continuation start
Next element: 1
Continuation resume
Next element: 2
Continuation resume
Next element: 3
Continuation end

Sequence при запросе следующиего элемента будет вызывать Continuation.run(scope), который будет выполнять блок кода до следующего yield и вытесняться. Следующий вызов Continuation.run(scope) будет начинать работу с места последнего вытеснения и выполнять код до очередного yield. Код Sequence может быть таким:

class Sequence implements Iterator<T>, SequenceScope<T>, Iterable<T> {
    private static final Object STOP = new Object();
    private Object next = STOP;
    private Continuation<T> nextStep;

    public Sequence(Continuation<T> nextStep) {
        this.nextStep = nextStep;
    }

    @Override
    public boolean hasNext() {
        if (next == STOP) {
            nextStep.run(this);
        }
        return next != STOP;
    }

    @Override
    public T next() {
        if (next == STOP) {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
        }

        T result = (T) next;
        next = STOP;
        return result;
    }

    @Override
    void yield(T t) {
        next = t;
    }

    public Iterator<T> iterator() { // сомнительная реализация, но сейчас это не имеет значения
        return this;
    }

}

interface SequenceScope<T> {
    void yield(T t);
}

Все прекрасно, кроме того, что java не умеет останавливать выполнение метода в произвольном месте, чтобы потом продолжить выполнение с места последней остановки. Поэтому нам придется сделать это вручную. Введем поле label, в котором будем хранить номер последнего вызванного yield.

class IntegerSequenceContinuation implements Continuation<Integer> {
    private int label = 0;
    private int i = 0;
    void run(SequenceScope<Integer> scope) {
        int i = this.i;
        switch (label) {
            case 0:
                System.out.println("Continuation start");
                scope.yield(i++);
                label = 1;
                this.i = i;
                return;
            case 1:
                System.out.println("Continuation resume");
                scope.yield(i++);
                label = 2;
                this.i = i;
                return;
            case 2:
                System.out.println("Continuation resume");
                scope.yield(i++);
                label = 3;
                this.i = i;
                return;
            case 3:
                System.out.println("Continuation end");
                label = 4;
            default:
                throw new RuntimeException();
        }
    }
}

У нас получилась state machine (конечный автомат), и по большому счету именно это делает котлин в своих корутинах (можете декомпилировать и посмотреть, если, конечно, что-нибудь поймете). У нас есть 4 состояния, каждый вызов run выполняет часть кода и делает переход к следующему состоянию. Локальную переменную i нам приходится сохранять в поле класса. Кроме неоправданной сложности у этого кода есть еще одна проблема: мы можем передать в качестве параметра scope разные значения при каждом вызове run. Поэтому, хорошо бы, и параметр scope сохранить в поле класса при первом вызове, и дальше работать с ним.

Континуация на java у нас реализована, но достаточно странным способом и только в одном экземпляре. Каждый раз писать нечто подобное никто не будет, редактировать такой код сложно, читать такой код сложно. Поэтому конечный автомат мы будем строить уже после компиляции.

Suspendable & Continuation

Как нам понять, завершила ли континуация работу или приостановила? Пусть метод run возвращает специальный объект SUSPEND в случае приостановки.

public interface Continuation<T> {
    Object SUSPEND = new Object() {
        @Override
        public String toString() {
            return "[SUSPEND]";
        }
    };

    T run();
}

Заметим, что я убрал входной параметр у континуации. Мы должны гарантировать, что параметры не будут меняться от вызова к вызову, лучший способ сделать это — удалить их. Пользователю, напротив, нужен параметр scope (он будет много для чего использоваться, но сейчас на его место передается SequenceScope, из которого вызывается наш yield). Кроме того, ни про какой SUSPEND пользователь знать не хочет и не хочет ничего возвращать. Введем интерфейс Suspendable.

public abstract class Suspendable<C extends Scope> {
    abstract public void run(C scope);
}

interface Scope {}

Почему абстрактный класс, а не интерфейс?

Использование класса вместо интерфейса не дает возможность писать лямбды и заставляет писать анонимные классы. Нам будет очень удобно работать в байткоде с континуациями как с классами, потому что в их полях можно сохранить локальные переменные. Но лямбды в байткоде выглядят не как класс. За подробностями идем сюда.

Suspendable это Continuation в дизайн тайме, a Continuation это Suspendable в рантайме. Пользователь пишет код на уровне Suspendable, а низкоуровневый код библиотеки работает с Continuation. Одно в другое превращается после модификации байткода.

Прежде мы говорили про вытеснение после вызова yield, но в будущем нам надо будет вытесняться и после некоторых других методов. Будем помечать такие методы аннотацией @Suspend. Это применимо и к самому yield:

public class SequenceScope<T> implements Scope {
    @Suspend
    public void yield(T t) {...}
}

Помним, что континуации у нас будут построены на конечных автоматах. Остановимся здесь немного подробнее. Конечным автомат называется, потому что у него конечное количество состояний. Для хранения текущего состояния будем использовать специальное поле label. Изначально поле label равно 0 — нулевое (начальное) состояние. Каждый вызов Continuation.run будет выполнять какой-то код и переходить в какое-то состояние (в любое кроме начального). После каждого перехода континуация должна сохранить все локальные переменные, номер текущего состояния и выполнить return SUSPEND. Переход к конечному состоянию будет обозначаться return null (в следующих статьях мы будем возвращать не только null). Вызов Continuation.run из конечного состояния должен завершаться исключением ContinuationEndException.

Итак, пользователь пишет код в Suspendable, после компиляции он превращается в Continuation, с которым работает библиотека, и, в частности, наши генераторы. Создание нового генератора для пользователя выглядит так:

Sequence<Integer> seq = new Sequence(new Suspendable() {...});

Но самому генератору нужна континуация, ведь ему нужно проинициализировать поле Continuation<T> nextStep;. Для получения Continuation из Suspendable в коде я написал специальный класс Magic.

package microutine.core;

import microutine.coroutine.CoroutineScopeImpl;

import java.lang.reflect.Field;

public class Magic {
    public static final String SCOPE = "scope$S";

    private static <C extends Scope, R> Continuation<R> createContinuation(Suspendable<C> suspendable, C scope) {
        try {
            Field contextField = suspendable.getClass().getDeclaredField(SCOPE);
            contextField.setAccessible(true);

            if (contextField.get(suspendable) != null)
                throw new IllegalArgumentException("Continuation already created");

            contextField.set(suspendable, scope);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }

        return getContinuation(suspendable);
    }

    public static <R, C extends Scope> Continuation<R> getContinuation(Suspendable suspendable) {
        if (getScope(suspendable) == null)
            throw new RuntimeException("No continuation created for provided suspendable");
        //noinspection unchecked
        return ((Continuation<R>) suspendable);
    }

    private static Scope getScope(Suspendable suspendable) {
        try {
            Field contextField = suspendable.getClass().getDeclaredField(SCOPE);
            contextField.setAccessible(true);
            return (Scope) contextField.get(suspendable);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}

Как эта магия работает? Параметром scope через рефлексию инициализируется поле scope$S (синтетическое поле, которое мы создадим уже в байткоде). Инициализируется континуация единственный раз в createContinuation, и повторная попытка инициализации приведет к эксепшну. Дальше происходит обыкновенное приведение типа к Continuation. Вообще я вас обманул, вся магия не здесь. Раз такое приведение типа возможно, то конкретный переданный Suspendable уже реализует Continuation. И произошло это во время компиляции.

Структура проекта

Проект будет состоять из трех частей:

Код библиотеки (Низкоуровневый и высокоуровневый API)
Тесты (Фактически, только в них сейчас можно использовать это библиотеку)
Конвертер Suspendable -> Continuation (Реализован в виде gradle таски в gradle buildSrc)

Так как конвертер пока что находится в buildSrc, использовать его где-то за пределами самой библиотеки будет невозможно. Но пока нам это и не надо. В будущем у нас будет два варианта: вынести его в отдельный градл плагин, или сделать свой java agent (как это делает Quasar) и выполнять трансформации в рантайме.

build.gradle

plugins {
    id "java"
}

group 'microutines'
version '1.0-SNAPSHOT'

sourceCompatibility = 1.8

task processYield(type: microutine.ProcessSuspendableTask) {
    classPath = compileJava.outputs.files + compileJava.classpath
    inputs.files(compileJava.outputs.files)
}

task processTestYield(type: microutine.ProcessSuspendableTask) {
    classPath = compileJava.outputs.files + compileTestJava.classpath
    inputs.files(compileTestJava.outputs.files)
}

compileJava.finalizedBy(processYield) // после компиляции запускаем байткод модификации
compileTestJava.finalizedBy(processTestYield)

repositories {
    mavenCentral()
}

dependencies {
    testCompile group: 'junit', name: 'junit', version: '4.12'
    compile group: 'junit', name: 'junit', version: '4.12'
}

Конвертацией Suspendable в Continuation будет заниматься градл таска ProcessSuspendableTask. В классе градл таски нет ничего интересного, она просто отбирает нужные классы и отправляет их на преобразование в класс SuspendableConverter. Именно он нас сейчас и интересует.

Генерация байткода

Для работы с байткодом будем использовать библиотеку OW2 ASM. Библиотека работает по принципу SAX парсера. Мы создаем новый ClassReader, скармливаем ему скомпилированный класс в виде массива байтов, и вызываем метод accept(ClassVisitor visitor). ClassReader будет парсить байткод и вызывать соответствущие методы у переданного визитора (visitMethod, visitClass, visitInsn). Визитор может работать в режиме адаптера и делегировать вызовы следующему визитору. Обычно, последним визитором является ClassWriter, в котором формируется конечный байткод. Если задача нелинейная (у нас как раз такая), может потребоваться несколько проходов по классу. Другой подход, предоставляемый asm — записать класс в специальный ClassNode, и делать преобразования уже над ним. Первый подход быстрее, но может не подойти для решений нелинейных задач, поэтому я использовал оба подхода.

Преобразованием Suspendable в Continuation занимаются 3 класса:

SuspendInfoCollector — анализирует метод Suspendable.run, собирает информацию о всех вызовах @Suspend методов и об используемых локальных переменных.
SuspendableConverter — создает нужные поля, меняет сигнатуру и дескриптор метода Suspendable.run, чтобы получить Continuation.run.
SuspendableMethodConverter — преобразовывает код метода Suspendable.run. Дописывает код сохранения и восстановления локальных переменных, сохранения текущего состояния в поле label и перехода к нужной инструкции.

Опишем некоторые моменты поподробней.

Поиск метода run выглядит вот так:

MethodNode method = classNode.methods.stream()
        .filter(methodNode -> methodNode.name.equals("run") && (methodNode.access & Opcodes.ACC_BRIDGE) == 0)
        .findFirst()
        .orElseThrow(() -> new RuntimeException("Unable to find method to convert"));

Ожидается, что в конвертируемом классе будет два метода run, и один из них с модификатором bridge (что это такое читаем здесь). Нас интересует метод без модификатора.

В JVM байткоде условный (и безусловный) переход можно выполнить в любое место. ASM имеет специальную абстракцию Label (метка), которая представляет собой позицию в байткоде. По всему коду после каждого вызова @Suspend методов мы расставим метки, к которым будем делать условный переход в начале метода run.


@Override
    public void visitCode() { // событие начала метода
        super.visitCode();

        Label startLabel = new Label();

        super.visitVarInsn(Opcodes.ALOAD, THIS_VAR_INDEX); // Помещаем в стек this
        super.visitFieldInsn(Opcodes.GETFIELD, myClassJvmName, "label$S$S", "I");  //Запрашиваем поле label$S$S
        super.visitVarInsn(Opcodes.ISTORE, labelVarIndex); // Сохраняем поле в локальную переменную

        super.visitVarInsn(Opcodes.ILOAD, labelVarIndex); // помещаем переменную label в стек
        super.visitIntInsn(Opcodes.BIPUSH, 0); // помещаем 0 в стек
        super.visitJumpInsn(Opcodes.IF_ICMPEQ, startLabel); // делаем условный переход к метке startLabel если два последних значения в стеке равны (label == 0)

        for (int i = 0; i < numLabels; i++) { // делаем тоже самое, но для следующих меток
            super.visitVarInsn(Opcodes.ILOAD, labelVarIndex);
            super.visitIntInsn(Opcodes.BIPUSH, i + 1);
            super.visitJumpInsn(Opcodes.IF_ICMPEQ, labels[i]);
        }

        super.visitTypeInsn(Opcodes.NEW, "microutine/core/ContinuationEndException"); // run был вызван после завершения работы континуации, выкидываем эксепшн
        super.visitInsn(Opcodes.DUP);
        super.visitMethodInsn(Opcodes.INVOKESPECIAL, "microutine/core/ContinuationEndException", "<init>", "()V", false);
        super.visitInsn(Opcodes.ATHROW);

        super.visitLabel(startLabel); // метка, после которой начинается пользовательский код 
    }

Расставляем метки после вызовов @Suspend методов.

@Override
public void visitMethodInsn(int opcode, String owner, String name, String descriptor, boolean isInterface) {
    boolean suspendPoint = Utils.isSuspendPoint(classLoader, owner, name);

    super.visitMethodInsn(opcode, owner, name, descriptor, isInterface);
    if (suspendPoint) {
        super.visitVarInsn(Opcodes.ALOAD, THIS_VAR_INDEX); // помещаем в стек this
        super.visitIntInsn(Opcodes.BIPUSH, suspensionNumber); // помещаем номер метки, в которую вернемся в следующий раз
        super.visitFieldInsn(Opcodes.PUTFIELD, myClassJvmName, "label$S$S", "I"); // сохранем ее в поле label$S$S

        saveFrame(); // сохраняем локальные переменные

        suspend(); 
        super.visitLabel(labels[suspensionNumber - 1]); // метка, в которую мы вернемся 
        restoreFrame(); // восстанавливаем локальные переменные
        suspensionNumber++;
    }
}

private void suspend() {
    super.visitFieldInsn(Opcodes.GETSTATIC, "microutine/core/Continuation", "SUSPEND", "Ljava/lang/Object;"); // помещаем в стек Continuation.SUSPEND
    super.visitInsn(Opcodes.ARETURN); // возвращаем его
}

Тесты

Напишем генератор, который выдает подряд три числа.

testIntSequence

public class YieldTest {
    @Test
    public void testIntSequence() {
        Sequence<Integer> sequence = new Sequence<Integer>(new SequenceSuspendable<Integer>() {
            @Override
            public void run(SequenceScope<Integer> scope) {
                scope.yield(10);
                scope.yield(20);
                scope.yield(30);
            }
        });

        List<Integer> list = new ArrayList<>();
        for (Integer integer : sequence) {
            list.add(integer);
        }

        assertEquals(10, (int) list.get(0));
        assertEquals(20, (int) list.get(1));
        assertEquals(30, (int) list.get(2));
    }
}

Сам тест ничего интересного не представляет, зато достаточно интересно декомпилировть class файл.

testIntSequence decompiled

public class YieldTest {
    public YieldTest() {
    }

    @Test
    public void testIntSequence() {
        class NamelessClass_1 extends SequenceSuspendable<Integer> implements Continuation {
            private SequenceScope scope$S;

            NamelessClass_1() {
            }

            public Object run(Object var1) {
                int label = this.label$S$S;
                SequenceScope var2;
                if (label != 0) {
                    if (label != 1) {
                        if (label != 2) {
                            if (label != 3) {
                                throw new ContinuationEndException();
                            } else {
                                var2 = this.scope$S;
                                this.label$S$S = 4;
                                return null;
                            }
                        } else {
                            var2 = this.scope$S;
                            this.yield(30);
                            this.label$S$S = 3;
                            this.scope$S = var2;
                            return Continuation.SUSPEND;
                        }
                    } else {
                        var2 = this.scope$S;
                        this.yield(20);
                        this.label$S$S = 2;
                        this.scope$S = var2;
                        return Continuation.SUSPEND;
                    }
                } else {
                    var2 = this.scope$S;
                    this.yield(10);
                    this.label$S$S = 1;
                    this.scope$S = var2;
                    return Continuation.SUSPEND;
                }
            }
        }

        Sequence<Integer> sequence = new Sequence(new NamelessClass_1());
        List<Integer> list = new ArrayList();
        Iterator var3 = sequence.iterator();

        while(var3.hasNext()) {
            Integer integer = (Integer)var3.next();
            list.add(integer);
        }

        Assert.assertEquals(10L, (long)(Integer)list.get(0));
        Assert.assertEquals(20L, (long)(Integer)list.get(1));
        Assert.assertEquals(30L, (long)(Integer)list.get(2));
    }
}

Код очень сильно раздулся, большинство инструкций — это сохранение и восстановление стекового кадра (локальных переменных). Однако, он работает. Приведенный пример отлично бы работал и без ленивой генерации. Рассмотрим пример посложнее.

fibonacci

public class YieldTest {
    @Test
    public void fibonacci() {
        Sequence<Integer> sequence = new Sequence<>(new Suspendable<Integer>() {
            @Override
            public void run(SequenceScope<Integer> scope) {
                scope.yield(1);
                scope.yield(1);

                int a = 1;
                int b = 1;

                while (true) {
                    b += a;
                    scope.yield(b);
                    a += b;
                    scope.yield(a);
                }
            }
        });

        //noinspection OptionalGetWithoutIsPresent
        Integer tenthFibonacci = StreamSupport.stream(sequence.spliterator(), false)
                .skip(9).findFirst().get();

        assertEquals(55, ((int) tenthFibonacci));
    }
}

Приведенный код генерирует бесконечную последовательность фибоначчи. Компилируем и декомпилируем:

fibonacci decompiled

public class YieldTest {
    public YieldTest() {
    }

     @Test
     public void fibonacci() {
         class NamelessClass_1 extends SequenceSuspendable<Integer> implements Continuation {
             private SequenceScope scope$S;
             private int aa$S;
             private int ba$S;

             NamelessClass_1() {
             }

             public Object run(Object var1) {
                 int label = this.label$S$S;
                 SequenceScope var2;
                 if (label != 0) {
                     if (label != 1) {
                         int var3;
                         int var4;
                         if (label != 2) {
                             if (label == 3) {
                                 var2 = this.scope$S;
                                 var3 = this.aa$S;
                                 var4 = this.ba$S;
                                 var3 += var4;
                                 var2.yield(var3);
                                 this.label$S$S = 4;
                                 this.scope$S = var2;
                                 this.aa$S = var3;
                                 this.ba$S = var4;
                                 return Continuation.SUSPEND;
                             }

                             if (label != 4) {
                                 throw new ContinuationEndException();
                             }

                             var2 = this.scope$S;
                             var3 = this.aa$S;
                             var4 = this.ba$S;
                         } else {
                             var2 = this.scope$S;
                             var3 = 1;
                             var4 = 1;
                         }

                         var4 += var3;
                         var2.yield(var4);
                         this.label$S$S = 3;
                         this.scope$S = var2;
                         this.aa$S = var3;
                         this.ba$S = var4;
                         return Continuation.SUSPEND;
                     } else {
                         var2 = this.scope$S;
                         var2.yield(1);
                         this.label$S$S = 2;
                         this.scope$S = var2;
                         return Continuation.SUSPEND;
                     }
                 } else {
                     var2 = this.scope$S;
                     var2.yield(1);
                     this.label$S$S = 1;
                     this.scope$S = var2;
                     return Continuation.SUSPEND;
                 }
             }
         }

         Sequence<Integer> sequence = new Sequence(new NamelessClass_1());
         Integer tenthFibonacci = (Integer)StreamSupport.stream(sequence.spliterator(), false).skip(9L).findFirst().get();
         Assert.assertEquals(55L, (long)tenthFibonacci);
     }
}

Понять что делает декомпилированный класс достаточно сложно. Как и в прошлый раз, большинство инструкций гоняют туда сюда локальные переменные. Некоторые из присвоений бесполезные, и переменные сразу перетираются другими значениями. Для решения этой проблемы требуется более глубокий анализ байткода, который сейчас мы делать не будем.

Одной из интересных особенностей полученного кода является отсутствие цикла while, хотя он есть в исходном коде. Ничего удивительного в этом нет. Тело цикла состоит из двух состояний конечного автомата. В конце тела цикла в байткоде должен стоять безусловный переход к коду проверки условия, но у нас оно 'разбито' двумя return SUSPEND.

Резюме

Задача, которую я поставил, на мой взгляд, выполнена весьма хорошо. Мы реализовали возможность писать ленивые генераторы через yield. Это может быть очень удобно как в примере с числами фибоначчи, но реальный код, который мы получаем на выходе — монструозен, непонятен и неоптимален. Проблемой я бы назвал только неоптимальность, но решать ее (по крайней мере ближайшее время) мы не будем. Можно понадеяться, что разогретый JIT компилятор сам пропустит бесполезные присвоения. Кроме yield я реализовал yieldAll — метод, который позволяет вкладывать одну последовательность в другую, но я не стал разбирать принцип его работы, потому что он прост до безобразия и без проблем реализуется поверх всего того, что мы уже сделали. Если все написанное до этого момента вам понятно, то вы без труда разберетесь сами, если загляните на гитхаб.

Самая сложная часть всей библиотеки — континуации — практически полностью реализована, и фактически является синтаксическим сахаром. Построение генераторов поверх континуаций в принципе дело достаточно простое, а для создания корутин осталось уже не так много. Я надеюсь, что уже на этом этапе ясна связь корутин и генераторов: и там и там пишется последовательный код, который выполняется асинхронно.

Теги:

Хабы: