vue虚拟dom和diff算法
vue的虚拟dom和diff算法
1.虚拟dom
虚拟dom，我的理解就是通过js对象的方式来具体化每一个节点，把dom树上面的每个节点都变为对象里的一个元素，元素的子元素变为子节点，节点上面的class、id、attribute等属性变为data内的值，然后通过dom上面的createElement、appendChild、insertBefore等方法进行生成dom树。
let VNode = {
sel:'div',
data:{
key:0,
props:{},
attrs:{},
class:{},
style:{},
fn:{}
},
text:'虚拟dom',
elm:'<div>虚拟dom</div>'
children:[
{
sel:'div',
data:{
key:0,
props:{},
attrs:{},
class:{},
style:{},
fn:{}
},
text:'虚拟dom children',
elm:'<div>虚拟dom children</div>'
children:[]
}
]
} 2.diff算法
看了diff算法后感觉写的真是巧妙，真正做到了最小量更新 。
diff是当父节点相同时用来对子节点进行最小量更新的算法。
diff算法采用四个指针：旧节点开始指针，旧节点结束指针，新节点开始指针，新节点结束指针；
（上方虚拟节点中的key就是为了在进行diff算法时判断是否是同一个节点便于最小量更新）
while( 旧节点开始指针<=旧节点结束指针&&新节点开始指针<=新节点结束指针 ){
分为以下五种情况：（前四种情况）
「
当进行下面5种判断后可能会出现 新节点[新节点开始指针] 旧节点[旧节点开始指针] 新节点[新节点结束指针] 旧节点[旧节点结束指针]为 空值的情况，如果出现空值则代表当前节点已经处理过了，所以就需要将指针 ++ 或者 --
if( 旧节点[旧节点开始指针] ==null ){
旧节点开始指针++
}else if( 旧节点[旧节点结束指针]==null ){
旧节点结束指针--
}else if( 新节点[新节点开始指针] ==null ){
新节点开始指针++
}else if( 新节点[新节点结束指针] ==null ){
新节点结束指针--
}
」
1、 新节点[新节点开始指针] 对比 旧节点[旧节点开始指针]
如果符合此种情况，则代表 新节点[新节点开始指针] 与 旧节点[旧节点开始指针] 为同一个节点，实行最小量更新，即只更新节点内的属性而不进行dom销毁创建操作，完成更新后 新节点开始指针++ ， 旧节点开始指针++
2、 新节点[新节点结束指针] 对比 旧节点[旧节点结束指针]
如果符合此种情况，则代表 新节点[新节点结束指针] 与 旧节点[旧节点结束指针] 为同一个节点，实行最小量更新，即只更新节点内的属性而不进行dom销毁创建操作，完成更新后 新节点结束指针-- ， 旧节点结束指针--
3、 新节点[新节点结束指针] 对比 旧节点[旧节点开始指针]
如果符合此种情况，则代表 新节点[新节点结束指针] 与 旧节点[旧节点开始指针] 为同一个节点，实行最小量更新，先更新节点内的属性，然后使用insertBefore将 旧节点[旧节点开始指针] 移动到 旧节点[旧节点结束指针] 之后，（注意：此处要移动到 旧节点[旧节点结束节点] 后，而不是所有旧节点后，因为这里的 旧节点结束指针 是会变化的）,
父节点.insertBefore(旧节点[旧节点开始指针].elm, 旧节点[旧节点结束指针].elm.nextSibling) 完成操作后 新节点结束指针-- ， 旧节点开始指针++
4、 新节点[新节点开始指针] 对比 旧节点[旧节点结束指针] 如果符合此种情况，则代表 新节点[新节点开始指针] 与 旧节点[旧节点结束指针] 为同一个节点，实行最小量更新，先更新节点内的属性，然后使用insertBefore将 旧节点[旧节点结束指针] 移动到 旧节点[旧节点开始指针] 前，（注意：此处要移动到 旧节点[旧节点开始指针] 前，而不是所有旧节点前，因为 旧节点开始指针 也是会发生变化的）
父节点.insertBefore(旧节点[旧节点结束指针].elm, 旧节点[旧节点开始指针].elm) 完成操作后， 旧节点结束指针-- ， 新节点开始指针++
5、遍历旧节点数组，生成一个以key为键，index为值的对象为 旧节点keyIndexMap ，然后查询 新节点[新节点开始指针] 中的key是否在 旧节点keyIndexMap 中存在；
如果不存在，则证明 新节点[新节点开始指针] 在旧节点列表中不存在，此时需要创建 新节点[新节点开始指针] 为真实dom，并将其插入至 旧节点[旧节点开始指针] 前(因为此时 新节点[新节点开始指针] 一定处于全部未处理的旧节点前)
父节点.insertBefore(创建dom(新节点[新节点开始指针]), 旧节点[旧节点开始指针].elm) 如果存在则先需要判断 旧节点[旧节点keyIndexMap[新节点 [新节点开始指针][ key] ]] 与 新节点[新节点开始指针] 的sel(标签)是否相同：
如果相同则代表为同一个标签，则进行最小量更新，先更新节点内的属性，然后insertBefore将 旧节点[旧节点keyIndexMap[新节点 [新节点开始指针][ key] ]] 移动到 旧节点[旧节点开始指针] 前，然后将 旧节点[旧节点keyIndexMap[新节点 [新节点开始指针][ key] ]] 设置为 undefined ，代表当前节点处理过了；
如果不同则代表不是同一个标签，则只创建 新节点[新节点开始指针] 的真实dom，然后将其插入到 旧节点[旧节点开始节点] 。
最后 新节点开始指针++
}
当以上循环完成后可能还会出现没有处理到的节点，所以还需要再查找没有处理到的节点：
如果是 新节点开始指针<=新节点结束指针 ，则代表新节点列表内还有没有处理的节点，没有处理的节点全部为新增节点，此时需要遍历 新节点[新节点开始指针] （包含）至 新节点[新节点结束指针] （包含）之间的节点，然后将其添加至 新节点[新节点结束指针+1] 之前 （新节点[新节点结束指针+1]可能为空，新节点[新节点结束指针+1]为空时可添加到最后）
for (let i = 新节点开始节点; i <= 新节点结束节点; i++) {
//insertBefore可以自动识别空值，如果是空值，则插入到最后
父节点.insertBefore(创建dom(新节点[i]), 新节点[新节点结束节点-1]?.elm)
} 如果是 旧节点开始指针<=旧节点结束指针 ，则代表旧节点内还有没有处理的节点，没有处理的节点全部为需要删除节点，此时需要遍历 旧节点[旧节点开始指针] （包含）至 旧节点[旧节点结束指针] （包含） 之间的节点，然后将其全部删除。
for (let i = 旧节点开始指针; i <= 旧节点结束指针; i++) {
旧节点[i] && (父节点.removeChild(旧节点[i].elm))
}
以上就是我对diff算法的理解，下面贴上代码(阉割版，部分情况没有考虑，旨在学习diff算法，可能会有bug)：
//updateChildren文件
import { sameVnode } from './is'
import patchVnode from './patchVnode'
import createElement from './createElement'
export default functionupdateChildren (parentElm, oldCh, newCh) {
console.log('updateChildren')
console.log(parentElm, oldCh, newCh)
//旧前
let oldStartIdx = 0
//新前
let newStartIdx = 0
//旧后
let oldEndIdx = oldCh.length - 1
//新后
let newEndIdx = newCh.length - 1
//旧节点
let oldStartVnode = oldCh[0]
//旧后节点
let oldEndVnode = oldCh[oldEndIdx]
//新节点
let newStartVnode = newCh[0]
//新后节点
let newEndVnode = newCh[newEndIdx]
let keyMap = {}
// 开始循环
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// debugger
console.log('while')
if (oldStartVnode === undefined || oldCh[oldStartIdx] === undefined) {
oldStartVnode = oldCh[++oldStartIdx]
} else if (oldEndVnode === undefined || oldCh[oldEndIdx] === undefined) {
oldEndVnode = oldCh[--oldEndIdx]
} else if (newStartVnode === undefined || newCh[newStartIdx] === undefined) {
newStartVnode = newCh[++newStartIdx]
} else if (newEndVnode === undefined || newCh[newEndIdx] === undefined) {
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newStartVnode)) {
//新前和旧前是同一个节点
console.log('新前和旧前是同一个节点')
patchVnode(oldStartVnode, newStartVnode)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {//旧后和新后是同一个节点
console.log('旧后和新后是同一个节点')
patchVnode(oldEndVnode, newEndVnode)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) {//新后和旧前是同一个节点
console.log('新后和旧前是同一个节点')
patchVnode(oldStartVnode, newEndVnode)
//当新后节点是旧前节点时，此时需要移动节点，移动旧前节点到旧后的后面
parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldEndVnode, newStartVnode)) {//旧后和新前是同一个节点
console.log('旧后和新前是同一个节点')
// 当旧后和新前是同一个节点时，此时需要移动旧后节点到旧前节点的前面
patchVnode(oldEndVnode, newStartVnode)
parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
//前四种都没有命中
if (Object.keys(keyMap).length === 0) {
keyMap = {}
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
const key = oldCh[i].key
if (key) {
keyMap[key] = i
}
}
}
console.log(keyMap)
//寻找当前节点在keyMap中的位置
const idxInOld = keyMap[newStartVnode.key]
console.log(idxInOld)
if (!idxInOld) {
//新节点不在旧节点中
parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
} else {
// 新节点在旧节点中,需要移动
const elmToMove = oldCh[idxInOld]
if (elmToMove.sel !== newStartVnode.sel) {
parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
} else {
patchVnode(elmToMove, newStartVnode)
// 把这项设置为undefined，表示已经移动过了
oldCh[idxInOld] = undefined
parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)
}
}
//指针向后移动
newStartVnode = newCh[++newStartIdx]
}
}
// 继续查询是否有剩余节点
if (newStartIdx <= newEndIdx) {
console.log('新节点还有剩余节点没有处理', newStartIdx, newEndIdx)
const before = newCh[newEndIdx + 1]?.elm
console.log(before)
for (let i = newStartIdx; i <= newEndIdx; i++) {
//insertBefore可以自动识别undefined，如果是undefined，则插入到最后
parentElm.insertBefore(createElement(newCh[i]), before)
}
} else if (oldStartIdx <= oldEndIdx) {
console.log('旧节点还有剩余节点没有处理', oldStartIdx, oldEndIdx)
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
oldCh[i] && (parentElm.removeChild(oldCh[i].elm))
}
}
}
let arr = [1, 1, 2, 35, 9, 2, 9]
arr.reduce((p, n) => {
return p ^ n
}, 0)
//is文件
export function sameVnode (vnode1, vnode2) {
return vnode1.sel === vnode2.sel && vnode1.key === vnode2.key;
} //createElement文件
//真正创建dom
export default function createElement (vnode) {
let domNode = document.createElement(vnode.sel);
if (
vnode.text !== "" &&
(vnode.children === undefined || vnode.children.length === 0)
) {
domNode.innerText = vnode.text;
// 补充elm
} else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
for (let i = 0; i < vnode.children.length; i++) {
domNode.appendChild(createElement(vnode.children[i]));
}
}
vnode.elm = domNode;
return vnode.elm
} //patchVnode文件
import createElement from './createElement'
import updateChildren from './updateChildren'
export default function patchVnode (oldVnode, newVnode) {
// console.log('patchVnode')
if (oldVnode === newVnode) return
if (newVnode.text && (!newVnode.children || newVnode.children.length === 0)) {//判断newVnode的text是否为空，且不等于oldVnode的text，如果满足以上条件，则更新text
oldVnode.text !== newVnode.text && (oldVnode.elm.innerText = newVnode.text);
} else {//newVnode的text为空，则判断newVnode的children是否为空，如果不为空，则更新children
// 新节点没有text属性
if (oldVnode.children && oldVnode.children.length > 0) {
// 老节点有children，新节点也有children
updateChildren(oldVnode.elm, oldVnode.children, newVnode.children);
} else {
// 老的没有children，新的有children
oldVnode.elm.innerHTML = '';
for (let i = 0; i < newVnode.children.length; i++) {
let dom = createElement(newVnode.children[i])
oldVnode.elm.appendChild(dom)
}
}
}
} //patch文件
import vnode from "./vnode";
import createElement from "./createElement";
import patchVnode from './patchVnode'
import { sameVnode } from './is'
export default function (oldVnode, newVnode) {
// console.log(oldVnode, newVnode)
//判断传入的第一个参数，是dom节点还是vnode
if (oldVnode.sel === "" || oldVnode.sel === undefined) {
//传入的如果是dom节点需要包装为虚拟节点
oldVnode = vnode(
oldVnode.tagName.toLowerCase(),
{},
[],
undefined,
oldVnode,
);
}
// 判断oldVnode和newVnode是否是同一个节点
if (sameVnode(oldVnode, newVnode)) {
// console.log("是同一个节点");
patchVnode(oldVnode, newVnode);
} else {
// console.log("不是同一个节点");
let newVnodeElm = createElement(newVnode, oldVnode.elm);
if (oldVnode.elm.parentNode && newVnodeElm) {
oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm);
}
oldVnode.elm.parentNode.removeChild(oldVnode.elm);
}
} //VNode文件
export default function (sel, data, children, text, elm) {
const key = data.key
return {
sel,
data,
children,
text,
elm,
key,
}
} //h文件
import vnode from './vnode.js'
//h('div',{},'文字')
//h('div',{},'[]')
//h('div',{},h())
export default function (sel, data, c) {
//检查参数个数
if (arguments.length !== 3) {
throw new Error('h()参数个数不正确')
}
// 检查C类型
if (typeof c === 'string' || typeof c === 'number') {
return vnode(sel, data, undefined, c, undefined)
} else if (Array.isArray(c)) {
let children = []
for (let i = 0; i < c.length; i++) {
if (!(typeof c[i] === 'object' && c[i].hasOwnProperty('sel'))) {
throw new Error('传入的数组参数中有项不是h函数')
}
children.push(c[i])
}
// 循环结束，children收集完毕
return vnode(sel, data, children, undefined, undefined)
} else if (typeof c === 'object' && c.hasOwnProperty('sel')) {
let children = [c]
return vnode(sel, data, children, undefined, undefined)
} else {
throw new Error('h()参数类型不正确')
}
}