Vue.js设计与实现-快速Diff算法
发表于:2024-12-10
字数统计:4302 字
预计阅读15分钟
html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Document</title>
<script src="https://unpkg.com/@vue/reactivity@3.0.5/dist/reactivity.global.js"></script>
</head>
<body>
<div id="app"></div>
</body>
<script>
function createRenderer(options) {
const {
createElement,
setElementText,
insert,
patchProps,
createText,
createComment,
setText,
} = options;
function render(vnode, container) {
if (vnode) {
// 新node存在，将其与旧node一起传递给patch函数，进行打补丁
patch(container._vnode, vnode, container);
} else {
if (container._vnode) {
// 旧node存在，且新node不存在，说明是卸载(unmount)操作
// 只需要将container中的DOM清空即可
// container.innerHTML = "";
// 8.5使用innerHTML直接清空是不严谨的，应该对每个DOM元素按照卸载流程清空
// 调用unmount函数卸载vnode
unmount(container._vnode);
}
}
// 把vnode存储到container._vnode下面，就是此次渲染结束，新node应该叫做旧node了
container._vnode = vnode;
}
function hydrate() {
// do sth...
}
function patch(n1, n2, container, anchor = null) {
// doing sth...
// 如果n1存在，则对比n1和n2的类型
console.log('update')
if (n1 && n1.type !== n2.type) {
// 如果新旧vnode的类型不同，直接将旧vnode卸载
unmount(n1);
n1 = null;
}
// 代码运行到这里，证明n1和n2所描述的内容相同
const { type } = n2;
// 如果n2.type的值是字符串类型，则它描述的是普通标签元素
if (typeof type === "string") {
if (!n1) {
// 挂载
mountElement(n2, container, anchor);
} else {
// 更新
patchElement(n1, n2);
}
} else if (type === Text) {
// 文本节点
if (!n1) {
// 如果没有就节点，那么挂载
const el = (n2.el = createText(n2.children));
// 插入
insert(el, container);
} else {
// 旧node存在，替换
const el = (n2.el = n1.el);
if (n2.children !== n1.children) {
setText(el, n2.children);
}
}
} else if (type === Comment) {
// 文本节点
if (!n1) {
// 如果没有就节点，那么挂载
const el = (n2.el = createComment(n2.children));
// 插入
insert(el, container);
} else {
// 旧node存在，替换
const el = (n2.el = n1.el);
if (n2.children !== n1.children) {
setText(el, n2.children);
}
}
} else if(type === Fragment) {
if (!n1) {
n2.children.forEach(c => patch(null, c, container))
} else {
patchChildren(n1, n2, container)
}
}
else if (typeof type === "object") {
// 如果n2.type的值的类型是对象，则它描述的是组件
} else if (type === "xxx") {
// 处理其他类型的vnode
}
}
function mountElement(vnode, container, anchor = null) {
// 创建DOM元素
// 让vnode.el引用真实DOM元素，便于后续卸载操作
const el = (vnode.el = createElement(vnode.type));
if (typeof vnode.children === "string") {
// 如果children是字符串，就直接放进去
setElementText(el, vnode.children);
} else if (Array.isArray(vnode.children)) {
// 如果children是数组，则遍历每一个子节点，并调用patch函数挂载他们
vnode.children.forEach((child) => {
patch(null, child, el);
});
}
// 如果vnode.props存在才处理它
if (vnode.props) {
// 遍历
for (const key in vnode.props) {
const value = vnode.props[key];
// 使用shouldSetAsProps函数判断是否应该作为DOM Properties代理
// 直接设置，是el[key]就行了，浏览器代理到DOM Properties上
// 抽离了依赖浏览器API的代码，封装到配置项中
patchProps(el, key, null, value);
}
}
insert(el, container, anchor);
}
function unmount(vnode) {
// 如果要卸载的是fragment，那么卸载它的children
if (vnode.type === Fragment) {
vnode.children.forEach(c => unmount(c))
return
}
// 根据_vnode获取要卸载的真实DOM元素
const el = vnode.el;
// 获取el的父元素
const parent = el.parentNode;
parent && parent.removeChild(el);
}
function patchChildren(n1, n2, container) {
// 判断新的子节点的类型是否是文本节点
// 文本子节点
if (typeof n2.children === "string") {
// 旧子节点的类型有三种可能，没有子节点。文本子节点和一组子节点
// 为一组子节点时，逐个卸载
if (Array.isArray(n1.children)) {
n1.children.forEach((child) => unmount(child));
}
// 其他情况什么也不用干，直接替换就行
setElementText(container, n2.children);
} else if (Array.isArray(n2.children)) {
// 说明新子节点时一组子节点
// 封装patchKeyedChildren函数处理两组子节点
patchKeyedChildren(n1, n2, container)
} else {
// 代码运行到这里，说明新子节点不存在
// 旧子节点是一组子节点，只需逐个卸载
if (Array.isArray(n1.children)) {
n1.children.forEach((c) => unmount(c));
} else if (typeof n1.children === "string") {
// 旧子节点是文本子节点，清空内容
setElementText(container, "");
}
// 如果没有旧子节点，啥也不干
}
}
function patchKeyedChildren(n1, n2, container) {
const oldChildren = n1.children
const newChildren = n2.children
// 处理相同的前置节点
// 索引j指向新旧两组子节点的开头
let j = 0
let oldVnode = oldChildren[j]
let newVnode = newChildren[j]
// while循环向后遍历，知道余导拥有不同key值的节点为止
while (oldVnode.key === newVnode.key) {
patch(oldVnode, newVnode, container)
// 更新索引
j++
oldVnode = oldChildren[j]
newVnode = newChildren[j]
}
// 处理相同的后置节点
// 索引newEnd和oldEnd分别指示
let newEndIdx = newChildren.length - 1
let oldEndIdx = oldChildren.length - 1
oldVnode = oldChildren[oldEndIdx]
newVnode = newChildren[newEndIdx]
while (oldVnode.key === newVnode.key) {
patch(oldVnode, newVnode, container)
newEndIdx--
oldEndIdx--
oldVnode = oldChildren[oldEndIdx]
newVnode = newChildren[newEndIdx]
}
// 以上就是预处理的内容，接下来，如果预处理顺利，那么存在两种情况
// 只需要挂载节点或者删除节点
// 挂载节点的进入条件是旧节点指示j > oldEndIdx
// 删除节点的进入条件是J <= oldEndIdx
if (j > oldEndIdx && j <= newEndIdx) {
// 获取描点的索引
const anchorIndex = newEndIdx + 1
// 描点
const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
while (j <= newEndIdx) {
patch(null, newChildren[j++], container, anchor)
}
} else if (j <= oldEndIdx && j > newEndIdx) {
unmount(oldChildren[j++])
} else {
// 处理不理想的情况，这种情况是预处理后，仍有较多的节点需要进行Diff算法
// 在这里，其实需要处理的情况和双端Diff需要处理的情况一致。不过快速Diff对双端Diff也进行了一些修改
// 为节点创建了一个source数组，source的长度与新的一组子节点的剩余未处理节点对应。
// 数量
const count = newEndIdx - j + 1
const source = new Array(count).fill(-1)
// source数组将会存储新的一组子节点每个子节点在旧的一组子节点对应的位置索引，
// 后面会计算一个最长递增子序列，辅助完成DOM移动操作（算法）
const oldStart = j
const newStart = j
// 新增两个变量：moved和pos，逻辑等同于简单Diff算法
let moved = false
let pos = 0
// 构建索引表
const keyIndex = {}
for(let i = newStart; i < newEndIdx; i++) {
keyIndex[newChildren[i].key] = i
}
// 新增patched变量，代表更新过的节点数量
let patched = 0
// 填充source数组
// 遍历旧的一组子节点
for(let i = oldStart; i <= oldEndIdx; i++) {
const oldVnode = oldChildren[i]
// 如果更新过的节点数量小于需要更新的节点数量，则执行更新
// 这其实就是在有大量卸载的时候（往往比较常见），无需执行k = keyIndex[oldVnode.key]这种伪查表（循环操作）
if (patched <= count) {
// 查表
const k = keyIndex[oldVnode.key]
if (typeof k !== 'undefined') {
newVnode = newChildren[k]
patch(oldVnode, newVnode, container)
source[k - newStart] = i
// 判断节点是否需要移动
if (k < pos) {
moved = true
} else {
pos = k
}
} else {
// 没找到
unmount(oldVnode)
}
} else {
// 大量卸载时，走这里
unmount(oldVnode)
}
}
// 移动逻辑
if (moved) {
// DOM移动操作
// 计算最长递增子序列
// seq指示这个最长递增子序列在source数组的索引
const seq = getSequence(source)
// s指向最长递增子序列的最后一个元素
let s = seq.length - 1
// i 指向新的一组子节点的最后一个元素
let i = count - 1
// for循环使得i递减
for(i; i >= 0; i--) {
// 新的节点中，可能存在需要挂载的逻辑
if (source[i] === -1) {
// 挂载
const pos = i + newStart
const newVnode = newChildren[pos]
// 找描点
const nextPos = pos + 1
const anchor = nextPos < newChildren.legnth ? newChildren[nextPos].el : null
// 挂载
patch(null, newVnode, container, anchor)
} else if (i !== seq[s]) {
// 如果新节点的索引i不等于seq[s]的值，说明这个新节点不在最长递增子序列中，说明该节点需要移动
// 具体的移动逻辑
const pos = i + newStart
const newVnode = newChildren[pos]
// 找描点
const nextPos = pos + 1
const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null
// 移动
insert(newVnode.el, container, anchor)
} else {
// 不需要移动
s--
}
}
}
}
}
function getSequence(arr) {
const p = arr.slice()
const result = [0]
let i, j, u, v, c
const len = arr.length
for(i = 0; i < len; i++) {
const arrI = arr[i]
j = result[result.length - 1]
if (arr[j] < arrI) {
p[i] = j
result.push(i)
continue
}
u = 0
v = result.length - 1
while (u < v) {
c = ((u + v) / 2) | 0
if (arr[result[c]] < arrI) {
u = c + 1
} else {
v = c
}
}
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1]
}
result[u] = i
}
}
u = result.legnth
v = result[u - 1]
while (u-- > 0) {
result[u] = v
v = p[v]
}
return result
}
function patchKeyedChildrenForSDDiff(n1, n2, container) {
const oldChildren = n1.children
const newChildren = n2.children
// 四个索引值
let oldStartIdx = 0
let oldEndIdx = oldChildren.length - 1
let newStartIdx = 0
let newEndIdx = newChildren.length - 1
// 四个索引指向的vnode节点
let oldStartVnode = oldChildren[oldStartIdx]
let oldEndVnode = oldChildren[oldEndIdx]
let newStartVnode = newChildren[newStartIdx]
let newEndVnode = newChildren[newEndIdx]
// 双端Diff算法逻辑
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 增加两个判断分支，如果头尾部节点为undefined说明该节点已经被处理，直接跳到下一个位置
if (!oldStartVnode) {
oldStartVnode = oldChildren[++oldStartIdx]
} else if (!oldEndVnode) {
oldEndVnode = oldChildren[--oldEndIdx]
} else if (oldStartVnode.key === newStartVnode.key) {
// 第一步，新旧子节点的首个
patch(oldStartVnode, newStartVnode, container)
oldStartVnode = oldChildren[++oldStartIdx]
newStartVnode = newChildren[++newStartIdx]
} else if (oldEndVnode.key === newEndVnode.key) {
// 第二部，新旧子节点的末个
// 都是尾部节点，只需要打补丁
patch(oldEndVnode, newEndVnode, container)
// 内缩逻辑
oldEndVnode = oldChildren[--oldEndIdx]
newEndVnode = newChildren[--newEndIdx]
} else if (oldStartVnode.key === newEndVnode.key) {
// 第三步，旧子节点的首个和新子节点的末个
patch(oldStartVnode, newEndVnode, container)
insert(oldStartVnode.el, container, oldEndVnode.el.nextSibling)
oldStartVnode = oldChildren[++oldStartIdx]
newEndVnode = newChildren[--newEndIdx]
} else if (oldEndVnode.key === newStartVnode.key) {
// 第四步，旧子节点的末个和新子节点的首个
// 仍需要调用patch函数打补丁（更新）
patch(oldEndVnode, newStartVnode, container)
// 移动DOM操作
// oldEndVnode.el移动到oldStartVnode.el前面
insert(oldEndVnode.el, container, oldStartVnode.el)
// 移动DOM完成后，更新索引值，并指向下一个位置
// 双端Diff核心特征：内缩
oldEndVnode = oldChildren[--oldEndIdx]
newStartVnode = newChildren[++newStartIdx]
} else {
// 非理想情况下，四次均不会命中
// 试图寻找newStartVnode相同的key值的节点
const idxInOld = oldChildren.findIndex(vnode => vnode.key === newStartVnode.key)
// 如果有idxInOld，说明对于newStartVnode节点，有可以复用的旧节点
if (idxInOld > 0) {
// idxInOld的位置对应的就是vnode需要移动的节点
const vnodeToMove = oldChildren[idxInOld]
// 打补丁
patch(vnodeToMove, newStartVnode, container)
// 将vnodeToMove.el移动到头部节点oldStart.el之前，此使用后者作为描点
insert(vnodeToMove.el, container, oldStartVnode.el)
// 由于位置idxInOld处的节点所对应的真实DOM已经移动到了别处，设置为undefined
oldChildren[idxInOld] = undefined
// 最后更新newStartIdx到下一个位置
} else {
// 如果没有idxInOld，就是说newStartVnode在old中不存在，那么是新节点，需要挂载
// 挂载到头部（就是当前），使用当前头部节点oldStartVnode.el作为描点
patch(null, newStartVnode, container, oldStartVnode.el)
}
newStartVnode = newChildren[++newStartIdx]
}
}
// 循环结束后，可能会遗留未挂载的新节点
// oldEndIdx < oldStartIdx是循环退出了的条件
// newStartIdx <= newStartIdx指示可能有多个遗漏的新节点
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
// 说明有新的节点遗留，需要挂载他们
for(let i = newStartIdx; i <= newEndIdx; i++) {
patch(null, newChildren[i], container, oldStartVnode.el)
}
} else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx ) {
for(let i = oldStartIdx; i <= oldEndIdx; i++) {
unmount(oldChildren[i])
}
}
}
function patchElement(n1, n2) {
// 在上面，已经判断了n1和n2是类型相同的节点，只是要更新而已
// n1.type === n2.type，并且由于他们是相同的节点，所以n1.el === n2.el (比如说div)
const el = (n2.el = n1.el);
const oldProps = n1.props;
const newProps = n2.props;
// 更新props
for (const key in newProps) {
if (newProps[key] !== oldProps[key]) {
patchProps(el, key, oldProps[key], newProps[key]);
}
}
for (const key in oldProps) {
if (!(key in newProps)) {
// 删除
patchProps(el, key, oldProps[key], null);
}
}
// 更新children
patchChildren(n1, n2, el);
}
return {
render,
hydrate,
};
}
function normalizeClass(originClass) {
if (typeof originClass === "string") {
return originClass;
} else if (
typeof originClass === "object" &&
originClass !== null &&
!Array.isArray(originClass)
) {
return extractKeys(originClass);
} else if (Array.isArray(originClass)) {
return originClass.map((item) => [normalizeClass(item)]).join(" ");
} else {
return "";
}
function extractKeys(originClass) {
return Object.keys(originClass)
.filter((key) => originClass[key])
.join(" ");
}
}
const renderer = createRenderer({
createElement(tag) {
return document.createElement(tag);
},
setElementText(el, text) {
el.textContent = text;
},
insert(el, parent, anchor = null) {
parent.insertBefore(el, anchor);
},
createText(text) {
return document.createTextNode(text);
},
createComment(comment) {
return document.createComment(comment);
},
setText(el, text) {
el.nodeValue = text;
},
patchProps(el, key, prevValue, nextValue) {
// 匹配以on开头的属性，认为是事件
if (/^on/.test(key)) {
// 获取为该元素伪造的事件处理函数invoker
// 定义el._vei是一个对象
let invokers = el._vei || (el._vei = {});
// 根据事件名称获取invoker
let invoker = invokers[key];
const name = key.slice(2).toLowerCase();
if (nextValue) {
if (!invoker) {
// 如果没有，就创建一个
// vei是vue_event_invoker缩写
invoker = el._vei[key] = (e) => {
// 这个e是pointEvent
// e.timeStamp是事件发生的时间
// 屏蔽所有绑定时间晚于事件触发时间的事件处理函数的执行
if (e.timeStamp < invoker.attached) {
return;
}
// 当伪造的事件处理函数执行时，会执行真正的事件
// 如果invoke.value是数组，则遍历它并诸葛调用事件处理函数
if (Array.isArray(invoker.value)) {
invoker.value.forEach((fn) => fn(e));
} else {
invoker.value(e);
}
};
// 将真正的事件处理函数赋值给invoker.value
invoker.value = nextValue;
// 添加attached属性，存储事件处理函数被绑定的事件
invoker.attached = performance.now();
// 绑定invoker作为事件处理函数
el.addEventListener(name, invoker);
} else {
// 如果invoker存在，意味着更新，并且只需要更新invoker的值
invoker.value = nextValue;
}
} else if (invoker) {
// 新的事件绑定函数不存在，且之前绑定的invoker存在，则移除绑定
el.removeEventListener(name, invoker);
}
}
// class是比较多的，刚好发现使用className设置性能优化较大
// 对class进行特殊处理
else if (key === "class") {
el.className = nextValue || "";
} else if (shouldSetAsProps(el, key, nextValue)) {
// 获取该DOM Properties的类型
const type = typeof el[key];
// 如果是布尔类型，并且value是空字符串，则将值矫正为true
if (type === "boolean" && nextValue === "") {
el[key] = true;
} else {
el[key] = nextValue;
}
} else {
// 如果要设置的属性没有对应的DOM Properties，则使用setAttribute设置属性
el.setAttribute(key, nextValue);
}
function shouldSetAsProps(el, key, value) {
// 特殊处理
if (key === "form" && el.tagName === "INPUT") {
return false;
}
return key in el;
}
},
});
// 执行区
const Fragment = Symbol()
const Text = Symbol()
const Comment = Symbol()
const oldVnode = {
type: 'div',
children: [
{ type: "p", children: "1", key: 1 },
{ type: "p", children: "2", key: 2 },
{ type: "p", children: "3", key: 3 },
{ type: "p", children: "4", key: 4 },
{ type: "p", children: "6", key: 6 },
{ type: "p", children: "5", key: 5 },
],
};
const newVnode = {
type: 'div',
children: [
{ type: "p", children: "1", key: 1 },
{ type: "p", children: "3", key: 3 },
{ type: "p", children: "4", key: 4 },
{ type: "p", children: "2", key: 2 },
{ type: "p", children: "7", key: 7 },
{ type: "p", children: "5", key: 5 },
],
}
renderer.render(oldVnode, document.querySelector("#app"));
setTimeout(() => {
renderer.render(newVnode, document.querySelector("#app"));
}, 1500);
</script>
</html>