当前位置:首页 > 前端 > 正文内容

Vue的diff算法解析

放牧的风3个月前 (06-16)前端260

1. 前言


diff算法是一种通过同层的树节点进行比较的高效算法,避免了对树进行逐层搜索遍历,所以时间复杂度只有 O(n)。diff算法的在很多场景下都有应用,例如在 vue 虚拟 dom 渲染成真实 dom 的新旧 VNode 节点比较更新时,就用到了该算法。diff算法有两个比较显著的特点:

比较只会在同层级进行, 不会跨层级比较:

在diff比较的过程中,循环从两边向中间收拢:

2. diff流程

本着对 diff 过程的认识和 vue 源码的学习,我们通过 vue 源码的解读和实例分析来理清楚 diff 算法的整个流程,下面把整个 diff 流程拆成三步来具体分析:

第一步

vue 的虚拟 dom 渲染真实 dom 的过程中首先会对新老 VNode 的开始和结束位置进行标记:oldStartIdx、oldEndIdx、newStartIdx、newEndIdx。
let oldStartIdx = 0 // 旧节点开始下标
let newStartIdx = 0 // 新节点开始下标
let oldEndIdx = oldCh.length - 1 // 旧节点结束下标
let oldStartVnode = oldCh[0]  // 旧节点开始vnode
let oldEndVnode = oldCh[oldEndIdx] // 旧节点结束vnode
let newEndIdx = newCh.length - 1 // 新节点结束下标
let newStartVnode = newCh[0] // 新节点开始vnode
let newEndVnode = newCh[newEndIdx] // 新节点结束vnode

经过第一步之后,我们初始的新旧 VNode 节点如下图所示:

640 (2).png


第二步

标记好节点位置之后,就开始进入到的 while 循环处理中,这里是 diff 算法的核心流程,分情况进行了新老节点的比较并移动对应的 VNode 节点。while 循环的退出条件是直到老节点或者新节点的开始位置大于结束位置。


while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    ....//处理逻辑
}
接下来具体介绍 while 循环中的处理逻辑, 循环过程中首先对新老 VNode 节点的头尾进行比较,寻找相同节点,如果有相同节点满足 sameVnode(可以复用的相同节点) 则直接进行 patchVnode (该方法进行节点复用处理),并且根据具体情形,移动新老节点的 VNode 索引,以便进入下一次循环处理,一共有 2 * 2 = 4 种情形。下面根据代码展开分析:


情形一:当新老 VNode 节点的 start 满足sameVnode 时,直接 patchVnode 即可,同时新老 VNode 节点的开始索引都加1。


 if (sameVnode(oldStartVnode, newStartVnode)) {        
     patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)        
     oldStartVnode = oldCh[++oldStartIdx]        
     newStartVnode = newCh[++newStartIdx]     
 }

情形二:当新老 VNode 节点的 end 满足 sameVnode 时,同样直接 patchVnode 即可,同时新老 VNode 节点的结束索引都减1。

else if (sameVnode(oldEndVnode, newEndVnode)) {        
    patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)        
    oldEndVnode = oldCh[--oldEndIdx]        
    newEndVnode = newCh[--newEndIdx]      
}

情形三:当老 VNode 节点的 start 和新 VNode 节点的 end 满足 sameVnode 时,这说明这次数据更新后 oldStartVnode 已经跑到了 oldEndVnode 后面去了。这时候在 patchVnode 后,还需要将当前真实 dom 节点移动到 oldEndVnode 的后面,同时老 VNode 节点开始索引加1,新 VNode 节点的结束索引减1。

else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right        
    patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)        
    canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))        
    oldStartVnode = oldCh[++oldStartIdx]        
    newEndVnode = newCh[--newEndIdx]      
}

情形四:当老 VNode 节点的 end 和新 VNode 节点的 start 满足 sameVnode 时,这说明这次数据更新后 oldEndVnode 跑到了 oldStartVnode 的前面去了。这时候在 patchVnode 后,还需要将当前真实 dom 节点移动到 oldStartVnode 的前面,同时老 VNode 节点结束索引减1,新 VNode 节点的开始索引加1。

else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left        
    patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)        
    canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)        
    oldEndVnode = oldCh[--oldEndIdx]        
    newStartVnode = newCh[++newStartIdx]      
}

如果都不满足以上四种情形,那说明没有相同的节点可以复用。于是则通过查找事先建立好的以旧的 VNode 为 key 值,对应 index 序列为 value 值的哈希表。从这个哈希表中找到与 newStartVnode 一致 key 的旧的 VNode 节点,如果两者满足 sameVnode 的条件,在进行 patchVnode 的同时会将这个真实 dom 移动到 oldStartVnode 对应的真实 dom 的前面;如果没有找到,则说明当前索引下的新的 VNode 节点在旧的 VNode 队列中不存在,无法进行节点的复用,那么就只能调用 createElm 创建一个新的 dom 节点放到当前 newStartIdx 的位置。

else {// 没有找到相同的可以复用的节点,则新建节点处理        
    /* 
        生成一个key与旧VNode的key对应的哈希表(只有第一次进来undefined的时候会生成,也为后面检测重复的key值做铺垫) 
        比如childre是这样的 [{xx: xx, key: 'key0'}, {xx: xx, key: 'key1'}, {xx: xx, key: 'key2'}] beginIdx = 0 endIdx = 2 结果生成{key0: 0, key1: 1, key2: 2} 
    */        
    if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)        
    /*如果newStartVnode新的VNode节点存在key并且这个key在oldVnode中能找到则返回这个节点的idxInOld(即第几个节点,下标)*/        
    idxInOld = isDef(newStartVnode.key)          
    ? oldKeyToIdx[newStartVnode.key]          
    : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)        
    
    if (isUndef(idxInOld)) { // New element          
        /*newStartVnode没有key或者是该key没有在老节点中找到则创建一个新的节点*/          
        createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)        
    } else {          
        /*获取同key的老节点*/          
        vnodeToMove = oldCh[idxInOld]          
        if (sameVnode(vnodeToMove, newStartVnode)) {            
            /*如果新VNode与得到的有相同key的节点是同一个VNode则进行patchVnode*/            
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)            
            //因为已经patchVnode进去了,所以将这个老节点赋值undefined            
            oldCh[idxInOld] = undefined            
            /*当有标识位canMove实可以直接插入oldStartVnode对应的真实Dom节点前面*/            
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)          
        } else {            
            // same key but different element. treat as new element            
            /*当新的VNode与找到的同样key的VNode不是sameVNode的时候(比如说tag不一样或者是有不一样type的input标签),创建一个新的节点*/            
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)          
        }       
    }        
    newStartVnode = newCh[++newStartIdx]      
}

再来看我们的实例,第一次循环后,找到了旧节点的末尾和新节点的开头(都是D)相同,于是直接复用 D 节点作为 diff 后创建的第一个真实节点。同时旧节点的 endIndex 移动到了 C,新节点的 startIndex 移动到了 C。 

紧接着开始第二次循环,第二次循环后,同样是旧节点的末尾和新节点的开头(都是C)相同,同理,diff 后创建了 C 的真实节点插入到第一次创建的 B 节点后面。同时旧节点的 endIndex 移动到了 B,新节点的 startIndex 移动到了 E。 

接下来第三次循环中,发现 patchVnode 的4种情形都不符合,于是在旧节点队列中查找当前的新节点 E,结果发现没有找到,这时候只能直接创建新的真实节点 E,插入到第二次创建的 C 节点之后。同时新节点的 startIndex 移动到了 A。旧节点的 startIndex 和 endIndex 都保持不动。 

第四次循环中,发现了新旧节点的开头(都是A)相同,于是 diff 后创建了 A 的真实节点,插入到前一次创建的 E 节点后面。同时旧节点的 startIndex 移动到了B,新节点的startIndex 移动到了B。 

第五次循环中,情形同第四次循环一样,因此 diff 后创建了 B 真实节点 插入到前一次创建的 A 节点后面。同时旧节点的 startIndex 移动到了C,新节点的 startIndex 移动到了F。

这时候发现新节点的 startIndex 已经大于 endIndex 了。不再满足循环的条件了。因此结束循环,接下来走后面的逻辑。

第三步


当 while 循环结束后,根据新老节点的数目不同,做相应的节点添加或者删除。若新节点数目大于老节点则需要把多出来的节点创建出来加入到真实 dom 中,反之若老节点数目大于新节点则需要把多出来的老节点从真实 dom 中删除。至此整个 diff 过程就已经全部完成了。


if (oldStartIdx > oldEndIdx) {      
     /*全部比较完成以后,发现oldStartIdx > oldEndIdx的话,说明老节点已经遍历完了,新节点比老节点多, 所以这时候多出来的新节点需要一个一个创建出来加入到真实Dom中*/      
     refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm      
     addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue) //创建 newStartIdx - newEndIdx 之间的所有节点    
} else if (newStartIdx > newEndIdx) {      
     /*如果全部比较完成以后发现newStartIdx > newEndIdx,则说明新节点已经遍历完了,老节点多于新节点,这个时候需要将多余的老节点从真实Dom中移除*/      
     removeVnodes(oldCh, oldStartIdx, oldEndIdx) //移除 oldStartIdx - oldEndIdx 之间的所有节点    
}

再回过头看我们的实例,新节点的数目大于旧节点,需要创建 newStartIdx 和 newEndIdx 之间的所有节点。在我们的实例中就是节点 F,因此直接创建 F 节点对应的真实节点放到 B 节点后面即可。 

640 (4).png

结尾


最后通过上述的源码和实例的分析,我们完成了 Vue 中 diff 算法的完整解读。如果想要了解更多的 Vue 源码。欢迎进入我们的 github地址(https://github.com/DQFE/vue)进行查看,里面对每一行 Vue 源码都做了注释,方便大家的理解。


扫描二维码推送至手机访问。

版权声明:本文由放牧的风发布,如需转载请注明出处。

本文链接:https://grazingwind.com/post/70.html

标签: VUEdiff
分享给朋友:

相关文章

什么是BFC?看这一篇就够了

什么是BFC?看这一篇就够了

BFC 定义BFC(Block formatting context)直译为"块级格式化上下文"。它是一个独立的渲染区域,只有Block-level box参与, 它规定了内部的Block-level Box如何布局,并...

npm更新模块并同步到package.json中

使用原始npm1.查看需要更新的版本npm outdated该命令会列出所有需要更新的项目2.修改package.json中需要更新的包对应的版本号npm update由于npm update只能按照package.js...

经得住拷问的HTTPS原理解析

经得住拷问的HTTPS原理解析

此文涵盖的大致内容:理解HTTPS原理的概念什么是对称加密和非对称加密?什么是数字签名?怎么生成?怎么校验?啥时候是对称加密?啥时候是非对称加密?啥时候进行算法加密?什么算法?第三方机构包含哪些?HTTPS 是什么?具体流程HTTPS和HT...

用webstorm在chrome 调试页面时一直弹出 copy authorization url to clipboard

用webstorm在chrome 调试页面时一直弹出 copy authorization url to clipboard

用chrome来调试页面,每次刷新会弹出 requested without authorization,是因为更新后的bug,可以在Setting - debugger中设置 ...

三十分钟包会——正则表达式

三十分钟包会——正则表达式

一、前言正则表达式,对大家来说既熟悉又陌生。熟悉是因为工作中有很多场景能用到,比如手机号、邮箱、密码等规则校验。陌生则是因为正则表达式看上去就是一堆乱码,且一眼看上去很难看懂匹配规则。有时候在网上去找一个特定规则的正则表达式,搜出来的结果各...

ArcGIS API for JavaScript 4.4 版本加载谷歌地图

ArcGIS API for JavaScript 4.4 版本加载谷歌地图

ArcGIS API for JavaScript 4.X 版本升级后,API发生了很大的变化。其中就支持了WebEarth展示,主要是通过 esri/views/SceneView 实现的。在新版本中,默认都是加载Es...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。