本文通过对virtual-dom的源码进行阅读和分析,针对Virtual DOM的结构和相关的Diff算法进行讲解,让读者能够对整个数据结构以及相关的Diff算法有一定的了解。
Virtual DOM中Diff算法得到的结果如何映射到真实DOM中,我们将在下一篇博客揭晓。
本文的主要内容为:
注:这个Virtual DOM的实现并不是React Virtual DOM的源码,而是基于virtual-dom)这个库。两者在原理上类似,并且这个库更加简单容易理解。相较于这个库,React对Virtual DOM做了进一步的优化和调整,我会在后续的博客中进行分析。
作为Virtual DOM的元数据结构,VirtualNode位于vnode/vnode.js
文件中。我们截取一部分声明代码来看下内部结构:
上面就是一个VirtualNode的完整结构,包含了特定的标签名、属性、子节点等。
VText是一个纯文本的节点,对应的是HTML中的纯文本。因此,这个属性也只有text
这一个字段。
VPatch是表示需要对Virtual DOM执行的操作记录的数据结构。它位于vnode/vpatch.js
文件中。我们来看下里面的具体代码:
其中常量定义了对VNode节点的操作。例如:VTEXT就是增加一个VText节点,PROPS就是当前节点有Props属性改变。
了解了虚拟DOM中的三个结构,那我们下面来看下Virtual DOM的Diff算法。
这个Diff算法是Virtual DOM中最核心的一个算法。通过输入初始状态A(VNode)和最终状态B(VNode),这个算法可以得到从A到B的变化步骤(VPatch),根据得到的这一连串步骤,我们就可以知道哪些节点需要新增,哪些节点需要删除,哪些节点的属性有了变化。在这个Diff算法中,又分成了三部分:
下面,我们就来一个一个介绍这些Diff算法。
该算法是针对于单个VNode的比较算法。它是用于两个树中单个节点比较的场景。具体算法如下,如果不想直接阅读源码的同学也可以翻到下面,会有相关代码流程说明供大家参考:
代码具体逻辑如下:
a
和b
这两个VNode全等,则认为没有修改,直接返回。thunks
。a
是widget且b
为空,那么通过递归将a
和它的子节点的remove
操作添加到patch中。b
是VNode的话,
a
也是VNode,那么比较tagName
、namespace
、key
,如果相同则比较两个VNode的Props(用下面提到的diffProps算法),同时比较两个VNode的children(用下面提到的diffChildren算法);如果不同则直接将b
节点的insert
操作添加到patch中,同时将标记位置为true。a
不是VNode,那么直接将b
节点的insert
操作添加到patch中,同时将标记位置为true。b
是VText的话,看a
的类型是否为VText,如果不是,则将VText
操作添加到patch中,并且将标志位设置为true;如果是且文本内容不同,则将VText
操作添加到patch中。b
是Widget的话,看a
的类型是否为widget,如果是,将标志位设置为true。不论a
类型为什么,都将Widget
操作添加到patch中。a
和它的子节点的remove
操作添加到patch中。这就是单个VNode节点的diff算法全过程。这个算法是整个diff算法的入口,两棵树的比较就是从这个算法开始的。
看完了单个VNode节点的diff算法,我们来看下上面提到的diffProps
算法。
该算法是针对于两个比较的VNode节点的Props比较算法。它是用于两个场景中key值和标签名都相同的情况。具体算法如下,如果不想直接阅读源码的同学也可以翻到下面,会有相关代码流程说明供大家参考:
代码具体逻辑如下:
a
对象。
b
,则将此值存储下来,value赋值为undefined
。b
对象的值;如果b
对应的value是hook
的话,记录b的值。b
对应的value进行记录。b
对象,将所有a
对象中不存在的key值对应的对象都记录下来。整个算法的大致流程如下,因为比较简单,就不画相关流程图了。如果逻辑有些绕的话,可以配合代码食用,效果更佳。
下面让我们来看下最后一个算法,就是关于两个VNode节点的children属性的diffChildren
算法。这个个diff算法分为两个部分,第一部分是将变化后的结果b
的children进行顺序调整的算法,保证能够快速的和a
的children进行比较;第二部分就是将a
的children与重新排序调整后的b
的children进行比较,得到相关的patch。下面,让我们一个一个算法来看。
该算法的作用是将b
节点的children数组进行调整重新排序,让a
和b
两个children之间的diff算法更加节约时间。具体代码如下:
下面,我们来简单介绍下这个排序算法:
a
和b
中的children是否拥有key字段,如果没有,直接返回b
的children数组。a
的children元素。
move
操作patch(即remove
+insert
)。move
操作列表。通过上面这个排序算法,我们可以得到一个新的b
的children数组。在使用这个数组来进行比较厚,我们可以将两个children数组之间比较的时间复杂度从o(n^2)转换成o(n)。具体的方法和效果我们可以看下面的DiffChildren算法。
通过上面的重新排序算法整理了以后,两个children比较就只需在相同下标的情况下比较了,即aChildren的第N个元素和bChildren的第N个元素进行比较。然后较长的那个元素做insert
操作(bChildren)或者remove
操作(aChildren)即可。最后,我们将move操作再增加到patch中,就能够抵消我们在reorder时对整个数组的操作。这样只需要一次便利就得到了最终的patch值。
整个Virtual DOM的diff算法设计的非常精巧,通过三个不同的分部算法来实现了VNode、Props和Children的diff算法,将整个Virtual DOM的的diff操作分成了三类。同时三个算法又互相递归调用,对两个Virtual DOM数做了一次(伪)深度优先的递归比较。
下面一片博客,我会介绍如何将得到的VPatch操作应用到真实的DOM中,从而导致HTML树的变化。