引言

<<往期回顾>>

1. vue3源码分析——实现组件通信provide,inject
2. vue3源码分析——实现createRenderer，增加runtime-test
3. vue3源码分析——实现element属性更新，child更新

本期来实现，上一期中还差了children与children的对比😉😉😉 vue3更新流程中的children与children的对比，也就是diff算法，所有的源码请查看

正文

在children于children的对比中，vue3采用的是双端对比的方式，使用3个指针来进行移动对比，那肯定就会有许多的情况，且听我慢慢道来👍👍👍！

先看个结果

通过上面的测试用例，可以看到是分了7种情况来的，在本篇文章，不采用编写测试用例，有兴趣的可以自己去github上面查看，这里主要使用图文加上代码，帮助大家更快的理解vue3中的diff算法

锁定对比的范围

既然采用的是双端对比，那么肯定是需要3个指针的，请看下图：

总共有3个指针

• i 代表的是起始指针默认是 0
• e1 代表的是old children的末尾指针， 默认是 oldChildren.length -1
• e2 代表的是new children的末尾指针， 默认是 newChildren.length -1

既然有了指针，那是否需要锁定范围呢！指针做对应的移动。移动的方式如下：

• 如果oldChildren和newChildren左边的节点都一样，那么就需要i往右边移动，直到不同位置停止.
• 如果oldChildren和newChildren右边的节点都一样，那么对应的e1和e2往左边移动，同样也是到不同位置停止。

根据上面的需求，我相信都能得出一个条件并且写出以下代码

export function patchKeyedChildren(oldChildren, newChildren){
    let i = 0;
    let e1 = oldChildren.length - 1;
    let e2 = newChildren.length - 1;
    
    // 当 i <= e1 && i<= e2的时候，需要左边移动
    while(i <= e1 && i <= e2){
      if(oldChildren[i] 等于 newChildren[i]){
        i++
      }else{
        break;
      }
    }
    
    // 同理，右边的指针往左边移动也是这样
      while(i <= e1 && i <= e2){
      if(oldChildren[e1] 等于 newChildren[e2]){
        el--;
        e2--;
      }else{
        break;
      }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

上面的代码是伪代码，主要是用于说明情况，双端对比，拿到不相同的部分，接下来根据不相同的部分来进行分情况讨论

分情况讨论

总共有7中情况，分别是：

1. 老的比新的左边长，在新的左边创删除的节点
2. 老的比新的右边长，在新的右边创删除的节点
3. 老的比新大左边短,在新的左边创建新的节点
4. 老的比新的右边短，在新的右边创建新的节点
5. 老的比新的中间节点多,删除多余的节点
6. 老的新的中间节点一样多，位置发生变化，需要移动位置
7. 老的新的中间节点少，创建新的节点

老的左右边长

这里包含了老的左边长和右边长，都是需要删除对应边界的节点

老节点左边长

会发现，i不动， e1和 e2两个指针往左边移动

最终 i = 0, e1 = 1, e2 = -1,所以可以得出一个条件是 i > e2 && i <= e1

老节点右边长

可以发现，e1,e2不动，i往右边移动 最终 i = 3, e1 = 3, e2 = 2,所以可以得出一个条件是 i > e2 && i <= e1

老的比新的两边长，就是说只要满足 i > e2 && i <= e1这个条件，那就需要执行删除操作

export function patchKeyedChildren(oldChildren, newChildren){
// ……省略上面的指针移动代码
  if (i >= e2 && i <= e1) {
     // 为啥需要while呢，因为可能两边出现多个多余的节点，需要循环删除
      while (i <= e1) {
       // 删除当前节点
        hostRemove(n1[i].el)
        i++
      }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

老的左右边短

这里包含了，老节点的左边和右边比新的节点是更短的，需要创建新的节点

老的比新的左边短

i不动，e1，e2往左边移动

最终 i = 0, e1 = -1, e2 = 0,所以可以得出一个条件是 i > e1 && i <= e2

老的比新的右边短

e1,e2不动，i往右边移动

最终 i = 3, e1 = 2, e2 = 3,所以可以得出一个条件是 i > e1 && i <= e2

老的比新的两边短，就是说只要满足 i > e1 && i <= e2这个条件，那就需要执行新增节点的操作

export function patchKeyedChildren(oldChildren, newChildren){
// ……省略上面的代码
else  if (i > e1 && i <= e2) {
      //     a b   i = 0 e1 = -1 e2 = 0
      // d c a b  需要找到a的位置
      const nextPos = e2 + 1;
      const anchor = nextPos < l2 ? n2[nextPos].el : null
     // 同理，需要循环增加节点
      while (i <= e2) {
       // 插入节点
       patch(null, n2[i], container, parentComponent, anchor)
        i++
      }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

看到这里，恭喜你👍👍👍，vue3 diff的双端对比就已经结束了，接下来锁定了一个中间范围，来判断中间范围的内容，删除，移动位置，新增

中间节点老的比新的多

通过上面代码的执行，最终 i = 2, e1 =2， e2 = 2，但是这个不可以作为条件哦！思路需要转个弯🦮🦮🦮

通过i 和 e1可以锁定，老节点中间部分，i 和 e2可以锁定新节点的范围; 遍历老的节点,判断老的节点在新节点中是否存在,可以使用双重for循环,但是比较费时间,可以把新节点的内容给缓存起来,那么可以通过空间来换取时间

export function patchKeyedChildren(oldChildren, newChildren){
// ……省略上面的代码
else{
    // 中间对比
      const s1 = i;
      const s2 = i;
      // a b c d   i = 2 e1 = 2 e2 = 1
      // a b d
      // 条件  删除c

      // 判断旧节点是否在新节点里面，在的话保留，不在则删除
      const newIndexToOldIndexMap = new Map()
        // 把新节点的key装入map
      for (let j = s2; j <= e2; j++) {
        newIndexToOldIndexMap.set(newChildren[j].key, j)
      }
      // 然后遍历老的节点,判断是否在新的节点里面
       for (let i = s1; i <= e1; i++) {
        let newIndex;
        if (n1[i].key !== null) {
          newIndex = newIndexToOldIndexMap.get(n1[i].key)
        } else {
          // key 不存在，需要遍历新节点，看能不能找到这个节点
          for (let j = s2; j <= e2; j++) {
            if (isSameVNode(oldChildren[i], newChildren[j])) {
              newIndex = j
              break;
            }
          }
        }
        if (newIndex === undefined) {
          // 删除节点
          hostRemove(n1[i].el)
       }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

通过上面可以发现,如果在中间对比的时候不写key,将会再来一次for循环,那就比较费性能了!!!

中间对比,节点都存在,需要移动节点

通过上面代码的执行，最终 i = 2, e1 =4， e2 = 4， 在上面的图中,会发现新老节点中只有E的节点移动了,其他的节点都不动,那么怎么找出 [C,D,E]和[E,C,D]中的最长连续的节点呢?

遇到这个,肯定需要使用 最长递增子序列的算法啦,通过这个可以得出最长节点的连续范围.

但是最长递增子序列中需要一个数组,这个数组需要记录老节点与新节点的位置关系

\

通过上图,可以看到,先定义一个数组,长度是对比之后的长度,然后默认赋值为0,然后遍历老节点,用老节点的i来表示数组的结果,newIndex表示数据的下标,这样就能展示出新老节点的映射关系了

接下来实现一下这部分的功能,由于这一部分的内容与整体有关,我把整个diff的逻辑都放出来,全部已经写好注释了😉😉😉

 function patchKeyChildren(n1, n2, container, parentComponent, anchor) {

    // 采用双端对比法
    const l2 = n2.length
    const l1 = n1.length
    let i = 0;
    let e1 = l1 - 1;
    let e2 = l2 - 1;

    const isSameVNode = (vnode1, vnode2) => {
      return vnode1.type === vnode2.type && vnode1.key === vnode2.key
    }

    // 获取左侧的位置
    while (i <= e1 && i <= e2) {
      if (isSameVNode(n1[i], n2[i])) {
        // 对比对应的子节点
        patch(n1[i], n2[i], container, parentComponent, anchor)
      } else {
        break;
      }
      i++
    }
    // 获取右侧是位置
    while (i <= e1 && i <= e2) {
      if (isSameVNode(n1[e1], n2[e2])) {
        patch(n1[e1], n2[e2], container, parentComponent, anchor)
      } else {
        break;
      }
      e1--;
      e2--;
    }

    // 新的比老的短，删除老的
    if (i >= e2 && i <= e1) {
      while (i <= e1) {
        hostRemove(n1[i].el)
        i++
      }
    }

    // 新的比老的长，挂载新的
    else if (i > e1 && i <= e2) {
      // 往左侧添加 
      //    a b   i = 0 e1 = -1 e2 = 0
      // d c a b  需要找到a的位置
      const nextPos = e2 + 1;
      const anchor = nextPos < l2 ? n2[nextPos].el : null
      while (i <= e2) {
        patch(null, n2[i], container, parentComponent, anchor)
        i++
      }
    }
    else {
      // 中间对比
      const s1 = i;
      const s2 = i;
      // a b c d   i = 2 e1 = 2 e2 = 1
      // a b d
      // 条件  删除c

      // 判断旧节点是否在新节点里面，在的话保留，不在则删除
      const newIndexToOldIndexMap = new Map()
      // 增加一个优化点,如果旧节点的数量和新节点的数量已经一致，那么其余旧节点直接删除
      const toBePatched = e2 - s1 + 1;
      let patched = 0;

      // 将老节点和新节点做映射 b c d --> c d b
      const oldIndexToNewIndexMap = new Array(toBePatched).fill(0)
      // 判断是否需要移动节点，不需要移动则不需要调用获取最长递增子序列
      let moved = false;
      let maxIndexSoFar = 0;

      // 把新节点的key装入map
      for (let j = s2; j <= e2; j++) {
        newIndexToOldIndexMap.set(n2[j].key, j)
      }

      for (let i = s1; i <= e1; i++) {
        // 新节点已经满足前面对比的老节点，需要删除其余的老节点
        if (patched >= toBePatched) {
          hostRemove(n1[i].el)
          continue;
        }
        let newIndex;
        if (n1[i].key !== null) {
          newIndex = newIndexToOldIndexMap.get(n1[i].key)
        } else {
          // key 不存在，需要遍历新节点，看能不能找到这个节点
          for (let j = s2; j <= e2; j++) {
            if (isSameVNode(n1[i], n2[j])) {
              newIndex = j
              break;
            }
          }
        }
        if (newIndex === undefined) {
          // 删除节点
          hostRemove(n1[i].el)
        } else {
          // 更新映射关系
          oldIndexToNewIndexMap[newIndex - s1] = i + 1
          // 判断是否需要移动节点
          if (newIndex > maxIndexSoFar) {
            maxIndexSoFar = newIndex;
          } else {
            moved = true
          }
          // 存在的话，进行下一次的patch
          patch(n1[i], n2[newIndex], container, parentComponent, anchor)
          patched++
        }
      }

      // 获取最长递增序列  获取的是最长递增子序列的索引下标数组
      const longestIncreasingSubsequence = moved ? getLongestIncreasingSubsequence(oldIndexToNewIndexMap) : []
      // 遍历，判断当前的下标是否存在于最长递增序列中，存在则不需要移动，不存在需要移动

      // 使用游标j
      let j = longestIncreasingSubsequence.length - 1;
      for (let i = toBePatched - 1; i >= 0; i--) {
        // 计算下一个节点
        const curIndex = i + s2;
        const anchor = curIndex + 1 < l2 ? n2[curIndex + 1].el : null;
        if (oldIndexToNewIndexMap[i] === 0) {
          // 新增节点
          patch(null, n2[i + s2], container, parentComponent, anchor)
        }
        else if (moved) {
          if (j < 0 || i !== longestIncreasingSubsequence[j]) {

            // 移动节点
            hostInsert(n2[curIndex].el, container, anchor)
          } else {
            // 命中目标节点，不需要移动
            j--;
          }
        }
      }
    }
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

中间节点新增

对于这个功能,如果看懂了上面代码的话,是非常简单的,只需要判断oldIndexToNewIndexMap[i]是否为0,为0则代表,老节点中没有,新节点有,需要新增节点哦!

总结

本期主要实现了vue3的diff算法,主要分为7个部分:

1. 老的比新的左边长，在新的左边创删除的节点
2. 老的比新的右边长，在新的右边创删除的节点
3. 老的比新大左边短,在新的左边创建新的节点
4. 老的比新的右边短，在新的右边创建新的节点
5. 老的比新的中间节点多,删除多余的节点
6. 老的新的中间节点一样多，位置发生变化，需要移动位置
7. 老的新的中间节点少，创建新的节点

只有在中间节点一样多的时候,才会使用最长递增子序列,来判断哪些是需要移动的,只能说vue3的设计太厉害和灵活了,加油!!!