Vue3 Dom Diff算法核心逻辑解析一、什么是虚拟DOM 虚拟 DOM (Virtual DOM，简称 VDOM)

站长

2024年10月09日 15:33 · 阅读数 41

一、什么是虚拟DOM

虚拟 DOM (Virtual DOM，简称 VDOM) 是一种编程概念，意为将目标所需的 UI 通过数据结构“虚拟”地表示出来，保存在内存中，然后将真实的 DOM 与之保持同步

通过图片对比一下真实Dom和虚拟Dom

真实Dom打印
虚拟Dom打印从上面的两张图中我们可以清晰的对比出，虚拟Dom的确要比真实的Dom轻量很多

二、为何需要虚拟DOM

框架设计 vue在在运行前会把我们的模板代码最终编译为一个render函数这个设计就会需要每次在一个状态发生改变的时候，vue会重新运行这个render函数，如果每次都全量的将这些变化直接应用到页面上效率会非常低，所以为了尽可能的去复用没有变化的元素，所以先转为虚拟dom这个中间状态，每次变化时再去比较新旧两份虚拟dom，最后找到变化的部分再去应用到页面上。详见下图
跨平台如果vue每次更新都直接应用到页面里面的dom，那vue就只能在浏览器环境中使用了，但是有了虚拟dom这个中间层，它只是一个轻量的对象表示形式，如果用vue来开发小程序或者一些原生组件的时候，也可以通过虚拟dom去对应到原生的组件，从而实现跨平台开发。

三、Vue3 Diff细节

Diff入口patch函数

我们先从虚拟DOM更新机制的核心部分patch函数看起，它负责对比新旧虚拟DOM，并将变化高效地应用到实际的DOM中，这个方法定义在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,
  ) => {
    // 新旧节点是一个  退出patch
    if (n1 === n2) {
      return
    }

    // 新旧节点类型不同， 卸载旧的
    // n1.type === n2.type && n1.key === n2.key
    if (n1 && !isSameVNodeType(n1, n2)) {
      // 获得新节点插入的参照节点
      // parentNode.insertBefore(child, referenceNode)
      anchor = getNextHostNode(n1)
      // 卸载节点和它对应的真实DOM
      unmount(n1, parentComponent, parentSuspense, true)
      n1 = null
    }

    if (n2.patchFlag === PatchFlags.BAIL) {
      // 退出优化模式，并执行完整的虚拟DOM对比，确保正确更新 DOM
       // <component :is="vnode"/> 这种类型的写法patchFlag为PatchFlags.BAIL
      // 通过Vue模板在编译成渲染函数时，Vue会做一些编译时的优化，从而提高运行时性能
      optimized = false
      // 清空动态变化子节点
      // 内部结构稳定的块，dynamicChildren用于存储带有跟新标记的子节点
      // 在patch的时候只去比较这个里面存储的子节点数据
      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:
         // 静态节点
         // 比如<p>静态</p>, 模板内容是静态的，只有首次渲染的时候挂载
         // 后续diff的时候, 跳过这类节点的比较
        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) {
          // vNode是普通的 DOM 元素
          processElement(
            n1,
            n2,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            namespace,
            slotScopeIds,
            optimized,
          )
        } else if (shapeFlag & ShapeFlags.COMPONENT) {
          // vNode是一个vue组件
          processComponent(
            n1,
            n2,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            namespace,
            slotScopeIds,
            optimized,
          )
        } else if (shapeFlag & ShapeFlags.TELEPORT) {
          // vNode是一个Teleport组件节点
          ;(type as typeof TeleportImpl).process(
            n1 as TeleportVNode,
            n2 as TeleportVNode,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            namespace,
            slotScopeIds,
            optimized,
            internals,
          )
        } else if (__FEATURE_SUSPENSE__ && shapeFlag & ShapeFlags.SUSPENSE) {
          // vNode是一个Suspense组件节点
          ;(type as typeof SuspenseImpl).process(
            n1,
            n2,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            namespace,
            slotScopeIds,
            optimized,
            internals,
          )
        } else if (__DEV__) {
          warn('Invalid VNode type:', type, `(${typeof type})`)
        }
    }

    // 设置或更新ref引用  如果是组件引用的是组件实例，如果是DOM元素引用的是DOM元素
    if (ref != null && parentComponent) {
      setRef(ref, n1 && n1.ref, parentSuspense, n2 || n1, !n2)
    }
  }

processElement函数逻辑

从patch函数中可以看出，vue3在做页面更新的时候，针对不同类型的虚拟DOM分别做了不同的处理，现在来具体看一下虚拟DOM类型是元素时的处理逻辑

  const processElement = (
    n1: VNode | null,
    n2: VNode,
    container: RendererElement,
    anchor: RendererNode | null,
    parentComponent: ComponentInternalInstance | null,
    parentSuspense: SuspenseBoundary | null,
    namespace: ElementNamespace,
    slotScopeIds: string[] | null,
    optimized: boolean,
  ) => {
    // svg和math特殊处理
    // 因为需要相应的命名空间来渲染这些特殊的元素,否则不会正常工作
    // document.createElementNS("http://www.w3.org/2000/svg", "svg")
    // document.createElementNS("http://www.w3.org/1998/Math/MathML", "math")
    if (n2.type === 'svg') {
      namespace = 'svg'
    } else if (n2.type === 'math') {
      namespace = 'mathml'
    }
    
    // 旧节点点为null，表明新节点是新增节点
    if (n1 == null) {
      // 创建新的dom元素，并将它插入到容器的anchor的位置
      mountElement(
        n2,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        namespace,
        slotScopeIds,
        optimized,
      )
    } else {
     // 旧节点不为空，说明现在需要更新
     // 调用patchElement函数，对比新旧节点的差异，并对已有的DOM进行更新
      patchElement(
        n1,
        n2,
        parentComponent,
        parentSuspense,
        namespace,
        slotScopeIds,
        optimized,
      )
    }
  }

patchElement函数逻辑

调用patchElement函数对比出节点的差异，并将变化的部分更新到已有的DOM中

  const patchElement = (
    n1: VNode,
    n2: VNode,
    parentComponent: ComponentInternalInstance | null,
    parentSuspense: SuspenseBoundary | null,
    namespace: ElementNamespace,
    slotScopeIds: string[] | null,
    optimized: boolean,
  ) => {
    // 新旧节点共享DOM元素的引用
    const el = (n2.el = n1.el!)
    // dirs 表示元素上绑定的指令
    let { patchFlag, dynamicChildren, dirs } = n2
    // 合并新旧节点的patchFlag， 这个主要是为了解决开发调用cloneVNode的一些边界情况
    patchFlag |= n1.patchFlag & PatchFlags.FULL_PROPS
    const oldProps = n1.props || EMPTY_OBJ
    const newProps = n2.props || EMPTY_OBJ
    let vnodeHook: VNodeHook | undefined | null

    // disallow recurse in vnode/directive beforeUpdate hooks
    parentComponent && toggleRecurse(parentComponent, false)
    if ((vnodeHook = newProps.onVnodeBeforeUpdate)) {
      // 执行VNode更新前的钩子函数
      invokeVNodeHook(vnodeHook, parentComponent, n2, n1)
    }
    if (dirs) {
      // 执行指令的beforeUpdate钩子
      invokeDirectiveHook(n2, n1, parentComponent, 'beforeUpdate')
    }
    parentComponent && toggleRecurse(parentComponent, true)


    // 旧节点包含innerHTML或textContent属性，但新节点没有这些属性时，需要清空元素的内容
    if (
      (oldProps.innerHTML && newProps.innerHTML == null) ||
      (oldProps.textContent && newProps.textContent == null)
    ) {
      hostSetElementText(el, '')
    }

    if (dynamicChildren) {
      // 只更新动态变化的子节点
      // 比如下面这个结构 第一个span标签是静态节点，其他span标签就是dynamicChildren
      /**
      *  <div> 
      *   <span>Static text</span>
      *   <span>{{ dynamicText }}</span>
      *   <span>{{ dynamicText }}</span>
      *  </div>
      **/
      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,
      )
    }

    if (patchFlag > 0) {
      // patchFlag存在表明这个这个元素的渲染代码是由编译器生成，所以diff时可以走捷径
      // 根据不同的更新标记，可以快速判断出节点的哪些部分需要更新
      if (patchFlag & PatchFlags.FULL_PROPS) {
        // 元素属性包含多个动态的key，需要全量diff.类似下面这种，具体绑定的值
        // 编译时无法确认
        // <div v-bind="someObject" :[foo]="bar"></div>
        patchProps(el, oldProps, newProps, parentComponent, namespace)
      } else {
        if (patchFlag & PatchFlags.CLASS) {
          // 有动态的class绑定
          if (oldProps.class !== newProps.class) {
            hostPatchProp(el, 'class', null, newProps.class, namespace)
          }
        }

        if (patchFlag & PatchFlags.STYLE) {
          // 有动态的style绑定
          hostPatchProp(el, 'style', oldProps.style, newProps.style, namespace)
        }

        if (patchFlag & PatchFlags.PROPS) {
          // 除了class和style以外的一些动态属性绑定
          const propsToUpdate = n2.dynamicProps!
          for (let i = 0; i < propsToUpdate.length; i++) {
            const key = propsToUpdate[i]
            const prev = oldProps[key]
            const next = newProps[key]
            // 只更新发生变化的属性和value属性
            if (next !== prev || key === 'value') {
              hostPatchProp(el, key, prev, next, namespace, parentComponent)
            }
          }
        }
      }

      if (patchFlag & PatchFlags.TEXT) {
        // 这个元素只包含动态文本子节点， 更新文本内容
        if (n1.children !== n2.children) {
          hostSetElementText(el, n2.children as string)
        }
      }
    } else if (!optimized && dynamicChildren == null) {
      // 不走优化全量diff
      patchProps(el, oldProps, newProps, parentComponent, namespace)
    }

    if ((vnodeHook = newProps.onVnodeUpdated) || dirs) {
      queuePostRenderEffect(() => {
        // 在VNode更新完成后，执行VNode更新后的钩子函数
        vnodeHook && invokeVNodeHook(vnodeHook, parentComponent, n2, n1)
        // 执行指令的 `updated` 钩子
        dirs && invokeDirectiveHook(n2, n1, parentComponent, 'updated')
      }, parentSuspense)
    }
  }

patchChildren函数逻辑

接下来再来看下全量diff子节点的patchChildren函数的逻辑

  const patchChildren: PatchChildrenFn = (
    n1,
    n2,
    container,
    anchor,
    parentComponent,
    parentSuspense,
    namespace: ElementNamespace,
    slotScopeIds,
    optimized = false,
  ) => {
    // 旧子节点
    const c1 = n1 && n1.children
    // 旧 shapeFlag
    const prevShapeFlag = n1 ? n1.shapeFlag : 0
    // 新子节点
    const c2 = n2.children

    const { patchFlag, shapeFlag } = n2
    if (patchFlag > 0) {
      if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
        // 更新带有key的子节点列表（子节点全都有key或部分有key）
        patchKeyedChildren(
          c1 as VNode[],
          c2 as VNodeArrayChildren,
          container,
          anchor,
          parentComponent,
          parentSuspense,
          namespace,
          slotScopeIds,
          optimized,
        )
        return
      } else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
        // 更新没有key的子节点列表
        patchUnkeyedChildren(
          c1 as VNode[],
          c2 as VNodeArrayChildren,
          container,
          anchor,
          parentComponent,
          parentSuspense,
          namespace,
          slotScopeIds,
          optimized,
        )
        return
      }
    }
    
    // 虚拟DOM的子节点只会有三种情况： 数组、文本、或者没有子节点
    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,
          )
        }
      }
    }
  }

patchUnkeyedChildren函数逻辑

上面patchChildren函数逻辑中，如果新旧节点的子节点都是列表，并且子节点没有key属性就会执行patchUnkeyedChildren函数，接下来我们看下这个函数的具体逻辑

 const patchUnkeyedChildren = (
    c1: VNode[],
    c2: VNodeArrayChildren,
    container: RendererElement,
    anchor: RendererNode | null,
    parentComponent: ComponentInternalInstance | null,
    parentSuspense: SuspenseBoundary | null,
    namespace: ElementNamespace,
    slotScopeIds: string[] | null,
    optimized: boolean,
  ) => {
    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]))
      // 循环公共部分，对每个同级的虚拟DOM进行patch
      patch(
        c1[i],
        nextChild,
        container,
        null,
        parentComponent,
        parentSuspense,
        namespace,
        slotScopeIds,
        optimized,
      )
    }
    // 遍历结束
    if (oldLength > newLength) {
      // 如果还有旧节点，卸载旧节点
      unmountChildren(
        c1,
        parentComponent,
        parentSuspense,
        true,
        false,
        commonLength,
      )
    } else {
      // 如果还有新节点 挂载新节点
      mountChildren(
        c2,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        namespace,
        slotScopeIds,
        optimized,
        commonLength,
      )
    }
  }

patchKeyedChildren函数逻辑

当比较两个带有key值的虚拟节点列表的时候，内部会调用patchkeyedChildren对子节点进一步比较，这个函数主要分为五个主要的步骤，接下来我们来拆解这些对比的步骤

第一步从头部开始比较

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 // prev ending index
    // 新尾部指针
    let e2 = l2 - 1 // next ending index
    
    // 从头部开始比较
    while (i <= e1 && i <= e2) {
      // 头部指针小于等于两个尾部指针
      const n1 = c1[i]
      const n2 = (c2[i] = optimized
        ? cloneIfMounted(c2[i] as VNode)
        : normalizeVNode(c2[i]))
      
      // n1.type === n2.type && n1.key === n2.key
      if (isSameVNodeType(n1, n2)) {
        // 如果type和key相等， 调用patch更新
        patch(
          n1,
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          namespace,
          slotScopeIds,
          optimized,
        )
      } else {
        // 如果头部VNode不同，跳出循环
        break
      }
      // 头部下移
      i++
    }
    
    ....
   }

这一步可以表示为下面这个样子

Vue3 Dom Diff算法核心逻辑解析一、什么是虚拟DOM 虚拟 DOM (Virtual DOM，简称 VDOM) 先从头部开始比较，VNode类型相同头部指针向下走一步，VNode类型不同时跳出循环，结束第一步对比,进入第二步比较

第二步从底部开始比较

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)) {
   // 如果type和key相等， 调用patch更新
    patch(
      n1,
      n2,
      container,
      null,
      parentComponent,
      parentSuspense,
      namespace,
      slotScopeIds,
      optimized,
    )
  } else {
   // 如果尾部VNode不同，跳出循环
    break
  }
   // 尾部上移
  e1--
  e2--
}

这一步可以表示为下面这个样子 Vue3 Dom Diff算法核心逻辑解析一、什么是虚拟DOM 虚拟 DOM (Virtual DOM，简称 VDOM) 从底部比较，VNode类型相同尾部指针向上走一步，VNode类型不同时跳出循环，结束第二步对比,进入第三步比较

第三步挂载新增节点

可以优先查看一下DOM相关操作实际调用的API文件地址

if (i > e1) {
  // 旧节点遍历结束
  if (i <= e2) {
    // 新节点还有剩余，挂载剩余的新节点
    const nextPos = e2 + 1
    // 插入到节点anchor之前
    // parent.insertBefore(child, anchor || null)
    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++
    }
  }
}

这一步可以表示为下面这个样子 Vue3 Dom Diff算法核心逻辑解析一、什么是虚拟DOM 虚拟 DOM (Virtual DOM，简称 VDOM) 公共序列遍历结束后如果新vNode列表有剩余，代表有新增，挂载这部分新增节点

第四步删除旧节点

if (i > e2) {
  // 新节点遍历结束
  while (i <= e1) {
    // 旧节点还有剩余
    // 循环遍历删除旧节点  删除dom实际调用的API
    //  const parent = child.parentNode
    //    if (parent) {
    //       parent.removeChild(child)
    //    }
    unmount(c1[i], parentComponent, parentSuspense, true)
    i++
  }
}

这一步可以表示为下面这个样子

Vue3 Dom Diff算法核心逻辑解析一、什么是虚拟DOM 虚拟 DOM (Virtual DOM，简称 VDOM) 公共序列遍历结束后如果旧vNode列表有剩余，代表有删除，卸载这部分删除节点

第五步未知序列比较

在上面四步都走完后，还有一些节点没有遍历结束，通常是节点的位置发生了改变或插入新节点的情况，这一步一共分为三个小步

第一步生成新节点key:index map

// 旧前节点 初始值为当前头部指针位置
const s1 = i
// 新前节点
const s2 = i

// 5.1 给新节点构建 key:index map
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) {
  keyToNewIndexMap.set(nextChild.key, i)
}
}

这一步可以表示为下面这个样子 Vue3 Dom Diff算法核心逻辑解析一、什么是虚拟DOM 虚拟 DOM (Virtual DOM，简称 VDOM) 头尾的公共部分比较结束了，还剩余一些非公共的部分，新建了两个指针s1、s2,分别指向旧、新非公共序列的头部，然后将根据s2到e2这部分节点生成key:index映射表

第二步循环遍历旧节点

新节点的key:index映射表生成后，再遍历旧节点，寻找匹配的节点完成更新，最后卸载多余的节点

let j
// 已更新的节点
let patched = 0
// 待更新的节点数量
const toBePatched = e2 - s2 + 1
let moved = false
// 用来校验是否有节点需要移动
let maxNewIndexSoFar = 0
// 类似Map<新节点下标, 旧节点下标> 如果旧节点下标=0 代表这个新节点是新增节点
// 这个数组最后做最长递增子序列
const newIndexToOldIndexMap = new Array(toBePatched)
// 初始化 每个oldIndex下标都为0
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中寻找和旧节点相同key的节点下标
      newIndex = keyToNewIndexMap.get(prevChild.key)
    } else {
      // 如果旧节点没有key， 循环遍历未patch的新节点，
      // 寻找类型和旧节点一致的新节点下标
      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对饮的值设置为i+1
      newIndexToOldIndexMap[newIndex - s2] = i + 1
      if (newIndex >= maxNewIndexSoFar) {
        // 标记当前寻找到的新节点的下标
        maxNewIndexSoFar = newIndex
      } else {
        // 如果当前新节点的下标小于maxNewIndexSoFar，证明节点有移动
        moved = true
      }
      // 更新节点
      patch(
        prevChild,
        c2[newIndex] as VNode,
        container,
        null,
        parentComponent,
        parentSuspense,
        namespace,
        slotScopeIds,
        optimized,
      )
      // 已更新的节点数量+1
      patched++
    }
}

这一步可以表示为下面这个样子 Vue3 Dom Diff算法核心逻辑解析一、什么是虚拟DOM 虚拟 DOM (Virtual DOM，简称 VDOM) 在遍历过程中，maxNewIndexSoFar初始为0，遍历第一个C时maxNewIndexSoFar变为4，遍历第二个D maxNewIndexSoFar变为3，证明节点发生了移动

第三步移动节点和挂载新节点

最后一步主要是用来处理需要移动的节点，并且挂载新的节点

// 根据判断是否有节点移动，决定是否要计算最长递增子序列
// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
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) {
      // 0表示没有相同类型的旧节点，代表是新增节点，挂载节点
      patch(
        null,
        nextChild,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        namespace,
        slotScopeIds,
        optimized,
      )
    } else if (moved) {
      // 有节点发生移动
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        // 没有最长递增子序列（序列反转）
        // 或者节点不在最长递增子序列中
        move(nextChild, container, anchor, MoveType.REORDER)
      } else {
        // 下标上移
        j--
      }
    }
}

这一步可以表示为下面这个样子 Vue3 Dom Diff算法核心逻辑解析一、什么是虚拟DOM 虚拟 DOM (Virtual DOM，简称 VDOM) 最后对新节点执行挂载，移动相对位置发生变化的节点。

四、Vue Vopar

它是一个全新的渲染机制，受SolidJS框架的启发，它有以下的几个特点

没有虚拟DOM，直接操作DOM API，减少性能开销，占用更小的内存
不需要diff相关的代码，减少包体积
基于@vue/reactivity响应性系统开发

通过Vue Vopar官方的playground例子🌰传送门看下。通过例子可以看到，它把所有每一个会动态变化的部分当做响应式副作用执行，而不是在依赖更新的时候执行整个render函数。目前这个不带虚拟DOM的vue正在开发阶段，据2024vueconf大会介绍将会在今年年底发布一个beta版本，我们拭目以待吧。具体可以参照B站视频探索无虚拟DOM的Vue

五、总结

通过对Vue3的patch函数和它内部调用的一些函数进行分析，我们很快可以发现Vue3 Diff的一些特点

编译优化，虚拟节点加了更新标记patchFlag，优化Diff性能
新增shapeFlag，针对不同类型的虚拟节点做不同的diff逻辑
内部结构稳定的模板称为一个“区块”，通过dynamicChildren存储需要追踪更新的节点
通过新增Fragment片段，优化了Vue2模板只能有一个根节点的问题
通过最长递增子序列函数，最大限度的减少子节点Diff过程中节点元素的移动

Vue3 Dom Diff算法核心逻辑解析一、什么是虚拟DOM 虚拟 DOM (Virtual DOM，简称 VDOM)

转载自:https://juejin.cn/post/7416659736986566675

Vue3 Dom Diff算法核心逻辑解析一、什么是虚拟DOM 虚拟 DOM (Virtual DOM，简称 VDOM)

一、什么是虚拟DOM

通过图片对比一下真实Dom和虚拟Dom

二、为何需要虚拟DOM

三、Vue3 Diff细节

Diff入口patch函数

processElement函数逻辑

patchElement函数逻辑

patchChildren函数逻辑

patchUnkeyedChildren函数逻辑

patchKeyedChildren函数逻辑

第一步 从头部开始比较

第二步 从底部开始比较

第三步 挂载新增节点

第四步 删除旧节点

第五步 未知序列比较

第一步 生成新节点key:index map

第二步 循环遍历旧节点

第三步 移动节点和挂载新节点

四、Vue Vopar

五、总结

第一步从头部开始比较

第二步从底部开始比较

第三步挂载新增节点

第四步删除旧节点

第五步未知序列比较

第一步生成新节点key:index map

第二步循环遍历旧节点

第三步移动节点和挂载新节点