前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >如何实现一个虚拟 DOM——virtual-dom 源码分析

如何实现一个虚拟 DOM——virtual-dom 源码分析

作者头像
黄Java
发布2019-03-20 10:49:53
5990
发布2019-03-20 10:49:53
举报
文章被收录于专栏:黄Java的地盘黄Java的地盘

概述

本文通过对virtual-dom的源码进行阅读和分析,针对Virtual DOM的结构和相关的Diff算法进行讲解,让读者能够对整个数据结构以及相关的Diff算法有一定的了解。

Virtual DOM中Diff算法得到的结果如何映射到真实DOM中,我们将在下一篇博客揭晓。

本文的主要内容为:

  • Virtual DOM的结构
  • Virtual DOM的Diff算法

注:这个Virtual DOM的实现并不是React Virtual DOM的源码,而是基于virtual-dom)这个库。两者在原理上类似,并且这个库更加简单容易理解。相较于这个库,React对Virtual DOM做了进一步的优化和调整,我会在后续的博客中进行分析。

Virtual DOM的结构

VirtualNode

作为Virtual DOM的元数据结构,VirtualNode位于vnode/vnode.js文件中。我们截取一部分声明代码来看下内部结构:

上面就是一个VirtualNode的完整结构,包含了特定的标签名、属性、子节点等。

VText

VText是一个纯文本的节点,对应的是HTML中的纯文本。因此,这个属性也只有text这一个字段。

VPatch

VPatch是表示需要对Virtual DOM执行的操作记录的数据结构。它位于vnode/vpatch.js文件中。我们来看下里面的具体代码:

其中常量定义了对VNode节点的操作。例如:VTEXT就是增加一个VText节点,PROPS就是当前节点有Props属性改变。

Virtual DOM的Diff算法

了解了虚拟DOM中的三个结构,那我们下面来看下Virtual DOM的Diff算法。

这个Diff算法是Virtual DOM中最核心的一个算法。通过输入初始状态A(VNode)和最终状态B(VNode),这个算法可以得到从A到B的变化步骤(VPatch),根据得到的这一连串步骤,我们就可以知道哪些节点需要新增,哪些节点需要删除,哪些节点的属性有了变化。在这个Diff算法中,又分成了三部分:

  • VNode的Diff算法
  • Props的Diff算法
  • Vnode children的Diff算法

下面,我们就来一个一个介绍这些Diff算法。

VNode的Diff算法

该算法是针对于单个VNode的比较算法。它是用于两个树中单个节点比较的场景。具体算法如下,如果不想直接阅读源码的同学也可以翻到下面,会有相关代码流程说明供大家参考:

代码具体逻辑如下:

  1. 如果ab这两个VNode全等,则认为没有修改,直接返回。
  2. 如果其中有一个是thunk,则使用thunk的比较方法thunks
  3. 如果a是widget且b为空,那么通过递归将a和它的子节点的remove操作添加到patch中。
  4. 如果b是VNode的话,
    1. 如果a也是VNode,那么比较tagNamenamespacekey,如果相同则比较两个VNode的Props(用下面提到的diffProps算法),同时比较两个VNode的children(用下面提到的diffChildren算法);如果不同则直接将b节点的insert操作添加到patch中,同时将标记位置为true。
    2. 如果a不是VNode,那么直接将b节点的insert操作添加到patch中,同时将标记位置为true。
  5. 如果b是VText的话,看a的类型是否为VText,如果不是,则将VText操作添加到patch中,并且将标志位设置为true;如果是且文本内容不同,则将VText操作添加到patch中。
  6. 如果b是Widget的话,看a的类型是否为widget,如果是,将标志位设置为true。不论a类型为什么,都将Widget操作添加到patch中。
  7. 检查标志位,如果标识为为true,那么通过递归将a和它的子节点的remove操作添加到patch中。

这就是单个VNode节点的diff算法全过程。这个算法是整个diff算法的入口,两棵树的比较就是从这个算法开始的。

Prpps的Diff算法

看完了单个VNode节点的diff算法,我们来看下上面提到的diffProps算法。

该算法是针对于两个比较的VNode节点的Props比较算法。它是用于两个场景中key值和标签名都相同的情况。具体算法如下,如果不想直接阅读源码的同学也可以翻到下面,会有相关代码流程说明供大家参考:

代码具体逻辑如下:

  1. 遍历a对象。
    1. 当key值不存在于b,则将此值存储下来,value赋值为undefined
    2. 当此key对应的两个属性都相同时,继续终止此次循环,进行下次循环。
    3. 当key值对应的value不同且key值对应的两个value都是对象时,判断Prototype值,如果不同则记录key对应的b对象的值;如果b对应的value是hook的话,记录b的值。
    4. 上面条件判断都不同且都是对象时,则继续比较key值对应的两个对象(递归)。
    5. 当有一个不是对象时,直接将b对应的value进行记录。
  2. 遍历b对象,将所有a对象中不存在的key值对应的对象都记录下来。

整个算法的大致流程如下,因为比较简单,就不画相关流程图了。如果逻辑有些绕的话,可以配合代码食用,效果更佳。

Vnode children的Diff算法

下面让我们来看下最后一个算法,就是关于两个VNode节点的children属性的diffChildren算法。这个个diff算法分为两个部分,第一部分是将变化后的结果b的children进行顺序调整的算法,保证能够快速的和a的children进行比较;第二部分就是将a的children与重新排序调整后的b的children进行比较,得到相关的patch。下面,让我们一个一个算法来看。

reorder算法

该算法的作用是将b节点的children数组进行调整重新排序,让ab两个children之间的diff算法更加节约时间。具体代码如下:

下面,我们来简单介绍下这个排序算法:

  1. 检查ab中的children是否拥有key字段,如果没有,直接返回b的children数组。
  2. 如果存在,初始化一个数组newChildren,遍历a的children元素。
    1. 如果aChildren存在key值,则去bChildren中找对应key值,如果bChildren存在则放入新数组中,不存在则放入一个null值。
    2. 如果aChildren不存在key值,则从bChildren中不存在key值的第一个元素开始取,放入新数组中。
  3. 遍历bChildren,将所有achildren中没有的key值对应的value或者没有key,并且没有放入新数组的子节点放入新数组中。
  4. 将bChildren和新数组逐个比较,得到从新数组转换到bChildren数组的move操作patch(即remove+insert)。
  5. 返回新数组和move操作列表。

通过上面这个排序算法,我们可以得到一个新的b的children数组。在使用这个数组来进行比较厚,我们可以将两个children数组之间比较的时间复杂度从o(n^2)转换成o(n)。具体的方法和效果我们可以看下面的DiffChildren算法。

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树的变化。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 概述
  • Virtual DOM的结构
    • VirtualNode
      • VText
        • VPatch
        • Virtual DOM的Diff算法
          • VNode的Diff算法
            • Prpps的Diff算法
              • Vnode children的Diff算法
                • reorder算法
                  • DiffChildren算法
                  • 总结
                  领券
                  问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档