关于vue3:和面试官聊聊DiffVue3

这是聊 diff 的第三篇文章，聊聊 vue3 的 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 更好一些，防止了一些不必要的比对。

我先假如有如下节点, key 是 Vnode 的 key, children 代表该节点的内容

// 以前的节点
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>"},
]
// 新节点，最初更新的后果
const nextNodes = [{key: "k-11", children: "<span>11</span>"},
  {key: "k-0", children: "<span>0</span>"},
  {key: "k-5", children: "<span>5</span>"},
  {key: "k-13", children: "<span>13</span>"},
  {key: "k-1", children: "<span>1</span>"},
  {key: "k-7", children: "<span>7</span>"},
  {key: "k-16", children: "<span>16</span>"},
  {key: "k-3", children: "<span>3</span>"},
  {key: "k-15", children: "<span>15</span>"},
  {key: "k-17", children: "<span>7</span>"},
  {key: "k-4", children: "<span>4</span>"},
  {key: "k-6", children: "<span>6</span>"}
]

diff 是基于新旧的 diff, 先要明确这个大前提，如果刚刚开始没有节点，则会先 mount 而不会 patch。
最初冀望的后果（老节点都失去了复用）

另外新产生节点（newNodes）是基于老节点的，于是

// 最终的节点数据, 因为最终的节点是基于老节点的，这里做个模仿
let newNodes = JSON.parse(JSON.stringify(preNodes));

preNodes: 老节点；
nextNodes：新节点；
newNodes: 新产生节点，最初用于渲染为实在 dom. 其实 vue2 晚期就是先齐全产生新节点，最初再渲染为实在 dom. 前面版本变为一次（patch）优化遍历时就更新相应的 Dom.

中心思想提炼：从老节点中找到与新节点中 key 雷同的节点，进行复用。

具体思路：

1. 先找两端雷同的节点（key 雷同），找到即再往两头找。

如图，J 从结尾找，preEndIndex 和 nextEndIndex 别离对应老节点和新节点的开端索引。找到就减少 J 或者缩小 preEndIndex 和 nextEndIndex。

代码如下

let j = 0;

let preEndIndex = preNodes.length - 1;
let nextEndIndex = nextNodes.length - 1;
let preVNode = preNodes[j];
let nextVNode = nextNodes[j];

while(preVNode.key === nextVNode.key){
  j++;
  preVNode = preNodes[j];
  nextVNode = nextNodes[j];
}
preVNode = preNodes[preEndIndex];
nextVNode = nextNodes[nextEndIndex];
while(preVNode.key === nextVNode.key){preVNode = preNodes[--preEndIndex];
  nextVNode = nextNodes[--nextEndIndex];
}

思考到一种状况

下面的状况会呈现老节点比对完了，新节点还存在，那么最初会造成 J > preEndIndex[状况 1], 同理, 老节点未比对完，新节点曾经比对完, 那么会呈现 J > nextEndIdnex[状况 2].
针对这两种状况，

都要防止循环，引入 label 解决。
另外，状况 1 须要（从 newNodes 中）删除多余的节点，状况 2 须要（向 newNodes）减少新节点中未遍历的节点。

于是把原来代码改一下：

// ....
outer: {while(preVNode.key === nextVNode.key){
    j++;
    if(j> preEndIndex || j > newEndIndex) {break outer;}
    preVNode = preNodes[j];
    nextVNode = nextNodes[j];
  }
  preVNode = preNodes[preEndIndex];
  nextVNode = nextNodes[nextEndIndex];
  while(preVNode.key === nextVNode.key){if(j> preEndIndex || j > nextEndIndex) {break outer;}
    preVNode = preNodes[--preEndIndex];
    nextVNode = nextNodes[--nextEndIndex];
  }
}
if(j > preEndIndex) {
  // 老节点遍历完了，新节点还存在，将新节点放入。for(let i = j; i< nextEndIndex; i++){const addedNode = nextNodes[i];
    // 留神：框架外部是利用 appendchild 更新 dom.
    newNodes.splice(i,0,addedNode);
  }
}
else if(j > nextEndIndex){
  // 新节点遍历完了，老节点还存在，将老节点删除。const deleteLen = preEndIndex - j;
  // 留神：框架外部是重写 removeChild 更新 dom.
  newNodes.splice(i,deleteLen);
}else {// 均还有不同节点时}

大多数状况就像刚开始的例子一样：两头都还存在不同的节点，须要挪动和新增 。这个状况是patch 次要解决的中央, 代码写在下面的 else 外面。

具体思路是怎么呢，

2. 产生一个老节点可复用节点的映射数组

学生成一个每项为 -1 的数组noPatchedIndex，长度为新节点未遍历的节点长度。

遍历 未比对的老节点和新节点（这里有个优化细节：新节点不必遍历，因为构造的特殊性，间接生成key 对应 index 的对象 keyInIndex 例如{k-1: 0, k-2: 1, ...}，前面间接取）。

未比对老节点中如果存在未比对新节点雷同的节点那么在 noPatchedIndex 相应地位保存起来它在老节点中的索引。

另外判断时，新节点中不存在还需删除老节点，并且得出是否须要挪动元素（索引数组 noPatchedIndex 中存在非递增排序，即数组中以后项不能大于之后的项）

大略这个意思

新生成节点。k- 2 在新节点 (nextNodes) 中不存在，所以被删除。

3. 解决须要挪动的状况（复用节点解决）

大略有如下步骤：

①找出 noPatchedIndex 最大递增子序列 lisArr索引数组
②将未比对新节点与顺次插入到新节点。

针对①，这里有一个函数 lis，

lis([3,1,5,4,2]) //[1, 4] | 1,2 为最大递增子序列
lis([1,2,3]) //[0, 1, 2] | 1,2,3 为最大递增子序列
lis([0,-1,8,6,10,7]) //[1, 3, 5] | -1,6,7 为最大递增子序列

lis 具体实现请参考我的另一篇文章 [算法篇 — 寻找最大递增子序列]()

于是有

针对②，为什么要找最大递增子序列 lisArr呢，因为对于 lisArr 外面的项程序是不必动的，新节点的未比对节点只须要在这些项前后插入即可。
具体实现就是遍历noPatchedIndex 与 lisArr：

noPatchedIndex 项等于 -1, 示意，老节点中不存在的项，须要新增
noPatchedIndex 索引与 lisArr 不相等时，须要挪动老节点到响应的地位
noPatchedIndex 索引与 lisArr 相等时，不做操作。

须要留神：遍历都是从后向前遍历，目标是避免数组长度变换影响索引值进而影响节点取值，插入，删除。

为了直观的了解，上面来一波操作图：i 与 j 为 noPatchedIndex与 lisArr

删除的为红色，新增的为绿色，复用的节点为灰色；
节点复用插入时调用的是 DOM API [insertBefore]()这个是先回增加该节点如果存在反复是会删除原有节点的；
插入地位为节点 nextNodes[nopatchedIndex[lisArr[j]]] 对应在 oldNodes 的地位

1)i =10, j = 2 ; 节点 k-4 复用

2)i=9, j=1

3)i=8, j=1. 新增

4)i=7,j=1. k-3复用

5)i=6, j=0

6)i=5, j=0

7)i=4, j=0. 插入（波及到减少和删除），这里因为插入的是老节点，而原节点（2）在插入地位（0）前面，所以新增之后删除的索引地位要减一（代码中会有体现）

8)i=3,j=0新增

9)i=2, j=0. 插入（波及到减少和删除），这里因为插入的是老节点，而原节点（9）在插入地位（0）前面，所以新增之后删除的索引地位要减一（代码中会有体现）

10)i=1,j=0

11)i=0, j=0, 新增

12) i= -1, 循环完结。

最初后果来看，k-5, k-1, k-2, k-4, k-6 失去了复用, 那么 k-2 到哪去了呢，新节点 nextNodes 不含该节点天然在挪动（move）前就删除了！后面提到了。
至此，diff 过程完结了置信其实看图也能够看明确

哎，画图太累了🤣，当初真心对那么文章配有图解说的博主瑞思拜🙏🙏🙏（respect!!!）。absolute!!!

最初奉上全副代码。

// 老节点
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>"},
]
// 新节点
const nextNodes = [{key: "k-11", children: "<span>11</span>"},
  {key: "k-0", children: "<span>0</span>"},
  {key: "k-5", children: "<span>5</span>"},
  {key: "k-13", children: "<span>13</span>"},
  {key: "k-1", children: "<span>1</span>"},
  {key: "k-7", children: "<span>7</span>"},
  {key: "k-6", children: "<span>6</span>"},
  {key: "k-3", children: "<span>3</span>"},
  {key: "k-15", children: "<span>15</span>"},
  {key: "k-17", children: "<span>7</span>"},
  {key: "k-4", children: "<span>4</span>"},
  {key: "k-6", children: "<span>6</span>"}
]
// 最终的节点数据, 因为最终的节点是基于老节点的，这里做个模仿
let newNodes = JSON.parse(JSON.stringify(preNodes));

// 两个都从右边开始比对的索引
let j = 0;

let preEndIndex = preNodes.length - 1;
let nextEndIndex = nextNodes.length - 1;
let preVNode = preNodes[j];
let nextVNode = nextNodes[j];

outer: {while(preVNode.key === nextVNode.key){
    j++;
    if(j> preEndIndex || j > newEndIndex) {break outer;}
    preVNode = preNodes[j];
    nextVNode = nextNodes[j];
  }
  preVNode = preNodes[preEndIndex];
  nextVNode = nextNodes[nextEndIndex];
  while(preVNode.key === nextVNode.key){if(j> preEndIndex || j > nextEndIndex) {break outer;}
    preVNode = preNodes[--preEndIndex];
    nextVNode = nextNodes[--nextEndIndex];
  }
}
if(j > preEndIndex) {
  // 老节点遍历完了，新节点还存在，将新节点放入。for(let i = j; i< nextEndIndex; i++){const addedNode = nextNodes[i];
    // 留神：框架外部是利用 appendchild 更新 dom.
    newNodes.splice(i,0,addedNode);
  }
}
else if(j > nextEndIndex){
  // 新节点遍历完了，老节点还存在，将老节点删除。const deleteLen = preEndIndex - j;
  // 留神：框架外部是重写 removeChild 更新 dom.
  newNodes.splice(i,deleteLen);
}
else {
  // 保留是否须要挪动
  let moved = false;

  const preStart = j;
  const nextStart = j;
  let pos = 0;
  // 保留新节点 key-index 的 map, 防止屡次循环
  const keyInIndex = {}; //{ k-1: 1, k-2: 2, k-3:3,...}
  // 新节点未比对的节点长度
  const newLength = nextEndIndex - nextStart + 1;
  for(let i = nextStart; i< newLength; i++) {keyInIndex[nextNodes[i].key] = i
  }
  const oldLength = preEndIndex - preStart + 1;
  // 避免老节点比新节点多时，删除已找到的反复的节点
  let patched = 0;
  // 产生新节点能复用的老节点的索引数组
  const noPatchedIndex = Array(newLength).fill(-1); //- 1 状态保留
  for(let i = preStart; i< oldLength; i++) {const preNode = preNodes[i];
    if(patched <= nextEndIndex) {
      // 保留老节点 key 在新节点中对应的 index
      const k = keyInIndex[preNode.key];
      if(typeof k !== 'undefined'){
        let idx = k - preStart;
        noPatchedIndex[idx] = i;
        patched++;
        // 筛选出须要往前调换的元素
        if(k < pos) moved = true;
        else pos = k;
      }else {
        // 动静查找删除项索引
        const deleteIndex = newNodes.findIndex(node => node.key === preNodes[i].key)
        newNodes.splice(deleteIndex,1);
      }
    }else {newNodes.splice(i,1)
    }
  }
  
  // 解决须要挪动的状况
  if(moved){const newNodesCopy = JSON.parse(JSON.stringify(newNodes))
    // 最大递增子序列索引
    const lisArr = lis(noPatchedIndex);
    let j = lisArr.length - 1;
    // 遍历新节点中未比对的节点，从前面遍历，避免更新过程 index 非预期变动。for(let i=newLength - 1; i>=0; i--){const current = noPatchedIndex[i];
      // 更新的理论地位
      const pos = i+nextStart;
      let insertPos = newNodes.findIndex(node => node.key === nextNodes[nextStart+lisArr[j]].key);
      if(current === -1){// - 1 即为新增的状况
        // 留神 [1,2,3].splice(0,4) => [4,1,2,3]
        newNodes.splice(insertPos+1, 0, nextNodes[pos]);
        continue;
      }else if(lisArr[j] !== i) {// 能够复用非递增节点的状况
        /*
          insertBefore 作用：如果给定的子节点是对文档中现有节点的援用，insertBefore() 会将其从以后地位挪动到新地位
          以下的操作就是实现 insertBefore 办法。*/
        // 挪动元素在新节点的地位
        let oldPos = newNodes.findIndex(node => node.key === nextNodes[pos].key);

        // 须要删除插入的节点对应原来的节点
        // 新节点中插入老节点对应的地位
        newNodes.splice(insertPos+1, 0, newNodes[oldPos]);
        // 判断插入节点的地位在被插入地位的后面还是前面，如果是前面就加 1
        oldPos = insertPos > oldPos ? oldPos : oldPos+1;
        newNodes.splice(oldPos, 1)
      }else {j--;}
    }
  }
}
console.log('newNodes:', newNodes);
// 寻找最大递增子序列 索引
// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
/*
  [3,1,5,4,2] => [1,2]
*/
function lis(arr) {const p = arr.slice();
  const result = [0]; // 索引数组
  let i;
  let j;
  let u;
  let v;
  let c;
  const len = arr.length;
  for (i = 0; i < len; i++) {const arrI = arr[i];
    if (arrI !== 0) {
      // 取最初一个元素
      j = result[result.length - 1];
      if (arr[j] < arrI) {p[i] = j;
        result.push(i);
        continue;
      }
      u = 0;
      v = result.length - 1;
      //result 长度大于 1 时
      while (u < v) {
        // 取中位数
        c = ((u + v) / 2) | 0;
        if (arr[result] < arrI) {u = c + 1;} else {v = c; //result 中位数大于等于 以后项。v 取中位数}
      }
      if (arrI < arr[result[u]]) {if (u > 0) {p[i] = result[u - 1];
        }
        result[u] = i;
      }
    }
  }
  u = result.length;
  v = result[u - 1];
  while (u-- > 0) {result[u] = v;
    v = p[v];
  }
  return result;
}

本文中例子只是为了更好了解 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 ⇲

另外，大佬们正在翻译 vue3 的英文文档 docs-next-zh-cn

以上。

关于vue3:和面试官聊聊DiffVue3

Vue3_diff

过程剖析

全副代码

总结

参考