React Virtual DOM reconciliation

2021.12.09

在介绍 React 的 virtual DOM diff 算法前，我们先来简单过一下 virtual DOM 的概念，

什么是 virtual DOM？

The virtual DOM (VDOM) is a programming concept where an ideal, or “virtual”, representation of a UI is kept in memory and synced with the “real” DOM by a library such as ReactDOM. This process is called reconciliation. - React Official doc

It's important to understand that virtual DOM isn't a feature. It's a means to an end, the end being declarative, state-driven UI development. Virtual DOM is valuable because it allows you to build apps without thinking about state transitions, with performance that is generally good enough. That means less buggy code, and more time spent on creative tasks instead of tedious ones. - rich harris

思考下，如果我们自己要实现一个 virtual DOM 的话，我们需要考虑什么？

1. 如何基于 DOM 创建一个 Virtual DOM（即如何创建一个 VNode）
2. 当 Virtual DOM 更新的时候，如果高效的同步到 DOM 去（即，只将改动部分 patch 到 DOM 上，因为对 DOM 的操作很消耗性能，也就是 diff 算法）

这里我们主要讲第二点，在 React 的官方 diff 算法（Reconciliation）文档里也有提到，因为 Tree Edit Distance 算法有着 O(n^3) 的复杂度，React 基于下面两点假设将其优化到了 O(n) 的复杂度，也就是所谓的启发式（heuristic）算法，该算法基于以下两点，

1. Two elements of different types will produce different trees.

   不同的元素类型（tag）会生成不同的 VDOM

2. The developer can hint at which child elements may be stable across different renders with a key prop.

   可以用 key 来标识 VNode

第二点主要是为了解决 diff 两个 list 的时候可以高效的 diff 的问题，像下面这样，如果我们只是在 list 头部插入了个新值，常规操作我们肯定是，依次比较第一个 li，有改动则 patch，然后第二个 li，。。。，但是这样就会有一个问题，在头部插入会让 diff 算法 patch 每一个 DOM 节点。

但是你可以看到，我们其实只改动了第一个 DOM 节点，所以更加高效的方式是直接在头部插入一个 DOM 节点就完事了。而 key 这个属性可以作为 DOM 节点的 id，我们在 diff 的时候，可以直接看旧的 list 里面有没有这个 key，没有的话，说明就是新增的，直接插入即可。

<ul>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

<ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

为了能帮助大家更好的理解，我们来看下 snabbdom 这个库，它是一个虚拟 DOM 的库，它的 diff 算法 和 React 的 diff 算法是一致的，也是基于上面两点，话不多说，一起看下，

首先是 React diff 的两条规则，在 snabbdom 里面就是这么个简单的函数，通过对比 tag 和 key，来决定要不要重新销毁重建一个 node，

function sameVnode(vnode1, vnode2) {
	...
	// rule1:同类型的 我们会 patch vnode，否则，直接销毁重建一个 vnode
	// rule2:如果 vnode 有 key 的话，那么我们用 vnode 来标识 vnode，当 key 不一致的话，我们也销毁重建，不然就直接 patch
    return isSameSel && isSameKey && isSameIs;
}

写了个 demo，源码在 这里，在点击 ul 元素的时候会更新 vnode，再次进行 patch，我们可以打开控制台打断点进行 step by step 的查看，

// init.js patch
const patch = init([
  // patch node 的时候会利用到这些模块，来决定什么要 patch 什么不用
  classModule,
  propsModule,
  styleModule,
  eventListenersModule,
]);

const container = document.getElementById("container");

const newVnode = h("ul#container", {}, [
  h("li", { key: "a" }, "li a"),
  h("li", { key: "1" }, "li 1"),
  h("li", { key: "3" }, "li 3"),
  h("li", { key: "b" }, "li b"),
]);

const vnode = h(
  "ul#container",
  {
    on: {
      click: () => patch(vnode, newVnode),
    },
  },
  [
    h("li", { key: "1" }, "li 1"),
    h("li", { key: "2" }, "li 2"),
    h("li", { key: "3" }, "li 3"),
  ]
);
patch(container, vnode);

先来看下 patch 方法，

function patch(oldVnode, vnode) {
  let i, elm, parent;
  const insertedVnodeQueue = [];

  // 创建一个空的 vnode
  if (!isVnode(oldVnode)) {
    oldVnode = emptyNodeAt(oldVnode);
  }

  // 同一个 vnode 那么 patch 它同步到真实的 DOM 去
  if (sameVnode(oldVnode, vnode)) {
    patchVnode(oldVnode, vnode, insertedVnodeQueue);
  }
  // 不然销毁重造
  ...
  return vnode;
}

再来看下 patchVnode 的逻辑，这里的逻辑还是很简单的，所有的 patch 操作都放在了各个插件模块里面，妙啊(protocol/interface oriented) ，各个模块负责具体怎么 patch，

function patchVnode(oldVnode, vnode, insertedVnodeQueue) {
        ...
        //// vnode 都是 h 函数创建出来的，那么 vnode 的引用必然不一样，不过也不妨碍你 patch 相同的节点
        if (oldVnode === vnode)
            return;
        if (vnode.data !== undefined) {
        //// 调用各个模块实现的 update hooks 来 patch vnode 本身
            for (let i = 0; i < cbs.update.length; ++i)
                cbs.update[i](oldVnode, vnode);
        }
        //// 更新完 vnode 本身，再递归 patch vnode 的 children
        if (isUndef(vnode.text)) {
            //// 只是更新了 children 元素的话
            if (isDef(oldCh) && isDef(ch)) {
                if (oldCh !== ch)
                //// patch chilren
                    updateChildren(elm, oldCh, ch, insertedVnodeQueue);
            }
			...
       	...
    }

patch 完 Vnode 之后，我们继续 patch Vnode 的 children 如果有的话，来看下 updateChildren 方法，内部还是调用了 patchVnode，其实就是递归 patch Vnode，对于 children 的 patch 内部通过双指针夹逼的方式，

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue) {
  ...

  // 其中一个数组 patch 完即可，loop 结束后再处理需要删除和添加的 vnode
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    ...
    //// NOTE: 不用硬看，如果看不懂，问下自己，"如果在头部插了个 node, 如果直接对比的话,你会怎么处理？“
    //// 如果可以提前发现只是在头部插了个 node 的话，那么
    //// 你就可以只修改第一个 node，而保持其他 node 不变
    //// 没移动直接 patch 即可
    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];
    }
    //// 位置移动了 需要 patch and insert
    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];
    }
    //// --- end

    //// 插入或者交换位置的我们可以利用 key 来进行高效对比
    else {
      if (oldKeyToIdx === undefined) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      }
      idxInOld = oldKeyToIdx[newStartVnode.key];
      if (isUndef(idxInOld)) {
        // New element
        api.insertBefore(
          parentElm,
          createElm(newStartVnode, insertedVnodeQueue),
          oldStartVnode.elm
        );
      }
      //// 调换了位置
      //// 好说 
	  //// 凡是涉嫌位置移动的 最后到需要 insert 因为 dom 没有移动的 api
      else {
        elmToMove = oldCh[idxInOld];
        //// 调换的这两个 node tag 不相同 // 那么没办法复用 销毁重建
        if (elmToMove.sel !== newStartVnode.sel) {
          api.insertBefore(
            parentElm,
            createElm(newStartVnode, insertedVnodeQueue),
            oldStartVnode.elm
          );
        }
        //// 如果这两个 node tag 相同，那么直接 patch 属性即可
        else {
          patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
          oldCh[idxInOld] = undefined;
          api.insertBefore(parentElm, elmToMove.elm, oldStartVnode.elm);
        }
      }
      newStartVnode = newCh[++newStartIdx];
    }
  }
  //// 两端夹逼的结果
  //// 旧的 有 有 无 无
  //// 新的 无 有 有 无
  //// oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx 不成立 才到这里 所以 有有的情况需要排除 无无的情况不用做什么
  ///// 夹逼完的说明都已经 patch 和 insert 了
  //// 所以这里可以改写下我觉得 不然不好理解 顺手提了个 PR 到 github 被 merge 了
  // if(oldStartIdx <= oldEndIdx) {
  //     removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
  // }
  // if(newStartIdx <= newEndIdx) {
  //     before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;
  //     addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
  // }
  if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
    //// 新数组还没夹逼完
    //// 说明新数组在 patch 完旧的之后还有多，需要继续 insert
    //// oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx && oldStartIdx > oldEndIdx
    //// 说明 newStartIdx <= newEndIdx && oldStartIdx > oldEndIdx
    if (oldStartIdx > oldEndIdx) {
      before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;
      addVnodes(
        parentElm,
        before,
        newCh,
        newStartIdx,
        newEndIdx,
        insertedVnodeQueue
      );
    }

    //// oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx && oldStartIdx<= oldEndIdx
    else {
      //// 旧数组没夹逼完的
      //// 新数组的元素就已经 patch 和 insert 了
      //// 旧数组剩下的都是没用的了 需要移除
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
    }
  }
}

这样就 VDOM 的 patch 就完成了。

备注：学习的时候最好有实践作支撑，不然只看理论很容易忘，所以研读源码的时候，我都会写一个小 demo，用来打断点调试，方便学习，很多函数在第一次看的时候可以不用细看，我们看函数名就行了，先把整个流程串起来。

参考

1. Virtual DOM and Internals
2. citojs inferno snabbdom
3. JavaScript undefined vs void 0
4. Build your own React in 90 lines of JavaScript
5. React && VUE Virtual Dom的Diff算法统一之路 snabbdom.js解读
6. Virtual DOM is pure overhead
7. Build your own React（这里的动画也太酷了）
8. The purpose of the Virtual DOM