共计 9032 个字符,预计需要花费 23 分钟才能阅读完成。
这是 聊 diff 的第二篇文章,聊聊 vue2 的 diff 思路. 思路次要来自 vue-design 我的项目
【第一篇】和面试官聊聊 Diff___React
【第二篇】和面试官聊聊 Diff___vue2(本文)
【第三篇】和面试官聊聊 Diff___Vue3
为了更好的浏览体验, 倡议从第一篇看起
我是一名前端的小学生。行文中对某些设计原理了解有误 非常欢送 大家探讨斧正😁😁😁,谢谢啦!当然有好的倡议也谢谢提出来
(玩笑)
Let’s start
vue2_diff
比对流程
本文重视的是 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
),其实失常 节点插入 时,就会检测插入节点是否存在,如果存在是不会插入反复节点的,只会将原来节点调换至新的地位。
例子 1
这个例子就是把下面提到的图形解剖一步步出现。一大波图来袭
### 阐明
- 应用
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 ⇲
以上。