关于javascript:React系列四-virtualdom-diff算法实现分析

渲染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技术栈》