基本认识

什么是 DOM Diff ?
就是对比两个虚拟节点（新虚拟节点和旧虚拟节点），然后找出差异，形成一个补丁 patch 对象，然后根据 patch 对象去把真实的 DOM 进行匹配，所以最终还是要操作 DOM。但是这么做的目的是为了用最小的代价去操作 DOM，毕竟只要操作 DOM 就会产生一定的性能。

什么是虚拟节点呢？
简单理解就是一个普通的对象，把真实的节点通过对象的方式进行描述。
例如：

  1. const vDom = {
  2.   tag: 'span',
  3.   attrs: {},
  4.   children: "123"
  5. }

无论是 Vue 的template模版还是 React 的JSX，最终都会转换为虚拟节点，当更改数据的时候就会产生新的虚拟节点，然后就会进行对比，产生一个补丁，最后根据补丁去更新真实的 DOM。

例如我们有这么一段 HTML 内容，我们想要进行一些内容的更改：
Xnip2023-05-25_09-59-56.jpg
然后 DOM Diff 就会根据一定的算法规则进行对比，规则如下：
1、只会一级一级的去对比，不会进行跨级对比。
Xnip2023-05-25_10-03-47.jpg
也就是说，先对比第一层的ul，再对比第二层的li，但是上图中li属性data-id="1"就不会进行对比，因为它们不是一个层级。
如果是下面的结构，就可以逐一的进行对比：
Xnip2023-05-25_10-05-45.jpg

2、对比时会按照生成虚拟节点时候的标识（索引）进行对比。
Xnip2023-05-25_14-16-41.jpg

3、当 DOM 的位置发生变化时，是可以进行替换的，不需要重新渲染li节点
Xnip2023-05-25_10-08-00.jpg

4、Diff 是深度遍历的
遍历的时候会先遍历ul，然后遍历左侧第一列的li以及li的子级，然后再遍历中间列的li以及li的子级…整个过程是从上往下深度遍历的，而不是从左到右广度遍历。
Xnip2023-05-25_10-11-02.jpg

模拟一个 h 函数

例如我们想要用自己写的函数来创建一段这样的虚拟节点对象：
Xnip2023-05-25_10-11-02.jpg

  1. import { createElement } from "./virtualDom";
  3. const vDom = createElement(
  4.   "ul",
  5.   {
  6.     class: "list",
  7.     style: "width: 300px; height: 300px; background-color: orange"
  8.   },
  9.   [
  10.     createElement("li", { class: "item", "data-index": 0 }, [
  11.       createElement("p", { class: "text" }, ["第1个列表项"])
  12.     ]),
  13.     createElement("li", { class: "item", "data-index": 1 }, [
  14.       createElement("p", { class: "text" }, [
  15.         createElement("span", { class: "title" }, ["第2个列表项"])
  16.       ])
  17.     ]),
  18.     createElement("li", { class: "item", "data-index": 2 }, ["第3个列表项"])
  19.   ]
  20. );
  22. console.log(vDom);

可以看到上面这段代码使用createElement()函数来创建一个虚拟节点，那么首先肯定是要去实现这个createElement()函数：

1、我们新建一个virtualDom.js文件，该文件内只负责虚拟 DOM 相关的事情。

  1. import Element from "./Element";
  3. function createElement(type, props, children) {
  4.   // 实例化一个元素对象
  5.   return new Element(type, props, children);
  6. }
  8. export { createElement };
  1. class Element {
  2.   constructor(type, props, children) {
  3.     this.type = type;
  4.     this.props = props;
  5.     this.children = children;
  6.   }
  7. }
  9. export default Element;

这样结果如下：
image.png
这样就实现了一个虚拟节点树啦。

2、拿到虚拟节点树以后，我们写一个render()函数去把我们刚才生成的虚拟节点渲染为一个真实的 DOM：

  1. import { createElement, render } from "./virtualDom";
  3. const vDom = createElement(
  4.   "ul",
  5.   {
  6.     class: "list",
  7.     style: "width: 300px; height: 300px; background-color: orange"
  8.   },
  9.   [
  10.     createElement("li", { class: "item", "data-index": 0 }, [
  11.       createElement("p", { class: "text" }, ["第1个列表项"])
  12.     ]),
  13.     createElement("li", { class: "item", "data-index": 1 }, [
  14.       createElement("p", { class: "text" }, [
  15.         createElement("span", { class: "title" }, ["第2个列表项"])
  16.       ])
  17.     ]),
  18.     createElement("li", { class: "item", "data-index": 2 }, ["第3个列表项"])
  19.   ]
  20. );
  22. const rDom = render(vDom);
  23. console.log(rDom);
  1. import Element from "./Element";
  3. function setAtrrs(node, prop, value) {
  4.   // 单独封装这个函数是因为某些运输的值需要特殊的处理，例如：
  5.   // <input type="text" />
  6.   // input 的 value 属性不能通过 setAttribute() 方法去设置，而是 input.value 去设置
  7.   switch (prop) {
  8.     case "value":
  9.       // 如果节点是 <input /> 或者 <textarea></textarea>
  10.       if (node.tagName === "INPUT" || node.tagName === "TEXTAREA") {
  11.         node.value = value;
  12.       } else {
  13.         node.setAttribute(prop, value);
  14.       }
  15.       break;
  16.     case "style":
  17.       node.style.cssText = value;
  18.       break;
  19.     default:
  20.       node.setAttribute(prop, value);
  21.       break;
  22.   }
  23. }
  25. // 创建元素对象
  26. function createElement(type, props, children) {
  27.   return new Element(type, props, children);
  28. }
  30. // 渲染函数
  31. function render(vDom) {
  32.   // 因为每一个节点对象上有这 3 个属性，我们可以进行解构
  33.   const { type, props, children } = vDom;
  35.   // 然后根据对应的类型去创建 DOM
  36.   const el = document.createElement(type);
  38.   // 遍历 prop 对象，单独去设置元素的属性，因为某些属性比较特殊
  39.   for (const key in props) {
  40.     setAttrs(el, key, props[key]);
  41.   }
  43.   // 处理完当前元素，我们就要去处理子元素
  44.   // 例如 { type: "ul", children: [{ type: "li"}, { type: "li"}]}
  45.   children.map((c) => {
  46.     // 判断子元素是不是 Element 构造函数的实例对象
  47.     // 如果是就把子元素进行递归处理，否则就创建一个普通的文本节点
  48.     c = c instanceof Element ? render(c) : document.createTextNode(c);、
  49.     // 最后添加到父元素上
  50.     el.appendChild(c);
  51.   });
  53.   return el;
  54. }
  56. // 我们还需要把 setAttrs 也导出，因为后面会用到
  57. export { createElement, render, setAttrs };

当把vDom传递给render()执行后，我们就能得到真正的 DOM 节点了。
image.png

3、最后我们把这个节点渲染到页面上就行了。同样的，我需要把它交给一个函数去处理。

  1. import { createElement, render, renderDOM } from "./virtualDom";
  3. const vDom = createElement(
  4.   "ul",
  5.   {
  6.     class: "list",
  7.     style: "width: 300px; height: 300px; background-color: orange"
  8.   },
  9.   [
  10.     createElement("li", { class: "item", "data-index": 0 }, [
  11.       createElement("p", { class: "text" }, ["第1个列表项"])
  12.     ]),
  13.     createElement("li", { class: "item", "data-index": 1 }, [
  14.       createElement("p", { class: "text" }, [
  15.         createElement("span", { class: "title" }, ["第2个列表项"])
  16.       ])
  17.     ]),
  18.     createElement("li", { class: "item", "data-index": 2 }, ["第3个列表项"])
  19.   ]
  20. );
  22. const rDom = render(vDom);
  23. renderDOM(rDom, document.getElementById("app"));
  1. import Element from "./Element";
  3. // 设置属性
  4. function setAtrrs(node, prop, value) {
  5.   switch (prop) {
  6.     case "value":
  7.       if (node.tagName === "INPUT" || node.tagName === "TEXTAREA") {
  8.         node.value = value;
  9.       } else {
  10.         node.setAttribute(prop, value);
  11.       }
  12.       break;
  13.     case "style":
  14.       node.style.cssText = value;
  15.       break;
  16.     default:
  17.       node.setAttribute(prop, value);
  18.       break;
  19.   }
  20. }
  22. // 创建元素对象
  23. function createElement(type, props, children) {
  24.   return new Element(type, props, children);
  25. }
  27. // 渲染虚拟节点
  28. function render(vDom) {
  29.   const { type, props, children } = vDom;
  31.   const el = document.createElement(type);
  33.   for (const key in props) {
  34.     setAtrrs(el, key, props[key]);
  35.   }
  37.   children.map((c) => {
  38.     c = c instanceof Element ? render(c) : document.createTextNode(c);
  39.     el.appendChild(c);
  40.   });
  42.   return el;
  43. }
  45. // 渲染真实 DOM
  46. function renderDOM(rDom, rootEL) {
  47.   rootEL.appendChild(rDom);
  48. }
  50. export { createElement, render, renderDOM, setAtrrs };

renderDOM()函数内部很简单，就是把渲染完成后的真实 DOM 直接挂载到一个根元素上就可以了。

这样我们就完成了对一个虚拟节点的解析渲染了。
image.png

模拟一个 diff 函数

假如我现在要对以上的 DOM 进行更改，更改内容如下：
image.png
根据图片上的内容，可以得出更改的内容：
1、序号为 0 的ul的class属性变更为 list-warp
2、序号为 2 的p的class属性变更为 title
3、序号为 3 的文本内容变更为“特殊列表项”
4、序号为 6 的span元素进行了删除
5、序号为 7 的li元素类型变更为div元素

综上，我们可以把这些变更的内容，通过对象来记录下：

  1. const patches = {
  2.   0: [
  3.     {
  4.       type: "ATTR",
  5.       attrs: {
  6.         class: "list-wrap"
  7.       }
  8.     }
  9.   ],
  10.   2: [
  11.     {
  12.       type: "ATTR",
  13.       attrs: {
  14.         class: "title"
  15.       }
  16.     }
  17.   ],
  18.   3: [
  19.     {
  20.       type: "TEXT",
  21.       text: "特殊列表项"
  22.     }
  23.   ],
  24.   6: [
  25.     {
  26.       type: "REMOVE",
  27.       index: 6
  28.     }
  29.   ],
  30.   7: [
  31.     {
  32.       type: "REPLACE",
  33.       newNode: {}
  34.     }
  35.   ]
  36. };

因为一个元素的变更不可能为 1 个，所以我们把每个元素的变更保持为一个数组的方式。

下面是代码的变更操作：

  1. const vDom1 = createElement(
  2.   "ul",
  3.   {
  4.     class: "list",
  5.     style: "width: 300px; height: 300px; background-color: orange"
  6.   },
  7.   [
  8.     createElement("li", { class: "item", "data-index": 0 }, [
  9.       createElement("p", { class: "text" }, ["第1个列表项"])
  10.     ]),
  11.     createElement("li", { class: "item", "data-index": 1 }, [
  12.       createElement("p", { class: "text" }, [
  13.         createElement("span", { class: "title" }, ["第2个列表项"])
  14.       ])
  15.     ]),
  16.     createElement("li", { class: "item", "data-index": 2 }, ["第3个列表项"])
  17.   ]
  18. );
  20. const vDom2 = createElement(
  21.   "ul",
  22.   {
  23.     class: "list-wrap",
  24.     style: "width: 300px; height: 300px; background-color: orange"
  25.   },
  26.   [
  27.     createElement("li", { class: "item", "data-index": 0 }, [
  28.       createElement("p", { class: "title" }, ["特殊列表项"])
  29.     ]),
  30.     createElement("li", { class: "item", "data-index": 1 }, [
  31.       createElement("p", { class: "text" }, [
  32.         // span 进行了删除
  33.       ])
  34.     ]),
  35.     createElement("div", { class: "item", "data-index": 2 }, ["第3个列表项"])
  36.   ]
  37. );

1、下面我们想开始对vDom1和vDom2进行对比
我们通过一个叫做domDiff()的方法去进行对比，拿到结果。

  1. import { createElement, render, renderDOM } from "./virtualDom";
  2. import { domDiff } from "./domDiff";
  4. const vDom1 = createElement(
  5.   "ul",
  6.   {
  7.     class: "list",
  8.     style: "width: 300px; height: 300px; background-color: orange"
  9.   },
  10.   [
  11.     createElement("li", { class: "item", "data-index": 0 }, [
  12.       createElement("p", { class: "text" }, ["第1个列表项"])
  13.     ]),
  14.     createElement("li", { class: "item", "data-index": 1 }, [
  15.       createElement("p", { class: "text" }, [
  16.         createElement("span", { class: "title" }, ["第2个列表项"])
  17.       ])
  18.     ]),
  19.     createElement("li", { class: "item", "data-index": 2 }, ["第3个列表项"])
  20.   ]
  21. );
  23. const vDom2 = createElement(
  24.   "ul",
  25.   {
  26.     class: "list-wrap",
  27.     style: "width: 300px; height: 300px; background-color: orange"
  28.   },
  29.   [
  30.     createElement("li", { class: "item", "data-index": 0 }, [
  31.       createElement("p", { class: "title" }, ["特殊列表项"])
  32.     ]),
  33.     createElement("li", { class: "item", "data-index": 1 }, [
  34.       createElement("p", { class: "text" }, [
  35.         // span 进行了删除
  36.       ])
  37.     ]),
  38.     createElement("div", { class: "item", "data-index": 2 }, ["第3个列表项"])
  39.   ]
  40. );
  42. const rDom = render(vDom1);
  43. renderDOM(rDom, document.getElementById("app"));
  45. const patch = domDiff(vDom1, vDom2);
  46. console.log(patch)

2、然后我要去实现这个domDiff()方法最后返回patch差异对象。

  1. import { REMOVE, REPLACE, TEXT, ATTR } from "./patchTypes";
  3. let patches = {}; // 一个全局的 patch 对象
  4. let vnIndex = 0;
  6. function domDiff(oldVDOM, newVDOM) {
  7.   let index = 0;
  9.   // 给 vNodeWalk 函数一个初始化的下标，结合我们本文的案例
  10.   // 就是给 ul 一个 index="0"
  11.   vNodeWalk(oldVDOM, newVDOM, index);
  12.   return patches;
  13. }
  15. function vNodeWalk(oldNode, newNode, index) {
  16.   // 每一个元素的更改内容
  17.   let vnPatch = [];
  19.   if (!newNode) {
  20.     // 如果没有新的节点，说明旧的节点被删除了
  21.     vnPatch.push({
  22.       type: REMOVE,
  23.       index
  24.     });
  25.   } else if (typeof oldNode === "string" && typeof newNode === "string") {
  26.     // 如果旧节点和新节点都是字符串
  27.     if (oldNode !== newNode) {
  28.       vnPatch.push({
  29.         type: TEXT,
  30.         text: newNode
  31.       });
  32.     }
  33.   } else if (oldNode.type !== newNode.type) {
  34.     // 如果节点的类型不同，说明节点发生了变化
  35.     vnPatch.push({
  36.       type: REPLACE,
  37.       newNode
  38.     });
  39.   } else if (oldNode.type === newNode.type) {
  40.     // 如果节点类型一样，那就是看属性是否发生了变化
  41.     const attrPatch = attrsWalk(oldNode.props, newNode.props);
  43.     if (Object.keys(attrPatch).length > 0) {
  44.       vnPatch.push({
  45.         type: ATTR,
  46.         attrs: attrPatch
  47.       });
  48.     }
  50.     childrenWalk(oldNode.children, newNode.children);
  51.   }
  53.   if (vnPatch.length > 0) {
  54.     patches[index] = vnPatch;
  55.   }
  56. }
  58. // 让子级去递归 diff
  59. function childrenWalk(oldChildren, newChildren) {
  60.   if (!oldChildren) {
  61.     return false;
  62.   }
  64.   oldChildren.forEach((el, index) => {
  65.     // 这里的 vnIndex 是全局的 index
  66.     // 因为 diff 是深度遍历的，所以是 ul>li>p 这样遍历的
  67.     // 所以当每个元素的子元素遍历的时候都会去操作这个 index
  68.     // 因为 ul 有一个默认的 index=0 所以我们不关心 ul
  69.     // ul 的子元素是 li ，所以 li.index=1 > p.index=2 > ...
  70.     // 这样深度遍历，所以 vnIndex 就是作为一个全局的 index ，每次遍历都会进行改变
  71.     vNodeWalk(el, newChildren[index], ++vnIndex);
  72.   });
  73. }
  75. // 处理元素的属性
  76. function attrsWalk(oldProps, newProps) {
  77.   let attrPatch = {};
  79.   // 判断是否更改
  80.   for (const key in oldProps) {
  81.     if (oldProps[key] !== newProps[key]) {
  82.       attrPatch[key] = newProps[key];
  83.     }
  84.   }
  86.   // 判断是否新增
  87.   for (const key in newProps) {
  88.     if (!oldProps.hasOwnProperty(key)) {
  89.       attrPatch[key] = newProps[key];
  90.     }
  91.   }
  93.   return attrPatch;
  94. }
  96. export { domDiff };

以上代码中，我们主要是通过domDiff()方法作为入口，然后使用vNodeWalk()方法去判断每一种类型的变化，最终把最有节点的变化都保存到了patches对象中，该对象的结构和我们上文中定义的patches对象结构是一致的！
另外，关于上面代码，你需要理解的是vnIndex的作用。因为我们介绍 DOM Diff 的时候说过了，其一个特点是深度优先遍历，所以上面代码中我们首次执行vNodeWalk()方法的是就传递了一个初始化的index，也就是给ul元素绑定了一个index。然后ul元素对比完就会执行childrenWalk()方法，然后就会去自加vnIndex全局下标，对应本文案例就是给li绑定index=1，然后li又执行完又去执行childrenWalk()，然后再操作vnIndex，这时p元素就是index=2。
执行完第一次子元素，就去执行第二层子元素，这时同样还是操作vnIndex…
DOM Diff - 图12
简单画了这么一个草图。
通过domDiff的对比，我们最终得到了和上文中一样的patch对象：
image.png

3、那么最后一步肯定就是要去对应真实的 DOM 进行操作了。

  1. import { createElement, render, renderDOM } from "./virtualDom";
  2. import { domDiff } from "./domDiff";
  3. import { doPatch } from "./doPatch.js";
  5. const vDom1 = createElement(
  6.   "ul",
  7.   {
  8.     class: "list",
  9.     style: "width: 300px; height: 300px; background-color: orange"
  10.   },
  11.   [
  12.     createElement("li", { class: "item", "data-index": 0 }, [
  13.       createElement("p", { class: "text" }, ["第1个列表项"])
  14.     ]),
  15.     createElement("li", { class: "item", "data-index": 1 }, [
  16.       createElement("p", { class: "text" }, [
  17.         createElement("span", { class: "title" }, ["第2个列表项"])
  18.       ])
  19.     ]),
  20.     createElement("li", { class: "item", "data-index": 2 }, ["第3个列表项"])
  21.   ]
  22. );
  24. const vDom2 = createElement(
  25.   "ul",
  26.   {
  27.     class: "list-wrap",
  28.     style: "width: 300px; height: 300px; background-color: orange"
  29.   },
  30.   [
  31.     createElement("li", { class: "item", "data-index": 0 }, [
  32.       createElement("p", { class: "title" }, ["特殊列表项"])
  33.     ]),
  34.     createElement("li", { class: "item", "data-index": 1 }, [
  35.       createElement("p", { class: "text" }, [
  36.         // span 进行了删除
  37.       ])
  38.     ]),
  39.     createElement("div", { class: "item", "data-index": 2 }, ["第3个列表项"])
  40.   ]
  41. );
  43. const rDom = render(vDom1);
  44. renderDOM(rDom, document.getElementById("app"));
  46. const patch = domDiff(vDom1, vDom2);
  47. doPatch(rDom, patch);

我们继续写一个doPatch()方法，让这个方法去做对应的渲染。

  1. import { ATTR, TEXT, REPLACE, REMOVE } from "./patchTypes";
  2. import { setAttrs, render } from "./virtualDom";
  3. import Element from "./Element";
  5. let finalPatches = {}; // 全局的 patch 对象
  6. let rnIndex = 0; // 全局的 index
  8. function doPatch(rDom, patches) {
  9.   finalPatches = patches;
  10.   rNodeWalk(rDom);
  11. }
  13. function rNodeWalk(rNode) {
  14.   // 这里的 rnIndex 和 domDiff 里的 vnIndex 作用是一样的
  15.   const rnPatch = finalPatches[rnIndex++];
  16.   const childNodes = rNode.childNodes;
  18.   if (rnPatch) {
  19.     // 先去处理自己
  20.     patchAction(rNode, rnPatch);
  21.   }
  23.   // 然后让子元素去递归
  24.   [...childNodes].map((c) => {
  25.     rNodeWalk(c);
  26.   });
  27. }
  29. function patchAction(rNode, rnPatch) {
  30.   rnPatch.map((p) => {
  31.     switch (p.type) {
  32.       case ATTR:
  33.         for (let key in p.attrs) {
  34.           const value = p.attrs[key];
  36.           // 如果有值就调用 virtualDom 文件的 setAttrs() 对属性进行设置或者覆盖
  37.           if (value) {
  38.             setAttrs(rNode, key, value);
  39.           } else {
  40.             // 否则进行删除
  41.             rNode.removeAttribute(key);
  42.           }
  43.         }
  44.         break;
  45.       case TEXT:
  46.         // 直接进行替换
  47.         rNode.textContent = p.text;
  48.         break;
  49.       case REPLACE:
  50.         const newNode =
  51.           p.newNode instanceof Element
  52.             ? render(p.newNode)
  53.             : document.createTextNode(p.newNode);
  55.         // 替换为新的元素
  56.         rNode.parentNode.replaceChild(newNode, rNode);
  57.         break;
  58.       case REMOVE:
  59.         // 删除
  60.         rNode.parentNode.removeChild(rNode);
  61.         break;
  62.       default:
  63.         break;
  64.     }
  65.   });
  66. }
  68. export { doPatch };

这样就完成了替换！
image.png

源码地址：
JSPlusPlus/index.js at main · xiechen1201/JSPlusPlus