React系列（四）--- virtualdom diff算法实现分析

系列文章

React系列（一）-- 2013起源 OSCON - React Architecture by vjeux

React系列（二）-- React基本语法实现思路

React系列（三）-- Jsx, 合成事件与Refs

React系列（四）--- virtualdom diff算法实现分析

React系列（五）--- 从Mixin到HOC

React系列（六）--- 从HOC再到HOOKS

渲染DOM

经历过PHP模板开发或者JQuery的洗礼的人都知道,它们实现重新渲染采用最简单粗暴的办法就是重新构建DOM替换旧DOM,问题也很明显

• 性能消耗高
• 无法保存状态(聚焦,滚动等)

我们先看看创建一个元素所包含的实例属性有多少个

const div = document.createElement('div');
let num = 0;
let str = ''
for (let key in div) {
  num++;
  str += key + ', '
}

console.log(num); // 299
console.log(str); 

align, title, lang, translate, dir, hidden, accessKey, draggable, spellcheck, autocapitalize, contentEditable, isContentEditable, inputMode, offsetParent, offsetTop, offsetLeft, offsetWidth, offsetHeight, style, innerText, outerText, onbeforexrselect, onabort, onblur, oncancel, oncanplay, oncanplaythrough, onchange, onclick, onclose, oncontextmenu, oncuechange, ondblclick, ondrag, ondragend, ondragenter, ondragleave, ondragover, ondragstart, ondrop, ondurationchange, onemptied, onended, onerror, onfocus, onformdata, oninput, oninvalid, onkeydown, onkeypress, onkeyup, onload, onloadeddata, onloadedmetadata, onloadstart, onmousedown, onmouseenter, onmouseleave, onmousemove, onmouseout, onmouseover, onmouseup, onmousewheel, onpause, onplay, onplaying, onprogress, onratechange, onreset, onresize, onscroll, onseeked, onseeking, onselect, onstalled, onsubmit, onsuspend, ontimeupdate, ontoggle, onvolumechange, onwaiting, onwebkitanimationend, onwebkitanimationiteration, onwebkitanimationstart, onwebkittransitionend, onwheel, onauxclick, ongotpointercapture, onlostpointercapture, onpointerdown, onpointermove, onpointerup, onpointercancel, onpointerover, onpointerout, onpointerenter, onpointerleave, onselectstart, onselectionchange, onanimationend, onanimationiteration, onanimationstart, ontransitionrun, ontransitionstart, ontransitionend, ontransitioncancel, oncopy, oncut, onpaste, dataset, nonce, autofocus, tabIndex, attachInternals, blur, click, focus, enterKeyHint, virtualKeyboardPolicy, onpointerrawupdate, namespaceURI, prefix, localName, tagName, id, className, classList, slot, attributes, shadowRoot, part, assignedSlot, innerHTML, outerHTML, scrollTop, scrollLeft, scrollWidth, scrollHeight, clientTop, clientLeft, clientWidth, clientHeight, attributeStyleMap, onbeforecopy, onbeforecut, onbeforepaste, onsearch, elementTiming, onfullscreenchange, onfullscreenerror, onwebkitfullscreenchange, onwebkitfullscreenerror, children, firstElementChild, lastElementChild, childElementCount, previousElementSibling, nextElementSibling, after, animate, append, attachShadow, before, closest, computedStyleMap, getAttribute, getAttributeNS, getAttributeNames, getAttributeNode, getAttributeNodeNS, getBoundingClientRect, getClientRects, getElementsByClassName, getElementsByTagName, getElementsByTagNameNS, getInnerHTML, hasAttribute, hasAttributeNS, hasAttributes, hasPointerCapture, insertAdjacentElement, insertAdjacentHTML, insertAdjacentText, matches, prepend, querySelector, querySelectorAll, releasePointerCapture, remove, removeAttribute, removeAttributeNS, removeAttributeNode, replaceChildren, replaceWith, requestFullscreen, requestPointerLock, scroll, scrollBy, scrollIntoView, scrollIntoViewIfNeeded, scrollTo, setAttribute, setAttributeNS, setAttributeNode, setAttributeNodeNS, setPointerCapture, toggleAttribute, webkitMatchesSelector, webkitRequestFullScreen, webkitRequestFullscreen, ariaAtomic, ariaAutoComplete, ariaBusy, ariaChecked, ariaColCount, ariaColIndex, ariaColSpan, ariaCurrent, ariaDescription, ariaDisabled, ariaExpanded, ariaHasPopup, ariaHidden, ariaKeyShortcuts, ariaLabel, ariaLevel, ariaLive, ariaModal, ariaMultiLine, ariaMultiSelectable, ariaOrientation, ariaPlaceholder, ariaPosInSet, ariaPressed, ariaReadOnly, ariaRelevant, ariaRequired, ariaRoleDescription, ariaRowCount, ariaRowIndex, ariaRowSpan, ariaSelected, ariaSetSize, ariaSort, ariaValueMax, ariaValueMin, ariaValueNow, ariaValueText, getAnimations, nodeType, nodeName, baseURI, isConnected, ownerDocument, parentNode, parentElement, childNodes, firstChild, lastChild, previousSibling, nextSibling, nodeValue, textContent, ELEMENT_NODE, ATTRIBUTE_NODE, TEXT_NODE, CDATA_SECTION_NODE, ENTITY_REFERENCE_NODE, ENTITY_NODE, PROCESSING_INSTRUCTION_NODE, COMMENT_NODE, DOCUMENT_NODE, DOCUMENT_TYPE_NODE, DOCUMENT_FRAGMENT_NODE, NOTATION_NODE, DOCUMENT_POSITION_DISCONNECTED, DOCUMENT_POSITION_PRECEDING, DOCUMENT_POSITION_FOLLOWING, DOCUMENT_POSITION_CONTAINS, DOCUMENT_POSITION_CONTAINED_BY, DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC, appendChild, cloneNode, compareDocumentPosition, contains, getRootNode, hasChildNodes, insertBefore, isDefaultNamespace, isEqualNode, isSameNode, lookupNamespaceURI, lookupPrefix, normalize, removeChild, replaceChild, addEventListener, dispatchEvent, removeEventListener,

然后浏览器根据CSS规则查找匹配节点,计算合并样式布局,为了避免重新计算一般浏览器会保存这些数据.但这是整个过程下来依然会耗费大量的内存和 CPU 资源.

Virtual DOM

实际也是操作Dom树进行渲染更新,但是它只是针对修改部分进行局部渲染,将影响降到最低,虽然实现方式各有不同,但是大体步骤如下:

1. 用Javascript对象结构描述Dom树结构,然后用它来构建真正的Dom树插入文档
2. 当状态发生改变之后,重新构造新的Javascript对象结构和旧的作对比得出差异
3. 针对差异之处进行重新构建更新视图

无非就是利用Js做一层映射比较,操作简单并且速度远远高于直接比较Dom树

基础工具函数

无非就是一些类型判断的简化函数

util.js

// 检验类型
function typeIs(type, data) {
  type = type.charAt(0).toUpperCase() + type.slice(1)
  return Object.prototype.toString.call(data) === `[object ${type}]`
}

// 多类型判断
function isType(type, data) {
  if (typeIs('String', type)) return typeIs(type, data)
  if (typeIs('Array', type)) return type.some(key => typeIs(key, data))
  console.error(
    `params type must be a String or Array but receive a ${typeof type}`
  )
  return false
}

// 非空对象
function isNotEmptyObj(obj) {
  return isType('object', obj) && JSON.stringify(obj) != "{}";
}

// 设置属性
function setAttr(node, key, value) {
  switch (key) {
    case "style":
      node.style.cssText = value;
      break;
    case "value":
      var tagName = node.tagName || "";
      tagName = tagName.toLowerCase();
      if (tagName === "input" || tagName === "textarea") {
        node.value = value;
      } else {
        // if it is not a input or textarea, use `setAttribute` to set
        node.setAttribute(key, value);
      }
      break;
    default:
      node.setAttribute(key, value);
      break;
  }
}

export {
  typeIs,
  isType,
  isNotEmptyObj,
  setAttr
};

CreateElement实现

我之前讲JSX的时候举过这么个例子,然后我们就以这个来实现效果吧

<div className="num" index={1}>
  <span>123456</span>
</div>

"use strict";

React.createElement("div", {
  className: "num",
  index: 1
}, React.createElement("span", null, "123456"));

基本定义

我们从上文可以确定入参跟调用方式，所以可以得出这个函数的基本形态

element.js

class Element {
  constructor(tagName, props, children) {
  }

  render() {
  }
}

// 改变传参方式,免去手动实例化
export default function CreateElement(tagName, props, children) {
  return new Element(tagName, props, children);
}

参数处理

从文档定义可以知道调用的几种可能性

$$ React.createElement( type, [props], [...children] ) $$

constructor(tagName, props, children) {
  // 解析参数
  this.tagName = tagName;
  // 字段处理,可省略参数
  this.props = isType('object', props) ? props : {};

  /* 
    三种情况：
    1，有children入参
    2，this.props有入参，字符串则为文本节点，数组则是children
    3，空
  */
  children = children || (!isNotEmptyObj(this.props) && ((isType('string', props) && [props]) || (isType('array', props) && props))) || []
  // 其他类型默认转成文本
  children.map(item => {
    if (item instanceof Element || isType('string', item)) {
      return item
    } else {
      return '' + item
    }
  })
  this.children = children;
  // 运算符计算给定的表达式并返回undefined
  // key就是大家所知的排序用
  this.key = props ? props.key : void NOKEY;
}

到了这一步我们就算明确了具体参数了

渲染结构

这步比较简单，只要分成几步：

1. 创建标签
2. 属性赋值
3. 递归渲染子元素，重复执行这三步直到完成所有元素
4. 返回最终完整dom树

render() {
  // 根据tagName构建
  const dom = document.createElement(this.tagName);

  // 设置props
  objForEach(this.props, propName =>
    dom.setAttribute(propName, this.props[propName])
  );

  // 渲染children
  this.children.forEach(child => {
    const childDom =
      child instanceof Element
        ? child.render() // 如果子节点也是虚拟DOM，递归构建DOM节点
        : document.createTextNode(child); // 如果字符串，只构建文本节点
    dom.appendChild(childDom);
  });
  return dom;
}

调用

新建示例,调用方式如下

index.js

// 1. 构建虚拟DOM
const tree = createElement("div", { id: "root" }, [
  createElement("h1", { style: "color: blue" }, ["Tittle1"]),
  createElement("p", ["Hello, virtual-dom"]),
  createElement("ul", [
    createElement("li", { key: 1 }, ["li1"]),
    createElement("li", { key: 2 }, ["li2"]),
    createElement("li", { key: 3 }, ["li3"]),
    createElement("li", { key: 4 }, ["li4"])
  ])
]);

// 2. 通过虚拟DOM构建真正的DOM
const root = tree.render();
document.body.appendChild(root);

运行之后能正常得出结果了,那么第一步骤算是完成了,具体还有更多不同类型标签,对应事件状态先略过.

界面如图

Javascript结构如图

结构原型如下

假设DOM改变

我们创建新的Dom树作对比

// 3. 生成新的虚拟DOM
const newTree = createElement("div", { id: "container" }, [
  createElement("h1", { style: "color: red" }, ["Title2"]),
  createElement("h3", ["Hello, virtual-dom"]),
  createElement("ul", [
    createElement("li", { key: 3 }, ["li3"]),
    createElement("li", { key: 1 }, ["li1"]),
    createElement("li", { key: 2 }, ["li2"]),
    createElement("li", { key: 5 }, ["li5"])
  ])
]);

Javascript结构如图

diff算法

这是整个实现里面最关键的一步,因为这决定了计算的速度和操作Dom的数量

React将Virtual DOM转换成actual DOM树的最少操作过程成为调和（reconciliation）

diff 策略

React diff算法主要分三个策略

1. WEB UI中DOM节点跨层级移动操作少可以忽略不计
2. 相同类的组件会生成相似的结构，不同类的组件生成不同的结构
3. 同一层级的一组子节点可以通过唯一id区分

基于以上几点，React分别对tree diff，component diff以及element diff进行算法优化

tree diff

传统 diff 算法的复杂度为 O(n^3)，但是一般Dom跨层级的情况是非常少见的。所以React 只针对同层级Dom节点做比较，将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题。

比较大的问题就是当节点跨层级移动并不会进行移动而是直接替换整个节点,所以切记这点性能问题

component diff

• 同一类型组件会进行Virtual DOM进行比较
• 如果不是相同类型的组件发生变化,会导致自其从上往下整体替换
• React提供了一个shouldComponentUpdate决定是否更新

尽可能将动态组件往底层节点迁移,有利于提高性能

element diff

元素操作无非就是几种,我们定义几个类型做状态标记

type.js

const REPLACE = "replace";
const REORDER = "reorder";
const PROPS = "props";
const TEXT = "text";
const NOKEY = "no_key"

export {
  REPLACE,
  REORDER,
  PROPS,
  TEXT,
  NOKEY
}

其中NOKEY就是专门给那些没有定义key的组件做默认,React对同一层级的同组子节点，添加唯一key 进行区分进行位移而不是直接替换,这点对于整体性能尤为关键

diff 实现

我们首先可以确定的是需要的入参一般用到新树，旧树，节点位置，得出一份偏差结果数据

diff.js

/**
 * diff 算法
 * @param {旧Dom树} oTree
 * @param {新Dom树} nTree
 * 返回差异记录
 */
function diff(oTree, nTree) {
  // 节点位置
  let index = 0;
  // 差异记录
  const patches = {};
  // 算法
  dfsWalk(oTree, nTree, index, patches);
  return patches;
}

export default diff;

我们其实dfsWalk代表我们使用的搜索算法

搜索算法

深度优先遍历(DFS)：沿着分支一直搜索，直到尽头再回溯到上一个分支节点搜索同层级分支

广度优先遍历(BFS)：优先同层级节点搜索，直到所有节点均完成才终止

随机游走(Random Walk)：从当前节点随机选择一个相邻节点，核心概念是指任何无规则行走者所带的守恒量都各自对应着一个扩散运输定律。

dfsWalk

根据我们之前的论点我们可以得出几种需要考虑的操作情况：

1. 替换节点
2. 新增节点
3. 移除节点
4. 重排节点

节点情况：

1. 文本节点
2. 带唯一值的同层级同类型节点
3. 子节点
4. 无节点

结合上面的类型可以得出他们关系

第一步简单的文本对比，其他先完整替换，数据结构用操作类型type和节点content记录下来

/**
 * 
 * @param {*} oNode 旧节点
 * @param {*} nNode 新节点
 * @param {*} index 节点索引
 * @param {*} patches 差异记录
 * @returns 
 */
function dfsWalk(oNode, nNode, index, patches) {
  // 本次的差异记录
  const currentPatch = [];

  // 首次渲染的时候
  if (nNode === null) return;

  // 如果是文本节点并且不相同直接替换
  if (isType('string', oNode) && isType('string', nNode)) {
    oNode !== nNode &&
      currentPatch.push({
        type: TEXT,
        content: nNode
      });
  } else {
    // 都不符合上面情况就直接新增
    currentPatch.push({ type: REPLACE, node: nNode });
  }

  // 最终对比结果
  currentPatch.length && (patches[index] = currentPatch);
}

很明显我们还差具体的节点对比实现，而具体对比的前提条件有以下几种：

• 相同标签
• 相同key（包括都没有key的情况）

如果满足前提的话，可能发生变化的情况有：

• props
• children

我们先假定两个函数功能已实现的方法先完成这部分逻辑

diffProps：对比属性

diffChildren：对比子元素

if (oNode && nNode && oNode.tagName === nNode.tagName && oNode.key === nNode.key) { // 同种标签并且key相同
    // 至少一方有值
    if (isNotEmptyObj(oNode.props) || isNotEmptyObj(nNode.props)) {
      // 计算props结果,返回差异记录
      const propsPatches = diffProps(oNode.props, nNode.props);
      propsPatches && currentPatch.push({
        type: PROPS,
        props: propsPatches
      });
    }
    if (oNode.children.length || nNode.children.length) {
      // 计算children结果,返回差异记录
      const childrenPatches = diffChildren(oNode.children, nNode.children, index, patches, currentPatch);
      childrenPatches && currentPatch.push({
        type: PROPS,
        children: childrenPatches
      });
    }
}

对比属性

新旧节点的props属性比较

/**
 * 对比节点props
 * @param {旧节点} oNode
 * @param {新节点} nNode
 */
function diffProps(oProps, nProps) {
  if (!oProps && !nProps) return null

  let isChange = false;
  // 节点属性记录
  const propsPatched = {};
  // 过滤相同属性
  const oKey = Object.keys(oProps)
  const nKey = Object.keys(nProps)
  const keyAry = [...new Set(oKey.concat(nKey))]

  // 替换/新增属性
  keyAry.forEach(key => {
    // 记录是否变化
    if (nProps[key] !== oProps[key]) !isChange && (isChange = true);
    propsPatched[key] = nProps[key] || oProps[key];
  });

  return !isChange ? null : propsPatched;
}

list-diff 最小移动算法

因为我们都知道子元素肯定是数组形式，所以我们需要进行的实际是两个数组之间的差异，考虑到我们存在相同列表元素的位移情况，所以我们最终得到的应该是最少实现修改步骤，这里我们先使用第三方库实现

Diff two lists in time O(n). I The algorithm finding the minimal amount of moves is Levenshtein distance which is O(n*m). This algorithm is not the best but is enougth for front-end DOM list manipulation.

This project is mostly influenced by virtual-dom algorithm.

var diff = require("list-diff2")
var oldList = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}]
var newList = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}]

var moves = diff(oldList, newList, "id")
// `moves` is a sequence of actions (remove or insert): 
// type 0 is removing, type 1 is inserting
// moves: [
//   {index: 3, type: 0},
//   {index: 0, type: 1, item: {id: "c"}}, 
//   {index: 3, type: 0}, 
//   {index: 4, type: 1, item: {id: "f"}}
//  ]

moves.moves.forEach(function(move) {
  if (move.type === 0) {
    oldList.splice(move.index, 1) // type 0 is removing
  } else {
    oldList.splice(move.index, 0, move.item) // type 1 is inserting
  }
})

// now `oldList` is equal to `newList`
// [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}]
console.log(oldList) 

对比子元素

新旧节点的子元素对比

/**
 * 同级对比
 * @param {*} oChildren 旧子数组
 * @param {*} nChildren 新子数组
 * @param {*} index 父count索引
 * @param {*} patches 差异记录
 * @param {*} currentPatch 当前层级差异记录
 */
function diffChildren(oChildren, nChildren, index, patches, currentPatch) {
  if (!oChildren.length && !nChildren.length) return

  // 得出相对简化移动路径
  const diffs = listDiff(oChildren, nChildren, "key");
  // 记录排序位移
  diffs.moves.length && currentPatch.push({ type: REORDER, moves: diffs.moves });
  // 改变之后依然保留的元素
  const keepChildren = diffs.children;
}

这里还少了很重要的一步，因为children里面可能嵌套了多层children，所以我们还需要使用递归方法继续比对，考虑到上面的说深度优先遍历(DFS), 我们看一下

深度遍历的原型图如下我们需要有一个索引值来确认搜索顺序，所以回到创建元素对象函数需要加一个逻辑

class Element {
  constructor(tagName, props, children) {
    // -----省略-----
    
    // 该实例子节点总数
    let count = 0;
    if (isType('array', this.children)) {
      this.children.forEach((item) => {
        // 即节点下的children包含在内，需要累计
        if (item instanceof Element) {
          count += item.count;
        }
        count++;
      });
    }
    this.count = count;
  }
}

从下图可以知道一些关键信息

当前元素的count等于所有子节点数量，所以可以从这知道下一同级节点的顺序，结合上面的深度搜索图形，我们可以得出搜索节点顺序

/**
 * 同级对比
 * @param {*} oChildren 旧子数组
 * @param {*} nChildren 新子数组
 * @param {*} index 父count索引
 * @param {*} patches 差异记录
 * @param {*} currentPatch 当前层级差异记录
 */
function diffChildren(oChildren, nChildren, index, patches, currentPatch) {
  if (!oChildren.length && !nChildren.length) return

  // 得出相对简化移动路径
  const diffs = listDiff(oChildren, nChildren, "key");
  // 记录排序位移
  diffs.moves.length && currentPatch.push({ type: REORDER, moves: diffs.moves });
  // 改变之后依然保留的元素
  const keepChildren = diffs.children;

  // 同层级节点遍历
  let leftNode = null;
  // 当前节点所在顺序
  let curNodeIndex = index;
  // 只对比保留的元素
  oChildren.forEach((item, idx) => {
    const keepChild = keepChildren[idx];
    // 找出下一对比节点顺序
    curNodeIndex = leftNode?.count
      // 当前所在顺序=上一节点顺序+上一节点子元素数量+1
      ? curNodeIndex + leftNode.count + 1
      : curNodeIndex + 1;
    // 保留元素中发生变化的需要继续对比子元素，这一步是实现深度优先遍历的关键
    item !== keepChild && dfsWalk(item, keepChild, curNodeIndex, patches);
    // 下一对比节点
    leftNode = item;
  });
}

差异结果

// 4. 比较两棵虚拟DOM树的不同
const patches = diff(tree, newTree);

得出差异如下

更新视图

知道差异之后接下来的视图更新就比较简单了，首先按记录顺序逐步渲染替换

patch

/**
 * 渲染差异
 * @param {*} node 根节点
 * @param {*} patches 差异记录
 */
function patch(node, patches) {
  const walker = { index: 0 };
  dfsWalk(node, walker, patches);
}

// 深度遍历更新
function dfsWalk(node, walker, patches) {
  // 当前操作层级步骤
  const currentPatches = patches[walker.index];

  // 渲染子节点
  node.childNodes && node.childNodes.forEach(item => {
    walker.index++;
    dfsWalk(item, walker, patches);
  });

  // 开始渲染
  currentPatches && applyPatches(node, currentPatches);
}

export default patch;

applyPatches

针对之前那不同标志做对应处理

/**
 * 应用渲染
 * @param {*} node 渲染节点
 * @param {*} currentPatches 当前差异记录
 */
function applyPatches(node, currentPatches) {
  currentPatches.forEach(item => {
    if (item.type === REPLACE) return replaceComponent(node, item)
    if (item.type === PROPS) return setProps(node, item.props)
    if (item.type === TEXT) return replaceText(node)
    if (item.type === REORDER) return reorderChildren(node, item.moves)
    throw new Error("Unknown patch type " + item.type);
  });
}

replaceComponent

/**
 * 替换组件
 * @param {*} node 旧节点
 * @param {*} item 新节点
 */
function replaceComponent(node, item) {
  // 区分是元素还是文本替换
  const nNode = isType('string', item.node)
    ? document.createTextNode(item.node)
    : item.node.render();
  // 进行元素替换
  node.parentNode.replaceChild(nNode, node);
}

setProps

/**
 * 修改属性
 * @param {*} node 修改节点
 * @param {*} props 修改属性
 */
function setProps(node, props) {
  const ksys = Object.keys(props)
  ksys.forEach(key => {
    if (props[key] === void NOKEY) {
      node.removeAttribute(key);
    } else {
      setAttr(node, key, props[key]);
    }
  });
}

replaceText

/**
 * 替换文本
 * @param {*} node 替换节点
 */
function replaceText(node) {
  if (node.textContent) {
    // 使用纯文本
    node.textContent = item.content;
  } else {
    // 仅仅对CDATA片段，注释comment，Processing Instruction节点或text节点有效
    node.nodeValue = item.content;
  }
}

reorderChildren

其中重排过程大概如下

例如

1,2,3,4 -》 3,1,2,5

需要进行四步

一，索引值3位移除4：1,2,3二，索引值0位插入3：3,1,2,3三，索引值3位插入5：3,1,2,5,3四，索引值4位移除3：3,1,2,5

/**
 * 列表重排
 * @param {*} node 列表父节点
 * @param {*} moves 差异步骤
 */
function reorderChildren(node, moves) {
  // 拷贝数组
  const staticNodeList = Array.from(node.childNodes).slice(0);

  // 记录携带key的组件
  const maps = {};
  staticNodeList.forEach(node => {
    // Element
    if (node.nodeType === 1) {
      const key = node.getAttribute("key");
      key && (maps[key] = node);
    }
  });

  // 执行差异记录步骤
  moves.forEach(move => {
    const index = move.index;
    const child = node.childNodes[index]

    // 0:删除 1:替换
    if (move.type === 0) {
      // 找到对应节点删除
      staticNodeList[index] === child && node.removeChild(child);
      // 移除拷贝数据
      staticNodeList.splice(index, 1);
    } else if (move.type === 1) {
      let insertNode;
      const keyData = maps[move.item.key]
      if (keyData) {
        // 拷贝替换节点,不直接使用是因为可能后面需要操作
        insertNode = keyData.cloneNode(true)
      } else {
        // 不携带key都是重新渲染，创建节点/文本
        insertNode = isType('object', move.item)
          ? move.item.render()
          : document.createTextNode(move.item);
      }

      // 同步staticNodeList信息
      staticNodeList.splice(index, 0, insertNode);
      // 操作Dom
      node.insertBefore(insertNode, child || null);
    }
  });
}

运行完整流程

import createElement from "./element.js";
import diff from "./diff.js";
import patch from "./patch.js";

// 1. 构建虚拟DOM
const tree = createElement("div", { id: "root" }, [
  createElement("h1", { style: "color: blue" }, ["Tittle1"]),
  createElement("p", ["Hello, virtual-dom"]),
  createElement("ul", [
    createElement("li", { key: 1 }, ["li1"]),
    createElement("li", { key: 2 }, ["li2"]),
    createElement("li", { key: 3 }, ["li3"]),
    createElement("li", { key: 4 }, ["li4"])
  ])
]);

// 2. 通过虚拟DOM构建真正的DOM
const root = tree.render();
document.body.appendChild(root);

// 3. 生成新的虚拟DOM
const newTree = createElement("div", { id: "container" }, [
  createElement("h1", { style: "color: red" }, ["Title2"]),
  createElement("h3", ["Hello, virtual-dom"]),
  createElement("ul", [
    createElement("li", { key: 3 }, ["li3"]),
    createElement("li", { key: 1 }, ["li1"]),
    createElement("li", { key: 2 }, ["li2"]),
    createElement("li", { key: 5 }, ["li5"])
  ])
]);

// 4. 比较两棵虚拟DOM树的不同
const patches = diff(tree, newTree);
setTimeout(() => {
  patch(root, patches);
}, 6000);

结果如图

参考

深度剖析：如何实现一个 Virtual DOM 算法

《深入React技术栈》