渲染器的核心 Diff 算法

function patchChildren(prevChildFlags, nextChildFlags, prevChildren, nextChildren, container) {
  switch (prevChildFlags) {

    // ...

    // 旧的 children 中有多个子节点
    default:
      switch (nextChildFlags) {
        
        // ...

        default:
          // 新的 children 中有多个子节点
          // 获取公共长度，取新旧 children 长度较小的那一个
          const prevLen = prevChildren.length
          const nextLen = nextChildren.length
          const commonLength = prevLen > nextLen ? nextLen : prevLen
          for (let i = 0; i < commonLength; i++) {
            patch(prevChildren[i], nextChildren[i], container)
          }

          // 如果 nextLen > prevLen，将多出来的元素添加
          if (nextLen > prevLen) {
            for (let i = commonLength; i < nextLen; i++) {
              mount(nextChildren[i], container)
            }
          // 如果 prevLen > nextLen，将多出来的元素移除
          } else if (prevLen > nextLen) {
            for (let i = commonLength; i < prevLen; i++) {
              container.removeChild(prevChildren[i].el)
            }
          }
          break
      }
      break
  }
}

// 旧的 children
[
  h('li', null, 1),
  h('li', null, 2),
  h('li', null, 3)
]

// 新的 children
[
  h('li', null, 2),
  h('li', null, 3),
  h('li', null, 4)
]

// 遍历新的 children
for (let i = 0; i < nextChildren.length; i++) {
  const nextVNode = nextChildren[i]
  let j = 0
  // 遍历旧的 children
  for (j; j < prevChildren.length; j++) {
    const prevVNode = prevChildren[j]
    // 如果找到了具有相同 key 值的两个节点，则调用 patch 函数更新之
    if (nextVNode.key === prevVNode.key) {
      patch(prevVNode, nextVNode, container)
      break // 这里需要 break
    }
  }
}

// 用来存储寻找过程中遇到的最大索引值
let lastIndex = 0
// 遍历新的 children
for (let i = 0; i < nextChildren.length; i++) {
  const nextVNode = nextChildren[i]
  let j = 0
  // 遍历旧的 children
  for (j; j < prevChildren.length; j++) {
    const prevVNode = prevChildren[j]
    // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新之
    if (nextVNode.key === prevVNode.key) {
      patch(prevVNode, nextVNode, container)
      if (j < lastIndex) {
        /**
         *  假设我们当前正在更新的节点是 li-a，那么如上代码中的变量 i 就是节点 li-a 在新 children 中的位置索引
         *  所以 nextChildren[i - 1] 就是 li-a 节点的前一个节点，也就是 li-c 节点，由于 li-c 节点存在对真实 DOM 的引用
         *  所以我们可以通过其 el 属性拿到真实 DOM
         * 
         *  我们的目标是把 li-a 节点对应的真实 DOM 移动到 li-c 节点所对应真实 DOM 的后面
         *  所以我们的思路应该是想办法拿到 li-c 节点对应真实 DOM 的下一个兄弟节点
         *  并把 li-a 节点所对应真实 DOM 插到该节点的前面
         * 
         *  所以 refNode 引用是 li-c 节点对应真实 DOM 的下一个兄弟节点
         *  拿到了正确的 refNode 之后，我们就可以调用容器元素的 insertBefore 方法来完成 DOM 的移动了
         *  移动的对象就是 li-a 节点所对应的真实 DOM，由于当前正在处理的就是 li-a 节点
         *  所以 prevVNode 就是旧 children 中的 li-a 节点，它是存在对真实 DOM 的引用的，即 prevVNode.el
         */
        // 需要移动
        // refNode 是为了下面调用 insertBefore 函数准备的
        const refNode = nextChildren[i - 1].el.nextSibling
        // 调用 insertBefore 函数移动 DOM
        container.insertBefore(prevVNode.el, refNode)
      } else {
        // 更新 lastIndex
        lastIndex = j
      }
      break // 这里需要 break
    }
  }
}

let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
  const nextVNode = nextChildren[i]
  /**
   *  我们在原来的基础上添加了变量 find，它将作为一个标志，代表新 children 中的节点是否存在于旧 children 中，初始值为 false
   *  一旦在旧 children 中寻找到了相应的节点，我们就将变量 find 的值设置为 true
   *  所以如果内层循环结束后，变量 find 的值仍然为 false，则说明在旧的 children 中找不到可复用的节点
   *  这时我们就需要使用 mount 函数将当前遍历到的节点挂载到容器元素
   */
  let j = 0, find = false
  for (j; j < prevChildren.length; j++) {
    const prevVNode = prevChildren[j]
    if (nextVNode.key === prevVNode.key) {
      find = true
      patch(prevVNode, nextVNode, container)
      if (j < lastIndex) {
        // 需要移动
        const refNode = nextChildren[i - 1].el.nextSibling
        container.insertBefore(prevVNode.el, refNode)
        break
      } else {
        // 更新 lastIndex
        lastIndex = j
      }
    }
  }
  /**
   *  我们应该按照节点在新的 children 中的位置将其添加到正确的地方
   *  所以我们先找到当前遍历到的节点的前一个节点，即 nextChildren[i - 1]
   *  接着找到该节点所对应真实 DOM 的下一个子节点作为 refNode，即 nextChildren[i - 1].el.nextSibling
   *  但是由于当前遍历到的节点有可能是新 children 的第一个节点，这时 i - 1 < 0，这将导致 nextChildren[i - 1] 不存在
   *  所以当 i - 1 < 0 时，我们只需要把新的节点插入到最前面即可（第一个节点），所以我们使用 prevChildren[0].el 作为 refNode
   * 
   *  最后调用 mount 函数挂载新节点时，我们为其传递了第四个参数 refNode（这就是第四个参数的作用）
   *  即当 refNode 存在时，我们应该使用 insertBefore 方法代替 appendChild 方法
   */
  if (!find) {
    // 挂载新节点
    // 找到 refNode
    const refNode =
      i - 1 < 0
        ? prevChildren[0].el
        : nextChildren[i - 1].el.nextSibling
    mount(nextVNode, container, false, refNode)
  }
}

let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
  // ... 省略（见上方）
}
// 移除已经不存在的节点
// 遍历旧的节点
for (let i = 0; i < prevChildren.length; i++) {
  const prevVNode = prevChildren[i]
  // 拿着旧 VNode 去新 children 中寻找相同的节点
  const has = nextChildren.find(
    nextVNode => nextVNode.key === prevVNode.key
  )
  if (!has) {
    // 如果没有找到相同的节点，则移除
    container.removeChild(prevVNode.el)
  }
}

let oldStartIdx = 0
let oldEndIdx = prevChildren.length - 1
let newStartIdx = 0
let newEndIdx = nextChildren.length - 1

let oldStartVNode = prevChildren[oldStartIdx]
let oldEndVNode = prevChildren[oldEndIdx]
let newStartVNode = nextChildren[newStartIdx]
let newEndVNode = nextChildren[newEndIdx]

if (oldStartVNode.key === newStartVNode.key) {
  // 步骤一：oldStartVNode 和 newStartVNode 比对
} else if (oldEndVNode.key === newEndVNode.key) {
  // 步骤二：oldEndVNode 和 newEndVNode 比对
} else if (oldStartVNode.key === newEndVNode.key) {
  // 步骤三：oldStartVNode 和 newEndVNode 比对
} else if (oldEndVNode.key === newStartVNode.key) {
  // 步骤四：oldEndVNode 和 newStartVNode 比对
}

if (oldStartVNode.key === newStartVNode.key) {
  // 步骤一：oldStartVNode 和 newStartVNode 比对
} else if (oldEndVNode.key === newEndVNode.key) {
  // 步骤二：oldEndVNode 和 newEndVNode 比对
} else if (oldStartVNode.key === newEndVNode.key) {
  // 步骤三：oldStartVNode 和 newEndVNode 比对
} else if (oldEndVNode.key === newStartVNode.key) {
  // 步骤四：oldEndVNode 和 newStartVNode 比对

  // 先调用 patch 函数完成更新
  patch(oldEndVNode, newStartVNode, container)
  // 更新完成后，将容器中最后一个子节点移动到最前面，使其成为第一个子节点
  container.insertBefore(oldEndVNode.el, oldStartVNode.el)
  // 更新索引，指向下一个位置
  oldEndVNode = prevChildren[--oldEndIdx]
  newStartVNode = nextChildren[++newStartIdx]
}

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // ...
}

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    /**
     *  当 oldStart === newStart 的时候
     *  由于该节点无论是在新 children 中还是旧 children 中，都是当前索引范围内的第一个节点，所以位置不需要变化
     *  即不需要移动操作，只需要调用 patch 函数更新即可，同时也要将相应的位置所以下移一位
     */
    patch(oldStartVNode, newStartVNode, container)
    oldStartVNode = prevChildren[++oldStartIdx]
    newStartVNode = nextChildren[++newStartIdx]
  } else if (oldEndVNode.key === newEndVNode.key) {
    /**
     *  当 oldEnd === newEnd 的时候
     *  说明二者在新旧 children 中都是最末尾的一个节点
     *  所以是不需要进行移动操作的，只需要调用 patch 函数更新即可，同时将相应的索引前移一位
     */
    patch(oldEndVNode, newEndVNode, container)
    oldEndVNode = prevChildren[--oldEndIdx]
    newEndVNode = newEndVNode[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {
    /**
     *  当 oldStart === newEnd 的时候
     *  说明该节点对应的真实 DOM 原本是第一个子节点，但现在变成了当前索引范围内的最后一个节点
     *  所以移动操作也是比较明显的，我们将 oldStartVNode 对应的真实 DOM 移动到 oldEndVNode 所对应真实 DOM 的后面即可
     */
    patch(oldStartVNode, newEndVNode, container)
    container.insertBefore(
      oldStartVNode.el,
      oldEndVNode.el.nextSibling
    )
    oldStartVNode = prevChildren[++oldStartIdx]
    newEndVNode = nextChildren[--newEndIdx]
  } else if (oldEndVNode.key === newStartVNode.key) {
    /**
     *  当 newStart === oldEnd 的时候
     *  说明该节点所对应的真实 DOM 原本是最后一个子节点，并且更新之后它应该变成第一个子节点
     *  所以我们需要把该节点所对应的真实 DOM 移动到最前方即可，所以我们的操作如下
     * 
     *  1. 先调用 patch 函数完成更新
     *  2. 更新完成后，将容器中最后一个子节点移动到最前面，使其成为第一个子节点
     *  3. 更新索引，指向下一个位置
     */
    patch(oldEndVNode, newStartVNode, container)
    container.insertBefore(oldEndVNode.el, oldStartVNode.el)
    oldEndVNode = prevChildren[--oldEndIdx]
    newStartVNode = nextChildren[++newStartIdx]
  }
}

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // ...
  } else if (oldEndVNode.key === newEndVNode.key) {
    // ...
  } else if (oldStartVNode.key === newEndVNode.key) {
    // ...
  } else if (oldEndVNode.key === newStartVNode.key) {
    // ...
  } else {
    // 遍历旧 children，试图寻找与 newStartVNode 拥有相同 key 值的元素
    const idxInOld = prevChildren.findIndex(
      node => node.key === newStartVNode.key
    )
  }
}

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // ...
  } else if (oldEndVNode.key === newEndVNode.key) {
    // ...
  } else if (oldStartVNode.key === newEndVNode.key) {
    // ...
  } else if (oldEndVNode.key === newStartVNode.key) {
    // ...
  } else {
    // 遍历旧 children，试图寻找与 newStartVNode 拥有相同 key 值的元素
    const idxInOld = prevChildren.findIndex(
      node => node.key === newStartVNode.key
    )
    if (idxInOld >= 0) {
      // vnodeToMove 就是在旧 children 中找到的节点，该节点所对应的真实 DOM 应该被移动到最前面
      const vnodeToMove = prevChildren[idxInOld]
      // 调用 patch 函数完成更新
      patch(vnodeToMove, newStartVNode, container)
      // 把 vnodeToMove.el 移动到最前面，即 oldStartVNode.el 的前面
      container.insertBefore(vnodeToMove.el, oldStartVNode.el)
      // 由于旧 children 中该位置的节点所对应的真实 DOM 已经被移动，所以将其设置为 undefined（这是很关键的一步）
      prevChildren[idxInOld] = undefined
    }
    // 将 newStartIdx 下移一位，准备进行下一轮的比较
    newStartVNode = nextChildren[++newStartIdx]
  }
}

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (!oldStartVNode) {
    oldStartVNode = prevChildren[++oldStartIdx]
  } else if (!oldEndVNode) {
    oldEndVNode = prevChildren[--oldEndIdx]
  } else if (oldStartVNode.key === newStartVNode.key) {
    // ...
  }
    // ...
}

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (!oldStartVNode) {
    oldStartVNode = prevChildren[++oldStartIdx]
  } 
  
    // ... 

  else {
    if (idxInOld >= 0) {
      // ... 
    } else {
      // 使用 mount 函数挂载新节点
      mount(newStartVNode, container, false, oldStartVNode.el)
    }
    newStartVNode = nextChildren[++newStartIdx]
  }
}

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // ...
}
if (oldEndIdx < oldStartIdx) {
  // 添加新节点
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    mount(nextChildren[i], container, false, oldStartVNode.el)
  }
}

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 省略...
}
if (oldEndIdx < oldStartIdx) {
  // 添加新节点
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    mount(nextChildren[i], container, false, oldStartVNode.el)
  }
} else if (newEndIdx < newStartIdx) {
  // 移除操作
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    container.removeChild(prevChildren[i].el)
  }
}

text1: I use vue for app development
text2: I use react for app development

text1: vue
text2: react

text1: I like react
text2: I like react too


// ==> 实际上

text1:
text2: too

text1: I like react too
text2: I like react 


// ==> 实际上

text1: too
text2:

// 更新相同的前缀节点
// j 为指向新旧 children 中第一个节点的索引
let j = 0
let prevVNode = prevChildren[j]
let nextVNode = nextChildren[j]
// while 循环向后遍历，直到遇到拥有不同 key 值的节点为止
while (prevVNode.key === nextVNode.key) {
  // 调用 patch 函数更新
  patch(prevVNode, nextVNode, container)
  j++
  prevVNode = prevChildren[j]
  nextVNode = nextChildren[j]
}

// 更新相同的后缀节点

// 指向旧 children 最后一个节点的索引
let prevEnd = prevChildren.length - 1
// 指向新 children 最后一个节点的索引
let nextEnd = nextChildren.length - 1

prevVNode = prevChildren[prevEnd]
nextVNode = nextChildren[nextEnd]

// while 循环向前遍历，直到遇到拥有不同 key 值的节点为止
while (prevVNode.key === nextVNode.key) {
  // 调用 patch 函数更新
  patch(prevVNode, nextVNode, container)
  prevEnd--
  nextEnd--
  prevVNode = prevChildren[prevEnd]
  nextVNode = nextChildren[nextEnd]
}

j: 1
prevEnd: 0
nextEnd: 1

// 满足条件，则说明从 j -> nextEnd 之间的节点应作为新节点插入
if (j > prevEnd && j <= nextEnd) {
  // 所有新节点应该插入到位于 nextPos 位置的节点的前面
  const nextPos = nextEnd + 1
  const refNode =
    nextPos < nextChildren.length ? nextChildren[nextPos].el : null
  // 采用 while 循环，调用 mount 函数挂载节点
  while (j <= nextEnd) {
    mount(nextChildren[j++], container, false, refNode)
  }
}

j: 1
prevEnd: 1
nextEnd: 0

if (j > prevEnd && j <= nextEnd) {
  // j -> nextEnd 之间的节点应该被添加
  const nextPos = nextEnd + 1
  const refNode =
    nextPos < nextChildren.length ? nextChildren[nextPos].el : null
  while (j <= nextEnd) {
    mount(nextChildren[j++], container, false, refNode)
  }
} else if (j > nextEnd) {
  // j -> prevEnd 之间的节点应该被移除
  while (j <= prevEnd) {
    container.removeChild(prevChildren[j++].el)
  }
}

// while 循环向后遍历，直到遇到拥有不同 key 值的节点为止
while (prevVNode.key === nextVNode.key) {
  // 调用 patch 函数更新
  // ...
  j++
  // ...
}

// while 循环向前遍历，直到遇到拥有不同 key 值的节点为止
while (prevVNode.key === nextVNode.key) {
  // 调用 patch 函数更新
  // ...
  prevEnd--
  nextEnd--
  // ...
}

// 满足条件，则说明从 j -> nextEnd 之间的节点应作为新节点插入
if (j > prevEnd && j <= nextEnd) {
  // j -> nextEnd 之间的节点应该被添加
  // ...
} else if (j > nextEnd) {
  // j -> prevEnd 之间的节点应该被移除
  // ...
}

outer: {
  while (prevVNode.key === nextVNode.key) {
    patch(prevVNode, nextVNode, container)
    j++
    if (j > prevEnd || j > nextEnd) {
      break outer
    }
    prevVNode = prevChildren[j]
    nextVNode = nextChildren[j]
  }
  // 更新相同的后缀节点
  prevVNode = prevChildren[prevEnd]
  nextVNode = nextChildren[nextEnd]
  while (prevVNode.key === nextVNode.key) {
    patch(prevVNode, nextVNode, container)
    prevEnd--
    nextEnd--
    if (j > prevEnd || j > nextEnd) {
      break outer
    }
    prevVNode = prevChildren[prevEnd]
    nextVNode = nextChildren[nextEnd]
  }
}

/**
 *  基本逻辑如下
 *  我们在外层循环逐个从旧 children 中取出未处理的节点，并尝试在新 children 中寻找拥有相同 key 值的可复用节点
 *  一旦找到了可复用节点，则调用 patch 函数更新之
 */
// 构造 source 数组
const nextLeft = nextEnd - j + 1 // 新 children 中剩余未处理节点的数量
const source = []
for (let i = 0; i < nextLeft; i++) {
  source.push(-1)
}

const prevStart = j
const nextStart = j
let moved = false
let pos = 0

// 构建索引表
// Index Map 中的键是节点的 key，值是节点在新 children 中的位置索引
// 可以使得我们能够非常快速的定位旧 children 中的节点在新 children 中的位置
const keyIndex = {}
for (let i = nextStart; i <= nextEnd; i++) {
  keyIndex[nextChildren[i].key] = i
}

// 我们还需要一个数量标识，用来代表已经更新过的节点的数量
// 我们知道，已经更新过的节点数量应该小于新 children 中需要更新的节点数量
// 一旦更新过的节点数量超过了新 children 中需要更新的节点数量，则说明该节点是多余的节点，我们也应该将其移除
let patched = 0

// 遍历旧 children 的剩余未处理节点
for (let i = prevStart; i <= prevEnd; i++) {
  prevVNode = prevChildren[i]

  if (patched < nextLeft) {
    // 通过索引表快速找到新 children 中具有相同 key 的节点的位置
    const k = keyIndex[prevVNode.key]
    /**
     *  我们试图拿旧 children 中的节点尝试去新 children 中寻找具有相同 key 值的节点，但并非总是能够找得到
     *  当 k === 'undefined' 时，说明该节点在新 children 中已经不存在了，这时我们应该将其移除
     */
    if (typeof k !== 'undefined') {
      nextVNode = nextChildren[k]
      // patch 更新
      patch(prevVNode, nextVNode, container)

      // 变量 patched 将作为数量标识，它的初始值为 0，只有当条件 patched < nextLeft 不成立时
      // 说明该节点已经不存在与新 children 中了，是一个多余的节点，于是我们将其移除
      patched++

      /**
       *  这里需要注意的是，由于 k - nextStart 的值才是正确的位置索引，而非 k 本身，并且外层循环中变量 i 的值就代表了该节点在旧 children 中的位置
       *  所以直接将 i 赋值给 source[k - nextStart] 即可达到目的
       */
      // 更新 source 数组
      source[k - nextStart] = i

      /**
       *  这里采用类似 react 的方式
       *  变量 k 代表我们在遍历新 children 中遇到的节点的位置索引，变量 pos 用来存储遇到的位置索引的最大值
       *  一旦发现后来遇到索引比之前遇到的索引要小，即 k < pos，则说明需要移动操作，这时我们更新变量 moved 的值为 true
       */
      // 判断是否需要移动
      if (k < pos) {
        moved = true
      } else {
        pos = k
      }
    } else {
      // 没找到，说明旧节点在新 children 中已经不存在了，应该移除
      container.removeChild(prevVNode.el)
    }
  } else {
    // 多余的节点，应该移除
    container.removeChild(prevVNode.el)
  }
}

if (moved) {
  // 如果 moved 为真，则需要进行 DOM 移动操作
  // 调用 lis 函数求出数组 source 的最长递增子序列为 [ 0, 1 ]
  const seq = lis(sources) // [ 0, 1 ]
}

if (moved) {
  const seq = lis(source)
  // j 指向最长递增子序列的最后一个值
  let j = seq.length - 1
  /**
   *  变量 j 指向最长递增子序列的最后一个位置，使用 for 循环从后向前遍历新 children 中剩余未处理的子节点
   *  这里的技巧在于 i 的值的范围是 0 到 nextLeft - 1，这实际上就等价于我们对剩余节点进行了重新编号
   */
  // 从后向前遍历新 children 中的剩余未处理节点
  for (let i = nextLeft - 1; i >= 0; i--) {

    /**
     *  判断当前节点的位置索引值 i 是否与子序列中位于 j 位置的值相等，总的来说分为三种情况
     *  1. 如果 source[i] === -1，应该作为全新的节点挂载
     *  2. 如果 i !== seq[j]，如果不相等，则说明该节点需要被移动
     *  3. 如果 i === seq[j]，相等则说明该节点不需要被移动，并让 j 指向下一个位置
     */
    if (source[i] === -1) {
      // 作为全新的节点挂载

      // 该节点在新 children 中的真实位置索引
      const pos = i + nextStart
      const nextVNode = nextChildren[pos]
      // 该节点下一个节点的位置索引
      const nextPos = pos + 1
      // 挂载
      mount(
        nextVNode,
        container,
        false,
        nextPos < nextChildren.length
          ? nextChildren[nextPos].el
          : null
      )
    } else if (i !== seq[j]) {
      // 说明该节点需要移动

      // 为了将节点挂载到正确的位置，我们需要找到当前节点的真实位置索引
      // 该节点在新 children 中的真实位置索引
      const pos = i + nextStart
      const nextVNode = nextChildren[pos]
      // 以及当前节点的后一个节点，并挂载该节点的前面即可
      const nextPos = pos + 1
      // 移动
      container.insertBefore(
        nextVNode.el,
        nextPos < nextChildren.length
          ? nextChildren[nextPos].el
          : null
      )
    } else {
      // 当 i === seq[j] 时，说明该位置的节点不需要移动
      // 并让 j 指向下一个位置
      j--
    }
  }
}