Nicander知识小站

Appearance

本部分内容是关于如何高效的进行子节点的更新操作相关的算法。

简单 diff 算法 ​

第八章中关于子节点的更新操作用了一种很粗暴的方式，即直接卸载掉旧的节点，再挂载新的节点。这种方式没有考虑 dom 元素的复用，会进行大量的 dom 操作，而 dom 操作是很耗费性能的操作。

简单 diff 算法的核心思路是：找出可以进行复用的元素，然后尽可能地通过 DOM 移动操作来完成更新，避免过多地对 DOM 元素进行销毁和重建。

简单 Diff 算法的核心逻辑是，拿新的一组子节点中的节点去旧的一组子节点中寻找可复用的节点。如果找到了，则记录该节点的位置索引。我们把这个位置索引称为最大索引。在整个更新过程中，如果一个节点的索引值小于最大索引，则说明该节点对应的真实 DOM 元素需要移动。

找出可以进行复用的 dom 元素 ​

这里的实现逻辑是进行两次 for 循环，通过 vnode 上的 key 属性，找出新旧两组节点中相同的节点。

这里的 key 属性就是 v-for 中需要有:key 绑定的原因；

javascript
// 遍历新的 children
for (let i = 0; i < newChildren.length; i++) {
  const newVNode = newChildren[i]
  // 遍历旧的 children
  for (let j = 0; j < oldChildren.length; j++) {
    const oldVNode = oldChildren[j]
    // 如果找到了具有相同 key 值的两个节点，说明可以复用，但仍然需要调用 patch 函数更新
    if (newVNode.key === oldVNode.key) {
      patch(oldVNode, newVNode, container)
      break // 这里需要 break
    }
  }
}

判断可复用元素是否需要移动 ​

这里我们遍历新节点组时，新节点组中每个节点在旧节点中的索引会形成一个索引数组（可以理解为新节点在移动前的顺序），比如说下边这个例子，新节点遍历后形成的队列为[3,1,2]，并不是一个递增的队列，而我们最终排序后的队列应该是此时新节点组中节点的顺序，所以肯定是一个递增的队列，所以需要进行移动。

所以可以这样理解，我们 最终需要让这个队列变为递增队列

落实到代码中，我们可以再新节点遍历过程中，记录一个新节点在旧节点中（具有相同 key） 的最大索引lastIndex，如果在后续查找过程中，存在索引值比当前记录的lastIndex小，则说明该节点应该在lastIndex需要移动。

移动元素 ​

在找出了需要移动的元素后，我们需要解决如何移动元素（移动到哪里）。

我们最终元素（更新后的真实 dom 节点）的排序就是根据新节点组中节点的顺序，所以只需要把当前找到的新 children 中需要进行移动的节点p<sub>n</sub>移动到上一个节点p<sub>n-1</sub>所对应的真实 dom 的后边。

落实到代码中也很简单：

javascript
function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children
    let lastIndex = 0
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      let j = 0
      for (j; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]
        if (newVNode.key === oldVNode.key) {
          patch(oldVNode, newVNode, container)
          if (j < lastIndex) {
            // 代码运行到这里，说明 newVNode 对应的真实 DOM 需要移动
            // 先获取 newVNode 的前一个 vnode，即 prevVNode
            const prevVNode = newChildren[i - 1]
            // 如果 prevVNode 不存在，则说明当前 newVNode 是第一个节点，它不需要移动
            if (prevVNode) {
              // 由于我们要将 newVNode 对应的真实 DOM 移动到 prevVNode 所对应真实 DOM 后面，
              // 所以我们需要获取 prevVNode 所对应真实 DOM 的下一个兄弟节点，并将其作为锚点
              const anchor = prevVNode.el.nextSibling
              // 调用 insert 方法将 newVNode 对应的真实 DOM 插入到锚点元素前面，
              // 也就是 prevVNode 对应真实 DOM 的后面
              insert(newVNode.el, container, anchor)
            }
          } else {
            lastIndex = j
          }
          break
        }
      }
    }
  } else {
    // 省略部分代码
  }
}

找出新增的元素 ​

对于新 children 中需要新增的节点，我们需要解决：

  • 找出新增的节点
  • 挂载到正确的位置

这两个问题都不难解决，我们在两层 for 循环遍历中，如果 新 children 中的某个节点没有在旧 children 中找到，则说明他是新增的节点newVNode，我们只需要把他挂载到newVNode的前一个虚拟节点prevVNode 所对应的真实 DOM 的后边。

javascript
function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children
    let lastIndex = 0
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      let j = 0
      // 在第一层循环中定义变量 find，代表是否在旧的一组子节点中找到可复用的节点，
      // 初始值为 false，代表没找到
      let find = false
      for (j; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]
        if (newVNode.key === oldVNode.key) {
          // 一旦找到可复用的节点，则将变量 find 的值设为 true
          find = true
          patch(oldVNode, newVNode, container)
          if (j < lastIndex) {
            const prevVNode = newChildren[i - 1]
            if (prevVNode) {
              const anchor = prevVNode.el.nextSibling
              insert(newVNode.el, container, anchor)
            }
          } else {
            lastIndex = j
          }
          break
        }
      }
      // 如果代码运行到这里，find 仍然为 false，
      // 说明当前 newVNode 没有在旧的一组子节点中找到可复用的节点
      // 也就是说，当前 newVNode 是新增节点，需要挂载
      if (!find) {
        // 为了将节点挂载到正确位置，我们需要先获取锚点元素
        // 首先获取当前 newVNode 的前一个 vnode 节点
        const prevVNode = newChildren[i - 1]
        let anchor = null
        if (prevVNode) {
          // 如果有前一个 vnode 节点，则使用它的下一个兄弟节点作为锚点元素
          anchor = prevVNode.el.nextSibling
        } else {
          // 如果没有前一个 vnode 节点，说明即将挂载的新节点是第一个子节点
          // 这时我们使用容器元素的 firstChild 作为锚点
          anchor = container.firstChild
        }
        // 挂载 newVNode
        patch(null, newVNode, container, anchor)
      daima

代码中，我们使用了find变量来表示是否在旧节点中找到了相同 key 的节点，如果没有找到，说明是新增节点，则进入另一段逻辑：将新增节点挂载到正确位置。

找出需要删除的元素 ​

也有可能存在新 children 中没有，而旧 children 中有，也就是需要删除节点的情况。

这种情况处理和新增元素的处理办法基本相同。

javascript
function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    let lastIndex = 0
    for (let i = 0; i < newChildren.length; i++) {
      // 省略部分代码
    }

    // 上一步的更新操作完成后
    // 遍历旧的一组子节点
    for (let i = 0; i < oldChildren.length; i++) {
      const oldVNode = oldChildren[i]
      // 拿旧子节点 oldVNode 去新的一组子节点中寻找具有相同 key 值的节点
      const has = newChildren.find(
        vnode => vnode.key === oldVNode.key
      )
      if (!has) {
        // 如果没有找到具有相同 key 值的节点，则说明需要删除该节点
        // 调用 unmount 函数将其卸载
        unmount(oldVNode)
      }
    }

  } else {
    // 省略部分代码
  }
}

TODO: 双端 diff ​

简单 diff 算法对于 dom 的移动操作并不是最优的，比如说对于下边这种情况来说，简单 diff 算法需要进行两次 dom 移动：

  1. 第一次移动p-1移动到p-3后边
  2. 第二次移动 p-2移动到p-3后边

而我们可以发现，其实只需要直接将 p-3移动到p-1的前边就可以达到目的了。

那么双端 diff 算法是怎么做的呢？为什么可以解决这个问题？

双端 diff 算法是从两端进行比较，我们指定四个索引值分别指向新旧两组 vnode 的头尾元素，然后我们按照下图中每轮四步走的顺序进行比较，

① 新子节点的头部节点newStartIdx跟旧子节点中的头部节点oldStartIdx比较，如果两者 key 相同，说明是同一个节点，

TODO: 快速 diff ​