简单虚拟 DOM 结构
- DOM 节点
- js模拟 vnode 节点
snabbdom使用
- index.html
- index.js
diff算法
- 步骤
- 复杂度
  - 树 diff 的时间复杂度 O(n^3)
  - 优化时间复杂度到 O(n)
snabbdom源码分析
- 案例分析
  - 大白话解释
  - hook 钩子
- 源码分析
infernojs源码分析
diff 过程
vnode.key的作用是什么？
Vue 与 React实现对比
Vue2和Vue3和React三者的diff算法有什么

Virtual DOM 就是用 JS 对象去模拟 DOM 结构，它是真实 DOM 的抽象，只保留一些有用的信息，更轻量地描述 DOM 树的结构；新旧 vnode 对比，得出最小的更新范围，最后更新 DOM；数据驱动视图的模式下，有效控制 DOM 操作。

简单虚拟 DOM 结构

DOM 节点

<div id="app" class="container">
  <p>我是p标签</p>
  <ul style="background-color: red">
    <li>我是a标签</li>
  </ul>
</div>

js模拟 vnode 节点

{
    tag: "div",
    props: {
        className: "container",
        id: "app",
    },
    children: [
        {
            tag: "p",
            children: "我是p标签",
        },
        {
            tag: "ul",
            props: { style: "background-color: red" },
            children: [
                {
                    tag: "li",
                    children: "我是a标签",
                },
            ],
        },
    ],
};

snabbdom使用

案例代码：https://github.com/WuChenDi/Front-End/tree/master/12-snabbdom/virtual-dom

index.html

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>snabbdom</title>
    </head>
    <body>
    <div id="app">app</div>
    <div id="container">container</div>
    <button id="btn-change">change</button>
    <script src="./src/index.js"></script>
    </body>
</html>

index.js

// index.js
{
  import { init, h } from "snabbdom";
  let patch = init([]);
  let vnode = h("div", "Hello World");
  let app = document.querySelector("#app");
  console.log(app);
  let oldVnode = patch(app, vnode);
  vnode = h("div#dd", "Hello cdd");
  patch(oldVnode, vnode);
}
{
  import { init, h } from "snabbdom";
  let patch = init([]);
  let vnode = h("div#container", [
    h("h1", "我是h1标签"),
    h("ul", [h("li", "我是li标签")]),
  ]);
  let app = document.querySelector("#app");
  patch(app, vnode);
  setTimeout(() => {
    var newVnode = h("div#container", [h("h2", "我是h2标签")]);
    patch(vnode, newVnode);
  }, 2000);
  // setTimeout(() => {
  //     var newVnode = h("div#container", [h("h2", "我是h2标签")]);
  //     patch(vnode, h("!"));
  // }, 2000);
}
{
  import { init, h } from "snabbdom";
  // 定义 patch
  const patch = init([
    snabbdom_class,
    snabbdom_props,
    snabbdom_style,
    snabbdom_eventlisteners,
  ]);
  const container = document.getElementById("container");
  // 生成 vnode
  const vnode = h("ul#list", {}, [
    h("li.item", {}, "Item 1"),
    h("li.item", {}, "Item 2"),
  ]);
  patch(container, vnode);
  document.getElementById("btn-change").addEventListener("click", () => {
    // 生成 newVnode
    const newVnode = h("ul#list", {}, [
      h("li.item", {}, "Item 1"),
      h("li.item", {}, "Item B"),
      h("li.item", {}, "Item 3"),
    ]);
    patch(vnode, newVnode);
  });
}

diff算法

步骤

用 js 对象来描述 dom 树结构，然后用这个 js 对象来创建一棵真正的 dom 树，插入到文档中；当状态更新时，将新的 js 对象和旧的 js 对象进行比较，得到两个对象之间的差异；最后将差异应用到真正的 dom 上。

复杂度

树 diff 的时间复杂度 O(n^3)

第一次需要对 oldVnode 遍历一次tree
然后第二次对 vnode 遍历tree
最后两者排序

优化时间复杂度到 O(n)

只比较同一层级，不跨级比较
tag 不相同，则直接删掉重建，不再深度比较
tag 与 key，两者都相同，则认为是相同节点，不再深度比较

虚拟DOM（Virtual DOM）和 diff - 图1
虚拟DOM（Virtual DOM）和 diff - 图2

snabbdom源码分析

https://github.com/snabbdom/snabbdom https://github.com/coconilu/Blog/issues/152

案例分析

import {
    init,
    classModule,
    propsModule,
    styleModule,
    eventListenersModule,
    h,
} from "snabbdom";
const patch = init([
    // Init patch function with chosen modules
    classModule, // makes it easy to toggle classes
    propsModule, // for setting properties on DOM elements
    styleModule, // handles styling on elements with support for animations
    eventListenersModule, // attaches event listeners
]);
const container = document.getElementById("container");
const vnode = h("div#container.two.classes", { on: { click: someFn } }, [
    h("span", { style: { fontWeight: "bold" } }, "This is bold"),
    " and this is just normal text",
    h("a", { props: { href: "/foo" } }, "I'll take you places!"),
]);
// Patch into empty DOM element – this modifies the DOM as a side effect
patch(container, vnode);
const newVnode = h(
    "div#container.two.classes",
    { on: { click: anotherEventHandler } },
    [
        h(
            "span",
            { style: { fontWeight: "normal", fontStyle: "italic" } },
            "This is now italic type"
        ),
        " and this is still just normal text",
        h("a", { props: { href: "/bar" } }, "I'll take you places!"),
    ]
);
// Second `patch` invocation
patch(vnode, newVnode); // Snabbdom efficiently updates the old view to the new state

大白话解释

首先 snabbdom 模块提供一个 init 方法，调用 init 方法会返回一个 patch 函数，第一个参数 oldVNode 或 DOM，第二个参数是新的 VNode 节点，调用 patch 函数会对 DOM 进行更新。通过调用 h 函数来创建 VNode。初始化 patch(container, vnode)，container作为应用根节点，更新patch(vnode, newVnode)。

hook 钩子

Name	Triggered when	触发时机	Arguments to callback
pre	the patch process begins	patch 开始之前	none
init	a vnode has been added	已经创建了一个 vnode	vnode
create	a DOM element has been created based on a vnode	已经基于 vnode 创建了一个 DOM，但尚未挂载	emptyVnode, vnode
insert	an element has been inserted into the DOM	创建的 DOM 被挂载了	vnode
prepatch	an element is about to be patched	一个元素即将被 patch	oldVnode, vnode
update	an element is being updated	元素正在被更新	oldVnode, vnode
postpatch	an element has been patched	元素已经 patch 完毕	oldVnode, vnode
destroy	an element is directly or indirectly being removed	一个元素被直接或间接地移除了。间接移除的情况是指被移除元素的子元素	vnode
remove	an element is directly being removed from the DOM	一个元素被直接移除了（卸载）	vnode, removeCallback
post	the patch process is done	patch 结束	none

源码分析

https://github.com/WuChenDi/Front-End/blob/master/12-snabbdom/3.0.1

vnode

export interface VNode {
  sel: string | undefined; // selector
  data: VNodeData | undefined;
  children: Array<VNode | string> | undefined; // 子节点
  elm: Node | undefined; // element, 存储 HTMLELement
  text: string | undefined; // 文本节点
  key: Key | undefined; // 节点 key
}
export interface VNodeData {
  props?: Props; // 节点属性
  attrs?: Attrs; // 节点 attribute 属性
  class?: Classes; // class 类名
  style?: VNodeStyle; // style 样式
  dataset?: Dataset; // html 自定义属性 data-
  on?: On; // 事件
  attachData?: AttachData;
  hook?: Hooks; // 钩子
  key?: Key;
  ns?: string; // for SVGs
  fn?: () => VNode; // for thunks
  args?: any[]; // for thunks
  is?: string; // for custom elements v1
  [key: string]: any; // for any other 3rd party module
}

h 函数

h 渲染函数实际上只用于创建 vnode，并没有将 vnode 绘制到文档中。作为接口，h 渲染函数本身也只包含参数多态的处理，由于存在多种参数情况，所以首先会对参数进行格式化，在对 children 处理，如果是 svg 元素，调用 addNS 函数处理，最后返回 vnode 。

export function h(sel: string): VNode;
export function h(sel: string, data: VNodeData | null): VNode;
export function h(sel: string, children: VNodeChildren): VNode;
export function h(sel: string, data: VNodeData | null, children: VNodeChildren): VNode;
export function h(sel: any, b?: any, c?: any): VNode {
  let data: VNodeData = {};
  let children: any;
  let text: any;
  let i: number;
  // 参数格式化
  if (c !== undefined) {
    if (b !== null) {
      data = b;
    }
    if (is.array(c)) {
      children = c;
    } else if (is.primitive(c)) {
      text = c;
    } else if (c && c.sel) {
      children = [c];
    }
  } else if (b !== undefined && b !== null) {
    if (is.array(b)) {
      children = b;
    } else if (is.primitive(b)) {
      text = b;
    } else if (b && b.sel) {
      children = [b];
    } else {
      data = b;
    }
  }
  // 如果存在 children，将不是 vnode 的项转成 vnode
  if (children !== undefined) {
    for (i = 0; i < children.length; ++i) {
      if (is.primitive(children[i]))
        children[i] = vnode(
          undefined,
          undefined,
          undefined,
          children[i],
          undefined
        );
    }
  }
  // svg 元素添加 namespace
  if (sel[0] === "s" && sel[1] === "v" && sel[2] === "g" && (sel.length === 3 || sel[3] === "." || sel[3] === "#")) {
    addNS(data, children, sel);
  }
  // 返回 vnode
  return vnode(sel, data, children, text, undefined);
}

sameVnode 函数

sameVnode 函数的主要逻辑是用来判断 vnode 节点是否为相同

function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
    // key 和 sel 都相等
    // 如果 key 没有传入 => undefined === undefined // true
    // 不传 key 情况分析：不在循环体里面，像直接定义的情况，直接通过 tag/sel 来比较
    const isSameKey = vnode1.key === vnode2.key;
    const isSameIs = vnode1.data?.is === vnode2.data?.is;
    const isSameSel = vnode1.sel === vnode2.sel;
    return isSameSel && isSameKey && isSameIs;
}

createKeyToOldIdx 函数

createKeyToOldIdx 函数返回 map 将所有定义了 key 的 oldVNode 在数组中的 index 作为键值，key作为键名存储起来，然后赋给 oldKeyToIdx（updateChildren 方法使用）

function createKeyToOldIdx(children: VNode[], beginIdx: number, endIdx: number): KeyToIndexMap {
    const map: KeyToIndexMap = {};
    for (let i = beginIdx; i <= endIdx; ++i) {
        const key = children[i]?.key;
        if (key !== undefined) {
            map[key as string] = i;
        }
    }
    return map;
}

createElm 函数

大白话

createElm 函数的主要逻辑在于创建真实的 DOM 节点 vnode.elm。首先调用 init hook ，然后创建 DOM 树分为如下三种情形：

vnode.sel === ‘!’ 表示当前元素是注释节点，调用 createComment 创建注释节点，挂载到 vnode.elm；
vnode.sel !== ‘undefined’，对当前选择器进行解析（tag、id，class等），调用 createElementNS 或 createElement 生成 elm，接着调用 create hook，如果存在 children，遍历所有子节点并递归调用 createElm 创建 dom，通过 appendChild 挂载到当前的 elm 上，不存在 children 但存在 text，便使用 createTextNode 来创建文本，再次调用 create hook 与 insert hook 存储起来等 dom 插入后才会调用，这里用个数组来保存能避免调用时再次对 vnode 树做遍历；
以上两种都不满足时，表示当前只是 text，调用 createTextNode 来创建文本，然后挂载到 vnode.elm；

流程图

coding
```typescript function createElm(vnode: VNode, insertedVnodeQueue: VNodeQueue): Node { let i: any; let data = vnode.data; if (data !== undefined) { // 调用 init hook const init = data.hook?.init; if (isDef(init)) {
```
init(vnode);
data = vnode.data;
```
} } const children = vnode.children; const sel = vnode.sel; // 注释节点 if (sel === “!”) { if (isUndef(vnode.text)) {
```
vnode.text = "";
```
} // 创建注释节点 vnode.elm = api.createComment(vnode.text!); } else if (sel !== undefined) { // Parse selector const hashIdx = sel.indexOf(“#”); const dotIdx = sel.indexOf(“.”, hashIdx); const hash = hashIdx > 0 ? hashIdx : sel.length; const dot = dotIdx > 0 ? dotIdx : sel.length; const tag = hashIdx !== -1 || dotIdx !== -1 ? sel.slice(0, Math.min(hash, dot)) : sel; const elm = (vnode.elm = isDef(data) && isDef((i = data.ns)) ? api.createElementNS(i, tag, data) : api.createElement(tag, data));

if (hash < dot) elm.setAttribute(“id”, sel.slice(hash + 1, dot)); if (dotIdx > 0) elm.setAttribute(“class”, sel.slice(dot + 1).replace(/./g, “ “));

// 调用 create hook for (i = 0; i < cbs.create.length; ++i) cbs.createi;

// 挂载子节点（递归创建节点） if (is.array(children)) {
```
for (i = 0; i < children.length; ++i) {
  const ch = children[i];
  if (ch != null) {
    api.appendChild(elm, createElm(ch as VNode, insertedVnodeQueue));
  }
}
```
} else if (is.primitive(vnode.text)) {
```
api.appendChild(elm, api.createTextNode(vnode.text));
```
} const hook = vnode.data!.hook; if (isDef(hook)) {
```
// 调用 create hook
hook.create?.(emptyNode, vnode);
if (hook.insert) {
  // insert hook 存储起来 等 dom 插入后才会调用，这里用个数组来保存能避免调用时再次对 vnode 树做遍历
  insertedVnodeQueue.push(vnode);
}
```
} } else { // 文本节点 vnode.elm = api.createTextNode(vnode.text!); } return vnode.elm; }

<a name="IVqbP"></a>
### patchVnode 函数
<a name="wJfOf"></a>
#### 大白话
patchVnode 函数的主要逻辑在于更新节点。首先调用 vnode 上的 prepatch hook，如果当前的两个 vnode 完全相同，直接返回。然后分如下两大类情形：
- vnode.text === undefined
   - 新旧节点都存在 children，执行 updateChildren 更新
   - 存在新 children，不存在旧 children，如果旧 text 存在，则先清空在调用 addVnodes 添加children
   - 不存在新 children，存在旧 children，调用 removeVnodes 移除旧节点的 children
   - oldVnode 存在 text，调用 setTextContent 置空
- vnode.text !== undefined，移除 oldVnode 对应的 dom 节点，并使用 setTextContent 更新 vnode.elm
<a name="yhXcy"></a>
#### 流程图
![](https://cdn.nlark.com/yuque/0/2021/jpeg/1544252/1619164370250-dc9e73ff-4f20-479d-a9b2-d58f59cb56e4.jpeg)
<a name="1qVpj"></a>
#### coding
```typescript
function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
    // 执行 prepatch hook
    const hook = vnode.data?.hook;
    hook?.prepatch?.(oldVnode, vnode);
    // 设置 vnode.elm
    const elm = (vnode.elm = oldVnode.elm)!;
    // 旧 children
    const oldCh = oldVnode.children as VNode[];
    // 新 children
    const ch = vnode.children as VNode[];
    // 如果 oldVnode 和 vnode 是完全相同，说明无需更新，直接返回。
    // 极少这种情况，除非人为测试
    if (oldVnode === vnode) return;
    // hook 相关
    if (vnode.data !== undefined) {
        // 调用 update hook
        for (let i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
        // 调用 vnode update hook
        vnode.data.hook?.update?.(oldVnode, vnode);
    }
    // 新test(vnode.text) === undefined (vnode.children != undefined) / (vnode.children 一般有值)
    // text 与 children 不可能共存，但是都为 undefined 成立
    if (isUndef(vnode.text)) {
        // 新旧都有 children
        if (isDef(oldCh) && isDef(ch)) {
            // 新旧节点都存在 children 就执行 updateChildren
            if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
        }
        // 存在新 children，不存在旧 children（有可能存在旧 text）
        else if (isDef(ch)) {
            // 如果旧 text 存在值，先置空
            if (isDef(oldVnode.text)) api.setTextContent(elm, "");
            // 添加 children
            addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
        }
        // 存在旧 children，不存在新 children（有可能存在旧 text）
        else if (isDef(oldCh)) {
            // 移除旧节点的 children
            removeVnodes(elm, oldCh, 0, oldCh.length - 1);
        } else if (isDef(oldVnode.text)) {
            // 旧节点存在 text 置空
            api.setTextContent(elm, "");
        }
    }
    // else: vnode.text !== undefined (vnode.children 无值)
    else if (oldVnode.text !== vnode.text) {
        // 移除旧 children
        if (isDef(oldCh)) {
            // 新节点删除了 children ,删除老的 DOM 元素
            removeVnodes(elm, oldCh, 0, oldCh.length - 1);
        }
        // 文本节点更新
        api.setTextContent(elm, vnode.text!);
    }
    // 调用 postpatch hook
    hook?.postpatch?.(oldVnode, vnode);
}

updateChildren 函数

大白话

流程图

coding

function updateChildren(parentElm: Node, oldCh: VNode[], newCh: VNode[], insertedVnodeQueue: VNodeQueue) {
    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: KeyToIndexMap | undefined;
    let idxInOld: number;
    let elmToMove: VNode;
    let before: any;
    // 遍历 oldCh newCh，对节点进行比较和更新
    // 每轮比较最多处理一个节点，算法复杂度 O(n)
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        if (oldStartVnode == null) {
            oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
        } else if (oldEndVnode == null) {
            oldEndVnode = oldCh[--oldEndIdx];
        } else if (newStartVnode == null) {
            newStartVnode = newCh[++newStartIdx];
        } else if (newEndVnode == null) {
            newEndVnode = newCh[--newEndIdx];
        }
        // 以旧 vnode 首节点和新 vnode 首节点对比
        else if (sameVnode(oldStartVnode, newStartVnode)) {
            patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
            oldStartVnode = oldCh[++oldStartIdx];
            newStartVnode = newCh[++newStartIdx];
        }
        // 以旧 vnode 尾节点和新 vnode 尾节点对比
        else if (sameVnode(oldEndVnode, newEndVnode)) {
            patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
            oldEndVnode = oldCh[--oldEndIdx];
            newEndVnode = newCh[--newEndIdx];
        }
        // 以旧 vnode 首节点和新 vnode 尾节点对比
        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];
        }
        // 以旧 vnode 尾节点和新 vnode 新节点对比
        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];
        }
        // 以上4中都未命中
        else {
            if (oldKeyToIdx === undefined) {
                oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
            }
            // 拿新节点 key ， 能否对应上 oldCh 中的某个节点的 key
            idxInOld = oldKeyToIdx[newStartVnode.key as string];
            // 对应不上
            if (isUndef(idxInOld)) {
                // New element
                api.insertBefore(
                    parentElm,
                    createElm(newStartVnode, insertedVnodeQueue),
                    oldStartVnode.elm!
                );
            }
            // 对应上了
            else {
                // 拿到对应上 key 的节点
                elmToMove = oldCh[idxInOld];
                // sel 是否相等（sameVnode 条件）
                // sel 不相等，key相等
                if (elmToMove.sel !== newStartVnode.sel) {
                    // New element
                    api.insertBefore(
                        parentElm,
                        createElm(newStartVnode, insertedVnodeQueue),
                        oldStartVnode.elm!
                    );
                }
                // sel 相等，key 相等
                else {
                    patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
                    oldCh[idxInOld] = undefined as any;
                    api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
                }
            }
            // 更新之后，调整指针
            newStartVnode = newCh[++newStartIdx];
        }
    }
    // oldCh 已经全部处理完成，而 newCh 还有新的节点，需要对剩下的每个项都创建新的 dom
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
        if (oldStartIdx > oldEndIdx) {
            before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;
            addVnodes(
                parentElm,
                before,
                newCh,
                newStartIdx,
                newEndIdx,
                insertedVnodeQueue
            );
        } else {
            // newCh 已经全部处理完成，而 oldCh 还有旧的节点，需要将多余的节点移除
            removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
        }
    }
}

infernojs源码分析

be continued

diff 过程

patch
patchVnode
addVnode
removeVnode
updateChildren
diff算法极致的性能优化做出的改变

vnode.key的作用是什么？

key 是用来判断两个 VNode 是否相同，参与到 diff 过程的一些判断中。key 情况分如下两种情况：

当 key 相同时，调用 patchVnode 函数更新节点，首先在旧列表中找到对应的 DOM 节点，然后执行移动操作；
当 key 不相同时，会调用 createElm 函数创建新节点，然后如果存在父节点，便将其插入到 dom 上，然后移除旧的 dom 节点来完成更新；

换句话说，key 用来在一个兄弟节点列表中进行唯一标记，这样在构建新节点的时候，会根据 key 去查找已经存在的节点，而不是就地复用，同时移除 key 不存在的节点。

Vue 与 React实现对比

Vue v2+ 中的 patch 机制就是基于 snabbdom 类库实现的（v3+ 切换到 infernojs）。
React v16+ 在推行 Fiber 之后，摒弃了递归 diff 的做法，但 diff 的核心思想是类似的。

Vue2和Vue3和React三者的diff算法有什么

Vue2：双端比较
Vue3：最长递增子序列
React：仅右移

虚拟DOM（Virtual DOM） 和 diff

简单虚拟 DOM 结构

DOM 节点

js模拟 vnode 节点

snabbdom使用

index.html

index.js

diff算法

步骤

复杂度

树 diff 的时间复杂度 O(n^3)

优化时间复杂度到 O(n)

snabbdom源码分析

案例分析

大白话解释

hook 钩子

源码分析

vnode

h 函数

sameVnode 函数

createKeyToOldIdx 函数

createElm 函数

大白话

流程图

coding

updateChildren 函数

大白话

流程图

coding

infernojs源码分析

diff 过程

vnode.key的作用是什么？

Vue 与 React实现对比

Vue2和Vue3和React三者的diff算法有什么

虚拟DOM（Virtual DOM）和 diff