关于vue.js:和面试官聊聊Diffvue2

这是聊 diff 的第二篇文章，聊聊 vue2 的 diff 思路. 思路次要来自 vue-design 我的项目

【第一篇】和面试官聊聊 Diff___React
【第二篇】和面试官聊聊 Diff___vue2(本文)
【第三篇】和面试官聊聊 Diff___Vue3

为了更好的浏览体验, 倡议从第一篇看起

我是一名前端的小学生。行文中对某些设计原理了解有误 非常欢送 大家探讨斧正😁😁😁，谢谢啦！当然有好的倡议也谢谢提出来

（玩笑）

Let’s start

本文重视的是 patch 过程，具体的细节和边界就没有思考。

== 另外注意 ==

三篇文章 diff 的解说，为了不便展现节点复用，用了 children 保留内容，实际上这是不合理的，因为 children 不同还会递归补丁（patch）

diff 也不是 vue optimize 的全副，只是其中一部分，例如 compile 时确定节点类型，不同类型不同的 mount/patch 解决形式等等。
Vue2.x 的 diff 绝对于 react 更好一些，防止了一些不必要的比对。

基本思路

当初比如说由若干个新老节点（preNodes / nextNodes）。

应用 nextStartIdx、nextEndIdx、nextStartNode、nextEndNode 保留 == 新节点 == 首尾索引和首尾节点。
应用 preStartIdx、preEndIdx、preStartNode、preEndNode 保留 == 老节点 == 首尾索引和首尾节点。

先将新旧节点首尾一一比对，遇到 undefined 跳过
- 如果雷同则 前移 / 后移 比对节点（首首雷同，均后移；尾尾雷同，均前移；首尾雷同，新首后移，旧尾前移；尾首雷同）。
- 如果存在首尾遍历了全副节点，那么删除多余节点（状况①）或新增节点（状况②）即可
雷同的都比对结束后，将新节点（nextNodes）中未比对的每个节点与老节点（preNodes）中 未比对 节点（是一个 key 和 index 对应的 map）中所有节点比对
- 如果存在雷同，将老节点中相应节点重置为 undefined, 否者在新生成节点中增加 / 删除相应节点。

状况①（也可能是首尾 / 尾首比对），再持续循环，会有 preStartIdx > preEndIdx, 表明有新增节点，要增加

状况②（也可能是首尾 / 尾首比对），再持续循环，会有 nextStartIdx > nextEndIdx, 表明有多余节点，要删除

代码体现：

if(preStartIdx > preEndIdx) { // 有间断多余的新节点需减少
  const addStartIndex = nextStartIdx > 0 ? nextStartIdx-1 : 0;
  let insertIndex = newNodes.findIndex(node => nextNodes[addStartIndex].key === node.key)
  for(let i = nextStartIdx; i<= nextEndIdx; i++){newNodes.splice(insertIndex +1, 0, nextNodes[i])
    insertIndex++;
  }
}else if(nextStartIdx > nextEndIdx) {// 有间断多余的旧节点，需删除(开端开始删除)  123456 | 1256
  // const delStartIndex = preStartIdx > 0 ? preEndIdx -1 : 0;
  let deleteIndex = newNodes.findIndex(node => preNodes[preEndIdx].key === node.key)
  for(let i=preEndIdx; i>=preStartIdx; i--){if(preNodes[i] === undefined) continue;
    newNodes.splice(deleteIndex, 1);
    deleteIndex--;
  }
}

比方有以下节点：

// 旧节点
const preNodes = [{key: "k-1", children: "<span>old1</span>"},
  {key: "k-2", children: "<span>old2</span>"},
  {key: "k-3", children: "<span>old3</span>"},
  {key: "k-4", children: "<span>old4</span>"},
  {key: "k-5", children: "<span>old5</span>"},
  {key: "k-6", children: "<span>old6</span>"},
  {key: "k-7", children: "<span>old7</span>"},
  {key: "k-8", children: "<span>old8</span>"},
]
// 新节点
const nextNodes = [{key: "k-8", children: "<span>8</span>"},
  {key: "k-7", children: "<span>7</span>"},
  {key: "k-12", children: "<span>12</span>"},
  {key: "k-5", children: "<span>5</span>"},
  {key: "k-3", children: "<span>3</span>"},
  {key: "k-11", children: "<span>11</span>"},
  {key: "k-2", children: "<span>2</span>"},
  {key: "k-13", children: "<span>13</span>"},
  {key: "k-9", children: "<span>9</span>"},
  {key: "k-1", children: "<span>1</span>"},
]

通过补丁 diff 后, 冀望失去后果

能够看到老节点都失去了复用~~

用图来具体实现下面节点变换过程。

== 留神 ==：图中删除插入是我用数组代替节点插入的操作（例如insertbefore），其实失常节点插入时，就会检测插入节点是否存在，如果存在是不会插入反复节点的，只会将原来节点调换至新的地位。

这个例子就是把下面提到的图形解剖一步步出现。一大波图来袭

### 阐明

应用 nextStartIdx、nextEndIdx、nextStartNode、nextEndNode 保留 == 新节点 == 首尾索引和首尾节点。

应用 preStartIdx、preEndIdx、preStartNode、preEndNode 保留 == 老节点 == 首尾索引和首尾节点。

绿色示意新增节点，红色示意删除节点，湖蓝色示意复用节点。

初始状态

preStartIdx = 0；preEndIdx = 7；nextStartIdx = 0；nextEndIdx = 9；
尾首雷同，将旧首节点（k-1）插入到旧尾节点 (k-8) 前面。且 preStartIdx + 1, nextEndIdx -1

preStartIdx = 1；preEndIdx = 7；nextStartIdx = 0；nextEndIdx = 8；
尾首雷同，将旧尾节点（k-8）插入到旧首节点 (k-2) 后面。且 nextStartIdx + 1, preEndIdx -1

preStartIdx = 1；preEndIdx = 6；nextStartIdx = 1；nextEndIdx = 8；
尾首雷同，将旧尾节点（k-7）插入到旧首节点 (k-2) 后面。且 nextStartIdx + 1, preEndIdx -1

preStartIdx = 1；preEndIdx = 5；nextStartIdx =2；nextEndIdx = 8；
两边 (首尾) 比对实现，开始两头比对（newNodes 未比对节点与 preNodes 未比对所有节点一一比对），k-12在老节点未比对区间无雷同，减少到 k - 2 后面

preStartIdx = 1；preEndIdx = 5；nextStartIdx = 3；nextEndIdx = 8；
找到 k-5 雷同（复用）,k-5 减少到 k-2 后面, 删除原来 ( newNodes) 的 k-5，老节点中 k-5置为undefined

preStartIdx = 1；preEndIdx = 5；nextStartIdx = 4；nextEndIdx = 8；
找到 k-3雷同（复用）,k-3减少到 k-2后面, 删除原来 (newNodes) 的 k-3，老节点中 k-3 置为undefined

preStartIdx = 1；preEndIdx = 5；nextStartIdx = 5；nextEndIdx = 8；
k-11未找到雷同节点，k-11 减少到 k-2 后面

preStartIdx = 1；preEndIdx = 5；nextStartIdx = 6；nextEndIdx = 8；
首首节点 k-2 雷同，k-2 减少到 k-2 后面, 删除原来的 k-2

因为 undefined 会跳过，即 preStartIdx = 3；preEndIdx = 5；nextStartIdx = 0；nextEndIdx = 9；
k-13 未找到雷同节点，k-13 减少到 k-4 后面

preStartIdx = 3；preEndIdx = 5；nextStartIdx = 8；nextEndIdx = 8；
新节点前后索引相等，k-9 增加到 k-4 后面

满足 nextStartIdx >nextEndIdx 删除多余节点

最初后果

兄弟们，点个赞啊，累死我了，哎~~~(图搞了我两个多小时)

这个例子节点为;

const preNodes = [{key: "k-1", children: "<span>old1</span>"},
  {key: "k-2", children: "<span>old2</span>"},
  {key: "k-3", children: "<span>old3</span>"},
  {key: "k-4", children: "<span>old4</span>"},
  {key: "k-5", children: "<span>old5</span>"},
  {key: "k-6", children: "<span>old6</span>"},
  {key: "k-7", children: "<span>old7</span>"},
  {key: "k-8", children: "<span>old8</span>"},
  {key: "k-9", children: "<span>old9</span>"},
]
// /* 旧首 == 新尾  旧尾 == 新首 旧尾 == 新首 首首 旧首 == 新尾 尾尾 */
const nextNodes = [{key: "k-9", children: "<span>9</span>"},
  {key: "k-12", children: "<span>12</span>"},
  {key: "k-8", children: "<span>8</span>"},
  {key: "k-13", children: "<span>13</span>"},
  {key: "k-6", children: "<span>6</span>"},
  {key: "k-2", children: "<span>2</span>"},
  {key: "k-15", children: "<span>15</span>"},
  {key: "k-5", children: "<span>5</span>"},
  {key: "k-14", children: "<span>14</span>"},
  {key: "k-19", children: "<span>19</span>"},
  {key: "k-7", children: "<span>7</span>"},
  {key: "k-3", children: "<span>3</span>"},
  {key: "k-1", children: "<span>1</span>"},
]

为什么非凡呢，因为会产生首尾和两头比对穿插进行（其实原本就相互影响），
这个我就不去画图解释了，这个例子为加深了解所用。

间接贴代码了

function vue2_diff(){
   const preNodes = [{key: "k-1", children: "<span>old1</span>"},
     {key: "k-2", children: "<span>old2</span>"},
     {key: "k-3", children: "<span>old3</span>"},
     {key: "k-4", children: "<span>old4</span>"},
     {key: "k-5", children: "<span>old5</span>"},
     {key: "k-6", children: "<span>old6</span>"},
     {key: "k-7", children: "<span>old7</span>"},
     {key: "k-8", children: "<span>old8</span>"},
   ]

   const nextNodes = [{key: "k-8", children: "<span>8</span>"},
     {key: "k-7", children: "<span>7</span>"},
     {key: "k-12", children: "<span>12</span>"},
     {key: "k-5", children: "<span>5</span>"},
     {key: "k-3", children: "<span>3</span>"},
     {key: "k-11", children: "<span>11</span>"},
     {key: "k-2", children: "<span>2</span>"},
     {key: "k-13", children: "<span>13</span>"},
     {key: "k-9", children: "<span>9</span>"},
     {key: "k-1", children: "<span>1</span>"},
   ]

   let preStartIdx = 0;
   let nextStartIdx = 0;
   let preStartNode = preNodes[0];
   let nextStartNode = nextNodes[0];
   let preEndIdx = preNodes.length - 1;
   let nextEndIdx = nextNodes.length - 1;
   let preEndNode = preNodes[preEndIdx];
   let nextEndNode = nextNodes[nextEndIdx];

   const newNodes = JSON.parse(JSON.stringify(preNodes));

   function isSameNode(node1, node2){return node1.key === node2.key;}

   while(preStartIdx <= preEndIdx && nextStartIdx <= nextEndIdx){if(preStartNode === undefined){console.log('undefined:', preStartNode);
       preStartNode = preNodes[++preStartIdx];
     }else if(preEndNode === undefined){console.log('undefined:', preEndNode);
       preEndNode = preNodes[--preEndIdx]
     }else if(isSameNode(preStartNode, nextStartNode)){
       // 新旧首首雷同
       preStartNode = preNodes[++preStartIdx];
       nextStartNode = nextNodes[++nextStartIdx];
     }else if(isSameNode(preEndNode, nextEndNode)) {
       // 新旧尾尾雷同
       preEndNode = preNodes[--preEndIdx];
       nextEndNode = nextNodes[--nextEndIdx];
     }else if(isSameNode(preStartNode, nextEndNode)) {
       // 执行 将旧首节点插入到旧尾节点前面
       const insertPos = newNodes.findIndex(node => node.key === preEndNode.key);
       const deletePos = newNodes.findIndex(node => node.key === preStartNode.key);
       // 增加
       newNodes.splice(insertPos+1, 0, preStartNode);
       // 删除
       const delIndex = insertPos < deletePos ? deletePos + 1 : deletePos;
       newNodes.splice(delIndex, 1);
       
       preStartNode = preNodes[++preStartIdx];
       nextEndNode = nextNodes[--nextEndIdx];
     }else if(isSameNode(preEndNode, nextStartNode)) {
       // 执行 将旧尾节点插入（insertBefore）到旧首节点后面
       const insertPos = newNodes.findIndex(node => node.key === preStartNode.key);
       const deletePos = newNodes.findIndex(node => node.key === preEndNode.key);
       // 增加
       newNodes.splice(insertPos, 0, preEndNode);
       // 删除
       const delIndex = insertPos < deletePos ? deletePos + 1 : deletePos;
       newNodes.splice(delIndex, 1);
       nextStartNode = nextNodes[++nextStartIdx];
       preEndNode = preNodes[--preEndIdx];
     }else {const oldKeyInIndex = {};
       for(let i=preStartIdx; i<=preEndIdx; i++){if(!preNodes[i]) continue; // 解决 undefined 状况
         oldKeyInIndex[preNodes[i].key] = i;
       }
       const moveNodeIndex = oldKeyInIndex[nextStartNode.key]
       if(moveNodeIndex !== undefined){
         // 找到即 insertBefore, 将以后节点插入到旧开始节点在 newNodes 的地位的前面
         const insertPos = newNodes.findIndex(node => node.key === preStartNode.key);
         const deletePos = newNodes.findIndex(node => node.key === preNodes[moveNodeIndex].key);

         newNodes.splice(insertPos, 0, preNodes[moveNodeIndex]);
         newNodes.splice(deletePos+1, 1);
         preNodes[moveNodeIndex] = undefined;
       }else {// 增加
         const insertPos = newNodes.findIndex(node => preStartNode.key === node.key);  
         newNodes.splice(insertPos, 0, nextStartNode);
       }
       nextStartNode = nextNodes[++nextStartIdx];
     }
   }
   if(preStartIdx > preEndIdx) { // 有间断多余的新节点需减少
     const addStartIndex = nextStartIdx > 0 ? nextStartIdx-1 : 0;
     let insertIndex = newNodes.findIndex(node => nextNodes[addStartIndex].key === node.key)
     for(let i = nextStartIdx; i<= nextEndIdx; i++){newNodes.splice(insertIndex +1, 0, nextNodes[i])
       insertIndex++;
     }
   }else if(nextStartIdx > nextEndIdx) {// 有间断多余的旧节点，需删除(开端开始删除)  123456 | 1256
     // const delStartIndex = preStartIdx > 0 ? preEndIdx -1 : 0;
     let deleteIndex = newNodes.findIndex(node => preNodes[preEndIdx].key === node.key)
     for(let i=preEndIdx; i>=preStartIdx; i--){if(preNodes[i] === undefined) continue;
       newNodes.splice(deleteIndex, 1);
       deleteIndex--;
     }
   }
   console.log('vue2 diff:', newNodes);
  }

本文中例子只是为了更好了解 diff 思路, patch 过程与真实情况还有些差别

反复节点问题。新老节点有反复节点时，本文 diff 函数没解决这种状况。
仅是用数组模仿了 Vnode, 实在的 Vnode 不止 key 和 children, 还有更多的参数
比对雷同节点时，仅比对了 key, 实在其实还波及到 class（类名）、attrs（属性值）、孩子节点（递归）等属性比对; 另外下面的 children 也要比对若不同也要递归遍历
插入、删除、增加节点我用的数组。其实应该用 insertbefore、delete、add。这些办法均是独自封装不能采纳绝对应的 Dom Api, 因为 vue 不止用在浏览器环境。
…

Vue@3.2⇲ 曾经进去了，React@18也快了，哎，框架学不完的。还是多看看不变的货色吧（js, 设计模式，数据结构，算法 …）

哎哎哎，，同志，看完怎么不点赞，别看他人就说你呢，你几个意思？

站在他人肩膀能看的更远。

【举荐】vue-design
【掘金小册】分析 Vue.js 外部运行机制
【Vue patch 源码地址】vue-next ⇲

以上。

关于vue.js:和面试官聊聊Diffvue2

vue2_diff

比对流程

图例解说

例子 1

加深了解的例子

代码实现

代码

总结

参考