Секрет исходного кода React 3 Подробное объяснение алгоритма Diff

React.js
Секрет исходного кода React 3 Подробное объяснение алгоритма Diff

Добро пожаловать на подпискуДемистификация технологии ReactСсылка на код React 16.13.1

Что такое диф

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

  • Над сгибом отображается все дерево DOM.
  • Обновления компонентов локально обновляют дерево DOM на основе измененного состояния.

Так как же React узнает, какие узлы DOM нужно обновить?

существуетпредыдущий пост здесьМы сказали, что вrenderсценаbeginWorkВ функции узел Fiber, сгенерированный последним обновлением, сравнивается с объектом JSX этого обновления (соответствующимClassComponentизthis.renderвозвращаемое значение метода илиFunctionComponentвозвращаемое значение выполнения) для сравнения. Генерируется по результатам сравненияworkInProgress Fiber, то есть обновленный узел Fiber.

говорить простым языком

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

Этот процесс сравнения называется Diff. В этой статье в основном объясняетсяАлгоритм Rect DiffВнутренняя реализация Diff, пожалуйста, обратитесь к простому объяснению DiffРеагировать на документацию

Узкое место Diff и как с ним справляется React

Поскольку сама операция Diff также приведет к потерям производительности, в документации React упоминается, что даже в самых передовых алгоритмах сложность алгоритма полного сравнения двух деревьев до и после составляет O(n 3 ), где n — количество деревьев в дереве количество элементов.

Если бы этот алгоритм использовался в React, вычисления, необходимые для отображения 1000 элементов, составили бы порядка миллиарда. Эта стоимость просто слишком высока.

Чтобы уменьшить сложность алгоритма, в React diff будут установлены три ограничения:

  1. Diff только на родственных элементах. Если узел DOM пересекает иерархию между двумя обновлениями, React не будет пытаться использовать его повторно.

  2. Два разных типа элементов создают разные деревья. если элемент состоит изdivсталиp, React уничтожитdivи его дочерние узлы, и создать новыйpи его дочерние узлы.

  3. Разработчики могут использоватьkeyсвойства, чтобы указать, какие дочерние элементы стабильны при визуализации. Рассмотрим следующий пример:

// 更新前
<div>
    <p key="ka">ka</p>
    <h3 key="song">song</h3>
</div>

// 更新后
<div>
    <h3 key="song">song</h3>
    <p key="ka">ka</p>
</div>

если нетkey, React будет думатьdivПервый дочерний узелpсталиh3, второй дочерний узел состоит изh3сталиp. Это соответствует настройке ограничения 2 и приведет к уничтожению и созданию нового.

Но когда мы используемkeyУказав отношения между узлами до и после, React знаетkey === "ka"изpОн все еще существует после обновления, поэтому узлы DOM можно использовать повторно, но порядок необходимо поменять местами.

Это три ограничения, которые React накладывает, чтобы справиться с узкими местами алгоритмической производительности.

Как работает разница

Далее мы посмотрим на конкретную реализацию Diff. Мы развлекаемся от функции входаreconcileChildFibersНачнем, а потом посмотрим, как реализованы разные типы Diff.

Введение в функцию ввода функции Diff

Давайте посмотрим на входную функцию Diff, не пугайтесь длины кода, на самом деле логика очень проста - внутри функции она будет основываться наnewChildТипы вызывают разные функции-обработчики.

// 根据newChild类型选择不同diff函数处理
function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
): Fiber | null {

  const isObject = typeof newChild === 'object' && newChild !== null;

  if (isObject) {
    // object类型，可能是 REACT_ELEMENT_TYPE 或 REACT_PORTAL_TYPE
    switch (newChild.$typeof) {
      case REACT_ELEMENT_TYPE:
        // 调用 reconcileSingleElement 处理
      // ...其他case
    }
  }

  if (typeof newChild === 'string' || typeof newChild === 'number') {
    // 调用 reconcileSingleTextNode 处理
  }

  if (isArray(newChild)) {
    // 调用 reconcileChildrenArray 处理
  }

  // 一些其他情况调用处理函数

  // 以上都没有命中，删除节点
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}

здесьnewChildПараметр представляет собой обновленный объект JSX (соответствующийClassComponentизthis.renderвозвращаемое значение метода илиFunctionComponentвозвращаемое значение выполнения)

Как реализованы различные типы различий

Мы можем разделить Diff на две категории по количеству узлов на одном уровне:

  1. когдаnewChildТипobject,number,string, представляющий только один узел на одном уровне
  2. когдаnewChildТипArray, есть несколько узлов на одном уровне

Далее мы обсудим их отдельно.

Случай 1: Diff только с одним узлом на том же уровне

Для одного узла мы начинаем с типаobjectНапример, войдетreconcileSingleElement

  const isObject = typeof newChild === 'object' && newChild !== null;

  if (isObject) {
    // 对象类型，可能是 REACT_ELEMENT_TYPE 或 REACT_PORTAL_TYPE
    switch (newChild.$typeof) {
      case REACT_ELEMENT_TYPE:
        // 调用 reconcileSingleElement 处理
      // ...其他case
    }
  }

Эта функция будет делать следующее:

Второй шагОпределите, можно ли повторно использовать узел DOM, давайте посмотрим, как судить по коду:

Не бойтесь, логика тоже очень проста

function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement
): Fiber {
  const key = element.key;
  let child = currentFirstChild;
  
  // 首先判断是否存在对应DOM节点
  while (child !== null) {
    // 上一次更新存在DOM节点，接下来判断是否可复用
    if (child.key === key) {
    
    // ️同学看这里，首先比较key是否相同
      switch (child.tag) {
        // ...省略case
        
        default: {
          if (child.elementType === element.type) {
            // ️同学看这里，key相同后再看type是否相同
            // 如果相同则表示可以复用
            return existing;
          }
          
          // type不同则跳出循环
          break;
        }
      }
      //  key不同或type不同都代表不能复用，会到这里
      // 不能复用的节点，被标记为删除
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  // 创建新Fiber，并返回
}

Помните, что мы только что упомянули, ограничения пресетов React,

Как видно из кода, React в первую очередь судитkeyто же самое, еслиkeyтакое же суждениеtypeНезависимо от того, один и тот же узел DOM, его можно использовать повторно только в том случае, если все они одинаковы.

вопросы по классной практике

Сделаем несколько упражнений для его закрепления:

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

// 习题1 更新前
<div>ka song</div>
// 更新后
<p>ka song</p>

// 习题2 更新前
<div key="xxx">ka song</div>
// 更新后
<div key="ooo">ka song</div>

// 习题3 更新前
<div key="xxx">ka song</div>
// 更新后
<p key="ooo">ka song</p>

// 习题4 更新前
<div key="xxx">ka song</div>
// 更新后
<div key="xxx">xiao bei</div>

.

.

.

.

Учитель объявил ответ:

Упражнение 1: Не установленоkey propПо умолчаниюkey = null;, поэтому ключ до и после обновления один и тот же, обаnull, но до обновленияtypeдляdiv, обновлено доp,typeИзменения нельзя использовать повторно.

Упражнение 2. До и после обновленияkeyменяй, не надо судитьtype, нельзя использовать повторно.

Упражнение 3. До и после обновленияkeyменяй, не надо судитьtype, нельзя использовать повторно.

Упражнение 4. До и после обновленияkeyа такжеtypeНичего не изменилось и может быть использовано повторно.childrenизменения, необходимо обновить дочерние элементы DOM.

Вы все поняли?

Случай 2: сравнение с несколькими элементами на одном уровне

Только что мы представили одноэлементный Diff, теперь рассмотрим, что у нас естьFunctionComponent:

function List () {
    return (
        <ul>
            <li key="0">0</li>
            <li key="1">1</li>
            <li key="2">2</li>
            <li key="3">3</li>
        </ul>
    )
}

Его возвращаемое значение является объектом JSX.childrenСвойство представляет собой не один элемент, а массив из четырех объектов

В этой ситуации,reconcileChildFibersизnewChildПараметрыArray, что соответствует следующей ситуации внутри функции:

  if (isArray(newChild)) {
    // 调用 reconcileChildrenArray 处理
  }

Далее давайте посмотрим, как React обрабатывает различия нескольких элементов на одном уровне.

Подробное объяснение Diff нескольких узлов на одном уровне

Общий обзор

Сначала рассмотрим ситуацию, с которой нам нужно иметь дело:

  • Случай 1 Обновление узла
// 情况1 节点更新

// 之前
<ul>
    <li key="0" className="before">0<li>
    <li key="1">1<li>
</ul>

// 之后情况1 节点属性变化
<ul>
    <li key="0" className="after">0<li>
    <li key="1">1<li>
</ul>

// 之后情况2 节点类型更新
<ul>
    <div key="0">0<li>
    <li key="1">1<li>
</ul>
  • Случай 2 Добавление или уменьшение узла
// 情况2 节点新增或减少

// 之前
<ul>
    <li key="0">0<li>
    <li key="1">1<li>
</ul>

// 之后情况1 新增节点
<ul>
    <li key="0">0<li>
    <li key="1">1<li>
    <li key="2">2<li>
</ul>

// 之后情况2 删除节点
<ul>
    <li key="1">1<li>
</ul>
  • Случай 3 Изменение положения узла
// 情况3 节点位置变化

// 之前
<ul>
    <li key="0">0<li>
    <li key="1">1<li>
</ul>

// 之后
<ul>
    <li key="1">1<li>
    <li key="0">0<li>
</ul>

Diff нескольких элементов на одном уровне должен принадлежать одному или нескольким из трех вышеперечисленных случаев.

Как разработать алгоритм

Если бы мне пришлось разрабатывать алгоритм Diff, первое решение, которое я бы придумал, было бы таким:

  1. Определить, к какому делу относится обновление текущего узла
  2. Если он новый, выполните новую логику
  3. Если это удаление, выполните логику удаления
  4. Если это обновление, выполните логику обновления

Согласно этому плану, на самом деле существует неявная предпосылка:Приоритет различных операций одинаков

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

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

Хотя этот обновленный объект JSXnewChildrenв виде массива, но иnewChildrenКаждое значение сравнивается с последним обновленным узлом Fiber, а одноуровневые узлы узла Fiber определяютсяsiblingСвязанный список указателей.

которыйnewChildren[0]а такжеoldFiberСравнивать,newChildren[1]а такжеoldFiber.siblingСравнивать.

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

По вышеуказанным причинам общая логика алгоритма Diff будет проходить через два раунда обхода.

Первый раунд обхода: обработка обновленных узлов.

Второй раунд обхода: обработайте оставшиеся узлы, которые не являются частью обновления.

первый круг обхода

Первый раунд шагов обхода выглядит следующим образом:

  1. траверсnewChildren,i = 0,БудуnewChildren[i]а такжеoldFiberСравните и оцените, можно ли повторно использовать узел DOM.
  2. Если многоразовый,i++,СравниватьnewChildren[i]а такжеoldFiber.siblingЯвляется ли он многоразовым. Повторите шаг 2, если его можно использовать повторно.
  3. Если не многоразовый, сразу прыгать со всего обхода.
  4. еслиnewChildrenпройдено илиoldFiberпройдено (т.е.oldFiber.sibling === null), выпрыгнуть из траверса.

Когда мы, наконец, завершаем обход, есть два результата:

Результат 1: Если это обход, выскочивший из шага 3,newChildrenне законченный переход,oldFiberДаже не закончил.

взять каштан

В следующем коде можно повторно использовать первые 2 узла,key === 2узелtypeИзменение, не повторное использование, выпрыгнуть из обхода.

В настоящее времяoldFiberоставатьсяkey === 2не пройдено,newChildrenоставатьсяkey === 2,key === 3Не пройден.

// 之前
            <li key="0">0</li>
            <li key="1">1</li>
            <li key="2">2</li>
            
// 之后
            <li key="0">0</li>
            <li key="1">1</li>
            <div key="2">2</div>
            <li key="3">3</li>

Результат 2: Если это обход, выскочивший из шага 4, он может бытьnewChildrenпройдено илиoldFiberпройдены, или все они пройдены одновременно.

приходи еще

// 之前
            <li key="0" className="a">0</li>
            <li key="1" className="b">1</li>
            
// 之后情况1 newChildren与oldFiber都遍历完
            <li key="0" className="aa">0</li>
            <li key="1" className="bb">1</li>
            
// 之后情况2 newChildren没遍历完，oldFiber遍历完
            <li key="0" className="aa">0</li>
            <li key="1" className="bb">1</li>
            <li key="2" className="cc">2</li>
            
// 之后情况3 newChildren遍历完，oldFiber没遍历完
            <li key="0" className="aa">0</li>

С этими двумя результатами мы начинаем второй раунд обхода.

Второй круг обхода

Что касается второго результата, подумайте об этом с умом,newChildrenне закончено,oldFiberЧто значит пройтись?

Старые узлы DOM используются повторно, и в это время добавляются новые узлы, что означает, что новые узлы вставляются в этом обновлении, нам нужно только пройти остальныеnewChildrenОперации вставки выполняются последовательно (Fiber.effectTag = Placement;).

Точно так же мы делаем выводы из одного случая в другой.newChildrenПосле пересечения,oldFiberНе проходил то, что это значит?

ИзбытокoldFiberБольше не существует в этом обновлении, поэтому нужно пройти остальныеoldFiber, выполните операцию удаления последовательно (Fiber.effectTag = Deletion;).

Так как же быть с результатом?newChildrenа такжеoldFiberНи один из них не был пройден, а это значит, что некоторые узлы изменили свое положение в этом обновлении.

接下来，就是Diff算法最精髓的部分！ ! ! !打起精神来，我们胜利在望

Узлы, которые обрабатывают обмен позициями

Поскольку некоторые узлы поменялись позициями, индекс позиции больше нельзя использовать для сравнения узлов до и после, так как же один и тот же узел может соответствовать в двух обновлениях?

Вы, должно быть, подумали, что нам нужно использоватьkeyхарактеристики.

быстро найтиkeyсоответствующийoldFiber, мы удаляем все ожидающиеoldFiberвставить сkeyИмущество является ключевым,Fiberпо стоимостиmap.

const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

пройти оставшиесяnewChildren,пройти черезnewChildren[i].keyможет быть вexistingChildrenнайти вkeyидентичныйoldFiber.

Далее дело в том, постучать по доске

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

Затем мы определяем переменную на входе функции Diff

let lastPlacedIndex = 0;

Эта переменная представляет текущий последний повторно используемый узел, соответствующийoldFiberИндекс места, где он был в последнем обновлении. Мы используем эту переменную, чтобы определить, нужно ли узлу двигаться.

Не сбивает с толку, не бойтесь, учительский каштан опять идет

Здесь мы упрощаем написание, каждая буква представляет собой узел, а значение буквы представляет собой значение узла.key


// 之前
abcd

// 之后
acdb

===第一轮遍历开始===
a（之后）vs a（之前）  
key不变，可复用
此时 a 对应的oldFiber（之前的a）在之前的数组（abcd）中索引为0
所以 lastPlacedIndex = 0;

继续第一轮遍历...

c（之后）vs b（之前）  
key改变，不能复用，跳出第一轮遍历
此时 lastPlacedIndex === 0;
===第一轮遍历结束===

===第二轮遍历开始===
newChildren === cdb，没用完，不需要执行删除旧节点
oldFiber === bcd，没用完，不需要执行插入新节点

将剩余oldFiber（bcd）保存为map

// 当前oldFiber：bcd
// 当前newChildren：cdb

继续遍历剩余newChildren

key === c 在 oldFiber中存在
const oldIndex = c（之前）.index;
即 oldIndex 代表当前可复用节点（c）在上一次更新时的位置索引
此时 oldIndex === 2;  // 之前节点为 abcd，所以c.index === 2
比较 oldIndex 与 lastPlacedIndex;

如果 oldIndex >= lastPlacedIndex 代表该可复用节点不需要移动
并将 lastPlacedIndex = oldIndex;
如果 oldIndex < lastplacedIndex 该可复用节点之前插入的位置索引小于这次更新需要插入的位置索引，代表该节点需要向右移动

在例子中，oldIndex 2 > lastPlacedIndex 0，
则 lastPlacedIndex = 2;
c节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：bd
// 当前newChildren：db

key === d 在 oldFiber中存在
const oldIndex = d（之前）.index;
oldIndex 3 > lastPlacedIndex 2 // 之前节点为 abcd，所以d.index === 3
则 lastPlacedIndex = 3;
d节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：b
// 当前newChildren：b

key === b 在 oldFiber中存在
const oldIndex = b（之前）.index;
oldIndex 1 < lastPlacedIndex 3 // 之前节点为 abcd，所以b.index === 1
则 b节点需要向右移动
===第二轮遍历结束===

最终acd 3个节点都没有移动，b节点被标记为移动

Я полагаю, вы уже понимаете, как оценивается движение узла. Если вы все еще немного запутались, это нормально~~ Давайте посмотрим на другой каштан~~

// 之前
abcd

// 之后
dabc

===第一轮遍历开始===
d（之后）vs a（之前）  
key改变，不能复用，跳出遍历
===第一轮遍历结束===

===第二轮遍历开始===
newChildren === dabc，没用完，不需要执行删除旧节点
oldFiber === abcd，没用完，不需要执行插入新节点

将剩余oldFiber（abcd）保存为map

继续遍历剩余newChildren

// 当前oldFiber：abcd
// 当前newChildren dabc

key === d 在 oldFiber中存在
const oldIndex = d（之前）.index;
此时 oldIndex === 3; // 之前节点为 abcd，所以d.index === 3
比较 oldIndex 与 lastPlacedIndex;
oldIndex 3 > lastPlacedIndex 0
则 lastPlacedIndex = 3;
d节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：abc
// 当前newChildren abc

key === a 在 oldFiber中存在
const oldIndex = a（之前）.index; // 之前节点为 abcd，所以a.index === 0
此时 oldIndex === 0;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 0 < lastPlacedIndex 3
则 a节点需要向右移动

继续遍历剩余newChildren

// 当前oldFiber：bc
// 当前newChildren bc

key === b 在 oldFiber中存在
const oldIndex = b（之前）.index; // 之前节点为 abcd，所以b.index === 1
此时 oldIndex === 1;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 1 < lastPlacedIndex 3
则 b节点需要向右移动

继续遍历剩余newChildren

// 当前oldFiber：c
// 当前newChildren c

key === c 在 oldFiber中存在
const oldIndex = c（之前）.index; // 之前节点为 abcd，所以c.index === 2
此时 oldIndex === 2;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 2 < lastPlacedIndex 3
则 c节点需要向右移动

===第二轮遍历结束===

Как видите, мы думали, что изabcdсталиdabc, просто изменитеdДвигайтесь вперед.

Но на самом деле React сохраняетdбез изменений, будетabcпереехал вdпозади.

Из этого видно, что с учетом производительности мы хотим минимизировать операцию перемещения узлов с задней части на переднюю.

Я считаю, что после стольких каштанов вы уже поняли принцип Диффа, поаплодируйте себе

Весь аннотированный кодпосмотреть здесь

Суммировать

Наши первые три статьи объяснили

На этом логика рендеринга всего React завершена.

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

Категории