Vue源码之虚拟DOM和diff算法(二) 手写diff算法
个人练习结果仓库(持续更新):Vue源码解析
patch函数简要流程

新旧节点不是同一个虚拟节点(新节点内容是 text
)
不做过多解释了,代码中已经把每一步都解释了
src \ mysnabbdom \ patch.js
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| import vnode from './vnode.js' import createElement from './createElement.js'
export default function (oldVnode, newVnode) { if (oldVnode.sel === '' || oldVnode.sel === undefined) { oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], '', oldVnode) }
if (oldVnode.sel === newVnode.sel && oldVnode.key === newVnode.key) { console.log('需要精细化比对') } else {
const newDomNode = createElement(newVnode)
const pivot = oldVnode.elm
pivot.parentNode.insertBefore(newDomNode, pivot) pivot.parentNode.removeChild(pivot) } }
|
如果 oldVnode
和 newVnode
不是同一个虚拟节点,那么就直接暴力删除旧的,插入新的。
所以需要一个函数 createElement
,它的功能是将新虚拟节点创建为DOM节点并返回。
src \ mysnabbdom \ createElement.js
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|
export default function (vnode) { const domNode = document.createElement(vnode.sel)
if (vnode.text !== '' && (vnode.children === undefined || vnode.children.length === 0)) { domNode.innerText = vnode.text vnode.elm = domNode }
return vnode.elm }
|
测试
src \ index.js
1 2 3 4 5 6 7 8 9
| import h from './mysnabbdom/h.js' import patch from './mysnabbdom/patch.js'
const myVnode1 = h('h2', {}, '文字')
const container = document.getElementById('container')
patch(container, myVnode1)
|

新旧虚拟节点不是同一个节点,都能实现上树(不只是第一次)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| import h from './mysnabbdom/h.js' import patch from './mysnabbdom/patch.js'
const myVnode1 = h('h2', {}, 'hello')
const container = document.getElementById('container')
patch(container, myVnode1)
const myVnode2 = h('h3', {}, 'hi')
patch(myVnode1, myVnode2)
|

新旧节点不是同一个虚拟节点(新节点内容是子节点)
src \ mysnabbdom \ createElement.js(部分)
1 2 3 4 5 6 7 8 9
| else if (Array.isArray(vnode.children) && vnode.children.length >= 0) { for (let i = 0; i < vnode.children.length; i++) { const childDomNode = createElement(vnode.children[i])
domNode.appendChild(childDomNode) } }
|
测试
src \ index.js
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| import h from './mysnabbdom/h.js' import patch from './mysnabbdom/patch.js'
const myVnode1 = h('ul', {}, h('li', {}, [ h('li', {}, '赤'), h('li', {}, '蓝'), h('li', {}, '紫'), h('li', {}, [ h('div', {}, [ h('ol', {}, [ h('li', {}, '白'), h('li', {}, '黑') ]) ]) ]), ] ))
const container = document.getElementById('container')
patch(container, myVnode1)
|

patch函数精细化比对流程

patch函数
实现简单部分的精细化比对,即不包括流程图中星星部分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| if (oldVnode.sel === newVnode.sel && oldVnode.key === newVnode.key) { patchVnode(oldVnode, newVnode) if (oldVnode === newVnode) { return }
if (newVnode.text !== undefined && (newVnode.children === undefined || newVnode.children.length === 0)) { if (newVnode.text === oldVnode.text) { return }
oldVnode.elm.innerText = newVnode.text } else { if (oldVnode.children !== undefined && oldVnode.children.length > 0) {
console.log('最复杂的情况') } else { oldVnode.elm.innerText = ''
for (let i = 0; i < newVnode.children.length; i++) { let domNode = createElement(newVnode.children[i]) oldVnode.elm.append(domNode) } } }
}
|
测试
oldVnode和newVnode是内存中同一个对象
1 2 3 4 5 6 7 8 9 10
| const myVnode1 = h('h2', {}, 'hello')
const container = document.getElementById('container')
patch(container, myVnode1)
const myVnode2 = myVnode1
patch(myVnode1, myVnode2)
|
newVnode
的内容是 text
, oldVnode
的内容是子节点
1 2 3 4 5 6 7 8 9 10
| const myVnode1 = h('h2', {}, h('p', {}, 'hello'))
const container = document.getElementById('container')
patch(container, myVnode1)
const myVnode2 = h('h2', {}, 'hi')
patch(myVnode1, myVnode2)
|
newVnode
和 oldVnode
的内容都是 text
(只写不同的,相同的自测)
1 2 3 4 5 6 7 8 9 10
| const myVnode1 = h('h2', {}, 'hello')
const container = document.getElementById('container')
patch(container, myVnode1)
const myVnode2 = h('h2', {}, 'hi')
patch(myVnode1, myVnode2)
|
newVnode
的内容是子节点, oldVnode
的内容是 text
1 2 3 4 5 6 7 8 9 10 11 12 13
| const myVnode1 = h('section', {}, 'hello')
const container = document.getElementById('container')
patch(container, myVnode1)
const myVnode2 = h('section', {}, [ h('p', {}, '赤'), h('p', {}, '蓝'), h('p', {}, '紫') ]) patch(myVnode1, myVnode2)
|
diff的子节点更新策略
准备
将精细化比对,最小化更新部分代码封装成函数 patchVnode
修改 vnode.js
文件,将data中的key
取出来
1 2 3 4 5 6 7 8 9 10
| export default function (sel, data, children, text, elm) { return { sel, data, children, text, elm, key: data.key } }
|
原理

如上图所示,一共有四个指针,其中,旧前、旧后指向旧子节点的首尾,新前、新后指向新子节点的首尾。
有四种命中查找:命中一种就不会再进行命中判断了。没有命中的话,则按箭头方向换一种命中查找方式

规则:
前指针
只能向下移动,后指针
只能向上移动
- 当
前指针
在后指针
下面时,循环完毕、(不包括在相同位置的情况)
新增
为了简便,直接把子节点用一个字母来表示
简单版本:

如果旧节点先循环完毕,则此时新前指针、新后指针范围内的节点是新增节点(包括新前指针、新后指针指向的节点)
复杂版本:

如果四种方式的查找都无法命中,则直接在旧子节点中寻找相同key的元素,不存在的话,新增并将该元素追加到旧前指针
之前,新前指针
下移
删除

位置变换

增 + 删 + 位置变化

key一样,节点内容却不同的情况
详解Vue的Diff算法(例6)
原理总结
- 新前旧前:
- 命中,
新前指针
、旧前指针
下移,回到1,继续看有没有命中
- 未命中,继续向下尝试命中
- 新后旧后:
- 命中,
新后指针
、旧后指针
上移,回到1,继续看有没有命中
- 未命中,继续向下尝试命中
- 新后旧前:
- 命中,移动
旧前指针
指向的节点到旧后指针
的后面,并将原位置设置为 undefined
,旧前指针
下移,新后指针
上移
- 未命中,继续向下尝试命中
- 新前旧后:
- 命中,移动
旧后指针
指向的节点到旧前指针
的前面,并将原位置设置为 undefined
,旧后指针
上移,新前指针
下移
- 未命中
- 在旧节点中寻找相同
key
的节点
- 存在
- 在旧节点中找到的和
新前指针
指向的节点是同一个节点的话,将该节点追加到 旧前
之前,并将原位置设置为 undefined
, 新前指针
下移一位
- 在旧节点中找到的和
新前指针
指向的节点不是同一个节点的话,新增 新前指针
指向的节点,将该节点追加到 旧前指针
之前, 新前指针
下移一位
- 不存在
- 新增并将该节点追加到
旧前指针
之前, 新前指针
下移一位
- 循环结束
- 新节点先循环完毕:删除
旧前指针
、旧后指针
之间的节点,包括 旧前
、 旧后
指向的节点
- 旧节点先循环完毕:新增
新前指针
、新后指针
之间的节点到 旧前指针
前,包括 新前
、 新后
指向的节点
实操
src \ patchVnode.js(最复杂的情况,单独抽出来,在updateChildren中操作)
1 2 3 4
| if (oldVnode.children !== undefined && oldVnode.children.length > 0) { updateChildren(oldVnode.elm, oldVnode.children, newVnode.children) }
|
src \ updateChildren.js
没什么难度,看原理总结慢慢写就行了(谨慎点)
阉割版本,只需要 sel
和 key
相同就认为是同一个虚拟节点。(即不需要判断内容是否相同)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
|
import createElement from "./createElement.js" import patchVnode from "./patchVnode.js"
function checkSamVnode(v1, v2) { return v1.sel === v2.sel && v1.key === v2.key }
export default function updateChildren(parentElm, oldCh, newCh) { let oldStartIdx = 0 let oldEndIdx = oldCh.length - 1 let oldStartVnode = oldCh[0] let oldEndVnode = oldCh[oldEndIdx]
let newStartIdx = 0 let newEndIdx = newCh.length - 1 let newStartVnode = newCh[0] let newEndVnode = newCh[newEndIdx]
let map = {};
while (oldStartIdx <= oldEndIdx & newStartIdx <= newEndIdx) { if (oldStartVnode === undefined) { oldStartVnode = oldCh[++oldStartIdx] } if (oldEndVnode === undefined) { oldEndVnode = oldCh[--oldEndIdx] }
if (checkSamVnode(newStartVnode, oldStartVnode)) { console.log('新前旧前命中')
patchVnode(oldStartVnode, newStartVnode) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] } else if (checkSamVnode(newEndVnode, oldEndVnode)) { console.log('新后旧后命中')
patchVnode(oldEndVnode, newEndVnode) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx] } else if (checkSamVnode(newEndVnode, oldStartVnode)) { console.log('新后旧前命中')
patchVnode(oldStartVnode, newEndVnode)
parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibiling) oldStartVnode = undefined
newEndVnode = newCh[--newEndIdx] oldStartVnode = oldCh[++oldStartIdx] } else if (checkSamVnode(newStartVnode, oldEndVnode)) { console.log('新前旧后命中')
patchVnode(oldEndVnode, newStartVnode)
parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm) oldEndVnode = undefined
newStartVnode = newCh[++newStartIdx] oldEndVnode = oldCh[--oldEndIdx] } else { for (let i = oldStartIdx; i <= oldEndIdx; i++) { const item = oldCh[i] if (item === undefined) { continue } const key = item.key map[key] = i }
const indexOld = map[newStartVnode.key] if (indexOld) { const elmToMove = oldCh[indexOld] patchVnode(elmToMove, newStartVnode)
parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm) oldCh[indexOld] = undefined } else { const newDomNode = createElement(newStartVnode) parentElm.insertBefore(newDomNode, oldStartVnode.elm) }
newStartVnode = newCh[++newStartIdx] } }
if (newStartIdx <= newEndIdx) { for (let i = newStartIdx; i <= newEndIdx; i++) { const item = newCh[i] if (item === undefined) { continue; }
const newDomNode = createElement(item)
if (!oldStartVnode) { parentElm.appendChild(newDomNode) } else { parentElm.insertBefore(newDomNode, oldStartVnode.elm) } } } else if (oldStartIdx <= oldEndIdx) { for (let i = oldStartIdx; i <= oldEndIdx; i++) { const item = oldCh[i] if (item === undefined) { continue; } parentElm.removeChild(item.elm) } }
}
|
参考资料:
详解Vue的Diff算法 - 知乎 (zhihu.com)