浅谈Vue DIFF

目录

• 不带 key 的操作
• 带 key 的操作
• 简单 DIFF
• Vue是如何找到需要进行移动的元素
• Vue是如何移动元素的
• Vue是如何进行新增元素的
• Vue 是如何删除多余的旧元素的
• 双指针 DIFF
• 快速 DIFF
• 如何新增？
• 如何删除？
• 如何判断是否移动？

不带 key 的操作

对于不带 key 的情况，我们的操作略显原始，整个流程如下：

• 首先获取 oldChildren 和 newChildren 的长度
• 如果说两者一样长的话

就从 tag/children 逐个进行比对，如果相同，则进行保留，如果不同，则进行删除，并且重新进行挂载。

• 如果说两者不一样长的话

如果 newChildren 更长，就在进行如上操作之后，再从 newChildren 多处的部分开始，逐个进行添加。

如果 oldChildren 更长，就在进行如上操作之后，再从 oldChildren 多出的部分开始，逐个进行删除。

代码如下：

const patch = (n1, n2) => {
    if(n1.tag !== n2.tag) {
      const n1ElParent = n1.el.parentElement;
      n1ElParent.removeChild(n1.el);
      mount(n2, n1ElParent)
    } else {
      // 取出 element 对象，并且在 n2 中进行保存
      const el = n1.el = n2.el
      // 为了获取 value
      const oldProps = n1.props || []
      const newProps = n2.props || []
      // 遍历新对象
      for(const key in newProps) {
        const oldValue = oldProps[key]
        const newValue = newProps[key]
        if(oldValue != newValue) {
          if(key.startsWith("on")) {
            el.addEventListener(key.slice(2).toLowerCase(), newValue);
          } else {
            el.setAttribute(key, newValue);
          }
        }
      }
      // 删除旧的 props
      for(const key in oldProps) {
        if(key.startsWith("on")) {
          const value = oldProps[key];
          // removeEventListener(type, listener)
          // type ==> 一个字符串，表示需要移除的事件类型 ｜ listener ==> 需要从目标事件中移除的事件处理函数。
          el.removeEventListener(key.slice(2).toLowerCase(), value)
        } 
        if(!(key in newProps)) {
          el.removeAttribute(key)
        }
      }
      // 3. 处理children
      const oldChildren = n1.children || []
      const newChildren = n2.children || []
      // 如果新的 node 的 children 只是一个字符串，那直接覆盖就可以了
      if (typeof newChildren === 'string') {
        // 如果旧的也是字符串，那就判断一下是不是一样的，然后覆盖一下
        if (typeof oldChildren === 'string') {
          if (newChildren != oldChildren) {
            el.textContent = newChildren
          }
        } else {
          // 如果新的是很多很多东西，我直接覆盖就可以了
          el.innerHTML = newChildren
        }
      } else {
        // 这种情况新的 node 并不是字符串，是数组啥的
        // 然后判断一下旧的的情况
        // 如果是字符串
        if(typeof oldChildren === 'string') {
          el.innerHTML = ""
          newChildren.forEach((item) => {
            mount(item, el)
          })
        } else {
          // 如果都不是字符串的话
          // 拿到共同长度
          const commonLength = Math.min(oldChildren.length, newChildren.length)
          for(let i=0;i<commonLength;i++) {
            patch(oldChildren[i], newChildren[i])
          }
          // 如果新的节点的子节点多一些的话，那就全部挂载上去
          if(newChildren.length > oldChildren.length) {
            newChildren.slice(commonLength).forEach((item) => {
              mount(item, el)
            })
          }
          // 如果旧的节点的子节点多一些，那就一个个删除！
          if(newChildren.length > oldChildren.length) {
            oldChildren.slice(commonLength).forEach((item) => {
              el.removeChild(item)
            })
          }
        }
      }
    }
  }

带 key 的操作

这个就比较灵性了。

简单 DIFF

首先我们还是正常进行比对

我们开两个 for 循环，外层是 newChildren ，内层是 oldChildren，如果两者的 key 相同，我们就可以进行到下一步了 ==> 找到需要进行移动的元素。

Vue是如何找到需要进行移动的元素

我们会创建一个 lastIndex 参数，用来标记 key 相同的情况的最大的 Index，大致逻辑是：

if (j < lastIndex) {
  // 进行 patch 操作
} else {
  lastIndex = i
}

所以在我们的 j 小于 lastIndex 的时候，我们就知道，该移动了～

Vue是如何移动元素的

我们知道 j（旧的vnode Index） < lastIndex 的 case 我们要进行移动

我们首先要拿到 newChildren[i – 1]（新 vnode 的 i – 1 的值），当前新节点的前一个 vnode，然后进行移动，最后直接 insert 就好了。

Vue是如何进行新增元素的

我们会创建一个 find 参数，用来判断这个节点是不是新节点

如果是旧节点，我们就走移动逻辑

如果是新节点，我们就在后面新增，这里有一个问题，就是我加在谁的后面

如果 newChildren[i – 1] 为 null，我们就直接挂载到第一个节点上

如果 newChildren[i – 1] 不为 null，我们就把新节点挂载到 newChildren[i – 1] 上

Vue 是如何删除多余的旧元素的

我们遍历完新元素之后，还需要遍历一遍旧元素，如果说当前旧元素的 key 在新元素中无对应，那就摘出来，删除它。

双指针 DIFF

流程如下：

• 首先是 oldStart <- newStart
• 然后是 oldEnd <- newEnd
• 然后是 oldEnd <- newStart
• 最后是 newEnd <- newStart

这样看起来是没有问题的，但是如果没有一个匹配到呢，那是不是就有问题啦？

在这种情况下，我们应该用 newStart 的 key 和 oldChildren 中的所有 key 做比较，得到 idx ，如果 idx > 0 ，则我们就做移动，然后把这个位置设置为 undefined，后面如果碰到了这个位置就直接跳过去。

快速 DIFF

快速 DIFF 做了一个预处理，把相同的东西提前打补丁处理了。

分别从前往后开循环以及从后往前开循环，把相同的处理掉，不同的留下来。

如何新增？

如图所示，如果我们前后两轮循环遍历完之后，newEnd <= j，就说明有新增，我们找到 oldEnd，while(j >= newEnd)在它的后面一个接一个的挂载进去就可以了。

如何删除？

如图所示，如果我们前后两轮循环遍历完之后，oldEnd <= j，就说明有新增，我们找到 oldEnd，while (j <= oldEnd) 一路删除上去。

我们刚才看到的两种都是理想情况，那如果预处理之后情况依旧复杂呢？

function patchKeyedChildren(n1, n2, container) { 
    const newChildren = n2.children
    const oldChildren = n1.children
    // 更新相同的前置节点
    // 省略部分代码
    // 更新相同的后置节点
    // 省略部分代码
    if (j > oldEnd && j <= newEnd) { 
        // 省略部分代码 
    } else if (j > newEnd && j <= oldEnd) { 
        // 省略部分代码 
    } else {
        // 增加 else 分支来处理非理想情况
    }
}

这个时候我们再开一个 source 数组

source 数组将用来存储新的一组子节点中的节点在旧的一组子节点中的位置索引，后面将会使用它计算出一个最长递增子序列，并用于辅助完成 DOM 移动的操作

由于之前我们要寻找两个 key 相等的值需要使用两个 for 循环，这样就会导致时间复杂度相当的高，所以我们在这里使用了一个 key-index[新数组的索引]的映射表，这样我们只需要做一次便利就可以了，不需要去做嵌套，时间复杂度从 O(N^2) -> O(N)。

如何判断是否移动？

和之前简单 DIFF 的流程很像，之前我们是找最大索引值，如果索引小的都需要移动，索引更大则更新 lastIndex

我们在讲解简单 Diff 算法时曾提到，如果在遍历过程中遇到的索引值呈现递增趋势，则说明不需要移动节点，反之则需要。

所以这里的 moved 为 true 我们就可以移动了。

如何移动元素通过 source 找到最长递增子序列

通过最长递增子序列得到一个子序列索引的数组，最长递增子序列不需要移动

然后做处理，对于新节点，也就是 source 中是 -1 的情况，我们直接新增就好了，如果不是新节点，我们就判断两者是否相同，相同则移动最长递增子序列中的索引，不同则移动 source 中的索引。

以下是对于索引中两者不相同的处理。