简易 Diff 算法

简单来说,当新旧 vnode 的字节点都是一组节点时,为了以最小的性能开销完成更新操作,需要比较两组子节点,用于比较的算法就叫做 Diff 算法。我们知道,操作 DOM 的性能开销通常比较大,而渲染器的核心 Diff 算法就是为了解决这个问题而诞生的。

减少 DOM 操作性能开销

核心 Diff 只关心新旧虚拟节点都存在一组子节点的情况。如果我们针对两组子节点的更新,只采用卸载全部,再挂载全部新子节点。这么做确实可以完成更新,单由于没有复用任何 DOM 元素,会产生极大的性能开销。

以下面的新旧虚拟节点为例:

const oldVNode = {
  type: 'div',
  children: [
    { type: 'p', children: '1' },
    { type: 'p', children: '2' },
    { type: 'p', children: '3' }
  ]
}

const newVNode = {
  type: 'div',
  children: [
    { type: 'p', children: '4' },
    { type: 'p', children: '5' },
    { type: 'p', children: '6' }
  ]
}
js

如果我们采用卸载全部,再挂载全部新子节点的方法,需要执行 6 次 DOM 操作:

  • 卸载所有旧子节点,需要 3 次 DOM 删除操作;
  • 挂载所有新子节点,需要 3 次 DOM 添加操作。

但是,通过观察上面新旧 vnode 的子节点,可以发现:

  • 更新前后的所有子节点都是 p 标签,即便签元素不变;
  • 只有 p 标签的子节点(文本节点)会发生变化。

例如,oldVNode 的第一个子节点是一个 p 标签,且该 p 标签的子节点类型是文本节点,内容是 “1”。而 newVNode 的第一个子节点也是一个 p 标签,它的子节点的类型也是文本节点,内容是 “4”。可以发现,更新前后改变的只有 p 标签文本节点的内容。所以,最理想的更新方式是,直接更新这个 p 标签的文本节点的内容。这样只需要一次 DOM 操作,即可完成一个 p 标签更新。新旧虚拟节点都有 3 个 p 标签作为子节点,所以一共只需要 3 次 DOM 操作就可以完成全部节点的更新。相比原来需要执行 6 次 DOM 操作才能完成更新的方式,性能提升了一倍。

按照这个思路,我们可以重新实现两组子节点的更新逻辑,如下面 patchChildren 函数的代码所示:

function patchChildren (n1, n2, container) {
  if (typeof n2.children === 'string') {
    // ...
  } else if (Array.isArray(n2.children)) {
    // 新旧 children
    const oldChildren = n1.children
    const newChildren = n2.children
    // 遍历旧 children
    for (let i = 0; i < oldChildren.length; i++) {
      patch(oldChildren[i], newChildren[i])
    }
  } else {
    // ...
  }
}
js

在前端代码中,oldChildrennewChildren 分别是旧的一组子节点和新的一组子节点。我们遍历前者,并将两者中对应位置的节点分别传递给 patch 函数进行更新。patch 函数在执行更新时,如果发现新旧子节点只有文本内容不同,只会更新其文本节点的内容。这样,我们就可以将 6 次 DOM 操作减少为 3 次。下图是整个更新过程的示意图。

simple_diff01.png

这种做法虽然能够减少 DOM 操作次数,但问题也很明显。我们通过遍历旧的一组子节点,并假设新的一组子节点的数量与之相同,只有在这种情况下,这段代码才能正确地工作。但是,新旧两组子节点的数量未必相同。当新的一组子节点的数量少于旧的一组子节点的数量时,意味着有些节点在更新后应该被卸载。

simple_diff02.png

当旧的一组子节点一共有 4 个 p 标签,而新的一组子节点中只有 3 个 p 标签。这说明,在更新过程中,需要将不存在的 p 标签卸载。类似地,新的一组子节点的数量也可能比旧的一组子节点的数量多。

simple_diff03.png

当新的一组子节点比旧的一组子节点多了一个 p 标签。在这种情况下,我们应该挂载新增节点。

通过上面的分析我们意识到,在进行新旧两组子节点的更新时,不应该总是遍历旧的一组子节点或遍历新的一组子节点,而是应该遍历其中长度较短的那一组。这样,我们才能够尽可能多地调用 patch 函数进行更新。接着,再对比新旧两组子节点的长度,如果新的一组子节点更长,则说明有新子节点需要挂载,否则说明有旧子节点需要卸载。

function patchChildren (n1, n2, container) {
  if (typeof n2.children === 'string') {
    // ...
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children
    
    const oldLen = oldChildren.length
    const newLen = newChildren.length

    const commonLength = Math.min(oldLen, newLen)

    for (let i = 0; i < commonLength; i++) {
      patch(oldChildren[i], newChildren[i])
    }

    if (newLen > oldLen) {
      for (let i = commonLength; i < newLen; i++) {
        patch(null, newChildren[i], container)
      }
    } else {
      for (let i = commonLength; i < oldLen; i++) {
        unmount(oldChildren[i])
      }
    }
  } else {
    // ...
  }
}
js

这样,无论新旧两组子节点的数量关系如何,我们都可以正确地挂载或卸载它们。

DOM 复用与 key 的作用

我们可以通过减少 DOM 操作的次数,提升更新性能。但这种方式仍存在可优化的空间。举个例子,假设新旧两组子节点的内容如下:

[
  { type: 'p' },
  { type: 'div' },
  { type: 'span' }
]

[
  { type: 'span' },
  { type: 'p' },
  { type: 'div' }
]
js

如果使用上面介绍的算法来完成上述两组子节点的更新,则需要 6 次 DOM 操作。

但是,观察新旧两组子节点,很容易发现,二者只是顺序不同。所以最优的处理方式是,通过 DOM 的移动来完成子节点的更新,这要比不断地执行子节点的卸载和挂载性能更好。但是,想要通过 DOM 的移动来完成更新,必须要保证一个前提:新旧两组子节点中的确存在可复用的节点。这个很好理解,如果新的子节点没有在旧的一组子节点中出现,就无法通过移动节点的方式完成更新。所以现在问题就变成:应该如何确定新的子节点是否出现在旧的一组子节点中。拿上面的例子来说,如果确定新的一组子节点中第 1 个子节点 { type: 'sppan' } 与旧子节点中的第 3 个子节点相同呢?一种解决方案是,通过 vnode.type 来判断,只要 vnode.type 的值相同,我们就认为两者是相同的节点。但这种方式并不可靠。

[
  { type: 'p', children: '1' },
  { type: 'p', children: '2' },
  { type: 'p', children: '3' }
]

[
  { type: 'p', children: '3' },
  { type: 'p': children: '1' },
  { type: 'p', children: '2' }
]
js

观察上面两组子节点,我们发现,这个案例可以通过移动 DOM 的方式来完成更新,但是所有节点的 vnode.type 属性值都相同,这导致我们无法确定新旧两组子节点中节点的对应关系,也就无法得知应该进行怎样的 DOM 移动才能完成更新。这时,我们就需要引入额外的 key 来作为 vnode 的标识,如下面的代码所示:

[
  { type: 'p', children: '1', key: 1 },
  { type: 'p', children: '2', key: 2 },
  { type: 'p', children: '3', key: 3 }
]

[
  { type: 'p', children: '3', key: 3 },
  { type: 'p': children: '1', key: 1 },
  { type: 'p', children: '2', key: 2 }
]
js

key 属性就像虚拟节点的 “身份证” 号,只要两个虚拟节点的 type 属性值和 key 属性值都相同,那么我们就认为它们是相同的,即可以进行 DOM 的复用。下图展示了有 key 和无 key 时新旧两组子节点的映射情况。

simple_diff04.png

如果没有 key,我们无法知道新子节点与旧子节点间的映射关系,也就无法知道应该如何移动节点。有 key 的话情况则不同,我们根据子节点的 key 属性,能够明确知道新子节点在旧子节点中的位置,这样就可以进行相应的 DOM 移动操作了。

有必要强调一点是,DOM 可复用并不意味着不需要更新,如果下面的两个虚拟节点所示:

const oldVNode = { type: 'p', key: 1, children: 'text 1' }
const newVNode = { type: 'p', key: 1, children: 'text 2' }
js

这两个虚拟节点拥有相同的 key 值和 vnode.type 属性值。这意味着,在更新时可以复用 DOM 元素,即只需要通过移动操作来完成更新。但仍需要对这两个虚拟节点进行打补丁操作,因为新的虚拟节点(newVNode)的文本子节点的内容已经改变了。因此,在讨论如何移动 DOM 之前,我们需要先完成打补丁操作。

function patchChildren (n1, n2, container) {
  if (typeof n2.children === 'string') {
    // ...
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    const oldLen = oldChildren.length
    const newLen = newChildren.length

    // 判断是否可以复用
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      for (let j = 0; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]
        // 如果找到具有相同 key 值的节点,说明可以复用,但是仍需要调用 patch 函数更新
        if (newVNode.key === oldVNode.key) {
          patchChildren(oldVNode, newVNode, container)
          break;
        }
      }
    }

		// ...
  } else {
    // ...
  }
}
js

在上面这段代码中,我们重新实现了新旧两组子节点的更新逻辑。可以看到,我们使用了两层 for 循环,外层循环用于遍历新的一组子节点,内层循环则遍历旧的一组子节点。在内层循环中,我们逐个对比新旧子节点的 key 值,试图在旧的子节点中找到可复用的节点。一旦找到,则调用 patch 函数进行打补丁。经过这一步操作后,我们能保证所有可复用的节点本身都经过更新完毕。

const oldVNode = {
  type: 'div',
  children: [
    { type: 'p', children: '1', key: 1 },
    { type: 'p', children: '2', key: 2 },
    { type: 'p', children: 'hello', key: 3 }
  ]
}

const newVNode = {
  type: 'div',
  children: [
    { type: 'p', children: 'world', key: 3 },
    { type: 'p', children: '1', key: 1 },
    { type: 'p', children: '2', key: 2 },
  ]
}

renderer.renderer(oldVNode, document.querySelector('#app'))
setTimeout(() => {
  renderer.renderer(newVNode, document.querySelector('#app'))
}, 1000)
js

运行上面这段代码,1 秒后,key 值为 3 的子节点对应的真实 DOM 的文本内容会由 “hello” 更新为字符串 “world”。

更新操作具体过程分析如下:

  • 第一步,取新的一组子节点中的第一个子节点,即 key 值为 3 的节点。尝试在旧的一组子节点中寻找具有相同 key 值的节点。我们发现,旧的子节点 oldVNode[2] 的 key 值为 3,于是调用 patch 函数进行打补丁。在这一步操作完成之后,渲染器会把 key 值为 3 的虚拟节点所对应的真实 DOM 的文本内容由字符串 “hello” 更新为字符串 “world”。
  • 第二步,取新的一组子节点中的第二个子节点,即 key 值为 1 的节点。尝试在旧的一组子节点寻找具有相同 key 值的节点。我们发现,旧的子节点 oldVNode[0] 的 key 值为 1,于是调用 patch 函数进行打补丁。由于 key 值等于 1 的新旧子节点没有任何差异,所以什么都不会做。
  • 第三步,取新的一组子节点中的最后一个子节点,即 key 值为 2 的节点,最终结果与第二步相同。

经过上述更新操作,所有节点对应的真实 DOM 元素都更新完毕了。但真实 DOM 仍然保持旧的一组子节点的顺序,即 key 值为 3 的节点对应的真实 DOM 仍然是最后一个子节点。由于在新的一组子节点中,key 值为 3 的节点已经变为第一个子节点了,因此我们还需要通过移动节点来完成真实 DOM 顺序的更新。

找到需要移动的元素

现在,我们已经能够通过 key 值找到可复用的节点了。接下来需要思考的时候,如何判断一个节点是否需要移动,以及如何移动。对于第一个问题,我们可以采用逆向思维的方式,先想一想在什么情况下节点不需要移动?答案很简单,当新旧两组子节点的节点顺序不变时,就不需要额外的移动操作。

simple_diff05.png

当新旧两组子节点的顺序没有发生变化:

  • key 值为 1 的节点在旧 children 数组中的索引为 0;
  • key 值为 2 的节点在旧 children 数组中的索引为 1;
  • key 值为 3 的节点在旧 children 数组中的索引为 2。

接着,我们对新旧两组子节点采用上一节介绍的更新算法,看看新旧两组子节点的顺序没有发生变化时,更新算法具有怎么的特点。

  • 第一步:取新的一组子节点中的第一个节点 p-1 ,它的 key 为 1。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点,发现能够找到,并且该节点在旧的一组子节点中的索引为 0;
  • 第二步:取新的一组子节点中的第二个节点 p-2,它的 key 为 2。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点,发现能够找到,并且该节点在旧的一组子节点中的索引为 1;
  • 第三步:取新的一组子节点中的第二个节点 p-3,它的 key 为 3。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点,发现能够找到,并且该节点在旧的一组子节点中的索引为 2。

在这个过程中,第一次寻找可复用的节点时,都会记录该可复用节点在旧的一组子节点中的位置索引。如果把这些位置索引值按照先后顺序排列,则可以得到一个序列:0、1、2。这是一个递增的序列,在这种情况下不需要移动任何节点。

我们再来看另外一个例子。

simple_diff06.png

同样,我们根据图中的例子再次执行更新算法。

  • 第一步:取新的一组子节点中的第一个节点 p-3 ,它的 key 为 3。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点,发现能够找到,并且该节点在旧的一组子节点中的索引为 2;
  • 第一步:取新的一组子节点中的第一个节点 p-1 ,它的 key 为 1。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点,发现能够找到,并且该节点在旧的一组子节点中的索引为 0。节点 p-1 对应的真实 DOM 需要移动。
  • 第一步:取新的一组子节点中的第一个节点 p-2 ,它的 key 为 2。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点,发现能够找到,并且该节点在旧的一组子节点中的索引为 1。节点 p-2 对应的真实 DOM 需要移动。

以上就是 Diff 算法在执行更新的过程中,判断节点是否需要移动的方式。在上面的例子中,我们可以得出节点 p-1 和节点 p-2 需要移动的结论。这是因为在旧的 children 中的索引要小于节点 p-3 在旧 children 中的索引。如果我们按照先后顺序记录在寻找节点过程中所遇到的位置索引,将会得到序列:2、0、1。可以发现,这个序列不具有递增的趋势。

其实我们可以将节点 p-3 在旧 children 中的索引定义为:在旧 children 中寻找具有相同 key 值节点的过程中,遇到的最大索引值。如果在后续寻找的过程中,存在索引值比当前遇到的最大索引值还要小的节点,则意味着该节点需要移动。

我们可以用 lastIndex 变量存储整个寻找过程中遇到的最大索引值,如下面的代码所示:

function patchChildren (n1, n2, container) {
  if (typeof n2.children === 'string') {
    // ...
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    const oldLen = oldChildren.length
    const newLen = newChildren.length

    // 存储寻找过程中遇到的最大索引值
    let lastIndex = 0

    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      for (let j = 0; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]

        // 如果找到具有相同 key 值的节点,说明可以复用,但是仍需要调用 patch 函数更新
        if (newVNode.key === oldVNode.key) {
          patchChildren(oldVNode, newVNode, container)

          if (j < lastIndex) {
            // 如果当前找到的节点在旧 children 中的索引小于最大索引值 lastIndex
            // 说明该节点对应的真实 DOM 需要移动
          } else {
            // 如果当前找到的节点在旧 children 中的索引小于最大索引值
            // 则更新 lastIndex 的值
            lastIndex = j
          }
          break;
        }
      }
    }
  } else {
    // ...
  }
}
js

如以上代码及注释所示,如果新旧节点的 key 值相同,说明我们在旧 children 中找到了可复用的 DOM 的节点。此时我们用该节点在旧 children 中的索引 j 与 lastIndex 进行比较,如果 j 小于 lastIndex ,说明当前 oldVnode 对应的真实 DOM 需要移动,否则说明不需要移动。但此时应该将变量 j 的值赋值给变量 lastIndex ,以保证寻找节点的过程中,变量 lastIndex 始终存储着当前遇到的最大索引值。

现在,我们已经找到了需要移动的节点,下面我们将讨论如何移动节点,从而完成节点顺序的更新。

如何移动元素

我们讨论了如何判断节点是否需要移动。移动节点指的是,移动一个虚拟节点所对应的真实 DOM 节点,并不是移动虚拟节点本身。既然移动的时真实 DOM 节点,那么就需要取得对它的引用。我们知道,当一个虚拟节点被挂载后,其对应的真实 DOM 节点会存在它的 vnode.el 属性中。

simple_diff07.png

因此,在代码中,我们可以通过旧子节点的 vnode.el 属性取得它对应的真实 DOM 节点。

当更新操作发生时,渲染器会调用 patchElement 函数在新旧虚拟节点之间进行打补丁。

function patchElement (n1, n2) {
  // 新的 vnode 也引用了真实 DOM 元素
  const el = n2.el = n1.el
  // ...
}
js

可以看到,patchElement 函数首先将旧节点的 n1.el 属性赋值给新节点的 n2.el 属性。这个赋值语句其实就是 DOM 元素的复用。在复用 DOM 元素之后,新节点也将持有对真实 DOM 的引用。

simple_diff08.png

可以看到,无论是新子节点还是旧子节点,都存在对真实 DOM 的引用,在此基础上,我们就可以进行 DOM 移动操作了。

const oldVNode = {
  type: 'div',
  children: [
    { type: 'p', children: '1', key: 1 },
    { type: 'p', children: '2', key: 2 },
    { type: 'p', children: 'hello', key: 3 }
  ]
}

const newVNode = {
  type: 'div',
  children: [
    { type: 'p', children: 'world', key: 3 },
    { type: 'p', children: '1', key: 1 },
    { type: 'p', children: '2', key: 2 },
  ]
}
js

simple_diff06.png

以图示为例, 它的更新步骤如下:

  • 第一步:取新的一组子节点中第一个节点 p-3,它的 key 为 3,尝试在旧的一组子节点中找到具有相同 key 值的可复用节点。发现可以找到,并且该节点在旧的一组子节点中的索引为 2。此时变量 lastIndex 的值为 0,索引 2 不小于 0,所以节点 p-3 对应的真实 DOM 不需要移动,但需要更新变量 lastIndex 的值为 2.

  • 第二步:取新的一组子节点中第二个节点 p-1,它的 key 为 1,尝试在旧的一组子节点中找到具有相同 key 值的可复用节点。发现可以找到,并且该节点在旧的一组子节点中的索引为 0。此时变量 lastIndex 的值为 2,索引 0 小于 2,所以节点 p-1 对应的真实 DOM 需要移动。

    我们发现,节点 p-1 对应的真实 DOM 需要移动,但是应该移动到哪?我们知道,新 children 的顺序其实就是更新后真实 DOM 节点应有的顺序。所以节点 p-1 在新 children 中的位置就代表真实 DOM 更新后的位置。由于节点 p-1 在新 children 中排在节点 p-3 后面,所以我们应该把节点 p-1 所对应的真实 DOM 移动导节点 p-3 所对应的真实 DOM 后面。

    这样操作后,此时真实 DOM 的顺序为 p-2、p-3、p-1。

simple_diff09.png

  • 第三步:取新的一组子节点中第二个节点 p-2 ,它的 key 为 2,尝试在旧的一组子节点中找到具有相同 key 值的可复用节点。发现可以找到,并且该节点在旧的一组子节点中的索引为 1。此时变量 lastIndex 的值为 2,索引 1 小于 2,所以节点 p-2 对应的真实 DOM 需要移动。

    第三步和第二步类似,节点 p-2 对应的真实 DOM 也需要移动。同样,由于节点 p-2 在新 children 中排在节点 p-1 后面,所以我们应该把节点 p-2 对应的真实 DOM 移动到节点 p-1 对应的真实 DOM 后面。

simple_diff10.png

经过这一步移动操作之后,我们发现,真实 DOM 的顺序与新的一组子节点的顺序想通了。至此,更新操作完成。

function patchChildren (n1, n2, container) {
  if (typeof n2.children === 'string') {
    // ...
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    const oldLen = oldChildren.length
    const newLen = newChildren.length

    // 存储寻找过程中遇到的最大索引值
    let lastIndex = 0

    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      let j = 0;
      for (j; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]

        // 如果找到具有相同 key 值的节点,说明可以复用,但是仍需要调用 patch 函数更新
        if (newVNode.key === oldVNode.key) {
          patch(oldVNode, newVNode, container)

          if (j < lastIndex) {
            // 如果当前找到的节点在旧 children 中的索引小于最大索引值 lastIndex
            // 说明该节点对应的真实 DOM 需要移动
            // 获取 newVNode 的前一个 vnode,即 prevVNode
            const prevVNode = newChildren[i - 1]
            // 如果 prevVnode 不存在,说明当前 newVNode 是第一个节点,不需要移动
            if (prevVNode) {
              // 由于我们要将 newVnode 对应的真实 DOM 移动到 prevVNode 所对应真实 DOM 后面
              // 所以我们需要获取 prevVNode 所对应真实 DOM 的下一个兄弟节点,并将其作为锚点
              const anchor = prevVNode.el.nextSibling
              // 调用 insert 方法将 newVNode 对应的真实 DOM 插入到锚点元素前面
              // 也就是 prevVNode 对应的真实 DOM 后面
              insert(newVnode.el, container, anchor)
            }
          } else {
            // 如果当前找到的节点在旧 children 中的索引小于最大索引值
            // 则更新 lastIndex 的值
            lastIndex = j
          }
          break;
        }
      }
    }
  } else {
    // ...
  }
}
js

在这段代码中,如果条件 j < lastIndex 成立,则说明当前 newVNode 所对应的真实 DOM 需要移动。根据前文的分析可知,我们需要获取当前 newVNode 节点的前一个虚拟节点,即 newChildren[i - 1] ,然后使用 insert 函数完成节点的移动,其中 insert 函数依赖浏览器原生的 insertBefore 函数。

const renderer = createRenderer({
  insert (el, parent, anchor = null) {
    // insertBefore 需要描点元素 anchor
    parent.insertBefore(el, anchor)
  }
})
js

添加新元素

本小节我们将讨论添加新节点的情况。

simple_diff11.png

从图中可知,在新的一组子节点中,多出来一个节点 p-4,它的 key 值为 4,该节点在旧的一组子节点不存在,因此应该将其视为新增节点。对于新增节点,在更新时我们应该正确地将它挂载,这主要分为两步:

  • 找到新增节点;
  • 将新增节点挂载到正确位置。

首先,我们来看一下如何找到新增节点。为了搞清楚这个问题,我们需要根据图中给出的例子模拟执行下逻辑。在此之前,我们需要弄清楚新旧两组子节点与真实 DOM 元素的当前状态。

simple_diff12.png

接着,我们开始模拟更新逻辑。

  • 第一步:取新的一组子节点中第一个节点 p-3,它的 key 值为 3,尝试在旧的一组子节点中寻找可复用的节点。发现能够找到,并且该节点在旧的一组子节点中的索引值为 2。此时,变量 lastIndex 的值为 0,索引值 2 不小于 lastIndex 的值 0,所以节点 p-3 对应的真实 DOM 不需要移动,但是需要将变量 lastIndex 的值更新为 2。
  • 第二步:取新的一组子节点中第一个节点 p-1,它的 key 值为 1,尝试在旧的一组子节点中寻找可复用的节点。发现能够找到,并且该节点在旧的一组子节点中的索引值为 0。此时,变量 lastIndex 的值为 2,索引值 0 小于 lastIndex 的值 2,所以节点 p-1 对应的真实 DOM 需要移动,并且应该移动到节点 p-3 对应的真实 DOM 后面。经过这一步的移动操作后,真实 DOM 的顺序为 p-2、p-3、p-1。
  • \kl;
  • 第三步:取新的一组子节点中第一个节点 p-4,它的 key 值为 4,尝试在旧的一组子节点中寻找可复用的节点。由于在旧的一组子节点中,没有 key 值为 4 的节点,因此渲染器会把节点 p-4 看作新增节点并挂载它。但是,应该将挂载到哪里呢?为了搞清楚这个问题,我们需要观察节点 p-4 在新的一组子节点中的位置。由于节点 p-4 出现在节点 p-1 后面,我们我们应该把节点 p-4 挂载到节点 p- 1 所对应的真实 DOM 后面。经过这一步操作后,此时真实 DOM 的顺序是:p-2、p-3、p-1、p-4,其中 p-4 是刚刚挂载的。
  • 第四步:取新的一组子节点中第一个节点 p-2,它的 key 值为 2,尝试在旧的一组子节点中寻找可复用的节点。发现能够找到,并且该节点在旧的一组子节点中的索引值为 1。此时,变量 lastIndex 的值为 2,索引值 1 小于 lastIndex 的值 2,所以节点 p-2 对应的真实 DOM 需要移动,并且应该移动到节点 p-4 对应的真实 DOM 后面。经过这一步的移动操作后,真实 DOM 的顺序为 p-3、p-1、p-4、p-2。至此,真实 DOM 顺序已经与新的一组子节点的顺序相同,更新完成。

接着,我们来实现代码。

function patchChildren (n1, n2, container) {
  if (typeof n2.children === 'string') {
    // ...
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    const oldLen = oldChildren.length
    const newLen = newChildren.length

    // 存储寻找过程中遇到的最大索引值
    let lastIndex = 0

    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      let j = 0;

      // 第一层循环中定义变量 find,代表是否在旧的一组子节点中找到可复用的节点,
      // 初始值为 false,代表没找到
      let find = false

      for (j; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]

        // 如果找到具有相同 key 值的节点,说明可以复用,但是仍需要调用 patch 函数更新
        if (newVNode.key === oldVNode.key) {
          // 找到可复用的节点,将变量 find 的值设置为 true
          find = true

          patch(oldVNode, newVNode, container)

          if (j < lastIndex) {
            // 如果当前找到的节点在旧 children 中的索引小于最大索引值 lastIndex
            // 说明该节点对应的真实 DOM 需要移动
            // 获取 newVNode 的前一个 vnode,即 prevVNode
            const prevVNode = newChildren[i - 1]
            // 如果 prevVnode 不存在,说明当前 newVNode 是第一个节点,不需要移动
            if (prevVNode) {
              // 由于我们要将 newVnode 对应的真实 DOM 移动到 prevVNode 所对应真实 DOM 后面
              // 所以我们需要获取 prevVNode 所对应真实 DOM 的下一个兄弟节点,并将其作为锚点
              const anchor = prevVNode.el.nextSibling
              // 调用 insert 方法将 newVNode 对应的真实 DOM 插入到锚点元素前面
              // 也就是 prevVNode 对应的真实 DOM 后面
              insert(newVnode.el, container, anchor)
            }
          } else {
            // 如果当前找到的节点在旧 children 中的索引小于最大索引值
            // 则更新 lastIndex 的值
            lastIndex = j
          }
          break;
        }
      }

      // 如果代码运行到这里,find 仍然是 false
      // 说明当前 newVNode 没有在旧的一组子节点中找到可复用的节点
      // 也就是说,当前 newVNode 是新增节点,需要挂载
      if (!find) {
        // 为了将节点挂载到正确位置,我们需要先获取锚点元素
        // 首先获取当前 newVNode 的前一个 vnode 节点
        const parentVNode = newChildren[i - 1]
        
        let anchor = null

        if (prevVNode) {
          // 如果存在前一个 vnode 节点,则使用它的下一个兄弟节点作为锚点元素
          anchor = prevVNode.el.nextSibling
        } else {
          // 如果没有前一个 vnode 节点,说明即将挂载的新节点是第一个子节点
          // 这时我们使用容器元素的 fristChild 作为锚点
          anchor = container.firstChild
        }

        // 挂载 newVNode
        patch(null, newVnode, container, anchor)
      }
    }
  } else {
    // ...
  }
}
js

观察上面这段代码。首先,我们在外层循环中定义了名为 find 的变量,它代表渲染器能否在旧的一组子节点中找到可复用的节点。变量 find 的初始值为 false,一旦寻找到可复用的节点,则将变量 find 的值设置为 true。如果内层循环结束后,变量 find 的值仍然为 false,则说明 newVNode 是一个全新的节点,需要挂载它。为了将节点挂载到正确位置,我们需要先获取锚点元素:找到 newVNode 的前一个虚拟节点,即 preVNode,如果存在,则使用它对应的真实 DOM 的下一个兄弟节点作为锚点元素;如果不存在,则说明即将挂载的 newVNode 节点是容器元素的第一个子节点,此时应该使用容器元素的 container.firstChild 作为锚点元素。最后,将锚点元素 anchor 作为 patch 函数的第四个参数,调用 patch 函数完成节点的挂载。

function patch (n1, n2, container, anchor) {
  // ...
  if (typeof type === 'string') {
    if (!n1) {
      // 挂载时将锚点元素作为第三个参数传递给 mountElement 函数
      mountElement(n2, container, anchor)
    } else {
      patchElement(n1, n2)
    }
  } else if (type === Text) {
    // ...
  } else if (type === Fragment) {
    // ...
  }
}

function mountElement (vnode, container, anchor) {
  // ...

  // 插入节点时,将锚点元素透传给 insert 函数
  insert(el, container, anchor)
}
js

移动不存在的元素

在更新子节点时,不仅会遇到新增元素,还会出现元素被删除的情况。

simple_diff13.png

在新的一组节点中,节点 p-2 已经不存在了,这说明该节点被删除了。渲染器应该能找到那些需要删除的节点并正确地将其删除。

首先我们来讨论如何找到需要删除的节点。

simple_diff14.png

现在我们开始模拟执行更新的过程。

  • 第一步:取新的一组子节点中的第一个节点 p-3,它的 key 值为 3。尝试在旧的一组子节点中寻找可复用的节点。发现能够找到,并且该节点在旧的一组子节点中的索引值为 2 。此时变量 lastIndex 的值 为 0,索引 2 不小于 lastIndex 的值 0,所以节点 p-3 对应的真实 DOM 不需要移动,但需要更新变量 lastIndex 的值为 2。
  • 第二步:取新的一组子节点中的第一个节点 p-1,它的 key 值为 1。尝试在旧的一组子节点中寻找可复用的节点。发现能够找到,并且该节点在旧的一组子节点中的索引值为 0 。此时变量 lastIndex 的值 为 2,索引 0 小于 lastIndex 的值 2,所以节点 p-1 对应的真实 DOM 需要移动,并且应该移动到节点 p-3 对应的真实 DOM 后面。经过这一步的移动操作后,真实 DOM 的状态如下:

simple_diff15.png

至此,更新结束。不过我们会发现,节点 p-2 对应的真实 DOM 仍然存在,所以需要增加额外的逻辑来删除遗留节点。思路很简单,当基本的更新结束时,我们需要遍历旧的一组子节点,然后取新的一组子结点中寻找具有相同 key 值得节点。如果找不到,则说明应该删除该节点。

function patchChildren (n1, n2, container) {
  if (typeof n2.children === 'string') {
    // ...
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    const oldLen = oldChildren.length
    const newLen = newChildren.length

    // 存储寻找过程中遇到的最大索引值
    let lastIndex = 0
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      let j = 0;

      // 第一层循环中定义变量 find,代表是否在旧的一组子节点中找到可复用的节点,
      // 初始值为 false,代表没找到
      let find = false

      for (j; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]

        // 如果找到具有相同 key 值的节点,说明可以复用,但是仍需要调用 patch 函数更新
        if (newVNode.key === oldVNode.key) {
          // 找到可复用的节点,将变量 find 的值设置为 true
          find = true

          patch(oldVNode, newVNode, container)

          if (j < lastIndex) {
            // 如果当前找到的节点在旧 children 中的索引小于最大索引值 lastIndex
            // 说明该节点对应的真实 DOM 需要移动
            // 获取 newVNode 的前一个 vnode,即 prevVNode
            const prevVNode = newChildren[i - 1]
            // 如果 prevVnode 不存在,说明当前 newVNode 是第一个节点,不需要移动
            if (prevVNode) {
              // 由于我们要将 newVNode 对应的真实 DOM 移动到 prevVNode 所对应真实 DOM 后面
              // 所以我们需要获取 prevVNode 所对应真实 DOM 的下一个兄弟节点,并将其作为锚点
              const anchor = prevVNode.el.nextSibling
              // 调用 insert 方法将 newVNode 对应的真实 DOM 插入到锚点元素前面
              // 也就是 prevVNode 对应的真实 DOM 后面
              insert(newVNode.el, container, anchor)
            }
          } else {
            // 如果当前找到的节点在旧 children 中的索引小于最大索引值
            // 则更新 lastIndex 的值
            lastIndex = j
          }
          break;
        }
      }

      // 如果代码运行到这里,find 仍然是 false
      // 说明当前 newVNode 没有在旧的一组子节点中找到可复用的节点
      // 也就是说,当前 newVNode 是新增节点,需要挂载
      if (!find) {
        // 为了将节点挂载到正确位置,我们需要先获取锚点元素
        // 首先获取当前 newVNode 的前一个 vnode 节点
        const parentVNode = newChildren[i - 1]
        
        let anchor = null

        if (prevVNode) {
          // 如果存在前一个 vnode 节点,则使用它的下一个兄弟节点作为锚点元素
          anchor = prevVNode.el.nextSibling
        } else {
          // 如果没有前一个 vnode 节点,说明即将挂载的新节点是第一个子节点
          // 这时我们使用容器元素的 fristChild 作为锚点
          anchor = container.firstChild
        }

        // 挂载 newVNode
        patch(null, newVNode, container, anchor)
      }
    }

    // 上一步得更新操作完成后
    // 遍历旧的一组子节点
    for (let i = 0; i < oldChildren.length; i++) {
      const oldVNode = oldChildren[i]
      // 拿旧子节点 oldVNode 去新的一组子节点中寻找具有相同 key 值得节点
      const has = newChildren.find(vnode => vnode.key === oldVNode.key)
      if (!has) {
        // 如果没有找到具有相同 key 值得节点,则说明需要删除该节点
        // 调用 unmount 函数将其卸载
        unmount(oldVNode)
      }
    }
  } else {
    // ...
  }
}
js

如以上代码注释所示,在上一步得更新操作完成后,我们还需要遍历旧得一组子节点,目的是检查旧子节点在新的一组子节点中是否仍然存在,如果已经不存在,则调用 unmount 函数将其卸载。

总结

本篇文章,我们首先讨论了 Diff 算法的作用。Diff 算法用来计算两组子节点的差异,并试图最大程度地复用 DOM 元素。通过遍历新旧两组子节点中数量多的那一组,逐个调用 patch 函数进行打补丁,然后比较新旧两组子节点的数量,如果新的一组子节点数量更多,说明新子节点需要挂载。否则说明在旧的一组子节点中,有节点需要卸载。

然后,我们讨论子虚拟节点中 key 属性的作用。在更新时,渲染器通过 key 属性找到可复用的节点,然后尽可能地通过 DOM 移动操作来完成更新,避免过多地对 DOM 元素进行销毁和重建。

接着,我们讨论了简单 Diff 算法时如何寻找要移动的节点的。简单 Diff 算法的核心逻辑时,拿新的一组子节点中的节点去旧的一组子节点中寻找可复用的节点。如果找到,则记录该节点的位置索引。然后我们把逐个位置索引称为最大索引。在整个更新过程中,如果一个节点的索引值小于最大索引,则说明该节点对应的真实 DOM 元素需要移动。

最后,我们通过几个例子讲解了渲染器是如何移动、添加、删除虚拟节点所对应的 DOM 元素的。