【Vue】diff算法

Litchi 发布于

最后更新于

vdom 的核心就是使用 JS 模拟 DOM 节点，然后进行计算与对比，找出最小的更新范围，再更新 DOM 节点。而这个对比过程就是 diff 算法，所以说 diff 算法是 vdom 中最核心、最关键的部分。

diff 算法概述

diff 即对比，这是一个广泛的概念，例如 linux diff、git diff 等，vdom 中的 diff 就是对两颗树做 diff。树 diff 的时间复杂度为 O(n^3)，时间复杂度太高，算法不可用。但是后来创建框架的大佬们将 diff 算法的时间复杂度优化到 O(n)，具体改变如下：

  • 只比较同一层级，不跨级比较
  • tag 不相同，则直接删掉重建，不再深度比较
  • tag 和 key，两者都相同，则认为是相同节点，不再深度比较

(同一层级比较示例图)

snabbdom 源码解读

注意，本文不是一行行讲解源码，而是通过源码了解 diff 算法的过程。

虚拟 DOM 那一节讲过，snabbdom 的使用重点是：① h函数（根据传递进来的参数，返回一个 vnode 对象）；② vnode 对象（用来表示相应的 dom 结构）；③ patch 函数（找到最小更新范围并更新 DOM 节点）。

以下代码为 snabbdom 源码的缩略，对本文理解不重要的部分被省略，snabbdom 是使用 TypeScript 写的。

我们先看一下 snabbdom 中 h.ts 返回的 h 函数：

1
2
3
4
5
6
7
8
9
10
export function h(sel: string): VNode; // 只传标签
export function h(sel: string, data: VNodeData | null): VNode; // 传递标签和数据
export function h(sel: string, children: VNodeChildren): VNode; // 传递标签和子节点
export function h(sel: string, data: VNodeData | null, children: VNodeChildren): VNode; // 传递标签、数据、子节点
export function h (sel: any, b?: any, c?: any): VNode {
  // 省略具体的处理
  
  // 返回 vnode
  return vnode(sel, data, children, text, undefined);
};

可以看出最终返回的是 vnode 函数的返回值。再继续看一下 vnode 函数：

1
2
3
4
5
6
7
8
function vnode (sel: string | undefined,
  data: any | undefined,
  children: Array<VNode | string> | undefined,
  text: string | undefined,
  elm: Element | Text | undefined): VNode {
  let key = data === undefined ? undefined : data.key;
  return { sel, data, children, text, elm, key }; // elem是vnode对应的dom元素
}

可以看出最终返回的是一个对象。

我们使用 h 函数创建完 vnode 之后，最后一步就是使用 patch 函数给真实的 DOM 元素打补丁。就是在 patch 函数内找到最小更新范围并更新 DOM 节点。

diff 算法流程图（和下面的代码结合起来看）：

patch 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function patch (oldVnode: VNode | Element, vnode: VNode): VNode {
    // 省略部分代码

    // 第一个参数不是 vnode
    if (!isVnode(oldVnode)) {
      // 创建一个空的 vnode ，关联到这个 DOM 元素，后续比较的依旧是两个 vnode
      oldVnode = emptyNodeAt(oldVnode);
    }

    // 相同的 vnode（key 和 sel 都相等）
    if (sameVnode(oldVnode, vnode)) {
      // vnode 对比
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    
    // 不同的 vnode ，直接删掉重建
    } else {
      elm = oldVnode.elm!;
      parent = api.parentNode(elm);

      // 重建
      createElm(vnode, insertedVnodeQueue);

      if (parent !== null) {
        api.insertBefore(parent, vnode.elm!, api.nextSibling(elm));
        removeVnodes(parent, [oldVnode], 0, 0);
      }
    }

    // 省略部分代码
  
    return vnode;
  };

下面具体看一下 sameVnode 函数与 patchVnode 函数。

sameVnode 函数：

1
2
3
4
5
function sameVnode (vnode1: VNode, vnode2: VNode): boolean {
  // key 和 sel 都相等
  // undefined === undefined // true
  return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel;
}

上面说过，为了优化时间复杂度，我们会直接先比较 vnode 的 tag 与 key。若 tag 不相同则直接将节点删掉重建，这样子虽然比较暴力，但是可以大大优化时间复杂度，这是一种取舍。若 tag 与 key 相同时，则认为是相同节点，不再深度比较，直接使用 patchVnode 函数继续比较子节点。只有 v-for 时 key 是必须的，但是其他时候也可以给标签加上 key 属性，若没写 key，则 key 默认为 undefined，undefined 全等于 undefined。

patchVnode 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 此处我们不关心 insertedVnodeQueue
function patchVnode (oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
  // 省略部分代码

  // 设置 vnode.elem
  const elm = vnode.elm = oldVnode.elm!;
  
  // 旧 children
  let oldCh = oldVnode.children as VNode[];
  // 新 children
  let ch = vnode.children as VNode[];

	// vnode 和 oldVnode 全等，直接返回
  if (oldVnode === vnode) return;

  // 省略部分代码

  // 注意：vnode.text 和 vnode.children 不可能同时有值
  // vnode.text === undefined
  if (isUndef(vnode.text)) {
    // 新旧都有 children
    if (isDef(oldCh) && isDef(ch)) {
      if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
      // 新有children，旧无children （旧有text ）
    } else if (isDef(ch)) {
      // 清空 text
      if (isDef(oldVnode.text)) api.setTextContent(elm, '');
      // 添加 children
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
      // 旧有children，新无children
    } else if (isDef(oldCh)) {
      // 移除 children
      removeVnodes(elm, oldCh, 0, oldCh.length - 1);
      // 旧有text
    } else if (isDef(oldVnode.text)) {
      api.setTextContent(elm, '');
    }

    // else : vnode.text !== undefined （此时 vnode.children 无值）
  } else if (oldVnode.text !== vnode.text) {
    // 移除旧 children
    if (isDef(oldCh)) {
      removeVnodes(elm, oldCh, 0, oldCh.length - 1);
    }
    // 设置新 text
    api.setTextContent(elm, vnode.text!);
  }
  
  // 省略部分代码
}

若 vnode 和 oldVnode 都有 children，则需要调用 updateChildren 函数进行进一步比较。

updateChildren 函数：

这个函数很复杂，这里只是为了了解它的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// 此处我们不关心 insertedVnodeQueue
function updateChildren (parentElm: Node, oldCh: VNode[], newCh: VNode[], insertedVnodeQueue: VNodeQueue) {
  
  // 首先设置了 oldStartIdx、oldEndIdx、newStartIdx、oldEndIdx
  let oldStartIdx = 0, newStartIdx = 0;
  let oldEndIdx = oldCh.length - 1;
  let oldStartVnode = oldCh[0];
  let oldEndVnode = oldCh[oldEndIdx];
  let newEndIdx = newCh.length - 1;
  let newStartVnode = newCh[0];
  let newEndVnode = newCh[newEndIdx];
  let oldKeyToIdx: KeyToIndexMap | undefined;
  let idxInOld: number;
  let elmToMove: VNode;
  let before: any;
  
  // 循环开始，索引从两边往中间移动
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (oldStartVnode == null) {
      oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
    } else if (oldEndVnode == null) {
      oldEndVnode = oldCh[--oldEndIdx];
    } else if (newStartVnode == null) {
      newStartVnode = newCh[++newStartIdx];
    } else if (newEndVnode == null) {
      newEndVnode = newCh[--newEndIdx];

      // 以下是 snabbdom 中的对比方式，不同的框架中的对比方式可能有所不同
      // 开始和开始对比
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];

      // 结束和结束对比
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];

      // 开始和结束对比
    } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
      patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
      api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!));
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];

      // 结束和开始对比
    } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
      patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
      api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];

      // 如果都不满足以上四种情形，则说明新children和旧children的开始和结束节点没有相同的。
      // 于是通过查找 key  来看是否有对应的节点，如果 key 值无对应，则没有对应节点，
      // 直接新建节点并插入；如果 key 值有对应，则再看 sel 值是否相等。若 sel 不相等，
      // 则新建节点并插入；否则调用 patchVnode，并将节点插入对应位置。
    } else {
      if (oldKeyToIdx === undefined) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      }
      // 拿新节点 key ，能否对应上 oldCh 中的某个节点的 key
      idxInOld = oldKeyToIdx[newStartVnode.key as string];

      // 没对应上
      if (isUndef(idxInOld)) { 
        // 新建节点并插入
        api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!);
        newStartVnode = newCh[++newStartIdx];

        // 对应上了
      } else {
        // 对应上 key 的节点
        elmToMove = oldCh[idxInOld];

        // sel 是否相等（sameVnode 的条件）
        // sel 不相等
        if (elmToMove.sel !== newStartVnode.sel) {
          // 新建节点并插入
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!);

        // sel 相等，key 相等
        } else {
          patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
          oldCh[idxInOld] = undefined as any;
          api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
        }
        newStartVnode = newCh[++newStartIdx];
      }
    }
  }
  
  // 循环结束后，若是旧children先遍历完，则表示新children有剩余，把新children剩余节点批量
  // 插入到右边。若是新children先遍历完，则表示旧children有剩余，则把旧children剩余节点
  // 批量删除。
  if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
    if (oldStartIdx > oldEndIdx) {
      before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;
      addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
    } else {
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
    }
  }
}

注意，我们之前说过，diff 算法只比较同一层级，不跨级比较，因此我们这里谈论的比较都是对同一层级中的节点进行比较。

示例：

初始状态：

第一步：

第二步：

第三步：

第四步：

第五步：

第六步：

循环结束

将 new 中剩余节点加入

最后结果：

Litchi

Litchi

怕什么真理无穷，进一寸有一寸的欢喜

41
0
4
CATEGORIES
TAGS
ES HTTP Vue 综合