vue3.0的patch相对于2.0做了很多优化，vue3.0在编译阶段会对vnode进行flag标记，用于对vnode更新时的diff做性能优化。下面我们从patch函数入口开始一步一步的了解3.0时如何进行patch的，以及具体有了哪些性能提升。

一、前言：

vue3.0编译阶段做了很多优化工作，来帮运行阶段减轻负担，比如生成patchFlag以减少运行时的diff性能损耗，静态节点提升以减少vnode创建带来的开销等… 具体编译阶段是如何运作的可以看上一篇关于vue3.0编译系统的文章。
首先普及两个flag的概念：

• shapFlag：用来标记VNode种类的标志位，比如ELEMENT表示普通dom，COMPONENT表示组件类型：

export const enum ShapeFlags {
 ELEMENT = 1, // 普通元素
 FUNCTIONAL_COMPONENT = 1 << 1, // 函数组件
 STATEFUL_COMPONENT = 1 << 2, // 状态组件
 TEXT_CHILDREN = 1 << 3, // 文本子节点
 ARRAY_CHILDREN = 1 << 4, // 数组子节点
 SLOTS_CHILDREN = 1 << 5, // 插槽子节点
 TELEPORT = 1 << 6, // 传送组件
 SUSPENSE = 1 << 7, // 悬念组件
 // ...
}

• patchFlag：编译时生成的flag，runtime在处理diff逻辑时，diff算法会进入优化模式，patchFlag均为编译时生成，当然你如果愿意的话也可以自己手写render来传入patchFlag，但其实是不建议这么做的。在diff优化模式中，算法仅需对标记patchFlag的vnode进行处理（各个flag有相应的优化策略），其他的可略过，以获得性能上的提升。各个patchFlag的作用源码注释写的非常清楚。
  注意一点：
  （1）patchFlag > 0一定是动态节点，-1（HOIST）代表提升静态节点。
  （2）负的patchFlag不参与位运算，比如flag & HOIST这种是不允许的
  （3）patchFlag可以使用联合类型“|”，表示同时为节点打上多种flag，用“&”判断当前节点的patchFlag是否包含制定flag。看下源码注解给的例子：

const flag = TEXT | CLASS
if (flag & TEXT) { ... }

const enum PatchFlags {
 // 插值生成的动态文本节点
 TEXT = 1,
 // 动态class绑定
 CLASS = 1 << 1,
 // 动态绑定style，需要注意一点，如果绑定的是静态object，即object不会动态变化
 // 将同样被当作静态属性来处理，静态属性声明会被提升到render函数体的最前端
 // 减少不必要的属性创建开销
 // e.g. style="color: red" and :style="{ color: 'red' }" both get hoisted as
 //   const style = { color: 'red' }
 //   render() { return e('div', { style }) }
 STYLE = 1 << 2,
 // dom元素包含除class、style之外的动态属性，或者组件包含动态属性（可以是class、style）
 // 动态属性在编译阶段被收集到dynamicProps中，运行时做diff操作时会只对比动态属性的变化
 // 省略对其他无关属性的diff（删除的属性无需关心）
 PROPS = 1 << 3,
 // 包含动态变化的keys，需要对属性做全量diff，该标志位和
 // CLASS、STYLE、PROPS是互斥的，不会同时存在，有FULL_PROPS
 // 上面提到的三个标志位会失效
 FULL_PROPS = 1 << 4,
 // 服务端渲染相关
 HYDRATE_EVENTS = 1 << 5,
 // 稳定的fragment类型，其children不会变化，元素次序固定，
 // 如`<div v-for="item in 10">{{ item }}</div>`生成的fragment
 STABLE_FRAGMENT = 1 << 6,
 // fragment的children全部或部分节点标记key
 KEYED_FRAGMENT = 1 << 7,
 // fragment的children节点均未标记key
 UNKEYED_FRAGMENT = 1 << 8,
 // 不需要做props的patch，比如节点包含ref或者指令 ( onVnodeXXX hooks ) ，
 // 但是节点会被当作动态节点收集到对应block的dynamicChildren中
 NEED_PATCH = 1 << 9,
 // 插槽相关
 DYNAMIC_SLOTS = 1 << 10,
 // 静态节点，由于被提升到render函数体最顶部，因此节点一旦声明就会维持在内存里
 // re-render时就不需要再重复创建节点了，同时diff时会跳过静态节点，因为内容不发生任何变化
 HOISTED = -1,
 // 特殊处理，具体作用可看源码注释
 BAIL = -2
}

二、patch

标题的patch指的不只是patch函数，而是整个虚拟dom映射到真实dom的过程，本节重点讲解整个链路。

patch：
可以理解为渲染系统最为核心的方法，基本上集中了大部分核心渲染操作。

const patch: PatchFn = (
    n1,
    n2,
    container,
    anchor = null,
    parentComponent = null,
    parentSuspense = null,
    isSVG = false,
    optimized = false
  ) => {
    // 如果不是相同类型的节点（tag、key都相同才算相同节点）
    // 直接卸载旧的vnode
    if (n1 && !isSameVNodeType(n1, n2)) {
      anchor = getNextHostNode(n1)
      unmount(n1, parentComponent, parentSuspense, true)
      n1 = null
    }
    
    // bail不做diff优化
    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, isSVG)
        } else if (__DEV__) {
          patchStaticNode(n1, n2, container, isSVG)
        }
        break
      // fragment片段节点
      case Fragment:
        processFragment(
          n1,
          n2,
          container,
          anchor,
          parentComponent,
          parentSuspense,
          isSVG,
          optimized
        )
        break
      default:
        if (shapeFlag & ShapeFlags.ELEMENT) {
          // 普通dom节点
          processElement(
            n1,
            n2,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            optimized
          )
        } else if (shapeFlag & ShapeFlags.COMPONENT) {
          // 组件节点
          processComponent(
            n1,
            n2,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            optimized
          )
        } else if (shapeFlag & ShapeFlags.TELEPORT) {
          // 传送组件
          ;(type as typeof TeleportImpl).process(
            n1,
            n2,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            optimized,
            internals
          )
        } else if (__FEATURE_SUSPENSE__ && shapeFlag & ShapeFlags.SUSPENSE) {
          // 悬念组件
          ;(type as typeof SuspenseImpl).process(
            n1,
            n2,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            optimized,
            internals
          )
        } else if (__DEV__) {
          warn('Invalid VNode type:', type, `(${typeof type})`)
        }
    }

    // 每次patch都要重新设置ref，这也就是为什么在编译阶段不对含有ref的节点进行提升的原因
    // 因为ref是当作动态属性来看待的
    if (ref != null && parentComponent) {
      setRef(ref, n1 && n1.ref, parentComponent, parentSuspense, n2)
    }
  }

上面的processXXX是对挂载和更新补丁的统一操作入口，接下来对几个重点类型的mount、patch操作做讲解：

1. element

processElement：
dom元素节点类型的处理。

const processElement = (
  n1: VNode | null,
  n2: VNode,
  container: RendererElement,
  anchor: RendererNode | null,
  parentComponent: ComponentInternalInstance | null,
  parentSuspense: SuspenseBoundary | null,
  isSVG: boolean,
  optimized: boolean
) => {
  isSVG = isSVG || (n2.type as string) === 'svg'
  if (n1 == null) {
    // 首次挂载，不做详细介绍，就是递归创建真实节点
    mountElement(
      n2,
      container,
      anchor,
      parentComponent,
      parentSuspense,
      isSVG,
      optimized
    )
  } else {
    // patch更新
    patchElement(n1, n2, parentComponent, parentSuspense, isSVG, optimized)
  }
}

patchElement：
很重要的方法，element节点打更新补丁的核心逻辑

const patchElement = (
  n1: VNode,
  n2: VNode,
  parentComponent: ComponentInternalInstance | null,
  parentSuspense: SuspenseBoundary | null,
  isSVG: boolean,
  optimized: boolean
) => {
  const el = (n2.el = n1.el!)
  let { patchFlag, dynamicChildren, dirs } = n2
  // 如果n2.patchFlag和n1的相同，取该flag，否则取FULL_PROPS
  patchFlag |= n1.patchFlag & PatchFlags.FULL_PROPS
  const oldProps = n1.props || EMPTY_OBJ
  const newProps = n2.props || EMPTY_OBJ
  let vnodeHook: VNodeHook | undefined | null

  // 执行vnode钩子onVnodeBeforeUpdate
  if ((vnodeHook = newProps.onVnodeBeforeUpdate)) {
    invokeVNodeHook(vnodeHook, parentComponent, n2, n1)
  }
  // 运行时指令，执行指令的beforeUpdate钩子
  if (dirs) {
    invokeDirectiveHook(n2, n1, parentComponent, 'beforeUpdate')
  }

  // 省略无关代码...
  // 属性patch
  if (patchFlag > 0) {
    // 可以走diff优化通道的动态节点
    if (patchFlag & PatchFlags.FULL_PROPS) {
      // 节点包含动态属性keys，比如这种case：:[attr]="test"，
      // 属性的名称是动态变化的，需要对属性做全量diff
      patchProps(
        el,
        n2,
        oldProps,
        newProps,
        parentComponent,
        parentSuspense,
        isSVG
      )
    } else {
      // 动态class绑定
      if (patchFlag & PatchFlags.CLASS) {
        if (oldProps.class !== newProps.class) {
          hostPatchProp(el, 'class', null, newProps.class, isSVG)
        }
      }

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

      // 除style、class外的动态属性，对dynamicProps中收集的动态属性做diff就可以了，
      // 忽略无关属性
      if (patchFlag & PatchFlags.PROPS) {
        // if the flag is present then dynamicProps must be non-null
        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 ||
            (hostForcePatchProp && hostForcePatchProp(el, key))
          ) {
            hostPatchProp(
              el,
              key,
              prev,
              next,
              isSVG,
              n1.children as VNode[],
              parentComponent,
              parentSuspense,
              unmountChildren
            )
          }
        }
      }
    }

    // 动态文本变化，直接重新设置新文本
    if (patchFlag & PatchFlags.TEXT) {
      if (n1.children !== n2.children) {
        hostSetElementText(el, n2.children as string)
      }
    }
  } else if (!optimized && dynamicChildren == null) {
    // 不走优化diff，全量diff
    patchProps(
      el,
      n2,
      oldProps,
      newProps,
      parentComponent,
      parentSuspense,
      isSVG
    )
  }

  const areChildrenSVG = isSVG && n2.type !== 'foreignObject'
  if (dynamicChildren) {
    // block节点，忽略层级对dynamicChildren进行比对即可，dynamicChildren包含了
    // block树中所有的动态子代节点或子代block，因此无需再比对children
    patchBlockChildren(
      n1.dynamicChildren!,
      dynamicChildren,
      el,
      parentComponent,
      parentSuspense,
      areChildrenSVG
    )
    
    // 省略无关代码...
  } else if (!optimized) {
    // 不优化走children的全量diff
    patchChildren(
      n1,
      n2,
      el,
      null,
      parentComponent,
      parentSuspense,
      areChildrenSVG
    )
  }

  if ((vnodeHook = newProps.onVnodeUpdated) || dirs) {
    // 更新补丁后的钩子触发，注意：不是立即出发，vue中的更新钩子是
    // 由scheduler调度器来控制执行时机的，effect先入队，在nextTick
    // 执行
    queuePostRenderEffect(() => {
      vnodeHook && invokeVNodeHook(vnodeHook, parentComponent, n2, n1)
      dirs && invokeDirectiveHook(n2, n1, parentComponent, 'updated')
    }, parentSuspense)
  }
}

patchBlockChildren:
对block下的动态子代节点进行patch操作。

const patchBlockChildren: PatchBlockChildrenFn = (
  oldChildren,
  newChildren,
  fallbackContainer,
  parentComponent,
  parentSuspense,
  isSVG
) => {
  for (let i = 0; i < newChildren.length; i++) {
    const oldVNode = oldChildren[i]
    const newVNode = newChildren[i]
    // 决定子节点patch时的实际父节点容器，三种情况需要访问实际的父节点dom：
    // fragment、不同vnode、组件
    const container = 
      // fragment本质上是一个无实际容器的片段，但是像v-for生成的fragment中，
      // 在进行fragment diff时会涉及到节点的增删、移位，这种情况是需要通过真实
      // 父节点容器来操作的，因此需要提供fragment节点原本的父级容器
      oldVNode.type === Fragment ||
      // 同样的道理，非相同类型的vnode在patch时要替换节点，因此需要提供真实的父节点
      !isSameVNodeType(oldVNode, newVNode) ||
      // 组件内容是不确定的，比如多根节点的情况，就是一个fragment，因此也需要
      // 提供真实的父级容器
      oldVNode.shapeFlag & ShapeFlags.COMPONENT
        ? hostParentNode(oldVNode.el!)!
        : // 其他情况下，patch操作并不会涉及到使用父级dom容器，处于性能考虑，
          // 自然没必要再用dom操作获取vnode对应父级dom了
          fallbackContainer
    // 新旧动态子节点patch，element都是单节点，所以diff children时不需要anchor
    patch(
      oldVNode,
      newVNode,
      container,
      null, // anchor
      parentComponent,
      parentSuspense,
      isSVG,
      true
    )
  }
}

1. fragment

虚拟外部容器的片段，和react里的fragment是一个作用，解决了2.0时代不支持多根template的问题。
注意：fragment在编译阶段生成的都是block节点
processFragment：

const processFragment = (
  n1: VNode | null,
  n2: VNode,
  container: RendererElement,
  anchor: RendererNode | null,
  parentComponent: ComponentInternalInstance | null,
  parentSuspense: SuspenseBoundary | null,
  isSVG: boolean,
  optimized: boolean
) => {
  // 片段的坐标，确定片段插入的起始位置，也就是起始锚点。
  // fragment将vnode的el起始定位节点，vnode的anchor作为结束定位节点
  // fragment vnode和普通单节点有一点区别：其el并非fragment对应的真实
  // dom，因为fragment自身没有一个真正的实体dom，因此是将fragment chidren
  // 在dom中的前一个元素作为el，结尾后一个元素作为anchor，起到一个定位效果
  // 方便用nextSibling
  const fragmentStartAnchor = (n2.el = n1 ? n1.el : hostCreateText(''))!
  const fragmentEndAnchor = (n2.anchor = n1 ? n1.anchor : hostCreateText(''))!

  let { patchFlag, dynamicChildren } = n2
  // patchFlag < 0不做diff优化，比如静态节点提升的情况
  if (patchFlag > 0) {
    optimized = true
  }

  // 省略无关代码...

  if (n1 == null) {
    hostInsert(fragmentStartAnchor, container, anchor)
    hostInsert(fragmentEndAnchor, container, anchor)
    // 和element类似，mountChildren首次挂载子节点
    mountChildren(
      n2.children as VNodeArrayChildren,
      container,
      fragmentEndAnchor,
      parentComponent,
      parentSuspense,
      isSVG,
      optimized
    )
  } else {
    if (
      patchFlag > 0 &&
      patchFlag & PatchFlags.STABLE_FRAGMENT &&
      dynamicChildren
    ) {
      // 稳定的fragment，如template多根节点，或者这种
      // `<div v-for="i in 10">{{ i }}</div>`
      // 这种fragment明显是稳定的，但是其子代可能包含动态节点
      // 因此直接patchBlockChildren
      patchBlockChildren(
        n1.dynamicChildren!,
        dynamicChildren,
        container,
        parentComponent,
        parentSuspense,
        isSVG
      )
      
      // 省略无关代码...
    } else {
      // 非稳定的fragment，比如这种：
      //  `<div v-for="i in dynanicArr">{{ i }}</div>`
      // 虽然v-for的渲染单元结构固定，但是dynanicArr数组是会变化的，因此会导致
      // fragment的子节点顺序和内容的不确定性，所以直接将fragment子节点
      // 作为dynamicChildren比较明显是不正确的：
      // 比如dynanicArr从[1, 2]变成[3, 4, 2, 1]，假如你给
      // 每个子节点的key是非数组index（直接用index会有问题，老生常谈了）
      // 而是和数组元素内容强相关的元素值，key组：1 - 2 -> 3 - 4 - 2 - 1
      // 那么直接用patchDynamicChildren的话，diff会忽略节点顺序
      // 这么比较会导致更新错乱。
      // 那没办法，只能走children的全量diff了，因此不稳定的fragment不会挂载
      // dynamicChildren，虽然fragment本身是block。
      // 需要注意的是，不稳定fragment的每个子节点都是block，保证子节点可以
      // 继续走优化diff
      patchChildren(
        n1,
        n2,
        container,
        fragmentEndAnchor, // anchor
        parentComponent,
        parentSuspense,
        isSVG,
        optimized
      )
    }
  }
}

重头戏来了，来看看patchChildren是怎么做子代节点的diff的，这是vue3.0 diff算法里相对比较重的部分，子代节点的diff在3.0也是迎来了升级，看下源码一探究竟。
patchChildren：
其中最核心的部分是patchKeyedChildren和patchUnkeyedChildren。

const patchChildren: PatchChildrenFn = (
  n1,
  n2,
  container,
  anchor,
  parentComponent,
  parentSuspense,
  isSVG,
  optimized = false
) => {
  const c1 = n1 && n1.children
  const prevShapeFlag = n1 ? n1.shapeFlag : 0
  const c2 = n2.children

  const { patchFlag, shapeFlag } = n2
  // patchFlag > 0可优化diff
  if (patchFlag > 0) {
    if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
      // 部分或全部子节点标记key的diff
      patchKeyedChildren(
        c1 as VNode[],
        c2 as VNodeArrayChildren,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        optimized
      )
      return
    } else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
      // 全部子节点均未标记key的diff
      patchUnkeyedChildren(
        c1 as VNode[],
        c2 as VNodeArrayChildren,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        optimized
      )
      return
    }
  }

  // 文本, 数组或无子节点的情况
  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,
          isSVG,
          optimized
        )
      } else {
        // 无新子节点，卸载子节点
        unmountChildren(c1 as VNode[], parentComponent, parentSuspense, true)
      }
    } else {
      // 新旧子节点为null或文本节点
      if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
        hostSetElementText(container, '')
      }
      // 新子节点为数组节点，挂载新的子节点
      if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        mountChildren(
          c2 as VNodeArrayChildren,
          container,
          anchor,
          parentComponent,
          parentSuspense,
          isSVG,
          optimized
        )
      }
    }
  }
}

接下来看一下patchKeyedChildren和patchUnkeyedChildren，前者处理的场景是一组子节点有部分或全部标记key的情况，后者相反，是均未标记key的情况。
比如这两个例子：

<!-- keyed -->
<div v-for="(item, index) in list" :key="`${item}-${index}`">{{ item }}</div>
<!-- unkeyed -->
<div v-for="(item, index) in list">{{ item }}</div>

第一个会调用patchKeyedChildren，第二个调用patchUnkeyedChildren。先看下patchUnkeyedChildren，比较简单。

patchUnkeyedChildren：
非常简单，就是一次比对patch，多出来的挂载，少的卸载。

const patchUnkeyedChildren = (
  c1: VNode[],
  c2: VNodeArrayChildren,
  container: RendererElement,
  anchor: RendererNode | null,
  parentComponent: ComponentInternalInstance | null,
  parentSuspense: SuspenseBoundary | null,
  isSVG: boolean,
  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]))
    patch(
      c1[i],
      nextChild,
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      optimized
    )
  }

  // 多出来的新节点挂载，删除掉的旧节点卸载
  if (oldLength > newLength) {
    // remove old
    unmountChildren(c1, parentComponent, parentSuspense, true, commonLength)
  } else {
    // mount new
    mountChildren(
      c2,
      container,
      anchor,
      parentComponent,
      parentSuspense,
      isSVG,
      optimized,
      commonLength
    )
  }
}

patchKeyedChildren：
部分或全部标记key的子节点组diff，该部分是diff算法里比较重量级的部分，涉及到的算法知识相对较多，下面将详细介绍，先看下源码。

const patchKeyedChildren = (
  c1: VNode[],
  c2: VNodeArrayChildren,
  container: RendererElement,
  parentAnchor: RendererNode | null,
  parentComponent: ComponentInternalInstance | null,
  parentSuspense: SuspenseBoundary | null,
  isSVG: boolean,
  optimized: boolean
) => {
  let i = 0
  const l2 = c2.length
  let e1 = c1.length - 1 // 旧子节点组的尾指针
  let e2 = l2 - 1 // 新子节点组的尾指针

  // case1 头部向尾部遍历
  // 从节点组头部向尾部遍历，遇到尾指针则停止。遍历过程中，遇到相似节点（tag、key均相等）
  // 直接patch比对，否则退出遍历，此时i记录了diff最新的头部推进指针
  // (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,
        isSVG,
        optimized
      )
    } else {
      break
    }
    i++
  }

  // case2 尾部向头部遍历
  // 从节点组尾部向头部遍历，只要有一个尾指针遇到指针i则停止。遍历过程中，
  // 遇到相似节点（tag、key均相等）直接patch比对，否则退出遍历，此时e1，e2
  // 记录了diff最新的尾部推进指针
  // 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,
        isSVG,
        optimized
      )
    } else {
      break
    }
    e1--
    e2--
  }

  // case3 旧节点组首尾指针相撞，新节点组首尾指针未相撞
  // 经过上面（case1、case2）的首尾夹逼操作后，如果start -> end和end -> start
  // 两个方向至少有一个遍历没有中途断掉，那么首尾指针便会相撞。该case下旧节点组均经过
  // patch操作，新节点组中间部分存在断档，因此当作新增节点进行挂载操作
  // (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
      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,
          isSVG
        )
        i++
      }
    }
  }

  // case4 旧节点组首尾指针未相撞，新节点组首尾指针相撞
  // 经过上面（case1、case2）的首尾夹逼操作后，如果start -> end和end -> start
  // 两个方向至少有一个遍历没有中途断掉，那么首尾指针便会相撞。该case下新节点组均经过
  // patch操作，旧节点组中间部分存在断档，因此当作待删除节点进行卸载操作
  // (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++
    }
  }

  // case5 存在未知序列
  // 该case下，start -> end和end -> start两个方向在遍历中途均断掉
  // （由于tag或key不想等），导致新旧节点组中间均出现了未进行patch操作
  // 的节点序列
  // [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 // 新未知序列头指针

    // 建立
    const keyToNewIndexMap: Map<string | number, number> = new Map()
    // 遍历新未知序列，记录新序列中节点的key - index键值对
    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)
      }
    }

    // 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
    // 记录已执行patch的新序列节点数量
    let patched = 0
    // 将要执行patch的节点数目，即新序列的节点数量
    const toBePatched = e2 - s2 + 1
    let moved = false
    // used to track whether any node has moved
    let maxNewIndexSoFar = 0
    
    // used for determining longest stable subsequence
    // 初始化新旧节点对应关系表，因为只记录index对应关系，
    // 所以用数组来当作map来记录，用数组记录也是为了用于
    // 创建最长稳定子序列。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]
      // 只有找到旧节点对应的新节点才会执行patch并为patched计数，
      // 因此一旦patched === toBePatched，说明新序列的节点全部
      // patch完毕，旧节点中新访问到的节点不可能在有对应的新节点了，
      // 因此直接卸载对应就节点即可
      if (patched >= toBePatched) {
        // all new children have been patched so this can only be a removal
        unmount(prevChild, parentComponent, parentSuspense, true)
        continue
      }

      let newIndex
      if (prevChild.key != null) {
        // 如果旧节点携带有效的key值，通过之前生成的新序列key-index映射表
        // 检索到含有相同key新节点的index
        newIndex = keyToNewIndexMap.get(prevChild.key)
      } else {
        // 对于不携带key的旧节点，尝试在新节点序列中找出一个同样不携带key
        // 且为相似节点的新节点，并记录对应新节点的index
        for (j = s2; j <= e2; j++) {
          if (
            newIndexToOldIndexMap[j - s2] === 0 &&
            isSameVNodeType(prevChild, c2[j] as VNode)
          ) {
            newIndex = j
            break
          }
        }
      }
      
      if (newIndex === undefined) {
        // newIndex为空，说明未找到与旧节点相对应的新节点，直接卸载
        unmount(prevChild, parentComponent, parentSuspense, true)
      } else {
        // 新旧节点对应关系表，记录新节点index对应的旧节点index，
        // 注意：0是特殊标志位，标示当前新节点无对应的旧节点
        newIndexToOldIndexMap[newIndex - s2] = i + 1
        // 记录是否需要做节点移位操作，如何发现节点是否移位了呢，
        // 在遍历patch过程中，每次patch都记录下最大的新节点index
        // 其实也就是上一次的newIndex，如果每次记录的newIndex都
        // 保证比上次大，那么新旧序列中前后两个节点的相对位置是没有
        // 发生变化的，反之则标记需要移位，因为节点的相对位置变了，
        // 比如这样：
        // (a b) c
        // (a c b)
        // b在新旧序列中相对a的位置都是在后面，至于中间插进来的c
        // 在新旧序列对比b、c的时候，由于c最新对应的newIndex已经
        // 小雨b对应的newIndex，因此会记录需要移位
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex
        } else {
          moved = true
        }
        // 新旧点点相对应，做patch操作
        patch(
          prevChild,
          c2[newIndex] as VNode,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          optimized
        )
        // 记录已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
      // 确定锚点，如果是完整序列最后一个节点，anchor为父节点对应的anchor
      // 否则就是上一个子节点
      const anchor =
        nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
      if (newIndexToOldIndexMap[i] === 0) {
        // 如果newIndexToOldIndexMap对应的值为0，说明新节点没有对应的旧节点，
        // 毫无疑问是新增节点，直接挂载
        patch(
          null,
          nextChild,
          container,
          anchor,
          parentComponent,
          parentSuspense,
          isSVG
        )
      } else if (moved) {
        // 节点的位移操作
        // 位移发生的条件:
        // 1. moved标志位为true
        // 2. 最长稳定子序列为空，比如节点组反转的case，对应j < 0
        // 3. 最长稳定子序列当前值和当前访问的新节点index不相同
        // 新子节点序列和最长稳定子序列都是由尾部向前遍历，
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
          // 将需要移位的新节点dom元素移位到anchor前面，最终的移位的结果就是
          // 两元素在dom中的位置和在vnode中的位置完全一致
          move(nextChild, container, anchor, MoveType.REORDER)
        } else {
          // 不移位就前移j指针
          j--
        }
      }
    }
  }
}

setupComponent:

初始化组件的props，执行组件的setup函数，并将setup返回结果挂载到组件实例的setupState上

export function setupComponent(
  instance: ComponentInternalInstance,
  isSSR = false
) {
  isInSSRComponentSetup = isSSR

  const { props, children, shapeFlag } = instance.vnode
  const isStateful = shapeFlag & ShapeFlags.STATEFUL_COMPONENT
  initProps(instance, props, isStateful, isSSR)
  initSlots(instance, children)

  const setupResult = isStateful
    ? setupStatefulComponent(instance, isSSR)
    : undefined
  isInSSRComponentSetup = false
  return setupResult
}

function setupStatefulComponent(
  instance: ComponentInternalInstance,
  isSSR: boolean
) {
  const Component = instance.type as ComponentOptions

  // 省略无关代码...
 
  // 2. 执行组件里用户定义的setup函数
  const { setup } = Component
  if (setup) {
    const setupContext = (instance.setupContext =
      setup.length > 1 ? createSetupContext(instance) : null)

    currentInstance = instance
    // 执行setup前先将shouldTrack置为false，响应式系统我们介绍过
    // shouldTrack为false代表不做track依赖收集，也就是说，当你在setup
    // 中触发响应数据的属性时，依赖不会通过track函数收集到对应的dep中
    // 注意⚠️：虽然setup执行期间track不收集依赖，但是立即执行effect在栈中的
    // 嵌套关系依然会确定下来，方便setup执行完毕后保证对effectStack中依赖
    // 的按序收集，相当于setup期间effect只是“存档”，setup之后再“读档”
    pauseTracking()
    const setupResult = callWithErrorHandling(
      setup,
      instance,
      ErrorCodes.SETUP_FUNCTION,
      [__DEV__ ? shallowReadonly(instance.props) : instance.props, setupContext]
    )
    // setup执行完毕，恢复之前的shouldTrack状态
    resetTracking()
    currentInstance = null

    if (isPromise(setupResult)) {
      // 省略无关代码...
    } else {
      // 将setup返回结果挂载到组件实例的setupState上
      handleSetupResult(instance, setupResult, isSSR)
    }
  } else {
    finishComponentSetup(instance, isSSR)
  }
}

// setup执行结果挂载到组件实例上
export function handleSetupResult(
  instance: ComponentInternalInstance,
  setupResult: unknown,
  isSSR: boolean
) {
  if (isFunction(setupResult)) {
    // setup returned an inline render function
    instance.render = setupResult as InternalRenderFunction
  } else if (isObject(setupResult)) {
    // 省略无关代码...
    // setup returned bindings.
    // assuming a render function compiled from template is present.
    instance.setupState = proxyRefs(setupResult)
  }
  // 省略无关代码...
  finishComponentSetup(instance, isSSR)
}

createRenderer：

baseCreateRenderer：

render:
render是虚拟dom映射到真实dom节点的核心，render函数会生成vnode，和组件实例上的_vnode（上一次生成的vnode）做patch，这里分两种情况：1⃣️无_vnode，直接mount新生成的vnode。2⃣️有_vnode，新旧vnode做patch处理。

normalizeVNode：标准化vnode，vue中children支持Array、string、null三种类型，该函数会将这行类型的传入数据转化为标准的vnode，强调一点，对于已存在的vnode如果未挂载，直接返回原anode，否则会clone一个新的。
patchUnkeyedChildren：新旧vnode的children均是未标记key的（unkeyed），按照新旧children的最短长度遍历，依次执行patch操作，遍历完成后，检查新旧children中未遍历到的vnode，旧children多出来的vnode会执行卸载操作（unmount），新children多出来的会挂载（mount）
patchKeyedChildren：新旧vnode的children均是标记key的（unkeyed），全部标记key或部分标记都算。optimized时vnode一定是VNode类型
patchStaticNode：patch静态节点，静态节点也就是未绑定动态变化属性的节点，比如<div>static</div>这种就是staticNode，<div>{{value}}</div>这种就是动态节点。该函数会对比新旧vnode的children，如果不一致，会卸载n1（通过removeStaticNode方法），并将n1的下一个节点作为anchor（n2挂载使用），然后将n2挂载（通过InsertStaticContent方法），并将children的首节点作为el，尾节点作为anchor。（疑问：n2挂载时会剥掉外壳，把children插入？）
removeStaticNode：将n1.el与anchor之间的所有dom节点卸载。
InsertStaticContent：接收一个innerHTML模版字符串（n2.children），并将其插入到createElement创建出的临时容器，将innerHTML中包含的子节点按顺序依次根据anchor插入（决定了removeStaticNode的内容），并返回插入的首尾节点。
processFragment：fragment片段的处理，包含mount和patch处理逻辑。生成首尾anchor用于定位fragment的位置区间，头部anchor为n1节点的el，没有的话创建text节点，尾部节点为n1节点的anchor，没有则创建text节点。（1）mount过程：将首尾anchor插入到入参anchor前，再通过mountChildren函数以尾部anchor为入参anchor将fragment.children依次mount，这样fragment.children就被mount到首尾anchor之间。（2）patch过程：分两种情况，1⃣️patchFlag>0且是稳定片段（patchFlag = STABLE_FRAGMENT）且有动态子节点（dynamicChildren）：通过patchBlockChildren方法patch新旧vnode的dynamicChildren，稳定片段由两种生成方式，根template和带有v-for指令的template，这两种方式生成的fragment总是同种类型的子节点，比如<div v-for=“item in array”>{{value}}</div>，生成的fragment一定都是div类型的子节点，不会出现其他类型，因此时稳定的。2⃣️不满足1⃣️中条件会正常走patchChildren方法，有三种场景，keyed、unkeyed、人工拼凑的fragment
patchBlockChildren：入参包含新旧vnode的dynamicChildren，遍历dynamicChildren，首先确定每个dynamicChildren元素的父级容器container，有三种情况必须获取到实际的父级dom容器：fragment、新旧vnode类型不同做替换、组件vnode，这三种情况下只有获取到真实的dom容器才能做patch操作，其他情况不关心真实的dom容器，使用入参的fallbackContainer即可

代码待补充...

二、VNode

vue3.0的vnode在2.0基础上进化了不少，比如新增的block概念，下面会重点介绍下block到底是个什么东西。

1. block

block是一个块状节点区域的概念，其最大特点就是含有动态子代节点（dynamicChildren），方便vue做diff时忽略不必要的层级遍历，带来性能提升。只需要在运行时的block创建阶段做一次子树遍历收集，后面无论如何更新data都只会做最小范围的diff，这是相当划算的，否则以后每次更新都需要完全遍历做diff。
openBlock在栈中为当前block开辟一个存储数组，在createBlock时会收集子代节点中的动态节点和block，存储到该当前存储数组，并作为当前block的dynamicChildren，存储完成后当前数组也就没有了，出栈并恢复到父级block对应的存储数组。牢记一点：block嵌套结构时通过block栈来维护的，形成一颗block树。
通常是这样使用：(openBlock(), createBlock('div', {}, [...]))，为什么openBlock声明新存储array一定要在createBlock之前呢，因为currentBlock要存储子代节点，就需要在createBlock调用前，这样保证currentBlock在createBlock真正执行前就收集好了所有的子代节点。如果是createBlock已经调用再openBlock声明存储数组，这时子代节点已经创建完毕，所以currentBlock无法再收集子代节点，这样显然达不到为block挂载dynamicChildren的目的。

// 用于维护父子block关系的栈结构
const blockStack: (VNode[] | null)[] = []
// 当前block的子代block及动态节点容器
let currentBlock: VNode[] | null = null

// createBlock之前首先开辟一个子代节点存储数组
function openBlock(disableTracking = false) {
  blockStack.push((currentBlock = disableTracking ? null : []))
}

// 创建block
function createBlock(
  type: VNodeTypes | ClassComponent,
  props?: { [key: string]: any } | null,
  children?: any,
  patchFlag?: number,
  dynamicProps?: string[]
): VNode {
  const vnode = createVNode(
    type,
    props,
    children,
    patchFlag,
    dynamicProps,
    true /* isBlock: prevent a block from tracking itself */
  )
  // 在createVnode时，子代vnode肯定是先创建出来，也就是说currentBlock从
  // 子代节点先跟踪并收集对应的子代节点，当上层节点创建时，将栈顶的currentBlock
  // 插入上层节点vnode
  vnode.dynamicChildren = currentBlock || EMPTY_ARR
  // 收集、插入完毕，currentBlock出栈
  blockStack.pop()
  // 将currentBlock恢复到上一次入栈的currentBlock，也就是父级block
  currentBlock = blockStack[blockStack.length - 1] || null
  // 将当前创建的block收集到父级block对应的存储数组中
  if (currentBlock) {
    currentBlock.push(vnode)
  }
  return vnode
}

然后看一下createVNnode
_createVNode:
创建普通的vnode，有一点需要特别注意，在创建vnode时如果开启了追踪（shouldTrack > 0），并且是动态节点（patchFlag > 0），那么当前block节点区域对应的currentBlock存储数组会将该vnode收集进去，这样就完成了block对子代动态节点的跟踪收集。

function _createVNode(
  type: VNodeTypes | ClassComponent | typeof NULL_DYNAMIC_COMPONENT,
  props: (Data & VNodeProps) | null = null,
  children: unknown = null,
  patchFlag: number = 0,
  dynamicProps: string[] | null = null,
  isBlockNode = false
): VNode {
  if (!type || type === NULL_DYNAMIC_COMPONENT) {
    if (__DEV__ && !type) {
      warn(`Invalid vnode type when creating vnode: ${type}.`)
    }
    type = Comment
  }

  if (isVNode(type)) {
    return cloneVNode(type, props, children)
  }

  // class component normalization.
  if (isFunction(type) && '__vccOpts' in type) {
    type = type.__vccOpts
  }

  // class & style normalization.
  if (props) {
    // for reactive or proxy objects, we need to clone it to enable mutation.
    if (isProxy(props) || InternalObjectKey in props) {
      props = extend({}, props)
    }
    let { class: klass, style } = props
    if (klass && !isString(klass)) {
      props.class = normalizeClass(klass)
    }
    if (isObject(style)) {
      // reactive state objects need to be cloned since they are likely to be
      // mutated
      if (isProxy(style) && !isArray(style)) {
        style = extend({}, style)
      }
      props.style = normalizeStyle(style)
    }
  }

  // encode the vnode type information into a bitmap
  const shapeFlag = isString(type)
    ? ShapeFlags.ELEMENT
    : __FEATURE_SUSPENSE__ && isSuspense(type)
      ? ShapeFlags.SUSPENSE
      : isTeleport(type)
        ? ShapeFlags.TELEPORT
        : isObject(type)
          ? ShapeFlags.STATEFUL_COMPONENT
          : isFunction(type)
            ? ShapeFlags.FUNCTIONAL_COMPONENT
            : 0

  if (__DEV__ && shapeFlag & ShapeFlags.STATEFUL_COMPONENT && isProxy(type)) {
    type = toRaw(type)
    warn(
      `Vue received a Component which was made a reactive object. This can ` +
        `lead to unnecessary performance overhead, and should be avoided by ` +
        `marking the component with \`markRaw\` or using \`shallowRef\` ` +
        `instead of \`ref\`.`,
      `\nComponent that was made reactive: `,
      type
    )
  }

  const vnode: VNode = {
    __v_isVNode: true,
    __v_skip: true,
    type,
    props,
    key: props && normalizeKey(props),
    ref: props && normalizeRef(props),
    scopeId: currentScopeId,
    children: null,
    component: null,
    suspense: null,
    dirs: null,
    transition: null,
    el: null,
    anchor: null,
    target: null,
    targetAnchor: null,
    staticCount: 0,
    shapeFlag,
    patchFlag,
    dynamicProps,
    dynamicChildren: null,
    appContext: null
  }

  // 省略无关代码...

  normalizeChildren(vnode, children)

  // presence of a patch flag indicates this node needs patching on updates.
  // component nodes also should always be patched, because even if the
  // component doesn't need to update, it needs to persist the instance on to
  // the next vnode so that it can be properly unmounted later.
  if (
    shouldTrack > 0 &&
    !isBlockNode &&
    currentBlock &&
    // the EVENTS flag is only for hydration and if it is the only flag, the
    // vnode should not be considered dynamic due to handler caching.
    patchFlag !== PatchFlags.HYDRATE_EVENTS &&
    (patchFlag > 0 ||
      shapeFlag & ShapeFlags.SUSPENSE ||
      shapeFlag & ShapeFlags.TELEPORT ||
      shapeFlag & ShapeFlags.STATEFUL_COMPONENT ||
      shapeFlag & ShapeFlags.FUNCTIONAL_COMPONENT)
  ) {
    currentBlock.push(vnode)
  }

  return vnode
}

block树存在的意义是什么呢，针对同一个template只生成一个根block他不香吗，直接平级diff一次就可以了。这样是很棒，不过像这个例子就不行了：

<template>
  <div>
    <p v-if="true">
      <span>{{ block }}</span>
    </p>
    <div v-else>
      <span>{{ block }}</span>
    </div>
  </div>
</template>

如果是只使用根block的话，上面的template生成的是这样的结构：

div(block)
  --p(undynamic vnode)
    --span(dynamic vnode)

创建block时span会收集到根级div的dynamicChildren中，在做diff时直接比较新旧span，并不再进行更深层次的diff，这样带来的问题就是只有span会更新，v-if branch对应的节点（p、di v）被忽略，导致未更新，这显然是不对的，实际上是需要做替换更新的。
那就说回来了，block树就是为了解决这个问题。像v-if、v-for（不稳定时的）生成的节点是不稳定的，可能会受到数据驱动导致节点动态变化（顺序、内容），但是可能该节点本身却是不会变化的（就像上面例子，p、div本身是静态的，但子代还有动态内容），对于不稳定的节点，vue3.0会将这种节点创建为block，并收集到父级block的dynamicChildren中，这样就形成了稳定的结构，即block tree。
To be continued…