我正在参加「启航计划」

源码调试

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

关于上文提到 ni，是相似npm/pnpm/yarn等包管理工具。了解可参阅：尤雨溪推荐神器 ni ，能代替 npm/yarn/pnpm ？简略好用！源码揭秘！

接下来咱们需求调试vue源码，我总结了2种常用方式，详细过程如下图：

  • sourcemap

    图解 vue diff 算法

  • vitest vscode扩展

    图解 vue diff 算法

参阅：据说90%的人不知道能够用测试用例(Vitest)调试开源项目(Vue3) 源码

diff 算法简介

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

图解 vue diff 算法

vue 框架对虚拟 dom 做了 diff 算法优化，将复杂度降到了O(n)，详细是怎么优化完成的：

图解 vue diff 算法

同层节点才彼此比较。 不同类型节点，直接进行毁掉/创建；类型相同的节点，使用算法优化查找效率。vue2、vue3 diff算法优化查找的战略不尽相同，下面咱们来详细探究学习吧！

vue2 diff算法

vue2 diff算法完成的源码：src/core/vdom/patch.ts

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

图解 vue 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 的有些差异，全体流程图如下所示：

图解 vue diff 算法

依据上述流程图，可总结出 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框架思维的小伙伴更好地了解其底层原理，取得提高！