Vue3中diff算法比对新老节点孩子数组

• 上一节说到当调用render函数时，可以重新渲染新节点，也可以更新新节点，更新操作中最复杂的就是要对比新老节点的各种差异，在对比过程中，新老节点的孩子节点都是数组，该如何比对呢？
• 对比新老孩子节点数组的目的，就是为了尽可能的复用之前的节点，这里就要分几种情况：
  • 从数组头部对比能够对比完
    • 如[a,b,c,d,e] - [a,b,c]
    • 只需要从头部挨个对比，就能全部对比完成
  • 从尾部对比能够对比完
    • 如[a,b,c,d,e] - [c,d,e]
    • 这里从后往前对比，可以对比完
  • 需要较乱，无法按顺序对比
    • 如[a,b,c,d,e] - [a,e,f,g,d]
• 先看 第一种情况，从头对比，每一个节点都相同，直到节点全部可以对比完成，说明所有的节点都可以复用，这里就需要做出判断，既然所有节点都可以比对完，那就看是新数组长度长还是旧数组长度长
  • 如果旧数组长度长，那么新数组里的元素全部都可以复用旧数组的元素，无需创建元素，只需要重新调用patch方法，即可把每一个新元素给渲染了，并把多余的旧元素删除。
  • 如果新数组长度长，如旧数组 [a,b,c]，新数组[a,b,c,d,e]，那么[a,b,c]可以直接复用旧数组的元素，后面两个新元素直接创建并插入就好
  • 同理第二种情况也是这种思路

  	 //    比较c1和c2的差异，尽量复用之前的节点
        let i = 0;
        let e1 = c1.length - 1
        let e2 = c2.length - 1
        while (i <= e1 && i <= e2) {
            const n1 = c1[i]
            const n2 = c2[i]
            if (isSameVNode(n1, n2)) {
                patch(n1, n2, el)
            } else {
                break
            }
            i++
        }
        while (e1 >= 0 && e2 >= 0) {
            const n1 = c1[e1]
            const n2 = c2[e2]
            if (isSameVNode(n1, n2)) {
                patch(n1, n2, el)
            } else {
                break
            }
            e1--
            e2--
        }
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

* 通过i和e1,e2的关系来判断新老数组哪个长度长
1

if(i>e1){
            if(i<e2){
                while(i<e2){
                    const nextPos = e2+1
                    let anchor = c2.length<=nextPos?null:c2[nextPos].el
                    patch(null,c2[i],el,anchor)
                    i++
                }
            }
        }
        else if(i>e2){
            if(i<=e1){
                while(i<=e1){
                    umount(c1[i])
                    i++
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 假设旧孩子节点数组为[a,b,c,d,e,f,g],新节点数组为[a,b,s,d,m,e,c,f,g]，经过前面的步骤，需要对比的旧节点变为[c,d,e]，新节点变为[s,d,m,e,c]，显然将剩余的旧节点数组挨个删除，然后重新渲染新的节点数组可以完成渲染，但是这样做显然效率不高。
• 可以发现，新节点中c,d,e节点在旧节点中存在，原则上我们可以复用。

 let s1 = i
            let s2 = i
            let toBePatched = e2-s2+1
            const keyToNewIndexMap = new Map()
            for(let i = s2;i<=e2;i++){
                keyToNewIndexMap.set(c2[i].key,i)
            }
            //初始化一个序列
            const seq = new Array(toBePatched).fill(0)
            for(let i = s1;i<=e1;++i){
                let oldValue = c1[i]
                let newIndex = keyToNewIndexMap.get(c1.key)
                if(newIndex == null){
                    //说明新孩子里不存在这个节点，那就要删除
                    umount(oldValue)
                }else {
                    //记录老旧节点的位置
                    seq[newIndex-s2] = i+1
                     //比较属性
                     patch(oldValue,c2[newIndex],el)
                }
            }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 如果新节点在旧节点中存在，则复用旧节点，更新其属性和孩子，并创建数组seq,记录旧节点和新节点的位置关系，如果不存在，则直接卸载旧节点。
• seq中索引表示新节点 位置，值表示旧节点位置，记录的时候让i+1是为了和初始值0区分，有0的位置表示是新节点和旧节点没有对应关系。
• 这样操作下来，keyToNewIndexMap和seq分别为:
  • keyToNewIndexMap:

* seq
1

• 以上操作成功把可以复用的元素给更新了，用不到的元素给删除，但是可以看到，旧节点中能复用的元素的位置和新节点的不同，要想复用旧节点，还需要把旧节点的位置挪到新节点给定的位置，我们已经有了seq中的对照关系，按照新旧节点的位置一个个挪移元素可以达到要求，但是显然效率太低。
• vue采取的做法是求seq的最长递增子序列，保留该序列，然后让其它不在该序列的元素按顺序插入，这样可以保证移动的元素次数最少，如seq序列如果为[2, 3, 1, 5, 6, 8, 7, 9, 4],那么最长递增子序列为[2,3,5,6,7,9]，保持这几个元素不动，其它元素调整位置即可
• 因此diff比对转化成计算seq的最大递增子序列
  • 默认设置一个数组result = [0],数组用来记录seq中数值的索引，遍历seq中的数，让其在result中从小到大排序，如seq[i] > seq[result[result.length-1]] ，则result.push(i)，否则，从后往前查找result中之前的值，直到seq[i] > seq[result[n-1]] ，另result[n] = i
  • 同时设置一个记录索引的数组p，默认都为0，resulut每记录一个数，p记录该数在result中的前一个数，即记录该数左边的那个数。

 let len = arr.length
    let result = [0];
    let p = new Array(len).fill(0); // p 中存的是什么目前不重要
    let lastIndex;
    let start
    let end
    let middle;
    for (let i = 0; i < len; i++) {
        const arrI = arr[i];
        if (arrI !== 0) { // 0在vue3中意味着新增节点，这个不计入最长递增子序列列表
            lastIndex = result[result.length - 1]; // 去到数组中的最后一项，就是最大的那个索引
            if (arr[lastIndex] < arrI) { // 说明当前这一项比结果集中最后一项大则直接将索引放入即可
                p[i] = lastIndex; // 存的是索引
                result.push(i);
                continue
            }
            // 否则的情况
            start = 0;
            end = result.length - 1; // 二分查找
            while (start < end) { // 计算有序比较都可以这样搞
                middle = Math.floor(((start + end) / 2));
                if (arr[result[middle]] < arrI) {
                    start = middle + 1;
                } else {
                    end = middle
                }
            }
            if (arrI < arr[result[end]]) {
                p[i] = result[end - 1]
                result[end] = i
            }

        }
    }
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

• 如果arr = [2, 3, 1, 5, 6, 8, 7, 9, 4],那么最终得出的result为[2,1,8,4,6,7]，p为[0,0,undefined,1,3,4,4,6,1]
• 然后就可以 根据倒叙查找，找到最长递增子序列的索引。

//倒叙追溯，先取到结果中的最后一个
     let i = result.length
     let last = result[i-1]
     while(i-->0){
         result[i] = last
         last = p[last]
     }
     return result
1
2
3
4
5
6
7
8

• 最终result的结果 为[0,1,3,4,6,7]，其所对应的arr中的值为[2,3,5,6,7,9]
• 找到的result表示老的节点数组中不需要移动的节点序号，接下来需要从后往前挨个遍历新节点 数组,设置索引i为最后一个元素索引,j为result最后一个索引，则i>=j
  • 如果 seq[i] === 0，表面没有复用的节点，则直接创建一个新节点，插入到i+1的前面
  • 如果i !== result[i]，说明旧节点能服用，但需要将节点重新插入到这里
  • 反之 i== result[i]，则不需要管这个元素，令j–

 //这里incr接收result
            let incr = getSequence(seq)
            let j = incr.length - 1
            for(let i = toBePatched-1;i>=0;i--){
                const currentIndex = i+s2
                const child = c2[currentIndex]
                const anchor = c2.length<= currentIndex+1?null:c2[currentIndex+1].el
                if(seq[i] === 0){
                    //说明是新增节点
                    patch(null,child,el,anchor)
                }else {
                    if(i!==incr[j]){
                        //需要移动
                        hostInsert(child.el,el,anchor)
                    }else {
                        j--
                    }
                }
            }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 自此，新旧节点的更新操作逻辑基本就是 这样