关于javascript:从头写一个-Reactlike-框架优化-diff

前言

在从头写一个 React-like 框架：工程搭建中，咱们将 mini React 进行了重构，这次咱们来优化一下现有的 diff 逻辑，在 Fiber 架构中，次要有 reconcile 和 commit 两大阶段，diff 的过程产生在 reconcile 阶段。

现有性能

先看一下现有的 reconcileChildren 实现：

function reconcileChildren(WIPFiber: Fiber, children: VNode): void {
  let index = 0
  let prevSibling = null

  const oldChildren = WIPFiber.kids || []
  const newChildren = (WIPFiber.kids = arrayfy(children))

  const length = Math.max(oldChildren.length, newChildren.length)

  while (index < length) {const oldChild = oldChildren[index]
    const currentChild = newChildren[index]

    const sameType = oldChild && currentChild && oldChild.type === currentChild.type

    if (sameType) {
      currentChild.effectTag = 'UPDATE'
      // ...
    }

    if (currentChild && !sameType) {
      currentChild.effectTag = 'PLACEMENT'
      // ...
    }
    
    if (oldChild && !sameType) {
      oldChild.effectTag = 'DELETION'
      deletions.push(oldChild)
    }
    // ...
  }
}

因为新旧 children 的长短不定，咱们取两者中较大的长度进行遍历，保障新旧 children 中至多有一个列表所有节点都能被遍历到。如果新旧节点的 type 雷同，则认为新旧节点能够复用 DOM，否则不能复用。循环中一共有三种状况：

1. 新旧节点 type 雷同，阐明 新旧节点都存在，并且 type 雷同，effectTag 记为 ‘UPDATE’
2. 新节点存在且 type 不同，阐明该新节点须要被创立，effectTag 记为 'PLACEMENT'
3. 旧节点存在且 type 不同，阐明该旧节点须要被删除，effectTag 记为 'DELETION'

随后在 commit 阶段，只须要依据不同的 effectTag 进行不同的 dom 操作即可：

// reconciler.js
function commitWork(fiber: Fiber): void {
  // ...
  if (fiber.effectTag === 'PLACEMENT') {parentDom.appendChild(fiber.dom)
  }

  if (fiber.effectTag === 'DELETION') {commitDeletion(fiber, parentDom as HTMLElement)
    if (fiber.ref) {fiber.ref.current = null}
    return
  }

  if (fiber.effectTag === 'UPDATE') {
    updateDom(
      fiber.dom,
      fiber.prevProps,
      fiber.props
    )
  }
  // ...
}

这是一种最简略的 diff 策略，仅依据 type 判断节点是否能够复用，比方在上面的例子中：

<ul>
  {keys.map(key =><li>{key}</li>)
  }
</ul>

如果 keys 是从 [1, 2, 3] 变为 [3, 2, 1]，在 reconcile 过程中，li 节点会全副复用，因为他们的 fiber type 雷同，然而略微变一下就会大有不同：

<ul>
  {keys.map(key => key === 1 ? <div>key 1 div</div> : <li>{key}</li>)
  }
</ul>

当初 key === 1 时，渲染出的 dom 不再是 li 而是 div，所以如果 keys 从 [1, 2, 3] 变为 [3, 2, 1]，在 1 和 3 处别离会进行一次创立 dom 和一次删除 dom，咱们须要对这种状况进行优化。

增加 key

首要问题是：仅通过 type 不能精确地找到可复用节点，所以须要额定属性建设新旧节点的映射关系，这个属性就是咱们熟知的 key。首先在构建 fiber 节点时查看 key 属性，如果有间接挂载到节点上：

// h.js
export function h(type, props, ...children): VNode {props = props || {}
  const key = props.key || null

  while (children.some(child => Array.isArray(child))) {children = children.flat()
  }

  return {
    type,
    // 增加 key 属性
    key,
    props: {
      ...props,
      children: children.map(child => typeof child === 'object' ? child : createTextElement(child)).filter(e => e != null)
    }
  }
}

有了 key 之后，咱们认为当新旧节点的 type 和 key 都相等时，新旧节点的 dom 能够复用。新的 diff 中用到如下变量，别离是新旧 children 的首尾元素：

const oldChildren = WIPFiber.kids || []
const newChildren = (WIPFiber.kids = arrayfy(children))
// 新旧 children 首尾下标
let oldStart = 0
let oldEnd = oldChildren.length - 1
let newStart = 0
let newEnd = newChildren.length - 1
// 新旧 children 的首尾元素
let oldStartNode = oldChildren[oldStart]
let oldEndNode = oldChildren[oldEnd]
let newStartNode = newChildren[newStart]
let newEndNode = newChildren[newEnd]

先从新旧 children 的两端尝试寻找可复用的节点，oldStartNode, newStartNode 别离是新旧 children 的第一个节点，如果 oldStartNode, newStartNode 的 key 和 type 雷同，则认为这两个节点能够复用 dom，间接更新属性（effectTag = 'UPDATE'）即可，更新实现后，oldStart, newStart 别离指向下一个地位，oldStartNode, newStartNode 也随之变成 残余未进行 diff 的新旧 children 的第一个元素；当 oldStartNode, newStartNode key 不同时，暂停首部的比拟，同理再从新旧 children 尾部开始比拟，这样就能够先将新旧 children 两端不须要挪动的可复用节点优先更新，当 oldStart > oldEnd 或 newStart > newEnd 时，证实 oldChildren, newChildren 其中一个曾经全副参加过 diff，循环终止：

while (oldStart <= oldEnd && newStart <= newEnd) {// 首尾 key, type 雷同的节点优先更新(effectTag = 'UPDATE')
  if (isSame(oldStartNode, newStartNode)) {clone(newStartNode, oldStartNode)
    newStartNode.effectTag = 'UPDATE'

    oldStartNode = oldChildren[++oldStart]
    newStartNode = newChildren[++newStart]
  } else if (isSame(oldEndNode, newEndNode)) {clone(newEndNode, oldEndNode)
    newEndNode.effectTag = 'UPDATE'

    oldEndNode = oldChildren[--oldEnd]
    newEndNode = newChildren[--newEnd]
  }
  // ...
}

两端的节点 diff 实现后，开始遍历 newChildren 中残余的节点，因为当初有了 key，通过 findIndex 就能够判断 oldChildren 中有没有可复用的节点，如果有，对新旧节点进行 patch，这里新旧节点在各自 children 中的地位是不同的，后续须要挪动节点，所以 effectTag 记为 INSERT，而且在 commit 阶段才会真正进行 dom 操作，这里先通过 after 属性先记录新节点要插入地位之后的节点（因为理论用到的是 insertBefore 办法），因为咱们遍历的是 newChildren，阐明 以后节点在新的渲染中是残余未 diff 列表中的第一个，所以该节点的 after 是 oldStartNode。如果 oldChildren 中没有可复用的节点，则将 newStartNode 的 effectTag 置为 'INSERT' 示意以后地位须要新插入一个节点。diff 实现后，将 oldChildren 中对应地位的节点置为 null，并将 newStart 指向下一个元素。因为在 diff 的过程中，每次对可复用节点实现更新操作后，都会将 oldChildren 中对应的元素置为 null，因而在循环的最开始，咱们要判断一下 oldStartNode，oldEndNode 元素是否存在，不存在则指向下一个元素：

if (!oldStartNode) {oldStartNode = oldChildren[++oldStart]
} else if (!oldEndNode) {oldEndNode = oldChildren[--oldEnd]
} else if (isSame(oldStartNode, newStartNode)) {// ...} else if (isSame(oldEndNode, newEndNode)) {// ...} else {const indexInOld = oldChildren.findIndex(child => isSame(child, newStartNode))
  // 存在可复用节点，实现新旧节点的 patch 操作，此处的 'INSERT' 示意节点须要被挪动
  if (indexInOld >= 0) {const oldNode = oldChildren[indexInOld]
    clone(newStartNode, oldNode)
    newStartNode.effectTag = 'INSERT'
    newStartNode.after = oldStartNode
    oldChildren[indexInOld] = undefined
  } else {
    // 无可复用节点，无需 patch，此处的 'INSERT' 示意节点须要被创立
    newStartNode.effectTag = 'INSERT'
    newStartNode.after = oldStartNode
  }
  newStartNode = newChildren[++newStart]
}

最初，当 while 循环实现后，咱们须要检查一下 oldStart, oldEnd, newStart, newEnd 之间的关系：

1. 如果 oldEnd < oldStart，阐明旧节点全副参加 diff 后，还有新节点没参加 diff，这些节点是须要间接新增的节点。能够间接遍历残余的 newChildren，将这些节点顺次增加到新 dom 序列的开端 newChildren[newEnd + 1]
2. 如果 newEnd < newStart，阐明新节点全副参加 diff 后，还有旧节点没参加 diff，这些节点时须要删除的节点，间接循环残余的 oldChildren，顺次删除即可：

if (oldEnd < oldStart) {for (let i = newStart; i <= newEnd; i++) {let node = newChildren[i]
    node.effectTag = 'INSERT'
    node.after = newChildren[newEnd + 1]
  }
} else if (newEnd < newStart) {for (let i = oldStart; i <= oldEnd; i++) {let node = oldChildren[i]
    if (node) {
      node.effectTag = 'DELETION'
      deletions.push(node)
    }
  }
}

到此，简略优化后的 diff 流程就曾经实现了。

结语

相比于旧的 diff 计划，新的 diff 计划有以下改良：

1. 能够通过 key 更精确地判断新旧 children 中是否有可复用的节点
2. 会优先从两端解决可间接进行复用的节点，会缩小一些 findIndex 的次数
3. 新的 diff 中采纳 'INSERT' (insertBefore) 而不是 'PLACEMENT' (appendChild), 灵活性更好

对于 diff 流程，我从这个博客中学到了很多，外面讲得很具体，还有很多配图帮忙了解，最次要的是要想分明 oldStart, oldEnd, newStart, newEnd 他们中携带的信息，博客中的示例代码是 diff 过程和更新 dom 一起进行的，这一点并不适用于 fiber 架构，所以我进行了一些小革新（先标记 effectTag 和 after，commit 阶段对立更新 dom），代码在 github 上，有趣味的同学能够看看(棘手 star 一下也是极好的) ^_^