DOM-DIFF

在 React17+ 中 DOM-DIFF 就是根据老的 fiber 树和最新的 JSX 对比生成新的 fiber 树的过程

正常树的 diff 算法时间复杂度是 O(n^3)，但是这个时间复杂度太高，所以 React 进行了一些优化

React 中的优化规则

• 只对同级节点进行对比，如果 DOM 节点跨层级移动，则 React 不会复用
• 不同类型的元素会产出不同的结构，会销毁老的结构，创建新的结构
• 可以通过 key 标识移动的元素

单节点，新的元素只有一个的情况

1. type 不同

<div>
  // 在调和阶段，需要把这个老节点标记为删除
  <h1 key="null">h1</h1> 
</div>

更新为：

<div>
  // 生成新的 fiber 节点并标记为插入
  <h2 key="null">h2<h2>
</div>

在 commit 阶段，会执行两个操作：

• div.removeChild(h1)
• div.appendChild(h2)

2. type 和 key 都不同

<div>
  // h1 标记为删除
  <h1 key="h1">h1</h1>
  <h2 key="h2">h2</h2>
  <h3 key="h3">h3</h2>
</div>

更新为：

<div>
  <h2 key="h2">h2</h2>
</div>

对于这个案例，先拿 h2 和 h1 匹配，发现不能复用，把 h1 标记为删除，匹配到 h2，可以复用，然后把剩下的节点全部删除

• div.removeChild(h1)
• div.removeChild(h3)

3. key 相同 type 也相同

<div>
  <h1 key="h1">h1</h1>
</div>

更新为：

<div>
  <h1 key="h1">h1 - new</h1>
</div>

如果对比后发现新老节点一样的，那么会复用老节点，复用老节点的 DOM 元素和 Fiber 对象

再看属性有无变更，如果有变化，则会把此 Fiber 节点标记为更新

h1.innerHTML = 'h1 - new'

4. key 相同但是 type 不同，直接删除所有老节点

<div>
  <h1 key="h1">h1</h1>
  <h2 key="h2">h2</h2>
</div>

更新为：

<div>
  <p key="h1">p</p>
</div>

如果 key 相同，但是 type 不同，则不再进行后续对比了，因为 key 一样代表是同一个元素，如果 type 不一样说明节点已经发生改变，直接把老节点全部删掉，插入新节点即可

key 相同表示这是同一个元素

• div.removeChild(h1)
• div.removeChild(h2)
• div.appendChild(p)

多节点

如果有多个节点，节点有可能会更新，删除，新增，多节点的时候会经过两轮遍历

第一轮遍历主要处理节点的更新，更新包括属性和类型的更新

第二轮遍历主要处理节点的新增、删除和移动

移动时的原则是尽量少量的移动，如果必须有一个要动，地位高的不动，地位低的动

对比，都可复用，只需更新

<ul>
  <li key="A">A</li>
  <li key="B">B</li>
  <li key="C">C</li>
  <li key="D">D</li>
</ul>

更新为：

<ul>
  <li key="A">A - new</li>
  <li key="B">B - new</li>
  <li key="C">C - new</li>
  <li key="D">D - new</li>
</ul>

最后会得到一个操作序列：

1. 更新 A
2. 更新 B
3. 更新 C
4. 更新 D

key 相同，type 不同

<ul>
  <li key="A">A</li> // Fiber 节点
  <li key="B">B</li>
  <li key="C">C</li>
  <li key="D">D</li>
</ul>

更新为：

<ul>
  <div key="A">A - new</div> // JSX 节点
  <li key="B">B - new</li>
  <li key="C">C - new</li>
  <li key="D">D - new</li>
</ul>

第一步比较第一个节点，发现不能复用，老的标记删除，新的标记插入

后面的都可复用

最后结论是：

删除老的 li A，插入 divA，更新 B C D

DOM-DIFF 是一个对比老的 Fiber 链表和新的 JSX 数组，生成新的 Fiber 链表的过程

老的是 Fiber，新的是 JSX

key 不同退出第一轮循环

因为如果 key 不一样已经发生位置变化了

<ul>
  <li key="A" style={oldStyle}>A</li>
  <li key="B" style={oldStyle}>B</li>
  <li key="C" style={oldStyle}>C</li>
  <li key="D" style={oldStyle}>D</li>
  <li key="E" style={oldStyle}>E</li>
  <li key="F" style={oldStyle}>F</li>
</ul>

更新为：

<ul>
  <li key="A" style={oldStyle}>A - new</li>
  <li key="C" style={oldStyle}>C - new</li>
  <li key="E" style={oldStyle}>E - new</li>
  <li key="B" style={oldStyle}>B - new</li>
  <li key="G" style={oldStyle}>G</li>
</ul>

首先第一轮循环

oldA 和 newA 比较，一样，可以复用，更新 A

oldB 和 newC 比较，key 不一样，跳出第一轮循环

进行第二轮循环

建一个 map 对象 let map = {'B': B, 'C': C, ' 'D': D, 'E': E, 'F': F}(不处理 A，因为 A 在第一轮循环已经处理完了) 表示还没有复用的节点

继续遍历新节点，到 newC 了

newC 节点在 map 找有没有 key 为 C 的 fiber 节点

如果有，并且可以复用（Fiber 和 DOM 可以复用），说明只是位置变了，把 oldC 标标记为更新

• lastPlacedIndex 表示最大的不需要动的老的节点的索引

• oldC 的 oldIndex 是 2，oldIndex > lastPlacedIndex，所以 C 不需要动

• lastPlacedIndex = 2

• map 中删除 C

再看 newE

• 在 map 里面找 E，找到了 oldE，oldIndex 是 4，lastPlacedIndex < 4，E 也不动

• lastPlacedIndex = 4

• map 中删除 E

到 newB 了，找到 oldB，oldIndex = 1 < lastPlacedIndex，oldB 需要往后挪

newG 不在 map 里面，标记为插入

等 JSX 数组全部遍历完之后，把 map 里面全部 fiber 节点标记为删除，也就是 oldE 和 oldF

在 react 里面，每一个操作都有一个权重（上图中那个表），每种操作都有权重，这些都记录在 effectList 里面

每次 DOM Diff 会生成一个 effectList，在 commitMutationEffects（ReactFiberWorkLoop.old.js） 会使用，根据 effectList 进行操作

另外，那个优先级在 ReactFiberFlags.js 里面可以找到