快人一步掌握vue源码解读,搞定diff算法!(超详细)

云加社区 2021-09-15 18:25


导语 | 最近碰到部分业务场景,代码逻辑需要了解“数组变更后,具体变更了哪一些元素,以及变更的位置…”。于是仔细研究并覆写了一遍针对数组变化的diff算法,在这里做下diff算法的逻辑分享&&源码解读。



一、介绍前的准备工作


我们先了解diff方法的运行规则和前提方法。


(一)虚拟node进行深度优先&&同级对比


深度优先:



同级对比:


如上图所示:


每次vnode都是执行同级对比(对应dom同一个父元素)


代码逻辑如下图:



(二)简单判断

`sameVnode`函数用来进行判断是否是同一个vnode元素。


源代码:



如图所示:


这里有两个重要元素:


  1. `key` : 开发者定义的:“key”;

  2. `sel `: 元素tagName+元素id+元素class。


sel的定义源码如下:



vNode构建函数:



(三)构建索引



逻辑如图:




二、如何处理元素


尽量不新增/删除dom,如下图所示:



如果是相同vnode,源码如下:




三、开始比较


首先会进行时间复杂度O(n)的while循环,循环条件为“遍历旧节点数组&&遍历新节点数组,谁先遍历完循环就结束”。


源码如下图:



在每次的循环过程中,会有两大类判断方法:


  • 首尾比较&&首尾序号



逻辑:如图上所示,首先在循环遍历前标记好新,旧节点数组的开始位置和结束位置的序:oldStartIdx、oldEndIdx、newStartIdx、newEndIdx;其次在循环遍历的过程中采用“首首比较,尾尾比较,首尾比较”。


源码如下:



如果数据为图上所示,那么根据首尾比较方法会有如下图所示结果,最终全部执行了更新操作:



  • 索引比较--最坏情况,这里的时间复杂度也是O(n),即整个算法复杂度O(n)+O(n)


每次遍历的过程中可能存在“新数组节点新增/旧数组节点删除”,那么前后对比就满足不了条件。这里逻辑会进入索引比较;


比如这种情况:



那么,循环中会执行一遍创建旧数组的索引对象。


那么从创建到比较的整个逻辑图如下:


这里的源码如下:



  • 当旧节点不存在新增的节点时,进行当前oldStartIdx位置的添加:


源码如下:



  • 当旧数组存在节点,那么进行位置移动:



源码:



  • 当节点遍历完之后


会存在两种情况,“新数组已经遍历完,但旧数组没有遍历完成” 和 “旧数组遍历完成,但新数组没有遍历完成”。


故源代码的判断如下:



  • 旧数组没有循环完成:


效果如下图所示:


这里注意一个点,我们每次的节点更新会移动序号,即使被删除的节点不在一块最终也会被首尾比较算法 “摞在一块”,(oldStartIdx~oldEndIdx)。上图所示更加明显一些。

源码在这里就进行批量删除:



  • 新数组没有循环完成:


效果如下图所示:

经过前后对比&&索引的过滤后,只会存在新末尾节点!==旧节点及之前的连续的新节点(!==旧节点);所以这里也“摞在一块”,即(newStartIdx~newEndIdx)。


源码如下:



这样,整个diff的对比算法就已经走完了。所以核心就是:前后对比+索引



四、关键点


关键点大概如下:




五、vue3.0对于diff比较前的优化


vue3.0针对“无脑”patchVnode进行了过滤--静态类型Vnode:


老版的源码:



这里,我们再重复下vue2.x系列的对比更新逻辑:



新版的vue3.0增加了静态类型Vnode,如果是静态类型的vnode 那么直接跳过更新,修改新节点引用即可:



备注:comment类型目前翻到它的源码也只是更改引用,源码作者加上了一行注释。



这里再加一句,flagment碎片类型为新增的vnode类型, 即:



vue3.0的过滤判断源码如下:




六、数组比较的应用


由于想监听数组的变化,故参考了diff算法覆写类似的逻辑。用来在update,add,dels时代码层面获取操作的具体节点明细(新旧节点的位置,内容)。


git地址:http://git.code.oa.com/winkchen/diffArr.git


同时tnpm包tnpmi@tencent/arraydiff


tnpm地址:

http://mirrors.tencent.com/#/private/npm/detail?repo_id=537&project_name=%40tencent%2Farraydiff



 作者简介


陈碧松(winkchen)

腾讯web前端开发工程师

腾讯web前端开发工程师。目前负责腾讯IEG智慧发行的前端开发工作,有丰富的游戏内活动开发,游戏内视频直播开发经验。



 推荐阅读


事务消息大揭秘!RocketMQ、Kafka、Pulsar全方位对比

Linux入门必看:如何在60秒内分析Linux性能?

“Docker VS Kubernetes”是共生还是相爱相杀?

揭秘!是什么能让APP快速精准定位?





推荐阅读