• Contents

相关代码位置如下： packages/runtime-core/src/renderer.ts

已知有一个列表：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="c">c</li>
  <li key="d">d</li>
</ul>

然后在中间插入一行，得到一个新列表：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="e">e</li> <!-- 新增 -->
  <li key="c">c</li>
  <li key="d">d</li>
</ul>

在插入操作的前后，它们对应渲染生成的 vnode 可以用一张图表示：（差异主要在新子节点中的 b 节点后面多了一个 e 节点）

将例子稍微修改一下，增加一个 e 节点

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="c">c</li>
  <li key="d">d</li>
  <li key="e">e</li>
</ul>

然后在删除中间一项，得到一个新列表：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
	<!-- 删除 -->
  <li key="d">d</li>
  <li key="e">e</li>
</ul>

在删除操作的前后，它们对应渲染生成的 vnode 可以用一张图表示：（差异主要在新子节点中的 b 节点后面少了一个 c 节点）

通过这两个例子，可以发现新旧 children 拥有相同的头尾节点。对于相同的节点，我们只需要做对比更新即可，所以 diff 算法的第一步从头部开始同步

同步头部节点

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 旧子节点的尾部索引
  let e1 = c1.length - 1
  // 新子节点的尾部索引
  let e2 = l2 - 1
  // 1. 从头部开始同步
  // i = 0, e1 = 3, e2 = 4
  // (a b) c d
  // (a b) e c d
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    if (isSameVNodeType(n1, n2)) {
      // 相同的节点，递归执行 patch 更新节点
      patch(n1, n2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized)
    }
    else {
      break
    }
    i++
  }
}

在整个 diff 的过程，我们需要维护几个变量：头部的索引 i、旧子节点的尾部索引 e1 和新子节点的尾部索引 e2。

同步头部节点就是从头部开始，依次对比新节点和旧节点，如果它们相同的则执行 patch 更新节点；如果不同或者索引 i 大于索引 e1 或者 e2，则同步过程结束。

同步头部节点后的结果：（完成头部节点同步后：i 是 2，e1 是 3，e2 是 4）

同步尾部节点

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 旧子节点的尾部索引
  let e1 = c1.length - 1
  // 新子节点的尾部索引
  let e2 = l2 - 1
  // 1. 从头部开始同步
  // i = 0, e1 = 3, e2 = 4
  // (a b) c d
  // (a b) e c d
  // 2. 从尾部开始同步
  // i = 2, e1 = 3, e2 = 4
  // (a b) (c d)
  // (a b) e (c d)
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized)
    }
    else {
      break
    }
    e1--
    e2--
  }
}

同步尾部节点就是从尾部开始，依次对比新节点和旧节点，如果相同的则执行 patch 更新节点；如果不同或者索引 i 大于索引 e1 或者 e2，则同步过程结束。

同步尾部节点后的结果：（完成尾部节点同步后：i 是 2，e1 是 1，e2 是 2）