diff算法原理和总结 - 翁先森的博客

这里举例采用 vue 的框架设计进行解释 diff

diff 算法的核心其实是都是只关心新旧的虚拟节点都存在一组子节点的情况。目的都是达到减少性能的开销，其中有比较直观的就是—减少 dom 节点的操作

在Vue3 渲染器设计与总结中当涉及到两组子节点的更新的时候，我们采用的是全量卸载并且重新挂载的形式去进行子节点的更新的，这样是非常不合理。

如果只从 “挂载”和“卸载”的两个简单角度出发，我们可以很容易实现一个减少 dom 开销的更新逻辑，如下几图所示

情况一：数量相同的情况

[Image missing: 2023-01-29-00-17-49-image.png]

情况二：旧节点多于新节点

[Image missing: 2023-01-29-00-19-24-image.png]

情况三：旧节点少于新节点

[Image missing: 2023-01-29-00-20-45-image.png]

综上：数量相同的节点我们先进行 patch 从而进行更新操作，卸载和挂载从剩余的节点出发做处理。

因此我们可以改造 patchChildren 的函数简单实现这套逻辑

1
/** 更新children */
2
function pacthChildren(n1, n2, container) {
3
  // 判断新子节点的类型是否是文本节点
4
  if (typeof n2.children === "string") {
5
    // ...
6
  } else if (Array.isArray(n2.children)) {
7
    const oldChildren = n1.children;
8
    const newChildren = n2.children;
9
    /** 旧节点长度 */
10
    const oldL = oldChildren.length;
11
    /** 新节点长度 */
12
    const newL = newChildren.length;
13
    // 比较两者长度，取最短的，然后进行pacth操作
14
    const minL = Math.min(oldL, newL);
15
    // 遍历，目的就是为了达到减少dom的操作
16
    for (let i = 0; i < minL; i++) {
17
      patch(oldChildren[i], newChildren[i]);
18
    }
19
    // 如果有新增节点，及newL > oldL, 说明有节点要进行挂载
20
    if (newL > oldL) {
21
      for (let i = minL; i < newL; i++) {
22
        patch(null, newChildren[i], container);
23
      }
24
    } else if (oldL > newL) {
25
      for (let i = minL; i < oldL; i++) {
26
        unmount(oldChildren[i]);
27
      }
28
    }
29
  } else {
30
    // ...
31
  }
32
}

但是这种方式仍然不是最优的解法，当我们考虑以下这种情况。

1
// 旧节点：
2
[
3
    {type:'p'},
4
    {type:'span'},
5
    {type:'div'}
6
]
7
// 新节点
8
[
9

10
    {type:'div'},
11
    {type:'p'},
12
    {type:'span'},
13
]

他们只是简单的进行了位置的移动，却要进行 3 次的卸载和 3 次的挂载 dom 的操作。因此我们可以从 dom 的复用角度出发，从而引出 diff 算法实现更优解

简单 diff 算法#

要想知道前后的节点进行了移动从而去复用，必须要有标识，在 react 和 vue 中都是采用 key 的形式去给虚拟 dom 做标识的；

1
[
2
  {
3
    "type": "p",
4
    "key": "123",
5
    "children": "123"
6
  },
7
  {
8
    "type": "span",
9
    "key": "234",
10
    "children": "234"
11
  },
12
  {
13
    "type": "div",
14
    "key": "345",
15
    "children": "345"
16
  }
17
]

打补丁#

在我们有了标识了就可以知道前后节点对应的位置，但是 key 值的前后不变，不代表节点不需要更新，因为前后的 children 或者相关的属性也会发生变化，如下

1
/** 旧 */
2
const oldVNode = {
3
  type: "div",
4
  children: [
5
    { type: "p", children: "1", key: "1" },
6
    { type: "p", children: "2", key: "2" },
7
    { type: "p", children: "weng", key: "3" },
8
  ],
9
};
10
/** 新 */
11
const newVNode = {
12
  type: "div",
13
  children: [
14
    { type: "p", children: "kaimin", key: "3" },
15
    { type: "p", children: "1", key: "1" },
16
    { type: "p", children: "2", key: "2" },
17
  ],
18
};

因此我们从新的节点中找到对应 key 值的旧节点从而先进行打补丁的一个操作

1
/** 更新children */
2
function pacthChildren(n1, n2, container) {
3
  // 判断新子节点的类型是否是文本节点
4
  if (typeof n2.children === "string") {
5
    // ...
6
  } else if (Array.isArray(n2.children)) {
7
    const oldChildren = n1.children;
8
    const newChildren = n2.children;
9

10
    // 遍历新children
11
    for (let i = 0; i < newChildren.length; i++) {
12
      const newVNode = array[i];
13
      for (let j = 0; j < oldChildren.length; j++) {
14
        const oldVNode = array[j];
15
        // 如果找到了前后想等key的vnode，那么先进行打补丁操作
16
        if (newVNode.key === oldVNode.key) {
17
          patch(oldVNode, newVNode, container);
18
          break; // 找到了直接退出循环
19
        }
20
      }
21
    }
22
  } else {
23
    // ...
24
  }
25
}

打完补丁之后，前后节点的顺序仍然是不同的，所以我们要进行移动可复用节点

找到可移动的元素#

判断一个节点是否需要移动，则就是判断更新前后的节点顺序有无发生变化

前后节点的 key 值没有发生变化，对应的索引更新后也是 0，1，2 和旧 children 的索引保持一个一个递增的状态，因此这种情况是不需要节点移动的

p-[key]

[Image missing: 2023-01-29-10-37-47-image.png]

如果节点前后顺序改变了

[Image missing: 2023-01-29-10-43-49-image.png]

更新后，节点的索引为，2，0，1，因此我们可以得出，此次更新打破了原有的索引递增规则，原始节点索引为 0 和 1 的节点需要进行移动，且真实的 dom 元素需要移动到 p-3 dom 节点的后头

其实可以将 p-3 在旧 children 中对应的索引定义为：在旧 children 中寻找相同 key 值节点的过程中，遇到的最大索引值，如果后续在寻找过程中发现节点索引值比这个还要小，说明需要进行移动

因此我们改动代码，用一个 “遇到的最大索引” — lastIndex来做标记

1
/** 更新children */
2
function pacthChildren(n1, n2, container) {
3
  // 判断新子节点的类型是否是文本节点
4
  if (typeof n2.children === "string") {
5
    // ...
6
  } else if (Array.isArray(n2.children)) {
7
    const oldChildren = n1.children;
8
    const newChildren = n2.children;
9

10
    /** 寻找旧数组相同key值节点的过程中，遇到的最大索引 */
11
    let lastIndex = 0; // ➕
12

13
    // 遍历新children
14
    for (let i = 0; i < newChildren.length; i++) {
15
      const newVNode = array[i];
16
      for (let j = 0; j < oldChildren.length; j++) {
17
        const oldVNode = array[j];
18
        // 如果找到了前后想等key的vnode，那么先进行打补丁操作
19
        if (newVNode.key === oldVNode.key) {
20
          patch(oldVNode, newVNode, container);
21
          if (j < lastIndex) {
22
            // ➕
23
            // 说明需要移动节点了
24
          } else {
25
            // 表明j比lastIndex还大，需要更新
26
            lastIndex = j; // ➕
27
          }
28
          break; // 找到了直接退出循环
29
        }
30
      }
31
    }
32
  } else {
33
    // ...
34
  }
35
}

现在就找到了需要移动的节点，只要这个节点的旧节点的索引，小于 lastIndex，则就需要移动，接下来说如何移动他

移动节点#

如上的例子，移动完 p-1 之后 vNode 和真实 dom 的对应关系，我们知道新 children 的顺序其实就是更新后的真实 dom 的顺序，所以这里我们把 p-1 移动到 p-3 对应的真实 dom 后面，p-2 同理，p-3 在这个过程是保持不动的。所以我们根据这种情况对 dom 顺序进行操作

[Image missing: 2023-01-29-11-09-30-image.png]

因此我们加入移动真实 dom 的代码

1
/** 更新children */
2
function pacthChildren(n1, n2, container) {
3
  // 判断新子节点的类型是否是文本节点
4
  if (typeof n2.children === "string") {
5
    // ...
6
  } else if (Array.isArray(n2.children)) {
7
    const oldChildren = n1.children;
8
    const newChildren = n2.children;
9

10
    /** 寻找旧数组相同key值节点的过程中，遇到的最大索引 */
11
    let lastIndex = 0;
12

13
    // 遍历新children
14
    for (let i = 0; i < newChildren.length; i++) {
15
      const newVNode = array[i];
16
      for (let j = 0; j < oldChildren.length; j++) {
17
        const oldVNode = array[j];
18
        // 如果找到了前后想等key的vnode，那么先进行打补丁操作
19
        if (newVNode.key === oldVNode.key) {
20
          patch(oldVNode, newVNode, container);
21
          if (j < lastIndex) {
22
            // 说明需要移动节点了
23
            /** 先获取newVNode的前一个Vnode */
24
            const prevVnode = newChildren[i - 1];
25
            // 如果prevVnode不存在，则说明当前newVNode是第一个节点，他不需要进行移动
26
            if (prevVnode) {
27
              // 由于需要将newVNode所对应的真实DOM移到prevVnode所对应的真实DOM的后面
28
              // 所以需要获取prevVNode所对应的真实DOM的下一个兄弟节点，将其作为锚点
29
              const anchor = prevVnode.el.nextSibling;
30
              // 调用inser方法将其插入到anchor锚点的前面，也就是prevVNode对应真实DOM的后面
31
              insert(newVNode.el, container, anchor);
32
            }
33
          } else {
34
            // 表明j比lastIndex还大，需要更新
35
            lastIndex = j;
36
          }
37
          break; // 找到了直接退出循环
38
        }
39
      }
40
    }
41
  } else {
42
    // ...
43
  }
44
}

添加新节点#

以上说的都是前后节点数量相同的情况，现在说新节点数大于旧节点数的情况；

[Image missing: 2023-01-29-16-24-46-image.png]

出发点就是：

找到需要添加的新节点
想办法弄进去

找到需要添加的节点#

找到需要添加的节点，这层好理解，也就是我们在外层（newChildren）遍历去找内层的（oldChildren）key 相同节点的这个过程中，没有找见，说明这个节点就是一个新增的节点。

在内层遍历的时候，这里采用一个find的字段去表示是否找到了节点是 key 相同的。

1
/** 更新children */
2
function pacthChildren(n1, n2, container) {
3
  // 判断新子节点的类型是否是文本节点
4
  if (typeof n2.children === "string") {
5
    // ...
6
  } else if (Array.isArray(n2.children)) {
7
    const oldChildren = n1.children;
8
    const newChildren = n2.children;
9

10
    /** 寻找旧数组相同key值节点的过程中，遇到的最大索引 */
11
    let lastIndex = 0;
12
    /** 表明是否在oldChildren中找到了可复用节点 */
13
    let find = false; // ➕
14

15
    // 遍历新children
16
    for (let i = 0; i < newChildren.length; i++) {
17
      const newVNode = array[i];
18
      for (let j = 0; j < oldChildren.length; j++) {
19
        const oldVNode = array[j];
20
        // 如果找到了前后想等key的vnode，那么先进行打补丁操作
21
        if (newVNode.key === oldVNode.key) {
22
          // 找到了复用的节点，设置为true
23
          find = true; // ➕
24
          patch(oldVNode, newVNode, container);
25
          if (j < lastIndex) {
26
            // 说明需要移动节点了
27
            /** 先获取newVNode的前一个Vnode */
28
            const prevVnode = newChildren[i - 1];
29
            // 如果prevVnode不存在，则说明当前newVNode是第一个节点，他不需要进行移动
30
            if (prevVnode) {
31
              // 由于需要将newVNode所对应的真实DOM移到prevVnode所对应的真实DOM的后面，所以需要获取prevVNode所对应的真实DOM的下一个兄弟节点，将其作为锚点
32
              const anchor = prevVnode.el.nextSibling;
33
              // 调用inser方法将其插入到anchor锚点的前面，也就是prevVNode对应真实DOM的后面
34
              insert(newVNode.el, container, anchor);
35
            }
36
          } else {
37
            // 表明j比lastIndex还大，需要更新
38
            lastIndex = j;
39
          }
40
          break; // 找到了直接退出循环
41
        }
42
      }
43
    }
44
  } else {
45
    // ...
46
  }
47
}

正确添加节点#

通过 find 字段，我们可以增加逻辑，当没有找到相关的复用节点的时候，就可以执行插入：

插入的节点必须插入在 newVNode 的前一个节点的后头，因此需要找到前面一个节点锚点
如果没有前一个节点的情况，那说明，这个 newVNode 所对应的 DOM 是整个 dom 树的第一个节点

因此改造逻辑

1
/** 更新children */
2
function pacthChildren(n1, n2, container) {
3
  // 判断新子节点的类型是否是文本节点
4
  if (typeof n2.children === "string") {
5
    // 当新节点为文本节点的时候，如果旧节点是一组子的节点，我们需要逐个去卸载，其他情况啥也不做
6
    if (Array.isArray(n1.children)) {
7
      n1.children.forEach((node) => unmount(node));
8
    }
9
    // 最后设置新的节点内容
10
    setElementText(container, n2.children);
11
  } else if (Array.isArray(n2.children)) {
12
    const oldChildren = n1.children;
13
    const newChildren = n2.children;
14

15
    /** 寻找旧数组相同key值节点的过程中，遇到的最大索引 */
16
    let lastIndex = 0;
17
    /** 表明是否在oldChildren中找到了可复用节点 */
18
    let find = false;
19

20
    // 遍历新children
21
    for (let i = 0; i < newChildren.length; i++) {
22
      const newVNode = array[i];
23
      for (let j = 0; j < oldChildren.length; j++) {
24
        const oldVNode = array[j];
25
        // 如果找到了前后想等key的vnode，那么先进行打补丁操作
26
        if (newVNode.key === oldVNode.key) {
27
          // 找到了复用的节点，设置为true
28
          find = true;
29
          patch(oldVNode, newVNode, container);
30
          if (j < lastIndex) {
31
            // 说明需要移动节点了
32
            /** 先获取newVNode的前一个Vnode */
33
            const prevVnode = newChildren[i - 1];
34
            // 如果prevVnode不存在，则说明当前newVNode是第一个节点，他不需要进行移动
35
            if (prevVnode) {
36
              // 由于需要将newVNode所对应的真实DOM移到prevVnode所对应的真实DOM的后面，所以需要获取prevVNode所对应的真实DOM的下一个兄弟节点，将其作为锚点
37
              const anchor = prevVnode.el.nextSibling;
38
              // 调用inser方法将其插入到anchor锚点的前面，也就是prevVNode对应真实DOM的后面
39
              insert(newVNode.el, container, anchor);
40
            }
41
          } else {
42
            // 表明j比lastIndex还大，需要更新
43
            lastIndex = j;
44
          }
45
          break; // 找到了直接退出循环
46
        }
47
      }
48

49
      // 如果走到这里find仍然为false，说明这个newNode是新节点，oldChildren中没找到可复用的节点
50
      if (!find) {
51
        /** 先获取newVNode的前一个Vnode */
52
        const prevVnode = newChildren[i - 1];
53
        /** 锚点 */
54
        let anchor = null;
55
        if (prevVnode) {
56
          // 如果有前一个vnode节点，那么就赋值给他的下一个兄弟节点
57
          anchor = prevVnode.el.nextSibling;
58
        } else {
59
          // 说没有前一个节点，那么当前的节点就是整个容器的第一个节点
60
          anchor = container.firstChild;
61
        }
62
        // 执行新节点的挂载操作
63
        patch(null, newVNode, container, anchor);
64
      }
65
    }
66
  } else {
67
    // ...
68
  }
69
}

移除节点#

如下讨论节点被删除的情况

[Image missing: 2023-01-29-20-00-16-image.png]

如图 p-2 节点在更新之后被删除了，按照原有新节点遍历遍历之后，我们会发现，旧的数组中还有残余，因此还需要增加处理老节点中被删除的节点处理逻辑

对于老节点，我们增加如下逻辑：

遍历老节点，从中找到新节点中不存在的节点
卸载老节点

1
/** 更新children */
2
function pacthChildren(n1, n2, container) {
3
  // 判断新子节点的类型是否是文本节点
4
  if (typeof n2.children === "string") {
5
    //...
6
  } else if (Array.isArray(n2.children)) {
7
    const oldChildren = n1.children;
8
    const newChildren = n2.children;
9

10
    /** 寻找旧数组相同key值节点的过程中，遇到的最大索引 */
11
    let lastIndex = 0;
12
    /** 表明是否在oldChildren中找到了可复用节点 */
13
    let find = false;
14

15
    // 遍历新children
16
    for (let i = 0; i < newChildren.length; i++) {
17
      // ...
18
    }
19

20
    // 遍历老children
21
    for (let i = 0; i < oldChildren.length; i++) {
22
      const oldVNode = oldChildren[i];
23
      // 拿旧子节点oldVNode去新的一组中寻找相同key值的节点
24
      const has = newChildren.find((vnode) => vnode.key === oldVNode.key);
25
      // 如果发现新节点中不存在，择要删掉
26
      if (!has) {
27
        unmount(oldVNode);
28
      }
29
    }
30
  } else {
31
    //...
32
  }
33
}

简单 diff 算法就到这里。

双端 diff 算法#

双端 diff 算法指的就是 - 同时对新旧两组子节点的两个端点进行比较的算法

相较于简单 diff 算法，双端 diff 有个优势，通过 4 个指针去进行节点比较找到可复用的节点，比如涉及到简单 diff 中的一个例子

[Image missing: 2023-01-29-10-43-49-image.png]

简单 diff 要进行 2 次的 dom 节点的位置改变

而双端 diff 在这种情况下只需要 1 次 dom 操作（迁移 p-3 节点到 p-1 的前面）

四个端点的表示#

[Image missing: 2023-01-30-09-47-11-image.png]

以下使用代码表示：

1
/** 双端diff算法 */
2
function patchKeyedChildren(n1, n2, container) {
3
  const oldChildren = n1.children;
4
  const newChildren = n2.children;
5
  // 四个索引
6
  let oldStartIdx = 0;
7
  let oldEndIdx = oldChildren.length - 1;
8
  let newStartIdx = 0;
9
  let newEndIdx = newChildren.length - 1;
10
  // 四个索引对应的vNode
11
  let oldStartVNode = oldChildren[oldStartIdx];
12
  let oldEndVNode = oldChildren[oldEndIdx];
13
  let newStartVNode = newChildren[newStartIdx];
14
  let newEndVNode = newChildren[newEndIdx];
15
}

比较方式#

[Image missing: 2023-01-30-10-32-38-image.png]

主要分为 4 个步骤，按照如图 1，2，3，4 的步骤进行比较

1
/** 双端diff算法 */
2
function patchKeyedChildren(n1, n2, container) {
3
  const oldChildren = n1.children;
4
  const newChildren = n2.children;
5
  // 四个索引
6
  let oldStartIdx = 0;
7
  let oldEndIdx = oldChildren.length - 1;
8
  let newStartIdx = 0;
9
  let newEndIdx = newChildren.length - 1;
10
  // 四个索引对应的vNode
11
  let oldStartVNode = oldChildren[oldStartIdx];
12
  let oldEndVNode = oldChildren[oldEndIdx];
13
  let newStartVNode = newChildren[newStartIdx];
14
  let newEndVNode = newChildren[newEndIdx];
15

16
  if (oldStartVNode.key === newStartVNode.key) {
17
    // 第一步：比较oldStartVNode 和newStartVNode
18
  } else if (oldEndVNode.key === newEndVNode.key) {
19
    // 第二步：比较oldEndVNode 和 newEndVNode
20
  } else if (oldStartVNode.key === newEndVNode.key) {
21
    // 第三步：比较oldStartVNode和 newEndVNode
22
  } else if (oldEndVNode.key === newStartVNode.key) {
23
    // 第四步：比较oldEndVNode和 newStartVNode
24
  }
25
}

假如在步骤 1 或者 2 中找到对应复用的节点，说明他们的位置相对而言没有改变，所以不需要进行移动，这时候只需要进行节点的打补丁操作即可，之后将对应的索引同时上移或者是下移。

1
/** 双端diff算法 */
2
function patchKeyedChildren(n1, n2, container) {
3
  const oldChildren = n1.children;
4
  const newChildren = n2.children;
5
  // 四个索引
6
  let oldStartIdx = 0;
7
  let oldEndIdx = oldChildren.length - 1;
8
  let newStartIdx = 0;
9
  let newEndIdx = newChildren.length - 1;
10
  // 四个索引对应的vNode
11
  let oldStartVNode = oldChildren[oldStartIdx];
12
  let oldEndVNode = oldChildren[oldEndIdx];
13
  let newStartVNode = newChildren[newStartIdx];
14
  let newEndVNode = newChildren[newEndIdx];
15

16
  if (oldStartVNode.key === newStartVNode.key) {
17
    // 第一步：比较oldStartVNode 和newStartVNode
18
    // 打补丁
19
    patch(oldStartVNode, newStartVNode, container);
20
    // 更新索引
21
    oldStartVNode = oldChildren[++oldStartIdx];
22
    newStartVNode = newChildren[++newStartIdx];
23
  } else if (oldEndVNode.key === newEndVNode.key) {
24
    // 第二步：比较oldEndVNode 和 newEndVNode
25
    // 打补丁
26
    patch(oldEndVNode, newEndVNode, container);
27
    // 更新索引
28
    oldEndVNode = oldChildren[--oldEndIdx];
29
    newEndVNode = newChildren[--newEndIdx];
30
  } else if (oldStartVNode.key === newEndVNode.key) {
31
    // 第三步：比较oldStartVNode和 newEndVNode
32
  } else if (oldEndVNode.key === newStartVNode.key) {
33
    // 第四步：比较oldEndVNode和 newStartVNode
34
  }
35
}

假如是步骤 4 命中，说明原本在 oldChildren 中是最后一个节点，但是在新顺序中，变成了第一个节点，对应到代码中的逻辑就是：将索引 oldEndIdx 指向的真实 dom 节点，移动到索引 oldStartIdx 指向的虚拟节点所对应的真实 dom 前面，同时更新索引

1
/** 双端diff算法 */
2
function patchKeyedChildren(n1, n2, container) {
3
  const oldChildren = n1.children;
4
  const newChildren = n2.children;
5
  // 四个索引
6
  let oldStartIdx = 0;
7
  let oldEndIdx = oldChildren.length - 1;
8
  let newStartIdx = 0;
9
  let newEndIdx = newChildren.length - 1;
10
  // 四个索引对应的vNode
11
  let oldStartVNode = oldChildren[oldStartIdx];
12
  let oldEndVNode = oldChildren[oldEndIdx];
13
  let newStartVNode = newChildren[newStartIdx];
14
  let newEndVNode = newChildren[newEndIdx];
15

16
  if (oldStartVNode.key === newStartVNode.key) {
17
    // 第一步：比较oldStartVNode 和newStartVNode
18
    // 打补丁
19
    patch(oldStartVNode, newStartVNode, container);
20
    // 更新索引
21
    oldStartVNode = oldChildren[++oldStartIdx];
22
    newStartVNode = newChildren[++newStartIdx];
23
  } else if (oldEndVNode.key === newEndVNode.key) {
24
    // 第二步：比较oldEndVNode 和 newEndVNode
25
    // 打补丁
26
    patch(oldEndVNode, newEndVNode, container);
27
    // 更新索引和头尾部节点变量
28
    oldEndVNode = oldChildren[--oldEndIdx];
29
    newEndVNode = newChildren[--newEndIdx];
30
  } else if (oldStartVNode.key === newEndVNode.key) {
31
    // 第三步：比较oldStartVNode和 newEndVNode
32
  } else if (oldEndVNode.key === newStartVNode.key) {
33
    // 第四步：比较oldEndVNode和 newStartVNode
34
    // 打补丁
35
    patch(oldEndVNode, newStartVNode, container);
36
    // 移动dom
37
    insert(oldEndVNode.el, container, newStartVNode.el);
38
    // 移动完dom之后，更新索引
39
    oldEndVNode = oldChildren[--oldEndIdx];
40
    newStartVNode = newChildren[++newStartIdx];
41
  }
42
}

假如是步骤 3 命中，说明原本在 oldChildren 中是第一个节点，但是在新顺序中，变成了最后一个节点，对应到代码中的逻辑是：将索引 oldStartIdx 指向的真实 dom 节点，移动到索引 oldEndIdx 指向的虚拟节点对应的真实 dom 的后面，同时更新索引

1
/** 双端diff算法 */
2
function patchKeyedChildren(n1, n2, container) {
3
  const oldChildren = n1.children;
4
  const newChildren = n2.children;
5
  // 四个索引
6
  let oldStartIdx = 0;
7
  let oldEndIdx = oldChildren.length - 1;
8
  let newStartIdx = 0;
9
  let newEndIdx = newChildren.length - 1;
10
  // 四个索引对应的vNode
11
  let oldStartVNode = oldChildren[oldStartIdx];
12
  let oldEndVNode = oldChildren[oldEndIdx];
13
  let newStartVNode = newChildren[newStartIdx];
14
  let newEndVNode = newChildren[newEndIdx];
15

16
  if (oldStartVNode.key === newStartVNode.key) {
17
    // 第一步：比较oldStartVNode 和newStartVNode
18
    // 打补丁
19
    patch(oldStartVNode, newStartVNode, container);
20
    // 更新索引
21
    oldStartVNode = oldChildren[++oldStartIdx];
22
    newStartVNode = newChildren[++newStartIdx];
23
  } else if (oldEndVNode.key === newEndVNode.key) {
24
    // 第二步：比较oldEndVNode 和 newEndVNode
25
    // 打补丁
26
    patch(oldEndVNode, newEndVNode, container);
27
    // 更新索引和头尾部节点变量
28
    oldEndVNode = oldChildren[--oldEndIdx];
29
    newEndVNode = newChildren[--newEndIdx];
30
  } else if (oldStartVNode.key === newEndVNode.key) {
31
    // 第三步：比较oldStartVNode和 newEndVNode
32
    // 打补丁
33
    patch(oldStartVNode, newEndVNode, container);
34
    insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);
35
    // 更新下一个索引
36
    oldStartVNode = oldChildren[++oldStartIdx];
37
    newEndVNode = newChildren[--newEndIdx];
38
  } else if (oldEndVNode.key === newStartVNode.key) {
39
    // 第四步：比较oldEndVNode和 newStartVNode
40
    // 打补丁
41
    patch(oldEndVNode, newStartVNode, container);
42
    // 移动dom
43
    insert(oldEndVNode.el, container, newStartVNode.el);
44
    // 移动完dom之后，更新索引
45
    oldEndVNode = oldChildren[--oldEndIdx];
46
    newStartVNode = newChildren[++newStartIdx];
47
  }
48
}

再将更新的逻辑封装到一个 while 循环中，由于每一轮的循环，都会更新相对应的索引值，所以循环的条件：头部的索引值要小于等于尾部索引值

1
/** 双端diff算法 */
2
function patchKeyedChildren(n1, n2, container) {
3
  const oldChildren = n1.children;
4
  const newChildren = n2.children;
5
  // 四个索引
6
  let oldStartIdx = 0;
7
  let oldEndIdx = oldChildren.length - 1;
8
  let newStartIdx = 0;
9
  let newEndIdx = newChildren.length - 1;
10
  // 四个索引对应的vNode
11
  let oldStartVNode = oldChildren[oldStartIdx];
12
  let oldEndVNode = oldChildren[oldEndIdx];
13
  let newStartVNode = newChildren[newStartIdx];
14
  let newEndVNode = newChildren[newEndIdx];
15

16
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
17
    if (oldStartVNode.key === newStartVNode.key) {
18
      // 第一步：比较oldStartVNode 和newStartVNode
19
      // 打补丁
20
      patch(oldStartVNode, newStartVNode, container);
21
      // 更新索引
22
      oldStartVNode = oldChildren[++oldStartIdx];
23
      newStartVNode = newChildren[++newStartIdx];
24
    } else if (oldEndVNode.key === newEndVNode.key) {
25
      // 第二步：比较oldEndVNode 和 newEndVNode
26
      // 打补丁
27
      patch(oldEndVNode, newEndVNode, container);
28
      // 更新索引和头尾部节点变量
29
      oldEndVNode = oldChildren[--oldEndIdx];
30
      newEndVNode = newChildren[--newEndIdx];
31
    } else if (oldStartVNode.key === newEndVNode.key) {
32
      // 第三步：比较oldStartVNode和 newEndVNode
33
      // 打补丁
34
      patch(oldStartVNode, newEndVNode, container);
35
      insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);
36
      // 更新下一个索引
37
      oldStartVNode = oldChildren[++oldStartIdx];
38
      newEndVNode = newChildren[--newEndIdx];
39
    } else if (oldEndVNode.key === newStartVNode.key) {
40
      // 第四步：比较oldEndVNode和 newStartVNode
41
      // 打补丁
42
      patch(oldEndVNode, newStartVNode, container);
43
      // 移动dom
44
      insert(oldEndVNode.el, container, newStartVNode.el);
45
      // 移动完dom之后，更新索引
46
      oldEndVNode = oldChildren[--oldEndIdx];
47
      newStartVNode = newChildren[++newStartIdx];
48
    }
49
  }
50
}

双端 diff 的优势#

比如简单 diff 中的所说的一个例子

[Image missing: 2023-01-30-21-14-52-image.png]

在简单的 diff 算法中，我们需要将 p-1 和 p-2 的节点移动到 p-3 的节点后面，进行两次的 dom 移动操作。

双端 diff 针对这种情况流程如下：

[Image missing: 2023-01-30-21-25-43-image.png]

第一轮循环

1~3 步骤：比较，两者 key 不同，不能复用

4 步骤：比较发现新的子节点头部节点和旧子节点的尾部节点 key 相同，因此我们执行第四个 else if 执行逻辑，旧的尾部节点移动到 oldStartVNode 对应的真实 dom 前面

[Image missing: 2023-01-30-22-54-23-image.png]

接下来开始新的一轮循环

1 步骤：比较新旧子节点的头部节点 key，发现相等，都在头部所以只需要打补丁即可，不需要移动，并且更新索引值

[Image missing: 2023-01-30-22-58-39-image.png]

再开始新的一轮循环

1 步骤直接匹配，同上，只需要打补丁和更新索引值就好了。到这一步不满足循环条件就直接跳出了

[Image missing: 2023-01-30-23-09-48-image.png]

非理想状态情况考虑#

上面的几种情况都是比较理想的情况，在每一轮的循环中，都可以匹配到相等的 key 值，但是非理想的状态下只能通过增加额外的处理方式来进行。

比如如下的这种情况：

[Image missing: 2023-01-30-23-13-44-image.png]

这种情况，无论是哪一轮，都不能匹配上，如果我们用之前的代码，循环直接就死了

这里有个骚操作，就是拿新子节点的头部节点，去旧子节点中寻找与之相同的 key 的节点。

在这里我们用 p-2 去找旧子节点中的匹配节点，发现下标是 1，而新的位置下标是 0，比他大，说明 p-2 节点对应的真实 dom 应该移动到 oldStartVNode 对应 dom 位置之前，因此我们追加逻辑

1
/** 双端diff算法 */
2
function patchKeyedChildren(n1, n2, container) {
3
  const oldChildren = n1.children;
4
  const newChildren = n2.children;
5
  // 四个索引
6
  let oldStartIdx = 0;
7
  let oldEndIdx = oldChildren.length - 1;
8
  let newStartIdx = 0;
9
  let newEndIdx = newChildren.length - 1;
10
  // 四个索引对应的vNode
11
  let oldStartVNode = oldChildren[oldStartIdx];
12
  let oldEndVNode = oldChildren[oldEndIdx];
13
  let newStartVNode = newChildren[newStartIdx];
14
  let newEndVNode = newChildren[newEndIdx];
15

16
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
17
    if (oldStartVNode.key === newStartVNode.key) {
18
      // ...
19
    } else if (oldEndVNode.key === newEndVNode.key) {
20
      // ...
21
    } else if (oldStartVNode.key === newEndVNode.key) {
22
      // ...
23
    } else if (oldEndVNode.key === newStartVNode.key) {
24
      // ...
25
    } else {
26
      // 遍历旧的子节点组，找到与newStartIdx拥有相同的key值的元素
27
      const idxInOld = oldChildren.findIndex(
28
        (node) => node.key === newStartVNode.key
29
      );
30
      // idxInOld大于0，说明找到了可复用的节点，并且需要将其对应的真实dom移动到头部
31
      if (idxInOld > 0) {
32
        const vnodeToMove = oldChildren[idxInOld];
33
        // 先打补丁
34
        patch(vnodeToMove, newStartVNode, container);
35
        // 将vnodeToMove.el移动到oldStartVnode.el之前，用其做锚点
36
        insert(vnodeToMove.el, container, oldStartVNode.el);
37
        // 由于位置idxInOld处的节点所对应的真实dom已经移到了别处，所以这里我们直接设置这个vnode为undefined
38
        oldChildren[idxInOld] = undefined;
39
        // 最后更新newStartIdx到下一个位置
40
        newStartIdx = newChildren[++newStartIdx];
41
      }
42
    }
43
  }
44
}

移动之后的状态图如下：

[Image missing: 2023-01-30-23-50-11-image.png]

之后再进行 2 轮的循环，最终索引会匹配到我们上面特殊处理后被置为 undefined 的节点，到了这一步我们也需要对 undefined 的情况做特殊处理，此时节点的状态如下

[Image missing: 2023-01-30-23-57-50-image.png]

再循环的时候，我们需要绕过 undefined 的这一个已经处理过的节点，可能涉及的情况就是，头部节点和尾部节点都不存在的情况，因此加入判断逻辑。

1
/** 双端diff算法 */
2
function patchKeyedChildren(n1, n2, container) {
3
  const oldChildren = n1.children;
4
  const newChildren = n2.children;
5
  // 四个索引
6
  let oldStartIdx = 0;
7
  let oldEndIdx = oldChildren.length - 1;
8
  let newStartIdx = 0;
9
  let newEndIdx = newChildren.length - 1;
10
  // 四个索引对应的vNode
11
  let oldStartVNode = oldChildren[oldStartIdx];
12
  let oldEndVNode = oldChildren[oldEndIdx];
13
  let newStartVNode = newChildren[newStartIdx];
14
  let newEndVNode = newChildren[newEndIdx];
15

16
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
17
    if (!oldStartVNode) {
18
      // ➕
19
      oldStartVNode = oldChildren[++oldStartIdx]; // ➕
20
    } else if (!oldEndVNode) {
21
      // ➕
22
      oldEndVNode = oldChildren[--oldEndIdx]; // ➕
23
    } else if (oldStartVNode.key === newStartVNode.key) {
24
      // ...
25
    } else if (oldEndVNode.key === newEndVNode.key) {
26
      // ...
27
    } else if (oldStartVNode.key === newEndVNode.key) {
28
      // ...
29
    } else if (oldEndVNode.key === newStartVNode.key) {
30
      // ...
31
    } else {
32
      // 遍历旧的子节点组，找到与newStartIdx拥有相同的key值的元素
33
      const idxInOld = oldChildren.findIndex(
34
        (node) => node.key === newStartVNode.key
35
      );
36
      // idxInOld大于0，说明找到了可复用的节点，并且需要将其对应的真实dom移动到头部
37
      if (idxInOld > 0) {
38
        const vnodeToMove = oldChildren[idxInOld];
39
        // 先打补丁
40
        patch(vnodeToMove, newStartVNode, container);
41
        // 将vnodeToMove.el移动到oldStartVnode.el之前，用其做锚点
42
        insert(vnodeToMove.el, container, oldStartVNode.el);
43
        // 由于位置idxInOld处的节点所对应的真实dom已经移到了别处，所以这里我们直接设置这个vnode为undefined
44
        oldChildren[idxInOld] = undefined;
45
        // 最后更新newStartIdx到下一个位置
46
        newStartIdx = newChildren[++newStartIdx];
47
      }
48
    }
49
  }
50
}

之后的流程就可以正常的进行了。

添加新元素情况#

如下这种情况

[Image missing: 2023-01-31-10-30-26-image.png]

经过一轮的循环会发现，1 2 3 4 步骤全部没有命中，那么我们会执行特殊的逻辑，以新节点的头部去旧子节点中去寻找与之 key 相等的，发现也没有命中。这里就需要补充逻辑，去弥补没有查找到的情况。

1
/** 双端diff算法 */
2
function patchKeyedChildren(n1, n2, container) {
3
  const oldChildren = n1.children;
4
  const newChildren = n2.children;
5
  // 四个索引
6
  let oldStartIdx = 0;
7
  let oldEndIdx = oldChildren.length - 1;
8
  let newStartIdx = 0;
9
  let newEndIdx = newChildren.length - 1;
10
  // 四个索引对应的vNode
11
  let oldStartVNode = oldChildren[oldStartIdx];
12
  let oldEndVNode = oldChildren[oldEndIdx];
13
  let newStartVNode = newChildren[newStartIdx];
14
  let newEndVNode = newChildren[newEndIdx];
15

16
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
17
    if (!oldStartVNode) {
18
      // ...
19
    } else if (!oldEndVNode) {
20
      // ...
21
    } else if (oldStartVNode.key === newStartVNode.key) {
22
      // ...
23
    } else if (oldEndVNode.key === newEndVNode.key) {
24
      // ...
25
      newEndVNode = newChildren[--newEndIdx];
26
    } else if (oldStartVNode.key === newEndVNode.key) {
27
      // ...
28
    } else if (oldEndVNode.key === newStartVNode.key) {
29
      // ...
30
    } else {
31
      // 遍历旧的子节点组，找到与newStartIdx拥有相同的key值的元素
32
      const idxInOld = oldChildren.findIndex(
33
        (node) => node.key === newStartVNode.key
34
      );
35
      // idxInOld大于0，说明找到了可复用的节点，并且需要将其对应的真实dom移动到头部
36
      if (idxInOld > 0) {
37
        const vnodeToMove = oldChildren[idxInOld];
38
        // 先打补丁
39
        patch(vnodeToMove, newStartVNode, container);
40
        // 将vnodeToMove.el移动到oldStartVnode.el之前，用其做锚点
41
        insert(vnodeToMove.el, container, oldStartVNode.el);
42
        // 由于位置idxInOld处的节点所对应的真实dom已经移到了别处，所以这里我们直接设置这个vnode为undefined
43
        oldChildren[idxInOld] = undefined;
44
      } else {
45
        // 没有命中说明，是新节点在newChildren中的头部，因此需要将此新节点挂载到oldStartVNode对应dom的前面
46
        patch(null, newStartVNode, container, oldStartVNode.el);
47
      }
48
      // 最后更新newStartIdx到下一个位置
49
      newStartVNode = newChildren[++newStartIdx];
50
    }
51
  }
52
}

以上是在 1 2 3 4 轮中，都没有命中的情况才会考虑到新节点的情况，如果其中一轮命中了，那么新节点会被忽略掉，如下这种情况

[Image missing: 2023-01-31-14-47-06-image.png]

在第 2 轮的比较中，能够匹配到相对应的 key 值，并且在后续的循环中都能一一对应找到节点，直至以下这种状态

[Image missing: 2023-01-31-15-50-48-image.png]

这种状态已经表明，索引越界，循环跳出了，但是此时的 p-4 新增的这个几点也被忽略了，

因此我们还需要增加逻辑，去处理遗漏的新增节点。

遗漏的节点位于的区间就在于 newStartIdx 和 newEndIdx 之间，所以我们去循环遍历挨个挂载，挂载时候的锚点仍然是处于 oldStartVNode 对应 dom

1
/** 双端diff算法 */
2
function patchKeyedChildren(n1, n2, container) {
3
  const oldChildren = n1.children;
4
  const newChildren = n2.children;
5
  // 四个索引
6
  let oldStartIdx = 0;
7
  let oldEndIdx = oldChildren.length - 1;
8
  let newStartIdx = 0;
9
  let newEndIdx = newChildren.length - 1;
10
  // 四个索引对应的vNode
11
  let oldStartVNode = oldChildren[oldStartIdx];
12
  let oldEndVNode = oldChildren[oldEndIdx];
13
  let newStartVNode = newChildren[newStartIdx];
14
  let newEndVNode = newChildren[newEndIdx];
15

16
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
17
    // ...
18
  }
19

20
  // 循环结束后检查索引的情况，避免需要新增的节点被遗漏
21
  if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
22
    // 如果满足条件，我们去遍历遗漏节点，逐个挂载
23
    for (let i = newStartIdx; i <= newEndIdx; i++) {
24
      // 以oldStartVNode对应的dom为锚点
25
      patch(null, newChildren[i], container, oldStartVNode.el);
26
    }
27
  }
28
}

移除不存在的元素#

移除和新增的类似，都是在最后一步检查索引值，如下这种情况：

[Image missing: 2023-01-31-16-04-50-image.png]

通过几次循环之后直到以下这种情况，此时的变量 newStartIdx 的值大于变量 newEndIdx 的值，停止循环，但是旧的一组节点中还存在未被处理的节点，所以应该将其移除，同理，此时是旧节点剩余，所以应该卸载在区间 oldStartIdx 和 oldEndIdx 之间的节点

[Image missing: 2023-01-31-16-25-31-image.png]

1
/** 双端diff算法 */
2
function patchKeyedChildren(n1, n2, container) {
3
  const oldChildren = n1.children;
4
  const newChildren = n2.children;
5
  // 四个索引
6
  let oldStartIdx = 0;
7
  let oldEndIdx = oldChildren.length - 1;
8
  let newStartIdx = 0;
9
  let newEndIdx = newChildren.length - 1;
10
  // 四个索引对应的vNode
11
  let oldStartVNode = oldChildren[oldStartIdx];
12
  let oldEndVNode = oldChildren[oldEndIdx];
13
  let newStartVNode = newChildren[newStartIdx];
14
  let newEndVNode = newChildren[newEndIdx];
15

16
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
17
    // ...
18
  }
19

20
  // 循环结束后检查索引的情况，避免需要新增的节点被遗漏
21
  if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
22
    // 如果满足条件，我们去遍历遗漏节点，逐个挂载
23
    for (let i = newStartIdx; i <= newEndIdx; i++) {
24
      patch(null, newChildren[i], container, oldStartVNode.el);
25
    }
26
  } else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
27
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
28
      unmount(oldChildren[i]);
29
    }
30
  }
31
}

到这里就都处理完了