《Vue.js 技术与实现》第9章简单 diff 阅读总结

上一章已经基本实现了一个渲染器了，但遗留了一个问题：一组节点和一组节点如何更新？

上一章其实已经给出了解决方案：暴力循环，先将旧节点全部 unmount，再将新节点全部 mount

但这看上去并不优雅

那么，如何解决一组旧节点和一组新节点的比对方案呢？这看上去似乎是个比较复杂的问题

针对旧节点的子节点和新节点的子节点数量不一的情况，给出如下方案：

取出新旧子节点长度的最小值，Math.min(oldLen, newLen)
循环公共长度，进行 patch 更新
如果新的子节点长度大于旧的子节点长度，说明有新增，则挂载 patch 更新
如果新的子节点长度小于旧的子节点长度，说明有删除，则卸载 patch 更新

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    if (Array.isArray(n1.children)) {
      n1.children.forEach((c) => unmount(c))
    }
    setElementText(container, n2.children)
  } 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])
    }
    // 如果 nextLen > prevLen，将多出来的元素添加
    if (newLen > oldLen) {
      for (let i = commonLength; i < newLen; i++) {
        patch(null, newChildren[i], container)
      }
    } else if (oldLen > newLen) {
      // 如果 prevLen > nextLen，将多出来的元素移除
      for (let i = commonLength; i < oldLen; i++) {
        unmount(oldChildren[i])
      }
    }
  } else {
    if (Array.isArray(n1.children)) {
      n1.children.forEach(c => unmount(c))
    } else if (typeof n1.children === 'string') {
      setElementText(container, '')
    }
  }
}

上述代码看上去已经比较完善了，但是还存在问题，比方说，节点标签没有变化，只有顺序和内容变化，针对这种问题，为了能够进行 DOM 复用，我们给节点添加 key，如下

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 }
  ]
}

在针对新旧节点比对是就可以使用 key 进行判断

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]
    let j = 0
    // 遍历旧的 children
    for (j; j < oldChildren.length; j++) {
      const oldVNode = oldChildren[j]
      // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新之
      if (newVNode.key === oldVNode.key) {
        patch(oldVNode, newVNode, container)
        break // 这里需要 break
      }
    }
  }
}

针对内容变化的节点我们可以直接使用 patch 就能处理，针对顺序变化的，需要考虑哪些顺序是变化（换言之哪些节点需要移动），并且又该如何移动呢？

接下来处理 key 相同但是节点顺序变化的问题，如下

定义 lastIndex，取第一个新的子节点在旧的子节点的下标作为 lastIndex
如果后续遍历，旧的里面找新的找到的下标小于这个 lastIndex，说明需要移动该节点

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]
    let j = 0
    // 遍历旧的 children
    for (j; j < oldChildren.length; j++) {
      const oldVNode = oldChildren[j]
      // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新之
      if (newVNode.key === oldVNode.key) {
        patch(oldVNode, newVNode, container)
        if (j < lastIndex) {
          // 需要移动
        } else {
          // 更新 lastIndex
          lastIndex = j
        }
        break // 这里需要 break
      }
    }
  }

}

因为外层循环在遍历新的子节点，第一个新的子节点肯定是不需要移动的，如果找出第二个新子节点在旧字节点的位置小于第一个新子节点在旧子节点的位置，说明第二个子节点顺序乱了，需要调整。因为新子节点顺序是从0 到 length 开始遍历的，如果新旧子节点顺序没有变化，新子节点在旧字节点的顺序，下标应该是递增的。如果不是，说明需要移动

需要移动的节点如何移动呢？

解决方案：挂载在上一个新节点对应真实 DOM 的后面。为什么这么做？因为上一个新子节点的 DOM 是排好序的（以第 0 个下标的新子节点为基准）

if (Array.isArray(n2.children)) {
  const oldChildren = n1.children
  const newChildren = n2.children

  let lastIndex = 0
  // 遍历新的 children
  for (let i = 0; i < newChildren.length; i++) {
    const newVNode = newChildren[i]
    let j = 0
    // 遍历旧的 children
    for (j; j < oldChildren.length; j++) {
      const oldVNode = oldChildren[j]
      // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新之
      if (newVNode.key === oldVNode.key) {
        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
          lastIndex = j
        }
        break // 这里需要 break
      }
    }
  }
  
}

接下来，还需要处理新增子节点的情况，即新子节点在旧子节点中找不到的情况

新增节点挂载过程，需要找一个锚点 anchor，anchor 设置为上一个新子节点 DOM 的下一个兄弟节点，如果没有上一个新子节点，那就说明是第一个节点，直接放在 container.firstChild 前面即可

if (Array.isArray(n2.children)) {
  const oldChildren = n1.children
  const newChildren = n2.children

  let lastIndex = 0
  // 遍历新的 children
  for (let i = 0; i < newChildren.length; i++) {
    const newVNode = newChildren[i]
    let j = 0
    let find = false
    // 遍历旧的 children
    for (j; j < oldChildren.length; j++) {
      const oldVNode = oldChildren[j]
      // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新之
      if (newVNode.key === oldVNode.key) {
        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
          lastIndex = j
        }
        break // 这里需要 break
      }
    }
    if (!find) {
      const prevVNode = newChildren[i - 1]
      let anchor = null
      if (prevVNode) {
        anchor = prevVNode.el.nextSibling
      } else {
				// 说明是第一个
        anchor = container.firstChild
      }
      patch(null, newVNode, container, anchor)
    }
  }
  
}

处理了新增节点的挂载，还要处理删除节点的卸载

// 遍历旧的节点
for (let i = 0; i < oldChildren.length; i++) {
  const oldVNode = oldChildren[i]
  // 拿着旧 VNode 去新 children 中寻找相同的节点
  const has = newChildren.find(
    vnode => vnode.key === oldVNode.key
  )
  if (!has) {
    // 如果没有找到相同的节点，则移除
    unmount(oldVNode)
  }
}

本章主要处理一组子节点与一组子节点的更新，整体代码如下：

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    if (Array.isArray(n1.children)) {
      n1.children.forEach((c) => unmount(c))
    }
    setElementText(container, n2.children)
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    let lastIndex = 0
    // 遍历新的 children
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      let j = 0
      let find = false
      // 遍历旧的 children
      for (j; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]
        // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新之
        if (newVNode.key === oldVNode.key) {
          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
            lastIndex = j
          }
          break // 这里需要 break
        }
      }
      if (!find) {
        const prevVNode = newChildren[i - 1]
        let anchor = null
        if (prevVNode) {
          anchor = prevVNode.el.nextSibling
        } else {
          anchor = container.firstChild
        }
        patch(null, newVNode, container, anchor)
      }
    }

    // 遍历旧的节点
    for (let i = 0; i < oldChildren.length; i++) {
      const oldVNode = oldChildren[i]
      // 拿着旧 VNode 去新 children 中寻找相同的节点
      const has = newChildren.find(
        vnode => vnode.key === oldVNode.key
      )
      if (!has) {
        // 如果没有找到相同的节点，则移除
        unmount(oldVNode)
      }
    }
    
  } else {
    if (Array.isArray(n1.children)) {
      n1.children.forEach(c => unmount(c))
    } else if (typeof n1.children === 'string') {
      setElementText(container, '')
    }
  }
}

问题：在新旧子节点查找相同节点（相同的key）时，使用了双层循环，空间复杂度是 O(n^2)，是否可以降低为 O(n) 呢？