乐趣区

关于vue3:和面试官聊聊DiffVue3

这是 聊 diff 的第三篇文章,聊聊 vue3 的 diff 思路. 思路次要来自 vue-design 我的项目

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

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

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

(玩笑)

Let’s start


Vue3_diff

过程剖析

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

== 另 外 注 意 ==

  • 三篇文章 diff 的解说,为了不便展现 节点复用,用了 children 保留内容,实际上这是不合理的,因为 children 不同还会递归补丁(patch)
  • diff 也不是 vue optimize 的全副,只是其中一部分,例如 compile 时确定节点类型,不同类型 不同的 mount/patch 解决形式等等。
    Vue2.x 的 diff 绝对于 react 更好一些,防止了一些不必要的比对。

我先假如有如下节点, keyVnodekey, 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 从结尾找,preEndIndexnextEndIndex 别离对应老节点和新节点的开端索引。找到就减少 J 或者缩小 preEndIndexnextEndIndex

代码如下

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 外面的项程序是不必动的,新节点的未比对节点只须要在这些项前后插入即可。
具体实现就是遍历noPatchedIndexlisArr

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

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

为了直观的了解,上面来一波操作图:i jnoPatchedIndexlisArr

删除的为红色,新增的为绿色,复用的节点为灰色;
节点复用插入时调用的是 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 也要比对若不同也要递归遍历
  • 插入、删除、增加节点我用的数组。其实应该用 insertbeforedeleteadd。这些办法均是独自封装不能采纳绝对应的 Dom Api, 因为 vue 不止用在浏览器环境。

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

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


参考

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

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

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


以上。

退出移动版