VUE源码学习第十二篇-patch(diff原理)

一时失言乱红尘 2022-01-13 01:09 280阅读 0赞

# 一、总述 #

前面章节介绍了响应式的原理，当监听的属性值发生变化，会触发其相关的订阅watcher对象更新。如果在模板中使用了该属性，则会触发render wacher的更新，最终实现dom的更新。dom更新的有两种实现方式，一种是"全量"的全局更新，一种是"增量"的局部更新，很显然，后一种的效率会更高。VUE就是采用的一种，会先对新旧的vdom进行比较，形成patch，从而实现dom的局部更新。

本章节主要介绍如何来比较vdom,即diff算法原理。

# 二、diff算法 #

vue是借鉴了react的diff算法，**比较只会在同级间进行，不会跨级比较**。下面这张图很形象的描述这种关系。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70][]

我们来看个dom实例

<div>
      <div> 
           <p>vue</p>
           <input type="text"></input>
      </div>
      <span>diff</span>
    </div>
    
    
    <div>
      <div> 
           <p>vue</p>
      </div>
      <span>diff</span>
      <input type="text"></input>
    </div>

最优的操作就是将第三层的input节点，直接移动到第二层，其他的节点保持不变。但在diff算法中，由于是同级比较，无法做到跨级移动，所以先比较第一层级元素(div)，再比较第二层级(div,span),然后再比较第三层级(p,input)，依次类推。具体的操作为，先在第二层增加input节点，然后在第三层删除该节点。

我们看下diff算法的原理，以下图为例，最终目标要将oldDom变换为newDom，以下是变换的方法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 1][]

1、在新老dom的首位和末位节点上，分别建立索引,如老dom的第一个节点索引标注为oldstart(简称os)，最后一个节点oldend(简称oe),新节点也按此标注。

2、新老两组节点间相互比较，可以看到最多需要比较4次。即os->ns,os->ne,oe->ns,oe->ne。

3、4次比较后，会产生5种结果。

(1)os==ns,即旧dom的开始节点，与新dom的开始节点相等，保持os节点位置不变，os,ns的索引向后移动一位。

(2)os==ne,即旧dom的开始节点，与新dom的结束节点相等，将os节点移动到oe的索引位置后面，os索引向后移动一位，ne索引向前移动一位。

(3)oe==ns,即旧dom的结束节点，与新dom的开始节点相等，将oe节点移动os的索引位置前，oe索引向前移动一位，ns索引向后移动一位。

(4)oe==ne，即旧dom的结束节点，与新dom的结束节点相等，保持oe节点的位置不变，oe，ne的索引向前移动一位。

(5)两组节点互不相等，在os与oe间，查找是否有与ns相同的节点，如果有，则移动到os节点位置前；如果没有，则创建ns节点，并插入到os节点位置前。ns索引向后移动一位。

4、以下两种条件，满足其一就结束比较

(1)oe>os,表示olddom先遍历完，就创建ns,ne间的节点，插入到dom中的ne前。。

(2)ne>ns，表示newdom先遍历完，说明os，oe间的节点是多余的，直接删除。

以上的过程的描述比较晦涩，下面我们用一个实例，按照图解的方式为大家逐步分解。

# 三、实例说明 #

olddom最终变换后成为newdom

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 2][]

**第一步：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 3][]

添加索引，开始比较，os==ns，a节点的位置不变，同时，os，ns索引向后移动一位。

**第二步：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 4][]

os==ne，将b节点移动到oe索引的后面，同时，os索引向后移动一位，ne索引向前移动一位。

**第三步：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 5][]

oe==ne，f节点位置保持不变，同时，oe，ne索引向前移动一位。

**第四步：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 6][]

oe==ns,e节点移动到os索引位置前，同时，ns向后移动一位，oe向前移动一位。

**第五步：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 7][]

此时，两组节点互不相等，同时k节点与os->oe间节点元素不相同(d，c)，创建k节点，并插入到os索引前。同时，ns索引向后移动一位。

**第六步：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 8][]

此时，ns与ne的索引位置是重合的，两组节点也是互不相等。g节点插入到ns的索引位置前，同时，ns索引向后移动一位。

**第七步：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 9][]

ne>ns,满足结束的条件，newdom先遍历完，os与oe之间的节点时多余，将移动掉。

最终由olddom变换成了newdom。

# 四、总结 #

本章节主要介绍diff算法的原理，下面将结合vue的源码，具体分析其实现过程。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70]: /images/20220112/0f3a92bc7818454fbb259f45a3dce70c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 1]: /images/20220112/2728cd003be24b089af5149749d4d695.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 2]: /images/20220112/bf31303e93f64374b187721dd902f4de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 3]: /images/20220112/de62e174ad9a4ede867eb2a8113c11e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 4]: /images/20220112/9058c586835247c6bc9dc5c5ed4cf2e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 5]: /images/20220112/cc50dbfa621a46f8987e5abf75e94d20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 6]: /images/20220112/2d8e20e063374f00a1fa628a9602df0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 7]: /images/20220112/7697fe6ce1ae4c379176176947e1f5d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 8]: /images/20220112/ef649f99f14441bca561b0208edb3fa5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 9]: /images/20220112/6d53e50d94404232830db846292dd72e.png