Vue3源码阅读笔记

2024/1/1：新年快乐，Vue2 一路走好~

Vue3源码结构分析

包的结构

github 上可以看到 Vue3 的代码是在vuejs/core目录下，包当中一些重要的内容如下：

• pnpm：提供多包的能力

• rollup：构建工具，用于打包

此外也可以看到最大的不同就是类型校验的能力从flow转变为了typescript

build 的能力

和 Vue2 类似，build的能力集成在scripts下的build.js中，思路和Vue2相同，只是用的 npm 包不同。

Packages

下面来讲 packages 中核心的几个包：

• compiler-core(核心编译时)

• reactivity(composition API 响应式处理)

• runtime-core(运行时处理)

• vue(demo)

compiler-core

这块对应的是编译生成虚拟 DOM 的能力，也就是 AST 转换的过程。

index.ts

compile 的入口文件最主要的内容就是导出 compile 的内容，所以我们接下去要看 compile.ts 做了什么

export { baseCompile } from './compile'

compile.ts

这块这要是三方面的能力：

export function baseCompile(
  source: string | RootNode,
  options: CompilerOptions = {},
): CodegenResult {
  // 1.
  const ast = isString(source) ? baseParse(source, resolvedOptions) : source
  // 2.
  transform(
    ast,
    extend({}, resolvedOptions, {
      nodeTransforms: [
        ...nodeTransforms,
        ...(options.nodeTransforms || []), // user transforms
      ],
      directiveTransforms: extend(
        {},
        directiveTransforms,
        options.directiveTransforms || {}, // user transforms
      ),
    }),
  )
  // 3.
  return generate(ast, resolvedOptions)
}

1. 将 template 字符串解析成 AST

export function baseParse(input: string, options?: ParserOptions): RootNode {
  reset()
  currentInput = input
  currentOptions = extend({}, defaultParserOptions)

  tokenizer.mode =
    currentOptions.parseMode === 'html'
      ? ParseMode.HTML
      : currentOptions.parseMode === 'sfc'
        ? ParseMode.SFC
        : ParseMode.BASE

  tokenizer.inXML =
    currentOptions.ns === Namespaces.SVG ||
    currentOptions.ns === Namespaces.MATH_ML

  const root = (currentRoot = createRoot([], input))
  tokenizer.parse(currentInput)
  root.loc = getLoc(0, input.length)
  root.children = condenseWhitespace(root.children)
  currentRoot = null
  return root
}

这部分是通过定义Tokenizer类，经过词法分析、语法分析、语义分析，最终生成了 AST。

const tokenizer = new Tokenizer(stack, {
  onerr: emitError,
  ontext(start, end) {...},
  // 插值表达式
  oninterpolation(start, end) {...},
  // 标签
  onopentagname(start, end) {...},
  onopentagend(end) {...},
  onclosetag(start, end) {...},
  // 自闭合标签
  onselfclosingtag(end) {...},
  // 属性名
  onattribname(start, end) {...},
  // v-...指令
  ondirname(start, end) {...}
})

以插值表达式为例，最终会返回的是一个对象，也就是基本的VNode的形式。

export function createInterpolation(
  content: InterpolationNode['content'] | string,
  loc: SourceLocation,
): InterpolationNode {
  return {
    type: NodeTypes.INTERPOLATION,
    loc,
    content: isString(content)
      ? createSimpleExpression(content, false, loc)
      : content,
  }
}

1. 将 AST 通过transform进行转换，因为此时的代码还不符合预期，需要更多定制化的处理

这里首先是通过createTransformContext创建transform上下文

然后通过traverseNode递归地去遍历之前生成的VNode

最后创建helpers，会在生成代码时用到

export function transform(root: RootNode, options: TransformOptions) {
  const context = createTransformContext(root, options)
  traverseNode(root, context)
  if (!options.ssr) {
    createRootCodegen(root, context)
  }
  root.helpers = new Set([...context.helpers.keys()])
}

traverseNode的过程如下，分析写在注释中了：

export function traverseNode(
  node: RootNode | TemplateChildNode,
  context: TransformContext,
) {
  context.currentNode = node
  const { nodeTransforms } = context
  const exitFns = []
  // 这里是类似车间的模式，nodeTransforms中集成了转化text、插值、element等能力
  for (let i = 0; i < nodeTransforms.length; i++) {
    const onExit = nodeTransforms[i](node, context)
    if (onExit) {
      if (isArray(onExit)) {
        exitFns.push(...onExit)
      } else {
        exitFns.push(onExit)
      }
    }
  }
  // 根据节点的type去进行不同的操作
  switch (node.type) {
    case NodeTypes.INTERPOLATION:
      if (!context.ssr) {
        context.helper(TO_DISPLAY_STRING)
      }
      break
    case NodeTypes.ELEMENT:
    case NodeTypes.ROOT:
      traverseChildren(node, context)
      break
  }
  let i = exitFns.length
  while (i--) {
    exitFns[i]()
  }
}

1. 生成最终的代码

export function generate(
  ast: RootNode,
  options: CodegenOptions & {
    onContextCreated?: (context: CodegenContext) => void
  } = {},
): CodegenResult {
  const context = createCodegenContext(ast, options)
  const { mode, push } = context

  const preambleContext = isSetupInlined
    ? createCodegenContext(ast, options)
    : context
  if (!__BROWSER__ && mode === 'module') {
    genModulePreamble(ast, preambleContext, genScopeId, isSetupInlined)
  } else {
    genFunctionPreamble(ast, preambleContext)
  }
  
  const functionName = `render`
  const args = ['_ctx', '_cache']

  const signature =
    !__BROWSER__ && options.isTS
      ? args.map(arg => `${arg}: any`).join(',')
      : args.join(', ')

  push(`function ${functionName}(${signature}) {`)

  push(`return `)
  genNode(ast.codegenNode, context)
  push(`}`)

  return {
    ast,
    code: context.code
  }
}

其中，createCodegenContext创建了生成代码的上下文：

function createCodegenContext(
  ast: RootNode,
  {
    mode = 'function',
  }: CodegenOptions,
): CodegenContext {
  const context: CodegenContext = {
    mode,
    helper(key) {
      return `_${helperNameMap[key]}`
    },
    push(code, newlineIndex = NewlineType.None, node) {
      context.code += code
    }
  }
  return context
}

genModulePreamble提供了模块引入的相关编译能力

也就是对import xx as xx from 'vue'的编译

function genModulePreamble(
  ast: RootNode,
  context: CodegenContext
) {
  const { push } = context

  if (ast.helpers.size) {
    const helpers = Array.from(ast.helpers)
    push(
      `import { ${helpers
        .map(s => `${helperNameMap[s]} as _${helperNameMap[s]}`)
        .join(', ')} } from ${JSON.stringify(runtimeModuleName)}\n`,
      NewlineType.End,
    )
  }
  newline()
  push(`export `)
}

genFunctionPreamble则是对const {} = Vue这样的引入的编译

function genFunctionPreamble(ast: RootNode, context: CodegenContext) {
  const {
    push,
    newline,
    runtimeModuleName,
    runtimeGlobalName,
  } = context
  const VueBinding = runtimeGlobalName
  const helpers = Array.from(ast.helpers)
  if (helpers.length > 0) {
    push(`const _Vue = ${VueBinding}\n`, NewlineType.End)
    const staticHelpers = [
      CREATE_VNODE,
      CREATE_ELEMENT_VNODE,
      CREATE_COMMENT,
      CREATE_TEXT,
      CREATE_STATIC,
    ]
      .filter(helper => helpers.includes(helper))
      .map(aliasHelper)
      .join(', ')
    push(`const { ${staticHelpers} } = _Vue\n`, NewlineType.End)
  }
  newline()
  push(`return `)
}

到此，其实就是通过模板字符串拼接的动作，生成了Vue API能够识别的语言。

reactivity 响应式处理

这里可以看到，在导出代码的同时，这个包当中还提供了对应的测试用例，这块是vitest提供的能力，所以我们如果自己要做第三方库，要考虑到提供代码、类型声明文件、demo、文档以及测试用例。

index.ts

可以看到入口导出的是各种各样的composition API

export {
  ref,
  shallowRef,
  isRef,
  toRef,
  toValue,
  toRefs,
  unref,
  proxyRefs,
  customRef,
  triggerRef
} from './ref'
export {
  reactive,
  readonly,
  isReactive,
  isReadonly,
  isShallow,
  isProxy,
  shallowReactive,
  shallowReadonly,
  markRaw,
  toRaw
} from './reactive'
export {
  computed
} from './computed'
export { deferredComputed } from './deferredComputed'
export {
  effect,
  stop,
  enableTracking,
  pauseTracking,
  resetTracking,
  pauseScheduling,
  resetScheduling,
  ReactiveEffect
} from './effect'
export { trigger, track, ITERATE_KEY } from './reactiveEffect'
export {
  effectScope,
  EffectScope,
  getCurrentScope,
  onScopeDispose,
} from './effectScope'
export { TrackOpTypes, TriggerOpTypes, ReactiveFlags } from './constants'

reactive.ts

在reactive当中，可以看到他创建了很多的WeakMap，这是为了更好地进行代码依赖的回收。

export const reactiveMap = new WeakMap<Target, any>()
export const shallowReactiveMap = new WeakMap<Target, any>()
export const readonlyMap = new WeakMap<Target, any>()
export const shallowReadonlyMap = new WeakMap<Target, any>()

接下去是去调用createReactiveObject，根据不同的类型传入不同的Map和Handler。

可以看到返回的就是proxy，首先判断Map中是否存在proxy，如果存在就返回，不存在就new Proxy

所以重点就是Handler做了什么

function createReactiveObject(
  target: Target,
  isReadonly: boolean,
  baseHandlers: ProxyHandler<any>,
  collectionHandlers: ProxyHandler<any>,
  proxyMap: WeakMap<Target, any>,
) {
  const existingProxy = proxyMap.get(target)
  if (existingProxy) {
    return existingProxy
  }
  const proxy = new Proxy(
    target,
    targetType === TargetType.COLLECTION ? collectionHandlers : baseHandlers,
  )
  proxyMap.set(target, proxy)
  return proxy
}

baseHandler.ts

baseReactiveHandler

每个handler其实都会传入isReadonly和shallow两个属性，接下去会做一些处理

• 在isReadonly为true时，数据不能被set，就不需要收集依赖了。

• 在shallow为true是，直接返回表层的数据

• 在res是对象isReadonly为false时，就把内部所有对象用reactive包裹，相当于递归调用

class BaseReactiveHandler implements ProxyHandler<Target> {
  constructor(
    protected readonly _isReadonly = false,
    protected readonly _shallow = false,
  ) {}

  get(target: Target, key: string | symbol, receiver: object) {
    const isReadonly = this._isReadonly,
      shallow = this._shallow
    if (key === ReactiveFlags.IS_REACTIVE) {
      return !isReadonly
    } else if (key === ReactiveFlags.IS_READONLY) {
      return isReadonly
    } else if (key === ReactiveFlags.IS_SHALLOW) {
      return shallow
    } else if (key === ReactiveFlags.RAW) {
      if (
        receiver ===
          (isReadonly
            ? shallow
              ? shallowReadonlyMap
              : readonlyMap
            : shallow
              ? shallowReactiveMap
              : reactiveMap
          ).get(target) ||
        Object.getPrototypeOf(target) === Object.getPrototypeOf(receiver)
      ) {
        return target
      }
      return
    }

    const targetIsArray = isArray(target)
    if (!isReadonly) {
      if (targetIsArray && hasOwn(arrayInstrumentations, key)) {
        return Reflect.get(arrayInstrumentations, key, receiver)
      }
      if (key === 'hasOwnProperty') {
        return hasOwnProperty
      }
    }
    const res = Reflect.get(target, key, receiver)
    if (isSymbol(key) ? builtInSymbols.has(key) : isNonTrackableKeys(key)) {
      return res
    }
    if (!isReadonly) {
    // 在触发get的时候进行依赖收集
      track(target, TrackOpTypes.GET, key)
    }
    if (shallow) {
      return res
    }
    if (isRef(res)) {
      return targetIsArray && isIntegerKey(key) ? res : res.value
    }
    if (isObject(res)) {
      return isReadonly ? readonly(res) : reactive(res)
    }
    return res
  }
}

MutableReactiveHandler

上面只进行了get时的处理，接下去要做set时的处理

class MutableReactiveHandler extends BaseReactiveHandler {
  constructor(shallow = false) {
    super(false, shallow)
  }

  set(
    target: object,
    key: string | symbol,
    value: unknown,
    receiver: object,
  ): boolean {
    const result = Reflect.set(target, key, value, receiver)
    
    if (target === toRaw(receiver)) {
      if (!hadKey) {
        // 在触发 set 的时候进行触发依赖
        trigger(target, TriggerOpTypes.ADD, key, value)
      } else if (hasChanged(value, oldValue)) {
        trigger(target, TriggerOpTypes.SET, key, value, oldValue)
      }
    }
    return result
  }
}

trigger

trigger负责在set的时候触发依赖

export function trigger(
  target: object,
  type: TriggerOpTypes,
  key?: unknown,
  newValue?: unknown,
  oldValue?: unknown,
  oldTarget?: Map<unknown, unknown> | Set<unknown>,
) {
  const depsMap = targetMap.get(target)
  if (!depsMap) {
    return
  }
  // 先收集deps
  let deps: (Dep | undefined)[] = []
  depsMap.forEach((dep, key) => {
    deps.push(dep)
  })

  pauseScheduling()
  for (const dep of deps) {
    if (dep) {
      triggerEffects(dep)
    }
  }
  resetScheduling()
}

其他API

其他的的API通过ReactiveFlags中的属性去处理，例如isReactive：

export function isReactive(value: unknown): boolean {
  if (isReadonly(value)) {
    return isReactive((value as Target)[ReactiveFlags.RAW])
  }
  return !!(value && (value as Target)[ReactiveFlags.IS_REACTIVE])
}

其中，ReactiveFlags声明如下：

export enum ReactiveFlags {
  SKIP = '__v_skip',
  IS_REACTIVE = '__v_isReactive',
  IS_READONLY = '__v_isReadonly',
  IS_SHALLOW = '__v_isShallow',
  RAW = '__v_raw',
}

runtime-core

index.ts

这里暴露了大量的API，这里关注export { h } from './h'和createAppAPI

h.ts

这里就是h函数的声明，可以看到就是根据传入的参数去调用createVNode

export function h(type: any, propsOrChildren?: any, children?: any): VNode {
  const l = arguments.length
  if (l === 2) {
    if (isObject(propsOrChildren) && !isArray(propsOrChildren)) {
      // single vnode without props
      if (isVNode(propsOrChildren)) {
        return createVNode(type, null, [propsOrChildren])
      }
      // props without children
      return createVNode(type, propsOrChildren)
    } else {
      // omit props
      return createVNode(type, null, propsOrChildren)
    }
  } else {
    if (l > 3) {
      children = Array.prototype.slice.call(arguments, 2)
    } else if (l === 3 && isVNode(children)) {
      children = [children]
    }
    return createVNode(type, propsOrChildren, children)
  }
}

createApp

这块创建了我们的App，包含我们开发时挂载到App上的很多内容的创建

export function createAppAPI<HostElement>(
  render: RootRenderFunction<HostElement>,
  hydrate?: RootHydrateFunction,
): CreateAppFunction<HostElement> {
  return function createApp(rootComponent, rootProps = null) {
    if (!isFunction(rootComponent)) {
      rootComponent = extend({}, rootComponent)
    }

    const context = createAppContext()
    const installedPlugins = new WeakSet()

    let isMounted = false

    const app: App = (context.app = {
      _uid: uid++,
      _component: rootComponent as ConcreteComponent,
      _props: rootProps,
      _container: null,
      _context: context,
      _instance: null,

      version,

      use(plugin: Plugin, ...options: any[]) {},

      mixin(mixin: ComponentOptions) {},

      component(name: string, component?: Component): any {},

      directive(name: string, directive?: Directive) {},

      mount(
        rootContainer: HostElement,
        isHydrate?: boolean,
        namespace?: boolean | ElementNamespace,
      ): any {},

      unmount() {},

      provide(key, value) {},
    })

    return app
  }
}

重点去看mount，主要分成两部分的内容，首先是创建根节点，然后就是调用render渲染根节点

mount(
  rootContainer: HostElement,
  isHydrate?: boolean,
  namespace?: boolean | ElementNamespace,
): any {
  if (!isMounted) {
    const vnode = createVNode(rootComponent, rootProps)
    vnode.appContext = context

    render(vnode, rootContainer, namespace)
    isMounted = true
    app._container = rootContainer

    return getExposeProxy(vnode.component!) || vnode.component!.proxy
  }
},

render

其实render这部分就是调用patch，这部分 Vue2 和 Vue3 没有区别，只是 diff 算法不同。

const render: RootRenderFunction = (vnode, container, namespace) => {
  if (vnode == null) {
    if (container._vnode) {
      unmount(container._vnode, null, null, true)
    }
  } else {
    patch(
      container._vnode || null,
      vnode,
      container,
      null,
      null,
      null,
      namespace,
    )
  }
  flushPreFlushCbs()
  flushPostFlushCbs()
  container._vnode = vnode
}

runtime-dom

Vue3靠虚拟dom，实现跨平台的能力，runtime-dom提供一个渲染器，这个渲染器可以渲染虚拟dom节点到指定的容器中，这就有点类似于react中的react-dom。

Vue3 diff

Vue3 diff算法的入口是patchChildren函数，位于runtime-core包下的renderer.ts中

const patchChildren: PatchChildrenFn = (...) => {
  const c1 = n1 && n1.children
  const prevShapeFlag = n1 ? n1.shapeFlag : 0
  const c2 = n2.children
  const { patchFlag, shapeFlag } = n2
  // 非全量diff，patchFlag > 0说明有动态属性
  if (patchFlag > 0) {
    // 分为子节点带key和不带key两种情况讨论
    if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
      patchKeyedChildren(...)
      return
    } else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
      // unkeyed
      patchUnkeyedChildren(...)
      return
    }
  }
  // 如果是文本节点
  if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
    // 旧虚拟节点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(...)
      } else {
        // 如果新虚拟节点没有子节点了，那么就卸载就虚拟节点的子节点
        unmountChildren(c1 as VNode[], parentComponent, parentSuspense, true)
      }
    } else {
      // 旧虚拟节点是null或者文本，新虚拟节点是数组或者null
      if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
        hostSetElementText(container, '')
      }
      // 挂载新的虚拟节点
      if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        mountChildren(...)
      }
    }
  }
}

那么我们接下去看没有key和有key的情况下的patch

patchUnkeyedChildren

const patchUnkeyedChildren = (...) => {
  c1 = c1 || EMPTY_ARR
  c2 = c2 || EMPTY_ARR
  const oldLength = c1.length
  const newLength = c2.length
  // 取新旧节点当中较短的长度作为公共长度
  const commonLength = Math.min(oldLength, newLength)
  let i
  // 这里就是递归的操作
  for (i = 0; i < commonLength; i++) {
    const nextChild = (c2[i] = optimized
      ? cloneIfMounted(c2[i] as VNode)
      : normalizeVNode(c2[i]))
    patch(...)
  }
  // 如果旧的子节点长度大于新的，那么就说明旧子节点需要卸载
  if (oldLength > newLength) {
    unmountChildren(...)
  } else {
    // 挂载新的子节点
    mountChildren(...)
  }
}

patchKeyedChildren

这里是Vue3 diff算法的核心

const patchKeyedChildren = (...) => {
  let i = 0
  const l2 = c2.length
  let e1 = c1.length - 1 // 指针指向旧的尾节点
  let e2 = l2 - 1 // 新尾节点指针
  ...
}

1.从头开始，遍历直到不相等为止，对相等的部分执行patch

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

2.从尾节点开始向前遍历直到不相等为止，对相同的部分执行patch

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.如果旧的节点已经被处理完了，而新的节点还没有，就要通过patch将新增节点挂载到正确的位置

if (i > e1) {
  if (i <= e2) {
    const nextPos = e2 + 1
    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.如果旧节点还没遍历完，但新节点已经遍历完了，就进行unmount

else if (i > e2) {
  while (i <= e1) {
    unmount(c1[i], parentComponent, parentSuspense, true)
    i++
  }
}

5.如果第一次从前往后遍历和从后往前遍历之后，没有出现只剩下新增节点或是删除节点的情况下

• 首先，构建索引表，建立新节点的key和位置的映射。

const s1 = i
const s2 = i
const keyToNewIndexMap: Map<string | number | symbol, 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)
  }
}

• 构建新节点在旧节点中的索引的映射（数组）

let j
let patched = 0
const toBePatched = e2 - s2 + 1
let moved = false
let maxNewIndexSoFar = 0
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) {
    newIndex = keyToNewIndexMap.get(prevChild.key)
  } else {
    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 {
    newIndexToOldIndexMap[newIndex - s2] = i + 1
    if (newIndex >= maxNewIndexSoFar) {
      maxNewIndexSoFar = newIndex
    } else {
      moved = true
    }
    patch(...)
    patched++
  }
}

• 计算最长递增子序列，将剩下的部分进行移动，最终挂载

const increasingNewIndexSequence = moved
  ? getSequence(newIndexToOldIndexMap)
  : EMPTY_ARR
j = increasingNewIndexSequence.length - 1
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) {
    patch(...)
  } else if (moved) {
    if (j < 0 || i !== increasingNewIndexSequence[j]) {
      move(nextChild, container, anchor, MoveType.REORDER)
    } else {
      j--
    }
  }
}

getSequence

Vue3通过贪心+二分的方法获取最长递增子序列，注意这里要获取的是最长递增子序列而不是它的长度，所以要对原算法进行改造，result存储的就是长度为i的递增子序列最小末位置的索引，具体代码如下：

function getSequence(arr: number[]): number[] {
  const p = arr.slice()
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        p[i] = j
        result.push(i)
        continue
      }
      u = 0
      v = result.length - 1
      // 二分查找，找到比arrI小的节点，更新result的值
      while (u < v) {
        c = (u + v) >> 1
        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
      }
    }
  }
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

虽然动态规划也可以实现最长递增子序列，但是需要两层循环去根据之前的最长递增子序列推导出 i+1 位置的情况，时间复杂度是O(n^2)

因此，贪心+二分是更好地选择，时间复杂度是O(nlogn)。