vue-diff算法详解
前言
jquery时代，我们通过直接操作dom节点进行视图更新，但随着应用的复杂度加大，代码也变得更加难以维护，最简单粗暴的方式就是将整个DOM结构直接innerHTML到修改的页面上，带来的问题是不需要更新的节点也会触发重绘重排，耗费性能大。
可想而知，如果可以每次只更新修改部分，性能上有质的提升，以此为出发点，vue.js更新节点思路是将真实的DOM抽象成一个以JavaScript对象为节点的虚拟DOM树，简称vNode，可以对这棵虚拟树进行节点的创建、删除、修改等操作，在这个过程不需要操作真实DOM，对比操作前后的vNode差异，即diff算法的使用，会得出需要修改的最小单位，然后只对差异部分的真实DOM进行修改
比起每次操作都要触发真实dom的重绘和整块的innerHTML修改，vNode这种方式减少了很多不需要的DOM操作，大大提升了性能。
什么是VNode？
什么是vNode？vNode就是真实dom节点的抽象，简单来说，就是一个模拟树形结构的JavaScript对象，用属性描述真实DOM的各个特性，比如有如下的真实dom：
<div class="test">
<span class="demo">hello,VNode</span>
</div>
复制代码对应的vNode为：
{
elm: div, // 对真实节点的引用
tag: 'div', // 节点的标签
data: { // 一个存储节点属性的对象，对应节点的el[prop]属性，例如onclick , style
class: 'test'
},
children: [ // 存储子节点的数组
{
tag: 'span',
data: {
class: 'demo'
}
text: 'hello,VNode'
}
]
}
复制代码diff 比较
比较新旧节点时，比较只会在同层级进行，不会跨层级比较，复杂度o(n)
示例：
<!-- 之前 -->
<div> <!-- 层级1 -->
<p> <!-- 层级2 -->
<b> aoy </b> <!-- 层级3 -->
<span>diff</Span>
</P>
</div>
<!-- 之后 -->
<div> <!-- 层级1 -->
<p> <!-- 层级2 -->
<b> aoy </b> <!-- 层级3 -->
</p>
<span>diff</Span>
</div>
复制代码如果是手动直接操作dom，我们可能会直接将span节点移到下面，这是最优的操作，但在diff算法中的操作是先移除p里面span节点，再创建一个新的span插到p后面，新的span在层级2，旧的span节点在层级3，属于不同层级的比较
vue2.x diff源码分析
如何修改视图？
当某个数据被修改时，set方法会让Dep调用notify通知所有的订阅者Watcher，Watcher通过调用get方法执行vm._update方法，该方法通过patch给真实的DOM打补丁，更新相应的视图。
Vue.prototype._update = function (vnode, hydrating) {
var vm = this;
var prevEl = vm.$el;
var prevVnode = vm._vnode;
var restoreActiveInstance = setActiveInstance(vm);
vm._vnode = vnode;
// Vue.prototype.__patch__ is injected in entry points
// based on the rendering backend used.
if (!prevVnode) {
// initial render
vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */);
} else {
// updates
vm.$el = vm.__patch__(prevVnode, vnode);
}
restoreActiveInstance();
// update __vue__ reference
if (prevEl) {
prevEl.__vue__ = null;
}
if (vm.$el) {
vm.$el.__vue__ = vm;
}
// if parent is an HOC, update its $el as well
if (vm.$vnode && vm.$parent && vm.$vnode === vm.$parent._vnode) {
vm.$parent.$el = vm.$el;
}
// updated hook is called by the scheduler to ensure that children are
// updated in a parent's updated hook.
};
复制代码流程如下：
具体源码分析
patch函数
核心代码如下：
return function patch (oldVnode, vnode, hydrating, removeOnly) {
// vnode不存在，则直接销毁
if (isUndef(vnode)) {
if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
return
}
let isInitialPatch = false
const insertedVnodeQueue = []
if (isUndef(oldVnode)) {
// empty mount (likely as component), create new root element
// oldVode未定义，则此刻为root节点，创建一个新的节点
isInitialPatch = true
createElm(vnode, insertedVnodeQueue)
} else {
// 标记oldVnode是否有nodeType
const isRealElement = isDef(oldVnode.nodeType)
if (!isRealElement && sameVnode(oldVnode, vnode)) {
// patch existing root node
// 新旧节点值得比较，则只需patchVnode进一步对比
patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
} else {
...
// replacing existing element
const oldElm = oldVnode.elm
const parentElm = nodeOps.parentNode(oldElm)
// create new node
// 创建新节点
createElm(
vnode,
insertedVnodeQueue,
// extremely rare edge case: do not insert if old element is in a
// leaving transition. Only happens when combining transition +
// keep-alive + HOCs. (#4590)
oldElm._leaveCb ? null : parentElm,
nodeOps.nextSibling(oldElm)
)
...
// destroy old node
// 移除旧节点
if (isDef(parentElm)) {
removeVnodes([oldVnode], 0, 0)
} else if (isDef(oldVnode.tag)) {
invokeDestroyHook(oldVnode)
}
}
}
// 添加新节点
invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
return vnode.elm
}
复制代码patch接收参数oldVnode和vnode代码新旧两个节点。
-
vnode为undefined或者null，则直接销毁oldVnode
-
oldVnode未定义，则此刻为root节点，直接创建一个新的节点vnode
-
新旧节点都有定义，判断新旧节点是否值得比较，值得比较则执行patchVnode
/* 判断两个vnode是否是同一个节点，满足以下条件： key相同 tag （当前节点的标签名）相同 asyncFactory(async component factory function) 相同 isComment（是否为注释节点）相同 data（当前节点对应的对象，包含了具体的一些数据信息，是一个VNodeData类型，可以参考VNodeData类型中的数据信息）是否都有定义 当标签是input时，type必须相同 */ function sameVnode (a, b) { return ( a.key === b.key && a.asyncFactory === b.asyncFactory && ( ( a.tag === b.tag && a.isComment === b.isComment && isDef(a.data) === isDef(b.data) && sameInputType(a, b) ) || ( isTrue(a.isAsyncPlaceholder) && isUndef(b.asyncFactory.error) ) ) ) } /* 判断当标签是<input>的时候，type是否相同 某些浏览器不支持动态修改<input>类型，所以他们被视为不同节点 */ function sameInputType (a, b) { if (a.tag !== 'input') return true let i const typeA = isDef(i = a.data) && isDef(i = i.attrs) && i.type const typeB = isDef(i = b.data) && isDef(i = i.attrs) && i.type return typeA === typeB || isTextInputType(typeA) && isTextInputType(typeB) } 复制代码 -
不值得比较，则移除旧节点oldVnode，添加新节点vnode
patchVnode
两个节点值得比较时，会执行patchVnode方法，核心代码如下：
function patchVnode (
oldVnode,
vnode,
insertedVnodeQueue,
ownerArray,
index,
removeOnly
) {
if (oldVnode === vnode) {
return
}
// 让vnode.elm引用到真实的dom，当elm改变时，vnode.elm会同步变化
const elm = vnode.elm = oldVnode.elm
const oldCh = oldVnode.children
const ch = vnode.children
// vnode无文本内容
if (isUndef(vnode.text)) {
if (isDef(oldCh) && isDef(ch)) {
// 新旧节点都有子节点，进行updateChildren对比
if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
} else if (isDef(ch)) {
// 只有vnode有子节点，则清空elm文本内容，并插入新的子节点
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
} else if (isDef(oldCh)) {
// 只有oldVnode有子节点，直接移除旧节点子节点
removeVnodes(oldCh, 0, oldCh.length - 1)
} else if (isDef(oldVnode.text)) {
// 旧节点有文本内容，则直接清空文本内容
nodeOps.setTextContent(elm, '')
}
} else if (oldVnode.text !== vnode.text) {
// 都只有文本节点，且不相等，则直接替换为vnode的文本内容
nodeOps.setTextContent(elm, vnode.text)
}
...
}
复制代码新旧节点比较：
- oldVnode和vnode引用相同，则为同一个对象，不需要改变，直接return
- vnode有文本节点，且新旧节点的文本不相等，则将elm的文本节点设置为vnode.text
- vnode无文本节点前提下：
- 新旧节点都有子节点，则调用updateChildren进行子节点比较
- vnode有子节点，oldVnode无子节点，则清空elm的文本内容，并插入vnode的子节点
- vnode无子节点，oldVnode有子节点，则移除oldVnode的子节点
- oldVnode有文本节点，则直接清空elm文本内容
接下来详细讲解updateChildren
updateChildren
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
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, idxInOld, vnodeToMove, refElm
// removeOnly is a special flag used only by <transition-group>
// to ensure removed elements stay in correct relative positions
// during leaving transitions
const canMove = !removeOnly
if (process.env.NODE_ENV !== 'production') {
checkDuplicateKeys(newCh)
}
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) { // oldStartVnode 为 nul 或者undefined
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
} else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldCh[idxInOld] = undefined
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {
// same key but different element. treat as new element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
}
}
newStartVnode = newCh[++newStartIdx]
}
}
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx) {
removeVnodes(oldCh, oldStartIdx, oldEndIdx)
}
}
// 传入node，遍历oldCh，找到oldCh与node匹配的节点
function findIdxInOld (node, oldCh, start, end) {
for (let i = start; i < end; i++) {
const c = oldCh[i]
if (isDef(c) && sameVnode(node, c)) return i
}
}
复制代码oldVnode 与 vnode
取出子节点，对应oldCh，newCh
过程大概是这样：
- 传入新旧节点的子节点oldCh和newCh
- oldCh和newCh各有两个头尾的变量StartIdx 和 EndIdx，两个变量相互比较，一共有4种方式， 如果这4种方式都没有匹配，如果设置了key，则会用key进行比较，在比较的过程中，变量会忘中间靠，一旦StartIdx > EndIdx ，则说明oldCh和newCh至少有一个遍历完了，就会结束比较。
在比较过程中，只要对dom进行操作都调用nodeOps.insertBefore，功能同原生的insertBefore
具体比较规则：
-
sameVnode(oldStartVnode, newStartVnode)和sameVnode(oldEndVnode,newEndVnode)为true的情况，不需要对dom进行移动
-
当oldStartVnode， newEndVnode值得比较，说明真实dom节点oldStartVnode.elm 跑到oldEndVnode.elm的后面
-
当oldEndVnode，newStartVnode值得比较，说明真实dom节点oldEndVnode.elm移动到oldStartVnode.elm前面
-
若以上四种情况都不满足，先根据oldCh的key生成一个对应的hash表，若newStartVnode设置了key，则在hash表中找到与之key匹配的节点；若没有设置key，则调用
findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)每次遍历oldCh查找与之匹配的节点，不管有木有设置key，都会去查找匹配的节点，只是说若没有设置key，需要遍历差找，效率相对低
再分为两种情况：
- 若通过以上操作找到了匹配的节点，则判断newStartVnode与匹配的节点是否sameVnode，若是，则在真实的dom中移动匹配的节点到oldStartVnode.elm前面，并将旧节点对应的位置置为undefined；若不值得比较，则创建newStartVnode真实节点，并插入到oldStartVnode.elm前面
- 若没有找到匹配的节点，则通过newStartVnode创建真实节点，并插入到oldStartVnode.elm前面
-
在结束时，分两种情况：
oldStartIdx > oldEndIdx，可以认为oldCh先遍历完，此刻newCh可能刚好遍历完，也可能还没遍历完，若未遍历完，newStartIdx和newEndIdx之间的vnode是新增的，refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm若refElm为null，则newStartIdx和newEndIdx之间的vnode插到末尾，若refElm不为null，则这些新增的vnode插到refElm前面。newStartIdx > newEndIdx，可以认为newCh先遍历完。此时oldStartIdx和oldEndIdx之间的vnode在新的子节点里已经不存在了，调用removeVnodes将它们从dom里删除。
可能看这个过程还是很懵，接下来举个例子，演示下diff过程：
假设oldCh，newCh如下：
第1步：
oldS = a oldE = d
newS = b newE = c
复制代码属于上述规则的第4种情况，不管newS是否设置了key，都会去查找与之匹配的节点b，匹配到oldCh中的b，移动b到oldS即a前面，oldCh原先b所在的位置置为null，++newS
第2步：
oldS = a oldE = d
newS = e newE = c
复制代码满足第4种规则，newS = e，在oldCh没有与之匹配的e，则直接将e添加到oldS即a的前面，++newS
第3步：
oldS = a oldE = d
newS = d newE = c
复制代码满足第3种规则，oldE与newS匹配，则将oldE移动到oldS前面，即d移到a前面，–oldE，++newS
第4步：
oldS = a oldE = c
newS = c newE = c
复制代码满足第一种规则，oldE 匹配newE，不需要移动，–oldE，–newE，此刻满足newS>newE，newCh遍历结束，移除oldS，oldE之间的节点，即a，和原先b位置的null
模拟结束。
vue3.x diff算法优化
-
vue2中的虚拟dom是进行全量的对比
-
vue3新增了静态标记（PatchFlag）
在与上次虚拟节点进行对比时，只对比带有patch flag标记的节点，并且可以通过flag信息得知当前节点要对比的具体内容类型
通过一小段dom模板节点来验证：
<div>
<p>锻炼</p>
<p>身体</p>
{{msg}}
</div>
复制代码模板编译后的结果如下：
vue2.x
ffunction render() {
var _vm = this;
var _h = _vm.$createElement;
var _c = _vm._self._c || _h;
return _c('div', [_c('p', [_vm._v("锻炼")]), _c('p', [_vm._v("身体")]), _vm._v(
"\n " + _vm._s(_vm.msg) + "\n")])
}
复制代码vue3.x
import { createVNode as _createVNode, toDisplayString as _toDisplayString, createTextVNode as _createTextVNode, openBlock as _openBlock, createBlock as _createBlock } from "vue"
export function render(_ctx, _cache, $props, $setup, $data, $options) {
return (_openBlock(), _createBlock("div", null, [
_createVNode("p", null, "锻炼"),
_createVNode("p", null, "身体"),
_createTextVNode(" " + _toDisplayString(_ctx.msg), 1 /* TEXT */)
]))
}
复制代码 _createTextVNode(" " + _toDisplayString(_ctx.msg), 1 /* TEXT */)
vue3.x相较于vue2.x，可以看到{{msg}}这个节点，编译器在编译的时候给该节点加了标记1，表示该内容为文本类型，当与上一次虚拟dom进行对比时，这里只会对比带有flag的这个节点，而且通过flag信息也明确了节点内容类型，比起vue2.x的全量对比更高效
Patch Flag类型具体如下：
export const enum PatchFlags {
/**
* Indicates an element with dynamic textContent (children fast path)
*/
TEXT = 1, // 文本
/**
* Indicates an element with dynamic class binding.
*/
CLASS = 1 << 1, // 2 类
/**
* Indicates an element with dynamic style
* The compiler pre-compiles static string styles into static objects
* + detects and hoists inline static objects
* e.g. style="color: red" and :style="{ color: 'red' }" both get hoisted as
* const style = { color: 'red' }
* render() { return e('div', { style }) }
*/
STYLE = 1 << 2, // 4 样式
/**
* Indicates an element that has non-class/style dynamic props.
* Can also be on a component that has any dynamic props (includes
* class/style). when this flag is present, the vnode also has a dynamicProps
* array that contains the keys of the props that may change so the runtime
* can diff them faster (without having to worry about removed props)
*/
PROPS = 1 << 3, // 8
/**
* Indicates an element with props with dynamic keys. When keys change, a full
* diff is always needed to remove the old key. This flag is mutually
* exclusive with CLASS, STYLE and PROPS.
*/
FULL_PROPS = 1 << 4, // 16
/**
* Indicates an element with event listeners (which need to be attached
* during hydration)
*/
HYDRATE_EVENTS = 1 << 5, // 32
/**
* Indicates a fragment whose children order doesn't change.
*/
STABLE_FRAGMENT = 1 << 6, // 64
/**
* Indicates a fragment with keyed or partially keyed children
*/
KEYED_FRAGMENT = 1 << 7, // 128
/**
* Indicates a fragment with unkeyed children.
*/
UNKEYED_FRAGMENT = 1 << 8, // 256
/**
* Indicates an element that only needs non-props patching, e.g. ref or
* directives (onVnodeXXX hooks). since every patched vnode checks for refs
* and onVnodeXXX hooks, it simply marks the vnode so that a parent block
* will track it.
*/
NEED_PATCH = 1 << 9, // 512
/**
* Indicates a component with dynamic slots (e.g. slot that references a v-for
* iterated value, or dynamic slot names).
* Components with this flag are always force updated.
*/
DYNAMIC_SLOTS = 1 << 10, // 1024
/**
* Indicates a fragment that was created only because the user has placed
* comments at the root level of a template. This is a dev-only flag since
* comments are stripped in production.
*/
DEV_ROOT_FRAGMENT = 1 << 11, // 2048
/**
* SPECIAL FLAGS -------------------------------------------------------------
* Special flags are negative integers. They are never matched against using
* bitwise operators (bitwise matching should only happen in branches where
* patchFlag > 0), and are mutually exclusive. When checking for a special
* flag, simply check patchFlag === FLAG.
*/
/**
* Indicates a hoisted static vnode. This is a hint for hydration to skip
* the entire sub tree since static content never needs to be updated.
*/
HOISTED = -1,
/**
* A special flag that indicates that the diffing algorithm should bail out
* of optimized mode. For example, on block fragments created by renderSlot()
* when encountering non-compiler generated slots (i.e. manually written
* render functions, which should always be fully diffed)
* OR manually cloneVNodes
*/
BAIL = -2
}
export const PatchFlagNames = {
[PatchFlags.TEXT]: `TEXT`,
[PatchFlags.CLASS]: `CLASS`,
[PatchFlags.STYLE]: `STYLE`,
[PatchFlags.PROPS]: `PROPS`,
[PatchFlags.FULL_PROPS]: `FULL_PROPS`,
[PatchFlags.HYDRATE_EVENTS]: `HYDRATE_EVENTS`,
[PatchFlags.STABLE_FRAGMENT]: `STABLE_FRAGMENT`,
[PatchFlags.KEYED_FRAGMENT]: `KEYED_FRAGMENT`,
[PatchFlags.UNKEYED_FRAGMENT]: `UNKEYED_FRAGMENT`,
[PatchFlags.NEED_PATCH]: `NEED_PATCH`,
[PatchFlags.DYNAMIC_SLOTS]: `DYNAMIC_SLOTS`,
[PatchFlags.DEV_ROOT_FRAGMENT]: `DEV_ROOT_FRAGMENT`,
[PatchFlags.HOISTED]: `HOISTED`,
[PatchFlags.BAIL]: `BAIL`
}
复制代码思考：
- diff算法updateChildren对比新旧节点的子节点其实是一个对半查找算法，相比于简单从头到尾，可以降低时间复杂度
- diff对比得出最小修改单元，边操作真实的dom进行更新，那为什么不一次性对比完再修改dom呢，假如是这样的话，会有一个问题，需要去记录修改的单元，需要空间去存储这些中间值，增加复杂度，也浪费空间
- 为什么存储虚拟dom树使用js对象，而不是用一个hash，从查找的角度，hash查找更加便捷，但其实从整体的代码来看，对虚拟node主要是一个增删改的操作比较多，而且用hash可能空间上的占用会更大，衡量下，牺牲一点时间上的消耗，相比于用hash空间换时间更加值得。
参考资料：
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
