vue3的dom diff过程。
在diff过程中，通过找出最长递增子序列，确定出不需要变化的部分。

  • 快速diff算法相对双端diff算法更进一步优化。可在节点diff的过程中找出最长递增子序列，这个序列中的节点顺序是相对不发生变化的，所以可以更进一步的减少DOM移动操作。快速diff算法还包含预处理步骤，预处理会处理相同的前缀和后缀部分。

    11.1处理前置和后置元素

    快速diff算法借鉴纯文本diff算法中预处理的步骤。

    新增节点

    一组新旧子节点如下：

  • p-1、p-2、p-3

  • p-1、p-4、p-2、p-3

通过观察可以发现，新旧节点具有相同的前置节点p-1和相同的后置节点p-3、p-4。对于相同的前置和后置节点，他们在新旧两组节点中的相当位置不变，无需移动他们。
快速diff - 图1
对于前置节点，可以建立索引J，初始值为0，用来指向两组子节点的开头。
开启while循环，让索引J递增，直到遇到不同的节点位置。调整patchKeyedChildren函数代码

  1. function patchKeyedChildren(n1,n2, container){
  2.   const newChildren = n2.children;
  3.   const oldChildren = n1.children;
  4.   // 处理相同的前置节点 ，索引J指向新旧两组子节点的开头
  5.   let j =0;
  6.   let oldVnode = oldChildren[j];
  7.   let newVnode = newChildren[j];
  8.   // while循环向后变量，直到遇到不同key 停止
  9.   while(oldVnode.key === newVnode.key){
  10.     //调用patch函数
  11.     patch(oldVnode, newVnode, container);
  12.     //更新索引J的值
  13.     j++;
  14.     oldVnode = oldChildren[j];
  15.     newVnode = newChildren[j];
  16.   }
  17. }

通过while循环查找出所有的相同的前置节点，并调用patch函数进行打补丁。遇到不同的key，停止循环。经过操作之后，新旧两组子节点的状态如下图：
快速diff - 图2
while停止循环，变量索引j的值为1。接下来处理相同的后置节点。
由于新旧两组子节点的数量可能不同，所以需要定义2个索引newEnd和oldEnd，分别指向新旧两组子节点中的最后一个节点。
快速diff - 图3
开启while循环，从尾向前开始变量，调整patchKeyedChildren函数

  1. function patchKeyedChildren(n1,n2, container){
  2.   const newChildren = n2.children;
  3.   const oldChildren = n1.children;
  4.   // 处理相同的前置节点 ，索引J指向新旧两组子节点的开头
  5.   let j =0;
  6.   let oldVnode = oldChildren[j];
  7.   let newVnode = newChildren[j];
  8.   // while循环向后变量，直到遇到不同key 停止
  9.   while(oldVnode.key === newVnode.key){
  10.     //调用patch函数
  11.     patch(oldVnode, newVnode, container);
  12.     //更新索引J的值
  13.     j++;
  14.     oldVnode = oldChildren[j];
  15.     newVnode = newChildren[j];
  16.   }
  18.   // 更新相同的后置节点
  19.   // 设置索引oldEnd，指向旧节点的最后一个
  20.   let oldEnd = oldChildren.length -1;
  21.   // 设置索引newEnd，指向新节点的最后一个
  22.   let newEnd = newChildren.length - 1;
  23.   oldVnode = oldChildren[oldEnd];
  24.   newVnode = newChildren[newEnd];
  25.   // 从后向前遍历，直到遇到不同的key停止
  26.   while(oldVnode.key === newVnode.key){
  27.     patch(oldVnode, newVnode, container);
  28.     oldEnd--;
  29.     newEnd--;
  30.     oldVnode = oldChildren[oldEnd];
  31.     newVnode = newChildren[newEnd];
  32.   }
  33. }

后置节点处理完成后，更新oldEnd和newEnd的值，新旧两组子节点的状态如下：
快速diff - 图4
新旧子节点相同的前置和后置节点都被处理后，旧节点全部被处理，新节点遗留个节点p-4，说明该节点是新增节点。判断是新增节点的条件：

  • oldEnd < j成立，说明旧节点全部被处理

  • newEnd >= j成立，说明在预处理过后，在新的一组子节点中，仍然有未被处理的节点，这些节点就是新增节点。这个区间[j, newEnd]内的节点，都是新增节点。

    1. function patchKeyedChildren(n1,n2, container){
    2. const newChildren = n2.children;
    3. const oldChildren = n1.children;
    5. // 处理相同的前置节点 ，索引J指向新旧两组子节点的开头
    6. let j =0;
    7. let oldVnode = oldChildren[j];
    8. let newVnode = newChildren[j];
    9. // while循环向后变量，直到遇到不同key 停止
    10. while(oldVnode.key === newVnode.key){
    11.   //调用patch函数
    12.   patch(oldVnode, newVnode, container);
    13.   //更新索引J的值
    14.   j++;
    15.   oldVnode = oldChildren[j];
    16.   newVnode = newChildren[j];
    17. }
    19. // 更新相同的后置节点
    20. // 设置索引oldEnd，指向旧节点的最后一个
    21. let oldEnd = oldChildren.length -1;
    22. // 设置索引newEnd，指向新节点的最后一个
    23. let newEnd = newChildren.length - 1;
    24. oldVnode = oldChildren[oldEnd];
    25. newVnode = newChildren[newEnd];
    26. // 从后向前遍历，直到遇到不同的key停止
    27. while(oldVnode.key === newVnode.key){
    28.   patch(oldVnode, newVnode, container);
    29.   oldEnd--;
    30.   newEnd--;
    31.   oldVnode = oldChildren[oldEnd];
    32.   newVnode = newChildren[newEnd];
    33. }
    35. // 前置和后置预处理完毕后，还有剩余节点
    36. if(oldEnd < j && j <= newEnd){
    37.   // 锚点索引
    38.   const anchorIndex = newEnd + 1;
    39.   const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null;
    40.   // 采用while循环，调用patch函数，逐个挂载新增节点
    41.   while(j <= newEnd){
    42.    patch(null, newChildren[j++], container, anchor);
    43.   }
    44. }
    45. }

    第39行判断锚点的取值。如果超过新节点的总长度，则为null，说明在最后追加元素。
    第41行，开启while循环，遍历索引j和newEnd之间的节点，并调用patch函数挂载它们。

    删除节点

    上面案例是新增节点，接下来处理删除节点。有两组子节点

  • p-1、p-2、p-3

  • p-1、p-3

同样使用 j、oldEnd、newEnd进行标记。
快速diff - 图5
处理相同的前置节点，处理后的状态
快速diff - 图6
处理相同的后置节点，处理后的状态
快速diff - 图7
相同的前置和后置节点全部处理，此时新节点被全部处理，发现旧的一组子节点遗留了节点p-2。说明应该卸载区间[j, oldEnd]之间的元素。

  1. function patchKeyedChildren(n1,n2, container){
  2.   const newChildren = n2.children;
  3.   const oldChildren = n1.children;
  5.   // 处理相同的前置节点 ，索引J指向新旧两组子节点的开头
  6.   // ...
  8.   // 更新相同的后置节点
  9.   // 设置索引oldEnd，指向旧节点的最后一个
  10.   // ...
  12.   // 前置和后置预处理完毕后，还有剩余节点
  13.   if(oldEnd < j && j <= newEnd){
  14.     // 锚点索引
  15.     const anchorIndex = newEnd + 1;
  16.     const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null;
  17.     // 采用while循环，调用patch函数，逐个挂载新增节点
  18.     while(j <= newEnd){
  19.      patch(null, newChildren[j++], container, anchor);
  20.     }
  21.   }else if(newEnd < j && j <= oldEnd){
  22.     while(j<=oldEnd){ //卸载j 和 oldEnd之前的元素。
  23.       unmount(oldChildren[j++])
  24.     }
  25.   }
  26. }

代码示例

⭐️11.2判断是否需要DOM移动

上节介绍了预处理前置节点和后置节点，并简单处理了新增节点和删除节点的逻辑，并没有处理复杂的移动元素操作。使用一个复杂的例子，新旧两组子节点的顺序如下：

  • 旧的子节点：p-1、p-2、p-3、p-4、p-6，p-5；
  • 新的子节点：p-1、p-3、p-4、p-2、p-7、p-5；

对比发现，新的子节点多了p-7，少了节点p-6。相同的前置节点p-1，相同后置节点p-5；
快速diff - 图8
接下来要进行的处理：

  • 判断是否有节点需要移动，以及该如何移动
  • 找出被添加或移除的节点

处理过前置节点和后置节点，索引 j 和变量newEnd和oldEnd不满足下面两个条件中的任何一个。

  • j > oldEnd && j <= newEnd;
  • j > newEnd && j <= oldEnd;

给函数patchKeyedChildren添加处理分支 else

  1. function patchKeyedChildren(n1, n2, container){
  2.   const newChildren = n2.children;
  3.   const oldChildren = n1.children;
  4.   // 更新相同的前置节点
  5.   // ...
  7.   // 更新相同的后置节点
  8.   //...
  10.   if(j > oldEnd && j<= newEnd){
  11.    //...
  12.   }else if(j > newEnd && j<= oldEnd){
  13.     //..
  14.   }else{
  15.     //增加else分支，处理非理想情况
  16.   }
  17. }

后续的逻辑处理将添加到else分支，首先需要构造一个source数组，长度等于新的一组子节点在经过预处理后剩余的未处理的节点的数量，并初始化source中每个元素的初始值为-1.
快速diff - 图9

  1. else{
  2.   //构造source数组
  3.   const len = newEnd - j + 1;
  4.   const source = new Array(len);
  5.   source.fill(-1);
  6. }

source数组用来存储新的一组子节点中的节点在旧的一组子节点中的位置索引， 后边将会使用这个索引计算最长递增子序列，并完成DOM移动操作。

source默认初始值-1，用来存在新节点元素在旧节点中的索引值
快速diff - 图10
source的值为 [2, 3, 1, -1];如何用代码实现给source填充索引值，可以使用两层for循环来完成。外层循环遍历旧的子节点，内层循环遍历新的子节点；

  1. else{
  2.   //构造source数组
  3.   const len = newEnd - j + 1;
  4.   const source = new Array(len);
  5.   source.fill(-1);
  7.   // oldStart 和 newStart 分别为起始索引 j
  8.   const oldStart = j;
  9.   const newStart = j;
  10.   for(let i=oldStart; i<=oldEnd; i++){
  11.     const oldVnode = oldChildren[i];
  12.     //
  13.     for(let k=newStart; k<=newEnd; k++){
  14.       const newVnode = newChildren[k];
  15.       // 找到相同的key值
  16.       if(oldVnode.key === newVnode.key){
  17.         patch(oldVnode, newVnode, container)
  18.         //填充source数组
  19.         source[k - newStart] = i;
  20.       }
  21.     }
  22.   }
  23. }

source数组值填充完毕，但是目前这个方案使用了双层for循环，时间复杂度为O2

通过建立索引表，填充source值

当新旧节点数量较多时，两层for循环嵌套会带来性能问题，出于优化的目的，可以为新的一组子节点构建一张索引表，用来存储节点的key和节点位置索引之间的映射。
快速diff - 图11

  • source数组：新节点中的值，对应的值在旧节点中的索引
  • 索引表： 【新节点中的key值 : 节点位置的索引】

  • 第二个for循环，用来遍历旧的子节点，用旧子节点的key值去索引表keyIndx中查找该节点在新节点中的位置，并将结果存储为变量K。

    • k存在，说明节点可复用，调用patch进行打补丁，并填充source数组
    • 否则说明该节点已经不存在新的节点中，调用unmount函数卸载它 ```javascript if(j > oldEnd && j <= newEnd){ //… }else if(j > newEnd && j<= oldEnd){ //… }else{ const count = newEnd - j +1; const source = new Array(count); source.file(-1);

    // oldStart 和newStart 分别为起始索引 const oldStart = j; const newStart = j; //构建索引表 const keyIndex = {}; for(let i = newStart; i<=newEnd; i++){ // 以新节点的key值为key，以节点的索引序号为值 keyIndex[newChildren[i].key] = i; } // 遍历旧的子节点中未处理的节点 for(let i = oldStart; i<=oldEnd; i++){ oldVnode = oldChildren[i]; //通过旧节点中的key，在索引表中查找，相同key值的节点的位置 const k = keyIndex[oldVnode.key]; if(typeof k !== “undefined”){

    1. newVnode = newChildren[k];
    2. // 调用patch函数完成更新
    3. patch(oldVnode, newVnode, container);
    4. // 填充source数组
    5. source[k - newStart] = i;

    }else{

    1. unmount(oldVnode);

    } } }

    1. 上面执行完毕，source数组已经填充。接下来判断节点是否需要移动。<br />新增两个变量moved和pos，moved初始值为false，表示是否需要移动节点。pos表示位置索引，初始值为0，代表遍历旧节点过程中遇到的最大索引值。如果最大索引值呈递增趋势，则不需要移动节点，否则需要移动。
    2. ```javascript
    3. if(j > oldEnd && j <= newEnd){
    4. //...
    5. }else if(j > newEnd && j<= oldEnd){
    6. //...
    7. }else{
    8. const count = newEnd - j +1;
    9. const source = new Array(count);
    10. source.file(-1);
    12. // oldStart 和newStart 分别为起始索引
    13. const oldStart = j;
    14. const newStart = j;
    15. // 新增变量 moved和pos
    16. let moved = false;
    17. let pos = 0;
    18. //构建索引表
    19. const keyIndex = {};
    20. for(let i = newStart; i<=newEnd; i++){
    21.   // 以新节点的key值为key，以节点的索引序号为值
    22.   keyIndex[newChildren[i].key] = i;
    23. }
    24. // 遍历旧的子节点中未处理的节点
    25. for(let i = oldStart; i<=oldEnd; i++){
    26.   oldVnode = oldChildren[i];
    27.   //通过旧节点中的key，在索引表中查找，相同key值的节点的位置
    28.   const k = keyIndex[oldVnode.key];
    29.   if(typeof k !== "undefined"){
    30.     newVnode = newChildren[k];
    31.     // 调用patch函数完成更新
    32.     patch(oldVnode, newVnode, container);
    33.     // 填充source数组
    34.     source[k - newStart] = i;
    35.     // 判断节点是否需要移动
    36.     if(k < pos){ // k值小于pos值，说明非递增状态
    37.       moved = false;
    38.     } else {
    39.       pos = k; // k大于pos，更新pos的值
    40.     }
    41.   }else{
    42.     unmount(oldVnode);
    43.   }
    44. }
    45. }

    除此之外，还需要增加一个数量表示，代表已经更新过的节点数量，如果更新过的数量超过了新子节点要更新的数量，说明存在多余的节点，应该将它们卸载。
    新增patched变量，初始值为0.代表更新过节点数量。在第二个for循环中添加判断 patched <= count，则正常执行更新，每次更新都让变量patched自增；否则调用unmount函数将它们卸载。

    1. if(j > oldEnd && j <= newEnd){
    2. //...
    3. }else if(j > newEnd && j<= oldEnd){
    4. //...
    5. }else{
    6. const count = newEnd - j +1;
    7. const source = new Array(count);
    8. source.file(-1);
    10. // oldStart 和newStart 分别为起始索引
    11. const oldStart = j;
    12. const newStart = j;
    13. // 新增变量 moved和pos
    14. let moved = false;
    15. let pos = 0;
    16. //构建索引表
    17. const keyIndex = {};
    18. for(let i = newStart; i<=newEnd; i++){
    19.   // 以新节点的key值为key，以节点的索引序号为值
    20.   keyIndex[newChildren[i].key] = i;
    21. }
    22. //新增patched变量，代表更新过的节点的数量
    23. let patched = 0;
    24. // 遍历旧的子节点中未处理的节点
    25. for(let i = oldStart; i<=oldEnd; i++){
    26.   oldVnode = oldChildren[i];
    27.   //如果更新过的节点数量小于等于需要更新节点数量，则执行更新
    28.   if(patched <= count){
    29.     //通过旧节点中的key，在索引表中查找，相同key值的节点的位置
    30.     const k = keyIndex[oldVnode.key];
    31.     if(typeof k !== "undefined"){
    32.       newVnode = newChildren[k];
    33.       // 调用patch函数完成更新
    34.       patch(oldVnode, newVnode, container);
    35.       // 每次更新一个节点，都将patched+1
    36.       patched ++;
    37.       // 填充source数组
    38.       source[k - newStart] = i;
    39.       // 判断节点是否需要移动
    40.       if(k < pos){ // k值小于pos值，说明非递增状态
    41.         moved = false;
    42.       } else {
    43.         pos = k; // k大于pos，更新pos的值
    44.       }
    45.     }else{
    46.       unmount(oldVnode);
    47.     }
    48.   }else{
    49.     // 如果更新过的节点数量大于需要更新的节点数量，需要卸载多余节点
    50.     unmount(oldVnode);
    51.   }
    52. }
    53. }

    代码示例

    11.3如何移动元素

    上一节实现的目标：

  • 判断DOM是否需要DOM移动操作，创建了变量moved作为标识

  • 构建source数组，数组中存储着新的子节点中的节点在旧子节点中的位置，后面根据source数组计算出最长递增子系列，用于DOM移动操作。
    1. if(j > oldEnd && j <= newEnd){
    2. // ...
    3. }else if(j > newEnd && j <= oldEnd){
    4. //...
    5. }else{
    6. // ...
    7. for(let i=oldStart; i<=oldEnd; i++){
    8.  // ...
    9. }
    10. if(moved){
    11.   //如果moved为真，需要进行DOM移动
    12. }
    13. }
    代码新增if(moved)分支处理，如果moved为真，需要进行DOM移动，为了进行DOM移动，首先根据source数组的值计算出它的最长递增子序列。仍然使用如下图的例子
    快速diff - 图12
    数组source的值[2, 3, 1, -1]，该数组的最长递增子序列为[0, 1];

    最长递增子序列，使用lis函数计算一个数组的最长递增子序列，lis函数的返回结果是最长递增子序列中的元素在source数组中的位置索引。source的最长递增子序列是[2, 3]，最终结果是[0 ,1]; 最长递增子序列的概念https://en.wikipedia.org/wiki/Longest_increasing_subsequence。具体可以查看其它详细资料。

快速diff - 图13
子序列seq的值为[0,1],它的含义是，在新的子节点中，重新编码后索引值为0和1的这两个节点在更新时前后顺序没有发生变化，也就是DOM节点不用移动。0和1对应的节点为p-3和p-4。
快速diff - 图14
为了完成节点移动，还要创建索引值i和s

  • 用索引i指向新的子节点中的最后一个元素；i = count -1;
  • 用索引s指向递增子序列中的最后一个元素 ; s = seq.length -1;

快速diff - 图15
向上移动，说明for循环从后向前遍历。

  1. if(moved){
  2.   const seq = lis(sources);
  3.   // s 指向最长递增子序列的最后一个元素
  4.   let s = seq.length - 1;
  5.   // i 指向除去前置后置元素，剩下的需要更新的节点的最后一个
  6.   let i = count -1;
  7.   // for循环中 i 递减，
  8.   for(i; i>=0; i--){
  9.     if(i !== seq[s]){
  10.       // 如果索引i不等于 seq[s] 的值，说明节点需要移动
  11.     }else{
  12.       // 索引i等于seq[s]的值，节点不用移动，只要让s指向下一个位置。
  13.       s--;
  14.     }
  15.   }
  16. }

for循环的目的，就是让变量i向上移动，逐个访问新节点中需要更新的节点，这里的变量i就是节点的索引。
如果source[i] === -1；说明节点是全新的节点，需要进行挂载；

  1. if(moved){
  2.   const seq = lis(sources);
  3.   // s 指向最长递增子序列的最后一个元素
  4.   let s = seq.length - 1;
  5.   // i 指向除去前置后置元素，剩下的需要更新的节点的最后一个
  6.   let i = count -1;
  7.   // for循环中 i 递减，
  8.   for(i; i>=0; i--){
  9.     if(source[i] === -1){
  10.       //说明索引为i的节点是全新节点，该节点在children中的真实位置索引
  11.       const pos = i + newStart
  12.       const newVnode = newChildren[pos]
  13.       const nextPos = pos + 1;
  14.       // 锚点
  15.       const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null;
  16.       // 挂载
  17.       patch(null, newVnode, container, anchor)
  18.     }else if(i !== seq[s]){
  19.       // 如果索引i不等于 seq[s] 的值，说明节点需要移动
  20.     }else{
  21.       // 索引i等于seq[s]的值，节点不用移动，只要让s指向下一个位置。
  22.       s--;
  23.     }
  24.   }
  25. }

新节点创建完毕后，for循环执行了一次。进行i—，索引i向上移动一步，指向节点p-2。
接着进入下一轮for循环

  • 第一步：判断source[i]是否等于 -1 ；此时p-2节点的source的值为1，不需要重新挂载，进入下一步
  • 判断 i !== seq[s] 是否成立？此时索引 i 为2，索引 s的值为1；2 !==seq[s]成立，节点p-2对应的DOM需要移动。移动后，如下图

快速diff - 图16
用代码实现移动p-2节点

  1. if(moved){
  2.   const seq = lis(sources);
  3.   // s 指向最长递增子序列的最后一个元素
  4.   let s = seq.length - 1;
  5.   // i 指向除去前置后置元素，剩下的需要更新的节点的最后一个
  6.   let i = count -1;
  7.   // for循环中 i 递减，
  8.   for(i; i>=0; i--){
  9.     if(source[i] === -1){
  10.       //说明索引为i的节点是全新节点，该节点在children中的真实位置索引
  11.       const pos = i + newStart
  12.       const newVnode = newChildren[pos]
  13.       const nextPos = pos + 1;
  14.       // 锚点
  15.       const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null;
  16.       // 挂载
  17.       patch(null, newVnode, container, anchor)
  18.     }else if(i !== seq[s]){
  19.       // 如果索引i不等于 seq[s] 的值，说明节点需要移动
  20.       const pos = i + newStart;
  21.       const newVnode = newChildren[pos];
  22.       const nextPos = pos + 1;
  23.       //锚点
  24.       const anchor = nextPos < newChildren.length? newChildren[nextPos].el : null;
  25.       insert(newVnode, container, anchor);
  26.     }else{
  27.       // 索引i等于seq[s]的值，节点不用移动，只要让s指向下一个位置。
  28.       s--;
  29.     }
  30.   }
  31. }

移动节点类似挂载节点，不同点是移动节点是通过insert函数完成。
进行下一轮for循环，此时索引i指向节点p-4
快速diff - 图17
更新过程分三个步骤：

  • 判断source[i] === -1，条件不成立，不需要挂载节点
  • 判断 i !== seq[s] ，条件不成立
  • 此时 i === seq[s] , 条件成立，说明节点p-4不需要移动，只用让索引s指向s—；

快速diff - 图18