关于vue.js:史上最详细的-Vue-3-渲染过程与-diff-图解

前言

大家好，我是 Miyue，人称“小米”（不是那个小米）~

从上一篇 从 CreateApp 开始学习 Vue 源码 中，根本理解了 createApp() 与 app.mount() 两个办法的起源和大抵执行过程，这里仍然以上文的流程图来进行回顾：

所以在创立好利用 app 后执行 mount 函数，通过 createVNode 将咱们的入口组件 App.vue 转换成 VNode 树，最初应用 patch() 函数将 VNode 树转换为实在 Dom 渲染到页面上。

而 Vue 3 的 diff 算法，与 Vue 2 一样，仍然在 patch 过程中。

那么首先，先来看一下 VNode 的生成吧~

createVNode – 生成虚构节点

createVNode，即创立一个 VNode 虚构节点对象。

它最多接管 5 个参数（当然在 createApp 的时候只有一个 App.vue），其中 type 能够是一个字符串，也能够是一个 class 组件或者一般组件，甚至能够是一个 VNode 对象。

所以首先会对 type 进行解决，在没有传入 type 或者指定为 v-ndc 时，会主动转成 正文节点 类型，而后判断是否曾经是一个 VNode 对象；如果是的话，则返回对传入 VNode 的拷贝对象（除了局部属性之外，其余属性都是浅层拷贝）。

如果不是一个 VNode 的话，则进入后续循环（App.vue 就不是）。

之后的过程会先解决组件的 class 和 style 绑定格局，而后解决传入 type 参数对应的 VNode 对象类型，最初通过 createBaseVNode() 创立 VNode 返回。

而后，mount 函数外部会通过 render 函数进行 VNode 到实在 dom 的解析和渲染。

而 render 函数外部则是依据是否有新的 VNode 对象来确认是 挂载 / 更新 还是 卸载 dom 节点 —— 如果有新的 VNode 对象，则调用 patch 进行 VNode 的解析与渲染；否则调用 unmount 进行卸载。

patch 函数 – VNode 节点的分类解决

在 Vue 我的项目的开发过程中，咱们都晓得 组件与 HTML 元素都是通过标签在模板中应用的 ，并且除了元素与组件之外，可能还有正文节点等内容。所以在解析的时候也须要 依据不同的节点类型进行分类解决。

所以 patch 函数的次要性能就是 依据 VNode 对象的不同类型调用对应的解决办法，如果有绑定 ref 属性，则还会将绑定的 ref 元素（dom 节点或者组件实例）增加到以后的 Vue 实例上。

整个 patch 过程包含以下几步：

1. 判断新旧 VNode 对象是否完全一致，统一时间接退出
2. 如果新旧 VNode 对象的 类型不统一 ，则 卸载旧节点，将旧节点置为 null 进行后续逻辑
3. 依据新节点的 patchFlag 配置是否须要优化
4. 依据新节点的 type 类型，调用不同的解决办法；这里大部分办法名都是以 process 结尾，意为加工、解决对应元素
5. 如果设置了 ref 属性，则调用 setRef 解决对应绑定关系

过程图如下：

processFunctions – 节点理论处理过程

在 patch 过程中依据不同的 VNode.type 进行解决之后，别离会调用不同的函数来进行虚构节点的理论解决与 dom 更新。其中有相似文本与正文这样的简略节点，也有具备多个子元素或者动静组件等这样的简单标签，那么从易到难，先从简略的标签说起。

processText 与 processCommentNode

const processText = (oldVnode, newVnode, container, anchor) => {if(!oldVnode) {hostInsert(newVnode.el = hostCreateText(newVnode.children), container, anchor)
  } else {const el = (newVnode.el = newVnode.el!)
    if (newVnode.children !== oldVnode.children) {hostSetText(el, newVnode.children)
    }
  }
}
const processCommentNode = (oldVnode, newVnode, container, anchor) => {if(!oldVnode) {hostInsert(newVnode.el = hostCreateComment(newVnode.children), container, anchor)
  } else {newVnode.el = oldVnode.el}
}

纯文本节点很好了解，不存在旧内容时就在父级节点（container）中插入节点的文本内容，存在旧节点则首先比拟值是否相等，不等就更新。

而正文节点与纯文本不同的是，在更新的时候会间接更新 el 属性。

mountStaticNode – 挂载动态节点

如果是 开发环境 ，内容更新时还会用 patchStaticNode 来进行更新，然而 生产环境下只会在原节点被销毁之后才会进行挂载 ，也就是在 Vue 3 中提到的 动态晋升，用来进行性能优化。

非开发环境下，只有以下逻辑：

case Static:
  if (oldVnode == null) {mountStaticNode(newVnode, container, anchor, isSVG)
  }

// ...

const mountStaticNode = (n2, container, anchor, isSVG) => {[n2.el, n2.anchor] = hostInsertStaticContent!(
    n2.children,
    container,
    anchor,
    isSVG,
    n2.el,
    n2.anchor
  )
}

即间接将这个节点的内容插入到父级元素的指定地位下。

依据官网给出的 demo，大部分 template 中的内容都会编译为 StaticNode，例如：

processFragment – 多根节点解决

在 Vue 2 中，每个单文件组件下只能有一个根节点，而 Vue 3 中做了改良，咱们能够在单个组件的模板中间接增加多个根节点标签（jsx 写法仍然只能有一个根节点，因为须要合乎 jsx 标准）。

在咱们通过 create-vite 脚手架创立的我的项目中，App.vue 就是一个多根节点组件，此时就会进入到该函数逻辑中。

1、首次渲染

多根节点在首次渲染时逻辑较为简单，大抵如下：

const processFragment = (n1, n2, container, anchor, parentComponent, parentSuspense, isSVG,
  slotScopeIds, optimized) => {const fragmentStartAnchor = (n2.el = n1 ? n1.el : hostCreateText(''));
  const fragmentEndAnchor = (n2.anchor = n1 ? n1.anchor : hostCreateText(''));
  let {
      patchFlag,
      dynamicChildren,
      slotScopeIds: fragmentSlotScopeIds
  } = n2;
  if (fragmentSlotScopeIds) {
      slotScopeIds = slotScopeIds ?
          slotScopeIds.concat(fragmentSlotScopeIds) :
          fragmentSlotScopeIds;
  }
  if (n1 == null) {hostInsert(fragmentStartAnchor, container, anchor);
      hostInsert(fragmentEndAnchor, container, anchor);
      mountChildren(n2.children, container, fragmentEndAnchor, parentComponent, parentSuspense,
          isSVG, slotScopeIds, optimized);
  }
}

首次渲染与更新都有独特逻辑，即 设置多根节点组件的开始与终止锚点，而后将组件的每个根节点按程序向两头插入。

因为 App.vue 中的内容不便解析，咱们新增一个多根组件 FragmentOne，内容如下：

<template>
  <div class="fragment-1">
    <h1>{{name}} Page</h1>
  </div>
  <div class="fragment-2">
    <h1>Fragment Page</h1>
  </div>
  <div class="fragment-3">
    <h1>Fragment Page</h1>
  </div>
</template>

<script lang="ts" setup>
import {ref} from 'vue'
const name = ref<string | undefined>('FragmentOne')
</script>

当这个组件被解析到时，它会被编译成以下内容：

其中 children 数组中就是每一个根节点，而后在解决锚点时，因为是首次渲染，两个锚点会间接设置为两个空文本节点：

最初，会通过 mountChildren 办法遍历 children 数组，顺次执行 patch() 解决每一个子元素。

2、派发更新

多根组件的更新相比首次挂载要 简单很多 ，会依据 所有根节点的稳定性 来离开解决。

这里的稳定性指的是每个节点是否有 key，程序是否不变等，个别状况下是 非间接 v-for 创立的多根节点，程序与个数都不会扭转，然而每个节点外部可能会产生扭转，例如 create-vite 创立的我的项目中的 App.vue；当是稳固节点时，patchFlag 的值等于 64

大抵代码如下：

if (patchFlag > 0 && patchFlag & 64 && dynamicChildren && n1.dynamicChildren) {patchBlockChildren(n1.dynamicChildren, dynamicChildren, container, parentComponent, parentSuspense, isSVG, slotScopeIds);
    if (parentComponent && parentComponent.type.__hmrId) {traverseStaticChildren(n1, n2);
    } else if (n2.key != null || (parentComponent && n2 === parentComponent.subTree)) {traverseStaticChildren(n1, n2, true);
    }
} else {patchChildren(n1, n2, container, fragmentEndAnchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);
}

这里有两种状况：

1. 是稳固节点然而具备动静节点（v-for循环等），通过 patchBlockChildren 独自解决动静节点；而后通过 traverseStaticChildren 进行所有子节点的 el 属性解决
2. 不是稳固节点，则通过 patchChildren 来比照和更新每个子节点

patchChildren 最终就会进入 Vue 3 的外围 diff 过程 —— patchKeyedChildren。

Teleport.process & Suspense.process

在解决 一般 dom 元素 Element 与 Vue 组件 Component 的渲染之前，咱们先来理解一下 Vue 3 新增的 teleport 传送组件和 suspense 异步组件吧。

在下面的 patch 函数中，Teleport 和 Suspense 在 createVNode 阶段，会生成 绝对非凡的 VNode 对象，在 process 过程中，间接调用 Vnode 的 process() 办法。

这两个办法都接管一个 internals 参数，蕴含 renderer.ts 中定义的一系列挂载与更新的办法

const internals = {
    p: patch,
    um: unmount,
    m: move,
    r: remove,
    mt: mountComponent,
    mc: mountChildren,
    pc: patchChildren,
    pbc: patchBlockChildren,
    n: getNextHostNode,
    o: options
}

1、Teleport

作为新增组件，它的作用是 将组件外部的内容挂载到指定元素下，所以它在挂载和更新时须要独自解决。

而外部的逻辑与 fragment 有点儿相似：

1. 首次渲染

与 fragment 一样须要先设置锚点，而后依据 to 属性查找指定挂载元素 target。

如果 target 存在则将锚点插入进去，而后依据 disabled 配置来确认挂载对象，通过 mountChildren 将内容插入进指标元素中。

2. 派发更新

在更新时，一样会读取 disabled 和 to 两个属性的配置，然而首先会与 fragment 一样依据外部的动静节点等进行子节点内容先进行更新。

而后判断 disabled 和 to 是否有变动，如果有变动则会通过 moveTeleport 对组件外部的内容进行挪动。

最初通过 updateCssVars 更新 data-v 属性，解决 css 变量和作用域等。

大抵过程如下：

图中对 patchChildren 进行了省略，与下面 processFragment 的办法是一样的。

2、Suspense

Vue 3 文档中提醒的是这是一项 试验性功能，用来批量治理异步组件树（感觉有点儿相似于 Promise.all()）。

所以它的场景会有两种：加载中与加载完结。Suspense 提供两个插槽：default 和 fallback，其中 fallback 用来显示加载中状态，当加载完结后，会卸载 pending 状态的 fallback 内容而后加载异步组件的后果（也就是 default 插槽内的内容）。并且只有当 default 插槽内的 根节点产生扭转时，才会从新触发加载中状态。

所以它的处理过程就是 首次解析时会从新创立 default 与 fallback 两个插槽中的节点信息，而后依据 default 插槽中的内容加载状态，来确定以后是否须要更新，并且会抛出相应的事件。

这个看起来有点儿简单，当前再具体的解析吧~

processComponent 组件解决

对 Component 自定义 Vue 组件的解决，同样会辨别 n1 == null 的状况来确认是挂载还是更新；Vue 中内置的 KeepAlive、Translation 等组件也一样会在这里进行解决。

如果是 KeepAlive 组件中包装的组件，会设置标记位 shapeFlag 为 ShapeFlags.COMPONENT_KEPT_ALIVE（1 << 9 = 512），因为 KeepAlive 中的组件会被缓存，如果再次切换的话，须要复原缓存状态，所以在组件从新 挂载 时会执行另外的逻辑 parent.ctx.activate()；非 KeepAlive 包裹的组件则间接调用 mountComponent 执行组件挂载。

而组件 更新 时，则只须要间接调用 updateComponent 更新组件内容。

在 mountComponent 过程中，会对该组件生成的 VNode 进行调整，通过 createComponentInstance 办法创立一个 组件实例 更新到 VNode 对象的 component 属性上，最初通过 setupRenderEffect 设置一个 renderEffect（行将组件的渲染作为副作用函数），进行组件模板中的数据依赖收集，并执行一次副作用函数实现组件的首次渲染（数据更新时就会触发这个 renderEffect 再次执行，更新 dom，组件实例一样有一个 isMounted 属性用来辨别是首次渲染还是更新）。

例如咱们下面的例子，有一个多根组件 FragmentOne，在引入到 App.vue 中进行解析的时候，会对 FragmentOne 创立一个 VNode 对象，如下图：

这个组件因为是间接应用的，所以会间接调用 mountComponent 办法。

此时会调用 createComponentInstance 为 VNode 对象创立一个组件实例：

而后通过 setupRenderEffect 创立渲染函数副作用。在这个副作用函数中，它对应的执行函数就是组件的解析与更新函数：componentUpdateFn。在 非 SSR 我的项目中，会通过 renderComponentRoot(instance) 对组件内容进行解析，失去一个组件内容对应的规范格局子元素 VNode 对象—— subTree，最初会通过 patch 对 subTree 进行解析和更新。

当然首次挂载的过程中还会对一些属性进行解决，保障后续进行更新时能失常比照。

而在更新阶段，首先会通过 shouldUpdateComponent 比拟新旧节点的信息（例如 props 参数、slots 插槽内容等是否扭转）来确定是否须要对该组件进行全量更新，如果都没扭转则间接继承原来的 dom 节点和 VNode 对象。

processElement HTML 元素解决

在解析模板生成 VNode 的过程中，没有指定节点类型是默认都会设置 shapeFlag 为 ShapeFlags.ELEMENT（512），也就是原生的 HTML 节点类型；大部分时候，咱们所说的 diff 算法外围局部也产生在这个过程中。

与 processComponent 相似，Element 元素的解决次要也只辨别 oldVnode（也就是办法中的 n1）是否为 null，如果是，则代表是首次渲染；如果不是，则代表是对这个节点进行更新。

依据这两种状况，源码中别离定义了两个办法：mountElement 挂载节点、patchElement 更新节点。

mountElement 的过程比较复杂，蕴含了根节点（这个元素节点）创立、内容（文本还是蕴含子节点）解决、款式和类名绑定、自定义指令、生命周期监听等。

而 patchElement 的过程也同样简单，除了与 mount 阶段一样须要解决款式类名绑定、自定义指令等内容之外，还要比拟新旧节点内容进行 patch 相干更新函数的解决。

patchChildren – 两种子节点 Diff 形式

在下面的不同类型的 VNode 节点的处理过程中，自定义组件 Component、传送组件 Teleport、多根节点 Fragment 和 原始 HTML 节点 Element 在 patch 更新过程中，在解决子节点时 都有可能会调用 patchChildren 来解决子节点的更新。

子节点更新的解决形式有两种：patchBlockChildren 和 patchChildren，其中 patchBlockChildren 个别是在 动静节点 dynamicChildren 确定时调用，外部会间接 依照新的节点的动静子节点 dynamicChildren 数组的长度，遍历子节点数组并通过 patch 办法比照旧的子节点数组同地位元素。

而 patchChildren 则是在节点不存在 dynamicChildren 时对所有子节点数组进行全量的比照更新。

_对于 block 和 PatchFlags 的相干内容，也能够查看《Vue.js 设计与实现》一书的第十七章第一节：编译优化 – 动静节点收集与补丁标记_。

在 patchChildren 过程中，会判断节点的 patchFlag 标记位，来确定 子节点数组是否配置了 key 属性 。如果 存在 key，则会通过 patchKeyedChildren 对 新旧所有子节点进行 diff 解决，具体比照可复用节点并调用 patch 进行节点的最小量更新 ；而对于 不存在 key 的子节点数组，则调用 patchUnkeyedChildren 办法 依照新旧子节点数组中的最小长度，遍历最小长度下 新旧节点同地位的元素调用 patch 办法进行比照，遍历完结后在解决残余节点元素（新的挂载旧的移除）。

1、patchUnkeyedChildren – 无 key 子节点解决

下面说了 patchUnkeyedChildren 会依照新旧子节点数组的 最小长度 进行遍历，所以首先会获取他们的长度进行比照失去较小的那个 length：

c1 = c1 || EMPTY_ARR
c2 = c2 || EMPTY_ARR
const oldLength = c1.length
const newLength = c2.length
const commonLength = Math.min(oldLength, newLength)

而后通过这个最小长度 commonLength 来进行遍历，解决 新旧数组的同地位的子节点：

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, ... )
}

最初在解决残余元素，移除旧的增加新的：

if (oldLength > newLength) {
  // remove old
  unmountChildren(c1, ... , commonLength)
} else {
  // mount new
  mountChildren(c2, ..., commonLength)
}

const unmountChildren = (children, ... , start = 0) => {for (let i = start; i < children.length; i++) {unmount(children[i], ...)
  }
}
const mountChildren = (children, container, ... , start = 0) => {for (let i = start; i < children.length; i++) {const child = (children[i] = optimized
      ? cloneIfMounted(children[i] as VNode)
      : normalizeVNode(children[i]))
    patch(null,child,container, ...)
  }
}

因为不存在 key，所以深刻比照新旧节点的变动更加耗费性能，不如间接 当做地位没有产生扭转，间接更新同地位节点。

2、patchKeyedChildren – 外围 Diff 过程

当节点 具备 key 属性时，节点更新时就会进行咱们常说的 diff 过程，外围也就是为了 dom 节点复用，把雷同 key 属性的节点视为同一节点，依据属性的理论变动来更新具体的 dom 属性，以达到起码操作的目标。

在 Vue 2 中，对于这种状况采纳的是 双端比照算法 来实现 新旧节点数组的全量比照 ， 然而这种办法不是最快的。

Vue 3 在此基础上，借鉴了 ivi 和 inferno 两个框架所用到的 疾速 Diff 算法，并在此基础上进行了扩大，失去了现在源码中应用的 diff 算法。

因为源码比拟长，我将过程简化后以两个字符串数组进行比拟：

const list = document.querySelector('#process');

const isSameVNodeType = (n1, n2) => (n1 === n2);
const unmount = (node) => {console.log('unmount', node);
};
const patch = (n1, n2) => {console.log('patch', n1, n2);
};
const move = (node, anchor) => {console.log('move', node, 'anchor', anchor);
};

// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr) {const p = arr.slice();
  const result = [0];
  let i;let j;let u;let v;let 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;
      while (u < v) {c = (u + v) >> 1;
        if (arr[result] < 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;
}


// 正式开始
// 定义新旧节点数据
const c1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
const c2 = ['a', 'b', 'e', 'd', 'h', 'f', 'g'];

// 设置初始数据
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // prev ending index
let e2 = l2 - 1; // next ending index

// 1. sync from start
while (i <= e1 && i <= e2) {const n1 = c1[i];
  const n2 = c2[i];
  if (isSameVNodeType(n1, n2)) {patch(n1, n2);
  } else {break;}
  i++;
}

// 2. sync from end
while (i <= e1 && i <= e2) {const n1 = c1[e1];
  const n2 = c2[e2];
  if (isSameVNodeType(n1, n2)) {patch(n1, n2);
  } else {break;}
  e1--;
  e2--;
}

// 3. common sequence + mount
if (i > e1) {if (i <= e2) {
    const nextPos = e2 + 1;
    while (i <= e2) {patch(null, c2[i]);
      i++;
    }
  }
}

// 4. common sequence + unmount
else if (i > e2) {while (i <= e1) {unmount(c1[i]);
    i++;
  }
}

// 5. unknown sequence
else {
  const s1 = i; // prev starting index
  const s2 = i; // next starting index

  // 5.1 build key:index map for newChildren
  const keyToNewIndexMap = new Map();
  for (i = s2;i <= e2;i++) {const nextChild = c2[i];
    if (nextChild != null) {keyToNewIndexMap.set(nextChild, 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;
  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) {
      // all new children have been patched so this can only be a removal
      unmount(prevChild);
      continue;
    }

    let newIndex;
    if (prevChild != null) {newIndex = keyToNewIndexMap.get(prevChild);
    } else {
      // key-less node, try to locate a key-less node of the same type
      for (j = s2;j <= e2;j++) {
        if (newIndexToOldIndexMap[j - s2] === 0 &&
            isSameVNodeType(prevChild, c2[j])
        ) {
          newIndex = j;
          break;
        }
      }
    }

    if (newIndex === undefined) {unmount(prevChild);
    } else {newIndexToOldIndexMap[newIndex - s2] = i + 1;
      if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex;} else {moved = true;}
      patch(prevChild, c2[newIndex]);
      patched++;
    }
  }

  // 5.3 move and mount
  const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : [];
  j = increasingNewIndexSequence.length - 1;
  for (i = toBePatched - 1;i >= 0;i--) {
    const nextIndex = s2 + i;
    const nextChild = c2[nextIndex];
    const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1] : null;
    if (newIndexToOldIndexMap[i] === 0) {
      // mount new
      patch(null, nextChild);
    } else if (moved) {if (j < 0 || i !== increasingNewIndexSequence[j]) {// move(nextChild, container, anchor, MoveType.REORDER)
        move(nextChild, anchor);
      } else {j--;}
    }
  }
}

这段代码能够间接在控制台运行，也能够间接查看文章结尾的代码片段（会更新细节问题）。

假如咱们有这样的节点变动：

旧节点：['a', 'b', 'c', 'd', 'e', 'f', 'g']

新节点：['a', 'b', 'e', 'd', 'h', 'f', 'g']

通过的 diff 过程如下：

其中能够分为以下几个大的步骤：

1. 从头开始、同地位比拟 ，直到 遇到 key 不一样的节点（也就是第三位 c 和 e，此时 i = 2）
2. 从尾开始、倒序同地位比拟 ，直到 遇到 key 不一样的节点或者第一步的进行位 i（也就是遇到倒数第三位 e 和 h，此时 e1 和 e2 都等于 4）
3. 通过前两步之后，剩下的节点尽管有雷同节点，然而程序曾经扭转，所以须要重新处理。这里与 Vue 2 中的 双端均不雷同 的状况有些相似的过程，都会将一个节点数组转为 map 模式而后遍历另一个数组进行匹配和更新。然而这里也一样有一些不同，咱们在前面剖析时进行具体阐明。

这里能够发现 理论执行过程并没有齐全匹配代码中的 5 种状况 ，这是因为 三和四这两种状况都是产生在前两步完结后曾经有一个节点数组曾经全副遍历结束。

疾速 Diff 算法

在剖析 diff 算法之前，先理解一下这个 疾速 diff 算法 的“疾速”次要是体现在哪个方面。

依据《Vue.js 设计与实现》的阐明：疾速 Diff 算法蕴含预处理步骤，这其实是借鉴了纯文本 Diff 算法的思路。在纯文本 Diff 算法中，存在对两段文本进行预处理的过程。

在这个过程中，会 别离查找头部完全一致的内容与尾部完全一致的内容，将其排除后再比拟残余内容。

例如：

两段文本中只须要更新的仅仅只有两头局部，须要将 vue 改为 react。

接下来，咱们以这个例子进行整个 diff 过程的解析~

1、从头查找最长雷同 key 节点

咱们假如当初有这样的内容：

它在第一步完结后，更新到了第二个节点；i 会停留在第一个不同的节点地位。

此时残余内容为：

旧节点：['c', 'd', 'e', 'f', 'g'];
新节点：['e', 'd', 'h', 'f', 'g'];

2、从尾部倒序查找最长雷同 key 节点

在第二步完结之后，会进行这样的更新：

这一步不会解决 i 的地位，而是从两个数组的最开端节点顺次按程序比照同地位节点：

3、旧节点数组被遍历完结

因为最后的例子中没有触发代码中的第三、四步，所以这里的例子进行一下调整：

旧节点：['c', 'd', 'e', 'f', 'g'];
新节点：['c', 'd', 'h', 'j', 'e', 'f', 'g'];

此时过程如下：

也就是对新节点数组残余元素进行顺次遍历和挂载

4、新节点数组被遍历完结

第 三、四、五 三个步骤属于 互斥状况，所以源码中采纳的是 if 判断

因为这三个状况不一样，所以这一步须要对后面的例子再进行批改，假如新示例如下：

旧节点：['c', 'd', 'h', 'j', 'e', 'f', 'g'];
新节点：['c', 'd', 'e', 'f', 'g'];

此时的步骤就刚好与第三步相同：

也就是对旧节点数组残余元素进行顺次遍历和卸载

5、残余节点比照（挪动、更新、卸载）

只有在这一步才用到了 最长递增子序列 算法。

在这一步开始之前，咱们先理解一下什么是 最长递增子序列算法。

5.0 最长递增子序列

“在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值顺次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不肯定是间断的“。

—— 维基百科

对于以下的原始序列

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

最长递增子序列为：

值得注意的是，生成的递增子序列数组中的元素，在原数组中对应的元素下标不肯定是间断的。

在 Vue 3 中，这个算法被提取成了一个工具办法 getSequence，位于 renderer.ts 文件的最底部 。并且，Vue 3 中最这个办法进行了革新，最终生成的子序列 是以可生成 最长 子串数组的可用元素的 最大索引。

如果应用 Vue 3 中的 getSequence 办法来解决下面的这个原始序列，会失去这样的后果：

区别如下：

getSequence 办法的大抵过程如下：

1. 复制一份 arr 数组，用于记录每个元素在递增子序列中的前驱元素。
2. 初始化 result 数组为 [0]，用于记录递增子序列的索引。
3. 遍历 arr 数组，如果以后元素不为 0，则在递增子序列 result 中查找比以后元素小的最大元素的索引 j。
4. 如果 arr[j] < arr[i]，则将 p[i] 赋值为 j，并将 i 增加到递增子序列 result 中。
5. 否则，应用二分查找在递增子序列 result 中查找比以后元素小的最大元素的索引 u。
6. 如果 arr[i] 小于 result[u]，则将 p[i] 赋值为 result[u-1]。
7. 将 i 增加到递增子序列 result 中。
8. 通过 p 数组回溯递增子序列，生成最终的递增新索引序列。

5.1 新节点残余元素构建 Map

这一步就很简略了，间接循环 newChildren 的 i 到 e2 之间的残余元素，组成一个 key => index 的 Map。

const s1 = (s2 = i);

const keyToNewIndexMap = new Map();
for (i = s2;i <= e2;i++) {const nextChild = c2[i];
  if (nextChild != null) {keyToNewIndexMap.set(nextChild, i);
  }
}

5.2 与旧节点的比照复用

在 newChildren 的对应关系 keyToNewIndexMap 创立好之后，就会遍历 oldChildren 比照 key 雷同的 VNode 实例进行复用和更新。

而对于比拟完结后仍旧残余的旧节点则间接进行 unmount 卸载（因为残余的旧节点 key 都不能复用，所以间接视为废除节点）。

简化代码如下：

let j;
let patched = 0; // 已更新节点数
const toBePatched = e2 - s2 + 1; // newChildren 残余节点数（须要更新）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);
    continue;
  }

  // 判断以后节点是否有 key，存在则在 map 中查找，// 不存在则遍历新节点残余数组的雷同节点并更新索引
  let newIndex;
  // 这里是判断 prevChild.key != null
  if (prevChild != null) {newIndex = keyToNewIndexMap.get(prevChild);
  } else {
    // key-less node, try to locate a key-less node of the same type
    for (j = s2;j <= e2;j++) {
      if (newIndexToOldIndexMap[j - s2] === 0 &&
          isSameVNodeType(prevChild, c2[j])
      ) {
        newIndex = j;
        break;
      }
    }
  }

  if (newIndex === undefined) {
    // 仍然没有找到同 key 或者同 VNodeType 的新节点，则卸载旧节点
    unmount(prevChild);
  } else {
    // 找到了对应新节点，比照索引地位设置 moved 标识，执行 patch 更新
    newIndexToOldIndexMap[newIndex - s2] = i + 1;
    if (newIndex >= maxNewIndexSoFar) {
      // 如果新节点的索引大于等于 maxNewIndexSoFar，// 则将 maxNewIndexSoFar 更新为新节点的索引
      maxNewIndexSoFar = newIndex;
    } else {
      // 阐明向前挪动了
      moved = true;
    }
    patch(prevChild, c2[newIndex]);
    patched++; // 已更新 +1
  }
}

为了能更加体现整个过程中变动，咱们将下面的例子进行一下裁减：

旧节点：['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n'];
新节点：['a', 'b', 'e', 'd', 'h', 'g', 'f', 'o', 'p', 'r', 'k', 'j', 'l', 'm', 'n'];

其中蕴含了前两步的 头部雷同节点，尾部雷同节点，两头局部也蕴含了卸载、挪动、更新三种状况，并且数据量曾经比拟大，能够看出整体过程。

在第一步新节点数组索引 Map 对象构建完结之后，咱们会的失去一个 size 为 10 的 keyToNewIndexMap，并且此时的 须要更新节点数标识 toBePatched 为 10（因为都有 key 属性，所以此时 toBePatched = keyToNewIndexMap.size()）。

而后会遍历旧节点数组查找 key 雷同的节点的下标 newIndex（如果找不到还会在 newChildren 新节点的残余数组中查找 未被应用过 newIndexToOldIndexMap[j - s2] === 0 且同类型判断 isSameVNodeType 为 true 的节点，并将它的 index 下标作为 newIndex）。

这个过程完结后，如果 newIndex 仍然是 undefined，则证实这个节点无奈被复用，间接卸载；如果存在的话，则调用 patch 比照更新新旧节点元素。

大抵过程如下：

此时新节点残余数组中依然还有残余元素没有被挂载，而且节点程序不对，就须要进行最初一步：新建节点与地位挪动

5.3 新建节点与地位挪动

在这一步的开始，会判断 5.2 完结后的 moved 标识，判断是否须要进行挪动断定；如果需要的话，会通过 getSequence 查找地位更新的最长递增子串的 元素下标。

const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : [];
j = increasingNewIndexSequence.length - 1;

这里的 newIndexToOldIndex 记录了新节点残余数组中，每个节点的在旧节点残余数组中的地位下标，如果不存在记录则为 0。

此时数据如下：

这里的最长递增子串下标数组就是 [1, 4, 9]，对应的也就是 newChildren[4], newChildren[6], newChildren[11]，剩下的元素会依据这三个元素的地位进行插入。

而后，比照新旧节点的索引进行挪动或者新增：

if (newIndexToOldIndexMap[i] === 0) {patch(null, nextChild);
} else if (moved) {if (j < 0 || i !== increasingNewIndexSequence[j]) {move(nextChild, anchor);
  } else {j--;}
}

整个过程大抵为：

1. 获取子节点在新 VNode 中的地位 nextIndex 和子节点 VNode 对象 nextChild。
2. 获取子节点的后一个兄弟节点或父节点作为锚点 anchor。
3. 如果新旧 VNode 中该子节点对应的旧节点的索引为 0，则示意该子节点在旧 VNode 中不存在，须要新建该节点并挂载到容器中。
4. 如果该子节点须要挪动，则依据增序列和以后遍历的地位 i 的关系来判断是否须要挪动，如果须要挪动，则调用 move 函数来挪动该节点到正确的地位。

小结

到这里，Vue 3 的整个 渲染和更新 阶段的剖析就基本上完结了。

整个过程可能与咱们没有理解源码之前的了解有很大出入，比方笔者以前就认为 最长递增子串 是在更新阶段都会进行的算法，或者在 5.3 阶段的理论过程与 Vue 2 中的逻辑是相似的。

然而理论剖析之后才会发现整个过程与我的以前的了解天壤之别。

在 Vue 3 中，对模板的编译和渲染做了大量的优化，在 编译阶段 通过 动静节点收集和动态节点晋升 ，为 渲染阶段 的性能晋升打下了松软的根底，并且配合 疾速 Diff 算法 与 最长递增子串，相比 Vue 2 在 patchChildren 子节点更新 做出了微小晋升。

残缺流程能够查看 图解 diff（vue3）.svg

jcode

最初

本文到这里就完结啦~ 如果本文对你有帮忙，心愿你能点赞珍藏，如果文中有不当之处，也心愿你能在评论里及时指出，大家的反对也是我后退的能源~~

如果想要关注更多的前端内容，能够关注我的公众号：
MiyueFE 的前端圈，或者在 FrontendAskMeAnything 中提出疑难或者参加探讨~

最初，非常感激大家的浏览！

本文正在加入「金石打算」