React diff 探究

0. 前言

Virtual DOM 是 React 对真实 DOM 的一种抽象，其本质是一个 js 对象。

React render 函数每次执行都会生成一个新 Virtual DOM Tree，diff 算法就是比较前后两次 render 函数生成的 Virtual DOM Tree 的差异性，相比于通过传统 diff 方法比较随机两棵树差异的 O(n^3) 时间复杂度，React diff 算法可以将时间复杂度降至 O(n) （其中 n 为树中的节点数）。

通过 diff 算法，React 可以找出新老 Virtual DOM Tree 的最小差异集，下一步就是要把这些变化通过最少步骤更新到真实的 DOM 节点上，React 把构造新 Virtual DOM -> 执行 diff 算法 -> 更新老 Virtual DOM -> 更新真实 DOM 这一流程称为 reconciliation 流程。

Reconciliation is the process through which React updates the DOM.

以下是 render 函数执行后的组件生命周期图：

1. React Element

在介绍 Virtual DOM 之前，先了解下 React Element，React Element 是 React 应用的最小单元。

Elements are the smallest building blocks of React apps.

React Element 分为两种：DOM Element 和 Component Element。

• DOM Element：浏览器原生支持的 DOM 元素(比如 div，p 等)的抽象描述
• Component Element：通过 React Component 构建出来的元素（构建方式为函数或者 ES6 class 类）

  Components let you split the UI into independent, reusable pieces, and think about each piece in isolation.

2. Virtual DOM

以 React15 为例：

// virtual dom
const vDom = <div>virtual dom</div>

// babel 转义后变成 js 对象
const vDomObj = {
  $$typeof: Symbol(react.element),
  key: null,
  ref: null,
  type: 'div',
  props: {
    children: 'virtual dom'
  },
  _owner: {...},
  _store: {validated: false}
}

vDomObj 各属性含义如下：

name	type	description
$$typeof	Symbol	标志该对象是否是 React Element，设计初衷是为了避免 xss
key	string / null	Virtual DOM 的唯一标识
ref	string / function / null	真实 DOM 节点或 React 元素的索引
type	string / function	Virtual DOM 元素类型（包括 DOM Element 和 Component Element）
props	object	Virtual DOM 元素属性，包含 children
_owner	object	指明该 Virtual Dom 的父元素
_store	object	未知

3. diff 算法

React 官网中描述的 diff 算法基于以下两个假设：

1. Two elements of different types will produce different trees.
2. The developer can hint at which child elements may be stable across different renders with a key prop.

即：

1. 不同类型的元素产生会产生不同的节点树。
2. 不同子元素可以通过 key 属性来保持稳定。

除此之外，还有一个隐藏的假设：

1. Web UI 中的 DOM 节点的跨层级操作特别少，可以忽略不计。

基于假设三：分层比较

假设三是整个 diff 算法的基础，它确立了 React 对树的分层比较策略，即 diff 算法在比较新老 Virtual DOM Tree 的时候，只会比较同层级的 Virtual DOM，如下图，diff 算法只会比较相同颜色框中的节点。正是这种分层比较策略可以让 diff 在根据广度遍历一次 Virtual DOM Tree 后就完成整颗树的比较。

然而，在实际使用 React 过程中，无法完全避免节点的跨层级操作，比如下图中要将 A 节点从 B 节点下方跨层级移动到 R 节点下方，对于这种情况，diff 算法首先发现 R 节点的子节点多了一个 A 节点，因此会创建一个新的 A 节点，然后遍历 B 节点的子节点时，发现少了一个 A 节点，因此会删除原先 B 节点下方的 A 节点，整个过程即 find new R.A -> create R.A -> B.A not exists -> delete B.A。diff 算法不会把 B.A 完整的移动到 R.A 上，而是通过上述先增后删的操作来实现这种‘移动’效果。

基于假设一：减少比较次数

当对比两棵 Virtual DOM Tree 时，diff 算法会优先比较两棵树的根节点，如果它们的类型（type）不同则认为这两个根节点及其下属的子树是完全不同的，diff 算法不会再继续递归比较两棵子树，如下图所示，当 diff 算法检测到 R1.type !== R2.type，则其会把 R1 跟 R2 视为两个不同的节点，因此会删除 R1 节点及 R1.A 和 R1.B，然后再创建 R2、R2.A 和 R2.B。通过这种策略，diff 算法可以减少遍历比较次数，从而一定程度上提升算法的性能。

基于假设二：稳定的 DOM

Virtual DOM 的 key 属性用来标识该节点是否唯一，diff 算法可以根据 key 值来判断新老两个 Virtual DOM 在类型相同的情况下是否是同一个实例，如果新老 Virtual DOM 的 key 值不同，则 diff 算法会销毁老的实例，然后再创建一个新的实例。下面的代码在切换 Child 的 key 值后，会把原先的 a 实例销毁掉，再创建一个 b 实例。

class Child extends React.Component {
  constructor(props){
    super(props)
    
    console.log(`创建实例${props.name}`)
  }
  
  componentWillUnmount(){
    console.log(`销毁实例${this.props.name}`)
  }
  
  render() {
    return <div>子组件</div>
  }
}

class Parent extends React.Component {
  state = {key: 1, name: 'a'}
  
  render() {
    return (
      <div>
        <button onClick={() => this.setState({key: 2, name: 'b'})}>
          切换 key
        </button>
        <Child key={this.state.key} name={this.state.name} />
      </div>
    )
  }
}

/*
初始化: 打印出 '创建实例a'
点击切换按钮后: 打印出 '销毁实例a' -> 打印出 '创建实例b'
*/

key 的作用不仅仅体现在保证元素的稳定上，它还可以帮助 diff 算法快速找到 Virtual DOM 列表中的某个具体节点。

在实际应用中，经常会出现某个节点含有多个子节点的场景，对于 diff 算法来说，有效快速地比较出改变前后子节点列表的差异和更新步骤可以显著提升 React 应用的性能。

换言之，diff 算法要在 O(n) 的时间复杂度内找出将改变前子节点列表变换到改变后子节点列表的最少步骤，这个问题其实是求解最小编辑距离问题的变种，但是求解最小编辑距离的传统算法可以把时间复杂度控制在 O(n^2) 内，对于 React 来说依旧太费时，所以 React diff 算法采取了其他策略来保证时间复杂度为 O(n)。

让我们把问题抽象简化：给定改变前的子节点列表 prevList 和改变后的子节点列表 nextList，求将 prevList 变换成 nextList 所需的最少操作步骤，操作步骤可以为

• INSERT_MARKUP：若 nextList 中某节点 type 不存在 prevList 内，则需要对该新节点执行插入操作。
• MOVE_EXISTING：若 nextList 与 prevList 中存在相同 type 和 key 的节点，则直接复用 prevList 中节点，并对其做移动操作。
• REMOVE_NODE：若 nextList 中不存在与 prevList 中某节点相同 type 和 key 的节点，则从 prevList 中删除该节点。

我们需要一个队列 updateQueue 来按照优先顺序依次存放计算过程中得到的操作，updateQueue 是一个数组，它的每个元素是一个描述某次操作的 js 对象，其属性定义如下：

name	description
type	操作类型，包括 INSERT_MARKUP、MOVE_EXISTING、REMOVE_NODE
fromIndex	节点在 prevList 的初始位置信息
toIndex	经过移动或插入后，节点在 nextList 的位置信息
markupNode	要插入的子节点，仅对 INSERT_MARKUP 有效

相应的，我们为每种操作分别定义一个函数：

// 记录操作的队列
const updateQueue = []

// 记录插入操作
function enqueueInsert(markupNode, toIndex) {
  updateQueue.push({
    type: INSERT_MARKUP,
    markupNode,
    fromIndex: null
    toIndex
  })
}

// 记录移动操作
function enqueueMove(fromIndex, toIndex) {
  updateQueue.push({
    type: MOVE_EXISTING,
    fromIndex,
    toIndex
  })
}

// 记录删除操作
function enqueueRemove(fromIndex) {
  updateQueue.push({
    type: REMOVE_NODE,
    fromIndex,
    toIndex: null
  })
}

接下来，为了从 prevList 和 nextList 中快速查找某个节点，得把节点列表转换成一个存放 key - vnode 映射关系的对象。

// 节点列表转换为对象
function nodeListToMap (list = []) {
  const nodeMap = {}
  
  list.forEach(
    (vnode, index) => {
      // 如果不指定节点 key，则直接使用数组的下标
      nodeMap[vnode.key || index] = vnode
    }
  )
  
  return nodeMap
}

通过 nodeMap 分别获取到改变前后两个列表中 key 或 index 相同的两个节点，然后再根据这两个节点是否相等来判断下一步更新操作（插入、删除、移动），为了不遗漏两个列表中的节点，需要分别对两个列表中的节点进行遍历。

1.首先遍历 nextList 中的节点并将其与 prevList 中的节点进行对比。

2.再遍历 prevList 中的节点并将其与 nextList 中的节点进行对比。

通过以上两步操作，就可以将 prevList 变换到 nextList，至此还剩下三个关键的问题需要解决，即

• 计算新增节点在 nextList 中的插入位置
• 如何删除不存在的老节点
• 如何移动可复用的老节点

在解决的这三个问题之前，首先得了解几个概念

name	description
lastIndex	prevList 中被遍历过最右节点位置（即遍历过节点的最大下标），初始值为 0
nextIndex	nextList 中当前被遍历到的节点下标，初始值为 0
mountIndex	某个节点在 nextList 中的最终位置，初始值为该节点在 prevList 中的位置

对于插入操作，只需要把新增节点 nextNode 的 mountIndex 设置为 nextIndex，再根据 nextNode.mountIndex 把 nextNode 插入到 nextList 的对应位置即可。

// 插入节点
function insertNode(nextNode, nextIndex){
  nextNode.mountIndex = nextIndex
  
  enqueueInsert(nextNode, nextIndex)
}

对于删除操作，直接根据老节点在 prevList 中的原始位置删除即可。

// 删除节点
function removeNode(prevNode) {
  enqueueRemove(prevNode.mountIndex)
  
  prevNode.mountIndex = null
}

移动操作稍微复杂些，涉及到 lastIndex 和节点 mountIndex 的大小比较，如果 lastIndex > prevNode.mountIndex，说明当前遍历到的 prevNode 在 prevList 中就比上一个 prevNode 节点靠前，因此需要将当前遍历到的 prevNode 移动到 nextIndex 位置，反之则不用移动。

// 移动节点
function moveNode(prevNode, nextIndex, lastIndex) {
  if(prevNode.mountIndex < lastIndex) {
    enqueueMove(prevNode.mountIndex, nextIndex)
  }
}

完整的计算更新步骤的代码如下：

// 计算更新步骤
function updateList(prevList, nextList) {
  // 列表转对象
  const prevMap = nodeListToMap(prevList)
  const nextMap = nodeListToMap(nextList)
  
  let name
  // 初始化 lastIndex 和 nextIndex
  let lastIndex = 0
  let nextIndex = 0
  
  // 首先遍历 nextMap
  for(name in nextMap) {
    const nextNode = nextMap[name]
    // 根据该 name 获取到 prevNode
    const prevNode = prevMap[name]
    
    if(prevNode){
      if(prevNode.type === nextNode.type) {
        // 相同节点执行移动操作
        moveNode(prevNode, nextIndex, lastIndex)
        // 更新 lastIndex, 确保它是最右位置
        lastIndex = Math.max(prevNode.mountIndex, lastIndex)
        // 更新 prevNode 的最终位置
        prevNode.mountIndex = nextIndex
      } 
      else {
        // 不同节点，先删除 prevNode，再插入 nextNode
        // 更新 lastIndex, 确保它是最右位置
        lastIndex = Math.max(prevNode.mountIndex, lastIndex)
        // 删除 prevNode
        removeNode(prevNode)
        // 插入 nextNode
        insertNode(nextNode, nextIndex)
      }
      
    } 
    else {
      // 若 prevNode 不存在，则直接插入 nextNode
      insertNode(nextNode, nextIndex)
    }
    
    // 访问下一个 nextNode, 更新 nextIndex
    nextIndex ++
  }
  
  // 再遍历 prevMap
  for(name in prevMap){
    if(!nextMap[name]){
      // 如果老节点在 nextMap 中不存在，则直接删除
      removeNode(prevMap[name])
    }
  }
}

以上代码体现了 React diff 在处理 list diff 时候的基本逻辑，在 React 源码中其实现远比这个复杂，这种处理策略可以保证 diff 算法在处理 list diff 时候可以用线性时间算出更新步骤，可以结合以下例子加深理解：

prevList:   A      B      C
          key=a  key=b  key=c
nextList:   B      A      D
          key=b  key=a  key=d

假设节点列表变化前后节点排列顺序如上所示，根据 list diff 策略处理如下：

0.初始化时，updateQueue 为空数组，lastIndex、nextIndex 以及各节点的 mountIndex 如下：

	lastIndex	nextIndex	A	B	C	D
初始化	0	0	0	1	2	null

1.遍历 nextList.B，发现 prevList.B 也存在，比较 prevList.B.mountIndex 与 lastIndex，发现前者更大，故不需要移动 prevList.B，此时 prevList 中访问的节点最右位置变为 prevList.B.mountIndex，而 B 的最终位置则为 nextList 中当前访问的节点位置，即 nextIndex（prevList.B.mountIndex = nextIndex），然后切换到下一个 nextList 节点。

	lastIndex	nextIndex	A	B	C	D
初始化	0	0	0	1	2	null
遍历 nextList.B	1	1	0	0	2	null

2.遍历 nextList.A，发现 prevList.A 也存在，比较 prevList.A.mountIndex 与 lastIndex，发现后者更大，故需要移动 prevList.A，将 prevList.A 移动到 nextIndex 的位置，而保持 lastIndex 不变。updateQueue 变为：

updateQueue = [
  {type: MOVE_EXISTING, fromIndex: 0, toIndex: 1}
]

	lastIndex	nextIndex	A	B	C	D
初始化	0	0	0	1	2	null
遍历 nextList.B	1	1	0	0	2	null
遍历 nextList.A	1	2	1	0	2	null

3.遍历 nextList.D，发现 prevList.D 不存在，故直接将其插入到 nextIndex 的位置，updateQueue 变为：

updateQueue = [
  {type: MOVE_EXISTING, fromIndex: 0, toIndex: 1},
  {type: INSERT_MARKUP, fromIndex: null, toIndex: 2}
]

	lastIndex	nextIndex	A	B	C	D
初始化	0	0	0	1	2	null
遍历 nextList.B	1	1	0	0	2	null
遍历 nextList.A	1	2	1	0	2	null
遍历 nextList.D	1	3	1	0	2	2

4.遍历 prevList.A，发现 nextList.A 存在，跳过。

	lastIndex	nextIndex	A	B	C	D
初始化	0	0	0	1	2	null
遍历 nextList.B	1	1	0	0	2	null
遍历 nextList.A	1	2	1	0	2	null
遍历 nextList.D	1	3	1	0	2	2
遍历 prevList.A	1	3	1	0	2	2

5.遍历 prevList.B，发现 nextList.B 存在，跳过。

	lastIndex	nextIndex	A	B	C	D
初始化	0	0	0	1	2	null
遍历 nextList.B	1	1	0	0	2	null
遍历 nextList.A	1	2	1	0	2	null
遍历 nextList.D	1	3	1	0	2	2
遍历 prevList.A	1	3	1	0	2	2
遍历 prevList.B	1	3	1	0	2	2

6.遍历 prevList.C，发现 nextList.C 不存在，故需要删除该节点，updateQueue 变为：

updateQueue = [
  {type: MOVE_EXISTING, fromIndex: 0, toIndex: 1},
  {type: INSERT_MARKUP, fromIndex: null, toIndex: 2},
  {type: REMOVE_NODE, fromIndex: 2, toIndex: null}
]

	lastIndex	nextIndex	A	B	C	D
初始化	0	0	0	1	2	null
遍历 nextList.B	1	1	0	0	2	null
遍历 nextList.A	1	2	1	0	2	null
遍历 nextList.D	1	3	1	0	2	2
遍历 prevList.A	1	3	1	0	2	2
遍历 prevList.B	1	3	1	0	2	2
遍历 prevList.C	1	3	1	0	null	2

至此，就可以算出 list diff 后节点列表的更新步骤。

4. 为什么不将变化直接更新到真实 DOM 节点上？

通过 reconciliation 将节点变化部分更新到真实节点的意义在于：

• 通过 diff 算法对比 render 前后的 Virtual DOM 可以获取需要改变的 Virtual DOM 最小集合以及将这些变化部分更新到真实节点的最少步骤。
• 在更新真实节点的过程中，React 会根据 diff 获取到的更新步骤，在一次事件循环中执行完所有步骤并保证在此次事件循环中只执行一次真实节点的重绘和重排操作。

以上两点可以确保 React 在更新真实 DOM 过程中，避免无用重复的重排和重绘操作，从而降低更新操作带来的性能影响。

参考文献：

virtual-dom

react-reconciliation

不可思议的 react diff

how-virtual-dom-and-diffing-works-in-react