Vue源码解析12-patch中的diff算法

发表于 | | 本文总阅读量 次

上篇文章说到了patch中的新增dom过程，这篇会说diif算法。Vue的diff算法是基于snabbdom的，另外网上也有很多分析的文章，我自己是看的掘金上的篇博客。

在这里我主要会从代码实现上来描述。

入口

在patch函数中，如果新旧 vnode 属于sameVnode，那么就会执行patchVnode过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function patch(oldVnode, vnode, hydrating, removeOnly) {
  // ...

  if (isUndef(oldVnode)) {
    // 创建dom
  } else {
    const isRealElement = isDef(oldVnode.nodeType); // 是否为真实dom元素
    // sameVnode成立条件： key相同 && tag相同 && 都有data && 相同的input type
    if (!isRealElement && sameVnode(oldVnode, vnode)) {
      // 有新vnode有旧vnode，同时oldVnode不是真实dom，需要执行diff逻辑
      // patch existing root node
      patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly);
    }
  }
  // ...
}

sameVnode的判断逻辑如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function sameVnode(a, b) {
  return (
    a.key === b.key && // key相等
    ((a.tag === b.tag && // 标签名相同
    a.isComment === b.isComment &&
    isDef(a.data) === isDef(b.data) && // 都有vnode.data或都没有vnode.data
      sameInputType(a, b)) || // 相同的input type
      (isTrue(a.isAsyncPlaceholder) && a.asyncFactory === b.asyncFactory && isUndef(b.asyncFactory.error)))
  );
}

function sameInputType(a, b) {
  if (a.tag !== 'input') return true;
  let i;
  const typeA = isDef((i = a.data)) && isDef((i = i.attrs)) && i.type; // data.attrs.type
  const typeB = isDef((i = b.data)) && isDef((i = i.attrs)) && i.type;
  return typeA === typeB || (isTextInputType(typeA) && isTextInputType(typeB));
}

Vue对于sameVnode的判断逻辑和snabbdom不同，这点可以了解下。真正的patch逻辑在patchVnode函数中。

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
51
52
53
54
55
56
function patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly) {
  if (oldVnode === vnode) {
    return;
  }

  const elm = (vnode.elm = oldVnode.elm);

  // ...

  // reuse element for static trees.
  // note we only do this if the vnode is cloned -
  // if the new node is not cloned it means the render functions have been
  // reset by the hot-reload-api and we need to do a proper re-render.
  if (isTrue(vnode.isStatic) && isTrue(oldVnode.isStatic) && vnode.key === oldVnode.key && (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))) {
    vnode.componentInstance = oldVnode.componentInstance;
    return;
  }

  let i;
  const data = vnode.data;
  // 调用prepatch钩子
  if (isDef(data) && isDef((i = data.hook)) && isDef((i = i.prepatch))) {
    i(oldVnode, vnode);
  }

  const oldCh = oldVnode.children;
  const ch = vnode.children;
  if (isDef(data) && isPatchable(vnode)) {
    // 调用update钩子，主要是处理属性和事件绑定
    for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
    if (isDef((i = data.hook)) && isDef((i = i.update))) i(oldVnode, vnode);
  }
  if (isUndef(vnode.text)) {
    if (isDef(oldCh) && isDef(ch)) {
      // 新旧children均存在，调用diff来更新children
      if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly);
    } else if (isDef(ch)) {
      // 只有新children，全部插入到elm下
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ''); // 消除文本节点
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue); // 内部调用的是createElm来生成每个child dom
    } else if (isDef(oldCh)) {
      // 只有旧children，删除他们
      removeVnodes(elm, oldCh, 0, oldCh.length - 1); // 主要是调用remove和destroy钩子
    } else if (isDef(oldVnode.text)) {
      // 新旧children均没有，删除文本节点
      nodeOps.setTextContent(elm, '');
    }
  } else if (oldVnode.text !== vnode.text) {
    // 更新静态文本内容
    nodeOps.setTextContent(elm, vnode.text);
  }
  if (isDef(data)) {
    // postpatch钩子
    if (isDef((i = data.hook)) && isDef((i = i.postpatch))) i(oldVnode, vnode);
  }
}

isStatic属性为true的条件是当前节点是静态节点，所以这里vnode和oldVnode都是静态节点。

(isTrue(vnode.isCloned) || isTrue(vnode.isOnce)) 我们在生成render函数字符串中，会有_m或_o，他们分别是renderStatic和markOnce方法(src/core/instance/render-static.js中)。我们的patchVnode是在数据变化后调用，render方法是不变的，只不过因为执行render函数时数据变了，所以生成的vnode对象和之前不同。以_m为例，再次执行_m函数，会直接从vm._staticTrees中获取tree，并通过cloneVNode方法克隆一份出来，这种情况下vnode.isCloned值为true。

addVnodes和removeVnodes用于批量新增、删除dom，这里不再展开。

剩下的主要逻辑是在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
function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
  let oldStartIdx = 0;
  let 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, idxInOld, vnodeToMove, refElm;

  // removeOnly is a special flag used only by <transition-group>
  // to ensure removed elements stay in correct relative positions
  // during leaving transitions
  const canMove = !removeOnly;

  if (process.env.NODE_ENV !== 'production') {
    checkDuplicateKeys(newCh);
  }

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      // 旧数组的开头为空，向后移一位
      oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
    } else if (isUndef(oldEndVnode)) {
      // 旧数组的结尾为空，向前移一位
      oldEndVnode = oldCh[--oldEndIdx];
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      // 旧数组的开头和新数组的开头sameVnode，调用patcVnode，各自均向后移一位
      patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      // 旧数组的结尾和新数组的结尾sameVnode，调用patcVnode，各自均向前移一位
      patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // Vnode moved right
      // 旧数组的开头和新数组的结尾sameVnode，调用patcVnode，旧数组向后移一位，新数组向前移一位
      patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
      // 将oldChildren的开头节点放到oldChildren结束节点之后，注意不是newEndVnode之后
      canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // Vnode moved left
      // 旧数组的结尾和新数组的开头sameVnode，调用patcVnode，旧数组向前移一位，新数组向后移一位
      patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
      // oldChildren的结尾节点放到oldChildren开头节点之前，注意不是newStartVnode之前，也不是整个oldChildren的开头
      canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      // oldKeyToIdx: oldCh中每个元素的key到索引的映射
      if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      // 找到newStartVnode在旧数组中的位置：根据key来映射或者迭代查找
      idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
      if (isUndef(idxInOld)) {
        // New element，创建新节点，并插入到oldStartVnode之前
        // 如果索引不存在，说明这个节点是新创建的，插入到旧数组的当前开头之前
        createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
      } else {
        // 待删除元素，这是需要移动位置的节点
        vnodeToMove = oldCh[idxInOld];
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue);
          oldCh[idxInOld] = undefined;
          // 将这个待删除节点移到旧数组开头节点之前
          canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
        } else {
          // same key but different element. treat as new element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
        }
      }
      newStartVnode = newCh[++newStartIdx]; // 新数组向后移一位
    }
  }
  if (oldStartIdx > oldEndIdx) {
    // oldCh已经全部比较完，将newCh中剩下元素当做新增节点，放到最后
    refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
    // 新增的节点
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
  } else if (newStartIdx > newEndIdx) {
    // newCh已经全部比较完，将oldCh中剩下元素全部移除
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
  }
}

这就是diff算法的核心了，已经加上了非常详细的注释。大家可以先参考其他的文章了解diff，然后再来这里看代码的实现会轻松很多。