vue源码（diff算法）

简单 diff 算法

减少 DOM 操作的性能和开销

针对这样一个例子：

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

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

针对这个例子，我们希望只进行一次 DOM 操作，将 1、2、3 替换为 4、5、6，而不是先删除 1、2、3，再插入 4、5、6，并且需要考虑到新旧节点数量不一致的情况（需要先遍历短的节点列表，再遍历剩余的列表）。

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 (newLen < oldLen) {
      for (let i = commonLength; i < oldLen; i++) {
        unmount(oldChildren[i])
      }
    }
  } else {
    // 省略代码
  }
}

DOM 复用与 key 的作用

有下面一种情况：

// oldChildren
const old = [{ type: 'p' }, { type: 'div' }, { type: 'span' }]
  //newChildren
const new =  [{ type: 'span' }, { type: 'p' }, { type: 'div' }]

如果采用上面的方法，由于 type 不同，调用 patch 函数时，总共会有 6 次的DOM操作，但是实际上oldChildren和newChildren实际上只有顺序不同，因此只需要进行DOM的移动操作即可。

实际操作中，我们需要引入key属性来作为标识来帮助判断如何移动DOM。

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

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

key属性就像身份证，只要type属性和key属性相同，我们便可以认为他们可以进行DOM复用。注意：这里可以进行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
    for (let i = 0; i < newChildren.length; i++) {
      const newNode = newChildren[i]
      for (let j = 0; j < oldChildren.length; j++) {
        const oldNode = oldChildren[j]
        if (newNode.key === oldNode.key) {
          patch(oldNode, newNode, container)
          break
        }
      }
    }
  } else {
    // 省略代码
  }
}

这里只考虑patch内容，下面再考虑移动DOM。

找到需要移动的元素

这里的主要思路是：

• 遍历新的nodeList时，如果匹配到了key相同的旧的node，则进行patch操作，并且此时观察此时匹配到的index是否仍然保持递增的序列，如果仍然保持则更新lastIndex为新的index, 否则说明需要移动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
    // 增加了lastIndex变量来记录上一次遍历到的最大index位置
    let lastIndex = 0
    for (let i = 0; i < newChildren.length; i++) {
      const newNode = newChildren[i]
      for (let j = 0; j < oldChildren.length; j++) {
        const oldNode = oldChildren[j]
        if (newNode.key === oldNode.key) {
          patch(oldNode, newNode, container)
          if (j < lastIndex) {
            // 需要移动
          } else {
            lastIndex = j
          }
          break
        }
      }
    }
  } else {
    // 省略代码
  }
}