Как и почему React Fiber использует связанные списки для обхода дерева компонентов

Оригинальный адрес:Как и почему React использует связанный список в Fiber для обхода дерева компонентов

Оригинальный автор:Max Koretskyi

Перевод с:Команда облачных переводчиков Alibaba

Ссылка на перевод:GitHub.com/dawn-patted/he…

Переводчик:судя по небу

Корректор:также дерево,облако сна

Основной алгоритм работы цикла в планировщике React

Диаграмма рабочего цикла из замечательной конференции ReactConf 2017 Лина Кларка.речь

Чтобы просвещать себя и сообщество, я провожу много времени вобратный инжиниринг веб-технологийи напишите о своих выводах. В прошлом году я в основном сосредоточился на исходном коде Angular, опубликовав крупнейшую публикацию Angular в Интернете —Angular-In-Depth.Теперь я вложил свои основные усилия в React.обнаружение измененийЭто стало основной областью моих знаний в Angular, и, проявив немного терпения и отладки, я надеюсь вскоре достичь этого уровня в React. В React механизм обнаружения изменений часто называют «согласованием» или «рендерингом», а Fiber — его последней реализацией. Благодаря своей базовой архитектуре он предоставляет возможность реализовать множество интересных функций, таких как выполнение неблокирующего рендеринга, выполнение обновлений на основе приоритета, предварительный рендеринг контента в фоновом режиме и т. д. Эти характеристикиПараллельная философия Reactизвестный какразрезание времени.

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

Если вы сегодня погуглите «React Fiber», вы увидите много статей в результатах поиска. но в дополнение кЗаметки Эндрю Кларка, все статьи являются достаточно высокоуровневыми интерпретациями. В этой статье я буду ссылаться на заметки Эндрю Кларка,Подробно опишите некоторые особенно важные концепции в Fiber.. Когда мы закончим, у вас будет достаточно знаний, чтобы понятьОчень хороший доклад Лин Кларк на ReactConf 2017Схема рабочего цикла в .Вот разговор, который вам нужно увидеть. Однако после того, как вы потратите немного времени на чтение этой статьи, вам будет легче понять.

Этот пост открывает серию статей о внутренней реализации React Fiber.Около 70% того, что я узнал, было получено благодаря внутренней реализации, помимо прочтения трех статей о координации и механике рендеринга.

Давайте начнем!

Основание

Архитектура Fiber состоит из двух основных фаз: согласование/рендеринг и фиксация. В исходном коде этап координации часто называют «фазой рендеринга». Это этап, на котором React проходит дерево компонентов и:

Обновление состояния и свойств
Вызов хуков жизненного цикла
получить компонентchildren
объединить их с предыдущимchildrenсравнение
и выяснить, какие обновления DOM необходимо выполнить

Все эти действия называются заданиями в Fiber.Тип работы, которую необходимо выполнить, зависит от типа элемента React. Например, дляClass ComponentReact должен создать экземпляр класса, однако дляFunctional ComponentНо не нужен. Если Вы заинтересованы,это здесьВы можете увидеть все типы заданий в Fiber. Именно об этих действиях говорит Эндрю:

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

что именнослишком много казней одновременно? Ну, в принципе, если бы ReactСинхронизироватьПройдитесь по всему дереву компонентов и выполните задачи для каждого компонента, он может выполняться более 16 мс, чтобы код приложения выполнил свою логику. Это приведет к пропущенным кадрам, что приведет к негладкому изображению.

Так есть хороший способ?

Новые браузеры (и React Native) реализуют API, которые помогают с этим...

Новый API, который он упомянул,requestIdleCallbackГлобальная функция, которую можно использовать для постановки в очередь функций, которые вызываются, когда браузер бездействует. Вот как вы будете его использовать:

requestIdleCallback((deadline)=>{
    console.log(deadline.timeRemaining(), deadline.didTimeout)
});

Если я сейчас открою консоль и выполню приведенный выше код, Chrome напечатает49.9 false. это в основном говорит мне, что у меня есть49.9msделать любую работу, которую мне нужно сделать, и я не использовал все отведенное мне время, иначеdeadline.didTimeoutбудетtrue. пожалуйста, помнитеtimeRemainingМожет измениться, как только браузеру будет поручена какая-то работа, поэтому его следует постоянно проверять.

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

Теперь, если мы поместим все действия, которые React выполняет с компонентом, в функциюperformWorkи использоватьrequestIdleCallbackЧтобы запланировать задание, наш код может выглядеть так:

requestIdleCallback((deadline) => {
    // 当我们有时间时，为组件树的一部分执行工作    
    while ((deadline.timeRemaining() > 0 || deadline.didTimeout) && nextComponent) {
        nextComponent = performWork(nextComponent);
    }
});

Мы выполняем работу над одним компонентом и возвращаем ссылку на следующий компонент для работы. если не потомуПредыдущая реализация алгоритма координацииКак показано в, вы не можете синхронно обрабатывать все дерево компонентов, это сработает. Вот о чем говорит Андрей:

Чтобы использовать эти API, вам нужен способ разбить работу рендеринга на дополнительные единицы.

Итак, чтобы решить эту проблему, React пришлось заново реализовать алгоритм обхода дерева,От синхронной рекурсивной модели, основанной на встроенных стеках, к асинхронной модели со связанными списками и указателями.. Вот что Андрей написал здесь:

Если вы полагаетесь только на [встроенный] стек вызовов, он будет работать до тех пор, пока стек не станет пустым. . . Было бы неплохо, если бы мы могли прерывать стек вызовов по желанию и управлять фреймами стека вручную? Вот для чего предназначен React Fiber.Fiber — это повторная реализация стека, специально для компонентов React.. Вы можете думать об одном волокне как о кадре виртуального стека.

Это то, что я собираюсь рассказать сейчас.

Что сказать о стеке

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

В информатике,стек вызововпредставляет собой структуру данных стека, в которой хранится информация об активных подпрограммах компьютерной программы... основная причина существования стеков вызовов состоит в том, чтобы отслеживать, куда каждая активная подпрограмма должна возвращать управление после завершения выполнения... стеки вызовов определяются Состав кадра стека... Каждый кадр стека соответствует вызову подпрограммы, которая еще не завершилась. Например, если подпрограммаDrawSquareназываетсяDrawLineподпрограмма в данный момент выполняется, вершина стека вызовов может выглядеть так, как показано на рисунке ниже.

Почему стек связан с React?

Как мы определили в первой части этой статьи, React проходит по дереву компонентов на этапе согласования/рендеринга и выполняет некоторую работу для компонента. Предыдущие реализации координатора использовали модель синхронной рекурсии, которая опиралась на встроенный стек для обхода дерева.Официальная документация по согласованиюОписывает процесс и много говорит о рекурсии:

По умолчанию при рекурсии дочерних элементов узла DOM React будет перебирать оба списка дочерних элементов одновременно и генерировать мутации, когда есть разница.

Если подумать,Каждый рекурсивный вызов добавляет кадр в стек. и синхронно. Предположим, у нас есть следующее дерево компонентов:

использоватьrenderФункции представлены в виде объектов. Вы можете думать о них как об экземплярах компонентов:

const a1 = {name: 'a1'};
const b1 = {name: 'b1'};
const b2 = {name: 'b2'};
const b3 = {name: 'b3'};
const c1 = {name: 'c1'};
const c2 = {name: 'c2'};
const d1 = {name: 'd1'};
const d2 = {name: 'd2'};

a1.render = () => [b1, b2, b3];
b1.render = () => [];
b2.render = () => [c1];
b3.render = () => [c2];
c1.render = () => [d1, d2];
c2.render = () => [];
d1.render = () => [];
d2.render = () => [];

React необходимо перебрать дерево и выполнить работу для каждого компонента. Для простоты все, что нужно сделать, — это вывести имя текущего компонента и получить его дочерние элементы. Вот как мы можем сделать это рекурсивно.

рекурсивный обход

Основная функция для обхода дерева называетсяwalk, реализуется следующим образом:

walk(a1);

function walk(instance) {
    doWork(instance);
    const children = instance.render();
    children.forEach(walk);
}

function doWork(o) {
    console.log(o.name);
}

Вот мой результат:

a1, b1, b2, c1, d1, d2, b3, c2

Если вы не уверены в рекурсии, проверьтеМоя подробная статья о рекурсии.

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

Так как же React реализует алгоритм обхода дерева без рекурсии? Он использует алгоритм обхода дерева односвязного списка. Это позволяет приостановить обход и остановить рост стека.

обход связанного списка

Мне посчастливилось найти Себастьяна Маркбоге вздесьОбзор основных моментов алгоритма. Для реализации алгоритма нам понадобится структура данных с 3 полями:

child — ссылка на первый дочерний узел
sibling — ссылка на первого брата
return — ссылка на родительский узел

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

На следующей схеме показана иерархия объектов, связанных связными списками, и типы связей между ними:

Начнем с определения конструктора для нашего пользовательского узла:

class Node {
    constructor(instance) {
        this.instance = instance;
        this.child = null;
        this.sibling = null;
        this.return = null;
    }
}

и функция, которая берет массив узлов и связывает их вместе. мы используем его для связиrenderДочерний узел, возвращаемый методом:

function link(parent, elements) {
    if (elements === null) elements = [];

    parent.child = elements.reduceRight((previous, current) => {
        const node = new Node(current);
        node.return = parent;
        node.sibling = previous;
        return node;
    }, null);

    return parent.child;
}

Функция проходит массив узлов от последнего узла вперед, связывая их в один связанный список. Он возвращает ссылку на первый родственный узел. Вот простая демонстрация того, как это работает:

const children = [{name: 'b1'}, {name: 'b2'}];
const parent = new Node({name: 'a1'});
const child = link(parent, children);

// 下面两行代码的执行结果为true
console.log(child.instance.name === 'b1');
console.log(child.sibling.instance === children[1]);

Мы также реализуем вспомогательную функцию, которая выполняет некоторую работу для узла. В нашем случае будет напечатано имя компонента. Но в дополнение к этому, он также получает компонентchildrenи соедините их вместе:

function doWork(node) {
    console.log(node.instance.name);
    const children = node.instance.render();
    return link(node, children);
}

Хорошо, теперь мы готовы реализовать основной алгоритм обхода. Это реализация с приоритетом родителей и глубиной. Вот код с полезными комментариями:

function walk(o) {
    let root = o;
    let current = o;

    while (true) {
        // 为节点执行工作，获取并连接它的children
        let child = doWork(current);

        // 如果child不为空, 将它设置为当前活跃节点
        if (child) {
            current = child;
            continue;
        }

        // 如果我们回到了根节点，退出函数
        if (current === root) {
            return;
        }

        // 遍历直到我们发现兄弟节点
        while (!current.sibling) {

            // 如果我们回到了根节点，退出函数
            if (!current.return || current.return === root) {
                return;
            }

            // 设置父节点为当前活跃节点
            current = current.return;
        }

        // 如果发现兄弟节点，设置兄弟节点为当前活跃节点
        current = current.sibling;
    }
}

Хотя реализация кода не особенно сложна для понимания, вам может потребоваться немного запустить код, чтобы понять его.сделай это здесь. Идея состоит в том, чтобы сохранить ссылку на текущий узел и переназначить его, когда мы идем вниз по дереву, пока не достигнем конца ветки. Затем мы используемreturnУказатель возвращает корневой узел.

Если мы теперь рассмотрим стек вызовов этой реализации, мы увидим следующее изображение:

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

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

Fiber — это повторная реализация стека, специально для компонентов React. Вы можете думать об одном волокне как о кадре виртуального стека.

Итак, теперь мы управляем стеком, сохраняя ссылку на узел, который действует как верхний фрейм стека:

function walk(o) {
    let root = o;
    let current = o;

    while (true) {
            ...

            current = child;
            ...

            current = current.return;
            ...

            current = current.sibling;
    }
}

Мы можем остановить обход в любой момент и возобновить его позже. Это именно то, чего мы хотим добиться, чтобы иметь возможность использовать новыеrequestIdleCallbackДело об API.

Рабочие циклы в React

Вот как реализовать рабочий цикл в Reactкод:

function workLoop(isYieldy) {
    if (!isYieldy) {
        // Flush work without yielding
        while (nextUnitOfWork !== null) {
            nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
        }
    } else {
        // Flush asynchronous work until the deadline runs out of time.
        while (nextUnitOfWork !== null && !shouldYield()) {
            nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
        }
    }
}

Как видите, он прекрасно соответствует упомянутому выше алгоритму.nextUnitOfWorkПеременная в качестве верхнего фрейма, содержащая ссылку на текущий узел Fiber.

Этот алгоритм можетСинхронноПройдите по дереву компонентов и выполните работу (nextUnitOfWork) для каждой точки Fiber в дереве. Обычно это относится к так называемым интерактивным обновлениям, вызванным событиями пользовательского интерфейса (клики, ввод и т. д.). или это можетасинхронноПройдитесь по дереву компонентов и проверьте, осталось ли время после работы с узлом Fiber. функцияshouldYieldВозврат на основеdeadlineDidExpireа такжеdeadlineРезультат переменных, которые постоянно обновляются по мере того, как React выполняет работу для узла Fiber.

здесьПодробное введениеpeformUnitOfWorkфункция.

Я пишу серию статей, в которых погружаюсь в детали реализации алгоритма обнаружения изменений Fiber в React.

пожалуйста, продолжайтеTwitterа такжеMediumПодпишитесь на меня, и я сообщу, как только статья будет готова.

Спасибо за прочтение! Если вам понравился этот пост, пожалуйста, нажмите кнопку «Мне нравится» ниже 👏. Это много значит для меня и помогает другим увидеть этот пост.