web全栈体系

外观

目录

当 新旧 vnode 的子节点都是一组节点时，为了以最小的性能开销完成更新操作，需要比较两组子节点，用于比较的算法就叫作 Diff 算法。

9.1 减少 DOM 操作的性能开销 ​

之前我们在更新子节点时，简单地移除所有旧的子节点，然后添加所有新的子节点。 这种方式虽然简单直接，但会产生大量的性能开销，因为它没有复用任何 DOM 元素。 考虑下面的新旧虚拟节点示例：

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

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

上述代码，我们会执行六次操作，三次卸载旧节点，三次添加新节点，但实际上，旧新节点都是 'p' 标签，只是它们的文本内容变了。 理想情况下，我们只需要更新这些 'p' 标签的文本内容就可以了，这样只需要 3 次 DOM 操作，性能提升了一倍。 我们可以调整 patchChildren 函数，让它只更新变化的部分：

javascript
function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children;
    const newChildren = n2.children;

    // 遍历旧的 children
    for (let i = 0; i < oldChildren.length; i++) {
      // 调用 patch 函数逐个更新子节点
      patch(oldChildren[i], newChildren[i]);
    }
  } else {
    // 省略部分代码
  }
}

上述代码，patch 函数在执行更新时，发现新旧子节点只有文本内容不同，因此只会更新其文本节点的内容 image.png 但是这段代码假设新旧子节点的数量总是一样的，实际上新旧节点的数量可能发生变化，如果新节点较多，我们应该添加节点，反之则删除节点。 所以，我们应遍历长度较短的那组子节点，以便尽可能多地调用 patch 函数进行更新。然后，比较新旧子节点组的长度，如果新组长度更长，就挂载新子节点；反之，就卸载旧子节点：

javascript
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], container);
    }
    
    // 如果新子节点比旧子节点多，挂载新增的子节点
    if (newLen > oldLen) {
      for (let i = commonLength; i < newLen; i++) {
        patch(null, newChildren[i], container);
      }
    } else if (oldLen > newLen) { // 如果旧子节点比新子节点多，卸载多余的旧子节点
      for (let i = commonLength; i < oldLen; i++) {
        unmount(oldChildren[i]);
      }
    }
  } else {
    // 省略部分代码
  }
}

这样，无论新旧子节点组的数量如何，我们的渲染器都能正确地挂载或卸载它们。

9.2 DOM 复用与 key 的作用 ​

上面我们通过减少操作次数提高了性能，但仍有优化空间。 以新旧两组子节点为例，它们的内容如下：

javascript
// oldChildren
[
  { type: 'p' },
  { type: 'div' },
  { type: 'span' }
]

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

若使用之前的算法更新子节点，需要执行6次 DOM 操作。观察新旧子节点，发现它们只是顺序不同。 因此，最优处理方式是通过 DOM 移动来完成更新，而非频繁卸载和挂载。为实现这一目标，需确保新旧子节点中存在可复用节点。 为判断新子节点是否在旧子节点中出现，可以引入 key 属性作为虚拟节点的标识。只要两个虚拟节点的 type 和 key 属性相同，我们认为它们相同，可以复用DOM。例如： image.png

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

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

我们根据子节点的 key 属性，能够明确知道新子节点在旧子节点中的位置，这样就可以进行相应的 DOM 移动操作了。 注意 DOM 可复用并不意味着不需要更新，它可能内部子节点不一样：

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

所以补丁操作是在移动 DOM 元素之前必须完成的步骤，如下面的 patchChildren 函数所示：

javascript
function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children
    // 遍历新的 children
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      // 遍历旧的 children
      for (let j = 0; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]
        // 如果找到了具有相同 key 值的两个节点，说明可以复用，但仍然需要调用 patch 函数更新
        if (newVNode.key === oldVNode.key) {
          patch(oldVNode, newVNode, container)
          break // 这里需要 break
        }
      }
    }
  } else {
    // 省略部分代码
  }
}

在这段代码中，我们更新了新旧两组子节点。通过两层 for 循环，外层遍历新的子节点，内层遍历旧的子节点，我们寻找并更新了所有可复用的节点。 例如，有如下的新旧两组子节点：

javascript
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.render(oldVNode, document.querySelector('#app'))
setTimeout(() => {
  // 1 秒钟后更新
  renderer.render(newVNode, document.querySelector('#app'))
}, 1000);

运行上述代码，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 顺序的更新。

9.3 找到需要移动的元素 ​

现在，我们已经能够通过 key 值找到可复用的节点了。 下一步，我们确定哪些节点需要移动以及如何移动。我们逆向思考下，什么条件下节点无需移动。答案直观：新旧子节点顺序未变时，无需额外操作： image.png 新旧子节点顺序未变，举例说明旧子节点索引：

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

应用我们的更新算法，我们会发现每次寻找可复用节点时，我们记录了节点在旧子节点数组中的位置索引。 如果这些位置索引按照顺序排列，则可得到一个递增序列：0、1、2。在这种情况下，不需要移动任何节点。 我们再来看看另外一个例子： image.png

  1. 新子节点的第一个节点 p-3 的 key 为 3，在旧子节点中找到同 key 的节点，其在旧子节点中的索引为 2。
  2. 接着，新子节点的第二个节点 p-1 的 key 为 1，在旧子节点中找到同 key 的节点，其在旧子节点中的索引为 0。此时，索引值递增的顺序被打破了，节点 p-1 在旧子节点中的索引（0）小于节点 p-3 的索引（2），说明节点 p-1 在新子节点中排在 p-3 后，因此，节点 p-1 需要移动。
  3. 新子节点的第三个节点 p-2 的 key 为 2，在旧子节点中找到同 key 的节点，其在旧子节点中的索引为 1。此时，节点 p-2 在旧子节点中的索引（1）小于节点 p-3 的索引（2），说明节点 p-2 在新子节点中排在 p-3 后，因此，节点 p-2 也需要移动。

通过以上分析，新的子节点序列为：key 为 3 的节点（索引 2）、key 为 1 的节点（索引 0）、key 为 2 的节点（索引 1）。在这种情况下，我们可以看到索引序列：2、0、1，它并非递增序列，这表明了有节点需要移动。 基于这个思路，我们可以定义一个名为 lastIndex 的变量来存储在寻找过程中遇到的最大索引值。如果后续寻找过程中存在索引值小于 lastIndex 的节点，那么这个节点就需要移动。以下是这个策略的代码实现：

javascript
function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    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]
        if (newVNode.key === oldVNode.key) {
          patch(oldVNode, newVNode, container)
          if (j < lastIndex) {
            // 如果当前找到的节点在旧 children 中的索引小于最大索引值 lastIndex，
            // 说明该节点对应的真实 DOM 需要移动
          } else {
            // 如果当前找到的节点在旧 children 中的索引不小于最大索引值，
            // 则更新 lastIndex 的值
            lastIndex = j
          }
          break
        }
      }
    }
  } else {
    // 省略部分代码
  }
}

上述代码，如果新旧节点的 key 值相同，我们就找到了可以复用的节点。我们比较这个节点在旧子节点数组中的索引 j 与 lastIndex。 如果 j 小于 lastIndex，说明当前 oldVNode 对应的真实 DOM 需要移动； 否则，不需要移动。并将变量 j 的值赋给 lastIndex，以确保寻找节点过程中，变量 lastIndex 始终存储着当前遇到的最大索引值。

9.4 如何移动元素 ​

移动节点指的是，移动一个虚拟节点所对应的真实 DOM 节点，并不是移动虚拟节点本身。 既然移动的是真实 DOM 节点，那么就需要取得对它的引用才行。当一个虚拟节点被挂载后，其对应的真实 DOM 节点会存储在它的 vnode.el 属性中： image.png 因此，我们可以通过 vnode.el 属性取得它对应的真实 DOM 节点。

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

javascript
function patchElement(n1, n2) {
  // 新的 vnode 也引用了真实 DOM 元素
  const el = n2.el = n1.el
  // 省略部分代码
}

上述代码 patchElement 函数首先将旧节点的 n1.el 属性赋值给新节点的 n2.el 属性，这个赋值的意义其实就是 DOM 元素的复用。 在复用了 DOM 元素之后，新节点也将持有对真实 DOM 的引用： image.png 此时无论是新旧节点，都引用着真实 DOM，在此基础上，我们就可以进行 DOM 移动了。

为了阐述如何移动 DOM，，我们仍然引用上一节的更新案例： image.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 需要移动。此时我们知道，新 children 的顺序即为更新后实际 DOM 应有的顺序。因此，p-1 在新 children 中的位置决定了其在更新后实际 DOM 中的位置。由于 p-1 在新 children 中排在 p-3 后面，因此我们需要将 p-1 的实际 DOM 移动到 p-3 的实际 DOM 后面。移动后的实际 DOM 顺序为 p-2、p-3、p-1：
  • image.png把节点 p-1 对应的真实 DOM 移动到节点 p-3 对应的真实 DOM 后面
  • 第三步：选取新集合中的第三个节点 p-2（key 为 2），并尝试在旧集合中找到相同 key 的可复用节点。找到了这样的节点，其在旧集合中的索引为1。此时，由于 lastIndex 为 2，且 1 小于 2，所以，p-2 的实际 DOM 需要移动。此步骤与步骤二类似，我们需要将 p-2 的实际 DOM 移动到 p-1 的实际 DOM 后面。经过移动后，实际 DOM 的顺序与新的子节点集合的顺序相同，即为：p-3、p-1、p-2。至此，更新操作完成：
  • image.png把节点 p-2 对应的真实 DOM 移动到节点 p-1 对应的真实 DOM 后面

接下来，我们来看一下如何实现这个过程。具体的代码如下：

javascript
function patchChildren(n1, n2, container) {
	if (typeof n2.children === 'string') {
		// 省略部分代码
	} else if (Array.isArray(n2.children)) {
		const oldChildren = n1.children
		const newChildren = n2.children

		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]

				if (newVNode.key === oldVNode.key) {
					patch(oldVNode, newVNode, container)
					if (j < lastIndex) {
						// 如果满足这个条件，说明 newVNode 对应的真实 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 {
						lastIndex = j
					}
					break
				}
			}
		}
	} else {
		// 省略部分代码
	}
}

const renderer = createRenderer({
	// 省略部分代码
	insert(el, parent, anchor = null) {
		// insertBefore 需要锚点元素 anchor
		parent.insertBefore(el, anchor)
	},
	// 省略部分代码
})

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

9.5 添加新元素 ​

image.png 上图，我们有一个新的节点p-4， 它的 key 值为 4，这个节点在旧的节点集中不存在。该新增节点我们应该挂载：

  1. 找到新节点
  2. 将新节点挂载到正确位置

image.png 根据上图，我们开始模拟执行简单 Diff 算法的更新逻辑：

  • 第一步：我们首先检查新的节点集中的第一个节点 p-3。这个节点在旧的节点集中存在，因此我们不需要移动对应的 DOM 元素，但是我们需要将变量lastIndex的值更新为 2。
  • 第二步：接着，我们查看新的节点集中的第二个节点 p-1。在旧的节点集中，这个节点的索引值为 0，这个值小于 lastIndex 的值 2，因此我们需要移动 p-1 对应的DOM元素。移动后，DOM 的顺序将变为 p-2、p-3、p-1：
  • image.png
  • 第三步：我们现在查看新的节点集中的第三个节点 p-4。在旧的节点集中，我们找不到这个节点，因此我们将其视为新节点并将其挂载到 p-1 对应的DOM 元素后面。挂载后，DOM的顺序将变为 p-2、p-3、p-1、p-4：
  • image.png
  • 第四步：最后，我们查看新的节点集中的第四个节点 p-2。在旧的节点集中，这个节点的索引值为 1，这个值小于 lastIndex 的值 2，因此我们需要移动 p-2 对应的 DOM 元素。移动后，DOM的顺序将变为 p-3、p-1、p-4、p-2：
  • image.png

在此，我们看到真实 DOM 的顺序为：p-3、p-1、p-4、p-2。这表明真实 DOM 的顺序已经与新子节点的顺序一致，更新已经完成。 接下来，让我们通过 patchChildren 函数的代码实现来详细讲解：

javascript
function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    let lastIndex = 0
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      let j = 0
      let find = false // 初始设为 false，代表没找到可复用的节点
      for (j; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]
        if (newVNode.key === oldVNode.key) {
          find = true // 找到可复用的节点，设为 true
          patch(oldVNode, newVNode, container)
          if (j < lastIndex) {
            const prevVNode = newChildren[i - 1]
            if (prevVNode) {
              const anchor = prevVNode.el.nextSibling
              insert(newVNode.el, container, anchor)
            }
          } else {
            lastIndex = j
          }
          break
        }
      }
      if (!find) { // 如果没有找到可复用的节点，说明是新增节点，需要挂载
        const prevVNode = newChildren[i - 1]
        let anchor = prevVNode ? prevVNode.el.nextSibling : container.firstChild
        patch(null, newVNode, container, anchor) // 挂载新的VNode
      }
    }
  } else {
    // 省略部分代码
  }
}

上述代码，我们通过外层循环中定义的变量 find，查找是否存在可复用的节点。 如果内层循环结束后，find 的值仍为 false，说明当前 newVNode 是全新的节点，需要进行挂载。 挂载的位置由 anchor 确定，这个 anchor 可以是 newVNode 的前一个虚拟节点的下一个兄弟节点，或者容器元素的第一个子节点。 现在，我们需要调整 patch 函数以支持接收第四个参数 anchor，如下所示：

javascript
function patch(n1, n2, container, anchor) {
  // 省略部分代码
  if (typeof type === 'string') {
    if (!n1) {
      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)
}

9.6 移除不存在的元素 ​

在更新子节点时，不仅会遇到新增元素，还会出现元素被删除的情况： image.png 假设在新的子节点组中，节点 p-2 已经不存在，这说明该节点被删除了。

我们像上面一样模拟执行更新逻辑，这之前我们先看看新旧两组子节点以及真实 DOM 节点的当前状态： image.png

  • 第一步：取新的子节点组中的第一个节点 p-3，它的 key 值为 3。在旧的子节点组中寻找可复用的节点，发现索引为 2 的节点可复用，此时变量 lastIndex 的值为 0，索引 2 不小于 lastIndex 的值 0，所以 节点 p-3 对应的真实 DOM 不需要移动，但需要更新变量 lastIndex 的值为 2。
  • 第二步，取新的子节点组中的第二个节点 p-1，它的 key 值为 1。在旧的子节点组中发现索引为 0 的节点可复用。 并且该节点在旧的一组子节点中的索引值为 0。此时变量 lastIndex 的值为 2，索引 0 小于 lastIndex 的值 2，所以节 点 p-1 对应的真实 DOM 需要移动，并且应该移动到节点 p-3 对 应的真实 DOM 后面：
  • image.png
  • 最后，我们发现节点 p-2 对应的真实 DOM 仍然存在，所以需要增加逻辑来删除遗留节点。

我们可以在基本更新结束后，遍历旧的子节点组，然后去新的子节点组中寻找具有相同 key 值的节点。如果找不到，说明应删除该节点，如下面 patchChildren 函数的代码所示：

javascript
function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    let lastIndex = 0
    for (let i = 0; i < newChildren.length; i++) {
      // 省略部分代码
    }

    // 基本更新结束后，遍历旧的子节点组
    for (let i = 0; i < oldChildren.length; i++) {
      const oldVNode = oldChildren[i]
      // 在新的子节点组中寻找具有相同 key 值的节点
      const has = newChildren.find(
        vnode => vnode.key === oldVNode.key
      )
      // 如果没有找到，则说明需要删除该节点，调用 unmount 函数进行卸载
      if (!has) {
        unmount(oldVNode)
      }
    }
  } else {
    // 省略部分代码
  }
}

9.7 总结 ​

本章我们讨论 Diff 算法的作用，Diff 是用来计算两组子节点的差异，并最大程度复用 DOM 元素。 最开始我们采用了一种简单的方式来更新子节点，即卸载所有旧子节点，再挂载所有新子节点。然而这种操作无疑是非常消耗性能的。 于是我们改进为：遍历新旧两组子节点中数量较少的那一组，并逐个调用 patch 函数进行打补丁，然后比较新旧两组子节点的数量，如果新的一组子节点数量更多，说明有新子节点需要挂载；否则说明在旧的一组子节点中，有节点需要卸载。 然后我们讨论了 key 值作用，，它就像虚拟节点 的“身份证号”。渲染器通过 key 找到可复用元素，避免对 DOM 元素过多的销毁重建。 接着我们讨论了简单 Diff 逻辑：在新的一组节点中去寻找旧节点可复用的元素。如果找到了，则记录该节点的位置索引。我们把这个位置索引称为最大索引。在整个更新过程中，如果一个节点的索引值小于最大索引，则说明该节点对应的真实 DOM 元素需要移动。 最后，我们讲解了渲染器是如何移动、添加、删除 虚拟节点所对应的 DOM 元素的。

May all encounters not be in vain