patch更新时候，如果新旧节点都是数组的情况，当时采用把旧节点全部清除，然后完全重新添加新节点，这样可以实现目标，但是性能不佳。本章开始介绍vue的渲染器核心diff算法，简单来说就是新旧vnode节点的子节点都是一组节点的情况下，以最小性能开销完成更新操作。

9.1减少DOM操作的性能开销

有如下结构的新旧虚拟节点：

  1. // 旧vnode
  2. const oldVnode = {
  3.   type: "div",
  4.   children: [
  5.     {type: "p", children:1},
  6.     {type: "p", children:2},
  7.     {type: "p", children:3}
  8.   ]
  9. }
  11. // 新vnode
  12. const newVnode = {
  13.   type: "div",
  14.   children: [
  15.     {type: "p", children:4},
  16.     {type: "p", children:5},
  17.     {type: "p", children:6}
  18.   ]
  19. }

按照第8章的做法：

  • 卸载所有旧节点，需要3次DOM删除操作
  • 挂载所有新的子节点，需要3次DOM添加操作

这样完成目标需要6次操作DOM，性能不佳。通过观察可以发现，新旧node的子节点，之后children内容不同，可以通过算法实现只更新内容，这样就可以只需操作3次DOM就能达到目的，性能会提升一倍。
重新调整patchChildren函数

  1. function patchChildren(n1, n2, container) {
  2.   if(typeof n2.children === "string"){
  3.     // ...
  4.   } else if(Array.isArray(n2.children)){
  5.     // 重新实现两组子节点的更新方式
  6.     const oldChildren = n1.children;
  7.     const newChildren = n2.children;
  8.     // 遍历旧的children
  9.     for(let i = 0; i< oldChildren.length; i++){
  10.       //调用patch函数更新子节点
  11.       patch(oldChildren[i], newChildren[i])
  12.     }
  13.   }else{
  14.     //...
  15.   }
  16. }

oldChildren和newChildren分别代表旧的子节点和新的子节点，并将2组对应位置的节点分别传递给patch函数进行更新。patch函数在执行更新时，发现新旧子节点只有文本内容不同，只会更新文本节点内容。
用示意图展示更新过程，菱形表示新子节点，矩形表示旧的子节点，圆形表示真实的DOM节点。
简单的diff - 图1
这种做法减少了操作DOM的次数，但是当新旧子节点数量不同，会存在问题。新的子节点多，无法正常添加新节点，新的节点少，无法删除旧的子节点。
简单的diff - 图2
通过分析，在新旧两组子节点更新是，不能固定变量新的子节点或旧的子节点，而是应该遍历长度短的那一组，然后在接着比对新旧2组子节点的长度，如果新的子节点更长，说明有新节点要添加，否则就是旧的子节点要卸载。

  1. function patchChildren(n1, n2, container) {
  2.   if (typeof n2.children === 'string') {
  3.     if (Array.isArray(n1.children)) {
  4.       n1.children.forEach((c) => unmount(c))
  5.     }
  6.     setElementText(container, n2.children)
  7.   } else if (Array.isArray(n2.children)) {
  8.     const oldChildren = n1.children
  9.     const newChildren = n2.children
  10.     const oldLen = oldChildren.length
  11.     const newLen = newChildren.length
  12.     const commonLength = Math.min(oldLen, newLen)
  13.     for (let i = 0; i < commonLength; i++) {
  14.       patch(oldChildren[i], newChildren[i])
  15.     }
  16.     // 如果 nextLen > prevLen，将多出来的元素添加
  17.     if (newLen > oldLen) {
  18.       for (let i = commonLength; i < newLen; i++) {
  19.         patch(null, newChildren[i], container)
  20.       }
  21.     } else if (oldLen > newLen) {
  22.       // 如果 prevLen > nextLen，将多出来的元素移除
  23.       for (let i = commonLength; i < oldLen; i++) {
  24.         unmount(oldChildren[i])
  25.       }
  26.     }
  27.   } else {
  28.     if (Array.isArray(n1.children)) {
  29.       n1.children.forEach(c => unmount(c))
  30.     } else if (typeof n1.children === 'string') {
  31.       setElementText(container, '')
  32.     }
  33.   }
  34. }

代码示例

9.2DOM复用和Key的作用

diff算法的核心就是减少操作DOM的次数，提升性能。
使用上节的方式，仍存在优化空间，有如下新旧2组子节点

  1. // oldChildren
  2. [{type:"p"}, {type:"div"}, {type:"span"}]
  4. // newChildren
  5. [{type:"span"}, {type:"p"}, {type:"div"}]

如果使用上节的patchChildren算法，仍需要6次DOM操作。
但其实通过观察可以发现，新旧子节点只是顺序不同，最好的处理方式是，移动DOM来完成子节点的更新。
接下来就该处理如何确定新的子节点是否出现在旧的一组子节点中。仅仅通过判断type类型可以吗？其实这是不行的，如果子节点的类型都是p，那么就完全相同，是否就不需要移动更新呢，这样会出现bug。

  1. // oldchildren
  2. [
  3.   { type: 'p', children: '1', key: 1 },
  4.   { type: 'p', children: '2', key: 2 },
  5.   { type: 'p', children: 'hello', key: 3 }
  6. ]
  7. // newChildren
  8. [
  9.   { type: 'p', children: 'world', key: 3 },
  10.   { type: 'p', children: '1', key: 1 },
  11.   { type: 'p', children: '2', key: 2 }
  12. ]

这时就需要使用到key属性，key是节点的身份标识，通过key可以对比新旧子节点是否相同。
简单的diff - 图3
通过key属性可以明确知道新子节点在旧子节点中的位置，就可以进行对应的DOM移动操作。

  1. function patchChildren(n1, n2, container) {
  2.   if (typeof n2.children === 'string') {
  3.     if (Array.isArray(n1.children)) {
  4.       n1.children.forEach((c) => unmount(c))
  5.     }
  6.     setElementText(container, n2.children)
  7.   } else if (Array.isArray(n2.children)) {
  8.     const oldChildren = n1.children
  9.     const newChildren = n2.children
  11.     // 遍历新的 children
  12.     for (let i = 0; i < newChildren.length; i++) {
  13.       const newVNode = newChildren[i]
  14.       let j = 0
  15.       // 遍历旧的 children
  16.       for (j; j < oldChildren.length; j++) {
  17.         const oldVNode = oldChildren[j]
  18.         // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新
  19.         // 节点相同，内容或属性可能已经发生变化
  20.         if (newVNode.key === oldVNode.key) {
  21.           patch(oldVNode, newVNode, container)
  22.           break // 这里需要 break
  23.         }
  24.       }
  25.     }
  27.   } else {
  28.     if (Array.isArray(n1.children)) {
  29.       n1.children.forEach(c => unmount(c))
  30.     } else if (typeof n1.children === 'string') {
  31.       setElementText(container, '')
  32.     }
  33.   }
  34. }

第19行通过对比节点的key是否相同，来判断节点是否是同一个节点。如果是同一个节点，执行patch打补丁操作后直接跳出循环。
在代码中使用了双层for循环，外层循环用于遍历新的一组子节点，内层循环则遍历旧的一组子节点。找到相同节点则进行patch打补丁操作。经过这一步操作能够保证所有可复用的节点本身都更新完毕。
image.png
执行完毕后，key为3的元素仍显示在最后，下一步就需要找出需要移动的DOM元素，进行移动。

注意⚠️：这里的双层for循环，性能是极差的，在实际项目中无法使用。

代码示例

9.3找出需要移动的元素

通过key对比出相同节点可以复用，但是没有进行移动。要想进行移动，第一步需要找出要移动的节点，第二步进行移动操作。
本节目标是找出需要移动的节点元素。
什么情况下需要移动操作呢，肯定是新旧子节点元素的顺序发生了变化。
简单的diff - 图5
上图中新旧2组子节点的顺序没变化，图中也标注了旧的子节点的索引。

  • key为1的节点，在旧children数组中索引为0
  • key为2的节点，在旧children数组中索引为1
  • key为3的节点，在旧children数组中索引为2

新子节点找在旧子节点中找到可以复用的元素，这些复用节点在旧的一组子节点中的位置索引可以得到一个序列： 0 1 2，这是一个递增的序列，这种情况下不需要移动任何节点。
然后按照上节的更新，调整新节点的位置，结果如下图显示
简单的diff - 图6

  • 新子节点的第一个节点为p-3，它的key为3，在旧的子节点中可以查找到相同的key，说明可以复用，该节点在旧的子节点中的索引值为2.
  • 新子节点的第二个节点为p-1，它的key为1，可以在旧的子节点中找到对应key，可以复用，索引为0；
  • 新子节点的第二个节点为p-2，它的key为2，可以在旧的子节点中找到对应key，可以复用，索引为1；

这时可以发现索引值递增的顺序被打乱了，现在的序列为2、0、1；新p-1节点对应的索引小于新p-3节点对应的索引，【索引小本来应排在前】但是排在p-3的后边，说明p-1节点需要移动。同理，p-2节点的索引也小于p-3节点的索引，但仍排在后边，说明p-2节点需要移动。

在旧的children中查找具有相同key值节点的过程中，遇到的最大索引值，如果后续寻找的过程中，存在索引值比当前遇到的最大索引值还要小的节点，说明该节点需要移动。

可以使用lastIndex变量存储整个寻找过程中遇到的最大索引值。

  1. function patchChildren(n1, n2, container) {
  2.   if (typeof n2.children === 'string') {
  3.     // ...
  4.   } else if (Array.isArray(n2.children)) {
  5.     const oldChildren = n1.children
  6.     const newChildren = n2.children
  8.     // 用lastIndex存储寻找过程中遇到的最大索引值
  9.     let lastIndex = 0;
  10.     for (let i = 0; i < newChildren.length; i++) {
  11.       const newVNode = newChildren[i]
  12.       let j = 0
  13.       // 遍历旧的 children
  14.       for (j; j < oldChildren.length; j++) {
  15.         const oldVNode = oldChildren[j]
  16.         // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新
  17.         // 节点相同，内容或属性可能已经发生变化
  18.         if (newVNode.key === oldVNode.key) {
  19.           patch(oldVNode, newVNode, container)
  20.           if(j < lastIndex){
  21.             // 如果当前找到的可复用节点，在旧的children中的索引小于最大索引值lastIndex
  22.             // 说明该节点需要移动，怎么移动，下节在分析
  23.           }else{
  24.             // 如果当前找到的节点，在旧children中的索引 不小于 最大索引值，则更新lastINdex
  25.             lastIndex = j;
  26.           }
  27.           break // 这里需要 break
  28.         }
  29.       }
  30.     }
  32.   } else {
  33.     // ...
  34.   }
  35. }
  • 代码第18行，如果新节子节点的key相同，说明在旧的children中找到了可以复用的DOM节点
  • 用可复用的节点在旧的children中的索引j与lastIndex进行比较，如果j小于lastIndex，说明节点需要移动。否则不需要移动，不移动的同时要将该变量j的值赋值给变量lastIndex，保证lastIndex始终存储着当前遇到的最大索引值。

示例代码

9.4 如何移动元素

上节找到了需要移动的节点元素p-1和p-2，接下来就要移动他们。移动节点指的是移动虚拟节点对应的真实DOM节点。要移动真实的DOM节点，就需要获取到对它的引用。真实DOM节点都是保存在虚拟节点的vnode.el属性中
在更新操作时，渲染器会调用patchElement函数在新旧虚拟节点之间进行打补丁。

  1. function patchElement(n1, n2){
  2.   // 新的vnode n2 引用了真实的DOM元素
  3.   const el = n2.el = n1.el;
  4.   // ...
  5. }

简单的diff - 图7
patchElement函数首先将旧节点的n1.el属性赋值给新节点的n2.el属性，其实就是DOM元素的复用。复用之后，新节点也将持有对真实DOM的引用。
添加上新节节点之间的关系
简单的diff - 图8
更新步骤如下：

  • 新子节点的第一个节点p-3，key为3，通过遍历查询可以找到相同的key值，说明节点可以复用。并且该节点在旧的子节点中的索引为2，原lastIndex值为0，小于2，说明DOM节点不需要移动，并更新lastIndex值为2
  • 新子节点的第二个节点p-1，key为1，从旧节点中查询出可以复用节点，并且该节点在旧的子节点中索引为0，此时lastIndex为2，索引0小于2，说明节点p-1需要移动。
    • 节点p-1对应的真实DOM需要移动。新children的顺序就是更新后真实DOM节点应该的顺序，所以p-1节点在新children的位置就代表了真实DOM更新后的位置。p-1节点排在p-3节点的后边，所以应该把p-1节点所对应的真实DOM移动到节点p-3所对应的真实DOM后面，移动后DOM顺序 p-2、p-3、p-1
  • 新子节点的第三个阶段p-2，key为2，也是可以复用的节点，发现该节点在旧子节点中的索引为1，此时lastIndex的为为2，索引1小于2，所以节点p-2对应的真实DOM需要移动。
    • 节点p-2在新children中排在节点p-1后面，所以应该把p-2对应的真实DOM移动到p-1对应的真实DOM后。

简单的diff - 图9
经过移动操作，此时真实DOM的顺序与新的一组子节点的顺序相同，p-3、p-1、p-2。
最后用代码实现移动的过程。

  1. function patchChildren(n1, n2, children){
  2.   if(typeof n2.children === "string"){
  3.    //...
  4.   }else if(Array.isArray(n2.children)){
  5.     const oldChildren = n1.children;
  6.     const newChildren = n2.children;
  7.     let lastIndex = 0;
  8.     for(let i=0; i<newChildren.length; i++){
  9.       const newVnode = newChildren[i];
  10.       let j=0;
  11.       for(j; j< oldChildren.length; j++){
  12.         const oldeVnode = oldChildren[j];
  13.         if(newVnode.key === oldVnode.key){
  14.           patch(oldVnode, newVnode, container);//先进行patch，然后在进行移动
  15.           if(j<lastIndex){ //需要移动操作
  16.             // 进入这个判断，说明newVnode对应的真实DOM需要移动
  17.             // 先获取newVnode的前一个vnode，定义为preVnode
  18.             const prevVnode = newChildren[i-1];
  19.             // 如果prevVnode不存在，说明当前的newVnode是第一个节点，不需要移动
  20.             if(prevVnode){
  21.               // 将newVnode对应的真实DOM移动到prevVnode所对应的真实DOM后边
  22.               // 需要获取prevVnode所对应真实DOM的下一个兄弟节点，并将其设为锚点
  23.               cosnt anchor = prevVnode.el.nextSibling;
  24.               // 调用insert方法，将newVnode对应的真实DOM 插入到锚点元素前面
  25.               insert(newVnode.el, container, anchor);
  26.             }
  27.           }else{
  28.             lastIndex = j;
  29.           }
  30.           break;
  31.         }
  32.       }
  33.     }
  34.   }
  35. }

更新渲染器的参数方法，新增insert方法；insert函数依赖浏览器原生的insertBefore函数。

  1. const renderer = createRenderer({
  2.   // ...
  3.   insert(el, parent, anchor=null){
  4.     // insertBefore需要锚点元素 anchor
  5.     parent.insertBefore(el, anchor);
  6.   }
  7. })

代码示例

9.5添加新元素

如果在新子节点元素中新增了节点，多个p-4，它的key为4，该节点在旧的子节点中不存在，所以在更新时应该正确的将它挂载，主要分为2步：

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

简单的diff - 图10
开始模拟执行简单的Diff算法：

  • 新的子节点中第一个节点p-3，key为3，可以在旧的子节点中找到可复用节点，索引值为2。此时lastIndex的值为0，索引2不小于0，所以p-3不需要移动，需要将lastIndex的值更新为2；
  • 新的子节点中第2个节点p-1，key为1，可以在旧的子节点中找到可复用节点，索引值为0。此时lastIndex的值为2，索引0小于2，所以p-1需要移动，将节点p-1移动到p-3后边，经过这步的移动，此时真实DOM顺序为p-2、p-3、p-1；

简单的diff - 图11

  • 新的子节点中的第3个节点p-4，它的key为4，尝试在旧子节点中查询该节点，找不到可复用的节点，因此渲染器会把p-4看作新增节点并挂载它。节点p-4在新的一组子节点中的位置在p-1后边，所以应该把节点p-4挂载到p-1对应的真实DOM后边。 此时真实DOM顺序为p-2、p-3、p-1、p-4。

简单的diff - 图12

  • 新的子节点中第4个节点p-2，key为2，可以在旧的子节点中找到可复用节点，索引值为1。此时lastIndex的值为2，索引1小于2，所以p-2需要移动，将节点p-2移动到p-1后边，经过这步的移动，此时真实DOM顺序为p-3、p-1、p-4、p-2；至此真实DOM顺序已经和新的一组子节点顺序相同。

简单的diff - 图13
接下来通过代码实现节点的移动和挂载。
在外层循环中定义了名为find的变量，代表渲染器能否在旧的一组子节点中找到可复用的节点。find的初始值为false，一旦找到可复用节点，find更新为true。如果内层循环结束后，find变量仍为false时，说明newVnode是全新的节点，需要挂载它，为了将节点挂载到正确的位置，需要先获取锚点元素，找到newVnode的前一个虚拟节点，即prevVnode。如果存在，则使用它对应的真实DOM的下一个兄弟节点作为锚点元素，如果不存在，则说明将挂载的newVnode节点是容器元素的第一个子节点，此时使用容器元素的container.firstChild作为锚点元素。最后将锚点元素anchor作为patch函数的第4个参数，调用patch函数完成节点的挂载。

  1. function patchChildren(n1, n2, container) {
  2.     if (typeof n2.children === 'string') {
  3.       //...
  4.     } else if (Array.isArray(n2.children)) {
  5.       const oldChildren = n1.children
  6.       const newChildren = n2.children
  8.       let lastIndex = 0
  9.       // 遍历新的 children
  10.       for (let i = 0; i < newChildren.length; i++) {
  11.         const newVNode = newChildren[i]
  12.         let j = 0
  13.         let find = false
  14.         // 遍历旧的 children
  15.         for (j; j < oldChildren.length; j++) {
  16.           const oldVNode = oldChildren[j]
  17.           // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新
  18.           if (newVNode.key === oldVNode.key) {
  19.             find = true
  20.             patch(oldVNode, newVNode, container)
  21.             if (j < lastIndex) {
  22.               // 需要移动
  23.               const prevVNode = newChildren[i - 1]
  24.               if (prevVNode) {
  25.                 const anchor = prevVNode.el.nextSibling
  26.                 insert(newVNode.el, container, anchor)
  27.               }
  28.             } else {
  29.               // 更新 lastIndex
  30.               lastIndex = j
  31.             }
  32.             break // 这里需要 break
  33.           }
  34.         }
  35.         // 在旧子节点中未找到，说明是新增的节点
  36.         if (!find) {
  37.           //为了将节点挂载到正确位置，需要先获取锚点元素。
  38.           // 首先获取当前newVnode的前一个vnode节点。
  39.           const prevVNode = newChildren[i - 1]
  40.           let anchor = null
  41.           if (prevVNode) {
  42.             // 如果有前一个vnode节点，则使用它的下一个兄弟节点作为锚点元素。
  43.             anchor = prevVNode.el.nextSibling
  44.           } else {
  45.             // 如果没有前一个vnode节点，说明即将挂载的新节点是第一个子节点
  46.             // 需要使用容器元素 container.firstChild作为锚点
  47.             anchor = container.firstChild
  48.           }
  49.           patch(null, newVNode, container, anchor)
  50.         }
  51.       }
  53.     } else {
  54.       // ...
  55.     }
  56.   }

更新patch函数，。让其支持第4个参数。

  1. function patch(n1, n2, container, anchor) {
  2.   if (n1 && n1.type !== n2.type) {
  3.     unmount(n1)
  4.     n1 = null
  5.   }
  7.   const { type } = n2
  9.   if (typeof type === 'string') {
  10.     if (!n1) {
  11.       mountElement(n2, container, anchor)
  12.     } else {
  13.       patchElement(n1, n2)
  14.     }
  15.   } else if (type === Text) {
  16.     if (!n1) {
  17.       const el = n2.el = createText(n2.children)
  18.       insert(el, container)
  19.     } else {
  20.       const el = n2.el = n1.el
  21.       if (n2.children !== n1.children) {
  22.         setText(el, n2.children)
  23.       }
  24.     }
  25.   } else if (type === Fragment) {
  26.     if (!n1) {
  27.       n2.children.forEach(c => patch(null, c, container))
  28.     } else {
  29.       patchChildren(n1, n2, container)
  30.     }
  31.   }
  32. }

代码示例

9.6删除元素

更新子节点时，不仅会遇到新增元素，还会出现元素删除的情况。
简单的diff - 图14
在新的一组子节点中p-2节点已经不存在，说明该节点被删除。
模拟渲染器执行更新的过程
简单的diff - 图15

  • 新的子节点中第一个节点p-3，key为3，可以在旧的子节点中找到可复用节点，索引值为2。此时lastIndex的值为0，索引2不小于0，所以p-3不需要移动，需要将lastIndex的值更新为2；
  • 新的子节点中第2个节点p-1，key为1，可以在旧的子节点中找到可复用节点，索引值为0。此时lastIndex的值为2，索引0小于2，所以p-1需要移动，将节点p-1移动到p-3后边，经过这步的移动，此时真实DOM顺序为p-2、p-3、p-1；

简单的diff - 图16
此时已经更新结束，但是可以发现旧子节点中p-2仍然存在，所以需要增加额外的逻辑来删除遗留的节点。
当基本更新结束后，需要遍历一遍旧的子节点，然后去新的一组子节点中寻找具有相同key值的节点。如果找不到，则说明需要删除该节点。更新patchChild函数

  1. function patchChildren(n1, n2, container){
  2.   if(typeof n2.children === "string"){
  3.    //...
  4.   }else if(Array.isArray(n2.children)){
  5.     const oldChildren = n1.children;
  6.     const newChildren = n2.children;
  7.     let lastIndex= 0;
  8.     for(let i = 0; i<newChildren.length; i++){
  9.      //..
  10.     }
  11.     //遍历旧的一组子节点
  12.     for(let i=0;i<oldChildren.length; i++){
  13.       const oldVnode = oldChildren[i];
  14.       // 用旧子节点 oldVnode去新的一组子节点中寻找具有相同key值的节点
  15.       const has = newChildren.find(vnode => vnode.key === oldVnode.key);
  16.       //     如果新的子节点中不存在
  17.       if(!has){
  18.         // 在新的子节点中不存在，说明需要删除该节点，调用unmount函数将节点卸载
  19.         unmount(oldVnode);
  20.       }
  21.     }
  22.   }
  23. }

代码示例