Vue设计与实现：简单 Diff 算法

减少 DOM 操作的性能开销

现有的dom替换操作是卸载全部旧子节点，再挂载全部新子节点，由于没有复用任何 DOM 元素，所以会产生极大的性能开销

仅更新文本子节点

新旧vnode的children的数量、type相同，只有文本不一样

// 旧 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' }
  ]
}

解决思路：

新旧vnode的children的type都是p标签，只有children的文本不同，直接更新这个 p 标签的文本节点的内容，只需要 3 次 DOM 操作就可以完成全部节点 的更新。相比原来需要执行 6 次 DOM 操作才能完成更新的方式，其性能提升了一倍

1. 获取到新旧 children

function patchChildren(oldN, newN, container) {
    if (typeof newN.children === 'string') {
      // 省略部分代码
    } else if (Array.isArray(newN.children)) {
+      // 重新实现两组子节点的更新方式
+      // 新旧 children
+      const oldChildren = oldN.children
+      const newChildren = newN.children
+      // 遍历旧的 children
+      for (let i = 0; i < oldChildren.length; i++) {
+        // 调用 patch 函数逐个更新子节点
+        patch(oldChildren[i], newChildren[i])
+      }
    } else {
      // 省略部分代码
    }
  }

结果：

挂载、卸载子节点

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

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

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

// 旧 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' },
  ]
}

解决思路：

1. 获取到oldChildren、newChildren的length，通过比较得到最短的length也是两组子节点的公共长度
2. 先遍历公共长度调用 patch 函数逐个更新子节点
3. 如果 newLen > oldLen，说明有新子节点需要挂载，从commonLength开始遍历调用 patch 函数根据新子节点的type（普通标签节点、文本节点、注释节点）进行对应的操作
4. 如果 oldLen > newLen，说明有旧子节点需要卸载，调用unmount对应旧子节点

function patchChildren(oldN, newN, container) {
    if (typeof newN.children === 'string') {
      // 省略部分代码
    } else if (Array.isArray(newN.children)) {
      // 重新实现两组子节点的更新方式
      // 新旧 children
      const oldChildren = oldN.children
      const newChildren = newN.children
+     // 旧的一组子节点的长度
+     const oldLen = oldChildren.length
+     // 新的一组子节点的长度
+     const newLen = newChildren.length
+     // 两组子节点的公共长度，即两者中较短的那一组子节点的长度
+     const commonLength = Math.min(oldLen, newLen)
      // 遍历旧的 children
-      for (let i = 0; i < oldChildren.length; i++) {
+      for (let i = 0; i < commonLength; i++) {
        // 调用 patch 函数逐个更新子节点
        patch(oldChildren[i], newChildren[i])
      }
+     // 如果 newLen > oldLen，说明有新子节点需要挂载
+     if (newLen > oldLen) {
+       for (let i = commonLength; i < newLen; i++) {
+         // 调用 patch 函数逐个更新子节点
+         patch(null, newChildren[i], container)
+       }
+     } else if (oldLen > newLen) { // 如果 oldLen > newLen，说明有旧子节点需要卸载
+       for (let i = commonLength; i < oldLen; i++) {
+         // 卸载对应旧子节点
+         unmount(oldChildren[i])
+       } 
+     }
    } else {
      // 省略部分代码
    }
  }

结果：

DOM 复用与 key 的作用

key作为 vnode 的标识

新旧vnode的type都一样无法确定新旧两组子节点中节点的对应关系，也就无法得知应该进行怎样的 DOM 移动才能完成更新

// 旧 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: '3' },
    { type: 'p', children: '1' },
    { type: 'p', children: '2' }
  ]
}

需要引入额外的 key 来作为 vnode 的标识

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

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

解决思路：

1. 外层循环用于遍历新的一组子节点，内层循环则遍历旧的一组子节点。在内层循环中，逐个对比新旧子节点的 key 值，试图在旧的子节点中找到可复用的节点
2. 通过patch来判断oldVNode、newVNode的差异并更新
3. 找到相同的key就停止遍历

function patchChildren(oldN, newN, container) {
  if (typeof newN.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(newN.children)) {
    const oldChildren = oldN.children
    const newChildren = newN.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 {
    // 省略部分代码
  }
}

结果：

找到需要移动的元素

1. 新子节点第一个节点p-3，key为3，对应旧子节点的索引为2
2. 新子节点第二个节点p-1，key为1，对应旧子节点的索引为0，小于新节点p-3在旧子节点的索引2，索引p-1需要移动
3. 新子节点第二个节点p-2，key为2，对应旧子节点的索引为1，小于新节点p-3在旧子节点的索引2，索引p-2需要移动

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

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

解决思路：

p-3 在旧子节点中的索引定义为遇到的最大索引值，寻找的过程中，存在索引值比当前遇到的最大索引值还要小的节点，则意味着该节点需要移动

1. 如果新旧节点的 key 值相同,说明找到可复用的节点
2. 如果j小于lastIndex，说明当前旧子节点对应的真实 DOM 需要移动
3. 否则说明不需要移动，将变量j的值赋给变量lastIndex

function patchChildren(oldN, newN, container) {
  if (typeof newN.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(newN.children)) {
    const oldChildren = oldN.children
    const newChildren = newN.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 // 这里需要 break
        }
      }
    }

  } else {
    // 省略部分代码
  }
}

如何移动元素

获取当前新vnode的前一个vnode，然后使用 insert 函数完成节点的移动

解决思路：

1. p-3对应的旧子节点索引为2 > lastIndex（0）所以不需要移动，lastIndex替换成2
2. p-1对应的旧子节点索引为0 < lastIndex（2）,说明p-1是要移动的，通过newChildren[i - 1]拿到前一个vnode也就是prevVNode，如果能拿到就说明不是第一个节点，拿不到就说明是第一个节点则不需要更新
3. p-1在新子节点的前一个vnode也就是p-3，拿到p-3所对应真实 DOM 的下一个兄弟节点，并将其作为锚点，调用 insert 方法将p-1对应的真实 DOM 插入到锚点元素前面

function patchChildren(oldN, newN, container) {
    if (typeof newN.children === 'string') {
      // 省略部分代码
    } else if (Array.isArray(newN.children)) {
      const oldChildren = oldN.children
      const newChildren = newN.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 oldVNode = {
  type: 'div',
  children: [
    { type: 'p', children: '1', key: 1 },
    { type: 'p', children: '2', key: 2 },
    { type: 'p', children: '3', key: 3 }
  ]
}

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

解决思路：

1. 定义一个能否在旧的一组子节点中找到可复用的节点的变量find
2. 在旧子节点循环中，如果找到一样的key就把find设置为true代表找到可复用的节点
3. 在结束旧子节点循环find还是为false，说明旧子节点中没有可复用的节点，代表是新增节点
4. 获取当前新子节点的前一个vnode也就是prevVNode，判断prevVNode是否存在
5. 拿到prevVNode对应真实 DOM 的下一个兄弟节点作为锚点元素
6. 如果prevVNode不存在就说明是第一个节点，通过container.firstChild拿到container的第一个子节点作为锚点元素
7. 因为是新增节点所以需要调用patch

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

    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]
        if (newVNode.key === oldVNode.key) {
          // 一旦找到可复用的节点，则将变量 find 的值设为 true
          find = 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
        }
      }
+      // 如果代码运行到这里，find 仍然为 false，
+      // 说明当前 newVNode 没有在旧的一组子节点中找到可复用的节点
+      // 也就是说，当前 newVNode 是新增节点，需要挂载
+      if (!find) {
+        // 为了将节点挂载到正确位置，我们需要先获取锚点元素
+        // 首先获取当前 newVNode 的前一个 vnode 节点
+        const prevVNode = newChildren[i - 1]
+        let anchor = null
+        if (prevVNode) {
+          // 如果有前一个 vnode 节点，则使用它的下一个兄弟节点作为锚点元素
+          anchor = prevVNode.el.nextSibling
+        } else {
+          // 如果没有前一个 vnode 节点，说明即将挂载的新节点是第一个子节点
+          // 这时我们使用容器元素的 firstChild 作为锚点
+          anchor = container.firstChild
+        }
+        // 挂载 newVNode
+        patch(null, newVNode, container, anchor)
+      }
    }

  } else {
    // 省略部分代码
  }
}

patch、mountElement增加anchor参数，以便传递到insert中

  // patch 函数需要接收第四个参数，即锚点元素
-  function patch(oldN, newN, container) {
+  function patch(oldN, newN, container, anchor) {
    // 省略部分代码

    if (typeof type === 'string') {
      if (!oldN) {
        // 挂载时将锚点元素作为第三个参数传递给 mountElement 函数
-        mountElement(newN, container)
+        mountElement(newN, container, anchor)
      } else {
        patchElement(oldN, newN)
      }
    } else if (type === Text) {
      // 省略部分代码
    } else if (type === Fragment) {
      // 省略部分代码
    }
  }

  // mountElement 函数需要增加第三个参数，即锚点元素
-  function mountElement(vnode, container) {
+  function mountElement(vnode, container, anchor) {
    // 省略部分代码

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

结果：

移除不存在的元素

找到旧子节点不存在于新子节点中相同key的节点，卸载该节点

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

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

解决思路：

1. 遍历完新子节点后，旧子节点还没有完全遍历完，需要再遍历一次旧子节点
2. 在遍历旧子节点中拿到当前遍历的旧子节点跟新子节点判断是否有相同key的节点
3. 如果该旧子节点没有在新子节点中有相同key的节点，调用unmount卸载该节点

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

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

      // 上一步的更新操作完成后
+      // 遍历旧的一组子节点
+      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 {
      // 省略部分代码
    }
  }

结果：