源码调试

1.源码的学习步骤

看开源代码，第一步一般是看 README.md 和 contributing.md 贡献指南文档。

README.md 中一般有提到贡献指南文档的链接的。contributing.md 贡献指南文档就是为了让别人参与项目贡献。

第二步，克隆项目，按照贡献指南，把项目跑起来。

2.如何调试vue源码？

下载 vue2/3 源码，我们以 vue3 为例，先来看看contributing.md文档：

Development Setup You will need Node.js version 16+, and PNPM version 7+. We also recommend installing ni to help switching between repos using different package managers. ni also provides the handy nr command which running npm scripts easier. After cloning the repo, run:

$ pnpm i # install the dependencies of the project

接下来我们需要调试vue源码，我总结了2种常用方式，具体步骤如下图：

• sourcemap

• vitest vscode扩展

diff 算法简介

diff 算法对比2棵树的目的是为了找到哪些节点发生了变化，哪些节点没有发生变化可以复用。如果用最传统的diff算法，如下图所示，每个节点都要遍历另一棵树上的所有节点做比较，这就是o(n^2)的复杂度，加上更新节点时的o(n)复杂度，那就总共达到了o(n^3)的复杂度。

vue 框架对虚拟 dom 做了 diff 算法优化，将复杂度降到了O(n)，具体是如何优化实现的：

同层节点才相互比较。 不同类型节点，直接进行销毁/创建；类型相同的节点，使用算法优化查找效率。vue2、vue3 diff算法优化查找的策略不尽相同，下面我们来具体探索学习吧！

vue2 diff算法

vue2 diff算法实现的源码：src/core/vdom/patch.ts

diff 算法源码比较复杂，转化为流程图方便理解其算法思想，如下图所示：

根据上述流程图，可总结出 vue2 diff 算法优化查询策略：

• while 循环判断 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx 时，比较新旧节点的children（4种情况）： ① 头和头比 判断是否相同 sameVnode(oldStartVnode, newStartVnode)，新旧节点头指针都向右移一位，然后进入下一轮循环判断； ② 尾和尾比 判断是否相同 sameVnode(oldEndVnode, newEndVnode)，新旧节点尾指针都向左移一位，然后进入下一轮循环判断； ③ 头和尾比 判断是否相同 sameVnode(oldStartVnode, newEndVnode)，旧节点头指针向右移一位，新节点尾指针向左移一位，然后进入下一轮循环判断； ④ 尾和头比 判断是否相同 sameVnode(oldEndVnode, newStartVnode)，旧节点尾指针向左移一位，新节点头指针向右移一位，然后进入下一轮循环判断； ⑤ 其他 先判断 newStartVnode 的 key 是否存在，key 不存在则创建节点；若 key 存在，旧节点从前向后和 newStartVnode 的节点匹配是否相同，新节点头指针向右移一位，然后进入下一轮循环判断；
• 当 oldStartIdx > oldEndIdx，添加 newStartIdx 到 newEndIdx指针指向的节点。
• 当 newStartIdx > newEndIdx，移除 oldStartIdx 到 oldEndIdx指针指向的节点。

vue3 diff算法

vue3 diff算法的源码：packages/runtime-core/src/renderer.ts

vue3 diff 算法和 vue2 的有些差异，整体流程图如下所示：

根据上述流程图，可总结出 vue3 diff 优化查询策略：

①从头比对，自左向右 判断 isSameVNodeType(n1,n2) 新旧节点是否相同，相同进行 patch 更新，遇到不同节点就退出该循环； ②从尾比对，自右向左 判断 isSameVNodeType(n1,n2) 新旧节点是否相同，相同进行 patch 更新，遇到不同节点就退出该循环； ③新节点多于旧节点，需要挂载 通过以上2个循环后，如果 i>e1 && i<=e2，说明新节点多于旧节点，需要挂载多余新节点； ④旧节点多于新节点，需要卸载 同步骤③，当以上2个循环终止后，如果 i>e2，说明旧节点多于新节点，需要卸载多余旧节点； ⑤未知序列，乱序

• 构建 keyToNewIndexMap（key:index关系索引），记录记录旧节点元素在新节点中的位置关系；
• 遍历处理旧节点，判断 keyToNewIndexMap.get(prevChild.key)，如果新节点不在旧节点中，则删除节点；如果在，进行patch更新；
• 基于最长递增子序列算法，进行节点的移动和新增。

算法扩展：最长递增子序列

求最长递增子序列是 LeetCode 上的一道经典算法题，原题：300. 最长递增子序列。

什么是最长递增子序列？

删除（或不删除）数组中的元素，且不改变其余元素顺序，得到的子序列是升序的，叫递增子序列，子序列长度最长的就叫做最长递增子序列。

最长递增子序列在 diff 中有什么作用?

所谓的 diff 算法，简单来讲就是用来对一组节点进行比对更新：新增、删除、patch和移动。

我们举个例子，看一组新旧节点，具体来分析下节点更新策略：

旧节点：[c, d, e, f]
新节点：[e, c, d, i]

要得到上述新节点，有2种更新策略： ① c,d 节点不动，e 节点移动到 c 前面，删除 f 节点，然后在 d 后面新增 i 节点；（需要移动1次） ② e 节点不动，c,d 节点移动到 e 后面，删除 f 节点，然后在 d 后面新增 i 节点。（需要移动2次）

由上述分析，显然方法 ① 最优，移动次数最少。因此我们可知：最长递增子序列的确定，可以最大程度减少移动次数，有效地提升 diff 性能。

vue3 中，最长递增子序列源码实现

Vue3 内部，使用的是贪心+二分查找的算法来求解最长递增子序列的，具体源码如下：

/**
 * 求最长递增子序列：贪心+二分查找
 * @param arr 
 * @returns 
 */
function getSequence(arr: number[]): number[] {
  // 浅拷贝数组，不影响原数组 arr
  const p = arr.slice()
  // 定义返回数组（最长递增子序列的下标）
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    // 获取当前下标对应元素
    const arrI = arr[i]
    // 排除等于 0 的情况
    if (arrI !== 0) {
      // 获取 result 中的最后一个元素
      j = result[result.length - 1]
      // 当前值 > 最后一个元素，说明存在升序序列，将下标放入 result 返回数组
      if (arr[j] < arrI) {
        // 存储在 result 更新前的最后一个索引的值
        p[i] = j
        result.push(i)
        continue
      }
      u = 0 // 初始下标
      v = result.length - 1 // 终止下标
      // 二分查找，查找比 arrI 小的节点
      while (u < v) {
        // 获取中间位置 c
        c = (u + v) >> 1
        // 如果中间位的值 < arrI，则 u = 中间位 + 1
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          // 否则，v = c（中间位置）
          v = c
        }
      }
      // 如果 arr[result[u]] < arrI，则证明当前 证明当前 result 中存在的下标不是递增序列，则需要进行替换
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        // 进行替换，替换为递增序列
        result[u] = i
      }
    }
  }

  u = result.length
  v = result[u - 1]
  // 回溯数组p，找到最终的索引
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

vue3 对比 vue2 diff 优化部分

• Vue2 节点更新是全量Diff，Vue3 是静态标记+非全量Diff Vue2中，当数据发生变化，会生成一个新的 newVnode，和之前的 oldVnode 进行比较，找到差异点进行更新。而Vue3，在创建虚拟DOM树时，会根据DOM内容不会变化的打上静态标记，之后patch对比更新的时候，只比对不带静态标记的节点。
• Vue3 优化了 diff 查询策略 Vue3 基于最长递增子序列算法，进行移动/添加/删除/patch 更新，覆盖了Vue2 diff ③-⑤ 步骤，极大优化查询比较性能，其中 key 最大程度减少 DOM 的移动，减少了DOM操作。

总结

上述行文，主要是将vue2、vue3的 diff 算法代码实现转化成逻辑流程图并对比其差异，希望能帮助正在学习vue框架思想的小伙伴更好地理解其底层原理，获得提升！