Renderer 更新 -> 乱序 Diff

import { h, render } from '../dist/vue.esm.js'

const vNode = h('div', [
  h('p', { key: 'a', style: { color: 'blue' } }, 'a'),
  h('p', { key: 'b', style: { color: 'blue' } }, 'b'),
  h('p', { key: 'c', style: { color: 'blue' } }, 'c'),
  h('p', { key: 'd', style: { color: 'blue' } }, 'd'),
  h('p', { key: 'e', style: { color: 'blue' } }, 'e')
])

const vNode2 = h('div', [
  h('p', { key: 'a', style: { color: 'red' } }, 'a'),
  h('p', { key: 'c', style: { color: 'red' } }, 'c'),
  h('p', { key: 'd', style: { color: 'red' } }, 'd'),
  h('p', { key: 'b', style: { color: 'red' } }, 'b'),
  h('p', { key: 'e', style: { color: 'red' } }, 'e')
])

render(vNode, app)

setTimeout(() => {
  render(vNode2, app)
}, 1000)

function patchKeyedChildren(c1, c2, container) {
  // ... 双端 diff 代码

  if (i > e1) {
    // 挂载新节点
  }
  else if (i > e2) {
    // 卸载旧节点
  }
  else {
    // 进入乱序 diff 流程

    // 记录未处理节点的起始位置
    const s1 = i // 旧节点数组中的起始索引
    const s2 = i // 新节点数组中的起始索引

    /**
     * 建立新节点的 key -> index 映射
     *
     * 以示例场景为例：
     * c1: [a, (b, c, d), e]  -> s1 = 1, e1 = 3
     * c2: [a, (c, d, b), e]  -> s2 = 1, e2 = 3
     *
     * 建立的映射关系：
     * keyToNewIndexMap = {
     *   c: 1,  // c 在新数组中的索引是 1
     *   d: 2,  // d 在新数组中的索引是 2
     *   b: 3   // b 在新数组中的索引是 3
     * }
     */
    const keyToNewIndexMap = new Map()

    // 遍历新节点的未处理区域，建立映射
    for (let j = s2; j <= e2; j++) {
      const n2 = c2[j]
      keyToNewIndexMap.set(n2.key, j)
    }

    /**
     * 遍历旧节点，判断是否可复用
     *
     * 对于每个旧节点：
     * - 如果在新节点中找到相同的 key，说明可以复用，进行 patch 更新
     * - 如果在新节点中找不到，说明该节点被删除，需要卸载
     */
    for (let j = s1; j <= e1; j++) {
      const n1 = c1[j]
      const newIndex = keyToNewIndexMap.get(n1.key)

      if (newIndex !== undefined) {
        // 找到了对应的新节点，进行更新
        patch(n1, c2[newIndex], container)
      }
      else {
        // 在新节点中找不到，卸载这个旧节点
        unmount(n1)
      }
    }
  }
}

/**
 * 倒序遍历新节点的未处理区域
 *
 * 为什么要倒序？
 * - 因为我们需要一个稳定的参照点（anchor）来确定插入位置
 * - 从后往前处理，每次插入时，后面的节点位置已经是正确的
 * - 这样可以使用 c2[j + 1] 作为 anchor，保证插入位置准确
 */
for (let j = e2; j >= s2; j--) {
  const n2 = c2[j]

  /**
   * 确定锚点位置
   * - anchor 是当前节点应该插入到哪个节点之前
   * - c2[j + 1] 是新数组中的下一个节点（已经处理过，位置正确）
   * - 如果 j + 1 超出数组范围，说明是最后一个节点，anchor 为 null（追加到末尾）
   */
  const anchor = c2[j + 1]?.el || null

  if (n2.el) {
    // 节点已存在（在第一步中被 patch 过），只需要移动位置
    hostInsert(n2.el, container, anchor)
  }
  else {
    // 节点不存在（新增节点），需要挂载
    patch(null, n2, container, anchor)
  }
}

function patchKeyedChildren(c1, c2, container) {
  let i = 0
  let e1 = c1.length - 1
  let e2 = c2.length - 1

  // 1. 头部对比
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container)
    }
    else {
      break
    }
    i++
  }

  // 2. 尾部对比
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container)
    }
    else {
      break
    }
    e1--
    e2--
  }

  // 3. 处理对比结果
  if (i > e1) {
    // 挂载新节点
    const nextPos = e2 + 1
    const anchor = nextPos < c2.length ? c2[nextPos].el : null
    while (i <= e2) {
      patch(null, c2[i], container, anchor)
      i++
    }
  }
  else if (i > e2) {
    // 卸载旧节点
    while (i <= e1) {
      unmount(c1[i])
      i++
    }
  }
  else {
    // 4. 乱序 diff
    const s1 = i
    const s2 = i

    // 建立新节点的 key 映射
    const keyToNewIndexMap = new Map()
    for (let j = s2; j <= e2; j++) {
      const n2 = c2[j]
      keyToNewIndexMap.set(n2.key, j)
    }

    // 遍历旧节点，更新或卸载
    for (let j = s1; j <= e1; j++) {
      const n1 = c1[j]
      const newIndex = keyToNewIndexMap.get(n1.key)

      if (newIndex !== undefined) {
        patch(n1, c2[newIndex], container)
      }
      else {
        unmount(n1)
      }
    }

    // 倒序调整节点位置
    for (let j = e2; j >= s2; j--) {
      const n2 = c2[j]
      const anchor = c2[j + 1]?.el || null

      if (n2.el) {
        hostInsert(n2.el, container, anchor)
      }
      else {
        patch(null, n2, container, anchor)
      }
    }
  }
}