前言
在面试中谈到 vue 源码,一般都会扯扯 diff 算法,而这个 diff 又在网上传的神乎其神的,说是提升了页面更新性能,我们一起看看到底咋回事吧
传统diff算法
在 Jquery 时代,“前辈们”就告诉过我,频繁的操作 DOM 是很消耗性能的,我们可以在拼接完 HTML 片段后,通过 innerHTML 来替换整个 DOM,效率提升杠杠的。
所以之前我一直有个疑问,diff 算法为什么通过比较节点,复用节点可以达到性能提升,直接替换整个 innerHTML 不更高效么?
带着疑问在网上查阅了一些文章,感觉似乎是明白了
首先,创建一个完整的节点对象的成本是非常大的,因为 DOM 节点是个非常复杂的对象
const elm = document.createElement('div') for(let propName in elm) { console.log(propName) } 复制代码
所以即使我们在浏览器中通过 innerHTML 来替换整个 DOM,浏览器也会通过比较不同的节点来达到复用。
比较算法涉及每个新旧节点的两两比较,其复杂度为 O(n^2),比较之后还得计算最小转化方式,所以综合复杂度就是 O(n^3),我们称此为 传统diff算法
具体可以参看 react的diff 从O(n^3)到 O(n) ,请问 O(n^3) 和O(n) 是怎么算出来?
框架层diff算法的原理
相较于 传统的diff算法
,框架层的 diff 有个大前提假设
Web UI 中 DOM 节点跨层级的移动操作特别少,可以忽略不计
所以 diff 的核心就在于,它只对同层节点进行比较,忽略跨层节点的复用
就如上图所示,只会比较父元素相同的同层节点的复用性。
值得注意的是,同层节点的比较也不会两两进行,而是按照一定的顺序比较,或通过 key 属性判断,所以只需要遍历一次新节点,因此算法的复杂度就降低到了O(n)
通过vue源码来看diff
其实 diff 算法的原理就是这么简单,无非是递归加上遍历节点来比较节点复用性。但在 vue 源码中,具体是如何实现的呢?一起看看
虚拟节点(Virtual Dom)
首先要明白,在 vue 中会维护一个和 DOM 节点对应的 vnode
对象
例如
<div key="1">123</div> 复制代码
在 vue 中就会有个 vnode
对象与之对应,我们列举了其中几个关键属性
{ elm: el, // 对应真实的DOM节点 tag: 'div', key: 1, text: '123', children: [] } 复制代码
vnode
的 children
数组中对应子节点的 vnode
对象,所以在 vue 中通过 vnode
和真实的 DOM 树进行映射,我们也称之为虚拟树
。
正是有了虚拟树,当数据更新时。我们可以对比新数据构建的 vnode
和老数据构建的 oldVnode
的差异,来实现外科手术式的精准更新。
而我们对比差异的算法就是采用的 diff。通过 diff 对比虚拟树的差异,将差异通过打补丁(patch)的方式更新到对应的真实 DOM 节点上。
patch函数
patch函数是 diff 流程的入口函数
其接收两个入参,分别是虚拟节点 vnode
和 oldVnode
,对虚拟节点进行 diff 分析
function patch (oldVnode, vnode) { // some code if (sameVnode(oldVnode, vnode)) { // patch existing root node patchVnode(oldVnode, vnode) } else { // replacing existing element const oldElm = oldVnode.elm const parentElm = nodeOps.parentNode(oldElm) // create new node createElm( vnode, null, parentElm, nodeOps.nextSibling(oldElm) ) // destroy old node if (isDef(parentElm)) { removeVnodes([oldVnode], 0, 0) } } return vnode.elm } 复制代码
patch函数的逻辑比较简单
- 判断节点是否可以复用,可以复用则对节点打补丁
- 节点不可复用,创建新的节点插入到旧节点之前,同时删除旧节点
可以看出来,如果节点不可复用,直接创建新节点替换,旧的子节点也将不再考虑复用。这就是对应了 diff 的假设,Web UI 中 DOM 节点跨层级的移动操作特别少,可以忽略不计
我们再来看看 sameVnode 函数是如何判断可复用性的
function sameVnode (a, b) { return ( a.key === b.key && ( ( a.tag === b.tag && a.isComment === b.isComment && isDef(a.data) === isDef(b.data) && sameInputType(a, b) ) || ( isTrue(a.isAsyncPlaceholder) && a.asyncFactory === b.asyncFactory && isUndef(b.asyncFactory.error) ) ) ) } 复制代码
这段 vue 的完整源码涉及的变量比较多,我们只需要了解大致是通过 tag
key
inputType
来判断的就行。也就是说,当 tag
key
inputType
完全相同时,我们认定节点可复用。
patchVnode函数
接下来,再看看是如何对可复用节点进行打补丁的
function patchVnode(oldVnode, vnode) { // some code if (oldVnode === vnode) { return; } const elm = (vnode.elm = oldVnode.elm); const oldCh = oldVnode.children; const ch = vnode.children; // 非文本节点 if (isUndef(vnode.text)) { // 新旧节点都有子节点 if (isDef(oldCh) && isDef(ch)) { // 子节点的同层比较 if (oldCh !== ch) updateChildren(elm, oldCh, ch); } else if (isDef(ch)) { // 仅新元素有子节点 if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ""); addVnodes(elm, null, ch, 0, ch.length - 1, null); // 仅旧元素有子节点 } else if (isDef(oldCh)) { removeVnodes(oldCh, 0, oldCh.length - 1); } else if (isDef(oldVnode.text)) { // 清空文本 nodeOps.setTextContent(elm, ""); } // 文本节点,更新文本即可 } else if (oldVnode.text !== vnode.text) { nodeOps.setTextContent(elm, vnode.text); } } 复制代码
patchVnode函数的逻辑也不复杂,一起来分析分析
- 找到对应的 dom 节点 elm,并且赋值给 vnode.elm
- 判断新节点类型(vnode.text),如果是文本节点,更新 elm 文本即可
- 非文本节点下,判断新老节点的子节点
- 如果新老节点都有子节点,走子节点的同层比较流程 updateChildren
- 如果只有新节点有子节点,直接使用 addVnodes 为 elm 添加子节点(先删除文本)
- 如果只有旧节点有子节点,使用 removeVnodes 移除即可
- 如果都没有子节点,判断旧数据是否有文本节点,有则清空
这是一个很简单的通过数据(vnode oldVnode)来为真实节点 elm 打补丁更新节点的过程,addVnodes 和 removeVnodes 啥的就是直接操作 elm 节点更新了。
值得注意的是,这边涉及了子节点的同层比较 updateChildren,我们来看看它是如何工作的,也就是说如何从父节点进一步流转到子节点对比的。
updateChildren
子节点的对比流程就稍微复杂一点了,因为涉及如何判断是否存在同层可复用节点,是根据 key 属性来判定呢?还是通过其它顺序呢?
function updateChildren(parentElm, oldCh, newCh) { let oldStartIdx = 0; let newStartIdx = 0; let oldEndIdx = oldCh.length - 1; let oldStartVnode = oldCh[0]; let oldEndVnode = oldCh[oldEndIdx]; let newEndIdx = newCh.length - 1; let newStartVnode = newCh[0]; let newEndVnode = newCh[newEndIdx]; let oldKeyToIdx, idxInOld, vnodeToMove, refElm; while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (isUndef(oldStartVnode)) { oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left } else if (isUndef(oldEndVnode)) { oldEndVnode = oldCh[--oldEndIdx]; } else if (sameVnode(oldStartVnode, newStartVnode)) { patchVnode(oldStartVnode, newStartVnode); oldStartVnode = oldCh[++oldStartIdx]; newStartVnode = newCh[++newStartIdx]; } else if (sameVnode(oldEndVnode, newEndVnode)) { patchVnode(oldEndVnode, newEndVnode); oldEndVnode = oldCh[--oldEndIdx]; newEndVnode = newCh[--newEndIdx]; } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right patchVnode(oldStartVnode, newEndVnode); nodeOps.insertBefore( parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm) ); oldStartVnode = oldCh[++oldStartIdx]; newEndVnode = newCh[--newEndIdx]; } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left patchVnode(oldEndVnode, newStartVnode); nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm); oldEndVnode = oldCh[--oldEndIdx]; newStartVnode = newCh[++newStartIdx]; } else { if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx); if (isUndef(idxInOld)) { // New element createElm( newStartVnode, null, parentElm, oldStartVnode.elm ); } else { vnodeToMove = oldCh[idxInOld]; if (sameVnode(vnodeToMove, newStartVnode)) { patchVnode(vnodeToMove, newStartVnode); oldCh[idxInOld] = undefined; nodeOps.insertBefore( parentElm, vnodeToMove.elm, oldStartVnode.elm ); } else { // same key but different element. treat as new element createElm(newStartVnode, insertedVnodeQueue, parentElm); } } newStartVnode = newCh[++newStartIdx]; } } if (oldStartIdx > oldEndIdx) { refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm; addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx); } else if (newStartIdx > newEndIdx) { removeVnodes(oldCh, oldStartIdx, oldEndIdx); } } 复制代码
咋一看,代码还挺长的嘞,但其实就是有多个 IF-ELSEIF 的分类流程而已,相信我,代码看似冗长却依然简单
建议分析前像我一样先画个图,因为代码前部分的变量真的有点多
首先我们把 startIdx endIdx 称为左指针,右指针,相应的 startVnode,endVnode 我们称其为左节点,右节点,变量一下子就清晰了好多有木有
好了,开始分析逻辑了
- 当左指针小于等于右指针循环遍历(说明上下区间都有节点)
- 判断老节点边界为null的情况,向内移动指针
- 判断左节点是否可以复用,可以则为节点打补丁(递归调用 patchVnode,下同),向右移动指针
- 否则,判断右节点是否可以复用,可以则为节点打补丁,向左移动指针
- 否则,判断新右节点和旧左节点是否可以复用,可以则为节点打补丁,同时将旧左节点移动旧右节点前面,再向内移动指针(移动的过程会淘汰旧的右节点)
- 同理,判断新左节点和旧右节点,进行类似操作
- 当上面的几种情况都无法复用的话,接下来使用 key 来判断是否可以复用(判断新左节点)
首先,通过 createKeyToOldIdx 函数来得到旧节点索引和 key 属性的映射,数据结构为
{ keyIdx: oldChIdx } 复制代码
再赋值 idxInOld 变量为新左节点的 key 对应的旧节点索引
idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx); 复制代码
一起看看当新节点没有 key 的时候,findIdxInOld 函数的逻辑,返回第一个可以复用的旧节点
function findIdxInOld (node, oldCh, start, end) { for (let i = start; i < end; i++) { const c = oldCh[i] // 返回第一个可以复用的旧节点(旧节点的key也一定会是null) if (isDef(c) && sameVnode(node, c)) return i } } 复制代码
如果未找到 key 可复用的节点索引,则创建新的节点,移动到旧左节点(oldStartVnode.elm)之前
if (isUndef(idxInOld)) { // New element createElm( newStartVnode, null, parentElm, oldStartVnode.elm ); } 复制代码
如果找到 key 对应的旧节点,还要通过 sameVnode 再判断是否真正可复用,不可复用则还是创建新节点。确认 key 对应的旧节点可复用,为旧节点打补丁,旧节点数组元素设置为 null(这也是第一步要判断是否为 null 的原因),同时将旧节点移动到旧左节点(oldStartVnode.elm)之前
vnodeToMove = oldCh[idxInOld]; if (sameVnode(vnodeToMove, newStartVnode)) { patchVnode(vnodeToMove, newStartVnode); oldCh[idxInOld] = undefined; nodeOps.insertBefore( parentElm, vnodeToMove.elm, oldStartVnode.elm ); } else { // same key but different element. treat as new element createElm(newStartVnode, insertedVnodeQueue, parentElm); } 复制代码
最后完成本步逻辑,向内移动指针
newStartVnode = newCh[++newStartIdx]; 复制代码
- 执行完上边遍历程序之后,跳出循环
- 如果旧节点已经遍历完,则批量向后添加剩余新节点
if (oldStartIdx > oldEndIdx) { refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm; addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx); } 复制代码
- 如果新节点已经遍历完,则批量删除剩余旧节点
if (newStartIdx > newEndIdx) { removeVnodes(oldCh, oldStartIdx, oldEndIdx); } 复制代码
至此,updateChildren 的逻辑也就讲完了,其中的难点在于分类判断的情况比较多,而其精髓在于指针(索引)的移动。
温馨提示:insertBefore 方法是可以移动节点的,它会删除原节点,大家可以看看MDN的说明
举个例子
下面我们举个栗子看看
我们假定所有节点都有对应的 key 属性(值和字母对应)
- 对比左节点 A === A 可复用,向右移动指针
- 对比节点 B === B 可复用,将 B 移动 D 之前,向内移动指针
- C 找不到复用节点,在 D 之前创建新节点,同时移动指针
- 不满足循环条件,跳出循环
- 根据 oldStartIdx oldEndIdx 删除旧节点 D F G
总结
Diff 的原理其实比较简单,就是同层比较复用性。但是如何比较同层节点复用性的逻辑上还是比较繁多的,需要我们化繁为简,自然就能看懂。上面的分析可能会有错误的地方,欢迎大家指出。大家新年快乐!