Как Fiber в React использует связанный список для обхода дерева компонентов
Для просвещения сообщества, да и своего собственного, я провёл немало времени занимаясь реверс-инжинирингом веб-технологий и описывая свои находки во время этого процесса. В последний год я, в основном, фокусировался на исходниках Angular, что в итоге вылилось в крупнейшую публикацию об Angular, доступную в сети — Angular-in-Depth. Теперь настало время углубиться в React. Отслеживание изменений — это то о чем я знаю больше всего, если говорить об Angular, и с помощью усидчивости и усиленного дебаггинга, я рассчитываю достичь такого же уровня в React.
Механизм отслеживания изменений в React обычно называют согласованием или рендерингом, и Fiber — его новейшая реализация. Благодаря лежащей в его основе архитектуре, он даёт возможность внедрить массу любопытных вещей, таких, например, как выполнение неблокирующего рендеринга, применение обновлений, базирующееся на приоритетности и пре-рендеринг содержимого в фоне. Квантование времени — общее название этих возможностей в терминах парадигмы параллельного выполнения.
Помимо решения проблем непосредственно разработчиков приложений, внутренняя реализация этих механизмов крайне привлекательна с чисто инженерной точки зрения. Исходники — кладезь знаний, благодаря которой мы можем значительно вырасти в профессиональном плане.
Если вы сегодня погуглите “React Fiber”, то обнаружите множество статей. Однако, все они, за исключением заметок Эндрю Кларка, очень поверхностны. В этом материале я предполагаю дать исчерпывающее объяснение некоторых особо важных концепций Fiber. Когда вы закончите чтение, у вас будет достаточно знаний для понимания описания рабочего цикла из прекрасного выступления Лин Кларк на ReactConf 2017. Вы просто обязаны его увидеть. Тем не менее, оно будет значительно полезнее после того, как вы проведёте некоторое время за изучением исходников.
Этот пост — открывающий в серии “Внутренности React Fiber” (оригинал). Полагаю, что понял детали реализации процентов на 70, и сейчас у меня в работе находятся ещё три статьи о согласовании и механизме рендеринга.
Давайте начнём!
Готовим реквизит
Архитектура Fiber предусматривает два основных этапа: согласование/рендер и коммит. В исходном коде фаза согласования, как правило, упоминается как “render phase”. Это фаза, во время которой React обходит дерево компонентов и:
- обновляет состояние(state) и свойства(props)
- Вызывает хуки жизненного цикла
- получает детей компонента
- сравнивает их с предыдущим вариантом
- и определяет, какие обновления DOM необходимо произвести
Все эти действия в рамках Fiber именуются “работа”. Тип работы, которую необходимо произвести, зависит от типа React-элемента. К примеру, для компонента-класса React должен создать его экземпляр, в то время как для функционального компонента этого делать не надо. Если вас интересуют подробности, здесь вы можете найти все варианты, доступные для обработки Fiber. Эти действия — именно то, о чём Эндрю говорит здесь:
Проблема при работе с UI состоит в том, что если выполнять очень много работы одновременно, из анимации могут начать выпадать кадры…
Что значит “одновременно”? Ну, если React обходит всё дерево компонентов синхронно и обрабатывает каждый компонент, можно не уложиться в 16 миллисекунд, отведённых на этот процесс. И вот это и приведёт к выпадению кадров и дёрганью картинки.
И как этой беде помочь?
В новейших браузерах (и React Native) реализовано API, помогающее справиться с этой проблемой…
Новое API, о котором говорит Эндрю, это глобальная функция requestIdleCallback, позволяющая добавить функцию в очередь, чтобы вызвать её в период бездействия браузера.
Вот пример использования:
Если вы откроете консоль браузера и выполните этот код, Хром выведет что-то вроде 49.9 false. Эта информация означает, что у меня есть 49.9 мс, для выполнения моей задачи и при этом я не использовал их целиком, ведь в противном случае deadline.didTimeout было бы равно true. Не забудьте, что timeRemaining меняется в зависимости от выполняемой браузером задачи, так что этот показатель нужно постоянно отслеживать.
requestIdleCallbackимеет значительные ограничения и не выполняется достаточно часто, чтобы обеспечить плавную отрисовку UI, так что команде React пришлось внедрить собственную версию этой функциональности.
Теперь, если мы поместим все действия, которые React проделывает с компонентом, внутрь функции performWork и воспользуемся requestIdleCallback, чтобы спланировать выполнение, наш код будет выглядеть следующим образом:
Мы совершаем работу над одним компонентом и возвращаем ссылку на следующий компонент для продолжения. Это будет работать с одним но. Вы не сможете обработать всё дерево компонентов синхронно, как в предыдущей реализации алгоритма согласования. Именно об этой сложности говорит Эндрю:
…чтобы воспользоваться этими API, вы нужен способ разбить рендеринг на выполняемые по отдельности этапы.
Для решения этой проблемы React для обхода дерева был вынужден перейти от синхронной рекурсивной модели, полагающейся на встроенный стек, к асинхронной модели со связанным списком и указателями. Об этом Эндрю пишет здесь:
Если вы полагаетесь на [встроенный] стек, работа будет выполняться, пока стек не станет пуст… Не лучше ли будет, если мы сможем при желании выйти из стека вызовов и манипулировать кадрами стека вручную? Это и есть цель React Fiber. Fiber — реализация стека, предназначенная специально для React-компонентов. Можно думать об единичном fiber как о виртуальном кадре стека.
Именно это я и собираюсь объяснить.
Пара слов о стеке
Полагаю, вы знакомы с понятием стека вызовов. Это именно то, что вы видите при отладке в браузере с помощью точек останова. Здесь уместно привести несколько цитат и диаграмму из Википедии:
В теории вычислительных систем, стек вызовов — структура данных, хранящая информацию об активных подпрограммах компьютерной программы…основная задача стека вызовов — отслеживание того места, куда каждая активная подпрограмма должна вернуть контроль после завершения своего исполнения… Стек вызовов состоит из кадров…Каждый кадр стека соответствует подпрограмме, которая ещё не вернула результат исполнения. К примеру, если подпрограмма под названием
DrawLine, вызванная подпрограммойDrawSquare, в данный момент запущена, верхушка стека вызовов может выглядеть как на картинке ниже.
Как стек относится к React?
Как мы выяснили в первой части статьи, React во время фазы согласования/рендера обходит дерево компонентов и выполняет некоторую работу над отдельными компонентами. Предыдущая реализация согласователя для обхода дерева использовала синхронную рекурсивную модель, полагавшуюся на встроенный стек. Официальная документация, посвящённая согласованию, описывает этот процесс и много времени уделяет рекурсии:
По умолчанию, при рекурсивном обходе детей DOM-узла, React просто проходит по обеим спискам детей одновременно и генерирует изменения, когда обнаруживает разницу между ними.
Нетрудно сообразить, что каждый рекурсивный вызов добавляет в стек один кадр. И делает это синхронно. Предположим, что у нас есть такое дерево компонентов:
Функция render представит его части в виде объектов. Можете думать о них как об экземплярах компонентов:
React должен обойти дерево и выполнить работу для каждого компонента. Для простоты предположим, что работа заключается в том, чтобы напечатать имя текущего компонента и то же самое проделать для его детей. Вот как эту задачу можно решить с помощью рекурсии:
Рекурсивный обход
В нашей реализации основная функция, обходящая дерево, именуется walk.
Вот вывод, который мы получим:
a1, b1, b2, c1, d1, d2, b3, c2Если вы плохо знакомы с рекурсией, прочтите мою статью о ней.
Рекурсивный подход интуитивен и хорошо подходит для обхода деревьев. Однако, как мы уже выяснили, он имеет определённые ограничения. Самое значительное из них — то, что мы не можем разбить процесс на отдельные этапы. Мы не можем прервать работу на определённом компоненте и возобновить её впоследствии. Используя эту реализацию, React просто продолжает обход до тех пор пока не будет обработан последний компонент и стек вызовов не опустеет.
Так что именно сделал React, чтобы алгоритм обхода дерева не использовал рекурсию? Их новый алгоритм обходит дерево при помощи отдельного связанного списка. Такой подход даёт возможность прерывать обход и предотвращает разрастание стека.
Обход связанного списка
Мне повезло обнаружить код алгоритма, набросанный Себастьяном Маркбоге здесь. Чтобы реализовать алгоритм, нам необходима структура данных с тремя полями:
- child — ссылка на первого ребёнка
- sibling — ссылка на первого сиблинга
- return — ссылка на родителя
В контексте нового алгоритма согласования React структура данных с такими полями называется Fiber. Под капотом — это представление React-элемента, содержащее очередь необходимых работ. Больше информации об этом будет в следующих статьях.
Следующая диаграмма демонстрирует иерархию объектов, связанных при помощи списка, и типы отношений между ними:
Таким образом, давайте сначала определим функцию-конструктор узла:
И функцию, принимающую массив узлов и связывающую элементы этого массива. Мы будем использовать её, чтобы связать детей, которых вернёт метод render.
Функция проходит по массиву нод, начиная с последнего элемента и связывает их вместе в один связанный лист. Она возвращает ссылку на первого сиблинга из списка. Ниже демонстрация её работы:
Мы также реализуем вспомогательную функцию, производящую над нодой некоторую работу. В нашем случае, мы собираемся выводить имя компонента. Однако, кроме этого, мы также будем получать детей компонента и связывать их между собой:
Отлично, теперь мы готовы реализовать главный алгоритм обхода. Вот код с полезными комментариями:
Хотя эта реализация не очень уж сложна, вам может захотеться поиграть с ней. Это можно сделать здесь. Основная идея состоит в том, что мы сохраняем ссылку на текущую ноду и переприсваиваем её значение в процессе спуска по дереву, пока не дойдём до конца ветки. Затем мы используем return, чтобы вернуться к общему родителю.
Если теперь мы проверим стек вызовов этой реализации, картина будет примерно следующая:
Легко заметить, что стек не разрастается, пока мы спускаемся по дереву. Но если вызвать debugger внутри функции doWork и вывести имена нод, мы увидим следующее:
Выглядит так же, как стек вызовов в браузере. Таким образом, используя данный алгоритм, мы эффективно заменили браузерную реализацию стека вызовов своей собственной. Вот так это описывает Эндрю:
Fiber — новая реализация стека, предназначенная специально для React-компонентов. Думайте об единственном fiber, как о “виртуальном кадре стека”.
Раз мы теперь контролируем стек, сохраняя ссылку на ноду, ведущую себя как первый кадр:
мы можем остановить обход в любой момент и возобновить его позднее. Это именно тот самый результат, которого мы и желали достичь, чтобы использовать новое API requestIdleCallback.
Рабочий цикл в React
Вот код, реализующий рабочий цикл в React :
Обратите внимание, что он очень похож на алгоритм, описанный в этой статье. Он сохраняет ссылку на текущую fiber-ноду в переменной nextUnitOfWork, которая работает, как первый кадр стека.
Алгоритм может обходить дерево компонентов синхронно и обрабатывать каждую Fiber-ноду в дереве (nextUnitOfWork). Это обычный случай для так называемых интерактивных обновлений, вызываемых событиями UI (щелчок, изменение поля ввода и т.п.). Или же он может обходить компоненты асинхронно, проверяя, осталось ли время после обработки Fiber-ноды. Функция shouldYield возвращает результат, основанный на переменных deadlineDidExpire и deadline, который постоянно обновляются по мере того, как React обрабатывает Fiber-ноды.
Функция performUnitOfWork подробно описана здесь.