vlambda博客
学习文章列表

前言

在上一篇文章vue的首次渲染过程中提到在组件的首次渲染阶段会有一个副作用渲染函数setupRenderEffect，在这个函数内会使用响应式API Effect创建副作用函数componentEffect，这里只需要简单的理解为，当组件内的数据改动时这个由Effect包裹的componentEffect就会重新调用，在这个函数内部会判断当前组件是处于首次渲染还是更新，当组件内数据发生变化时会进入到update的分支，本文要看的diff流程也就是从这里开始。

PS: 当前的Vue版本是3.0.5。本文会忽略TELEPORT、SUSPENSE等特殊vnode类型，对于一些细微的优化也会忽略（比如patch函数的optimized参数）。

回顾setupRenderEffect

在组件的数据发生改变时会自动触发副作用渲染函数setupRenderEffect：

// runtime-core/src/renderer.ts
import { effect } from '@vue/reactivity'

const setupRenderEffect = (instance, initialVNode, container, ...) => {
  // 在当前的组件实例上添加 update 方法，通过响应式方法 effect 创建
  instance.update = effect(function componentEffect() {
    if (!instance.isMounted) {

      //...
      
    } else {
      // 非首次渲染，进入 update 阶段
      let { next, vnode } = instance
      // 缓存一份更新后的 vnode
      let originNext = next
      if (next) {
        // 这里需要把更新后的组件 vnode 赋值 el，因为下面第一次 渲染新的组件 vnode 时并没有设置 el
        next.el = vnode.el
        updateComponentPreRender(instance, next)
      } else {
        // 如果没有 next 直接指向当前 vnode
        next = vnode
      }
      // 渲染新的组件 vnode，因为数据发生了变化
      const nextTree = renderComponentRoot(instance)
      // 缓存旧的组件 vnode
      const preTree = instance.subTree
      // 更新实例上的 subTree 为新的组件 vnode
      instance.subTree = nextTree
      
      patch(prevTree, nextTree, ..., instance)
      // 更新 DOM 元素
      next.el = nextTree.el
    }
  }, prodEffectOptions)

这里主要看update的部分（即else代码块）。首先会先从组件实例instance里取出next（在处理组件一节会详细说明next存在与不存在的情况）。

组件内的数据发生了改变，所以要生成新的组件模板的vnode节点，在渲染阶段命名为subTree，然后还要保存一份旧的subTree，这样有了新旧subTree后就可以用patch函数更新DOM。

patch函数

在进入具体的diff流程之前，我们不妨先想一下，当数据发生改变时，会有哪些变化类型？

实际上按照类型可以分为更新普通DOM元素和更新vue组件这两种情况。下面先关注一下patch函数的逻辑。

// runtime-core/src/renderer.ts
const patch = (n1, n2, container, ...) => {
  // n1 是旧节点，n2 是新节点
  // 如果 n1、n2 新旧节点的类型不同，直接销毁旧节点
  if(n1 && !isSameVNodeType(n1, n2)) {
    unmount(n1, parentComponent, parentSuspense, true)
    n1 = null
  }
  
  const { type, ref, shapeFlag } = n2
  
  switch(type) {
    // 处理文本节点
    case Text:
      processText(n1, n2, container, anchor)
      break
    // 处理注释
    case Comment:
      processCommentNode(n1, n2, container, anchor)
      break
    
    // ...
    
    default: 
      // 处理 DOM 元素
      if(shapeFlag & ShapeFlags.ELEMENT) {
        processElement(n1, n2, container, ...)
      // 处理 vue 组件
      } else if (shapeFlag & ShapeFlags.COMPONENT) {
        processComponent(n1, n2, container, ...)
      }
      
      // ...
  }
  
}

最开始先判断新旧节点的类型是否一样，如果不一样，可以设想某个节点从div标签变成span标签，最合理的方式是直接舍弃旧节点，重新挂载新的节点。

再往下会根据当前节点类型type进行特定的处理。比如文本节点执行processText的特定处理、注释节点执行processCommentNode的特定处理。这样的前置处理实际上是一个优化，在编译阶段，vue会将模版语法编译成渲染函数，这个时候会把第一个参数节点类型type填上，如果这个参数命中了这样的特殊节点，会直接执行相应的process方法。

default块儿里才是分析的重点，即处理普通DOM元素和vue组件。

处理DOM元素

先举一个栗子🌰，假设有以下一段代码：

<template>
  <div>
    <button @click="add">add</button>
    <p>{{ num }}</p>
  </div>
</template>
<script>
import { ref } from 'vue'
export default {
  setup () {
    const num = ref(1)
    function add() {
      num.value += 1
    }
    return {
      num,
      add
    }
  }
}
</script>

这段代码非常简单，点击add按钮，p标签里的num会加一。

因为p标签是一个普通的DOM节点，所以在具体执行patch方法时，会走处理DOM的逻辑，执行processElement方法。

// runtime-core/src/renderer.ts
const processElement= (n1, n2, container, ...) => {
  // 无旧节点，首次渲染逻辑
  if (n1 === null) {
    // ...
  } else {
    patchElement(n1, n2, ...)
  }
}

我们只关心新旧节点都存在的update逻辑，所以接着看patchElement函数。

前置属性

在具体看patchElement之前，我们需要先了解两个前置属性：

1. PatchFlags

在vnode中有patchFlag这样一个字段，用来表示当前节点发生改变的类型。PatchFlags的所有枚举类型如下所示：

// shared/src/patchFlags.ts
export const enum PatchFlags {
  TEXT = 1,
  CLASS = 1 << 1,
  STYLE = 1 << 2,
  PROPS = 1 << 3,
  FULL_PROPS = 1 << 4,
  HYDRATE_EVENTS = 1 << 5,
  STABLE_FRAGMENT = 1 << 6,
  KEYED_FRAGMENT = 1 << 7,
  UNKEYED_FRAGMENT = 1 << 8,
  NEED_PATCH = 1 << 9,
  DYNAMIC_SLOTS = 1 << 10,
  DEV_ROOT_FRAGMENT = 1 << 11,
  HOISTED = -1,
  BAIL = -2
}

patchFlag所有的枚举类型都由二进制来表示，这样做的好处是很容易对多种类型进行判断，比如当前变化包括TEXT和CLASS。

在判断时，只需要对想要判断的类型进行&操作，如果大于0，说明包含此类型。

2. dynamicChildren

vue3中对静态节点做了标记，在patch阶段，不会比较静态节点，只会比较动态节点，即dynamicChildren内的节点。

patchElement

了解完上面两个属性后我们回归主线，看一下patchElement函数：

// runtime-core/src/renderer.ts
const patchElement = (n1, n2, ...) => {
  // 缓存旧的DOM节点，因为这是DOM的更新，所以旧DOM节点即 n1.el 一定存在
  const el = (n2.el = n1.el!)
  // 取出新节点的 patchFlag dynamicChildren 后面会进行判断
  let { patchFlag, dynamicChildren } = n2
  // 保存旧节点 props
  const oldProps = n1.props || {}
  // 保存新节点 props
  const newProps = n2.props || {}

  if (patchFlag > 0) {
    // 对所 props 都进行比较更新
    if (patchFlag & PatchFlags.FULL_PROPS) {
      patchProps(el, n2, oldProps, newProps, ...)
    } else {
      // 存在动态 class 属性时
      if (patchFlag & PatchFlags.CLASS) {
        if (oldProps.class !== newProps.class) {
          hostPatchProp(el, 'class', null, newProps.class, ...)
        }
      }
      // 存在动态 style 属性时
      if (patchFlag & PatchFlags.STYLE) {
        hostPatchProp(el, 'style', oldProps.style, newProps.style, ...)
      }
      
      // 针对除了 style、class 的 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) {
            hostPatchProp(el, key, prev, next, ...)
          }
        }
      }
      // 存在动态 文本
      if (patchFlag & PatchFlags.TEXT) {
        if (n1.children !== n2.children) {
          hostSetElementText(el, n2.children as string)
        }
      }
    } else if (dynamicChildren == null) {
      patchProps(el, n2, oldProps, newProps, ...)
    }
  }
  
  if (dynamicChildren) {
    patchBlockChildren(n1.dynamicChildren!, dynamicChildren, el, ...)
  } else {
    patchChildren(n1, n2, el, null, ...)
  }
}

对于DOM节点的更新主要是props和子节点的更新，其中利用patchFlag和dynamicChildren做了很多优化，不会每次都对props和子节点进行全量的对比更新。

下面这两张图对代码里的一些if else分支做了总结，vue3会充分利用patchFlag和dynamicChildren做优化，如果确定只是某个局部的变动，比如STYLE改变，那么只会调用hostPatchProp并传入对应的参数STYLE做特定的更新。

更新props

下面一一看下上图提到的几个函数具体做了什么：

1. hostPatchProp hostPatchProp函数会根据参数的 key执行相应的方法，比较简单。

// runtime-dom/src/patchProp.ts
export const patchProp = (el, key, prevValue, nextValue, ...) => {
  switch (key) {
    case 'class':
      // 更新 class
      patchClass(el, nextValue, isSVG)
      break
    case 'style':
      // 更新 style
      patchStyle(el, prevValue, nextValue)
      break
    default:
      // ...
      patchAttr(el, key, nextValue, isSVG)
  }
}

这几个方法都比较类似，最终都是调用原生的DOM API更新，其中看下patchClass方法，这个方法比较有意思的一点是，源码中注释写直接对className赋值比使用setAttribute方法要快，不得不说真的细hhhh。

// runtime-dom/src/modules/class.ts
export function patchClass(el, value) {
  if (value == null) {
    value = ''
  }
  ...
  // directly setting className should be faster than setAttribute in theory
  el.className = value
}

2. patchProps patchProps就如其名了，遍历所有属性，全部进行更新。

// runtime-core/src/renderer.ts
const patchProps = (el, vnode, oldProps, newProps, ...) => {
  if (oldProps !== newProps) {
    // 遍历 newProps 更新
    for (const key in newProps) {
      const next = newProps[key]
      const prev = oldProps[key]
      if (next !== prev) {
        hostPatchProp(el, key, prev, next, ...)
      }
    }
    
    if (oldProps !== EMPTY_OBJ) {
      // 遍历 oldProps
      for (const key in oldProps) {
        // 如果 存在某个属性 不在 newProps 调用 hostPatchProp 移除该属性
        if (!(key in newProps)) {
          hostPatchProp(el, key, oldProps[key], null,...)
        }
      }
    }
  }
}

3. patchBlockChildren

DOM是一颗树，不难想到会有子节点嵌套的情况，所以这里的子节点更新是一个深度优先遍历的过程，即更新完当前节点后，会去更新当前节点的子节点，不过vue3在这个过程中有所优化。具体会通过对patch的最后一个参数optimized传参来防止不必要的渲染。这里简单知道有这个优化即可，全部罗列出来比较繁琐，感兴趣的同学可以详细看看。

这个方法也比较简单，因为在编译的时候已经确定了哪些是动态节点，所以直接遍历所有的动态节点然后进行patch即可。

// runtime-core/src/renderer.ts
const patchBlockChildren = (oldChildren, newChildren, fallbackContainer, ...) => {
  for (let i = 0; i < newChildren.length; i++) {
    const oldVNode = oldChildren[i]
    const newVNode = newChildren[i]
    patch(oldVNode, newVNode, container, ...)
  }
}

4. patchChildren

对于子节点来说，只会有三种可能，分别是：文本节点、数组和空。所以这个方法里所有的if else分支就是在考虑新旧节点可能的全部情况，并进行相应的处理。

// runtime-core/src/renderer.ts
const patchChildren = (n1, n2, container, ...) => {
  const c1 = n1 && n1.children
  const prevShapeFlag = n1 ? n1.shapeFlag : 0
  const c2 = n2.children
  
  const { patchFlag, shapeFlag } = n2
  
  // ...
  
  // children has 3 possibilities: text, array or no children.
  if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
    // text children fast path
    if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
      // 如果旧子节点是数组 先卸载
      unmountChildren(c1, parentComponent, parentSuspense)
    }
    if (c2 !== c1) {
      // 更新文本节点
      hostSetElementText(container, c2)
    }
  } else {
    if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
      // 旧子节点是数组
      if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        // two arrays, cannot assume anything, do full diff
        patchKeyedChildren(c1, c2, container, ...)
      } else {
        // 没有新子节点，直接卸载旧子节点
        unmountChildren(c1, parentComponent, parentSuspense, true)
      }
    } else {
      // prev children was text OR null
      // new children is array OR null
      if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
        hostSetElementText(container, '')
      }
      // mount new if array
      if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        mountChildren(c2, container, ...)
      }
    }
  }
}

其中新旧节点都是数组的情况涉及到我们平常所说的diff算法，会放到后面专门去解析。

处理vue组件

看完处理DOM元素的情况，接下来看处理vue组件。再举一个例子🌰：

<template>
  <div>
    <button @click="add">add</button>
    <foo :num="num" />
  </div>
</template>
<script>
import { ref } from 'vue'
export default {
  setup () {
    const num = ref(1)
    function add() {
      num.value += 1
    }
    return {
      num,
      add
    }
  }
}
</script>
// foo 组件
<template>
  <div>
    <p>num is, {{ num }}</p>
  </div>
</template>
<script>
  export default {
    props: {
      num: Number
    }
  }
</script>

这个例子就是将之前的普通元素标签换成了foo组件，foo组件接收num props，点击add按钮就会加一。

让我们回到patch方法，当点击add按钮时会触发重新渲染，其中更新foo时会进入processComponent方法。

// runtime-core/src/renderer.ts
const processComponent = (n1, n2, container, ...) => {
  if (n1 === null) {
    // 首次渲染
    // ...
  } else {
    // 更新
    updateComponent(n1, n2, ...)
  }
}

在更新的时候我们只关心updateComponent。

// runtime-core/src/renderer.ts
const updateComponent = (n1, n2, ...) => {
  // 缓存最新的 组件 vnode
  const instance = (n2.component = n1.component)!
  // 对比新旧 vnode 节点，
  if (shouldUpdateComponent(n1, n2)) {
      // ...
      // 把最新组件vnode 赋值给 instance.next
      instance.next = n2
      // in case the child component is also queued, remove it to avoid
      // double updating the same child component in the same flush.
      invalidateJob(instance.update)
      // instance.update is the reactive effect runner.
      instance.update()
  } else {
    // no update needed. just copy over properties
    n2.component = n1.component
    n2.el = n1.el
    instance.vnode = n2
  }
}

在updateComponent方法内部，先缓存最新的组件实例，接下来有一个优化点，会通过shouldUpdateComponent方法来比较新旧组件是否需要更新，这里主要是对比组件vnode的props、children等属性。这样的提前判断会避免不必要的渲染，如果需要渲染，会把最新的组件vnode赋值给instance.next，这在下面调用组件首次渲染时注册的instance.update副作用渲染函数时会使用到。

至于invalidateJob这个方法，它是从scheduler.ts文件中引出的，所以大概可以知道是处理调度相关。再结合注释和传入的参数，就比较明白了。DOM结构是一棵树，从上面的流程中可以知道，在更新一个节点时不光会更新节点本身，还会更新节点的子节点，所以，vue会在这里进行检查，看是否当前组件的副作用函数已经在队列中了，如果在，直接移除掉，反正再往下也会主动触发更新。这样就避免了二次重复渲染。

如果对比了新旧节点发现不需要更新，那很好办，就不会主动调用instance.update触发更新，仅仅是更新相关的属性。

接着执行instance.update，这个函数就是在setupRenderEffect内创建的。最终子组件的更新还会走一遍自己副作用渲染函数，然后patch子组件的子模板DOM，接上上面的流程。

update流程小结

其实到这里可能还是不太清楚整个流程是怎样的，还是以上面的例子为代表，我们从头捋一遍点击add后到底经历了哪些流程。首先我们有一个根组件app，app模板的根DOM元素是div，div里面有button元素和foo组件。app与foo之间通过props: num通信，点击button时num会加一。

当点击add后，app组件内的num更新，由于初次渲染时在组件实例上添加了响应式的update方法。app组件会触发自身的update。

// runtime-core/src/renderer.ts
// setupRenderEffect 函数内
instance.update = effect(function componentEffect() {
  if (!instance.isMounted) {
    ...
  } else {
    let { next } = instance
    if (next) {
      updateComponentPreRender(instance, next)
    } else {
      next = vnode
    }
    const nextTree = renderComponentRoot(instance)
    const prevTree = instance.subTree
    instance.subTree = nextTree
    patch(prevTree, nextTree, ..., instance)
  }
}, prodEffectOptions)

注意现在是app组件自身的数据变化，所以此时是没有next的，接下来渲染新的子组件vnode，得到真实的模版vnode nextTree，用新旧subTree进行patch。

因为对比的是app内模板的普通元素vnode，此时patch的元素类型是div，进入更新普通元素的流程，先更新props，再更新子节点，当前div下的子节点有button和foo组件，先更新button元素，再更新foo组件。

在更新foo组件时，会先将foo组件instance.next赋值为最新的foo子组件vnode，之后再主动调用foo.update进入上面的副作用渲染函数，这次的实例是foo组件且next存在值。之后就是同样的逻辑，进入foo组件的patch，后面就省略掉不细说了。

可以发现，一个组件的更新存在两种情况。在副作用渲染函数的内部，如果next不存在，是组件本身数据发生变化引发的update，next存在，是父组件更新子组件的时候引发的update。

diff算法

在前面分析更新普通元素子节点时，有一种情况是新旧子节点都是数组，这个时候就需要某种成本较低的策略进行diff更新。

先假设所有元素都拥有一个独一无二的key值。

我们可以先想一下，新旧子节点都是数组会有哪几种变化情况？

无论是哪种变化最后都是由更新、添加、删除、移动这四种操作的一种或者几种的组合。

源码里面划分的比较清晰，主要分为了三种情况：在同一位置添加一个或多个节点、在同一位置删除一个或多个节点和处理未知序列。

从上面这三种情况可以看出一个共性，从头开始的一部分和从尾部倒序的一部分（所有淡黄色的）可能是不需要改变的，不论哪种情况整体都可以分为从头部正序不需要改动的部分、中间发生变动的部分、从尾部倒序不需要改动的部分。所以在最开始，可以先进行头部和尾部的预处理。

源码里在diff算法的最开始，会先从头部正序扫描和从尾部倒序扫描，以便排除类型一样的干扰项，进一步的提高效率。

此处的类型一样指vnode节点的type、key都一样。

// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
  // 从头部开始扫描的索引
  let i = 0
  // 新节点长度
  const l2 = c2.length
  // 旧数组序列尾部索引
  let e1 = c1.length - 1
  // 新数组序列尾部索引
  let e2 = l2 - 1
  
  // 1. 正序扫描头部，找到不相同的为止
  while (i <= e1 && i <= e2) {
    // 当前扫描到的旧数组序列中的节点
    const n1 = c1[i]
    // 当前扫描到的新数组序列中的节点
    const n2 = c2[i]
    // 如果当前的新旧节点 type、key 相同，才为 true
    if (isSameVNodeType(n1, n2)) {
      // 更新
      patch(n1, n2, ...)
    } else {
      break
    }
    i++
  }
  
  // 2. 倒序扫描尾部，找到不相同的为止
  while (i <= e1 && i<= e2) {
    // 当前扫描到的旧数组序列中的节点
    const n1 = c1[e1]
    // 当前扫描到的新数组序列中的节点
    const n2 = c2[e2]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, ...)
    } else {
      break
    }
    e1--
    e2--
  }
  
  // ...
}

这段代码就像上面说到的那样，先从头部正序扫描，再从尾部倒序扫描，终止的条件是当前索引不能越界或者遇到新旧数组序列中的节点，类型不一样或者key值不一样，扫描到相同的节点会进行patch更新，这里不用操心当前的节点到底是否需要更新，patch函数内部会做相关的判断。

同一位置的添加、删除

这种情况相对而言比较简单，因为只涉及到添加或者删除这两种单一的原子操作之一，且位置还都是固定。

只需要扫描头部尾部，找出是在哪个位置进行的添加或删除，之后再进行相应的操作即可。

添加节点使用这个例子，从头部和从尾部扫描完毕之后，各个变量情况如图所示。

// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
  // ...
  
  // 1. 正序扫描头部，找到不相同的为止
  // 2. 倒序扫描尾部，找到不相同的为止
  // 3. if (同一位置添加节点)
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1
      const anchor = nextPos < l2 ? (c2[nextPos].el : parentAnchor
      while (i <= e2) {
        // 第一个参数 旧节点 为 null，新的挂载节点
        patch(null, c2[i], ...)
        i++
      }
    }
  }
  
  // ...
}

如果i > e1 && i <= e2，第一个条件语句表示当前索引已经到了旧数组序列除去尾部相同节点的末尾，但是还没到新数组序列除去尾部相同节点的末尾，意味着新的数组序列在旧的数组序列上新添加了一个或多个的连续节点，所以自然而然会命中新添加节点的情况。只需要对[i, e2]这个新数组序列内的节点依次进行挂载即可。

当然，如果扫描完毕后情况相反，即当前索引到了新数组序列除去尾部相同节点的末尾，但是还没到旧数组序列除去尾部相同节点的末尾，即发生变化的索引区间新数组序列小于旧数组序列的，这意味着新数组序列在旧数组序列的基础上删除了一个或多个节点。只需要对[i, e2]这个旧数组序列内的节点依次进行卸载即可。

// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
  // ...
  
  // 1. 正序扫描头部，找到不相同的为止
  // 2. 倒序扫描尾部，找到不相同的为止
  // 3. if (同一位置添加节点) 没有命中
  // 4. else if (同一位置删除节点)
  else if (i > e2) {
    if (i <= e1) {
      while (i <= e1) {
        unmount(c1[i], ...)
        i++
      }
    }
  }
  // ...
}

未知数组序列

如果没有命中上面的两种情况，那么就需要处理未知数组序列了。看一下下面这个例子。

先人工分析一下，中间发生变动的部分经过了哪些改变：

1. 有节点的 移动， d节点移动到 c节点前， e节点移动到 d节点前。
2. 有节点的 添加，添加了 h节点。

按照之前的流程，仍旧是先进行头部与尾部的预处理扫描，通过i、e1、e2圈出发生改动的区间。这个例子不符合添加和删除的分支，所以进入最后一个elsec处理未知序列的代码块     。

// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
  // ...
  
  // 1. 正序扫描头部，找到不相同的为止
  // 2. 倒序扫描尾部，找到不相同的为止
  // 3. if (同一位置添加节点)       没有命中
  // 4. else if (同一位置删除节点)  没有命中
  // 5. else 处理未知数组序列
  else {
    // 旧数组未知序列开始索引
    const s1 = i
    // 新数组未知序列开始索引
    const s2 = i
    
    // 5.1 创建新数组未知序列的 key -> 索引 map
    const keyToNewIndexMap = new Map()
    // 因为针对新数组未知序列创建 map，所以临界是 e2
    for (i = s2; i <= e2; i++) {
      // 遍历到的新数组的节点
      const nextChild = c2[i]
      // 前面已经假设一定存在 key 值
      if (nextChild.key !== null) {
        // 存储的 <key, value> 是 节点 key 值、索引
        keyToNewIndexMap.set(nextChild.key, i)
      }
    }
    // ...
  }
  // ...
}

注释5开始现在正式进入到处理未知序列的流程中，会根据新数组的未知序列建立一个keyToNewIndexMap<key, index>的map结构。只需要遍历新数组的未知序列即可，得到{ e: 2, d: 3, c: 4, h: 5 }。

遍历旧数组序列进行选择性的更新和移除

下面我们遍历旧数组的未知序列，根据key值且对照着刚刚建立的keyToNewIndexMap，查找旧数组序列中哪些节点仍然存在可以patch、哪些节点不存在需要移除、哪些节点需要移动。

// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
  // ...
  
  // 1. 正序扫描头部，找到不相同的为止
  // 2. 倒序扫描尾部，找到不相同的为止
  // 3. if (同一位置添加节点)       没有命中
  // 4. else if (同一位置删除节点)  没有命中
  // 5. else 处理未知数组序列
  else {
    // 旧数组未知序列开始索引
    const s1 = i
    // 新数组未知序列开始索引
    const s2 = i
    
    // 5.1 创建新数组未知序列的 key -> 索引 map
    // 5.2 遍历旧数组未知序列，使用 key 值，根据keyToNewIndexMap 找出哪些节点需要patch、移除、移动
    // 新旧数组中已经 patch 过的节点数
    let patched = 0
    // 所有待处理的节点，是新数组未知序列的长度
    const toBePatched = e2 - s2 + 1
    // 是否有节点需要移动
    let moved = false
    // used to track whether any node has moved 跟踪是否有节点移动
    let maxNewIndexSoFar = 0
    // 这个数组本身的 index 代表新数组元素的索引，数组的值代表旧数组元素的索引
    const newIndexToOldIndexMap = new Array(toBePatched)
    // 初始化数组值为 0
    for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
    // 遍历旧数组未知序列
    for (i = s1; i <= e1; i++) {
      // 当前的 旧节点
      const prevChild = c1[i]
      // 如果已经 patch 过的旧节点数大于等于 所有新数组中待处理的节点
      // 说明所有新数组中的节点都已经 patch 完毕，其余的要移除
      if (patched >= toBePatched) {
        unmount(prevChild, ...)
        continue
      }
      let newIndex
      // 假设 key 一定存在
      if (prevChild.key != null) {
        // 从 keyToNewIndexMap 中获取当前节点在新数组中的索引
        newIndex = keyToNewIndexMap.get(prevChild.key)
      }
      // 如果当前节点在新数组中找不到，说明新数组中没有，移除该节点
      if (newIndex === undefined) {
        unmount(prevChild, ...)
      } else {
        // 更新数组，因为默认值是 0，i 有可能是 0，+ 1 避免和默认值冲突
        newIndexToOldIndexMap[newIndex - s2] = i + 1
        // maxNewIndexSoFar 初始值是0
        // 每次maxNewIndexSoFar赋值的是当前节点在 新数组中的索引
        // 如果新数组的顺序和旧数组一样，那么就是递增的
        // false 说明顺序发生改变
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex
        } else {
          moved = true
        }
        // patch 新旧节点中匹配的节点
        patch(prevChild. c2[newIndex], ...)
        // 当前 patch 过的节点数 +1
        pached++
      }
    }
  }
  // ...
}

因为现在的DOM还是由旧数组生成的，我们需要知道当前的这些旧DOM节点是需要更新还是删除还是移动。所以我们要去遍历旧数组的未知序列，并结合刚生成的keyToNewIndexMap与新数组的未知序列进行对比。

先定义了几个变量。patched表示当前已经更新的节点数，toBePatched表示当前待更新的全部节点，通过这个描述我们也就知道了，如果patched大于等于toBePatched，那么剩下的旧节点就是要全部舍弃的。

moved用来表示当前是否有移动的节点。

maxNewIndexSoFar用来判断是否有节点移动。

newIndexToOldIndexMap这个数组本身的index代表当前节点在新数组序列中的索引，实际的值代表当前节点旧子序列索引。默认值全部是0。

接下来开始正式遍历旧数组，先取出旧数组序列里的节点c1[i]，然后判断patched是否大于等于toBePatched，如果是，卸载当前的旧节点，跳出本次循环。

如果当前更新的节点数没有大于等于所有待更新的节点数，那么开始更新keyToNewIndexMap这个数组，只需要通过key值从newIndexToOldIndexMap内取出相应的newIndex索引即可。

如果找不到索引，说明在新的数组序列中这个节点不存在，直接删除此节点。

如果找到了这个索引，那么更新newIndexToOldIndexMap[newIndex - s2] = i + 1，这里为什么要i+1呢？因为这个数组的默认值设置为了0，如果当前的i就是0，会引起冲突。

再往下执行，因为maxNewIndexSoFar 初始值是0，每次maxNewIndexSoFar赋值的是当前节点在新数组中的索引，如果新数组的顺序和旧数组一样，那么每次的maxNewIndexSoFar不可能大于newIndex。如果大于了，说明有节点发生了移动，需要将moved设置为true。

最后，没有经过前面的删除，证明当前的这个节点在新旧节点中都是存在的，那么直接patch(prevChild, c2[newIndex])即可。最后别忘记把记录已更新节点数变量patched加一。

移动和挂载新节点

通过moved变量，我们已经知道了当前有节点移动，下面需要处理的就是移动和挂载新节点。

vue3移动节点采取的策略是先得到最长递增子序列的索引newIndexToOldIndexMap。举个列子：

• [2, 3, 1, 0]的最长递增子序列是 [2, 3]，最终需要的索引是 [0, 1]

关于如何求解最长递增子序列，推荐看leetcode300最长递增子序列题解，在这里就不赘述具体算法实现了，主要目标仍然是在整体流程。

// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
  // ...
  
  // 1. 正序扫描头部，找到不相同的为止
  // 2. 倒序扫描尾部，找到不相同的为止
  // 3. if (同一位置添加节点)       没有命中
  // 4. else if (同一位置删除节点)  没有命中
  // 5. else 处理未知数组序列
  else {
    // 5.1 创建新数组未知序列的 key -> 索引 map
    // 5.2 遍历旧数组未知序列，使用 key 值，根据keyToNewIndexMap 找出哪些节点需要patch、移除、移动
    // 5.3 移动和挂载新节点
    // 如果有节点移动，得到 newIndexToOldIndexMap 的最长递增子序列的索引
    const increasingNewIndexSequence = moved
        ? getSequence(newIndexToOldIndexMap)
        : EMPTY_ARR
    // 用于节点移动判断
    let j = increasingNewIndexSequence.length - 1
    // 倒序新数组的未知序列，因为插入节点时使用 insertBefore 即向前插，倒序遍历可以使用上一个更新的节点作为锚点
    for (i = toBePatched - 1; i >= 0; i--) {
      // 当前在整个新数组中，未知序列的索引，s2 是头部相同节点的偏移量
      const nextIndex = s2 + i
      // 当前在整个新数组中，未知序列的节点
      const nextChild = c2[nextIndex]
      // 当前节点的下一个节点，如果当前节点是最后一个节点，那么取整个父节点的下一个节点作为插入点
      const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1] : parentAnchor
      // 如果仍然是默认值 0 证明是一个全新的节点
      if (newIndexToOldIndexMap[i] === 0) {
        // 挂载新的节点
        patch(null, nextChild, container, anchor, ...)
      // 存在节点移动
      } else if (moved) {
        // 当前索引不是最长递增子序列里的值，需要移动
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
          move(nextChild, container, anchor)
        // 当前索引是最长递增子序列里的值，j 指向下一个
        } else {
          j--
        }
      }
    }
  }
  // ...
}

在得到最长递增子序列索引后，设置一个变量j，它的初始值是最长递增子序列索引的length - 1，即指向其末尾，主要是用来判断节点是否需要移动。

下面会倒序遍历新数组的未知序列，因为无论是在patch中还是下面移动节点的move方法，其插入节点的操作都是使用insertBefore向前插入。在每一次倒序遍历的时候，如果需要的话我们可以很轻松的选取上一次已经处理完毕的节点作为基准，把当前节点，插入到它的前面。

进入到每一轮的遍历，其实会出现三种情况：

1. 使用newIndexToOldIndexMap用当前的新数组索引查找旧数组索引，发现是初始值0，表示旧数组中没有这个节点，那么使用patch方法挂载一个新的节点即可。

2. 当前的索引不在最长递增子序列中（j < 0会越界，所以提前可以确定不存在），说明当前节点需要移动，那么调用move(nextChild, container, anchor)即可。

3. 当前的索引恰好是最长递增子序列的值，说明该节点不需要移动，维护j变量。

到这儿，完成了对于未知序列的更新就完成了，下面看一下当前这个例子的具体执行过程。

没有key值的情况

上面的流程一直在假设每一个节点都有一个独一无二的key值，如果我们不写key值会怎样呢？

因为一般数组渲染都会使用v-for，所以在这里这个没有key值的情况指所有的新旧数组节点都没有key，而非有的节点存在key，有的节点不存在key。

如果没有写key值，在patchChildren函数内，会根据patchFlag进入patchUnkeyedChildren这个函数内。

// runtime-core/src/renderer.ts
const patchChildren = (n1, n2, ...) => {
  // ...
  
  if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
    patchKeyedChildren(...)
    return
  } else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
    // 无 key 值的情况
    patchUnkeyedChildren(...)
    return
  }
  
  // ...
}

其实对于不写key值的diff处理非常的简单粗暴，会先取新旧数组长度较小的作为公共长度，然后以这个较小的长度挨个进行遍历并对新旧数组的节点patch。

之后判断：

• 如果新数组的长度大于旧数组，说明有新增的节点，那么只需要接着挂载即可。
• 如果新数组的长度小于旧数组，说明有删除的节点，那么只需要从尾部开始删除即可。

// runtime-core/src/renderer.ts
const patchUnkeyedChildren = (c1, c2, ...) => {
  c1 = c1 || EMPTY_ARR
  c2 = c2 || EMPTY_ARR
  const oldLength = c1.length
  const newLength = c2.length
  // 选取较小长度作为公共部分
  const commonLength = Math.min(oldLength, newLength)
  // 依次 patch 
  for (let i = 0; i < commonLength; i++) {
    const nextChild = c2[i]
    patch(c1[i], nextChild, ...)
  }
  if (oldLength > newLength) {
    // remove old
    unmountChildren(...)
  } else {
    // mount new
    mountChildren(...)
  }
}

举个例子🌰：

我们可以很明显的看出这种情况的不足：没有利用任何一个旧节点，全部进行无脑的patch更新。

最后

到此，你已经看完了vue3更新时的整个流程和完整的diff算法～如果有收获的话，点个赞支持一下吧～

参考资料

• https://github.com/vuejs/vue-next/blob/master/packages/runtime-core/src/renderer.ts

• https://juejin.cn/post/6919376064833667080