# 虚拟dom virtual DOM
DOM是很慢的。如果把一个简单的div元素的属性都打印出来：
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body>
<div id="k1"></div>
<div id="valuesP"></div>
</body>
</html>
<script type="text/javascript">
var myLink = document.getElementById("k1");
var str = '';
var num=0;
//结果拼接
for(var prop in myLink){ //循环遍历myLink的所有属性key
//拼接到str，key和value用冒号隔开
str += prop + " : " + myLink[prop] + "<br/>";
num++;
}
//打印到网页里
document.getElementById("valuesP").innerHTML = str;
console.log(num)//两三百个属性
</script>
而这仅仅是第一层。真正的 DOM 元素非常庞大，因为标准就是这么设计的。而且操作它们的时候要小心翼翼，轻微的触碰可能就会导致页面重排，这可是影响性能的罪魁祸首。
相对于 DOM 对象，原生的 JS 对象处理起来更快，而且更简单。DOM 树上的结构、属性信息都可以很容易地用JS对象表示出来：
var element = {
tagName: 'ul', // 节点标签名
props: { // DOM的属性，用一个对象存储键值对
id: 'list'
},
children: [ // 该节点的子节点
{tagName: 'li', props: {class: 'item'}, children: ["Item 1"]},
{tagName: 'li', props: {class: 'item'}, children: ["Item 2"]}
]
}
上面对应的HTML写法是：
<ul id='list'>
<li class='item'>Item 1</li>
<li class='item'>Item 2</li>
</ul>
既然原来 DOM 树的信息都可以用 JS 对象来表示，反过来，可以根据这个用对象表示的树结构来构建一棵真正的DOM树。
用 JS 对象表示 DOM 信息和结构，当状态变更的时候，重新渲染这个 JS 的对象结构。
可以用新渲染的对象树和旧的树对比，记录差异。记录的不同就是需要对页面真正的 DOM 操作，然后把它们应用在真正的 DOM 树上，页面就变更了。这样就可以做到：视图的结构确实是整个全新渲染了，但是最后操作DOM的时候确实只变更有不同的地方。
这就是所谓的 Virtual DOM 算法。包括几个步骤：
- 用 JS对象结构表示 DOM 树的结构；然后用这个树构建一个真正的 DOM 树，插到文档当中
- 当状态变更的时候，重新构造一棵新的对象树。然后用新的树和旧的树进行比较，记录两棵树差异
- 把2所记录的差异应用到步骤1所构建的真正的DOM树上，视图就更新了
Virtual DOM 本质上就是在 JS 和 DOM 之间做了一个缓存。可以类比 CPU 和硬盘，既然硬盘这么慢，就在它们之间加个缓存：既然 DOM 这么慢，就在 JS 和 DOM 之间加个缓存。CPU（JS）只操作内存（Virtual DOM），最后的时候再把变更写入硬盘（DOM）。
- patch函数
- patchVnode函数
- addVnodes removeVnodes函数
- updateChildren函数
# Vnode
- VNode的全称是Virtual Node，也就是虚拟节点；
- 事实上，无论是组件还是元素，它们最终在Vue中表示出来的都是一个个VNode（一个个节点）；
- VNode的本质是一个JavaScript的对象；
# VDom
虚拟DOM（VDOM 是多个vnode形成的树结构）
# diff 时间复杂度O(n)
vdom最核心最关键部分
- 只比较同一层级，不跨级
- tag不同，直接删除重建
- tag和key相同，则认为是相同节点，不再深度比较
vue的虚拟dom经过改良，只同级比较，同时标签名如果改变，就直接不再继续比较，直接删除老的，创建新标签。
# snabbdom
像vue的vnode就是依赖snabbdom
var snabbdom = require('snabbdom');
var patch = snabbdom.init([ // Init patch function with chosen modules
require('snabbdom/modules/class').default, // makes it easy to toggle classes
require('snabbdom/modules/props').default, // for setting properties on DOM elements
require('snabbdom/modules/style').default, // handles styling on elements with support for animations
require('snabbdom/modules/eventlisteners').default, // attaches event listeners
]);
var h = require('snabbdom/h').default; // helper function for creating vnodes
var container = document.getElementById('container');
var 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);
var 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
<body>
<div id="container"></div>
<button id='btn-change'>change</button>
<script src="https://cdn.bootcss.com/snabbdom/0.7.1/h.js"></script>
<script src="https://cdn.bootcss.com/snabbdom/0.7.1/snabbdom.js"></script>
<script src="https://cdn.bootcss.com/snabbdom/0.7.1/snabbdom-style.js"></script>
<script src="https://cdn.bootcss.com/snabbdom/0.7.1/snabbdom-props.js"></script>
<script src="https://cdn.bootcss.com/snabbdom/0.7.1/snabbdom-class.js"></script>
<script src="https://cdn.bootcss.com/snabbdom/0.7.1/snabbdom-eventlisteners.js"></script>
<script>
var snabbdom = window.snabbdom
var patch = snabbdom.init([
snabbdom_class,
snabbdom_props,
snabbdom_style,
snabbdom_eventlisteners
])
var h = snabbdom.h
var container = document.getElementById('container')
// 生成vnode
var vnode = h('ul#list', {}, [
h('li.item', {}, 'item 1'),
h('li.item', {}, 'item 2'),
])
// 初次渲染,把vnode的内容全部添加到空白的容器中
patch(container, vnode)
document.getElementById('btn-change').addEventListener('click', () => {
// 生成新的vnode
var newVnode = h('ul#list', {}, [
h('li.item', {}, 'item 1'),
h('li.item', {}, 'item B'),
h('li.item', {}, 'item 3'),
])
// 再次渲染,对比new vnode 和 old vnode,将真正需要渲染的部分进行渲染,不需要渲染的部分,不会更改
patch(vnode, newVnode)
})
</script>
</body>
# h函数
import { vnode, VNode, VNodeData } from "./vnode";
import * as is from "./is";
export type VNodes = 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.toString();
} 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.toString();
} else if (b && b.sel) {
children = [b];
} else {
data = b;
}
}
if (children !== undefined) {
for (i = 0; i < children.length; ++i) {
if (is.primitive(children[i]))
children[i] = vnode(
undefined,
undefined,
undefined,
children[i],
undefined
);
}
}
// children, text同时只存在一个
return vnode(sel, data, children, text, undefined);
}
# vnode函数
export interface VNode {
sel: string | undefined;
data: VNodeData | undefined;
children: Array<VNode | string> | undefined;
elm: Node | undefined;
text: string | undefined;
key: Key | undefined;
}
......
export function vnode(
sel: string | undefined,
data: any | undefined,
children: Array<VNode | string> | undefined,
text: string | undefined,
elm: Element | Text | undefined
): VNode {
const key = data === undefined ? undefined : data.key;
//返回一个标准的js对象
return { sel, data, children, text, elm, key };
}
# patch函数
- init.ts中的返回函数patch
function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
const isSameKey = vnode1.key === vnode2.key;
const isSameIs = vnode1.data?.is === vnode2.data?.is;
const isSameSel = vnode1.sel === vnode2.sel;
return isSameSel && isSameKey && isSameIs;
}
const hooks: Array<keyof Module> = [
"create",
"update",
"remove",
"destroy",
"pre",
"post",
];
export function init(modules: Array<Partial<Module>>, domApi?: DOMAPI) {
......
return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
let i: number, elm: Node, parent: Node;
const insertedVnodeQueue: VNodeQueue = [];
for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();
if (!isVnode(oldVnode)) {
oldVnode = emptyNodeAt(oldVnode);
}
//是不是之前的同一个元素
if (sameVnode(oldVnode, vnode)) {
//patchVnode比较children/text具体情况
patchVnode(oldVnode, vnode, insertedVnodeQueue);
} else {
elm = oldVnode.elm!;
parent = api.parentNode(elm) as Node;
createElm(vnode, insertedVnodeQueue);
if (parent !== null) {
api.insertBefore(parent, vnode.elm!, api.nextSibling(elm));
removeVnodes(parent, [oldVnode], 0, 0);
}
}
for (i = 0; i < insertedVnodeQueue.length; ++i) {
insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i]);
}
for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
return vnode;
};
}
# patchVnode
function patchVnode(
oldVnode: VNode,
vnode: VNode,
insertedVnodeQueue: VNodeQueue
) {
const hook = vnode.data?.hook;
hook?.prepatch?.(oldVnode, vnode);
//给新的vnode绑定elm
const elm = (vnode.elm = oldVnode.elm)!;
const oldCh = oldVnode.children as VNode[];
const ch = vnode.children as VNode[];
if (oldVnode === vnode) return;
if (vnode.data !== undefined) {
for (let i = 0; i < cbs.update.length; ++i)
cbs.update[i](oldVnode, vnode);
vnode.data.hook?.update?.(oldVnode, vnode);
}
//isUndef :判断是不是未定义text
if (isUndef(vnode.text)) {
if (isDef(oldCh) && isDef(ch)) {
if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
} else if (isDef(ch)) {
if (isDef(oldVnode.text)) api.setTextContent(elm, "");
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
} else if (isDef(oldCh)) {
removeVnodes(elm, oldCh, 0, oldCh.length - 1);
} else if (isDef(oldVnode.text)) {
api.setTextContent(elm, "");
}
} else if (oldVnode.text !== vnode.text) {
if (isDef(oldCh)) {
removeVnodes(elm, oldCh, 0, oldCh.length - 1);
}
api.setTextContent(elm, vnode.text!);
}
hook?.postpatch?.(oldVnode, vnode);
}
TIP
比较两个VNode，包括三种类型操作：属性更新、文本更新、子节点更新 具体规则如下：
- 新老节点均有children子节点，则对子节点进行diff操作，调用updateChildren
- 如果新节点有子节点而老节点没有子节点，先清空老节点的文本内容，然后为其新增子节点。
- 当新节点没有子节点而老节点有子节点的时候，则移除该节点的所有子节点。
- 当新老节点都无子节点的时候，只是文本的替换。
# updateChildren
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;
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];
} 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];
} 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];
} else {
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
}
idxInOld = oldKeyToIdx[newStartVnode.key as string];
if (isUndef(idxInOld)) {
// New element
api.insertBefore(
parentElm,
createElm(newStartVnode, insertedVnodeQueue),
oldStartVnode.elm!
);
} else {
elmToMove = oldCh[idxInOld];
if (elmToMove.sel !== newStartVnode.sel) {
api.insertBefore(
parentElm,
createElm(newStartVnode, insertedVnodeQueue),
oldStartVnode.elm!
);
} else {
patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
oldCh[idxInOld] = undefined as any;
api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
}
}
newStartVnode = newCh[++newStartIdx];
}
}
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 {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
}
}
}
# 虚拟dom总结
- diff算法是虚拟DOM技术的必然产物：通过新旧虚拟DOM作对比（即diff），将变化的地方更新在真 实DOM上；另外，也需要diff高效的执行对比过程，从而降低时间复杂度为O(n)。
- vue 2.x中为了降低Watcher粒度，每个组件只有一个Watcher与之对应，只有引入diff才能精确找到 发生变化的地方。
- vue中diff执行的时刻是组件实例执行其更新函数时，它会比对上一次渲染结果oldVnode和新的渲染 结果newVnode，此过程称为patch。
- diff过程整体遵循深度优先、同层比较的策略；两个节点之间比较会根据它们是否拥有子节点或者文 本节点做不同操作；比较两组子节点是算法的重点，首先假设头尾节点可能相同做4次比对尝试，如果 没有找到相同节点才按照通用方式遍历查找，查找结束再按情况处理剩下的节点；借助key通常可以非 常精确找到相同节点，因此整个patch过程非常高效。
# vue3的diff算法
- 缓存事件
- 静态标记
- 缓存静态提升
- 采用最长递增子序列算法
# 参考链接
← js基础类型 shadowroot →