渲染器-组件更新与diff算法

// 早期版本
instance.update = effect(componentUpdateFn, prodEffectOptions)

// Vue 3.5 - packages/runtime-core/src/renderer.ts
const setupRenderEffect: SetupRenderEffectFn = (
  instance,
  initialVNode,
  container,
  anchor,
  parentSuspense,
  namespace: ElementNamespace,
  optimized,
) => {
  const componentUpdateFn = () => {
    if (!instance.isMounted) {
      // 挂载逻辑...
    } else {
      // 更新逻辑...
    }
  }

  // 创建响应式副作用渲染函数
  instance.scope.on()
  const effect = (instance.effect = new ReactiveEffect(componentUpdateFn))
  instance.scope.off()

  // update 是 effect.run 的绑定版本，用于手动触发
  const update = (instance.update = effect.run.bind(effect))
  // job 是调度器实际执行的任务，使用 runIfDirty 实现惰性执行
  const job: SchedulerJob = (instance.job = effect.runIfDirty.bind(effect))
  job.i = instance
  job.id = instance.uid
  // 设置调度器：当响应式数据变化时，不直接执行更新，而是将 job 入队
  effect.scheduler = () => queueJob(job)

  toggleRecurse(instance, true)
  update()
}

// packages/reactivity/src/effect.ts
runIfDirty(): void {
  if (isDirty(this)) {
    this.run()
  }
}

// packages/reactivity/src/effect.ts
function isDirty(sub: Subscriber): boolean {
  for (let link = sub.deps; link; link = link.nextDep) {
    if (
      link.dep.version !== link.version ||
      (link.dep.computed &&
        (refreshComputed(link.dep.computed) ||
          link.dep.version !== link.version))
    ) {
      return true
    }
  }
  return false
}

// Vue 3.5 - packages/runtime-core/src/renderer.ts
const componentUpdateFn = () => {
  if (!instance.isMounted) {
    // 挂载逻辑...
  } else {
    // 更新组件
    let { next, bu, u, parent, vnode } = instance

    // Suspense 异步组件的特殊处理
    if (__FEATURE_SUSPENSE__) {
      const nonHydratedAsyncRoot = locateNonHydratedAsyncRoot(instance)
      if (nonHydratedAsyncRoot) {
        if (next) {
          next.el = vnode.el
          updateComponentPreRender(instance, next, optimized)
        }
        nonHydratedAsyncRoot.asyncDep!.then(() => {
          if (!instance.isUnmounted) {
            componentUpdateFn()
          }
        })
        return
      }
    }

    // updateComponent
    // This is triggered by mutation of component's own state (next: null)
    // OR parent calling processComponent (next: VNode)
    let originNext = next

    // 禁止在 beforeUpdate 生命周期钩子中递归触发组件更新
    toggleRecurse(instance, false)

    if (next) {
      next.el = vnode.el
      // 更新组件实例的 vnode 信息
      updateComponentPreRender(instance, next, optimized)
    } else {
      next = vnode
    }

    // beforeUpdate 生命周期钩子
    if (bu) {
      invokeArrayFns(bu)
    }
    // onVnodeBeforeUpdate 钩子
    if ((vnodeHook = next.props && next.props.onVnodeBeforeUpdate)) {
      invokeVNodeHook(vnodeHook, parent, next, vnode)
    }
    toggleRecurse(instance, true)

    // 渲染新的子树 vnode
    const nextTree = renderComponentRoot(instance)
    // 获取旧的子树 vnode
    const prevTree = instance.subTree
    // 更新子树引用
    instance.subTree = nextTree

    // 比对新旧子树并更新 DOM
    patch(
      prevTree,
      nextTree,
      hostParentNode(prevTree.el!)!,
      getNextHostNode(prevTree),
      instance,
      parentSuspense,
      namespace,
    )

    // 缓存更新后的 DOM 节点
    next.el = nextTree.el

    // 如果是自身状态触发的更新（originNext === null），需要更新 HOC 宿主元素
    if (originNext === null) {
      updateHOCHostEl(instance, nextTree.el)
    }

    // updated 生命周期钩子
    if (u) {
      queuePostRenderEffect(u, parentSuspense)
    }
    // onVnodeUpdated 钩子
    if ((vnodeHook = next.props && next.props.onVnodeUpdated)) {
      queuePostRenderEffect(
        () => invokeVNodeHook(vnodeHook!, parent, next!, vnode),
        parentSuspense,
      )
    }
  }
}

// Vue 3.5 - packages/runtime-core/src/renderer.ts
const updateComponentPreRender = (
  instance: ComponentInternalInstance,
  nextVNode: VNode,
  optimized: boolean,
) => {
  nextVNode.component = instance
  const prevProps = instance.vnode.props
  instance.vnode = nextVNode
  instance.next = null
  updateProps(instance, nextVNode.props, prevProps, optimized)
  updateSlots(instance, nextVNode.children, optimized)

  pauseTracking()
  // props 更新可能触发了 pre-flush 的 watchers
  // 在渲染更新之前先刷新它们
  flushPreFlushCbs(instance)
  resetTracking()
}

// Vue 3.5 - packages/runtime-core/src/renderer.ts
const patch: PatchFn = (
  n1,
  n2,
  container,
  anchor = null,
  parentComponent = null,
  parentSuspense = null,
  namespace = undefined,
  slotScopeIds = null,
  optimized = __DEV__ && isHmrUpdating ? false : !!n2.dynamicChildren,
) => {
  if (n1 === n2) {
    return
  }

  // 新老节点类型不同，卸载旧节点
  if (n1 && !isSameVNodeType(n1, n2)) {
    anchor = getNextHostNode(n1)
    unmount(n1, parentComponent, parentSuspense, true)
    n1 = null
  }

  // BAIL 优化标记：降级为全量比对
  if (n2.patchFlag === PatchFlags.BAIL) {
    optimized = false
    n2.dynamicChildren = null
  }

  const { type, ref, shapeFlag } = n2
  switch (type) {
    case Text:
      processText(n1, n2, container, anchor)
      break
    case Comment:
      processCommentNode(n1, n2, container, anchor)
      break
    case Static:
      if (n1 == null) {
        mountStaticNode(n2, container, anchor, namespace)
      } else if (__DEV__) {
        patchStaticNode(n1, n2, container, namespace)
      }
      break
    case Fragment:
      processFragment(
        n1, n2, container, anchor, parentComponent,
        parentSuspense, namespace, slotScopeIds, optimized,
      )
      break
    default:
      if (shapeFlag & ShapeFlags.ELEMENT) {
        processElement(
          n1, n2, container, anchor, parentComponent,
          parentSuspense, namespace, slotScopeIds, optimized,
        )
      } else if (shapeFlag & ShapeFlags.COMPONENT) {
        processComponent(
          n1, n2, container, anchor, parentComponent,
          parentSuspense, namespace, slotScopeIds, optimized,
        )
      }
      // ... 其他类型处理
  }
}

// Vue 3.5 - packages/runtime-core/src/vnode.ts
export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
  if (__DEV__ && n2.shapeFlag & ShapeFlags.COMPONENT && n1.component) {
    const dirtyInstances = hmrDirtyComponents.get(n2.type as ConcreteComponent)
    if (dirtyInstances && dirtyInstances.has(n1.component)) {
      // HMR 场景：强制卸载旧组件，重新挂载新组件
      n1.shapeFlag &= ~ShapeFlags.COMPONENT_SHOULD_KEEP_ALIVE
      n2.shapeFlag &= ~ShapeFlags.COMPONENT_KEPT_ALIVE
      return false
    }
  }
  return n1.type === n2.type && n1.key === n2.key
}

// Vue 3.5 - packages/runtime-core/src/renderer.ts
const processElement = (
  n1, n2, container, anchor, parentComponent,
  parentSuspense, namespace, slotScopeIds, optimized,
) => {
  if (n1 == null) {
    // 挂载逻辑...
  } else {
    patchElement(
      n1, n2, parentComponent, parentSuspense,
      namespace, slotScopeIds, optimized,
    )
  }
}

// Vue 3.5 - packages/runtime-core/src/renderer.ts
const patchElement = (
  n1, n2, parentComponent, parentSuspense,
  namespace, slotScopeIds, optimized,
) => {
  const el = (n2.el = n1.el!)
  let { patchFlag, dynamicChildren, dirs } = n2

  // #1426 考虑旧节点的 patchFlag，因为用户可能克隆编译器生成的 vnode
  patchFlag |= n1.patchFlag & PatchFlags.FULL_PROPS

  const oldProps = n1.props || EMPTY_OBJ
  const newProps = n2.props || EMPTY_OBJ

  // 禁止在 beforeUpdate 钩子中递归触发更新
  parentComponent && toggleRecurse(parentComponent, false)
  // onVnodeBeforeUpdate 钩子
  if ((vnodeHook = newProps.onVnodeBeforeUpdate)) {
    invokeVNodeHook(vnodeHook, parentComponent, n2, n1)
  }
  // 指令的 beforeUpdate 钩子
  if (dirs) {
    invokeDirectiveHook(n2, n1, parentComponent, 'beforeUpdate')
  }
  parentComponent && toggleRecurse(parentComponent, true)

  // #9135 innerHTML/textContent 清空需要在子节点挂载之前处理
  if (
    (oldProps.innerHTML && newProps.innerHTML == null) ||
    (oldProps.textContent && newProps.textContent == null)
  ) {
    hostSetElementText(el, '')
  }

  if (dynamicChildren) {
    // Block 优化路径：只比对动态子节点
    patchBlockChildren(
      n1.dynamicChildren!, dynamicChildren, el,
      parentComponent, parentSuspense,
      resolveChildrenNamespace(n2, namespace), slotScopeIds,
    )
  } else if (!optimized) {
    // 全量比对子节点
    patchChildren(
      n1, n2, el, null, parentComponent, parentSuspense,
      resolveChildrenNamespace(n2, namespace), slotScopeIds, false,
    )
  }

  // 更新 props
  if (patchFlag > 0) {
    if (patchFlag & PatchFlags.FULL_PROPS) {
      // 动态 key 的 props，需要全量比对
      patchProps(el, oldProps, newProps, parentComponent, namespace)
    } else {
      // class
      if (patchFlag & PatchFlags.CLASS) {
        if (oldProps.class !== newProps.class) {
          hostPatchProp(el, 'class', null, newProps.class, namespace)
        }
      }
      // style
      if (patchFlag & PatchFlags.STYLE) {
        hostPatchProp(el, 'style', oldProps.style, newProps.style, namespace)
      }
      // props
      if (patchFlag & PatchFlags.PROPS) {
        const propsToUpdate = n2.dynamicProps!
        for (let i = 0; i < propsToUpdate.length; i++) {
          const key = propsToUpdate[i]
          const prev = oldProps[key]
          const next = newProps[key]
          if (next !== prev || key === 'value') {
            hostPatchProp(el, key, prev, next, namespace, parentComponent)
          }
        }
      }
    }
    // text
    if (patchFlag & PatchFlags.TEXT) {
      if (n1.children !== n2.children) {
        hostSetElementText(el, n2.children as string)
      }
    }
  } else if (!optimized && dynamicChildren == null) {
    // 非优化模式，全量比对 props
    patchProps(el, oldProps, newProps, parentComponent, namespace)
  }
}

// Vue 3.5 - packages/runtime-core/src/renderer.ts
const patchChildren = (
  n1, n2, container, anchor, parentComponent,
  parentSuspense, namespace, slotScopeIds, optimized = false,
) => {
  const c1 = n1 && n1.children
  const prevShapeFlag = n1 ? n1.shapeFlag : 0
  const c2 = n2.children
  const { patchFlag, shapeFlag } = n2

  // 快速路径：编译器标记的优化路径
  if (patchFlag > 0) {
    if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
      // 有 key 的子节点 Fragment
      patchKeyedChildren(
        c1 as VNode[], c2 as VNodeArrayChildren, container, anchor,
        parentComponent, parentSuspense, namespace, slotScopeIds, optimized,
      )
      return
    } else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
      // 无 key 的子节点 Fragment
      patchUnkeyedChildren(
        c1 as VNode[], c2 as VNodeArrayChildren, container, anchor,
        parentComponent, parentSuspense, namespace, slotScopeIds, optimized,
      )
      return
    }
  }

  // children 有三种可能：文本、数组、空
  if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
    // 新子节点是文本
    if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
      // 旧子节点是数组 → 卸载旧子节点
      unmountChildren(c1 as VNode[], parentComponent, parentSuspense)
    }
    if (c2 !== c1) {
      // 新旧都是文本但内容不同 → 替换文本
      hostSetElementText(container, c2 as string)
    }
  } else {
    // 新子节点不是文本
    if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
      // 旧子节点是数组
      if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        // 新旧都是数组 → 执行 diff 算法
        patchKeyedChildren(
          c1 as VNode[], c2 as VNodeArrayChildren, container, anchor,
          parentComponent, parentSuspense, namespace, slotScopeIds, optimized,
        )
      } else {
        // 新子节点为空 → 卸载旧子节点
        unmountChildren(c1 as VNode[], parentComponent, parentSuspense, true)
      }
    } else {
      // 旧子节点不是数组（文本或空）
      if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
        // 旧子节点是文本 → 清空
        hostSetElementText(container, '')
      }
      if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        // 新子节点是数组 → 挂载新子节点
        mountChildren(
          c2 as VNodeArrayChildren, container, anchor,
          parentComponent, parentSuspense, namespace, slotScopeIds, optimized,
        )
      }
    }
  }
}

// Vue 3.5 - packages/runtime-core/src/renderer.ts
const processComponent = (
  n1, n2, container, anchor, parentComponent,
  parentSuspense, namespace, slotScopeIds, optimized,
) => {
  n2.slotScopeIds = slotScopeIds
  if (n1 == null) {
    // 挂载逻辑...
  } else {
    updateComponent(n1, n2, optimized)
  }
}

// Vue 3.5 - packages/runtime-core/src/renderer.ts
const updateComponent = (n1: VNode, n2: VNode, optimized: boolean) => {
  const instance = (n2.component = n1.component)!
  if (shouldUpdateComponent(n1, n2, optimized)) {
    if (
      __FEATURE_SUSPENSE__ &&
      instance.asyncDep &&
      !instance.asyncResolved
    ) {
      // 异步组件且尚未解析完成 → 仅更新 props 和 slots
      updateComponentPreRender(instance, n2, optimized)
      return
    } else {
      // 正常更新：将新 vnode 赋值给 next，触发更新
      instance.next = n2
      // instance.update 是 ReactiveEffect.run 的绑定版本
      instance.update()
    }
  } else {
    // 不需要更新，仅复制属性
    n2.el = n1.el
    instance.vnode = n2
  }
}

// Vue 3.5 - packages/runtime-core/src/componentRenderUtils.ts
export function shouldUpdateComponent(
  prevVNode: VNode,
  nextVNode: VNode,
  optimized?: boolean,
): boolean {
  const { props: prevProps, children: prevChildren, component } = prevVNode
  const { props: nextProps, children: nextChildren, patchFlag } = nextVNode
  const emits = component!.emitsOptions

  // HMR 更新时强制子组件更新
  if (__DEV__ && (prevChildren || nextChildren) && isHmrUpdating) {
    return true
  }

  // 有指令或过渡的组件 vnode，强制更新
  if (nextVNode.dirs || nextVNode.transition) {
    return true
  }

  if (optimized && patchFlag >= 0) {
    // 编译器优化路径
    if (patchFlag & PatchFlags.DYNAMIC_SLOTS) {
      // 动态 slots（如 v-for 中的 slot）需要更新
      return true
    }
    if (patchFlag & PatchFlags.FULL_PROPS) {
      // 完整 props 比对
      if (!prevProps) {
        return !!nextProps
      }
      return hasPropsChanged(prevProps, nextProps!, emits)
    } else if (patchFlag & PatchFlags.PROPS) {
      // 仅比对动态 props
      const dynamicProps = nextVNode.dynamicProps!
      for (let i = 0; i < dynamicProps.length; i++) {
        const key = dynamicProps[i]
        if (
          nextProps![key] !== prevProps![key] &&
          !isEmitListener(emits, key)
        ) {
          return true
        }
      }
    }
  } else {
    // 手写渲染函数路径
    // 有子内容（slots）且不稳定 → 需要更新
    if (prevChildren || nextChildren) {
      if (!nextChildren || !(nextChildren as any).$stable) {
        return true
      }
    }
    // props 引用相同 → 不需要更新
    if (prevProps === nextProps) {
      return false
    }
    // 旧 props 为空，新 props 不为空 → 需要更新
    if (!prevProps) {
      return !!nextProps
    }
    // 新 props 为空 → 需要更新
    if (!nextProps) {
      return true
    }
    // 完整 props 比对
    return hasPropsChanged(prevProps, nextProps, emits)
  }

  return false
}

function hasPropsChanged(
  prevProps: Data,
  nextProps: Data,
  emitsOptions: ComponentInternalInstance['emitsOptions'],
): boolean {
  const nextKeys = Object.keys(nextProps)
  if (nextKeys.length !== Object.keys(prevProps).length) {
    return true
  }
  for (let i = 0; i < nextKeys.length; i++) {
    const key = nextKeys[i]
    if (
      nextProps[key] !== prevProps[key] &&
      !isEmitListener(emitsOptions, key)
    ) {
      return true
    }
  }
  return false
}

<Child @update:modelValue="handler" />

<!-- App.vue -->
<template>
  <div>
    hello world
    <hello :msg="msg" />
    <button @click="changeMsg">修改 msg</button>
  </div>
</template>
<script setup>
import { ref } from 'vue'
import Hello from './hello.vue'

const msg = ref('你好')
function changeMsg() {
  msg.value = '你好啊，我变了'
}
</script>

<!-- hello.vue -->
<template>
  <div>{{ msg }}</div>
</template>
<script setup>
defineProps({
  msg: String
})
</script>

<div>
  <p>静态文本</p>
  <p>静态文本</p>
  <p>静态文本</p>
  <p>{{ dynamicText }}</p>
</div>

// 编译器生成的渲染函数伪代码
function render() {
  return (
    openBlock(),       // 开启一个新的 Block 上下文
    createBlock('div', null, [
      createVNode('p', null, '静态文本', PatchFlags.HOISTED),   // 静态节点，不收集
      createVNode('p', null, '静态文本', PatchFlags.HOISTED),   // 静态节点，不收集
      createVNode('p', null, '静态文本', PatchFlags.HOISTED),   // 静态节点，不收集
      createVNode('p', null, dynamicText, PatchFlags.TEXT),     // 动态节点，收集到 Block
    ])
  )
}

Block.dynamicChildren = [ VNode<p>{{ dynamicText }}</p> ]

// packages/runtime-core/src/renderer.ts
const patchBlockChildren: PatchBlockChildrenFn = (
  oldChildren,
  newChildren,
  fallbackContainer,
  parentComponent,
  parentSuspense,
  namespace: ElementNamespace,
  slotScopeIds,
) => {
  for (let i = 0; i < newChildren.length; i++) {
    const oldVNode = oldChildren[i]
    const newVNode = newChildren[i]
    // 确定容器（父元素）
    const container =
      oldVNode.el &&
      (oldVNode.type === Fragment ||
        !isSameVNodeType(oldVNode, newVNode) ||
        oldVNode.shapeFlag & (ShapeFlags.COMPONENT | ShapeFlags.TELEPORT))
        ? hostParentNode(oldVNode.el)!
        : fallbackContainer
    patch(
      oldVNode,
      newVNode,
      container,
      null,
      parentComponent,
      parentSuspense,
      namespace,
      slotScopeIds,
      true /* optimized */,
    )
  }
}

if (dynamicChildren) {
  // 靶向更新路径
  patchBlockChildren(
    n1.dynamicChildren!,
    dynamicChildren,
    el,
    parentComponent,
    parentSuspense,
    resolveChildrenNamespace(n2, namespace),
    slotScopeIds,
  )
} else if (!optimized) {
  // 全量 diff 路径
  patchChildren(
    n1,
    n2,
    el,
    null,
    parentComponent,
    parentSuspense,
    resolveChildrenNamespace(n2, namespace),
    slotScopeIds,
    false,
  )
}

// packages/runtime-core/src/renderer.ts
const patchKeyedChildren = (
  c1: VNode[],
  c2: VNodeArrayChildren,
  container: RendererElement,
  parentAnchor: RendererNode | null,
  parentComponent: ComponentInternalInstance | null,
  parentSuspense: SuspenseBoundary | null,
  namespace: ElementNamespace,
  slotScopeIds: string[] | null,
  optimized: boolean,
) => {
  let i = 0
  const l2 = c2.length
  let e1 = c1.length - 1 // 旧节点的尾部索引
  let e2 = l2 - 1         // 新节点的尾部索引

  // 1. sync from start
  // (a b) c
  // (a b) d e
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = (c2[i] = optimized
      ? cloneIfMounted(c2[i] as VNode)
      : normalizeVNode(c2[i]))
    if (isSameVNodeType(n1, n2)) {
      patch(
        n1,
        n2,
        container,
        null,
        parentComponent,
        parentSuspense,
        namespace,
        slotScopeIds,
        optimized,
      )
    } else {
      break
    }
    i++
  }
}

export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
  // 类型相同且 key 相同
  return n1.type === n2.type && n1.key === n2.key
}

  // 2. sync from end
  // a (b c)
  // d e (b c)
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = (c2[e2] = optimized
      ? cloneIfMounted(c2[e2] as VNode)
      : normalizeVNode(c2[e2]))
    if (isSameVNodeType(n1, n2)) {
      patch(
        n1,
        n2,
        container,
        null,
        parentComponent,
        parentSuspense,
        namespace,
        slotScopeIds,
        optimized,
      )
    } else {
      break
    }
    e1--
    e2--
  }

  // 3. common sequence + mount
  // (a b)
  // (a b) c
  // i = 2, e1 = 1, e2 = 2
  // (a b)
  // c (a b)
  // i = 0, e1 = -1, e2 = 0
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1
      // 锚点：如果 nextPos 在新子节点范围内，取其 el 作为插入参照
      // 否则使用 parentAnchor（父容器的末尾锚点）
      const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
      while (i <= e2) {
        patch(
          null,
          (c2[i] = optimized
            ? cloneIfMounted(c2[i] as VNode)
            : normalizeVNode(c2[i])),
          container,
          anchor,
          parentComponent,
          parentSuspense,
          namespace,
          slotScopeIds,
          optimized,
        )
        i++
      }
    }
  }

  // 4. common sequence + unmount
  // (a b) c
  // (a b)
  // i = 2, e1 = 2, e2 = 1
  // a (b c)
  // (b c)
  // i = 0, e1 = 0, e2 = -1
  else if (i > e2) {
    while (i <= e1) {
      unmount(c1[i], parentComponent, parentSuspense, true)
      i++
    }
  }

  // 5. unknown sequence
  // [i ... e1 + 1]: a b [c d e] f g
  // [i ... e2 + 1]: a b [e d c h] f g
  // i = 2, e1 = 4, e2 = 5
  else {
    const s1 = i // 旧子序列起始索引
    const s2 = i // 新子序列起始索引

    // 5.1 build key:index map for newChildren
    const keyToNewIndexMap: Map<PropertyKey, number> = new Map()
    for (i = s2; i <= e2; i++) {
      const nextChild = (c2[i] = optimized
        ? cloneIfMounted(c2[i] as VNode)
        : normalizeVNode(c2[i]))
      if (nextChild.key != null) {
        if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
          warn(
            `Duplicate keys found during update:`,
            JSON.stringify(nextChild.key),
            `Make sure keys are unique.`,
          )
        }
        keyToNewIndexMap.set(nextChild.key, i)
      }
    }

keyToNewIndexMap = {
  e → 2,
  c → 3,
  d → 4,
  i → 5
}

    // 5.2 loop through old children left to be patched and try to patch
    // matching nodes & remove nodes that are no longer present
    let j
    let patched = 0
    const toBePatched = e2 - s2 + 1  // 新子序列中待处理的节点数
    let moved = false                  // 是否需要移动节点
    // used to track whether any node has moved
    let maxNewIndexSoFar = 0           // 追踪遍历过程中遇到的最大新索引
    // works as Map<newIndex, oldIndex>
    // Note that oldIndex is offset by +1
    // and oldIndex = 0 is a special value indicating the new node has
    // no corresponding old node.
    // used for determining longest stable subsequence
    const newIndexToOldIndexMap = new Array(toBePatched)
    for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

    for (i = s1; i <= e1; i++) {
      const prevChild = c1[i]
      if (patched >= toBePatched) {
        // 所有新节点都已更新，剩余旧节点只能被删除
        unmount(prevChild, parentComponent, parentSuspense, true)
        continue
      }
      let newIndex
      if (prevChild.key != null) {
        // 有 key 的节点，通过 keyToNewIndexMap 快速查找
        newIndex = keyToNewIndexMap.get(prevChild.key)
      } else {
        // 无 key 的节点，遍历新子序列查找同类型节点
        for (j = s2; j <= e2; j++) {
          if (
            newIndexToOldIndexMap[j - s2] === 0 &&
            isSameVNodeType(prevChild, c2[j] as VNode)
          ) {
            newIndex = j
            break
          }
        }
      }
      if (newIndex === undefined) {
        // 旧节点不存在于新子序列中，卸载
        unmount(prevChild, parentComponent, parentSuspense, true)
      } else {
        // 记录新节点在旧子序列中的位置（+1 偏移，0 表示新增）
        newIndexToOldIndexMap[newIndex - s2] = i + 1
        // 判断是否有节点移动
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex
        } else {
          moved = true
        }
        // 更新节点
        patch(
          prevChild,
          c2[newIndex] as VNode,
          container,
          null,
          parentComponent,
          parentSuspense,
          namespace,
          slotScopeIds,
          optimized,
        )
        patched++
      }
    }

newIndexToOldIndexMap = [5, 3, 4, 0]
                        ↑  ↑  ↑  ↑
                        e  c  d  i
                        |  |  |  新增节点（0表示旧中不存在）
                        |  |  旧索引3+1=4（d在旧中位置3）
                        |  旧索引2+1=3（c在旧中位置2）
                        旧索引4+1=5（e在旧中位置4）

    // 5.3 move and mount
    // generate longest stable subsequence only when nodes have moved
    const increasingNewIndexSequence = moved
      ? getSequence(newIndexToOldIndexMap)
      : EMPTY_ARR
    j = increasingNewIndexSequence.length - 1
    // looping backwards so that we can use last patched node as anchor
    for (i = toBePatched - 1; i >= 0; i--) {
      const nextIndex = s2 + i
      const nextChild = c2[nextIndex] as VNode
      const anchor =
        nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
      if (newIndexToOldIndexMap[i] === 0) {
        // mount new
        patch(
          null,
          nextChild,
          container,
          anchor,
          parentComponent,
          parentSuspense,
          namespace,
          slotScopeIds,
          optimized,
        )
      } else if (moved) {
        // move if:
        // There is no stable subsequence (e.g. a reverse)
        // OR current node is not among the stable sequence
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
          move(nextChild, container, anchor, MoveType.REORDER)
        } else {
          j--
        }
      }
    }
  }

newIndexToOldIndexMap = [5, 3, 4, 0]

// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {
  const p = arr.slice()  // 回溯数组，记录每个元素的前驱索引
  const result = [0]      // result 存储的是索引，不是值
  let i, j, u, v, c
  const len = arr.length

  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {  // 0 表示新增节点，跳过
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        // 当前值大于 result 末尾对应的值，可以追加
        p[i] = j           // 记录前驱
        result.push(i)     // 追加当前索引
        continue
      }

      // 二分查找：在 result 中找到第一个 >= arrI 的位置
      u = 0
      v = result.length - 1
      while (u < v) {
        c = (u + v) >> 1  // 等价于 Math.floor((u + v) / 2)
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]  // 记录前驱
        }
        result[u] = i           // 替换
      }
    }
  }

  // 回溯：从 result 的最后一个元素开始，通过 p 数组还原正确的索引序列
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

u = 4, v = result[3] = 6
  result[3] = 6, v = p[6] = 2
  result[2] = 2, v = p[2] = 1
  result[1] = 1, v = p[1] = 0
  result[0] = 0, v = p[0] = 0